blob: 5836414b72cc0e309790144b1f951789fff37cc5 (
plain) (
blame)
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
(* Just to keep compatibility with Ocamlgraph *)
module type SElem = sig
type t
val compare: t -> t -> int
val hash: t -> int
val equal: t -> t -> bool
end
module MakeBidirectional(V:SElem) = struct
type t =
{ g_successors: (V.t, V.t Hashset.t) Hashtbl.t
; g_predecessors: (V.t, V.t Hashset.t) Hashtbl.t
; g_vertices : V.t Hashset.t
}
let create () =
{ g_successors = Hashtbl.create 101
; g_predecessors = Hashtbl.create 101
; g_vertices = Hashset.create ()
}
let nb_vertex g =
Hashset.length g.g_vertices
let _assert_mem g v =
assert (Hashset.mem g.g_vertices v)
let add_vertex g v =
if not @@ Hashset.mem g.g_vertices v then begin
Hashset.add g.g_vertices v;
Hashtbl.replace g.g_successors v @@ Hashset.create ();
Hashtbl.replace g.g_predecessors v @@ Hashset.create ()
end
let _succ g v =
Hashtbl.find g.g_successors v
let _pred g v =
Hashtbl.find g.g_predecessors v
let remove_vertex g v =
_assert_mem g v;
Hashset.remove g.g_vertices v;
let remove_pred w =
let pred = _pred g w in
Hashset.remove pred v
in
let succ = _succ g v in
Hashset.iter remove_pred succ
let add_edge g v w =
add_vertex g v;
add_vertex g w;
let v_succ = _succ g v in
let w_pred = _pred g w in
Hashset.add v_succ w;
Hashset.add w_pred v
let fold_vertex f g acc =
Hashset.fold f g.g_vertices acc
let succ g v =
_assert_mem g v;
List.of_seq @@ Hashset.to_seq @@ _succ g v
let pred g v =
_assert_mem g v;
List.of_seq @@ Hashset.to_seq @@ _pred g v
let remove_edge g v w =
_assert_mem g v;
_assert_mem g w;
let v_succ = _succ g v in
let w_pred = _pred g w in
Hashset.remove v_succ w;
Hashset.remove w_pred v
end
module MakeUndirected(V:SElem) = struct
type t =
{ g_neighbours: (V.t, V.t Hashset.t) Hashtbl.t
}
let create () =
{ g_neighbours = Hashtbl.create 101
}
let nb_vertex g =
Hashtbl.length g.g_neighbours
let _assert_mem g v =
assert (Hashtbl.mem g.g_neighbours v)
let add_vertex g v =
if not @@ Hashtbl.mem g.g_neighbours v then begin
Hashtbl.replace g.g_neighbours v @@ Hashset.create ();
end
let _nb g v =
Hashtbl.find g.g_neighbours v
let remove_vertex g v =
_assert_mem g v;
let remove_pred w =
let pred = _nb g w in
Hashset.remove pred v
in
let succ = _nb g v in
Hashset.iter remove_pred succ;
Hashtbl.remove g.g_neighbours v
let add_edge g v w =
add_vertex g v;
add_vertex g w;
let v_nb = _nb g v in
let w_nb = _nb g w in
Hashset.add v_nb w;
Hashset.add w_nb v
let fold_vertex f g acc =
let h k _ = f k in
Hashtbl.fold h g.g_neighbours acc
let succ g v =
_assert_mem g v;
List.of_seq @@ Hashset.to_seq @@ _nb g v
let fold_edges f g acc =
let h v nb acc =
let f' w acc = f w v acc in
Hashset.fold f' nb acc
in
Hashtbl.fold h g.g_neighbours acc
let iter_edges f g =
let h v nb =
let f' w = f w v in
Hashset.iter f' nb
in
Hashtbl.iter h g.g_neighbours
let out_degree g v =
_assert_mem g v;
Hashset.length @@ _nb g v
end
|
