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.