On passing a mutable array of structs down a recursive function call stack?

1

Edit: When I first posted this I forgot to mention the mutable aspect of the question.

TL;DR Let's say we have an array of structures. The this array of structures represents a graph. Each node of the graph is one of those structures. Each of those nodes/structures contains a Vector of indices to other nodes, thus forming a graph structure. Now, the question is: How to pass that array to a recursive function that will walk around the graph, passing the array to itself as it recursively calls itself to move through the graph?

After trying to do this with regular references/borrows for a while I concluded it was not going to be possible. I ended up doing it by wrapping the nodes array in an Rc<RefCell. With suitable '.borrow()'s and .clones() I managed to get something that works:

#[derive(Eq, PartialEq, Clone, Debug, Serialize, Deserialize)]
struct Node {
    id: usize,
    exits: Vec<usize>,
}
...
fn search (nodes: Rc<RefCell<Nodes>>, start_node: usize, current_node: usize, path: Vec<usize>, depth: usize) -> usize {
    // Bail out if recursion depth is crazy
    if (depth == 30usize) {
        panic!();
    }

    // Get the current node.
    let mut node = nodes.borrow()[current_node].clone();

    // Have we returned to the node we started from having made a loop?
    if (node.id == start_node) && (path.len() > 2) {
        println!("Path: {:?}", path);
        return depth;
    }

    // Have we already been here?
    if path.contains(&node.id) {
        return depth;
    }

    // Add the current node to the path.
    let mut path = path.clone();
    path.push(node.id);

    let mut path_length = 0usize;
    for (i, connection) in node.exits.iter().enumerate() {
        let l = search(nodes.clone(), start_node, *connection, path.clone(), depth + 1);
        path_length = std::cmp::max(path_length, l);
    }
    // Return the longest path found.
    path_length
}
...
    let mut nodes = Rc::new(RefCell::new(nodes));
    let path: Vec<usize> = vec![];
    let path_length = search(nodes, 0, 0, path, 0);
    println!("Longest path = {}", path_length);

What does anyone think? Any better ways to do this? Other comments?

The longer story is that on another forum some folks were discussing getting some original sources of the famous "Hunt The Wumpus" game to compile. Pre ANSI C and all that. There was also the issue of fixing a bug in one of them that hung up as it tried to generate random mazes of 20 nodes and three exits each.

Which got me curious as to how I would do it in Rust. The code to my Wumpus maze generator, including this recursive walk function is here for the curious: Rust Playground

It generates graphs that look like this:

graph

2

You don't have to clone all the time if your recursive function undoes its changes to the shared data structure after each recursive call. Additionally, you can compute the final length as you return up the recursive function stack, instead of returning the final length from the end of the recursion.

I sketched these ideas out in the playground, if you want to explore them. It compiles but I didn't due any actual testing; in particular I didn't make an effort to exactly match the values returned from your example and my sketch, so do take care with the details.

There is undoubtedly a better approach to the longest path problem in general, but hopefully this sketch addresses your actual question.

1 Like
3

Oh boy. After my taking most of the day to get that working in any shape or form you have totally rewritten it in no time!

There are too many changes there for me to get into tonight. I'll have a proper look tomorrow.

Is it so that you no longer need the Rc<RefCell<Nodes> because you have implemented the recursive search as a method on Graph and can therefor just rely on &self? I had no such luck just trying to pass &nodes to my standalone function.

Actually the task here is not finding the longest path. I already know that because the way I generate the graph is to link all the nodes in a simple loop, bidirectionally, and then randomly add connections bidirectional connections between randomly selected nodes until they are each connected to three others. Which seems to be the standard for the wumpus game.

Rather the problem was: If we had less nodes, say 6 and 12 edges, how would one test any given random net to see if it was a Platonic solid? A cube in this example.

Or given a Wumpus maze net that is said to be a dodecahedron, as per the original game, how would one check that it really is?

The approach I was heading toward was to find all the length 5 loops in the net. If there are twelve of them I think that proves it. (maybe)

Oh, that "path length check > 2" is in there because all the nodes are connected bidirectionally. I found myself taking one step forward and one backward, so back home it recorded a loop. But that is just a link between two nodes, cannot be a 2D face.

Thanks.

4

Is it so that you no longer need the Rc<RefCell<Nodes> because you have implemented the recursive search as a method on Graph and can therefor just rely on &self? I had no such luck just trying to pass &nodes to my standalone function.

No, you just don't need them. I'm not sure what led you to them. Here's your original playground code, minimally modified to compile on playground and remove the Rc<RefCell<Nodes>> in favor of &Nodes.

You could keep iterating on this to get rid of more clones and to pass path as a &mut Vec, for example.

1 Like
5

could you pass the path (as per @quinedot)

  ... current_node: usize, mut path: &mut Vec<usize>, depth: ...

and pop the pushed value before returning?

1 Like
6
  1. Can nodes be deleted individually from the graph?
  2. Is there a reasonable max. number of exits a node can have?
7

Sorry, I think I made a mistake of omission in my opening post. I forgot to say that I would like to have the array passed down as mutable. Likely I will want to mutate nodes in the future. As far as I know this cannot be done with :

fn search (nodes: &mut Nodes, start_node: usize, current_node: usize, path: Vec<usize>, depth: usize) -> usize {

Or at least I have not managed it. Hence the introduction of Rc<RefCell>. Am I right?

8

I was not anticipating the need to add or delete nodes once the graph is built.

All of the is inspired by the "Hunt The Wumpus" game: Hunt the Wumpus - Wikipedia.

In the original Wumpus the maze was in the form of a dodecahedron. 20 nodes, 30 edges, 12 faces. So only three connections in and out of each node.

Slightly later versions included the ability to create random mazes. But still with 10 nodes, 20 edges and 3 connections per node.

I was not anticipating expanding on this. It was only intended as a little weekend challenge to generate the maze. Which grew into the idea of traversing it to check various properties. Which grew... A Rust learning exercise for me.

I seems odd that I can't get the borrow checker to allow the Nodes array to be borrowed mutably by future incarnations of the same function recursively. After all, only one of the recursions is active at a time and it's all in the same function. But there we go.

9

It should be possible if search doesn’t hold any reference into nodes when it makes the recursive call. This may require dropping node before and getting it back out of the array after your recursive call returns.

10 
#[derive(Clone)]
struct Node {
    id: u8,
    exits: ::arrayvec::ArrayVec<[u8; 3]>,
}

No allocation means, you're encouraged to just clone the nodes within your function. Say good bye to RefCell and borrowing, except for the immediate call to clone. Instead of calling the function recursively, you may wanna use std::collections::VecDeque, instead, with a loop like

let visited = ::rustc_hash::FxHashSet::<<element type>>::default();

while let Some((<element id>, <element data>)) = queue.pop_front() {
    if visited.insert(<element id>) {
        // queue.extend(<iterator>)
        // queue.push_back(<element>)
    }
}
1 Like
11

Ooo, I do like ArrayVec.

So I made my nodes like so:

use arrayvec::ArrayVec;

type Exits = arrayvec::ArrayVec<[usize; 3]>; 
#[derive(Eq, PartialEq, Clone, Debug, Serialize, Deserialize)]
struct Node {
    id: usize,
    exits: Exits,
}

impl Node {
    fn new (id: usize) -> Node {
        Node {
            id
            exits: Exits::new(),
        } 
    }
}

And now my recursive search function signature is just:

fn search(nodes: &mut Nodes, ....) -> usize {

So more refcells and only one clone.

I thought about an iterative solution. That rather changes the whole nature of the problem as a question for this thread. I'm sticking with recursion.

Thanks.

12

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.