1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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)
|
