(*
 * In place transitive closures.
 *
 * -- Allen
 *)
signature TRANSITIVE_CLOSURE =
sig
   val acyclic_transitive_closure : 
         { + : 'e * 'e -> 'e,
           simple : bool
         } -> ('n,'e,'g) Graph.graph -> unit
   val acyclic_transitive_closure2 : 
         { +   : 'e * 'e -> 'e,
           max : 'e * 'e -> 'e
         } -> ('n,'e,'g) Graph.graph -> unit
   val transitive_closure : 
         ('e * 'e -> 'e) -> ('n,'e,'g) Graph.graph -> unit
end

structure TransitiveClosure : TRANSITIVE_CLOSURE =
struct

   structure G = Graph
   structure A = Array

   (* 
    * Transitive closure for an acyclic graph.
    * Should probably use a better algorithm.
    *)
   fun acyclic_transitive_closure {+,simple} (G' as G.GRAPH G) =
   let val N     = #capacity G ()
       val reach = A.array(N,~1)     (* reach[v] = u iff v -> u *)
       fun visit u =
       let fun visitEdge(v,u,e) =
           let fun trans(w,v,e') =
                   if A.sub(reach,w) = u then ()
                   else (A.update(reach,w,u); #add_edge G (w,u,e + e'))
           in  app trans (#in_edges G v)
           end
           val in_edges = #in_edges G u
       in  if simple then
              app (fn (v,_,_) => A.update(reach,u,v)) in_edges
           else ();
           app visitEdge in_edges
       end
       val list = GraphTopsort.topsort G' (map #1 (#nodes G ()))
   in  app visit list
   end

   fun acyclic_transitive_closure2 {+,max} (G' as G.GRAPH G) =
   let val N      = #capacity G ()
       val reach  = A.array(N,~1)  (* reach[v] = u iff v -> u *)
       val labels = A.array(N,[])  (* l in labels[v] iff v ->l u *)
       fun visit u =
       let fun ins(v,e,nodes) =
               if A.sub(reach,v) = u then 
                  (A.update(labels,v,e::A.sub(labels,v)); nodes)
               else (A.update(reach,v,u); A.update(labels,v,[e]); v::nodes)
           fun init([],nodes) = nodes
             | init((v,u,e)::es,nodes) = init(es,ins(v,e,nodes))
           fun addTrans([],nodes) = nodes
             | addTrans((v,u,e)::es,nodes) = 
               let fun trans([],nodes) = nodes
                     | trans((w,v,e')::es,nodes) = trans(es,ins(w,e + e',nodes))
               in  addTrans(es,trans(#in_edges G v,nodes)) end
           val in_edges = #in_edges G u
           val nodes = init(in_edges,[])        (* insert v -> u *)
           val nodes = addTrans(in_edges,nodes) (* insert w -> u if w -> v *)
           fun foldAll([],es) = es
             | foldAll(v::vs,es) =
                (case A.sub(labels,v) of
                   [] => raise Graph.Graph "acyclic_transitive_closure2"
                 | [e] => foldAll(vs,(v,u,e)::es)
                 | e'::es' => foldAll(vs,(v,u,foldr max e' es')::es)
                )
       in  #set_in_edges G (u,foldAll(nodes,[])) 
       end
       val list = GraphTopsort.topsort G' (map #1 (#nodes G ()))
   in  app visit list
   end

   fun transitive_closure f (G.GRAPH G) = raise Graph.Unimplemented

end