Tips for implementing a recursive algorithm on graph

Hello,

I want to implement an adjancency search in a graph. That is, I want for a node all the nodes that can be reached using at most depth edges.

I have this implementation so far, but I'm not sure if it is optimal. I'm not even sure if some tail recursive optimizations will be done.

struct Graph {
    adjacencies: Vec<Vec<usize>>,
}

impl Graph {
    fn new(adjacencies: Vec<Vec<usize>>) -> Graph {
        Graph { adjacencies }
    }

    // Returns all the nodes adjacent that are reachable using at most `depth`
    // edges starting from `node`.
    fn adjacent_to(&self, node: usize, depth: u32) -> Vec<usize> {
        if node >= self.adjacencies.len() {
            panic!("invalid node");
        }
        if depth == 0 {
            vec![node]
        } else {
            let mut adjacents = Vec::new();
            self.adjacent_to_recursion(node, depth, &mut adjacents);
            adjacents.sort();
            adjacents.dedup();
            adjacents
        }
    }

    // Helper function. Is it tail recursive?
    fn adjacent_to_recursion(&self, node: usize, depth: u32, adjacents: &mut Vec<usize>) {
        adjacents.extend(self.adjacencies[node].iter());
        adjacents.push(node);
        if depth > 1 {
            self.adjacencies[node]
                .iter()
                .for_each(|n| self.adjacent_to_recursion(*n, depth - 1, adjacents))
        }
    }
}

fn main() {
    let graph = Graph::new(vec![
        vec![1, 2],
        vec![2, 3],
        vec![4],
        vec![0, 1, 2],
        vec![0, 3],
    ]);

    assert_eq!(graph.adjacent_to(2, 0), &[2]);
    assert_eq!(graph.adjacent_to(2, 1), &[2, 4]);
    assert_eq!(graph.adjacent_to(2, 2), &[0, 2, 3, 4]);
    assert_eq!(graph.adjacent_to(2, 3), &[0, 1, 2, 3, 4]);
}

Any comments or reccomendations regarding the implementation are welcome.

Thanks!

I think it would be quite a lot more scalable if you collect the adjacents in a BTreeSet (or another set implementation, like FnvHashSet) instead of in a vector. Otherwise, it seems pretty good to me.

1 Like

I will look at that!

Actually, another recommendation would be to debug_assert the contents of adjacencies, like my are_valid_adjacencies function does (for an undirected graph though). Better than needlessly debugging botched input.

The recursive algorithm here has a very very bad algorithmic complexity. For example if you have this graph with seven nodes:

If you want all nodes reachable within a depth of 10, then the first level will make six calls, then each call makes six calls, then each of those makes six calls and so on. In total that's already sixty million calls. That's slow enough to timeout on the playground: link.

Also, you asked if it's tail recursive, but it's not, because it makes more than one call.

One approach to this is to skip nodes already in the list. Note that I changed it to a set so you can easily check if it's already there.

fn adjacent_to_recursion(&self, node: usize, depth: u32, adjacents: &mut BTreeSet<usize>) {
    if adjacents.contains(&node) { return; }
    adjacents.insert(node);
    if depth > 0 {
        self.adjacencies[node]
            .iter()
            .for_each(|n| self.adjacent_to_recursion(*n, depth - 1, adjacents))
    }
}

playground

2 Likes

Good point for the complexity. Didn't think about that at first.