Skip to content

Bug in all_simple_paths when source=target and feature request for multiple targets #864

@lazyhope

Description

@lazyhope

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:

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    A-crateArea: Petgraph crate functionalityC-bugfixCategory: PR with bug fixC-feature-requestCategory: A feature request🔴 B-logicalBug: Logical error

    Type

    No type

    Projects

    No projects

    Milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions