comparison toolboxes/FullBNT-1.0.7/graph/Old/dfs.m @ 0:e9a9cd732c1e tip

first hg version after svn

+function [d, pre, post, height, cycle, pred] = dfs(adj_mat, start, directed)
+% DFS Perform a depth-first search of the graph starting from 'start'.
+% [d, pre, post, height, cycle, pred] = dfs(adj_mat, start, directed)
+%
+% d(i) is the time at which node i is first discovered.
+% pre is a listing of the nodes in the order in which they are first encountered (opened).
+% post is a listing of the nodes in the order in which they are last encountered (closed).
+% A node is last encountered once we have explored all of its neighbors.
+% If the graph is directed, i's neighbors are its children.
+% If the graph is a tree, preorder is parents before children, and
+% postorder is children before parents.
+% For a DAG, topological order = reverse(postorder).
+% height(i) is the height (distance) of node i from the start.
+% 'cycle' is true iff a (directed) cycle is found.
+% pred(i) is the parent of i in the dfs tree rooted at start.
+% See Cormen, Leiserson and Rivest, "An intro. to algorithms" 1994, p478.
+
+% We can detect undirected cycles by checking if we are about to visit a node n which we have
+% already visited. To detect *directed* cycles, we need to know if n has been closed or is still open.
+% For example (where arcs are directed down)
+%   1    2
+%   \   /
+%     3
+% Assume we visit 1, 3 and then 2 in order. The fact that a child of 2 (namely, 3) has
+% already been visited is okay, because 3 has been closed.
+% The algorithms in Aho, Hopcroft and Ullman, and Sedgewick, do not detect directed cycles.
+
+n = length(adj_mat);
+
+global white gray black
+white = 0; gray = 1; black = 2;
+
+color = white*ones(1,n);
+d = zeros(1,n);
+height = zeros(1,n);
+pred = zeros(1,n);
+pre = [];
+post = [];
+cycle = 0;
+global count
+count = 0;
+h = 0;
+[d, pre, post, height, cycle, color, pred] = ...
+    dfs2(adj_mat, start, directed, h, d, pre, post, height, cycle, color, pred);
+
+
+
+%%%%%%%%%%
+
+function [d, pre, post, height, cycle, color, pred] = ...
+    dfs2(adj_mat, i, directed, h, d, pre, post, height, cycle, color, pred)
+
+global count
+global white gray black
+
+color(i) = gray;
+count = count + 1;
+d(i) = count;
+pre = [pre i];
+height(i) = h;
+if directed
+  ns = children(adj_mat, i);
+else
+  ns = neighbors(adj_mat, i);
+end
+for j=1:length(ns)
+  n=ns(j);
+  if ~directed & n==pred(i) % don't go back up the edge you just came down
+    % continue
+  else
+    if color(n) == gray % going back to a non-closed vertex via a new edge
+      %fprintf(1, 'cycle from %d to %d\n', i, n);
+      cycle = 1;
+    end
+    if color(n) == white % not visited n before
+      pred(n)=i;
+      [d, pre, post, height, cycle, color, pred] = ...
+	  dfs2(adj_mat, n, directed, h+1, d, pre, post, height, cycle, color, pred);
+    end
+  end
+end
+color(i) = black;
+post = [post i];
+