CODEWITHSUNDEEP
recursiondepth-first-searchdirected-graph
RenWal
RenWal

Reputation: 181

How to detect cycles in directed graph in iterative DFS?

My current project features a set of nodes with inputs and outputs. Each node can take its input values and generate some output values. Those outputs can be used as inputs for other nodes. To minimize the amount of computation needed, node dependencies are checked on application start. When updating the nodes, they are updated in the reverse order they depend on each other.

That said, the nodes resemble a directed graph. I am using iterative DFS (no recursion to avoid stack overflows in huge graphs) to work out the dependencies and create an order for updating the nodes.

I further want to avoid cycles in a graph because cyclic dependencies will break the updater algorithm and causing a forever running loop.

There are recursive approaches to finding cycles with DFS by tracking nodes on the recursion stack, but is there a way to do it iteratively? I could then embed the cycle search in the main dependency resolver to speed things up.

Upvotes: 4

Views: 4063

Answers (2)

Prune
Prune

Reputation: 77880

There are plenty of cycle-detection algorithms available on line. The simplest ones are augmented versions of Dijkstra's algorithm. You maintain a list of visited nodes and costs to get there. In your design, replace the "cost" with the path to get there.

In each iteration of the algorithm, you grab the next node on the "active" list and look at each node that follows it in the graph (i.e. each of its dependencies). If that node is on the "visited" list, then you have a cycle. The path you maintained in getting here shows the loop path.

Is that enough to get you moving?

Upvotes: 2

James Poag
James Poag

Reputation: 2380

Try a timestamp. Add a meta timestamp and set it to zero on your nodes.

Previous Answer (non applicable):

When you start a search, increment or grab a time() stamp. Then, when you visit a node, compare it to the current search timestamp. If it is the same, then you have found a cycle. If not then set the stamp to current.

Next search, increment again.

Ok, this is how I'm assuming you are performing your DFS search:

  • Add Root node to a stack (for searching) and a vector (for updating).
  • Pop the stack and add children of the current node to the stack and to the vector
  • loop until stack is empty
  • reverse iterate the vector and update values (by referencing child nodes)

The problem: Cycles will cause the same set of nodes to be added to the stack.

Solution 1: Use a boolean/timestamp to see if the node has been visited before adding to the DFS search stack. This will eliminate cycles, but will not resolve them. You can spit out an error and quit.

Solution 2: Use a timestamp, but increment it each time you pop the stack. If a child node has a timestamp set, and it is less than the current stamp, you have found a cycle. Here's the kicker. When iterating over the values backwards, you can check the timestamps of the child nodes to see if they are greater than the current node. If less, then you've found a cycle, but you can use a default value.

In fact, I think Solution 1 can be resolved the same way by never following more than one child when updating the value and setting all nodes to a default value on start. Solution 2 will give you a warning while evaluating the graph whereas solution 1 only gives you a warning when creating the vector.

Upvotes: 1

Related Questions