# Removing recursion

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.

Many thanks,
Max

Specifically how? Graph traversals are most naturally expressed using recursion; anything that artifically tries to remove it will likely be more complicated.

I'm not sure how to incorporate the information for how many times a node can be used in a path, really.

An additional parameter of type `HashMap<NodeIndex, usize>` should do the job.

1 Like

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)
}
}
``````

Can you share a minimal graph for which it causes a stack overflow?

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.

1 Like

Gosh, I can do a bit of investigation. Might not be able to find a minimal one quickly!

Thanks for this, could you sketch this out for me if possible? I tried re-writing as a loop, but couldn't actually think how to do it - doh.

Have you tried using Stacker? It can extend your stack.

If stacker doesn't support your platform and you're feeling extra adventurous you can also try my crate decurse.

1 Like

Thanks for this, I have not checked this out, but I will!

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.