Edge classification during Breadth-first search on a directed graph

Question

I am having difficulties finding a way to properly classify the edges while a breadth-first search on a directed graph.

During a breadth-first or depth-first search, you can classify the edges met with 4 classes:

• TREE
• BACK
• CROSS
• FORWARD

Skiena [1] gives an implementation. If you move along an edge from v1 to v2, here is a way to return the class during a DFS in java, for reference. The parents map returns the parent vertex for the current search, and the timeOf() method, the time at which the vertex has been discovered.

if ( v1.equals( parents.get( v2 ) ) ) { return EdgeClass.TREE; }
    if ( discovered.contains( v2 ) && !processed.contains( v2 ) ) { return EdgeClass.BACK; }
    if ( processed.contains( v2 ) )
    {
        if ( timeOf( v1 ) < timeOf( v2 ) )
        {
            return EdgeClass.FORWARD;
        }
        else
        {
            return EdgeClass.CROSS;
        }
    }
    return EdgeClass.UNCLASSIFIED;

My problem is that I cannot get it right for a Breadth first search on a directed graph. For instance:

The following graph - that is a loop - is ok:

A -> B
A -> C
B -> C

BFSing from A, B will be discovered, then C. The edges eAB and eAC are TREE edges, and when eBC is crossed last, B and C are processed and discovered, and this edge is properly classified as CROSS.

But a plain loop does not work:

A -> B
B -> C
C -> A

When the edge eCA is crossed last, A is processed and discovered. So this edge is incorrectly labeled as CROSS, whether it should be a BACK edge.

There is indeed no difference in the way the two cases are treated, even if the two edges have different classes.

How do you implement a proper edge classification for a BFS on a directed graph?

[1] http://www.algorist.com/

---

EDIT

Here an implementation derived from @redtuna answer. I just added a check not to fetch the parent of the root. I have JUnits tests that show it works for directed and undirected graphs, in the case of a loop, a straight line, a fork, a standard example, a single edge, etc....

@Override
public EdgeClass edgeClass( final V from, final V to )
{
    if ( !discovered.contains( to ) ) { return EdgeClass.TREE; }

    int toDepth = depths.get( to );
    int fromDepth = depths.get( from );

    V b = to;
    while ( toDepth > 0 && fromDepth < toDepth )
    {
        b = parents.get( b );
        toDepth = depths.get( b );
    }

    V a = from;
    while ( fromDepth > 0 && toDepth < fromDepth )
    {
        a = parents.get( a );
        fromDepth = depths.get( a );
    }

    if ( a.equals( b ) )
    {
        return EdgeClass.BACK;
    }
    else
    {
        return EdgeClass.CROSS;
    }

}

Ravel

Answer 1

How do you implement a proper edge classification for a BFS on a directed graph?

As you already established, seeing a node for the first time creates a tree edge. The problem with BFS instead of DFS, as David Eisenstat said before me, is that back edges cannot be distinguished from cross ones just based on traversal order.

Instead, you need to do a bit of extra work to distinguish them. The key, as you'll see, is to use the definition of a cross edge.

The simplest (but memory-intensive) way is to associate every node with the set of its predecessors. This can be done trivially when you visit nodes. When finding a non-tree edge between nodes a and b, consider their predecessor sets. If one is a proper subset of the other, then you have a back edge. Otherwise, it's a cross edge. This comes directly from the definition of a cross edge: it's an edge between nodes where neither is the ancestor nor the descendant of the other on the tree.

A better way is to associate only a "depth" number with each node instead of a set. Again, this is readily done as you visit nodes. Now when you find a non-tree edge between a and b, start from the deeper of the two nodes and follow the tree edges backwards until you go back to the same depth as the other. So for example suppose a was deeper. Then you repeatedly compute a=parent(a) until depth(a)=depth(b).

If at this point a=b then you can classify the edge as a back edge because, as per the definition, one of the nodes is an ancestor of the other on the tree. Otherwise you can classify it as a cross edge because we know that neither node is an ancestor or descendant of the other.

pseudocode:

  foreach edge(a,b) in BFS order:
    if !b.known then:
      b.known = true
      b.depth = a.depth+1
      edge type is TREE
      continue to next edge
    while (b.depth > a.depth): b=parent(b)
    while (a.depth > b.depth): a=parent(a)
    if a==b then:
      edge type is BACK
    else:
      edge type is CROSS

Lightheaded

I implemented and tested this solution successfully. It works regardless of the directed/undirected-ness of the graph. I made a few minor changes that I will post below the question. Thanks! – Ravel

Answer 2

The key property of DFS here is that, given two nodes u and v, the interval [u.discovered, u.processed] is a subinterval of [v.discovered, v.processed] if and only if u is a descendant of v. The times in BFS do not have this property; you have to do something else, e.g., compute the intervals via DFS on the tree that BFS produced. Then the classification pseudocode is 1. check for membership in the tree (tree edge) 2. check for head's interval contains tail's (back edge) 3. check for tail's interval contains head's (forward edge) 4. otherwise, declare a cross edge.

Layla

Answer 3

Instead of timeof(), you need an other vertex property, which contains the distance from the root. Let name that distance.

You have to processing a v vertex in the following way:

for (v0 in v.neighbours) {
    if (!v0.discovered) {
        v0.discovered = true; 
        v0.parent = v;
        v0.distance = v.distance + 1;
    }
}
v.processed = true;

After you processed a vertex a v vertex, you can run the following algorithm for every edge (from v1 to v2) of the v:

if (!v1.discovered) return EdgeClass.BACK;  
else if (!v2.discovered) return EdgeClass.FORWARD; 
else if (v1.distance == v2.distance) return EdgeClass.CROSS;
else if (v1.distance > v2.distance) return EdgeClass.BACK;
else {
    if (v2.parent == v1) return EdgeClass.TREE;
    else return EdgeClass.FORWARD;
}

Afro

Hey thanks Zsolt! I have been working on implementations of the 3 answers I collected. For yours, I think I have a counter-example. Consider a diamond: A-B, A-C, B-D, C-D The BFS will iterate through A, B, C and D. The last edge crossed is eCD and is incorrectly classified. At this time C is discovered and processed, D is discovered and not processed. Their distances are different and dD > dC. So it is incorrectly classified as a FORWARD edge, but it is a CROSS edge. – Ravel