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
|
open Graph
(*
The non-reducible example from Bourdoncle paper
Reference is in WeakTopological source
*)
(* Execution should print something like (i and i' can be switched) :
(1 4 1' 4') 2' 3' 2 3 (6 5' 6' 5) *)
module Vertex = struct
type t = string
let compare = Stdlib.compare
let hash = Hashtbl.hash
let equal = ( = )
end
module G = Persistent.Digraph.Concrete (Vertex)
module Wto = WeakTopological.Make (G)
let rec print_element = function
| WeakTopological.Vertex v -> print_string v
| WeakTopological.Component (head, components) ->
(* Printf is for the weak *)
print_string "(";
print_string head;
print_string " ";
print_components components;
print_string ")"
and print_components components =
WeakTopological.fold_left
(fun () elem -> print_element elem; print_string " ")
()
components
let edges = [
"1", "4";
"1", "2";
"2", "3";
"3", "6";
"4", "1'";
"5", "6";
"6", "5'";
"1'", "2'";
"1'", "4'";
"2'", "3'";
"3'", "6'";
"4'", "1";
"5'", "6'";
"6'", "5";
]
let g =
List.fold_left
(fun acc (v, w) -> G.add_edge acc v w)
G.empty edges
let result = Wto.recursive_scc g "1"
let () =
print_components result
|
