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)

Answer 1

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.

Answer 2

1. get only returns immutable references, you have to use get_mut if you want to modify the data
2. 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