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