Initial import of l4c

[snipe.git] / util / graph.sml

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