From b798ac29c37299b2f761243ae92ab8f7c4c4d7f1 Mon Sep 17 00:00:00 2001
From: Paweł Dybiec <pdybiec@stud.cs.uni.wroc.pl>
Date: Tue, 30 Oct 2018 15:32:56 +0100
Subject: Initial commit

---
 source/xi_lib/mygraph.ml | 155 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 155 insertions(+)
 create mode 100644 source/xi_lib/mygraph.ml

(limited to 'source/xi_lib/mygraph.ml')

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