Merge pull request #277 from fan-tom/simple_paths
Add all_simple_paths algorithm
diff --git a/Cargo.toml b/Cargo.toml
index df77606..c5f91a6 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -30,7 +30,7 @@
[dependencies]
fixedbitset = { version = "0.2.0", default-features = false }
quickcheck = { optional = true, version = "0.8", default-features = false }
-indexmap = { version = "1.0.2", optional = true }
+indexmap = { version = "1.0.2" }
serde = { version = "1.0", optional = true }
serde_derive = { version = "1.0", optional = true }
@@ -42,7 +42,7 @@
[features]
default = ["graphmap", "stable_graph", "matrix_graph"]
-graphmap = ["indexmap"]
+graphmap = []
serde-1 = ["serde", "serde_derive"]
stable_graph = []
matrix_graph = []
diff --git a/src/algo/mod.rs b/src/algo/mod.rs
index 2d3087f..d1771f9 100644
--- a/src/algo/mod.rs
+++ b/src/algo/mod.rs
@@ -46,6 +46,7 @@
};
pub use super::dijkstra::dijkstra;
pub use super::astar::astar;
+pub use super::simple_paths::all_simple_paths;
/// \[Generic\] Return the number of connected components of the graph.
///
diff --git a/src/lib.rs b/src/lib.rs
index 4a76111..b8251a9 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -60,6 +60,7 @@
pub mod unionfind;
mod dijkstra;
mod astar;
+mod simple_paths;
pub mod csr;
mod iter_format;
mod iter_utils;
diff --git a/src/simple_paths.rs b/src/simple_paths.rs
new file mode 100644
index 0000000..7d698df
--- /dev/null
+++ b/src/simple_paths.rs
@@ -0,0 +1,163 @@
+use std::{
+ hash::Hash,
+ iter::{from_fn, FromIterator},
+};
+
+use indexmap::IndexSet;
+
+use crate::{
+ Direction::Outgoing,
+ visit::{
+ IntoNeighborsDirected,
+ NodeCount,
+ },
+};
+
+/// Returns iterator that produces all simple paths from `from` node to `to`, which contains at least `min_intermidiate_nodes` nodes
+/// and at most `max_intermidiate_nodes`, if given, limited by graph's order otherwise
+/// Simple path is path without repetitions
+/// Algorithm is adopted from https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.all_simple_paths.html
+pub fn all_simple_paths<TargetColl, G>(graph: G,
+ from: G::NodeId,
+ to: G::NodeId,
+ min_intermidiate_nodes: usize,
+ max_intermidiate_nodes: Option<usize>) -> impl Iterator<Item=TargetColl>
+ where G: NodeCount,
+ G: IntoNeighborsDirected,
+ G::NodeId: Eq + Hash,
+ TargetColl: FromIterator<G::NodeId>
+{
+ // 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_intermidiate_nodes {
+ l + 1
+ } else {
+ graph.node_count() - 1
+ };
+
+ let min_length = min_intermidiate_nodes + 1;
+
+ // list of visited nodes
+ let mut visited: IndexSet<G::NodeId> = IndexSet::from_iter(Some(from));
+ // list of childs of currently exploring path nodes,
+ // last elem is list of childs of last visited node
+ let mut stack = vec![graph.neighbors_directed(from, Outgoing)];
+
+ from_fn(move || {
+ while let Some(children) = stack.last_mut() {
+ if let Some(child) = children.next() {
+ if visited.len() < max_length {
+ if child == to {
+ if visited.len() >= min_length {
+ let path = visited.iter().cloned().chain(Some(to)).collect::<TargetColl>();
+ return Some(path);
+ }
+ } else if !visited.contains(&child) {
+ visited.insert(child);
+ stack.push(graph.neighbors_directed(child, Outgoing));
+ }
+ } else {
+ if (child == to || children.any(|v| v == to)) && visited.len() >= min_length {
+ let path = visited.iter().cloned().chain(Some(to)).collect::<TargetColl>();
+ return Some(path);
+ }
+ stack.pop();
+ visited.pop();
+ }
+ } else {
+ stack.pop();
+ visited.pop();
+ }
+ }
+ None
+ })
+}
+
+#[cfg(test)]
+mod test {
+ use std::{
+ collections::HashSet,
+ iter::FromIterator,
+ };
+
+ use itertools::assert_equal;
+
+ use crate::{
+ dot::Dot,
+ prelude::DiGraph,
+ };
+
+ use super::all_simple_paths;
+
+ #[test]
+ fn test_all_simple_paths() {
+ let graph = DiGraph::<i32, i32, _>::from_edges(&[
+ (0, 1),
+ (0, 2),
+ (0, 3),
+ (1, 2),
+ (1, 3),
+ (2, 3),
+ (2, 4),
+ (3, 2),
+ (3, 4),
+ (4, 2),
+ (4, 5),
+ (5, 2),
+ (5, 3)
+ ]);
+
+ let expexted_simple_paths_0_to_5 = vec![
+ vec![0usize, 1, 2, 3, 4, 5],
+ vec![0, 1, 2, 4, 5],
+ vec![0, 1, 3, 2, 4, 5],
+ vec![0, 1, 3, 4, 5],
+ vec![0, 2, 3, 4, 5],
+ vec![0, 2, 4, 5],
+ vec![0, 3, 2, 4, 5],
+ vec![0, 3, 4, 5],
+ ];
+
+ println!("{}", Dot::new(&graph));
+ let actual_simple_paths_0_to_5: HashSet<Vec<_>> = all_simple_paths(&graph, 0u32.into(), 5u32.into(), 0, None)
+ .map(|v: Vec<_>| v.into_iter().map(|i| i.index()).collect())
+ .collect();
+ assert_eq!(actual_simple_paths_0_to_5.len(), 8);
+ assert_eq!(HashSet::from_iter(expexted_simple_paths_0_to_5), actual_simple_paths_0_to_5);
+ }
+
+ #[test]
+ fn test_one_simple_path() {
+ let graph = DiGraph::<i32, i32, _>::from_edges(&[
+ (0, 1),
+ (2, 1)
+ ]);
+
+ let expexted_simple_paths_0_to_1 = &[
+ vec![0usize, 1],
+ ];
+ println!("{}", Dot::new(&graph));
+ let actual_simple_paths_0_to_1: Vec<Vec<_>> = all_simple_paths(&graph, 0u32.into(), 1u32.into(), 0, None)
+ .map(|v: Vec<_>| v.into_iter().map(|i| i.index()).collect())
+ .collect();
+
+ assert_eq!(actual_simple_paths_0_to_1.len(), 1);
+ assert_equal(expexted_simple_paths_0_to_1, &actual_simple_paths_0_to_1);
+ }
+
+ #[test]
+ fn test_no_simple_paths() {
+ let graph = DiGraph::<i32, i32, _>::from_edges(&[
+ (0, 1),
+ (2, 1)
+ ]);
+
+ println!("{}", Dot::new(&graph));
+ let actual_simple_paths_0_to_2: Vec<Vec<_>> = all_simple_paths(&graph, 0u32.into(), 2u32.into(), 0, None)
+ .map(|v: Vec<_>| v.into_iter().map(|i| i.index()).collect())
+ .collect();
+
+ assert_eq!(actual_simple_paths_0_to_2.len(), 0);
+ }
+}
