Friday, April 03, 2015

Graphs in Rust

Graphs are a bit awkward to construct in Rust because of Rust's stringent lifetime and mutability requirements. Graphs of objects are very common in OO programming. In this tutorial I'm going to go over a few different approaches to implementation. My preferred approach uses arena allocation and makes slightly advanced use of explicit lifetimes. I'll finish up by discussing a few potential Rust features which would make using such an approach easier.

There are essentially two orthogonal problems: how to handle the lifetime of the graph and how to handle it's mutability.

The first problem essentially boils down to what kind of pointer to use to point to other nodes in the graph. Since graph-like data structures are recursive (the types are recursive, even if the data is not) we are forced to use pointers of some kind rather than have a totally value-based structure. Since graphs can be cyclic, and ownership in Rust cannot be cyclic, we cannot use Box<Node> as our pointer type (as we might do for tree-like data structures or linked lists).

No graph is truly immutable. Because there may be cycles, the graph cannot be created in a single statement. Thus, at the very least, the graph must be mutable during its initialisation phase. The usual invariant in Rust is that all pointers must either be unique or immutable. Graph edges must be mutable (at least during initialisation) and there can be more than one edge into any node, thus no edges are guaranteed to be unique. So we're going to have to do something a little bit advanced to handle mutability.

...

Read the full tutorial, with examples. There's also some discussion of potential language improvements in Rust to make dealing with graphs easier.

25 comments:

Robert said...

Seems to me it would be really nice to have the option of saying "I don't care about managing lifetimes myself here, just use a tracing GC for all this stuff".

I know that was once part of the Rust plan, and then the plan was to push it out to a library with language support for tracing hooks, and it seems now the option has disappeared entirely. Which makes me sad.

Unknown said...

I just wrote a quick post showing another way to model graphs:

http://smallcultfollowing.com/babysteps/blog/2015/04/06/modeling-graphs-in-rust-using-vector-indices/

I would offer a slight correction to the previous commenter, though: the option of tracing Gc is not currently available, but it is something I hope we will work on soon.

gasche said...

In Mezzo, they use a dynamic mechanism called "adoption and abandon" as a way to handle shared/cyclic nodes in a relatively ergonomic way (but paying the cost of a runtime check when taking ownership of a node during traversal).

See for example this code example for graphs. Adoption and Abandon has been described in various places, such as this blog post.

Anonymous said...

A graph is just a tuple G = (V, E) where V is some set of vertices, and E a set of edges, generally represented as tuples of vertices. In general, either your vertices or your edges are implicit to some degree. And lots of things in your program form graphs with or without your awareness or intention. Becoming aware of hidden graph structures in your code is often an "ah-hah" moment.

There are tons of ways to represent graphs. There is no precondition that they be either pointer-based or dynamic. You can form graphs from anything that allows any kind of associativity: arrays, genejric maps, function calls (as mentioned above), match statements, etc.

The point is you have a set of "things", and you have a set of "pairs of things", where each item in a given pair is a "thing". If you have a set of "things", and *any* other structure in your code which associates pairs of "things", that forms a graph -- whether or not that is what you indended!

It's very easy to form static graphs. For example, you can represent vertices as functions, edges as calls from one function to another. Yes: every program consists of a graph over functions! You could represent nodes as enum values, and edges as match clauses. Whether or not you intend, this forms a graph.

It's not that hard, guys.

Sudheer Patel said...

Thanks for sharing this post. you can learn Online Hyperion Training here.

Travel company in delhi said...

What a fantabulous post this has been. Never seen this kind of useful post. I am grateful to you and expect more number of posts like these. Thank you very much.

Jyotish said...

Hello,

Do you know? You are a very good and loyal friend, the information I was looking for on the Internet, I got it from your website and not only that, but I got much more information than I wanted. You have done your duty well as a blogger. I am proud of you, because you write articles for us, it helps us a lot and we get out of the place where we are stuck.

Really, whenever I read your articles, I like it so much that I cannot tell, because you have that talent which makes anyone crazy, I mean the words in your article are very true and are useful, that's why most people like to come to your website.

According to me, After reading the entire article, most people would have shared your article as well, because you give so much good knowledge to everyone that anyone would like to share your article.

Well, now let me go, I got pleasure by reading your article. Thanks a lot.

Ok Bye, Have a Wonderful Day. Findd Hindi

Jyotish Sahni said...

Hello,

"What a Fantastic Article is This"

Really, I found this article very helpful because there is a lot of beneficial and helpful information in this great article. I shared this article with my friends because it is very compulsory for reading as because of your truthful and honest content. Thank you for helping me find the information I needed.

Ok Bye, Have a Wonderful Day.

Regards,
Jyotish

How to Make a Better Comment on the Blog
What is the another name for Veda

Jyotish said...

Thanks for The Valuable & Fantastic Article 🙂.
FinddHindi is a great platform for learning knowledge about Internet and Technology.

learning.oilab said...

Thanks for sharing the article I always appreciate your topic. Python Training In Jodhpur

Finlock online said...

Such a very useful blog. Very Interesting to read this blog. Thanks for proving such a wonderful content. Cyber Insurance in india

AchieversIT said...

I really like you and This information is really very helpful. Thank you for sharing.
I will make sure to be reading your blog more. You made a good point Thanks!
if you want to learn UI Development Visit Our Website. https://www.achieversit.com/ui-development-training-course-institute-in-bangalore

periyannan said...

Thanks for sharing this unique information with us. Your post is really awesome. Your blog is really helpful for me..

artificial intelligence internship | best final year projects for cse | internship certificate online | internship for mba finance students | internship meaning in tamil

Alex Jarboe said...

Thanks for suggesting good list. I appreciate your work this is really helpful for everyone. Get more information at Splunk Training. Keep posting such useful information.

Anonymous said...


Interesting stuff to read. Keep it up.

SBI share price
Tata Steel Share Price
ITC Share Price
DLF share price
HDFC bank share price

Anonymous said...

One of the best article read so far! Well, if you are in need for Virtual assistant

emma jackson said...

This is a great post and have been looking for this since a long time. Well you can visit here if you are looking for software testing

4 said...

Loved it thanks for sharing
oracle scm online training

Ammy Anderson said...

We appreciate you sharing this special information with us. Your article is actually fantastic. I find your blog to be really beneficial. I would suggest Security Plus Training as a advanced skill.

bahu said...

One of the best article read so far!

bharath said...

This will be really helpful, thanks for sharing. will be waiting for more.

Anny Tech said...

Thank you for sharing the information.

Sameer said...

This will be really helpful, thanks for sharing.

Johan battler said...

Here is the detail of Watch Fox 505 Live Cricket World World Cup 2023 Streaming Free. Fox 505 Live is a very well-known channel for live broadcasting of sports, entertainment shows.

Cleaning Services Mooresville NC said...

Mooresville NC Cleaning Services offers professional cleaning solutions in the Mooresville area. Our team of experienced cleaners is dedicated to providing top-notch cleaning services for both residential and commercial properties. With our attention to detail and commitment to customer satisfaction, you can trust us to leave your space spotless and refreshed.

Whether you need regular cleaning services or a one-time deep clean, we have the expertise and resources to meet your needs. Contact Cleaning Services Mooresville NC today for a clean and healthy environment.