Debian Codegraph @

vendor/incremental-cycles/src/incremental_cycles.mli

raw
1 (** An incremental cycle detection algorithm for directed graphs. *)
2
3 (** {1 Functorial interface} *)
4
5 (** Signature for the graph data structure on which the algorithm operates.
6 It is the input signature of the [Make] functor.
7
8 This corresponds to a standard imperative directed graph structure.
9
10 Additionally, extra meta-data is associated to each node, to hold internal
11 data of the cycle detection algorithm. The meta-data is written and accessed
12 by the algorithm through the corresponding [set_*] and [get_*] functions; it
13 must not be modified otherwise.
14
15 The standard graph operations provided by [Raw_graph] are:
16 - adding a new vertex;
17 - adding a new edge between two existing vertices;
18 - returning the list of successors of a vertex;
19 - testing for equality of vertices.
20
21
22 The extra meta-data that [Raw_graph] must provide is:
23 - Vertices can be marked, and it must be possible to generate fresh marks.
24 Intuitively, a mark can be implemented as an integer, and generating a
25 fresh mark as incrementing some mark counter.
26 - Each vertex has an associated integer "level", which can be read and set.
27 - Each vertex has an associated list of "incoming" vertices.
28 - Each vertex has an associated "parent", which can be read and set to an
29 other vertex of the graph.
30
31 No particular assumption should be made by the implementor of [Raw_graph]
32 about the contents of these fields.
33 *)
34 module type Raw_graph = Incremental_cycles_intf.Raw_graph
35
36 (** Output signature of the functor [Incremental_cycles.Make]. *)
37 module type S = Incremental_cycles_intf.S
38
39 (** The algorithm is provided as a functor parameterized over the directed graph
40 implementation [Raw_graph].
41
42 NB: The algorithm does not allocate or maintain (long-lived) data itself: it
43 only mutates the graph by calling the operations provided by [Raw_graph].
44 *)
45 module Make (Raw_graph : Raw_graph) : S
46 with type graph := Raw_graph.graph
47 and type vertex := Raw_graph.vertex