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 T
s 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 box
ing 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 drop
ped, 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.