Mutable vectors in struct

Question

I'm trying to get a graph clustering algorithm to work in Rust. Part of the code is a WeightedGraph data structure with an adjacency list representation. The core would be represented like this (shown in Python to make it clear what I'm trying to do):

class Edge(object):
    def __init__(self, target, weight):
        self.target = target
        self.weight = weight

class WeightedGraph(object):
    def __init__(self, initial_size):
        self.adjacency_list = [[] for i in range(initial_size)]
        self.size = initial_size
        self.edge_count = 0

    def add_edge(self, source, target, weight):
        self.adjacency_list[source].append(Edge(target, weight))
        self.edge_count += 1

So, the adjacency list holds an array of n arrays: one array for each node in the graph. The inner array holds the neighbors of that node, represented as Edge (the target node number and the double weight).

My attempt to translate the whole thing to Rust looks like this:

struct Edge {
    target: uint,
    weight: f64
}

struct WeightedGraph {
    adjacency_list: ~Vec<~Vec<Edge>>,
    size: uint,
    edge_count: int
}

impl WeightedGraph {
    fn new(num_nodes: uint) -> WeightedGraph {
        let mut adjacency_list: ~Vec<~Vec<Edge>> = box Vec::from_fn(num_nodes, |idx| box Vec::new());

        WeightedGraph {
            adjacency_list: adjacency_list,
            size: num_nodes,
            edge_count: 0
        }
    }

    fn add_edge(mut self, source: uint, target: uint, weight: f64) {
        self.adjacency_list.get(source).push(Edge { target: target, weight: weight });
        self.edge_count += 1;
    }
}

But rustc gives me this error:

weightedgraph.rs:24:9: 24:40 error: cannot borrow immutable dereference of `~`-pointer as mutable
weightedgraph.rs:24         self.adjacency_list.get(source).push(Edge { target: target, weight: weight });
                            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

So, 2 main questions:

1. How can I get the add_edge method to work?

I'm thinking that WeightedGraph is supposed to own all its inner data (please correct me if I'm wrong). But why can add_edge not modify the graph's own data?

2. Is ~Vec<~Vec<Edge>> the correct way to represent a variable-sized array/list that holds a dynamic list in each element?

The tutorial also mentions ~[int] as vector syntax, so should it be: ~[~[Edge]] instead? Or what is the difference between Vec<Edge> and ~[Edge]? And if I'm supposed to use ~[~[Edge]], how would I construct/initialize the inner lists then? (currently, I tried to use Vec::from_fn)

score 7 · Accepted Answer · 2014-05-03 22:04:51Z

7

The WeightedGraph does own all its inner data, but even if you own something you have to opt into mutating it. get gives you a & pointer, to mutate you need a &mut pointer. Vec::get_mut will give you that: self.adjacency_list.get_mut(source).push(...).

Regarding ~Vec<Edge> and ~[Edge]: It used to be (until very recently) that ~[T] denoted a growable vector of T, unlike every other type that's written ~... This special case was removed and ~[T] is now just a unique pointer to a T-slice, i.e. an owning pointer to a bunch of Ts in memory without any growth capability. Vec<T> is now the growable vector type.

Note that it's Vec<T>, not ~Vec<T>; the ~ used to be part of the vector syntax but here it's just an ordinary unique pointer and represents completely unnecessary indirection and allocation. You want adjacency_list: Vec<Vec<Edge>>. A Vec<T> is a fully fledged concrete type (a triple data, length, capacity if that means anything to you), it encapsulates the memory allocation and indirection and you can use it as a value. You gain nothing by boxing it, and lose clarity as well as performance.

You have another (minor) issue: fn add_edge(mut self, ...), like fn add_edge(self, ...), means "take self by value". Since the adjacency_list member is a linear type (it can be dropped, it is moved instead of copied implicitly), your WeightedGraph is also a linear type. The following code will fail because the first add_edge call consumed the graph.

let g = WeightedGraph::new(2);
g.add_edge(1, 0, 2); // moving out of g
g.add_edge(0, 1, 3); // error: use of g after move

You want &mut self: Allow mutation of self but don't take ownership of it/don't move it.

edited May 3, 2014 at 22:04

answered May 3, 2014 at 21:59

user395760

Sign up to request clarification or add additional context in comments.

4 Comments

Martin S. Over a year ago

Thank you very much for your detailed answer! About the ~Vec<T> part: I am still a little bit confused because the tutorial contains linked list code (in section 9.1 Boxes) that uses Cons(u32, ~List). That made me think that references to structs/enums/types within another struct need a ~. So, is the ~ for the linked list only because of the recursive aspect? And what would be 'non-concrete' type which cannot be used directly as a value?

huon Over a year ago

"This special case was removed and ~[T] is now just a unique pointer to a T-slice" just a point of pedantry: the change in representation hasn't happened yet, so it's still represented as a growable vector, but all the growing methods (.push etc.) have been removed. Hopefully the representation will be changed soon.

Vladimir Matveev Over a year ago

@MartinS., yes, ~ is present there only to allow recursion. This tutorial explains pointers in detail. "Non-concrete" types which cannot be used directly as a value currently are [T] and T where T is a trait. That is, you cannot use [T] and trait objects without pointers, because their size is unknown. This is also explained in tutorials.

user395760 Over a year ago

@dbaupp I am aware that the DST transition is not complete yet. But IMHO it's so far along and agreed-upon that (1) the new mental model matches at least the API and (2) describing the post-DST status as status quo is only a small temporary lie that aids understanding.

Arjan · Accepted Answer · 2014-05-03 21:58:10Z

2

get only returns immutable references, you have to use get_mut if you want to modify the data
You only need Vec<Vec<Edge>>, Vec is the right thing to use, ~[] was for that purpose in the past but now means something else (or will, not sure if that is changed already)

You also have to change the signature of add_edge to take &mut self because now you are moving the ownership of self to add_edge and that is not what you want

answered May 3, 2014 at 21:58

Arjan

21.8k2 gold badges57 silver badges49 bronze badges

Collectives™ on Stack Overflow

Mutable vectors in struct

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related