Hey there, I wrote a small blog post about "Idiomatic tree and graph like structures in Rust". Credits also go to Simon Sapins experiments with "Rust Forest"
What do you think?
6 Likes
Thanks for posting!
Interestingly, just yesterday I realized (after hours of lifetime-induced headache, and finally deciding to use Rc<RefCell>) that I could simplify some code drastically by using indices into a Vec instead of references. So it was funny to see your post just now. It certainly is a very helpful concept, which would have saved me a lot of headache two days ago 
. (I also thought about whether the increased flexibility of indices over references meant that they provided less guarantees, but the only thing I came up with was that you should be safe if you don't delete elements from the vector.)
1 Like
Thank you for your reply! 
Yeah but some index reuse should also be possible somehow.
Replacing pointers by indirect references is a common trick in functional languages (this is the way, for example, we know that any mutable algorithm can be emulated in only logarithm slowdown by representing homogeneous mutable memory as a map (balanced search tree) from integers to values). It has some other advantages than simplifying ownership: for example, it is easier to detect if a directed graph represented this way contain cycles than with a direct graph-of-pointers representation -- unless you know how to efficiently store sets of adresses, which assumes that they are stable (no compaction), or you explicitly bake some extra "node identifier" in and maintain invariants over it.
However, there are also costs associated with it. In particular, the fact that there is no memory management means that you have to implement your own. This is just fine if the objects really have the lifetime that you approximated (they are all released at the same time), but there are various situations of usage of graphs where you may want to delete parts of the graph as they get disconnected / become unreachable by mutation, or compact the space storage of the graph (imagine that you keep adding and removing vertices randomly). In this case you have to implement your own reference-counting or otherwise GC-ing scheme, possibly with compaction, and his adds a lot of complexity.
2 Likes
Do you see any drawback in using Rust for your last mentioned approach?
No, the inconvenience of having to (sometimes) reimplement liveness and compaction by hand would apply in any language. What is Rust-specific in your story is your motivation: you are using the indirect representation as a way to avoid ownership patterns that the language does not let you express statically.
Independently: If you have a tree structure, have you tried using rc::Weak for the backreferences? You could have strong references to the first child and next sibling, and weak references to the parent, last child and previous sibling.