blob: 7d698df31e674b1cad221970f385029abcb847a8 [file] [log] [blame]
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);
}
}