Repository: Qiskit/rustworkx (language: python)

Issue:
rx.digraph_find_cycle() does not find the cycle in a graph
<!-- ⚠️ If you do not respect this template, your issue will be closed -->
<!-- ⚠️ Make sure to browse the opened and closed issues -->

### Information

- **rustworkx version**: 0.14.2
- **Python version**: 3.10.14
- **Rust version**: rustc 1.66.0-nightly (8b705839c 2022-09-26)
- **Operating system**: Linux

### What is the current behavior?
`rx.is_directed_acyclic_graph(graph)` returns False but `rx.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.
```
import rustworkx as rx

edges = [
    (6, 7),
    (8, 9),
    (15, 16),
    (0, 6),
    (2, 8),
    (9, 10),
    (7, 10),
    (10, 11),
    (11, 12),
    (10, 12),
    (12, 13),
    (12, 14),
    (4, 15),
    (16, 17),
    (14, 3),
    (13, 17),
    (17, 18),
    (18, 19),
    (17, 19),
    (19, 20),
    (19, 5),
    (20, 1),
    (27, 28),
    (28, 29),
    (34, 35),
    (21, 27),
    (23, 29),
    (29, 30),
    (30, 31),
    (29, 31),
    (31, 32),
    (31, 33),
    (25, 34),
    (32, 24),
    (35, 36),
    (33, 36),
    (36, 37),
    (37, 38),
    (36, 38),
    (38, 39),
    (38, 26),
    (39, 22),
    (42, 45),
    (44, 45),
    (40, 44),
    (45, 46),
    (46, 47),
    (45, 47),
    (47, 48),
    (47, 49),
    (48, 43),
    (49, 41),
    (56, 57),
    (57, 58),
    (61, 63),
    (50, 56),
    (52, 57),
    (58, 59),
    (57, 59),
    (59, 60),
    (54, 62),
    (59, 61),
    (60, 53),
    (62, 63),
    (63, 64),
    (64, 65),
    (63, 65),
    (65, 66),
    (65, 67),
    (66, 51),
    (67, 55),
    (74, 75),
    (75, 76),
    (80, 81),
    (68, 74),
    (70, 76),
    (76, 77),
    (77, 78),
    (76, 78),
    (78, 79),
    (78, 80),
    (72, 81),
    (79, 71),
    (81, 82),
    (82, 83),
    (81, 83),
    (83, 84),
    (83, 69),
    (84, 73),
    (1, 42),
    (3, 23),
    (24, 72),
    (22, 50),
    (5, 54),
    (41, 40),
    (26, 52),
    (69, 70),
]
edges = [x + (None,) for x in edges]
nodes = set()
for edge in edges:
    nodes.add(edge[0])
    nodes.add(edge[1])
nodes = list(nodes)

# Create a directed graph (PyDiGraph)
graph = rx.PyDiGraph()

# Add nodes and edges
graph.add_nodes_from(nodes)
graph.add_edges_from(edges)

# Check if the graph is a DAG
is_dag = rx.is_directed_acyclic_graph(graph)
print("Is the graph a DAG? {}".format(is_dag))

# Attempt to find a cycle
cycle = rx.digraph_find_cycle(graph)
print("Cycle found : {}".format(cycle))
```
Quite often the script produces:
```
Is the graph a DAG? False
Cycle found : EdgeList[]
```


Discussion / hints:
That sounds pretty bad. I haven’t reproduced the issue yet, but to give you a reasoning:
* The first method that is correct uses topological sort
* The second method runs a DFS to find a cycle with a given node. If you don’t specify we pick an arbitrary one, which could explain why you get no cycle at all

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 `find_cycle` using the SCC implementation 
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): 
```
cycle = rx.digraph_find_cycle(graph, graph.find_node_by_weight(81))
print(cycle)
```

You get:
```
EdgeList[(81, 82), (82, 83), (83, 69), (69, 70), (70, 76), (76, 77), (77, 78), (78, 80), (80, 81)]
```

I'll try to change the behaviour of `rx.is_directed_acyclic_graph(graph)`. It should always return a cycle if it exists and node is specified. I agree it is a bit misleading. But probably the original intention was to pass a node you already knew was in a cycle as an argument
Also, completely unrelated to the bug but you would probably like [`add_edges_from_no_data`](https://www.rustworkx.org/apiref/rustworkx.PyDAG.add_edges_from_no_data.html). You don't need to create the new edge list you created, just call `graph.add_edges_from_no_data(edges)` instead of `graph.add_edges(edges)` if you don't have weights.


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 `rx.digraph_find_cycle(graph)` should be that it always finds a cycle (if there is one) when no starting node is specified. It should find a cycle containing the starting node when one is given.

And I do not think there is anything wrong with `rx.is_directed_acyclic_graph(graph)`. It seems to correctly decide whether the graph is a DAG.
> 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 `rx.digraph_find_cycle(graph)` should be that it always finds a cycle (if there is one) when no starting node is specified. It should find a cycle containing the starting node when one is given.
> 
> And I do not think there is anything wrong with `rx.is_directed_acyclic_graph(graph)`. It seems to correctly decide whether the graph is a DAG.

In short, yes, it is a misnomer. A better name for the function would be `digraph_find_cycle_containing_node`.

Also, `is-directed_acyclic_graph` has an independent implementation that behaves as you expected.
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?
> 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

Fix patch:
diff --git a/releasenotes/notes/fix-digraph-find-cycle-141e302ff4a8fcd4.yaml b/releasenotes/notes/fix-digraph-find-cycle-141e302ff4a8fcd4.yaml
new file mode 100644
index 000000000..578459129
--- /dev/null
+++ b/releasenotes/notes/fix-digraph-find-cycle-141e302ff4a8fcd4.yaml
@@ -0,0 +1,12 @@
+---
+fixes:
+  - |
+    Fixed the behavior of :func:`~rustworkx.digraph_find_cycle` when
+    no source node was provided. Previously, the function would start looking
+    for a cycle at an arbitrary node which was not guaranteed to return a cycle.
+    Now, the function will smartly choose a source node to start the search from
+    such that if a cycle exists, it will be found.
+other:
+  - |
+    The `rustworkx-core` function `rustworkx_core::connectivity::find_cycle` now
+    requires the `petgraph::visit::Visitable` trait.
diff --git a/rustworkx-core/src/connectivity/find_cycle.rs b/rustworkx-core/src/connectivity/find_cycle.rs
index 4bbd755e5..c04847c50 100644
--- a/rustworkx-core/src/connectivity/find_cycle.rs
+++ b/rustworkx-core/src/connectivity/find_cycle.rs
@@ -11,8 +11,9 @@
 // under the License.
 
 use hashbrown::{HashMap, HashSet};
+use petgraph::algo;
 use petgraph::visit::{
-    EdgeCount, GraphBase, IntoNeighborsDirected, IntoNodeIdentifiers, NodeCount,
+    EdgeCount, GraphBase, IntoNeighborsDirected, IntoNodeIdentifiers, NodeCount, Visitable,
 };
 use petgraph::Direction::Outgoing;
 use std::hash::Hash;
@@ -57,22 +58,22 @@ where
     G: GraphBase,
     G: NodeCount,
     G: EdgeCount,
-    for<'b> &'b G: GraphBase<NodeId = G::NodeId> + IntoNodeIdentifiers + IntoNeighborsDirected,
+    for<'b> &'b G:
+        GraphBase<NodeId = G::NodeId> + IntoNodeIdentifiers + IntoNeighborsDirected + Visitable,
     G::NodeId: Eq + Hash,
 {
     // Find a cycle in the given graph and return it as a list of edges
-    let mut graph_nodes: HashSet<G::NodeId> = graph.node_identifiers().collect();
     let mut cycle: Vec<(G::NodeId, G::NodeId)> = Vec::with_capacity(graph.edge_count());
-    let temp_value: G::NodeId;
-    // If source is not set get an arbitrary node from the set of graph
-    // nodes we've not "examined"
+    // If source is not set get a node in an arbitrary cycle if it exists,
+    // otherwise return that there is no cycle
     let source_index = match source {
         Some(source_value) => source_value,
-        None => {
-            temp_value = *graph_nodes.iter().next().unwrap();
-            graph_nodes.remove(&temp_value);
-            temp_value
-        }
+        None => match find_node_in_arbitrary_cycle(&graph) {
+            Some(node_in_cycle) => node_in_cycle,
+            None => {
+                return Vec::new();
+            }
+        },
     };
     // Stack (ie "pushdown list") of vertices already in the spanning tree
     let mut stack: Vec<G::NodeId> = vec![source_index];
@@ -119,11 +120,47 @@ where
     cycle
 }
 
+fn find_node_in_arbitrary_cycle<G>(graph: &G) -> Option<G::NodeId>
+where
+    G: GraphBase,
+    G: NodeCount,
+    G: EdgeCount,
+    for<'b> &'b G:
+        GraphBase<NodeId = G::NodeId> + IntoNodeIdentifiers + IntoNeighborsDirected + Visitable,
+    G::NodeId: Eq + Hash,
+{
+    for scc in algo::kosaraju_scc(&graph) {
+        if scc.len() > 1 {
+            return Some(scc[0]);
+        }
+    }
+    for node in graph.node_identifiers() {
+        for neighbor in graph.neighbors_directed(node, Outgoing) {
+            if neighbor == node {
+                return Some(node);
+            }
+        }
+    }
+    None
+}
+
 #[cfg(test)]
 mod tests {
     use crate::connectivity::find_cycle;
     use petgraph::prelude::*;
 
+    // Utility to assert cycles in the response
+    macro_rules! assert_cycle {
+        ($g: expr, $cycle: expr) => {{
+            for i in 0..$cycle.len() {
+                let (s, t) = $cycle[i];
+                assert!($g.contains_edge(s, t));
+                let (next_s, _) = $cycle[(i + 1) % $cycle.len()];
+                assert_eq!(t, next_s);
+            }
+        }};
+    }
+
     #[test]
     fn test_find_cycle_source() {
         let edge_list = vec![
@@ -141,20 +178,13 @@ mod tests {
             (8, 9),
         ];
         let graph = DiGraph::<i32, i32>::from_edges(edge_list);
-        let mut res: Vec<(usize, usize)> = find_cycle(&graph, Some(NodeIndex::new(0)))
-            .iter()
-            .map(|(s, t)| (s.index(), t.index()))
-            .collect();
-        assert_eq!(res, [(0, 1), (1, 2), (2, 3), (3, 0)]);
-        res = find_cycle(&graph, Some(NodeIndex::new(1)))
-            .iter()
-            .map(|(s, t)| (s.index(), t.index()))
-            .collect();
-        assert_eq!(res, [(1, 2), (2, 3), (3, 0), (0, 1)]);
-        res = find_cycle(&graph, Some(NodeIndex::new(5)))
-            .iter()
-            .map(|(s, t)| (s.index(), t.index()))
-            .collect();
+        for i in [0, 1, 2, 3].iter() {
+            let idx = NodeIndex::new(*i);
+            let res = find_cycle(&graph, Some(idx));
+            assert_cycle!(graph, res);
+            assert_eq!(res[0].0, idx);
+        }
+        let res = find_cycle(&graph, Some(NodeIndex::new(5)));
         assert_eq!(res, []);
     }
 
@@ -176,10 +206,32 @@ mod tests {
         ];
         let mut graph = DiGraph::<i32, i32>::from_edges(edge_list);
         graph.add_edge(NodeIndex::new(1), NodeIndex::new(1), 0);
-        let res: Vec<(usize, usize)> = find_cycle(&graph, Some(NodeIndex::new(0)))
-            .iter()
-            .map(|(s, t)| (s.index(), t.index()))
-            .collect();
-        assert_eq!(res, [(1, 1)]);
+        let res = find_cycle(&graph, Some(NodeIndex::new(0)));
+        assert_eq!(res[0].0, NodeIndex::new(1));
+        assert_cycle!(graph, res);
+    }
+
+    #[test]
+    fn test_self_loop_no_source() {
+        let edge_list = vec![(0, 1), (1, 2), (2, 3), (2, 2)];
+        let graph = DiGraph::<i32, i32>::from_edges(edge_list);
+        let res = find_cycle(&graph, None);
+        assert_cycle!(graph, res);
+    }
+
+    #[test]
+    fn test_cycle_no_source() {
+        let edge_list = vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 2)];
+        let graph = DiGraph::<i32, i32>::from_edges(edge_list);
+        let res = find_cycle(&graph, None);
+        assert_cycle!(graph, res);
+    }
+
+    #[test]
+    fn test_no_cycle_no_source() {
+        let edge_list = vec![(0, 1), (1, 2), (2, 3)];
+        let graph = DiGraph::<i32, i32>::from_edges(edge_list);
+        let res = find_cycle(&graph, None);
+        assert_eq!(res, []);
     }
 }


Test patch:
diff --git a/tests/digraph/test_find_cycle.py b/tests/digraph/test_find_cycle.py
index 5e09d3520..0b9b67bab 100644
--- a/tests/digraph/test_find_cycle.py
+++ b/tests/digraph/test_find_cycle.py
@@ -13,6 +13,7 @@
 import unittest
 
 import rustworkx
+import rustworkx.generators
 
 
 class TestFindCycle(unittest.TestCase):
@@ -36,6 +37,14 @@ def setUp(self):
             ]
         )
 
+    def assertCycle(self, first_node, graph, res):
+        self.assertEqual(first_node, res[0][0])
+        for i in range(len(res)):
+            s, t = res[i]
+            self.assertTrue(graph.has_edge(s, t))
+            next_s, _ = res[(i + 1) % len(res)]
+            self.assertEqual(t, next_s)
+
     def test_find_cycle(self):
         graph = rustworkx.PyDiGraph()
         graph.add_nodes_from(list(range(6)))
@@ -43,13 +52,13 @@ def test_find_cycle(self):
             [(0, 1), (0, 3), (0, 5), (1, 2), (2, 3), (3, 4), (4, 5), (4, 0)]
         )
         res = rustworkx.digraph_find_cycle(graph, 0)
-        self.assertEqual([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)], res)
+        self.assertCycle(0, graph, res)
 
     def test_find_cycle_multiple_roots_same_cycles(self):
         res = rustworkx.digraph_find_cycle(self.graph, 0)
-        self.assertEqual(res, [(0, 1), (1, 2), (2, 3), (3, 0)])
+        self.assertCycle(0, self.graph, res)
         res = rustworkx.digraph_find_cycle(self.graph, 1)
-        self.assertEqual(res, [(1, 2), (2, 3), (3, 0), (0, 1)])
+        self.assertCycle(1, self.graph, res)
         res = rustworkx.digraph_find_cycle(self.graph, 5)
         self.assertEqual(res, [])
 
@@ -57,9 +66,9 @@ def test_find_cycle_disconnected_graphs(self):
         self.graph.add_nodes_from(["A", "B", "C"])
         self.graph.add_edges_from_no_data([(10, 11), (12, 10), (11, 12)])
         res = rustworkx.digraph_find_cycle(self.graph, 0)
-        self.assertEqual(res, [(0, 1), (1, 2), (2, 3), (3, 0)])
+        self.assertCycle(0, self.graph, res)
         res = rustworkx.digraph_find_cycle(self.graph, 10)
-        self.assertEqual(res, [(10, 11), (11, 12), (12, 10)])
+        self.assertCycle(10, self.graph, res)
 
     def test_invalid_types(self):
         graph = rustworkx.PyGraph()
@@ -69,4 +78,28 @@ def test_invalid_types(self):
     def test_self_loop(self):
         self.graph.add_edge(1, 1, None)
         res = rustworkx.digraph_find_cycle(self.graph, 0)
-        self.assertEqual([(1, 1)], res)
+        self.assertCycle(1, self.graph, res)
+
+    def test_no_cycle_no_source(self):
+        g = rustworkx.generators.directed_grid_graph(10, 10)
+        res = rustworkx.digraph_find_cycle(g)
+        self.assertEqual(res, [])
+
+    def test_cycle_no_source(self):
+        g = rustworkx.generators.directed_path_graph(1000)
+        a = g.add_node(1000)
+        b = g.node_indices()[-2]
+        g.add_edge(b, a, None)
+        g.add_edge(a, b, None)
+        res = rustworkx.digraph_find_cycle(g)
+        self.assertEqual(len(res), 2)
+        self.assertTrue(res[0] == res[1][::-1])
+
+    def test_cycle_self_loop(self):
+        g = rustworkx.generators.directed_path_graph(1000)
+        a = g.add_node(1000)
+        b = g.node_indices()[-1]
+        g.add_edge(b, a, None)
+        g.add_edge(a, a, None)
+        res = rustworkx.digraph_find_cycle(g)
+        self.assertEqual(res, [(a, a)])