test_digraph.sa
Generated by gen_html_sa_files from ICSI. Contact gomes@icsi.berkeley.edu for details
---------------------------> Sather 1.1 source file <--------------------------
-- Test digraph classes
-- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>
-- Copyright (C) 1995, International Computer Science Institute
-- $Id: test_digraph.sa,v 1.4 1996/07/13 05:42:05 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_DIGRAPH
class TEST_DIGRAPH 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 ::= #DIGRAPH_NODE_SET_VIEW{STR}(g);
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 ::= #DIGRAPH_EDGE_SET_VIEW{STR}(g);
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;