1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
(** Directed Acyclic Graph (DAG) implementation
This module provides a bi-directional DAG where each node maintains
references to both its parents and children for efficient traversal. *)
(** The type of a DAG with nodes of type ['a] *)
type 'a t
(** Internal node structure - abstract type for encapsulation *)
type 'a dagnode
(** {1 Exceptions} *)
exception DagNodeNotFound
(** Raised when attempting to access a node that doesn't exist in the DAG *)
exception DagNodeAlreadyExists
(** Raised when attempting to exclusively add a node that already exists *)
(** {1 Construction} *)
val init : unit -> 'a t
(** [init ()] creates a new empty DAG *)
val add_node : 'a -> 'a t -> unit
(** [add_node n dag] adds node [n] to [dag]. Does nothing if [n] already exists *)
val add_node_exclusive : 'a -> 'a t -> unit
(** [add_node_exclusive n dag] adds node [n] to [dag].
@raise DagNodeAlreadyExists if [n] already exists *)
val add_edge : 'a -> 'a -> 'a t -> unit
(** [add_edge a b dag] adds a directed edge from [a] to [b].
[a] becomes a parent of [b], and [b] becomes a child of [a].
Creates nodes [a] and [b] if they don't exist *)
val add_edges : ('a * 'a) list -> 'a t -> unit
(** [add_edges edges dag] adds multiple edges to [dag].
Equivalent to [List.iter (fun (a,b) -> add_edge a b dag) edges] *)
val add_edges_connected : 'a list -> 'a t -> unit
(** [add_edges_connected [n1; n2; n3; ...]] creates a chain of edges:
n1 -> n2 -> n3 -> ... *)
val add_children_edges : 'a -> 'a list -> 'a t -> unit
(** [add_children_edges parent children dag] adds edges from [parent]
to each element in [children] *)
val del_edge : 'a -> 'a -> 'a t -> unit
(** [del_edge a b dag] removes the edge from [a] to [b] if it exists *)
(** {1 Queries} *)
val length : 'a t -> int
(** [length dag] returns the number of nodes in [dag] *)
val exists_node : 'a -> 'a t -> bool
(** [exists_node n dag] returns [true] if node [n] exists in [dag] *)
val has_edge : 'a -> 'a -> 'a t -> bool
(** [has_edge a b dag] returns [true] if there is an edge from [a] to [b] *)
val get_node : 'a t -> 'a -> 'a dagnode
(** [get_node dag n] returns the node structure for [n].
@raise DagNodeNotFound if [n] doesn't exist *)
val get_nodes : 'a t -> 'a list
(** [get_nodes dag] returns all nodes in [dag] *)
val get_leaves : 'a t -> 'a list
(** [get_leaves dag] returns all nodes with no children *)
val get_roots : 'a t -> 'a list
(** [get_roots dag] returns all nodes with no parents *)
val get_children : 'a t -> 'a -> 'a list
(** [get_children dag n] returns the immediate children of [n].
@raise DagNodeNotFound if [n] doesn't exist *)
val get_parents : 'a t -> 'a -> 'a list
(** [get_parents dag n] returns the immediate parents of [n].
@raise DagNodeNotFound if [n] doesn't exist *)
val get_children_full : 'a t -> 'a -> 'a list
(** [get_children_full dag n] returns all descendants of [n] (transitive closure).
@raise DagNodeNotFound if [n] doesn't exist *)
val is_children : 'a t -> 'a -> 'a -> bool
(** [is_children dag a b] returns [true] if [b] is an immediate child of [a] *)
val is_children_full : 'a t -> 'a -> 'a -> bool
(** [is_children_full dag a b] returns [true] if [b] is a descendant of [a]
(checks transitive closure) *)
(** {1 Operations} *)
val copy : 'a t -> 'a t
(** [copy dag] creates a deep copy of [dag] *)
val subset : 'a t -> 'a list -> 'a t
(** [subset dag roots] creates a new DAG containing only the subgraph
reachable from [roots] *)
val merge : 'a t -> 'a t -> 'a list
(** [merge dest src] merges [src] into [dest] and returns a list of
duplicate nodes (nodes that existed in both DAGs) *)
val transitive_reduction : 'a t -> 'a t
(** [transitive_reduction dag] returns a new DAG with redundant edges removed.
An edge (a,c) is redundant if there exists a path a -> b -> c.
WARNING: O(v³) complexity - use with care *)
(** {1 Debugging} *)
val dump : ('a -> string) -> 'a t -> unit
(** [dump to_string dag] prints the DAG structure to stdout for debugging *)
val to_dot : ('a -> string) -> string -> bool -> 'a t -> string
(** [to_dot to_string name from_leaf dag] generates a GraphViz DOT representation.
- [to_string]: function to convert nodes to strings
- [name]: name of the graph
- [from_leaf]: if [true], edges point from leaves to roots *)
|
