diff toolboxes/FullBNT-1.0.7/graph/dfs_test.m @ 0:cc4b1211e677 tip

initial commit to HG from
Changeset:
646 (e263d8a21543) added further path and more save "camirversion.m"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/toolboxes/FullBNT-1.0.7/graph/dfs_test.m	Fri Aug 19 13:07:06 2016 +0200
@@ -0,0 +1,30 @@
+% Do the example in fig 23.4 p479 of Cormen, Leiserson and Rivest (1994)
+
+u = 1; v = 2; w = 3; x = 4; y = 5; z = 6;
+n = 6;
+dag=zeros(n,n);
+dag(u,[v x])=1;
+dag(v,y)=1;
+dag(w,[y z])=1;
+dag(x,v)=1;
+dag(y,x)=1;
+dag(z,z)=1;
+
+[d, pre, post, cycle, f, pred] = dfs(dag, [], 1);
+assert(isequal(d, [1 2 9 4 3 10]))
+assert(isequal(f, [8 7 12 5 6 11])
+assert(cycle)
+
+% Now give it an undirected cyclic graph
+G = mk_2D_lattice(2,2,0);
+% 1 - 3
+% |   |
+% 2 - 4
+[d, pre, post, cycle, f, pred] = dfs(G, [], 0);
+% d = [1 2 4 3]
+assert(cycle)
+
+% Now break the cycle
+G(1,2)=0; G(2,1)=0;
+[d, pre, post, cycle, f, pred] = dfs(G, [], 0);
+assert(~cycle)