1
$\begingroup$

Assuming I have a computer representation of a graph presented in the figure below:enter image description here

How can I find out whether there are some close-loops inside the graph, like the one marked in red (or more complicated ones)? In other words I need to create an algorithm that will check if there are some "recurencies" in the graph. By recurencies I mean the situation where one node will be producing results that will be used further down by nodes that are inputs to the first node.

Any tips, key words or directions where to look for the solution will be much appreciated. I am new to the subject so please let me know if something needs more explanation.

$\endgroup$
1
$\begingroup$

You are checking if this graph is a “directed acyclic graph,” i.e. if the graph contains any cycles. Searching for that should provide many methods for this.

One approach would be to assign a weight of $-1$ to all nodes in the graph and use one extra update on top of the regular $n$ updates of the Floyd-Warshall algorithm to detect if there is a negative cost cycle in the graph.

This works because having a cycle in the original graph is equivalent to having a negative cost cycle in the $-1$ weighted graph.

If there are $n$ vertices in the graph, the algorithm would run in $\Theta(n^3)$ time and use $\Theta(n^2)$ space.

If you’re using Python, you could use this implementation from SciPy and check if it raises a “negative cycle error”.

Another approach that would be faster and of less space is to check if a depth first search on the graph ever brings you back to a node you’ve already seen. If you have $n$ vertices and $m$ edges in the graph, this would take $\Theta(n+m) = \mathcal{O}(n^2)$ time and $\Theta(n)$ space.

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