CODEWITHSUNDEEP
algorithmlanguage-agnosticgraph-algorithm
Jakub Arnold
Jakub Arnold

Reputation: 87220

Detecting cycles in an oriented dependency graph and detecting if a vertex is part of the cycle or just depending on one

Given an oriented graph, I need a way to detect cycles in the graph, as well as find if a vertex is in a cycle, or just has an edge to one of the vertices in a cycle.

Here's an example:

A -> B
B -> A
C -> A

The A -> B and B -> A form a cycle in this case, and should be colored in one way, but the vertex C isn't part of the cycle, it just has an edge into the cycle, so it should be colored in a different way.

I can easily detect the cycles themself, by just starting at a random vertex, coloring it, and then doing DFS. If I hit a vertex with the same color, I know I'm in a cycle and will recursively propagate the error back. The problem is that it doesn't allow me to see if the error I got from a recursive call is because I'm currently in a cycle, or because I'm just pointing at one that was previously detected.

The graph basically represents dependencies of lazily evaluated cells, where I'm trying to see if a cell failed to evaluated because it transitively references itself, or because it depends on some other cell which is in a cycle (those two should be different errors.)

The way I have it implemented right now, I simply force evaluation on all the dependencies of a current cell, and assign the value based on the result of that evaluation. But as mentioned previously, this recursion doesn't allow me to distinguish the two cases.

Upvotes: 1

Views: 856

Answers (1)

M. Page
M. Page

Reputation: 2814

Tarjan algorithm for searching strongly connected components of a directed graph http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm allows you to make the distinction you need.

Upvotes: 1

Related Questions