(*
 * johnson.sml - Johnson's All-Pairs Shortest Paths Algorithm
 *   Ronald Garcia
 *   $Id: johnson.sml,v 1.3 2003/08/08 22:15:34 garcia Exp $
 *)

use "property_map.sml";
use "color_map.sml";
use "concepts.sml";
use "graph.sml";
use "adj_list.sml";
use "bellman_ford.sml";
use "dijkstra.sml";
use "utils.sml";

signature JohnsonPSig =
sig
 structure VertexListGraph : VertexListGraphSig
 structure IncidenceGraph : IncidenceGraphSig
 structure EdgeListGraph : EdgeListGraphSig
 structure DistanceMatrix : BasicMatrixSig where type value_t = int
 structure WeightMap : ReadablePropertyMapSig where type value_t = int 
 structure VertexIndexMap : ReadablePropertyMapSig where type value_t = int
 structure Compare : StrictWeakOrderingSig
 structure Combine : BinaryFunctionSig

 sharing EdgeListGraph = VertexListGraph = IncidenceGraph

 sharing type EdgeListGraph.edge_t = WeightMap.key_t
 sharing type VertexIndexMap.key_t = IncidenceGraph.vertex_t
 sharing type DistanceMatrix.key_t = IncidenceGraph.vertex_t
end

functor MakeJohnson (Params : JohnsonPSig) :
sig
    structure VLGraphT : VertexListGraphSig
    structure IGraphT : IncidenceGraphSig
    structure ELGraphT : EdgeListGraphSig
    structure VIMapT : ReadablePropertyMapSig where type value_t = int
    structure DMapsT : BasicMatrixSig where type value_t = int
    structure WMapT : ReadablePropertyMapSig
    structure CmpT : StrictWeakOrderingSig
    structure CmbT : BinaryFunctionSig

    val johnson_all_pairs_shortest_paths :
        VLGraphT.graph_t -> 
        DMapsT.data_t -> WMapT.data_t -> VIMapT.data_t ->
        CmpT.data_t -> CmbT.data_t -> 
        DMapsT.value_t -> DMapsT.value_t -> bool

end
=
struct
    structure VLGraphT = Params.VertexListGraph
    structure IGraphT = Params.IncidenceGraph
    structure ELGraphT = Params.EdgeListGraph
    structure DMapsT = Params.DistanceMatrix
    structure WMapT = Params.WeightMap
    structure VIMapT = Params.VertexIndexMap
    structure CmpT = Params.Compare
    structure CmbT = Params.Combine

    structure BF =
    MakeBellmanF(struct
                 structure EdgeListGraph = ALGraph
                 structure PredecessorMap = NumberMap
                 structure DistanceMap = NumberMap
                 structure WeightMap = EdgeMap
                 structure VertexIndexMap = IndexMap
                 structure Compare = NCompare
                 structure Combine = NCombine
                 end);

    structure DJ =
    MakeDijkstra(struct 
                    structure VertexListGraph = ALGraph
                    structure IncidenceGraph = ALGraph
                    structure PredecessorMap = NumberMap
                    structure DistanceMap = NumberMap
                    structure WeightMap = EdgeMap
                    structure VertexIndexMap = IndexMap
                    structure Compare = NCompare
                    structure Combine = NCombine
                    end);


                                    

fun johnson_all_pairs_shortest_paths 
    graph dmaps wmap imap cmp cmb inf zero = 

    (* Make graph G2 with V2 = V1 + s and E2 = E1 + {s,u}, u in G1,w2(s,u)=0 *)
    let
        val num2 = ((VLGraphT.num_vertices graph)+1)
        val graph2 = ALGraph.create num2
        val wmap2 = EdgeMap.create()
        val wmaph = EdgeMap.create()
        val dmap2 = NumberMap.create(num2)
        val h = NumberMap.create(num2)
        val pmap2 = NumberMap.create(num2)
    in
        (* Build graph for generating w2 *)
        app (fn edge =>
                let
                    val source = ELGraphT.source graph edge
                    val sidx = ((VIMapT.get imap source)+1)            
                    val target = ELGraphT.target graph edge
                    val tidx = ((VIMapT.get imap target)+1)
                in
                    ALGraph.add_edge (graph2, sidx,tidx);
                    EdgeMap.put wmap2 (sidx,tidx) (WMapT.get wmap edge);
                    ()
                end) (ELGraphT.edges graph);
        app (fn vertex => (
                ALGraph.add_edge (graph2, 0, ((VIMapT.get imap vertex)+1));
                EdgeMap.put wmap2 (0,(VIMapT.get imap vertex)+1) zero;
                ())) (VLGraphT.vertices graph);
        (* Call Bellman-Ford on graph G2 *)
        app (fn n => (
              NumberMap.put pmap2 n n;
              NumberMap.put dmap2 n inf
              )) (ALGraph.vertices(graph2));
        NumberMap.put dmap2 0 0;    (* start from s = 0 *)

        if BF.bellman_ford_shortest_paths
               graph2
               (ALGraph.num_vertices(graph2))
               pmap2
               dmap2
               wmap2
               (IndexMap.create())
	       (NCompare.create())
               (NCombine.create()) then (
            let
                val i = ref 0
            in
                while !i < num2 do (
                    NumberMap.put h (!i) (NumberMap.get dmap2 (!i));
                    i := !i + 1)
            end;
            app (fn e =>
                    let
                        val src = ALGraph.source graph2 e
                        val tgt = ALGraph.target graph2 e
                    in
                        EdgeMap.put
                            wmaph e
                            ((EdgeMap.get wmap2 e) +
                             (NumberMap.get h src) -
                             (NumberMap.get h tgt))
                    end) (ALGraph.edges graph2);
            app (fn v => (
                    DJ.dijkstra_shortest_paths 
                        graph2
                        v
                        pmap2
                        dmap2
                        wmaph
                        (IndexMap.create())
                        (NCompare.create())
                        (NCombine.create())
                        999999 
                        0;
                        app (fn v_prime =>
                              let
                                  val verts = VLGraphT.vertices graph
                              in
                                  if (v > 0) andalso (v_prime > 0) then
                                      DMapsT.put
                                          dmaps
                                          (List.nth (verts,v-1),
                                           List.nth (verts,v_prime-1))
                                          ((NumberMap.get dmap2 v_prime) -
                                           (NumberMap.get h v) +
                                           (NumberMap.get h v_prime))
                                  else
                                      ()
                              end) (ALGraph.vertices graph2)))
                (ALGraph.vertices graph2);
                true)
        else
            false
    end
end