Can a 3 Color DFS be used to identify cycles (not just detect them)?

Question

Can a 3 color DFS be used to identify all cycles in a directed graph not just detect them?

In other words if I have a directed graph with multiple cycles, can I run a function on them such that the function returns the list of nodes that compose each simple directed cycle in the graph and not just a boolean true or false? Most answers online show pseudocode for detection and not identification (ie functions which return boolean values instead of node lists). You can assume that the graphs I'm referring to are mostly tree like in structure and aren't deeper than 5 nodes or so.

So for example, for this graph:

The list would be [[a,b,e], [f,g], [c,d], [d,h]]

With white, grey, black DFS a cycle is found when a node already colored grey is visited a second time through a different edge. What I'm struggling to wrap my head around is when this happens, how do we back track to identify all of the nodes involved in this detected cycle without increasing complexity or running DFS a second time. In the example below, if we do a DFS (exploring right edges first) starting at A, the stack will look like this [A,B,C,E,D,B] and the cycle will be detected when B is visited a second time. Given this stack how do we deduce that C D and B only are part of the cycle and not E or A?

I am aware that there are plenty of algorithms other than DFS that can do this (such as Johnson's algorithm or Tarjan's with a twist) I just want something simple to implement.

Answer 1

The moment you find a grey node, you have the edge that closes the cycle in hand. All other edges are part of the DFS tree. That is, store the "cycle-closing" edge and obtain the rest afterwards.

That is, assuming that those are the cycles you are interested in. Other cycles (such that contain more than one non-DFS-tree edge) are more complicated, but I don't think those are easy to cover. A directed graph may have super-exponentially many cycles, so you can't expect to list them all with a simple, linear-time traversal.

Answer 2

The answer to this question is YES. A three color DFS algorithm can be used to both detect and identify the nodes associated with all simple cycles in a directed graph with more or less the same time complexity.

The key is to keep a stack of parent and child pairs as you recursively explore the graph using white, grey, black (3 color) depth first search. You must also remember to pop pairs off the stack after you are done exploring a child (ie when the child's color is set to black). This will give you an easy way to trace what nodes are traversed going to and from a "starting node" in a cycle.

I will add more detail and an example implementation later!

Answer 3

Here is an algorithm which takes your stack content $S$ when loop was detected & return array of the nodes which are forming cycle. From your example it is $ [A,B,C,E,D,B]$

 Algorithm_Get_Loop_Nodes(S):
     cycle_nodes = []
     repeated_node = S[top]
     while S[top] != repeated_node:
         prev_node = S.pop()
         curr_node = S[top]
         if curr_node is parent of prev_node:
            cycle_nodes.add(curr_node)
     return cycle_nodes