test_ugraph.sa

 
---------------------------> Sather 1.1 source file <--------------------------
-- 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_UGRAPH 
class TEST_UGRAPH is
   include TEST;
   
   main is
      class_name("UGRAPH{STR}");
      g ::= #UGRAPH{STR};
      g.add_node("1");
      g.add_node("2");
      g.add_node("3");
      g.add_node("4");
      g.add_node("5");
      g.add_node("6");
      g.add_node("7");
      g.connect("0","2");
      g.connect("1","2");
      g.connect("1","3");
      g.connect("1","4");
      g.connect("2","5");
      g.connect("3","5");
      g.connect("4","5");
      g.connect("5","6");
      compare_to_standard("UGRAPH",g);
      -- Test the topological sort routine
      t ::= #FLIST{STR};
--      loop t := t.push(g.topo_order!); end;
--      verify_tsort_result(t);
      
      g.add_node("9");
      g.add_node("11");
      g.connect("9","11");
      print_graph("Graph after adding 9,11 and (9,11)",g);
--      sg ::= g.subgraph.delete_some(bind(node_test(_)));
--      compare_to_standard("Subgraph of DIGRAPH", sg);
      
--      g2: DIGRAPH{STR} := #;
--      g2.add_node("0");
--      g2.add_node("1");
--      g2.add_node("2");
--      g2.add_node("3");
--      g2.add_node("4");
--      g2.add_node("5");
--      g2.add_node("6");
--      g2.add_node("7");
--      g2.connect("2","0");
--      g2.connect("2","1");
--      g2.connect("3","1");
--      g2.connect("4","1");
--      g2.connect("5","2");
--      g2.connect("5","3");
--      g2.connect("5","4");
--      g2.connect("6","5");
--      rg ::= g2.reverse_graph;
--      compare_to_standard("Reverse adaptor for DIGRAPH", rg);
      g2 ::= #UGRAPH{INT};
      g2.add_node(1);
      g2.add_node(2);
      g2.add_node(3);
      g2.add_node(4);
      g2.add_node(5);
      g2.connect(1,2);
      g2.connect(2,4);
      g2.connect(2,5);
      g2.connect(1,3);
      --    1
      --    /\
      --   2   3
      -- /  \
      --4    5
      t2 ::= #FLIST{INT};
      loop t2 := t2.push(g2.dfs!(1)) end;
      r1 ::= #FLIST{INT}(|1,2,4,5,3|);
      r2 ::= #FLIST{INT}(|1,3,2,4,5|);
      r3 ::= #FLIST{INT}(|1,2,5,4,3|);
      r4 ::= #FLIST{INT}(|1,3,2,5,4|);
      test("Dfs:"+t2.str, 
	   t2.equals(r1) or t2.equals(r2) or t2.equals(r3) or t2.equals(r4), 
	   true);
      finish;
   end;
  
   node_test(s: STR): BOOL is
      if (s.cursor.int > 7) then return(true)
      else return(false) end;
   end;   
   
   print_graph(msg: STR,g: $UGRAPH{STR}) is
      #OUT+"\n*****************\n"+msg+"\n*****************\n";
      #OUT+g.str
	    +"\n********************************************\n";
   end;      
      
   compare_to_standard(msg: STR, g: $UGRAPH{STR}) is
      -- Test a graph assuming that it is of the form below
      --      0   1     7
      --       \/\ \
      --       2  3 4
      --       |/ /
      --       5
      --       |
      --       6
      print_graph(msg,g);
      na: ARRAY{STR} := #(g.n_nodes);
      loop na.set!(g.node!) end;
      -- na ::= g.nodes.as_array;
      correct_nl ::= #FLIST{STR};
      correct_nl := correct_nl.push("0").push("1").push("2")
	    .push("3").push("4").push("5").push("6").push("7");
      test("test nodes",na.size.str,8.str);      
      -- Make sure all the nodes are returned
      loop
	 e ::= na.elt!;
	 test("node:"+e,correct_nl.contains(e).str,true.str);
      end;
      test("test node 0",g.has_node("0").str,true.str);      
      test("test node 1",g.has_node("1").str,true.str);      
      test("test node 2",g.has_node("2").str,true.str);      
      test("test node 3" ,g.has_node("3").str,true.str);      
      test("test node 4",g.has_node("4").str,true.str);      
      test("test node 5",g.has_node("5").str,true.str);      
      test("test node 6",g.has_node("6").str,true.str);      
      test("test node 9",g.has_node("9").str,false.str);      
      test("has_edge 0 2",g.has_edge(#UEDGE{STR}("0","2")).str,true.str);
      test("has_edge 0 7",g.has_edge(#UEDGE{STR}("0","7")).str,false.str);
   end;
   
   verify_tsort_result(l: FLIST{STR}) is
      -- Check whether the result of the tsort are ok
      -- The actual order will vary depending on the order in
      -- which children are stored. 
      first_nodes ::= l.sublist(0,3);
      second_nodes ::= l.sublist(3,3);
      third_nodes ::= l.sublist(6,2);
      test("First nodes contains 0",first_nodes.contains("0").str,true.str);
      test("First nodes contains 1",first_nodes.contains("1").str,true.str);
      test("First nodes contains 7",first_nodes.contains("7").str,true.str);
      test("Second nodes contains 2",second_nodes.contains("2").str,true.str);
      test("Second nodes contains 3",second_nodes.contains("3").str,true.str);
      test("Second nodes contains 4",second_nodes.contains("4").str,true.str);
      test("Last nodes",third_nodes.str,"5,6");
   end;

end; -- class TEST_DIGRAPH