2
$\begingroup$

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: Directed graph with cycles

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?

enter image description here

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.

$\endgroup$
  • $\begingroup$ What would the list look like, for example for a complete undirected graph? $\endgroup$ – Yuval Filmus Jan 1 '18 at 14:55
  • $\begingroup$ I added an example to clarify what I'm referring to. Also please note I'm talking about a directed not an undirected graph. $\endgroup$ – Omnomnious Jan 1 '18 at 15:08
  • 2
    $\begingroup$ I'm trying to understand what you mean by cycle. Are you interested in listing all simple directed cycles? As you mention, one problem is that there could be very many of them. $\endgroup$ – Yuval Filmus Jan 1 '18 at 16:14
  • 1
    $\begingroup$ Please edit the question to include that information in the question. People shouldn't have to read the comments to understand what you're asking. Also, rather than asking "Can you ask DFS to do this?" it's probably better to ask "How do I do this?", as you should be prepared that the answer might not involve DFS in any way. Finally, what research have you done? Have you searched thoroughly here and on CSTheory.SE and on Stack Overflow? I suspect I've seen questions before that discuss enumerating all cycles in a graph, though I don't know if I'm remembering that right. $\endgroup$ – D.W. Jan 2 '18 at 0:22
  • 1
    $\begingroup$ Got it. It might be helpful to add that context to the question, especially that you're looking for an algorithm that is easy to implement. Feel free to flag comments that are no longer needed or have been addressed by your edits. $\endgroup$ – D.W. Jan 2 '18 at 16:50
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ what do you mean by a non-DFS-tree edge? $\endgroup$ – Omnomnious Jan 3 '18 at 12:20
  • $\begingroup$ @Omnomnious A graph edge that is not part of the spanning tree found/traversed by the DFS. In DFS lingo, cycles that contain more than one back- or cross-edge can't be found that way. $\endgroup$ – Raphael Jan 3 '18 at 12:55
0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.