Edge classification in iterative DFS

Question

Edges can be classified according to three categories (back edge, tree/forward edge, cross edge) using a recursive DFS that labels nodes as unvisited, discovered or finished (or white, grey, black).

Can we also classify edges using the iterative version of the algorithm (cf. Depth-First Search )?

procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5          v = S.pop()
6          if v is not labeled as discovered:
7              label v as discovered
8              for all edges from v to w in G.adjacentEdges(v) do
9                  S.push(w)

This version only uses two categories, unvisited, and discovered. We could mark the node as finished after all neighboring nodes have been pushed to the stack but it wouldn't give the expected result.

EDIT (Clarification): The question is, can we modify the iterative version of DFS given above in order to classify edges as tree/forward edge, cross edge and back edge, just like it's commonly done with the recursive version by taking advantage of the node label/color?

Answer 1

Here is my solution in c++:

std::vector<bool> visited(number_of_nodes, false);
std::vector<int> entry(number_of_nodes, 0);
std::vector<int> exit(number_of_nodes, 0);

// trace stack of ancestors
std::vector<int> trace;

int time = 1;

// u is current node that moves around
int u = nodes.front();
trace.push_back(u);
visited[u] = true;

// iterative DFS with entry and exit times
while (!trace.empty()) {
    bool found = false;
    for (auto& v : neighbours_of(u)) {
        if ((!visited[v]) && (!found)) {
            found = true; // no blockage
            u = v;
            entry[u] = time++;
            visited[u] = true;
            trace.push_back(v);
            break;
        }
    }

    if (!found) {
        trace.pop_back();
        exit[u] = time++;
        u = trace.back();
    }
}

This will get the entry and exit times for the DFS. The edges can be classified according to the rules posted here using these times. You can do this on the fly as well, although the rules are a bit different. For instance, during the search if we encounter edge (u,v), and entry[v] is set but exit[v] is not yet set then (u,v) is a backward edge.

Answer 2

My solution to this is to simulate the recursion using a stack and a "current child" pointer.

When we peek at a node from the standard DFS stack, we will check whether the current child pointer is pointing at the end of the adjacency list for this node. If it is, we are done with this node. If not, we will push this child node (if eligible) onto the DFS stack without updating the current child pointer. This will allow us to perform post processing on this child later.

As an example, consider 10199 - Tourist Guide from UVa Judge. It basically asks us to find articulation points, which crucially depend on edge classification.

From Recursive Solution:

void CutVertexFinder::DFS(int root) {
  for (auto&& child : graph[root]) {
    if (child == parent[root]) continue;

    if (parent[child] == -1) {
      // Tree edge
      parent[child] = root;
      entry[child] = time++;
      farthest_ancestor[child] = child;

      num_children[root]++;
      DFS(child);

      if (entry[farthest_ancestor[child]] < entry[farthest_ancestor[root]]) {
        farthest_ancestor[root] = farthest_ancestor[child];
      }
    } else if (entry[child] < entry[root]) {
      // Back edge
      if (entry[child] < entry[farthest_ancestor[root]]) {
        farthest_ancestor[root] = child;
      }
    }
  }
}

From Iterative Solution:

void CutVertexFinder::DFS(int root) {
  std::vector<int> current_child_index(N, 0);
  stack<int> S;

  S.emplace(root);
  while (!S.empty()) {
    int node = S.top();

    const int child_index = current_child_index[node];
    if (child_index >= graph[node].size()) {
      S.pop();
      continue;
    }

    int child = graph[node][child_index];
    if (child == parent[node]) {
      current_child_index[node]++;
      continue;
    }

    if (parent[child] == -1) {
      parent[child] = node;
      entry[child] = time++;
      farthest_ancestor[child] = child;

      num_children[node]++;
      S.emplace(child);
      continue;
    }

    if (parent[child] == node) {
      if (entry[farthest_ancestor[child]] < entry[farthest_ancestor[node]]) {
        farthest_ancestor[node] = farthest_ancestor[child];
      }
    } else if (entry[child] < entry[node]) {
      if (entry[child] < entry[farthest_ancestor[node]]) {
        farthest_ancestor[node] = child;
      }
    }
    current_child_index[node]++;
  }
}

As you can see, the iterative solution is probably an overkill.

Answer 3

Suppose you work in the recursive version. Then it could be modified as follows:

DFS(G,v):
    v.discovered = True
    for all edges from v to w in G.adjacentEdges(v) do
    if not w.discovered then
        recursively call DFS(G,w)
    v.finished = True

Using the idea of bracketing, it is well known that:

• An edge is a tree edge if it leads to a vertex that is undiscovered.

• An edge is a backwards edge if it leads to a vertex that is discovered and not finished

• An edge is a cross or forward edge otherwise.

So now the only problem is to make it iterative. The only difference is that we now need to manipulate things the recursion did for us before. Say each vertex has numActiveChildren set to 0, and parent set to Nil. The iterative version could look as follows:

DFS-iterative(G,v):
    let S be a stack
    S.push(v)
    while S is not empty do
        v = S.pop()
        if not v.discovered do
            v.discovered = True
            for all edges from v to w in G.adjacentEdges(v) do
                if w.discovered do
                    w.parent.numActiveChildren = w.parent.numActiveChildren - 1
                v.numActiveChildren = v.numActiveChildren + 1
                w.parent = v
                S.push(w)

            while v != Nil and v.numActiveChildren = 0 do
                v.finished = True
                v = v.parent
                if v != Nil do
                    v.numActiveChildren = v.numActiveChildren - 1