test_wtd_digraph.sa

 
---------------------------> Sather 1.1 source file <--------------------------
-- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>
-- Copyright (C) 1995, International Computer Science Institute
-- $Id: test_wtd_digraph.sa,v 1.6 1996/07/13 05:42:08 gomes Exp $
--
-- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
-- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
-- LICENSE contained in the file: Sather/Doc/License of the
-- Sather distribution. The license is also available from ICSI,
-- 1947 Center St., Suite 600, Berkeley CA 94704, USA.


class TEST_WTD_DIGRAPH 
class TEST_WTD_DIGRAPH 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: A_LIST{STR} := #;
      loop mwp.append(g.max_weight_path_node!("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: A_LIST{STR} := #;
      loop mwp2.append(g.max_weight_path_node!("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
      res::=g2.bellman_ford(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};
      g2.dijkstra(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;