diff options
author | Paweł Dybiec <pdybiec@stud.cs.uni.wroc.pl> | 2018-10-30 15:32:56 +0100 |
---|---|---|
committer | Paweł Dybiec <pdybiec@stud.cs.uni.wroc.pl> | 2018-10-30 15:32:56 +0100 |
commit | b798ac29c37299b2f761243ae92ab8f7c4c4d7f1 (patch) | |
tree | eb9b9cc9be294fe5bd3acf9a342098ffc0ea06e5 /source/xi_lib/mygraph.ml |
Initial commit
Diffstat (limited to 'source/xi_lib/mygraph.ml')
-rw-r--r-- | source/xi_lib/mygraph.ml | 155 |
1 files changed, 155 insertions, 0 deletions
diff --git a/source/xi_lib/mygraph.ml b/source/xi_lib/mygraph.ml new file mode 100644 index 0000000..5836414 --- /dev/null +++ b/source/xi_lib/mygraph.ml @@ -0,0 +1,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 \ No newline at end of file |