title: Edge classification during Breadth-first search on a directed graph
body: <p>I am having difficulties finding a way to properly classify the edges while a breadth-first search on a directed graph. </p>
  
  <p>During a breadth-first or depth-first search, you can classify the edges met with 4 classes:</p>
  
  <ul>
  <li>TREE</li>
  <li>BACK</li>
  <li>CROSS</li>
  <li>FORWARD</li>
  </ul>
  
  <p>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 <code>timeOf()</code> method, the time at which the vertex has been discovered.</p>
  
  <pre class="lang-java prettyprint-override"><code>if ( v1.equals( parents.get( v2 ) ) ) { return EdgeClass.TREE; }
      if ( discovered.contains( v2 ) &amp;&amp; !processed.contains( v2 ) ) { return EdgeClass.BACK; }
      if ( processed.contains( v2 ) )
      {
          if ( timeOf( v1 ) &lt; timeOf( v2 ) )
          {
              return EdgeClass.FORWARD;
          }
          else
          {
              return EdgeClass.CROSS;
          }
      }
      return EdgeClass.UNCLASSIFIED;
  </code></pre>
  
  <p>My problem is that I cannot get it right for a <strong>Breadth first search on a directed graph</strong>. For instance:</p>
  
  <p>The following graph - that is a loop - is ok:</p>
  
  <pre><code>A -&gt; B
  A -&gt; C
  B -&gt; C
  </code></pre>
  
  <p>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. </p>
  
  <p>But a plain loop does not work:</p>
  
  <pre><code>A -&gt; B
  B -&gt; C
  C -&gt; A
  </code></pre>
  
  <p>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. </p>
  
  <p>There is indeed no difference in the way the two cases are treated, even if the two edges have different classes. </p>
  
  <p>How do you implement a proper edge classification for a BFS on a directed graph?</p>
  
  <p>[1] <a href="http://www.algorist.com/" rel="noreferrer">http://www.algorist.com/</a></p>
  
  <hr>
  
  <p>EDIT</p>
  
  <p>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....</p>
  
  <pre class="lang-java prettyprint-override"><code>@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 &gt; 0 &amp;&amp; fromDepth &lt; toDepth )
      {
          b = parents.get( b );
          toDepth = depths.get( b );
      }
  
      V a = from;
      while ( fromDepth &gt; 0 &amp;&amp; toDepth &lt; fromDepth )
      {
          a = parents.get( a );
          fromDepth = depths.get( a );
      }
  
      if ( a.equals( b ) )
      {
          return EdgeClass.BACK;
      }
      else
      {
          return EdgeClass.CROSS;
      }
  
  }
  </code></pre>