Initial import of l4c

[snipe.git] / util / graph.sml

diff --git a/util/graph.sml b/util/graph.sml
new file mode 100644 (file)
index 0000000..502cd7c
--- /dev/null
+++ b/util/graph.sml
@@ -0,0 +1,40 @@
+signature GRAPH =
+sig
+  type node
+  type graph
+  val addnode : graph -> node -> node list -> graph
+  val addedge : graph -> node -> node -> graph
+  val isdag : graph -> node -> bool
+end
+
+functor Graph (structure Node : ORD_KEY) :> GRAPH where type node = Node.key =
+struct
+  structure Map = SplayMapFn(Node)
+  structure Set = HashSetFn(Node)
+  type node = Node.key
+  type graph = (Set.set) Map.map
+
+  (* val addnode : graph -> node -> node list -> graph
+   * adds a node given its links (directed)
+   *)
+  fun addnode g n nl =
+    case Map.find (g,n)
+      of SOME(ns) => Map.insert (g, n, Set.addList (ns, nl))
+       | NONE => Map.insert (g, n, Set.addList (Set.empty, nl))
+
+  fun addedge g n1 n2 =
+    let
+      val set1 = case Map.find (g,n1) of SOME(a) => a | NONE => Set.empty
+      val set2 = case Map.find (g,n2) of SOME(a) => a | NONE => Set.empty
+    in
+      Map.insert (Map.insert (g, n2, set2), n1, Set.add (set1, n2))
+    end
+
+  fun isdag g n =
+    let
+      val nn = Set.numItems (case Map.find (g,n) of SOME(a) => a | NONE => Set.empty)
+      
+    in
+    end
+
+end