-
Notifications
You must be signed in to change notification settings - Fork 430
Description
Bug Report: all_simple_paths generates self-looping cycles when source=target
Description
When using all_simple_paths with source equal to target, the function incorrectly generates self-looping cycles instead of returning an empty result or handling this edge case appropriately.
An example is as follows:
use petgraph::Graph;
use petgraph::algo::all_simple_paths;
use petgraph::graph::NodeIndex;
use std::collections::hash_map::RandomState;
fn main() {
// Create a directed graph
let mut graph = Graph::new();
let a = graph.add_node("A");
let b = graph.add_node("B");
let c = graph.add_node("C");
// Add edges for complete graph (every node connected to every other node)
graph.add_edge(a, b, ());
graph.add_edge(a, c, ());
graph.add_edge(b, a, ());
graph.add_edge(b, c, ());
graph.add_edge(c, a, ());
graph.add_edge(c, b, ());
// Find all simple paths from A to A
let paths: Vec<Vec<NodeIndex>> = all_simple_paths::<Vec<NodeIndex>, _, RandomState>(
&graph, a, a, 0, None
).collect();
println!("Found {} paths from A to A:", paths.len());
for (i, path) in paths.iter().enumerate() {
print!("Path {}: ", i + 1);
for (j, &node) in path.iter().enumerate() {
if j > 0 { print!(" -> "); }
print!("{}", graph[node]);
}
println!();
}
}Expected Behavior
When source equals target, the function should either:
- Return an empty iterator (no simple paths from a node to itself)
- Return a single path containing only the source node
(See all_simple_paths returns empty generator when the source is one of the possible targets networkx/networkx#6690 for discussion on the design choice here. In summary, they chose the second approach for consistency with other APIs)
Actual Behavior
The function generates self-looping cycles, which violates the definition of "simple paths" (paths without repeated vertices).
Example output:
Found 2 paths from A to A:
Path 1: A -> C -> A
Path 2: A -> B -> A
These are cycles, not simple paths, since they repeat the starting vertex A.
Feature Request: Support multiple targets in all_simple_paths
Description
Currently, all_simple_paths only supports finding paths from a source to a single target. Adding support for multiple targets would provide significant performance benefits when searching for paths to any of several possible destinations.
Instead of calling all_simple_paths multiple times for different targets, a single call could find paths to any of the specified targets. This reduces redundant graph traversal when the source and path exploration overlap. Reference: networkx/networkx#3138
Both issues affect the usability and correctness of the path-finding functionality in petgraph.