package ocamlgraph

  1. Overview
  2. Docs

Module Cycles.JohnsonSource

Implementation of Johnson's 1975 algorithm for "Finding all the Elementary Cycles of a Directed Graph". It does not do any preprocessing, i.e., no removal of self-loops and no dissection into strongly connected components.

Be aware that a graph with n verticies may contain an exponential number of elementary cycles.

Parameters

module G : G

Signature

Sourceval iter_cycles : (G.V.t list -> unit) -> G.t -> unit

Calls the callback function for every elemental cycle in the given graph. The argument is the list of vertexes in the cycle in reverse order with no duplicates. For each generated list of vertexes v0; ...; vi; vj; ...; vn, there exist edges for all vj to vi, and also from v0 back to vn. Use Sig.G.find_edge to recover the edges.

Sourceval fold_cycles : (G.V.t list -> 'a -> 'a) -> G.t -> 'a -> 'a

A functional interface to iter_cycles.