19053565245

Committed 04 Nov 2025 12:02AM UTC coverage: 94.175% (-0.01%) from 94.186%

Build # 19053565245

Build Type

push

github

Committed by

web-flow

Commit Message

Improve all simple paths multi-target performance (#1520)

* Integrate petgraph's mult-target version of all_simple_paths

* Add release note

* Resolve review comments

Coverage Stats

20 of 20 new or added lines in 1 file covered. (100.0%)

2 existing lines in 1 file now uncovered.

18268 of 19398 relevant lines covered (94.17%)

958337.16 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.14

/rustworkx-core/src/connectivity/all_simple_paths.rs

// Licensed under the Apache License, Version 2.0 (the "License"); you may
// not use this file except in compliance with the License. You may obtain
// a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations
// under the License.

// This module was forked from petgraph:
//
// https://github.com/petgraph/petgraph/blob/9ff688872b467d3e1b5adef19f5c52f519d3279c/src/algo/simple_paths.rs
//
// to add support for returning all simple paths to a list of targets instead
// of just between a single node pair.

use hashbrown::HashSet;
use indexmap::IndexSet;
use indexmap::map::Entry;
use petgraph::Direction::Outgoing;
use petgraph::visit::{IntoNeighborsDirected, NodeCount};
use std::iter;
use std::{hash::Hash, iter::FromIterator};

use crate::dictmap::*;

/// Returns a dictionary with all simple paths from `from` node to all nodes in `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::prelude::*;
/// use hashbrown::HashSet;
/// use rustworkx_core::connectivity::all_simple_paths_multiple_targets;
///
/// 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 mut to_set = HashSet::new();
/// to_set.insert(d);
///
/// let ways = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, None);
///
/// let d_path = ways.get(&d).unwrap();
/// assert_eq!(4, d_path.len());
/// ```
pub fn all_simple_paths_multiple_targets<G>(
    graph: G,
    from: G::NodeId,
    to: &HashSet<G::NodeId>,
    min_intermediate_nodes: usize,
    max_intermediate_nodes: Option<usize>,
) -> DictMap<G::NodeId, Vec<Vec<G::NodeId>>>
where
    G: NodeCount,
    G: IntoNeighborsDirected,
    G::NodeId: Eq + Hash,
{
    // how many nodes are allowed in simple path up to target node
    // it is min/max allowed path length minus one, because it is more appropriate when implementing lookahead
    // than constantly add 1 to length of current path
    let max_length = if let Some(l) = max_intermediate_nodes {
        l + 1
    } else {
        graph.node_count() - 1
    };

    let min_length = min_intermediate_nodes + 1;

    // list of visited nodes
    let mut visited: IndexSet<G::NodeId> = IndexSet::from_iter(Some(from));
    // list of children of currently exploring path nodes,
    // last elem is list of children of last visited node
    let mut stack = vec![graph.neighbors_directed(from, Outgoing)];

    let mut output: DictMap<G::NodeId, Vec<Vec<G::NodeId>>> = DictMap::with_capacity(to.len());

    while let Some(children) = stack.last_mut() {
        if let Some(child) = children.next() {
            if visited.len() < max_length {
                if !visited.contains(&child) {
                    if to.contains(&child) && visited.len() >= min_length {
                        let new_path: Vec<G::NodeId> =
                            visited.iter().chain(&[child]).copied().collect();
                        match output.entry(child) {
                            Entry::Vacant(e) => {
                                e.insert(vec![new_path]);
                            }
                            Entry::Occupied(mut e) => {
                                e.get_mut().push(new_path);
                            }
                        }
                    }
                    visited.insert(child);
                    if to.iter().any(|n| !visited.contains(n)) {
                        stack.push(graph.neighbors_directed(child, Outgoing));
                    } else {
                        visited.pop();
                    }
                }
            // visited.len() == max_length
            } else {
                for c in children.chain(iter::once(child)) {
                    if to.contains(&c) && !visited.contains(&c) && visited.len() >= min_length {
                        let new_path: Vec<G::NodeId> =
                            visited.iter().chain(&[c]).copied().collect();
                        match output.entry(c) {
                            Entry::Vacant(e) => {
                                e.insert(vec![new_path]);
                            }
                            Entry::Occupied(mut e) => {
                                e.get_mut().push(new_path);
                            }
                        }
                    }
                }
                stack.pop();
                visited.pop();
            }
        } else {
            stack.pop();
            visited.pop();
        }
    }
    output
}

/// Returns the longest of all the simple paths from `from` node to all nodes in `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.
///
/// # Example
/// ```
/// use petgraph::prelude::*;
/// use hashbrown::HashSet;
/// use rustworkx_core::connectivity::longest_simple_path_multiple_targets;
///
/// 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 mut to_set = HashSet::new();
/// to_set.insert(d);
///
/// let path = longest_simple_path_multiple_targets(&graph, a, &to_set);
///
/// let expected = vec![a, b, c, d];
/// assert_eq!(path.unwrap(), expected);
/// ```
pub fn longest_simple_path_multiple_targets<G>(
    graph: G,
    from: G::NodeId,
    to: &HashSet<G::NodeId>,
) -> Option<Vec<G::NodeId>>
where
    G: NodeCount,
    G: IntoNeighborsDirected,
    G::NodeId: Eq + Hash,
{
    // list of visited nodes
    let mut visited: IndexSet<G::NodeId> = IndexSet::from_iter(Some(from));
    // list of children of currently exploring path nodes,
    // last elem is list of children of last visited node
    let mut stack = vec![graph.neighbors_directed(from, Outgoing)];

    let mut output_path: Option<Vec<G::NodeId>> = None;

    let update_path = |new_path: Vec<G::NodeId>,
                       output_path: &Option<Vec<G::NodeId>>|
     -> Option<Vec<G::NodeId>> {
        match output_path.as_ref() {
            None => Some(new_path),
            Some(path) => {
                if path.len() < new_path.len() {
                    Some(new_path)
                } else {
                    None
                }
            }
        }
    };

    while let Some(children) = stack.last_mut() {
        if let Some(child) = children.next() {
            if !visited.contains(&child) {
                if to.contains(&child) {
                    let new_path: Vec<G::NodeId> =
                        visited.iter().chain(&[child]).copied().collect();
                    let temp = update_path(new_path, &output_path);
                    if temp.is_some() {
                        output_path = temp;
                    }
                }
                visited.insert(child);
                if to.iter().any(|n| !visited.contains(n)) {
                    stack.push(graph.neighbors_directed(child, Outgoing));
                } else {
                    visited.pop();
                }
            }
        } else {
            stack.pop();
            visited.pop();
        }
    }
    output_path
}

#[cfg(test)]
mod tests {
    use crate::connectivity::{
        all_simple_paths_multiple_targets, longest_simple_path_multiple_targets,
    };
    use hashbrown::HashSet;
    use petgraph::prelude::*;

    #[test]
    fn test_all_simple_paths() {
        // create a path graph
        let mut graph = Graph::new_undirected();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);

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

        let mut to_set = HashSet::new();
        to_set.insert(d);

        let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, None);

        assert_eq!(paths.get(&d).unwrap(), &vec![vec![a, b, c, d]]);
    }

    #[test]
    fn test_all_simple_paths_with_two_targets_emits_two_paths() {
        // create a path graph
        let mut graph = Graph::new_undirected();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);

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

        let mut to_set = HashSet::new();
        to_set.insert(d);
        to_set.insert(e);

        let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, None);

        assert_eq!(
            paths.get(&d).unwrap(),
            &vec![vec![a, b, c, e, d], vec![a, b, c, d]]
        );
        assert_eq!(
            paths.get(&e).unwrap(),
            &vec![vec![a, b, c, e], vec![a, b, c, d, e]]
        );
    }

    #[test]
    fn test_digraph_all_simple_paths_with_two_targets_emits_two_paths() {
        // create a path graph
        let mut graph = Graph::new();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);

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

        let mut to_set = HashSet::new();
        to_set.insert(d);
        to_set.insert(e);

        let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, None);

        assert_eq!(paths.get(&d).unwrap(), &vec![vec![a, b, c, d]]);
        assert_eq!(
            paths.get(&e).unwrap(),
            &vec![vec![a, b, c, e], vec![a, b, c, d, e]]
        );
    }

    #[test]
    fn test_all_simple_paths_max_nodes() {
        // create a complete graph
        let mut graph = Graph::new_undirected();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);

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

        let mut to_set = HashSet::new();
        to_set.insert(b);

        let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, Some(0));

        assert_eq!(paths.get(&b).unwrap(), &vec![vec![a, b]]);

        let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, Some(1));

        assert_eq!(
            paths.get(&b).unwrap(),
            &vec![vec![a, e, b], vec![a, d, b], vec![a, c, b], vec![a, b],]
        );
    }

    #[test]
    fn test_all_simple_paths_with_two_targets_max_nodes() {
        // create a path graph
        let mut graph = Graph::new_undirected();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);

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

        let mut to_set = HashSet::new();
        to_set.insert(d);
        to_set.insert(e);

        let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, Some(2));

        assert_eq!(paths.get(&d).unwrap(), &vec![vec![a, b, c, d]]);
        assert_eq!(paths.get(&e).unwrap(), &vec![vec![a, b, c, e]]);
    }

    #[test]
    fn test_digraph_all_simple_paths_with_two_targets_max_nodes() {
        // create a path graph
        let mut graph = Graph::new();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);

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

        let mut to_set = HashSet::new();
        to_set.insert(d);
        to_set.insert(e);

        let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, Some(2));

        assert_eq!(paths.get(&d).unwrap(), &vec![vec![a, b, c, d]]);
        assert_eq!(paths.get(&e).unwrap(), &vec![vec![a, b, c, e]]);
    }

    #[test]
    fn test_all_simple_paths_with_two_targets_in_line_emits_two_paths() {
        // create a path graph
        let mut graph = Graph::new_undirected();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);

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

        let mut to_set = HashSet::new();
        to_set.insert(c);
        to_set.insert(d);

        let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, None);

        assert_eq!(paths.get(&c).unwrap(), &vec![vec![a, b, c]]);
        assert_eq!(paths.get(&d).unwrap(), &vec![vec![a, b, c, d]]);
    }

    #[test]
    fn test_all_simple_paths_min_nodes() {
        // create a cycle graph
        let mut graph = Graph::new();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);

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

        let mut to_set = HashSet::new();
        to_set.insert(d);

        let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 2, None);

        assert_eq!(paths.get(&d).unwrap(), &vec![vec![a, b, c, d]]);
    }

    #[test]
    fn test_all_simple_paths_with_two_targets_min_nodes() {
        // create a cycle graph
        let mut graph = Graph::new();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);

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

        let mut to_set = HashSet::new();
        to_set.insert(c);
        to_set.insert(d);

        let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 2, None);

        assert_eq!(paths.get(&c), None);
        assert_eq!(paths.get(&d).unwrap(), &vec![vec![a, b, c, d]]);
    }

    #[test]
    fn test_all_simple_paths_source_target() {
        // create a path graph
        let mut graph = Graph::new_undirected();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);

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

        let mut to_set = HashSet::new();
        to_set.insert(a);

        let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, None);

        assert_eq!(paths.get(&a), None);
    }

    #[test]
    fn test_all_simple_paths_on_non_trivial_graph() {
        // create a path graph
        let mut graph = Graph::new();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);
        let f = graph.add_node(5);

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

        let mut to_set = HashSet::new();
        to_set.insert(c);
        to_set.insert(d);

        let paths = all_simple_paths_multiple_targets(&graph, b, &to_set, 0, None);

        assert_eq!(
            paths.get(&c).unwrap(),
            &vec![vec![b, d, e, c], vec![b, f, e, c], vec![b, c]]
        );
        assert_eq!(
            paths.get(&d).unwrap(),
            &vec![
                vec![b, d],
                vec![b, f, e, d],
                vec![b, f, e, c, d],
                vec![b, c, d]
            ]
        );

        let paths = all_simple_paths_multiple_targets(&graph, b, &to_set, 1, None);

        assert_eq!(
            paths.get(&c).unwrap(),
            &vec![vec![b, d, e, c], vec![b, f, e, c]]
        );
        assert_eq!(
            paths.get(&d).unwrap(),
            &vec![vec![b, f, e, d], vec![b, f, e, c, d], vec![b, c, d]]
        );

        let paths = all_simple_paths_multiple_targets(&graph, b, &to_set, 0, Some(2));

        assert_eq!(
            paths.get(&c).unwrap(),
            &vec![vec![b, d, e, c], vec![b, f, e, c], vec![b, c]]
        );
        assert_eq!(
            paths.get(&d).unwrap(),
            &vec![vec![b, d], vec![b, f, e, d], vec![b, c, d]]
        );
    }

    #[test]
    fn test_longest_simple_path() {
        // create a path graph
        let mut graph = Graph::new_undirected();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);

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

        let mut to_set = HashSet::new();
        to_set.insert(d);

        let path = longest_simple_path_multiple_targets(&graph, a, &to_set);

        assert_eq!(path.unwrap(), vec![a, b, c, d]);
    }

    #[test]
    fn test_longest_simple_path_with_two_targets_emits_two_paths() {
        // create a path graph
        let mut graph = Graph::new_undirected();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);

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

        let mut to_set = HashSet::new();
        to_set.insert(d);
        to_set.insert(e);

        let path = longest_simple_path_multiple_targets(&graph, a, &to_set);

        assert_eq!(path.unwrap(), vec![a, b, c, e, d]);
    }

    #[test]
    fn test_digraph_longest_simple_path_with_two_targets_emits_two_paths() {
        // create a path graph
        let mut graph = Graph::new();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);

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

        let mut to_set = HashSet::new();
        to_set.insert(d);
        to_set.insert(e);

        let path = longest_simple_path_multiple_targets(&graph, a, &to_set);

        assert_eq!(path.unwrap(), vec![a, b, c, d, e]);
    }

    #[test]
    fn test_longest_simple_paths_with_two_targets_in_line_emits_two_paths() {
        // create a path graph
        let mut graph = Graph::new_undirected();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);

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

        let mut to_set = HashSet::new();
        to_set.insert(c);
        to_set.insert(d);

        let path = longest_simple_path_multiple_targets(&graph, a, &to_set);

        assert_eq!(path.unwrap(), vec![a, b, c, d]);
    }

    #[test]
    fn test_longest_simple_paths_source_target() {
        // create a path graph
        let mut graph = Graph::new_undirected();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);

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

        let mut to_set = HashSet::new();
        to_set.insert(a);

        let path = longest_simple_path_multiple_targets(&graph, a, &to_set);

        assert_eq!(path, None);
    }

    #[test]
    fn test_longest_simple_paths_on_non_trivial_graph() {
        // create a path graph
        let mut graph = Graph::new();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        let e = graph.add_node(4);
        let f = graph.add_node(5);

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

        let mut to_set = HashSet::new();
        to_set.insert(c);
        to_set.insert(d);

        let path = longest_simple_path_multiple_targets(&graph, b, &to_set);

        assert_eq!(path.unwrap(), vec![b, f, e, c, d],);
    }
}

1	// Licensed under the Apache License, Version 2.0 (the "License"); you may
2	// not use this file except in compliance with the License. You may obtain
3	// a copy of the License at
4	//
5	// http://www.apache.org/licenses/LICENSE-2.0
6	//
7	// Unless required by applicable law or agreed to in writing, software
8	// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
9	// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
10	// License for the specific language governing permissions and limitations
11	// under the License.
12
13	// This module was forked from petgraph:
14	//
15	// https://github.com/petgraph/petgraph/blob/9ff688872b467d3e1b5adef19f5c52f519d3279c/src/algo/simple_paths.rs
16	//
17	// to add support for returning all simple paths to a list of targets instead
18	// of just between a single node pair.
19
20	use hashbrown::HashSet;
21	use indexmap::IndexSet;
22	use indexmap::map::Entry;
23	use petgraph::Direction::Outgoing;
24	use petgraph::visit::{IntoNeighborsDirected, NodeCount};
25	use std::iter;
26	use std::{hash::Hash, iter::FromIterator};
27
28	use crate::dictmap::*;
29
30	/// Returns a dictionary with all simple paths from `from` node to all nodes in `to`, which contains at least `min_intermediate_nodes` nodes
31	/// and at most `max_intermediate_nodes`, if given, or limited by the graph's order otherwise. The simple path is a path without repetitions.
32	///
33	/// This algorithm is adapted from <https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.all_simple_paths.html>.
34	///
35	/// # Example
36	/// ```
37	/// use petgraph::prelude::*;
38	/// use hashbrown::HashSet;
39	/// use rustworkx_core::connectivity::all_simple_paths_multiple_targets;
40	///
41	/// let mut graph = DiGraph::<&str, i32>::new();
42	///
43	/// let a = graph.add_node("a");
44	/// let b = graph.add_node("b");
45	/// let c = graph.add_node("c");
46	/// let d = graph.add_node("d");
47	///
48	/// graph.extend_with_edges(&[(a, b, 1), (b, c, 1), (c, d, 1), (a, b, 1), (b, d, 1)]);
49	///
50	/// let mut to_set = HashSet::new();
51	/// to_set.insert(d);
52	///
53	/// let ways = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, None);
54	///
55	/// let d_path = ways.get(&d).unwrap();
56	/// assert_eq!(4, d_path.len());
57	/// ```
58	pub fn all_simple_paths_multiple_targets<G>(	80✔
59	graph: G,	80✔
60	from: G::NodeId,	80✔
61	to: &HashSet<G::NodeId>,	80✔
62	min_intermediate_nodes: usize,	80✔
63	max_intermediate_nodes: Option<usize>,	80✔
64	) -> DictMap<G::NodeId, Vec<Vec<G::NodeId>>>	80✔
65	where	80✔
66	G: NodeCount,	80✔
67	G: IntoNeighborsDirected,	80✔
68	G::NodeId: Eq + Hash,	80✔
69	{
70	// how many nodes are allowed in simple path up to target node
71	// it is min/max allowed path length minus one, because it is more appropriate when implementing lookahead
72	// than constantly add 1 to length of current path
73	let max_length = if let Some(l) = max_intermediate_nodes {	80✔
74	l + 1	40✔
75	} else {
76	graph.node_count() - 1	40✔
77	};
78
79	let min_length = min_intermediate_nodes + 1;	80✔
80
81	// list of visited nodes
82	let mut visited: IndexSet<G::NodeId> = IndexSet::from_iter(Some(from));	80✔
83	// list of children of currently exploring path nodes,
84	// last elem is list of children of last visited node
85	let mut stack = vec![graph.neighbors_directed(from, Outgoing)];	80✔
86
87	let mut output: DictMap<G::NodeId, Vec<Vec<G::NodeId>>> = DictMap::with_capacity(to.len());	80✔
88
89	while let Some(children) = stack.last_mut() {	1,614✔
90	if let Some(child) = children.next() {	1,534✔
91	if visited.len() < max_length {	1,094✔
92	if !visited.contains(&child) {	888✔
93	if to.contains(&child) && visited.len() >= min_length {	566✔
94	let new_path: Vec<G::NodeId> =	276✔
95	visited.iter().chain(&[child]).copied().collect();	276✔
96	match output.entry(child) {	276✔
97	Entry::Vacant(e) => {	108✔
98	e.insert(vec![new_path]);	108✔
99	}	108✔
100	Entry::Occupied(mut e) => {	168✔
101	e.get_mut().push(new_path);	168✔
102	}	168✔
103	}
104	}	290✔
105	visited.insert(child);	566✔
106	if to.iter().any(\|n\| !visited.contains(n)) {	1,058✔
107	stack.push(graph.neighbors_directed(child, Outgoing));	566✔
108	} else {	566✔
UNCOV 109	visited.pop();	×
UNCOV 110	}	×
111	}	322✔
112	// visited.len() == max_length
113	} else {
114	for c in children.chain(iter::once(child)) {	412✔
115	if to.contains(&c) && !visited.contains(&c) && visited.len() >= min_length {	412✔
116	let new_path: Vec<G::NodeId> =	152✔
117	visited.iter().chain(&[c]).copied().collect();	152✔
118	match output.entry(c) {	152✔
119	Entry::Vacant(e) => {	76✔
120	e.insert(vec![new_path]);	76✔
121	}	76✔
122	Entry::Occupied(mut e) => {	76✔
123	e.get_mut().push(new_path);	76✔
124	}	76✔
125	}
126	}	260✔
127	}
128	stack.pop();	206✔
129	visited.pop();	206✔
130	}
131	} else {	440✔
132	stack.pop();	440✔
133	visited.pop();	440✔
134	}	440✔
135	}
136	output	80✔
137	}	80✔
138
139	/// Returns the longest of all the simple paths from `from` node to all nodes in `to`, which contains at least `min_intermediate_nodes` nodes
140	/// and at most `max_intermediate_nodes`, if given, or limited by the graph's order otherwise. The simple path is a path without repetitions.
141	///
142	/// # Example
143	/// ```
144	/// use petgraph::prelude::*;
145	/// use hashbrown::HashSet;
146	/// use rustworkx_core::connectivity::longest_simple_path_multiple_targets;
147	///
148	/// let mut graph = DiGraph::<&str, i32>::new();
149	///
150	/// let a = graph.add_node("a");
151	/// let b = graph.add_node("b");
152	/// let c = graph.add_node("c");
153	/// let d = graph.add_node("d");
154	///
155	/// graph.extend_with_edges(&[(a, b, 1), (b, c, 1), (c, d, 1), (a, b, 1), (b, d, 1)]);
156	///
157	/// let mut to_set = HashSet::new();
158	/// to_set.insert(d);
159	///
160	/// let path = longest_simple_path_multiple_targets(&graph, a, &to_set);
161	///
162	/// let expected = vec![a, b, c, d];
163	/// assert_eq!(path.unwrap(), expected);
164	/// ```
165	pub fn longest_simple_path_multiple_targets<G>(	20✔
166	graph: G,	20✔
167	from: G::NodeId,	20✔
168	to: &HashSet<G::NodeId>,	20✔
169	) -> Option<Vec<G::NodeId>>	20✔
170	where	20✔
171	G: NodeCount,	20✔
172	G: IntoNeighborsDirected,	20✔
173	G::NodeId: Eq + Hash,	20✔
174	{
175	// list of visited nodes
176	let mut visited: IndexSet<G::NodeId> = IndexSet::from_iter(Some(from));	20✔
177	// list of children of currently exploring path nodes,
178	// last elem is list of children of last visited node
179	let mut stack = vec![graph.neighbors_directed(from, Outgoing)];	20✔
180
181	let mut output_path: Option<Vec<G::NodeId>> = None;	20✔
182
183	let update_path = \|new_path: Vec<G::NodeId>,	20✔
184	output_path: &Option<Vec<G::NodeId>>\|
185	-> Option<Vec<G::NodeId>> {	198✔
186	match output_path.as_ref() {	198✔
187	None => Some(new_path),	20✔
188	Some(path) => {	178✔
189	if path.len() < new_path.len() {	178✔
190	Some(new_path)	46✔
191	} else {
192	None	132✔
193	}
194	}
195	}
196	};	198✔
197
198	while let Some(children) = stack.last_mut() {	604✔
199	if let Some(child) = children.next() {	584✔
200	if !visited.contains(&child) {	390✔
201	if to.contains(&child) {	198✔
202	let new_path: Vec<G::NodeId> =	198✔
203	visited.iter().chain(&[child]).copied().collect();	198✔
204	let temp = update_path(new_path, &output_path);	198✔
205	if temp.is_some() {	198✔
206	output_path = temp;	66✔
207	}	132✔
208	}	×
209	visited.insert(child);	198✔
210	if to.iter().any(\|n\| !visited.contains(n)) {	432✔
211	stack.push(graph.neighbors_directed(child, Outgoing));	174✔
212	} else {	174✔
213	visited.pop();	24✔
214	}	24✔
215	}	192✔
216	} else {	194✔
217	stack.pop();	194✔
218	visited.pop();	194✔
219	}	194✔
220	}
221	output_path	20✔
222	}	20✔
223
224	#[cfg(test)]
225	mod tests {
226	use crate::connectivity::{
227	all_simple_paths_multiple_targets, longest_simple_path_multiple_targets,
228	};
229	use hashbrown::HashSet;
230	use petgraph::prelude::*;
231
232	#[test]
233	fn test_all_simple_paths() {
234	// create a path graph
235	let mut graph = Graph::new_undirected();
236	let a = graph.add_node(0);
237	let b = graph.add_node(1);
238	let c = graph.add_node(2);
239	let d = graph.add_node(3);
240	let e = graph.add_node(4);
241
242	graph.extend_with_edges([(a, b, 1), (b, c, 1), (c, d, 1), (d, e, 1)]);
243
244	let mut to_set = HashSet::new();
245	to_set.insert(d);
246
247	let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, None);
248
249	assert_eq!(paths.get(&d).unwrap(), &vec![vec![a, b, c, d]]);
250	}
251
252	#[test]
253	fn test_all_simple_paths_with_two_targets_emits_two_paths() {
254	// create a path graph
255	let mut graph = Graph::new_undirected();
256	let a = graph.add_node(0);
257	let b = graph.add_node(1);
258	let c = graph.add_node(2);
259	let d = graph.add_node(3);
260	let e = graph.add_node(4);
261
262	graph.extend_with_edges([(a, b, 1), (b, c, 1), (c, d, 1), (d, e, 1), (c, e, 1)]);
263
264	let mut to_set = HashSet::new();
265	to_set.insert(d);
266	to_set.insert(e);
267
268	let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, None);
269
270	assert_eq!(
271	paths.get(&d).unwrap(),
272	&vec![vec![a, b, c, e, d], vec![a, b, c, d]]
273	);
274	assert_eq!(
275	paths.get(&e).unwrap(),
276	&vec![vec![a, b, c, e], vec![a, b, c, d, e]]
277	);
278	}
279
280	#[test]
281	fn test_digraph_all_simple_paths_with_two_targets_emits_two_paths() {
282	// create a path graph
283	let mut graph = Graph::new();
284	let a = graph.add_node(0);
285	let b = graph.add_node(1);
286	let c = graph.add_node(2);
287	let d = graph.add_node(3);
288	let e = graph.add_node(4);
289
290	graph.extend_with_edges([(a, b, 1), (b, c, 1), (c, d, 1), (d, e, 1), (c, e, 1)]);
291
292	let mut to_set = HashSet::new();
293	to_set.insert(d);
294	to_set.insert(e);
295
296	let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, None);
297
298	assert_eq!(paths.get(&d).unwrap(), &vec![vec![a, b, c, d]]);
299	assert_eq!(
300	paths.get(&e).unwrap(),
301	&vec![vec![a, b, c, e], vec![a, b, c, d, e]]
302	);
303	}
304
305	#[test]
306	fn test_all_simple_paths_max_nodes() {
307	// create a complete graph
308	let mut graph = Graph::new_undirected();
309	let a = graph.add_node(0);
310	let b = graph.add_node(1);
311	let c = graph.add_node(2);
312	let d = graph.add_node(3);
313	let e = graph.add_node(4);
314
315	graph.extend_with_edges([
316	(a, b, 1),
317	(a, c, 1),
318	(a, d, 1),
319	(a, e, 1),
320	(b, c, 1),
321	(b, d, 1),
322	(b, e, 1),
323	(c, d, 1),
324	(c, e, 1),
325	(d, e, 1),
326	]);
327
328	let mut to_set = HashSet::new();
329	to_set.insert(b);
330
331	let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, Some(0));
332
333	assert_eq!(paths.get(&b).unwrap(), &vec![vec![a, b]]);
334
335	let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, Some(1));
336
337	assert_eq!(
338	paths.get(&b).unwrap(),
339	&vec![vec![a, e, b], vec![a, d, b], vec![a, c, b], vec![a, b],]
340	);
341	}
342
343	#[test]
344	fn test_all_simple_paths_with_two_targets_max_nodes() {
345	// create a path graph
346	let mut graph = Graph::new_undirected();
347	let a = graph.add_node(0);
348	let b = graph.add_node(1);
349	let c = graph.add_node(2);
350	let d = graph.add_node(3);
351	let e = graph.add_node(4);
352
353	graph.extend_with_edges([(a, b, 1), (b, c, 1), (c, d, 1), (d, e, 1), (c, e, 1)]);
354
355	let mut to_set = HashSet::new();
356	to_set.insert(d);
357	to_set.insert(e);
358
359	let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, Some(2));
360
361	assert_eq!(paths.get(&d).unwrap(), &vec![vec![a, b, c, d]]);
362	assert_eq!(paths.get(&e).unwrap(), &vec![vec![a, b, c, e]]);
363	}
364
365	#[test]
366	fn test_digraph_all_simple_paths_with_two_targets_max_nodes() {
367	// create a path graph
368	let mut graph = Graph::new();
369	let a = graph.add_node(0);
370	let b = graph.add_node(1);
371	let c = graph.add_node(2);
372	let d = graph.add_node(3);
373	let e = graph.add_node(4);
374
375	graph.extend_with_edges([(a, b, 1), (b, c, 1), (c, d, 1), (d, e, 1), (c, e, 1)]);
376
377	let mut to_set = HashSet::new();
378	to_set.insert(d);
379	to_set.insert(e);
380
381	let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, Some(2));
382
383	assert_eq!(paths.get(&d).unwrap(), &vec![vec![a, b, c, d]]);
384	assert_eq!(paths.get(&e).unwrap(), &vec![vec![a, b, c, e]]);
385	}
386
387	#[test]
388	fn test_all_simple_paths_with_two_targets_in_line_emits_two_paths() {
389	// create a path graph
390	let mut graph = Graph::new_undirected();
391	let a = graph.add_node(0);
392	let b = graph.add_node(1);
393	let c = graph.add_node(2);
394	let d = graph.add_node(3);
395	let e = graph.add_node(4);
396
397	graph.extend_with_edges([(a, b, 1), (b, c, 1), (c, d, 1), (d, e, 1)]);
398
399	let mut to_set = HashSet::new();
400	to_set.insert(c);
401	to_set.insert(d);
402
403	let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, None);
404
405	assert_eq!(paths.get(&c).unwrap(), &vec![vec![a, b, c]]);
406	assert_eq!(paths.get(&d).unwrap(), &vec![vec![a, b, c, d]]);
407	}
408
409	#[test]
410	fn test_all_simple_paths_min_nodes() {
411	// create a cycle graph
412	let mut graph = Graph::new();
413	let a = graph.add_node(0);
414	let b = graph.add_node(1);
415	let c = graph.add_node(2);
416	let d = graph.add_node(3);
417
418	graph.extend_with_edges([(a, b, 1), (b, c, 1), (c, d, 1), (d, a, 1), (b, d, 1)]);
419
420	let mut to_set = HashSet::new();
421	to_set.insert(d);
422
423	let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 2, None);
424
425	assert_eq!(paths.get(&d).unwrap(), &vec![vec![a, b, c, d]]);
426	}
427
428	#[test]
429	fn test_all_simple_paths_with_two_targets_min_nodes() {
430	// create a cycle graph
431	let mut graph = Graph::new();
432	let a = graph.add_node(0);
433	let b = graph.add_node(1);
434	let c = graph.add_node(2);
435	let d = graph.add_node(3);
436
437	graph.extend_with_edges([(a, b, 1), (b, c, 1), (c, d, 1), (d, a, 1), (b, d, 1)]);
438
439	let mut to_set = HashSet::new();
440	to_set.insert(c);
441	to_set.insert(d);
442
443	let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 2, None);
444
445	assert_eq!(paths.get(&c), None);
446	assert_eq!(paths.get(&d).unwrap(), &vec![vec![a, b, c, d]]);
447	}
448
449	#[test]
450	fn test_all_simple_paths_source_target() {
451	// create a path graph
452	let mut graph = Graph::new_undirected();
453	let a = graph.add_node(0);
454	let b = graph.add_node(1);
455	let c = graph.add_node(2);
456	let d = graph.add_node(3);
457	let e = graph.add_node(4);
458
459	graph.extend_with_edges([(a, b, 1), (b, c, 1), (c, d, 1), (d, e, 1)]);
460
461	let mut to_set = HashSet::new();
462	to_set.insert(a);
463
464	let paths = all_simple_paths_multiple_targets(&graph, a, &to_set, 0, None);
465
466	assert_eq!(paths.get(&a), None);
467	}
468
469	#[test]
470	fn test_all_simple_paths_on_non_trivial_graph() {
471	// create a path graph
472	let mut graph = Graph::new();
473	let a = graph.add_node(0);
474	let b = graph.add_node(1);
475	let c = graph.add_node(2);
476	let d = graph.add_node(3);
477	let e = graph.add_node(4);
478	let f = graph.add_node(5);
479
480	graph.extend_with_edges([
481	(a, b, 1),
482	(b, c, 1),
483	(c, d, 1),
484	(d, e, 1),
485	(e, f, 1),
486	(a, f, 1),
487	(b, f, 1),
488	(b, d, 1),
489	(f, e, 1),
490	(e, c, 1),
491	(e, d, 1),
492	]);
493
494	let mut to_set = HashSet::new();
495	to_set.insert(c);
496	to_set.insert(d);
497
498	let paths = all_simple_paths_multiple_targets(&graph, b, &to_set, 0, None);
499
500	assert_eq!(
501	paths.get(&c).unwrap(),
502	&vec![vec![b, d, e, c], vec![b, f, e, c], vec![b, c]]
503	);
504	assert_eq!(
505	paths.get(&d).unwrap(),
506	&vec![
507	vec![b, d],
508	vec![b, f, e, d],
509	vec![b, f, e, c, d],
510	vec![b, c, d]
511	]
512	);
513
514	let paths = all_simple_paths_multiple_targets(&graph, b, &to_set, 1, None);
515
516	assert_eq!(
517	paths.get(&c).unwrap(),
518	&vec![vec![b, d, e, c], vec![b, f, e, c]]
519	);
520	assert_eq!(
521	paths.get(&d).unwrap(),
522	&vec![vec![b, f, e, d], vec![b, f, e, c, d], vec![b, c, d]]
523	);
524
525	let paths = all_simple_paths_multiple_targets(&graph, b, &to_set, 0, Some(2));
526
527	assert_eq!(
528	paths.get(&c).unwrap(),
529	&vec![vec![b, d, e, c], vec![b, f, e, c], vec![b, c]]
530	);
531	assert_eq!(
532	paths.get(&d).unwrap(),
533	&vec![vec![b, d], vec![b, f, e, d], vec![b, c, d]]
534	);
535	}
536
537	#[test]
538	fn test_longest_simple_path() {
539	// create a path graph
540	let mut graph = Graph::new_undirected();
541	let a = graph.add_node(0);
542	let b = graph.add_node(1);
543	let c = graph.add_node(2);
544	let d = graph.add_node(3);
545	let e = graph.add_node(4);
546
547	graph.extend_with_edges([(a, b, 1), (b, c, 1), (c, d, 1), (d, e, 1)]);
548
549	let mut to_set = HashSet::new();
550	to_set.insert(d);
551
552	let path = longest_simple_path_multiple_targets(&graph, a, &to_set);
553
554	assert_eq!(path.unwrap(), vec![a, b, c, d]);
555	}
556
557	#[test]
558	fn test_longest_simple_path_with_two_targets_emits_two_paths() {
559	// create a path graph
560	let mut graph = Graph::new_undirected();
561	let a = graph.add_node(0);
562	let b = graph.add_node(1);
563	let c = graph.add_node(2);
564	let d = graph.add_node(3);
565	let e = graph.add_node(4);
566
567	graph.extend_with_edges([(a, b, 1), (b, c, 1), (c, d, 1), (d, e, 1), (c, e, 1)]);
568
569	let mut to_set = HashSet::new();
570	to_set.insert(d);
571	to_set.insert(e);
572
573	let path = longest_simple_path_multiple_targets(&graph, a, &to_set);
574
575	assert_eq!(path.unwrap(), vec![a, b, c, e, d]);
576	}
577
578	#[test]
579	fn test_digraph_longest_simple_path_with_two_targets_emits_two_paths() {
580	// create a path graph
581	let mut graph = Graph::new();
582	let a = graph.add_node(0);
583	let b = graph.add_node(1);
584	let c = graph.add_node(2);
585	let d = graph.add_node(3);
586	let e = graph.add_node(4);
587
588	graph.extend_with_edges([(a, b, 1), (b, c, 1), (c, d, 1), (d, e, 1), (c, e, 1)]);
589
590	let mut to_set = HashSet::new();
591	to_set.insert(d);
592	to_set.insert(e);
593
594	let path = longest_simple_path_multiple_targets(&graph, a, &to_set);
595
596	assert_eq!(path.unwrap(), vec![a, b, c, d, e]);
597	}
598
599	#[test]
600	fn test_longest_simple_paths_with_two_targets_in_line_emits_two_paths() {
601	// create a path graph
602	let mut graph = Graph::new_undirected();
603	let a = graph.add_node(0);
604	let b = graph.add_node(1);
605	let c = graph.add_node(2);
606	let d = graph.add_node(3);
607	let e = graph.add_node(4);
608
609	graph.extend_with_edges([(a, b, 1), (b, c, 1), (c, d, 1), (d, e, 1)]);
610
611	let mut to_set = HashSet::new();
612	to_set.insert(c);
613	to_set.insert(d);
614
615	let path = longest_simple_path_multiple_targets(&graph, a, &to_set);
616
617	assert_eq!(path.unwrap(), vec![a, b, c, d]);
618	}
619
620	#[test]
621	fn test_longest_simple_paths_source_target() {
622	// create a path graph
623	let mut graph = Graph::new_undirected();
624	let a = graph.add_node(0);
625	let b = graph.add_node(1);
626	let c = graph.add_node(2);
627	let d = graph.add_node(3);
628	let e = graph.add_node(4);
629
630	graph.extend_with_edges([(a, b, 1), (b, c, 1), (c, d, 1), (d, e, 1)]);
631
632	let mut to_set = HashSet::new();
633	to_set.insert(a);
634
635	let path = longest_simple_path_multiple_targets(&graph, a, &to_set);
636
637	assert_eq!(path, None);
638	}
639
640	#[test]
641	fn test_longest_simple_paths_on_non_trivial_graph() {
642	// create a path graph
643	let mut graph = Graph::new();
644	let a = graph.add_node(0);
645	let b = graph.add_node(1);
646	let c = graph.add_node(2);
647	let d = graph.add_node(3);
648	let e = graph.add_node(4);
649	let f = graph.add_node(5);
650
651	graph.extend_with_edges([
652	(a, b, 1),
653	(b, c, 1),
654	(c, d, 1),
655	(d, e, 1),
656	(e, f, 1),
657	(a, f, 1),
658	(b, f, 1),
659	(b, d, 1),
660	(f, e, 1),
661	(e, c, 1),
662	(e, d, 1),
663	]);
664
665	let mut to_set = HashSet::new();
666	to_set.insert(c);
667	to_set.insert(d);
668
669	let path = longest_simple_path_multiple_targets(&graph, b, &to_set);
670
671	assert_eq!(path.unwrap(), vec![b, f, e, c, d],);
672	}
673	}

Qiskit / rustworkx / 19053565245

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous