Recursive function review

code review
1

Hi all,

I am working on a project, and there is a pretty critical component of it which does some path finding through a graph. It's implemented recursively and works ok, but I want it to be better (and faster before I hit a limit). What I would really like to do is implement this recursive function as an iterator instead, but I am not feeling clever enough to do this...

I added a recursion counter recently, and this is pretty slow to go through before it hits the limit.

This might be really horrible code, but if anyone could give me any pointers to refactor this, that would be amazing. I realise that this is a brute force approach, which will only really work for small(ish) graphs (perhaps < ~50 nodes).

use anyhow::Result;
use petgraph::{
    graph::{Graph, IndexType, NodeIndex},
    visit::{EdgeRef, IntoNodeIdentifiers, IntoNodeReferences, NodeIndexable, NodeRef},
    Directed,
    Direction::Outgoing,
};
use std::collections::HashMap;

const MAX_RECURSION_DEPTH: usize = 1000;

fn recursive_path_finder_incl_coverage<T, U, Ix: IndexType>(
    graph: &Graph<T, U, Directed, Ix>, // my graph structure
    start_node: NodeIndex<Ix>, // node index of the starting node
    end_node: NodeIndex<Ix>, // node index of the end node
    visited: &mut HashMap<NodeIndex<Ix>, usize>, // keep track of nodes we have visited
    rel_coverage_map: &HashMap<NodeIndex<Ix>, usize>, // a hashmap of the nodes and their coverage, which determines how many times a node should be visited when computing a path.
    depth: usize,
) 
// sorry about the horrible return type.
-> Option<Result<Vec<Vec<NodeIndex<Ix>>>>> {

    // return None if we hit the max recursion depth
    if depth > MAX_RECURSION_DEPTH {
        return None;
    }

    // if the start node is the same as the end
    // the path is just to the end node
    if start_node == end_node {
        Some(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();

            let test = *rel_coverage_map.get(&next_node).unwrap();

            if !visited.contains_key(&next_node) || *visited.get(&next_node).unwrap() != test {
                *visited.entry(next_node).or_insert(0) += 1;
                let descendant_paths = match recursive_path_finder_incl_coverage(
                    graph,
                    next_node,
                    end_node,
                    visited,
                    rel_coverage_map,
                    depth + 1,
                ) {
                    // can I get rid of this unwrap? is it safe?
                    Some(p) => p.unwrap(),
                    None => return None,
                };
                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<_>>(),
                )
            }
        }
        Some(Ok(paths))
    }
}

Many thanks,
M

2

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.