|
wolffd@0
|
1 function [d, pre, post, height, cycle, pred] = dfs(adj_mat, start, directed)
|
|
wolffd@0
|
2 % DFS Perform a depth-first search of the graph starting from 'start'.
|
|
wolffd@0
|
3 % [d, pre, post, height, cycle, pred] = dfs(adj_mat, start, directed)
|
|
wolffd@0
|
4 %
|
|
wolffd@0
|
5 % d(i) is the time at which node i is first discovered.
|
|
wolffd@0
|
6 % pre is a listing of the nodes in the order in which they are first encountered (opened).
|
|
wolffd@0
|
7 % post is a listing of the nodes in the order in which they are last encountered (closed).
|
|
wolffd@0
|
8 % A node is last encountered once we have explored all of its neighbors.
|
|
wolffd@0
|
9 % If the graph is directed, i's neighbors are its children.
|
|
wolffd@0
|
10 % If the graph is a tree, preorder is parents before children, and
|
|
wolffd@0
|
11 % postorder is children before parents.
|
|
wolffd@0
|
12 % For a DAG, topological order = reverse(postorder).
|
|
wolffd@0
|
13 % height(i) is the height (distance) of node i from the start.
|
|
wolffd@0
|
14 % 'cycle' is true iff a (directed) cycle is found.
|
|
wolffd@0
|
15 % pred(i) is the parent of i in the dfs tree rooted at start.
|
|
wolffd@0
|
16 % See Cormen, Leiserson and Rivest, "An intro. to algorithms" 1994, p478.
|
|
wolffd@0
|
17
|
|
wolffd@0
|
18 % We can detect undirected cycles by checking if we are about to visit a node n which we have
|
|
wolffd@0
|
19 % already visited. To detect *directed* cycles, we need to know if n has been closed or is still open.
|
|
wolffd@0
|
20 % For example (where arcs are directed down)
|
|
wolffd@0
|
21 % 1 2
|
|
wolffd@0
|
22 % \ /
|
|
wolffd@0
|
23 % 3
|
|
wolffd@0
|
24 % Assume we visit 1, 3 and then 2 in order. The fact that a child of 2 (namely, 3) has
|
|
wolffd@0
|
25 % already been visited is okay, because 3 has been closed.
|
|
wolffd@0
|
26 % The algorithms in Aho, Hopcroft and Ullman, and Sedgewick, do not detect directed cycles.
|
|
wolffd@0
|
27
|
|
wolffd@0
|
28 n = length(adj_mat);
|
|
wolffd@0
|
29
|
|
wolffd@0
|
30 global white gray black
|
|
wolffd@0
|
31 white = 0; gray = 1; black = 2;
|
|
wolffd@0
|
32
|
|
wolffd@0
|
33 color = white*ones(1,n);
|
|
wolffd@0
|
34 d = zeros(1,n);
|
|
wolffd@0
|
35 height = zeros(1,n);
|
|
wolffd@0
|
36 pred = zeros(1,n);
|
|
wolffd@0
|
37 pre = [];
|
|
wolffd@0
|
38 post = [];
|
|
wolffd@0
|
39 cycle = 0;
|
|
wolffd@0
|
40 global count
|
|
wolffd@0
|
41 count = 0;
|
|
wolffd@0
|
42 h = 0;
|
|
wolffd@0
|
43 [d, pre, post, height, cycle, color, pred] = ...
|
|
wolffd@0
|
44 dfs2(adj_mat, start, directed, h, d, pre, post, height, cycle, color, pred);
|
|
wolffd@0
|
45
|
|
wolffd@0
|
46
|
|
wolffd@0
|
47
|
|
wolffd@0
|
48 %%%%%%%%%%
|
|
wolffd@0
|
49
|
|
wolffd@0
|
50 function [d, pre, post, height, cycle, color, pred] = ...
|
|
wolffd@0
|
51 dfs2(adj_mat, i, directed, h, d, pre, post, height, cycle, color, pred)
|
|
wolffd@0
|
52
|
|
wolffd@0
|
53 global count
|
|
wolffd@0
|
54 global white gray black
|
|
wolffd@0
|
55
|
|
wolffd@0
|
56 color(i) = gray;
|
|
wolffd@0
|
57 count = count + 1;
|
|
wolffd@0
|
58 d(i) = count;
|
|
wolffd@0
|
59 pre = [pre i];
|
|
wolffd@0
|
60 height(i) = h;
|
|
wolffd@0
|
61 if directed
|
|
wolffd@0
|
62 ns = children(adj_mat, i);
|
|
wolffd@0
|
63 else
|
|
wolffd@0
|
64 ns = neighbors(adj_mat, i);
|
|
wolffd@0
|
65 end
|
|
wolffd@0
|
66 for j=1:length(ns)
|
|
wolffd@0
|
67 n=ns(j);
|
|
wolffd@0
|
68 if ~directed & n==pred(i) % don't go back up the edge you just came down
|
|
wolffd@0
|
69 % continue
|
|
wolffd@0
|
70 else
|
|
wolffd@0
|
71 if color(n) == gray % going back to a non-closed vertex via a new edge
|
|
wolffd@0
|
72 %fprintf(1, 'cycle from %d to %d\n', i, n);
|
|
wolffd@0
|
73 cycle = 1;
|
|
wolffd@0
|
74 end
|
|
wolffd@0
|
75 if color(n) == white % not visited n before
|
|
wolffd@0
|
76 pred(n)=i;
|
|
wolffd@0
|
77 [d, pre, post, height, cycle, color, pred] = ...
|
|
wolffd@0
|
78 dfs2(adj_mat, n, directed, h+1, d, pre, post, height, cycle, color, pred);
|
|
wolffd@0
|
79 end
|
|
wolffd@0
|
80 end
|
|
wolffd@0
|
81 end
|
|
wolffd@0
|
82 color(i) = black;
|
|
wolffd@0
|
83 post = [post i];
|
|
wolffd@0
|
84
|
