|
wolffd@0
|
1 function [d, pre, post, cycle, f, 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, cycle, f, pred] = dfs(adj_mat, start, directed)
|
|
wolffd@0
|
4 %
|
|
wolffd@0
|
5 % Input:
|
|
wolffd@0
|
6 % adj_mat(i,j)=1 iff i is connected to j.
|
|
wolffd@0
|
7 % start is the root vertex of the dfs tree; if [], all nodes are searched
|
|
wolffd@0
|
8 % directed = 1 if the graph is directed
|
|
wolffd@0
|
9 %
|
|
wolffd@0
|
10 % Output:
|
|
wolffd@0
|
11 % d(i) is the time at which node i is first discovered.
|
|
wolffd@0
|
12 % pre is a list of the nodes in the order in which they are first encountered (opened).
|
|
wolffd@0
|
13 % post is a list of the nodes in the order in which they are last encountered (closed).
|
|
wolffd@0
|
14 % 'cycle' is true iff a (directed) cycle is found.
|
|
wolffd@0
|
15 % f(i) is the time at which node i is finished.
|
|
wolffd@0
|
16 % pred(i) is the predecessor of i in the dfs tree.
|
|
wolffd@0
|
17 %
|
|
wolffd@0
|
18 % If the graph is a tree, preorder is parents before children,
|
|
wolffd@0
|
19 % and postorder is children before parents.
|
|
wolffd@0
|
20 % For a DAG, topological order = reverse(postorder).
|
|
wolffd@0
|
21 %
|
|
wolffd@0
|
22 % See Cormen, Leiserson and Rivest, "An intro. to algorithms" 1994, p478.
|
|
wolffd@0
|
23
|
|
wolffd@0
|
24 n = length(adj_mat);
|
|
wolffd@0
|
25
|
|
wolffd@0
|
26 global white gray black color
|
|
wolffd@0
|
27 white = 0; gray = 1; black = 2;
|
|
wolffd@0
|
28 color = white*ones(1,n);
|
|
wolffd@0
|
29
|
|
wolffd@0
|
30 global time_stamp
|
|
wolffd@0
|
31 time_stamp = 0;
|
|
wolffd@0
|
32
|
|
wolffd@0
|
33 global d f
|
|
wolffd@0
|
34 d = zeros(1,n);
|
|
wolffd@0
|
35 f = zeros(1,n);
|
|
wolffd@0
|
36
|
|
wolffd@0
|
37 global pred
|
|
wolffd@0
|
38 pred = zeros(1,n);
|
|
wolffd@0
|
39
|
|
wolffd@0
|
40 global cycle
|
|
wolffd@0
|
41 cycle = 0;
|
|
wolffd@0
|
42
|
|
wolffd@0
|
43 global pre post
|
|
wolffd@0
|
44 pre = [];
|
|
wolffd@0
|
45 post = [];
|
|
wolffd@0
|
46
|
|
wolffd@0
|
47 if ~isempty(start)
|
|
wolffd@0
|
48 dfs_visit(start, adj_mat, directed);
|
|
wolffd@0
|
49 end
|
|
wolffd@0
|
50 for u=1:n
|
|
wolffd@0
|
51 if color(u)==white
|
|
wolffd@0
|
52 dfs_visit(u, adj_mat, directed);
|
|
wolffd@0
|
53 end
|
|
wolffd@0
|
54 end
|
|
wolffd@0
|
55
|
|
wolffd@0
|
56
|
|
wolffd@0
|
57 %%%%%%%%%%
|
|
wolffd@0
|
58
|
|
wolffd@0
|
59 function dfs_visit(u, adj_mat, directed)
|
|
wolffd@0
|
60
|
|
wolffd@0
|
61 global white gray black color time_stamp d f pred cycle pre post
|
|
wolffd@0
|
62
|
|
wolffd@0
|
63 pre = [pre u];
|
|
wolffd@0
|
64 color(u) = gray;
|
|
wolffd@0
|
65 time_stamp = time_stamp + 1;
|
|
wolffd@0
|
66 d(u) = time_stamp;
|
|
wolffd@0
|
67 if directed
|
|
wolffd@0
|
68 ns = children(adj_mat, u);
|
|
wolffd@0
|
69 else
|
|
wolffd@0
|
70 ns = neighbors(adj_mat, u);
|
|
wolffd@0
|
71 ns = setdiff(ns, pred(u)); % don't go back to visit the guy who called you!
|
|
wolffd@0
|
72 end
|
|
wolffd@0
|
73 for v=ns(:)'
|
|
wolffd@0
|
74 %fprintf('u=%d, v=%d, color(v)=%d\n', u, v, color(v))
|
|
wolffd@0
|
75 switch color(v)
|
|
wolffd@0
|
76 case white, % not visited v before (tree edge)
|
|
wolffd@0
|
77 pred(v)=u;
|
|
wolffd@0
|
78 dfs_visit(v, adj_mat, directed);
|
|
wolffd@0
|
79 case gray, % back edge - v has been visited, but is still open
|
|
wolffd@0
|
80 cycle = 1;
|
|
wolffd@0
|
81 %fprintf('cycle: back edge from v=%d to u=%d\n', v, u);
|
|
wolffd@0
|
82 case black, % v has been visited, but is closed
|
|
wolffd@0
|
83 % no-op
|
|
wolffd@0
|
84 end
|
|
wolffd@0
|
85 end
|
|
wolffd@0
|
86 color(u) = black;
|
|
wolffd@0
|
87 post = [post u];
|
|
wolffd@0
|
88 time_stamp = time_stamp + 1;
|
|
wolffd@0
|
89 f(u) = time_stamp;
|
|
wolffd@0
|
90
|
|
wolffd@0
|
91
|
