(* 
 * This module implements the Floyd/Warshall algorithm for computing
 * all pairs shortest paths.
 *
 * -- Allen
 *)

functor FloydWarshall(Num : ABELIAN_GROUP_WITH_INF) 
   : ALL_PAIRS_SHORTEST_PATHS =
struct

   structure Num = Num
   structure G   = Graph
   structure A   = Array2

   fun all_pairs_shortest_paths{graph=G.GRAPH G,weight} =
   let val N = #capacity G ()
       val D = A.array(N,N,Num.inf)
       val P = A.array(N,N,~1)
       fun init() =
       let fun diag ~1 = ()
             | diag i  = (A.update(D,i,i,Num.zero); diag(i-1))
       in  diag(N-1);
           #forall_edges G (fn e as (i,j,_) =>
            let val w   = weight e
            in  if Num.<(w,A.sub(D,i,j)) then
                   (A.update(P,i,j,i); A.update(D,i,j,w))
                else ()
            end)
       end
       fun l1(k)   = if k < N then (l2(k,0); l1(k+1)) else ()
       and l2(k,i) = if i < N then (l3(k,i,0,A.sub(D,i,k)); l2(k,i+1)) else ()
       and l3(k,i,j,d_ik) = if j < N then 
              let val d_ij = A.sub(D,i,j)
                  val d_kj = A.sub(D,k,j)
                  val x = Num.+(d_ik,d_kj)
              in  if Num.<(x,d_ij) then
                     (A.update(P,i,j,A.sub(P,k,j)); A.update(D,i,j,x))
                  else ();
                  l3(k,i,j+1,d_ik)
              end else ()
   in  init();
       l1(0);
       {dist=D,pred=P}
   end
end