-
Notifications
You must be signed in to change notification settings - Fork 132
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
rx.digraph_find_cycle() does not find the cycle in a graph #1171
Comments
That sounds pretty bad. I haven’t reproduced the issue yet, but to give you a reasoning:
Until we fix it in 0.14.3 or 0.15.0 please use https://www.rustworkx.org/apiref/rustworkx.strongly_connected_components.html and pick a component with more than one node. That method is correct and should always give you a cycle. I will probably fix |
I verified the problem. It is with the arbitrarily chosen starting node. If you pick this one (I plotted the graph to see the cycle):
You get:
I'll try to change the behaviour of |
Also, completely unrelated to the bug but you would probably like |
Thanks for looking into the bug. I am confused about your reasoning for the bug. The DFS cycle detection algorithm should find a cycle regardless of which arbitrary node was picked when the given graph is connected and only has one component. In my example, the given graph is a single connected graph. If you are saying the DFS algorithm attempts to find a cycle that has to contain the random starting node if none was given, that would explain the bug. But it is a misleading design choice. For example, if the input is a huge graph with a tiny cycle, this algorithm would have a very small chance of returning the cycle unless the user already knows where the tiny cycle is (in which case, what's the point of running this function anyway?). Was this intentional? I think the expected behavior for And I do not think there is anything wrong with |
In short, yes, it is a misnomer. A better name for the function would be Also, |
So currently, if I want to find a cycle in the graph without knowing which node is in it, I need to write a wrapper to make sure I visit all the nodes? Do you plan to support it? |
We will fix it in 0.15 to make it smarter and always return a cycle if it exists. If you need an urgent workaround I suggest checking the strongly connected components. Any component with more than one element is a cycle |
Information
What is the current behavior?
rx.is_directed_acyclic_graph(graph)
returns False butrx.digraph_find_cycle(graph)
fails to find the cycle in the graph.What is the expected behavior?
When
rx.is_directed_acyclic_graph(graph)
returns False,rx.digraph_find_cycle(graph)
should find a cycle in the graph.Steps to reproduce the problem
Running the following script several times. It quite often reproduces the bug. The graph is always correctly identified as not a DAG, but quite often
rx.digraph_find_cycle(graph)
does not find a cycle.Quite often the script produces:
The text was updated successfully, but these errors were encountered: