util/graph.sml

   1 signature GRAPH =
   2 sig
   3   type node
   4   type graph
   5   val addnode : graph -> node -> node list -> graph
   6   val addedge : graph -> node -> node -> graph
   7   val isdag : graph -> node -> bool
   8 end
   9
  10 functor Graph (structure Node : ORD_KEY) :> GRAPH where type node = Node.key =
  11 struct
  12   structure Map = SplayMapFn(Node)
  13   structure Set = HashSetFn(Node)
  14   type node = Node.key
  15   type graph = (Set.set) Map.map
  16
  17   (* val addnode : graph -> node -> node list -> graph
  18    * adds a node given its links (directed)
  19    *)
  20   fun addnode g n nl =
  21     case Map.find (g,n)
  22       of SOME(ns) => Map.insert (g, n, Set.addList (ns, nl))
  23        | NONE => Map.insert (g, n, Set.addList (Set.empty, nl))
  24
  25   fun addedge g n1 n2 =
  26     let
  27       val set1 = case Map.find (g,n1) of SOME(a) => a | NONE => Set.empty
  28       val set2 = case Map.find (g,n2) of SOME(a) => a | NONE => Set.empty
  29     in
  30       Map.insert (Map.insert (g, n2, set2), n1, Set.add (set1, n2))
  31     end
  32
  33   fun isdag g n =
  34     let
  35       val nn = Set.numItems (case Map.find (g,n) of SOME(a) => a | NONE => Set.empty)
  36
  37     in
  38     end
  39
  40 end