| 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 |