`rustworkx_core::dag_algo::longest_path` panics when `NodeId: PartialOrd` but not `Ord`

[jakelishman]

Information

• rustworkx version: 0.17.1
• Python version: -
• Rust version: 1.85
• Operating system: macOS

What is the current behavior?

longest_path declares a bound on G::NodeId: PartialOrd, but then simply calls Option::unwrap on the result of partial_cmp. If you have a weird node type where the node ids are only partially ordered, this can cause panics.

What is the expected behavior?

The function shouldn't panic. Either require Ord completely to break the ties, or supply a default in unwrap_or.

Upping the bound from PartialOrd to Ord could be considered a breaking API change, but a) rustworkx-core is still pre-v1, b) you have to deliberately jump through quite some hoops to get a NodeId: PartialOrd + !Ord and c) the implementation for PartialOrd + !Ord is kind of broken as-is so it can't really be used.

Steps to reproduce the problem

You can patch dag_algo.rs with this additional test, then run it with

cargo test -p rustworkx-core --lib

diff --git a/rustworkx-core/src/dag_algo.rs b/rustworkx-core/src/dag_algo.rs
index aa5a17c4..a210a5c5 100644
--- a/rustworkx-core/src/dag_algo.rs
+++ b/rustworkx-core/src/dag_algo.rs
@@ -823,6 +823,95 @@ mod test_longest_path {
         assert_eq!(result, Ok(Some((vec![], 0))));
     }
 
+    #[test]
+    fn test_partial_ord_id() {
+        use petgraph::prelude::*;
+        use petgraph::visit::*;
+
+        #[derive(Clone, Copy, Hash, PartialEq, Eq, Debug)]
+        struct WeirdNodeId(usize);
+        impl PartialOrd for WeirdNodeId {
+            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+                (self.0 % 2 == other.0 % 2).then_some(self.0.cmp(&other.0))
+            }
+        }
+
+        #[derive(Clone, Copy, Debug)]
+        struct MyGraph {
+            len: usize,
+        }
+        impl GraphBase for MyGraph {
+            type NodeId = WeirdNodeId;
+            type EdgeId = (WeirdNodeId, WeirdNodeId);
+        }
+        impl GraphProp for MyGraph {
+            type EdgeType = Directed;
+        }
+        impl Data for MyGraph {
+            type NodeWeight = ();
+            type EdgeWeight = ();
+        }
+        impl IntoNodeIdentifiers for &MyGraph {
+            type NodeIdentifiers = std::vec::IntoIter<WeirdNodeId>;
+            fn node_identifiers(self) -> Self::NodeIdentifiers {
+                (0..self.len)
+                    .map(WeirdNodeId)
+                    .collect::<Vec<_>>()
+                    .into_iter()
+            }
+        }
+        impl IntoNeighbors for &MyGraph {
+            type Neighbors = std::option::IntoIter<Self::NodeId>;
+            fn neighbors(self, _a: Self::NodeId) -> Self::Neighbors {
+                None.into_iter()
+            }
+        }
+        impl IntoNeighborsDirected for &MyGraph {
+            type NeighborsDirected = std::option::IntoIter<Self::NodeId>;
+            fn neighbors_directed(
+                self,
+                _a: Self::NodeId,
+                _dir: Direction,
+            ) -> Self::NeighborsDirected {
+                None.into_iter()
+            }
+        }
+        impl<'a> IntoEdgeReferences for &'a MyGraph {
+            type EdgeRef = (Self::NodeId, Self::NodeId, &'a ());
+            type EdgeReferences = std::option::IntoIter<Self::EdgeRef>;
+            fn edge_references(self) -> Self::EdgeReferences {
+                None.into_iter()
+            }
+        }
+        impl IntoEdges for &MyGraph {
+            type Edges = std::option::IntoIter<Self::EdgeRef>;
+            fn edges(self, _a: Self::NodeId) -> Self::Edges {
+                None.into_iter()
+            }
+        }
+        impl IntoEdgesDirected for &MyGraph {
+            type EdgesDirected = std::option::IntoIter<Self::EdgeRef>;
+            fn edges_directed(self, _a: Self::NodeId, _dir: Direction) -> Self::EdgesDirected {
+                None.into_iter()
+            }
+        }
+        impl Visitable for MyGraph {
+            type Map = std::collections::HashSet<WeirdNodeId>;
+            fn visit_map(&self) -> Self::Map {
+                Self::Map::with_capacity(self.len)
+            }
+            fn reset_map(&self, map: &mut Self::Map) {
+                map.clear()
+            }
+        }
+
+        let graph = MyGraph { len: 4 };
+        assert_eq!(
+            longest_path(&graph, |_| Ok::<_, std::convert::Infallible>(1)),
+            Ok(Some((vec![WeirdNodeId(3)], 0)))
+        )
+    }
+
     #[test]
     fn test_single_node_graph() {
         let mut graph: DiGraph<(), ()> = DiGraph::new();

which will give you something like

---- dag_algo::test_longest_path::test_partial_ord_id stdout ----

thread 'dag_algo::test_longest_path::test_partial_ord_id' (30047979) panicked at rustworkx-core/src/dag_algo.rs:324:45:
called `Option::unwrap()` on a `None` value

[mtreinish]

We should just update the trait bound to NodeId: Ord the IndexType trait from petgraph already requires Ord https://docs.rs/petgraph/latest/petgraph/graph/trait.IndexType.html so we can reasonably fix that. I don't really consider it a breaking change more of a fix, but we should still document it in the release notes when it's fixed.