Function all_simple_paths

pub fn all_simple_paths<TargetColl, G>(
    graph: G,
    from: G::NodeId,
    to: G::NodeId,
    min_intermediate_nodes: usize,
    max_intermediate_nodes: Option<usize>,
) -> impl Iterator<Item = TargetColl>
where
    G: NodeCount + IntoNeighborsDirected,
    G::NodeId: Eq + Hash,
    TargetColl: FromIterator<G::NodeId>,

Returns an iterator that produces all simple paths from from node to to, which contains at least min_intermediate_nodes nodes and at most max_intermediate_nodes, if given, or limited by the graph’s order otherwise. The simple path is a path without repetitions.

This algorithm is adapted from https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.all_simple_paths.html.

Example

use petgraph::{algo, prelude::*};

let mut graph = DiGraph::<&str, i32>::new();

let a = graph.add_node("a");
let b = graph.add_node("b");
let c = graph.add_node("c");
let d = graph.add_node("d");

graph.extend_with_edges(&[(a, b, 1), (b, c, 1), (c, d, 1), (a, b, 1), (b, d, 1)]);

let paths = algo::all_simple_paths::<Vec<_>, _>(&graph, a, d, 0, None)
  .collect::<Vec<_>>();

assert_eq!(paths.len(), 4);


// Take only 2 paths.
let paths = algo::all_simple_paths::<Vec<_>, _>(&graph, a, d, 0, None)
  .take(2)
  .collect::<Vec<_>>();

assert_eq!(paths.len(), 2);

Note

The number of simple paths between a given pair of vertices almost always grows exponentially, reaching O(V!) on a dense graphs at V vertices.

So if you have a large enough graph, be prepared to wait for the results for years. Or consider extracting only part of the simple paths using the adapter Iterator::take.