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;