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