equal
deleted
inserted
replaced
51 val restrict: (key -> bool) -> 'a T -> 'a T |
51 val restrict: (key -> bool) -> 'a T -> 'a T |
52 val merge: ('a * 'a -> bool) -> 'a T * 'a T -> 'a T (*exception DUP*) |
52 val merge: ('a * 'a -> bool) -> 'a T * 'a T -> 'a T (*exception DUP*) |
53 val join: (key -> 'a * 'a -> 'a) (*exception DUP/SAME*) -> |
53 val join: (key -> 'a * 'a -> 'a) (*exception DUP/SAME*) -> |
54 'a T * 'a T -> 'a T (*exception DUP*) |
54 'a T * 'a T -> 'a T (*exception DUP*) |
55 val irreducible_paths: 'a T -> key * key -> key list list |
55 val irreducible_paths: 'a T -> key * key -> key list list |
56 val all_paths: 'a T -> key * key -> key list list |
|
57 exception CYCLES of key list list |
56 exception CYCLES of key list list |
58 val add_edge_acyclic: key * key -> 'a T -> 'a T (*exception UNDEF | CYCLES*) |
57 val add_edge_acyclic: key * key -> 'a T -> 'a T (*exception UNDEF | CYCLES*) |
59 val add_deps_acyclic: key * key list -> 'a T -> 'a T (*exception UNDEF | CYCLES*) |
58 val add_deps_acyclic: key * key list -> 'a T -> 'a T (*exception UNDEF | CYCLES*) |
60 val merge_acyclic: ('a * 'a -> bool) -> 'a T * 'a T -> 'a T (*exception CYCLES*) |
59 val merge_acyclic: ('a * 'a -> bool) -> 'a T * 'a T -> 'a T (*exception CYCLES*) |
61 val topological_order: 'a T -> key list |
60 val topological_order: 'a T -> key list |
268 if eq_key (x, z) then cons (z :: path) |
267 if eq_key (x, z) then cons (z :: path) |
269 else fold (paths (z :: path)) (irreducible_preds G X path z); |
268 else fold (paths (z :: path)) (irreducible_preds G X path z); |
270 in if eq_key (x, y) andalso not (is_edge G (x, x)) then [[]] else paths [] y [] end; |
269 in if eq_key (x, y) andalso not (is_edge G (x, x)) then [[]] else paths [] y [] end; |
271 |
270 |
272 |
271 |
273 (* all paths *) |
|
274 |
|
275 fun all_paths G (x, y) = |
|
276 let |
|
277 val (_, X) = reachable (imm_succs G) [x]; |
|
278 fun paths path z = |
|
279 if not (null path) andalso eq_key (x, z) then [z :: path] |
|
280 else if Keys.member X z andalso not (member eq_key path z) |
|
281 then maps (paths (z :: path)) (immediate_preds G z) |
|
282 else []; |
|
283 in paths [] y end; |
|
284 |
|
285 |
|
286 (* maintain acyclic graphs *) |
272 (* maintain acyclic graphs *) |
287 |
273 |
288 exception CYCLES of key list list; |
274 exception CYCLES of key list list; |
289 |
275 |
290 fun add_edge_acyclic (x, y) G = |
276 fun add_edge_acyclic (x, y) G = |