Debian Codegraph @

vendor/incremental-cycles/src/incremental_cycles.ml

raw
1
2 include Incremental_cycles_intf
3
4 module Make (Raw_graph : Raw_graph) : S
5 with type graph := Raw_graph.graph
6 and type vertex := Raw_graph.vertex =
7 struct
8
9 (* This implements the algorithm of incremental cycle detection described in
10 Section 2 of the following paper:
11
12 A New Approach to Incremental Cycle Detection and Related Problems
13
14 Bender, M. A., Fineman, J. T., Gilbert, S., & Tarjan, R. E. (2015).
15
16 https://dl.acm.org/citation.cfm?id=2756553
17 *)
18
19 (******************************************************************************)
20 (* The implementation of the algorithm only depends on an abstract graph
21 structure, here implemented by [Raw_graph].
22
23 Here, [raw_graph.ml] provides a concrete implementation, but the proof
24 only relies on the abstract interface it implements. In the final exported
25 code (see the export/ directory), [Raw_graph] becomes a functor parameter.
26 *)
27
28 open Raw_graph
29
30 (******************************************************************************)
31 (* Interruptible fold_left.
32
33 At each step, the client function decides whether it wants to continue (by
34 using [Continue new_accumulator]) or stop (by using [Break return_value]).
35
36 Ultimately, [interruptible_fold] returns either the last accumulator or the
37 value returned by [Break], along with a boolean indicating whether it was
38 interrupted prematurely.
39 *)
40
41 type ('a, 'b) interruptible_fold_step =
42 | Continue of 'a
43 | Break of 'b
44
45 let rec interruptible_fold f l acc =
46 match l with
47 | [] -> Continue acc
48 | x :: xs ->
49 let res = f x acc in
50 match res with
51 | Continue acc -> interruptible_fold f xs acc
52 | Break _ -> res
53
54 (******************************************************************************)
55 (* The cycle detection algorithm, implemented as an [add_edge] function on
56 [graph], which either successfully inserts the edge, or reports a cycle. *)
57
58 type visit_backward_result =
59 | VisitBackwardCompleted
60 | VisitBackwardInterrupted
61 | VisitBackwardCyclic
62
63 (* Traverse the graph backwards from entries in [stack], looking for [target],
64 and marking explored vertices with [mark].
65
66 If a path to [target] is found, return [VisitBackwardCyclic].
67
68 If [fuel] runs out, return [VisitBackwardInterrupted].
69
70 Otherwise, report that the search was complete with [VisitBackwardCompleted].
71 *)
72 let rec visit_backward
73 (g: graph) (target: vertex) (mark: mark)
74 (fuel: int) (stack: vertex list):
75 visit_backward_result
76 =
77 (* fuel >= 0 *)
78 match stack with
79 | [] -> VisitBackwardCompleted
80 | vertex :: stack ->
81 let res = interruptible_fold (fun y (stack, fuel) ->
82 if fuel = 0 then
83 (* There is no fuel left *)
84 Break true
85 else if is_marked g y mark then
86 (* This vertex has already been visited, skip it *)
87 Continue (stack, fuel - 1)
88 else if vertex_eq y target then
89 (* A path to [target] has been found *)
90 Break false
91 else begin
92 set_mark g y mark;
93 set_parent g y vertex;
94 Continue (y :: stack, fuel - 1)
95 end
96 ) (get_incoming g vertex) (stack, fuel)
97 in
98 match res with
99 | Break timeout ->
100 if timeout then VisitBackwardInterrupted
101 else (set_parent g target vertex; VisitBackwardCyclic)
102 | Continue (stack, fuel) ->
103 visit_backward g target mark fuel stack
104
105 type backward_search_result =
106 | BackwardForward of int * mark
107 | BackwardCyclic
108 | BackwardAcyclic
109
110 (* The whole backwards search phase (Step 2 of the algorithm). Explores the
111 graph backwards starting from [v], and looking for [w].
112 This function mainly calls [visit_backward] and does some post-processing.
113
114 If [w] is found, return [BackwardCyclic].
115
116 If [w] is not found and the algorithm should continue with the forward
117 search phase, return [BackwardForward (new_w_level, visited)], where
118 [new_w_level] is the level at which [w] needs to be put, and [visited]
119 is the mark of vertices that have been visited during the search.
120
121 If [w] is not found and the algorithm should directly skip to the last step,
122 return [BackwardAcyclic].
123 *)
124 let backward_search
125 (fuel: int)
126 (g: graph) (v: vertex) (w: vertex):
127 backward_search_result
128 =
129 let mark = new_mark g in
130 let v_level = get_level g v in
131 set_mark g v mark;
132 match visit_backward g w mark fuel [v] with
133 | VisitBackwardCyclic -> BackwardCyclic
134 | VisitBackwardInterrupted ->
135 (* w_level < v_level + 1 *)
136 BackwardForward (v_level + 1, mark)
137 | VisitBackwardCompleted ->
138 let w_level = get_level g w in
139 if w_level = v_level then
140 BackwardAcyclic
141 else
142 (* w_level < v_level *)
143 BackwardForward (v_level, mark)
144
145 type forward_search_result =
146 | ForwardCyclic of vertex * vertex
147 | ForwardCompleted
148
149 (* Traverse the graph forwards. [stack] contains the current working set of
150 vertices; these are at level [new_level] but their neighbors have not been
151 yet all visited.
152
153 Only follow edges that point to vertices with a smaller level, but update the
154 incoming edges sets for all vertices encountered.
155
156 If a vertex that has been visited during the backward search phase is
157 encountered, return [ForwardCyclic]. Otherwise, return [ForwardCompleted]. *)
158 let rec visit_forward
159 (g: graph) (new_level: int) (visited: mark)
160 (stack: vertex list):
161 forward_search_result
162 =
163 match stack with
164 | [] -> ForwardCompleted
165 | x :: stack ->
166 let res = interruptible_fold (fun y stack ->
167 if is_marked g y visited then
168 (* We found a path to a marked vertex *)
169 Break y
170 else begin
171 let y_level = get_level g y in
172 set_parent g y x;
173 if y_level < new_level then begin
174 set_level g y new_level;
175 clear_incoming g y;
176 add_incoming g y x;
177 Continue (y :: stack)
178 end else if y_level = new_level then begin
179 add_incoming g y x;
180 Continue stack
181 end else (* y_level > new_level *)
182 Continue stack
183 end
184 ) (get_outgoing g x) stack
185 in
186 match res with
187 | Break y -> ForwardCyclic (x, y)
188 | Continue stack -> visit_forward g new_level visited stack
189
190 (* The whole forward search phase (Step 3 of the algorithm). Explores the
191 graph forwards starting from [w], updating the levels and incoming edges
192 sets.
193
194 This function is a simple wrapper over [visit_forward].
195 *)
196 let forward_search
197 (g: graph) (w: vertex) (new_w_level: int) (visited: mark):
198 forward_search_result
199 =
200 clear_incoming g w;
201 set_level g w new_w_level;
202 visit_forward g new_w_level visited [w]
203
204
205 type add_edge_result =
206 | EdgeAdded
207 | EdgeCreatesCycle of (unit -> vertex list)
208
209 let rec list_of_parents
210 (g: graph) (x: vertex) (y: vertex) (acc: vertex list):
211 vertex list
212 =
213 if vertex_eq x y then acc
214 else
215 let p = get_parent g x in
216 let acc' = p :: acc in
217 if vertex_eq p y then acc'
218 else list_of_parents g p y acc'
219
220 (* (z, t) is an edge of the graph such that:
221 - z has been visited by the forward traversal
222 - t has been visited by the backward traversal
223
224 So the path from w to v is of the form:
225 w -> ... -> z -> t -> ... -> v
226
227 [compute_cycle] returns the list of nodes in that path (including w and v).
228 *)
229 let compute_cycle (g: graph) (v: vertex) (w: vertex) (z: vertex) (t: vertex) =
230 list_of_parents g z w (z :: t :: List.rev (list_of_parents g t v []))
231
232 (* The core of the algorithm, wrapping up the previous phases.
233
234 This efficiently checks if there is a path from [w] to [v].
235 If there is none, then it adds the edge [(v, w)] to the graph. *)
236 let add_edge_or_detect_cycle (g: graph) (v: vertex) (w: vertex) =
237 let succeed () =
238 raw_add_edge g v w;
239 if get_level g v = get_level g w then
240 add_incoming g w v;
241 EdgeAdded
242 in
243 if vertex_eq v w then
244 EdgeCreatesCycle (fun () -> [v])
245 else if get_level g w > get_level g v then
246 (* There cannot be a path from [w] to [v], as levels form a
247 pseudo-lexicographic ordering: edges always go to equal or increasing
248 levels. *)
249 succeed ()
250 else match backward_search (get_level g v) g v w with
251 | BackwardCyclic ->
252 EdgeCreatesCycle (fun () -> w :: List.rev (list_of_parents g w v []))
253 | BackwardAcyclic -> succeed ()
254 | BackwardForward (new_level, visited) ->
255 match forward_search g w new_level visited with
256 | ForwardCyclic (z, t) ->
257 EdgeCreatesCycle (fun () -> compute_cycle g v w z t)
258 | ForwardCompleted -> succeed ()
259
260 let add_vertex (g: graph) (v: vertex) =
261 raw_add_vertex g v
262
263 end
264