------------------------->  GNU Sather - sourcefile  <-------------------------
-- Copyright (C) 1995 by International Computer Science Institute            --
-- This file is part of the GNU Sather library. It is free software; you may --
-- redistribute  and/or modify it under the terms of the GNU Library General --
-- Public  License (LGPL)  as published  by the  Free  Software  Foundation; --
-- either version 2 of the license, or (at your option) any later version.   --
-- This  library  is distributed  in the  hope that it will  be  useful, but --
-- WITHOUT ANY WARRANTY without even the implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE. See Doc/LGPL for more details.       --
-- The license text is also available from:  Free Software Foundation, Inc., --
-- 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA                     --
-------------->  Please email comments to <bug-sather@gnu.org>  <--------------

-- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>

class WTD_DIGRAPH_TEST is
   include TEST;

   main is
      class_name("WeightedDigraphAlgorithms");
      for_the_sake_of_instantiation: LBLD_DIGRAPH{INT,STR,FLT};
      g ::= #WTD_DIGRAPH{STR,INT};
      -- Nodes are STR, Edge and node weights are INTs

      g.add_node("1",1).add_node("2",2).add_node("4",4).add_node("3",3);
      g.add_node("5",5).add_node("10",10);
      g.connect("1","2",3).connect("2","3",5).connect("3","5",8);
      g.connect("1","10",11).connect("1","4",5).connect("4","5",9);
      g.connect("10","5",15);
      --     / 4----\
      --   1 -- 10-- 5
      --    \2--3---/
      #OUT+"Constructed Digraph:"+g.str+"\n";
      mwp: LIST{STR} := #;
      digraph_alg:WTD_DIGRAPH_ALG{STR,INT,WTD_DIGRAPH{STR,INT}};
      loop mwp.append(digraph_alg.max_weight_path_node!(g,"1","5")) end;
      #OUT+mwp.str+"\n";
      r ::= #LIST{STR}(#ARRAY{STR}(|"5","10","1"|));
      test("maxwtpath",mwp.str,r.str);
      g.add_node("7",7);
      g.connect("3","7",10);
      g.connect("7","5",12);
      --    /-4------\
      --   1 -- 10--- 5
      --    \2--3--7--/
      mwp2: LIST{STR} := #;
      loop mwp2.append(digraph_alg.max_weight_path_node!(g,"1","5")) end;
      #OUT+mwp2.str+"\n";
      r2 ::= #LIST{STR}(#ARRAY{STR}(|"5","7","3","2","1"|));
      test("maxwtpath1",mwp2.str,r2.str);
      g2 ::= #WTD_DIGRAPH{INT,FLT}; -- INT labels, FLT weights
      g2.add_node(1,0.0);g2.add_node(2,0.0);g2.add_node(3,0.0);g2.add_node(4,0.0);
      g2.connect(1,2,10.0);
      g2.connect(1,3,11.0);
      g2.connect(2,4,13.0);
      g2.connect(3,4,11.0);
      g2.connect(1,4,1.0);
      #OUT+"Weighted edge graph:\n"+g2.str+"\n";
      --   Thus defining:
      --          1
      --        / | \
      --   10.0/  |  \ 11.0
      --      /   |   \
      --     2    |1.  3
      --      \   |   /
      --  13.0 \  |  / 11.0
      --        \ | /
      --          4
      distances: MAP{INT,FLT}; -- Distances mapping
      preds: MAP{INT,INT};     -- Predecessor mapping
      digraph_alg2:WTD_DIGRAPH_ALG{INT,FLT,WTD_DIGRAPH{INT,FLT}};
      res::=digraph_alg2.bellman_ford(g2,1,out distances, out preds);
      -- distances[4] = 1.0 [3] = 11.0 [2] = 10.0 
      -- preds[4] = 1 [3] = 1 [2] = 1
      #OUT+"Distances:"+distances.str+"\n";
      #OUT+"Predecessors:"+preds.str+"\n";
      test("Distances4",distances[4],1.0);
      test("Distances3",distances[3],11.0);
      test("preds 4",preds[4],1);

      dists2: MAP{INT,FLT};
      preds2: MAP{INT,INT};
      digraph_alg2.dijkstra(g2,1,out dists2, out preds2);
      #OUT+"Distances:"+dists2.str+"\n";
      #OUT+"Predecessors:"+preds2.str+"\n";
      #OUT+"Distances:"+dists2.str+"\n";
      #OUT+"Predecessors:"+preds2.str+"\n";
      finish;
   end;
   
   
end;
