(*
 * graph251.sml - Graph of Figure 25.1 from CLR 2nd ed, p. 626
 *   Ronald Garcia
 *   $Id: graph251.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 "adj_list.sml";
use "utils.sml";

(* Definitions introduced
 * g - ALGraph
 * pmap - Predecessor Map
 * dmap - Distance Map
 * wmap - Weight Map
 *)

(* Graph with |V| = 5, |E| = 9 *)
val g = ALGraph.create(5);

(* See Figure 25.1 of CLR *)
ALGraph.add_edge(g,0,1);
ALGraph.add_edge(g,0,2);
ALGraph.add_edge(g,0,3);
ALGraph.add_edge(g,1,3);
ALGraph.add_edge(g,1,4);
ALGraph.add_edge(g,2,1);
ALGraph.add_edge(g,3,4);
ALGraph.add_edge(g,4,0);
ALGraph.add_edge(g,4,2);


val wmap = EdgeMap.create();
EdgeMap.put wmap (0,1) 3;
EdgeMap.put wmap (0,2) 8;
EdgeMap.put wmap (0,3) ~4;
EdgeMap.put wmap (1,3) 7;
EdgeMap.put wmap (1,4) 1;
EdgeMap.put wmap (2,1) 4;
EdgeMap.put wmap (3,4) 6;
EdgeMap.put wmap (4,0) 2;
EdgeMap.put wmap (4,2) ~5;


val dmap = NumberMap.create(5);
NumberMap.put dmap 0 0;
NumberMap.put dmap 1 9999;
NumberMap.put dmap 2 9999;
NumberMap.put dmap 3 9999;
NumberMap.put dmap 4 9999;

val pmap = NumberMap.create(5);
NumberMap.put pmap 0 0;
NumberMap.put pmap 1 1;
NumberMap.put pmap 2 2;
NumberMap.put pmap 3 3;
NumberMap.put pmap 4 4;