Implement a graph structure in Rust

Question

I'm trying to represent a graph in Rust using the type:

struct Node<'a> {
    edges: Vec<&'a Node<'a>>,
}
type Graph<'a> = Vec<Node<'a>>;

A Graph has the constraint that all the nodes point at other nodes in the same vector. I can create a singleton graph:

fn createSingleton<'a>() -> Graph<'a> {
    let mut items: Graph<'a> = Vec::new();
    items.push(Node { edges: Vec::new() });
    return items;
}

But when I try and create a graph with two nodes, where one points at the other:

fn createLink<'a>() -> Graph<'a> {
    let mut items: Graph<'a> = Vec::new();
    items.push(Node { edges: Vec::new() });
    items.push(Node { edges: vec![&items[0]] });
    return items;
}

I get an error:

cannot borrow `items` as mutable because it is also borrowed as immutable

In particular the &items[0] is an immutable borrow, and the second items.push seems to be a mutable borrow. Is it possible to construct the memory layout I desire? If so, how?

@FrenchBoiethios - thanks - as the `Graph` type or the `edges` type? Or should they both have that type? — Neil Mitchell, Sep 09 '19 at 16:28
And any way without going to `RefCell`, which I believe loses the safety guarantees I'd like from Rust? — Neil Mitchell, Sep 09 '19 at 16:34
See also [Why can't I store a value and a reference to that value in the same struct?](https://stackoverflow.com/q/32300132/155423) — Shepmaster, Sep 09 '19 at 17:53
@NeilMitchell `RefCell` does not lose the safety guarantees, but it does move them from compile time to run time. — Shepmaster, Sep 09 '19 at 17:53

score 1 · Answer 1 · answered Sep 09 '19 at 16:39

1

As soon as more than one structure can point to one of your Nodes, you'll lose the "one owner" world of Rust's memory guarantees, and you'll either need something like an Rc, or more esoterically, a weakref. I totally suggest reading https://rust-unofficial.github.io/too-many-lists/ to learn the many ins and outs of this territory.

answered Sep 09 '19 at 16:39

Dylan McNamee

1,696
14
16

That's a great link! – Neil Mitchell Sep 09 '19 at 18:38

Implement a graph structure in Rust

1 Answers1