(*
 * johnson_test.sml - Test case for Johnson's algorithm
 *   Ronald Garcia
 *   $Id: johnson_test.sml,v 1.2 2003/05/02 20:03:39 jewillco Exp $
 *)

(* Copyright 2003, Trustees of Indiana University
 * Please see the license in the file ../LICENSE
 *)

use "johnson.sml";
use "graph251.sml";



structure Johnson = 
MakeJohnson(struct 
            structure VertexListGraph = ALGraph
            structure IncidenceGraph = ALGraph
            structure EdgeListGraph = ALGraph
            structure DistanceMatrix = NumberMatrix
            structure WeightMap = EdgeMap
            structure VertexIndexMap = IndexMap
            structure Compare = NCompare
            structure Combine = NCombine
            end);


(* Dijkstra's does the following internally, Bellman-Ford does not. *)
app (fn n => (NumberMap.put pmap n n;
              NumberMap.put dmap n 99999)) (ALGraph.vertices(g));
NumberMap.put dmap (hd (ALGraph.vertices(g))) 0;              

val n = (ALGraph.num_vertices(g));
val dmaps =  (NumberMatrix.create(n,n));
Johnson.johnson_all_pairs_shortest_paths
    g
    dmaps
    wmap
    (IndexMap.create())
    (NCompare.create())
    (NCombine.create())
    99999
    0;

(* Now dmaps holds the distance values. *)