Graph (Recitation)

From Recitation: Euler paths, planar graphs, and Hamiltonian paths

Edge Classification¶

We have an edge e=(v,child), where v is always grey

• Tree edge:

  if (child.color==white)
  	e = TreeEdge;

• Back edge:

  if (child.color==grey)
      e = BackEdge;

• Forward edge:

  if (child.color==black && v.timeStamp<child.timeStamp)
      e = ForwardEdge;

• Cross edge:

  if (child.color==black && v.timeStamp > child.timeStamp)
      e = ForwardEdge;