Function all_simple_paths_multi

Source

pub fn all_simple_paths_multi<'a, TargetColl, G, S, F, C>(
    graph: G,
    from: G::NodeId,
    to: &'a HashSet<G::NodeId, S>,
    min_intermediate_nodes: usize,
    max_intermediate_nodes: Option<usize>,
    initial_cost: C,
    min_cost: Option<C>,
    cost_fn: F,
) -> impl Iterator<Item = (TargetColl, C)> + 'awhere
    G: NodeCount + IntoEdgesDirected + 'a,
    <G as IntoEdgesDirected>::EdgesDirected: 'a,
    G::NodeId: Eq + Hash,
    TargetColl: FromIterator<G::NodeId>,
    S: BuildHasher + Default,
    C: Clone + PartialOrd + 'a,
    F: Fn(C, &<<G as IntoEdgeReferences>::EdgeRef as EdgeRef>::Weight, usize) -> C + 'a,

Expand description

Calculate all simple paths from a source node to any of several target nodes.

This function is a variant of all_simple_paths that accepts a HashSet of target nodes instead of a single one. A path is yielded as soon as it reaches any node in the to set.

§Performance Considerations

The efficiency of this function hinges on the graph’s structure. It provides significant performance gains on graphs where paths share long initial segments (e.g., trees and DAGs), as the benefit of a single traversal outweighs the HashSet lookup overhead.

Conversely, in dense graphs where paths diverge quickly or for targets very close to the source, the lookup overhead could make repeated calls to all_simple_paths a faster alternative.

Note: If security is not a concern, a faster hasher (e.g., FxBuildHasher) can be specified to minimize the HashSet lookup overhead.

§Arguments

graph: an input graph.
from: an initial node of desired paths.
to: a HashSet of target nodes. A path is yielded as soon as it reaches any node in this set.
min_intermediate_nodes: the minimum number of nodes in the desired paths.
max_intermediate_nodes: the maximum number of nodes in the desired paths (optional).
initial_cost: the starting cost value before any edges are traversed.
min_cost: an optional threshold. If the accumulated cost drops below this value (via PartialOrd), the branch is pruned — it is neither yielded nor explored further.
cost_fn: an accumulator function (accumulated_cost, &edge_weight, edge_count) -> new_cost applied at each edge. The edge_count is the 0-based hop number from the source (i.e., 0 for the first edge, 1 for the second, etc.).

§Returns

Returns an iterator that produces (path, cost) tuples for all simple paths from from node to any node in the to set, which contains at least min_intermediate_nodes and at most max_intermediate_nodes intermediate nodes, if given, or limited by the graph’s order otherwise. The cost is the result of folding cost_fn over the edge weights along the path. Paths whose accumulated cost falls below min_cost at any point are excluded.

§Complexity

Time complexity: for computing the first k paths, the running time will be O(k|V| + k|E|).
Auxiliary space: O(|V|).

where |V| is the number of nodes and |E| is the number of edges.

§Example

use petgraph::prelude::*;
use std::collections::HashSet;
use std::collections::hash_map::RandomState;

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), (b, d, 1)]);

// Find paths from "a" to either "c" or "d", accumulating edge costs.
let targets = HashSet::from_iter([c, d]);
let mut paths = all_simple_paths_multi::<Vec<_>, _, RandomState, _, _>(
    &graph, a, &targets, 0, None, 0i32, None, |cost, weight, _| cost + weight,
)
    .collect::<Vec<_>>();

paths.sort_by_key(|(p, _)| p.clone());
let expected_paths = vec![
    (vec![a, b, c], 2),
    (vec![a, b, d], 2),
];

assert_eq!(paths, expected_paths);

all_simple_paths_multi