I'd be so grateful for any insight. I've been building some functionality on top of petgraph. I want to find all the simple paths in a graph between two nodes. This is with the caveat that I'd like to pass some kind of data structure to the path calculation where I can specify the maximum number of times a node can be visited, given the path is still legal (this means that some output paths will not be simple anymore).
Currently I'm using this algorithm from here:
// https://github.com/Ninjani/rosalind/blob/e22ecf2c9f0935d970b137684029957c0850d63f/t_ba11b/src/lib.rs
use petgraph::Directed;
use petgraph::Direction::Outgoing;
use petgraph::graph::{IndexType, NodeIndex};
use petgraph::Graph;
use petgraph::visit::EdgeRef;
pub fn all_paths<T, U, Ix: IndexType>(
graph: &Graph<T, U, Directed, Ix>,
start_node: NodeIndex<Ix>,
end_node: NodeIndex<Ix>,
) -> Vec<Vec<NodeIndex<Ix>>> {
let mut visited = HashSet::new();
visited.insert(start_node);
all_paths_helper(graph, start_node, end_node, &mut visited)
}
fn all_paths_helper<T, U, Ix: IndexType>(
graph: &Graph<T, U, Directed, Ix>,
start_node: NodeIndex<Ix>,
end_node: NodeIndex<Ix>,
visited: &mut HashSet<NodeIndex<Ix>>,
) -> Vec<Vec<NodeIndex<Ix>>> {
if start_node == end_node {
vec![vec![end_node]]
} else {
let mut paths = Vec::new();
for edge in graph.edges_directed(start_node, Outgoing) {
let next_node = edge.target();
if !visited.contains(&next_node) {
visited.insert(next_node);
let descendant_paths = all_paths_helper(graph, next_node, end_node, visited);
visited.remove(&next_node);
paths.extend(
descendant_paths
.into_iter()
.map(|path| {
let mut new_path = vec![start_node];
new_path.extend(path);
new_path
})
.collect::<Vec<_>>(),
)
}
}
paths
}
}
I'm getting stuck hacking this because of the recursion in this function. Can anybody help me remove this recursion? Or if there's a way of passing a HashMap<NodeIndex<Ix>, u32> (or any other data structure) specifying how many times a node can be included in a path, I'm all ears.
Specifically how? Graph traversals are most naturally expressed using recursion; anything that artifically tries to remove it will likely be more complicated.
Cool! Thanks. This code below actually works for very small graphs. Otherwise we get a stack overflow... any advice?
pub fn all_paths<T, U, Ix: IndexType>(
graph: &Graph<T, U, Directed, Ix>,
start_node: NodeIndex<Ix>,
end_node: NodeIndex<Ix>,
rel_coverage_map: &HashMap<NodeIndex<Ix>, u32>,
) -> Result<Vec<Vec<NodeIndex<Ix>>>> {
// change HashSet -> HashMap
// let mut visited = HashSet::new();
// visited.insert(start_node);
let mut visited = HashMap::new();
visited.insert(start_node, 1usize);
all_paths_helper(graph, start_node, end_node, &mut visited, rel_coverage_map)
}
fn all_paths_helper<T, U, Ix: IndexType>(
graph: &Graph<T, U, Directed, Ix>,
start_node: NodeIndex<Ix>,
end_node: NodeIndex<Ix>,
// visited: &mut HashSet<NodeIndex<Ix>>,
visited: &mut HashMap<NodeIndex<Ix>, usize>,
rel_coverage_map: &HashMap<NodeIndex<Ix>, u32>,
) -> Result<Vec<Vec<NodeIndex<Ix>>>> {
if start_node == end_node {
Ok(vec![vec![end_node]])
} else {
let mut paths = Vec::new();
for edge in graph.edges_directed(start_node, Outgoing) {
let next_node = edge.target();
// get the value for the current node
// and test if we hit this in the next bit of logic
let test = *rel_coverage_map.get(&next_node).unwrap();
if !visited.contains_key(&next_node)
|| !(*visited.get(&next_node).unwrap() == test as usize)
{
*visited.entry(next_node).or_insert(0) += 1;
let descendant_paths =
all_paths_helper(graph, next_node, end_node, visited, rel_coverage_map)
.unwrap();
visited.remove(&next_node);
paths.extend(
descendant_paths
.into_iter()
.map(|path| {
let mut new_path = vec![start_node];
new_path.extend(path);
new_path
})
.collect::<Vec<_>>(),
)
}
}
Ok(paths)
}
}
You'll have to implement all_paths_helper with a loop rather than using recursion if you want to avoid a stack overflow. Generally, any recursive function which is just calling itself can converted to a loop by using a Vec to hold the stack data.