------------------------->  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>  <--------------

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

class DIGRAPH_TEST is
   include TEST;

   indi(s,d: INT): DIEDGE{INT} is return #DIEDGE{INT}(s,d) end;
   
   main is
      -- Tests of digraph classes
      class_name("DIGRAPH{STR}");
      g ::= #DIGRAPH{STR};
      -- Create a directed graph of the form
      --      0  1     7
      --       \/\ \
      --       2  3 4
      --       | / /
      --       |/ /
      --       |/
      --       5
      --       |
      --       6

      g.add_node("0");  g.add_node("1"); g.add_node("7");
      g.connect("0","2");   g.connect("1","2");  g.connect("1","3");
      g.connect("1","4");
      g.add_node("2"); g.add_node("3"); g.add_node("4"); 
      g.connect("2","5");
      g.connect("3","5");
      g.connect("4","5");      
      g.add_node("5");
      g.connect("5","6");
      g.add_node("6");
      
      -- Make sure the graph was constructed right
      compare_to_standard("Original g",g);
      
      gcopy ::= g.copy;
      test("equal:"+gcopy,g.equals(gcopy),true);
      -- Test the topological sort routine
      ordering: FLIST{STR} := #FLIST{STR}(|"0","1","7","2","3","4","5","6"|);

      alg: DIGRAPH_ALG{STR,DIGRAPH{STR}};
      -- g_alg ::= #DIGRAPH_ALG_WRAP{STR,DIGRAPH{STR}}(g);
      -- test("is_topo_order",g_alg.is_topo_order(ordering),true);
      test("is_topo_order",g.is_topo_order(ordering),true);
      ordering2: FLIST{STR} := #FLIST{STR}(|"0","2","1"|);
      test("is_topo_order",g.is_topo_order(ordering2),false);
      t ::= #FLIST{STR};
      loop t := t.push(g.topo_order!); end;
      test("topo_order!:"+t.str,g.is_topo_order(t), true);
      
      g.add_node("9");
      g.add_node("11");
      g.connect("9","11");
      print_graph("g after adding 9,11 and (9,11)",g);

      g2 ::= #DIGRAPH{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
      #OUT+"g2 is"+g2.str+"\n";
      tdfs::= #FLIST{INT};
      -- g2_alg ::= #DIGRAPH_ALG_WRAP{INT,DIGRAPH{INT}}(g2);
      loop tdfs := tdfs.push(g2.df!(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:"+tdfs.str, 
	   tdfs.equals(r1) or tdfs.equals(r2) 
	   or tdfs.equals(r3) or tdfs.equals(r4), 
	   true);
      
      g2.connect(3,5);
      --    1
      --    /\
      --   2   3
      -- /  \ /
      --4    5
      tdfs2::= #FLIST{INT};
      loop tdfs2 := tdfs2.push(g2.df!(1)) end;
      r5 ::= #FLIST{INT}(|1,2,4,5,3|);
      r6 ::= #FLIST{INT}(|1,3,5,2,4|);
      r7 ::= #FLIST{INT}(|1,2,5,4,3|);
      test("Dfs2:"+tdfs2.str, 
	   tdfs2.equals(r5) or tdfs2.equals(r6) or tdfs2.equals(r7), true);

      tbfs ::= #FLIST{INT};
      loop tbfs := tbfs.push(g2.bf!(1)) end;
      r8 ::= #FLIST{INT}(|1,2,3,4,5|);
      r9 ::= #FLIST{INT}(|1,2,3,5,4|);
      r10 ::= #FLIST{INT}(|1,3,2,4,5|);
      r11 ::= #FLIST{INT}(|1,3,2,5,4|);
      test("bfs:"+tbfs.str, 
	   tbfs.equals(r8) or tbfs.equals(r9) 
	   or tbfs.equals(r10) or tbfs.equals(r11), true);
      tblayers ::= #FLIST{SET{INT}};
      loop tblayers := tblayers.push(g2.layer!); end;
      r12 ::= #SET{INT}(#ARRAY{INT}(|1|));
      r13 ::= #SET{INT}(#ARRAY{INT}(|2,3|));
      r14 ::= #SET{INT}(#ARRAY{INT}(|4,5|));
      #OUT+"Layers:"+tblayers.str+"\n";
      test("n layers",tblayers.size,3);
      test("layers1",r12.equals(tblayers[0]),true);
      test("layers1",r13.equals(tblayers[1]),true);
      test("layers1",r14.equals(tblayers[2]),true);
      finish;
   end;
  
   print_graph(msg: STR,g: $DIGRAPH{STR}) is
      #OUT+"\n*****************\n"+msg+"\n*****************\n";
      #OUT+g.str
	    +"\n********************************************\n";
   end;      
      
   compare_to_standard(msg: STR, g: $DIGRAPH{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);
      nv:SET{STR} := #SET{STR};
      loop nv.insert(g.node!); end;
      sz ::= nv.size;
      test("test node size "+msg+" "+nv,sz,8);
      -- Make sure all the nodes are returned
      correct_nodes::=#SET{STR}
	    (#ARRAY{STR}(|"0","1","2","3","4","5","6","7"|));
      test("correct nodes:"+nv,correct_nodes.equals(nv),true);
      edge_arr:ARRAY{DIEDGE{STR}} := |me(0,2),me(1,2),me(1,3),me(1,4),
				     me(2,5),me(3,5),me(4,5),me(5,6)|;
      correct_edges ::= #SET{DIEDGE{STR}}(edge_arr);
      ev ::= #SET{DIEDGE{STR}};
      loop ev.insert(g.edge!); end;
      test("edges:"+ev+"\ncorrect:"+correct_edges,
	   ev.equals(correct_edges),true);
      #OUT+"Edge difference:"+ev.sym_diff(correct_edges)+"\n";
   end;
   
   me(n1,n2: INT): DIEDGE{STR} is
      -- make edge
      return #DIEDGE{STR}(n1.str,n2.str);
   end;
					   
end;
-------------------------------------------------------------------

