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.

38 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.

Christina Alpanda said...

Thanks for sharing the best information and suggestions, I love your content, and they are very nice and very useful to us. If you are looking for the best applied data science with python, then visit igmguru.com. I appreciate the work you have put into this.

Sudheer Patel said...

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

AchieversIT said...


Really nice and informative blog, keep it up. Thanks for sharing and I have some suggestions.
if you want to learn pyhton Programming, Join Now Python Training in Bangalore.
Here is a Website- Software Training in Bangalore | AchieversIT
This may help you to find something useful

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

kriti said...

Thank you for sharing the information.
Power BI Training

Jyotish said...

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

kriti said...

Thank you for sharing the information.
DevOps Online Training

learning.oilab said...

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

Rajeshshrimali said...

Such a very useful blog. Very Interesting to read this blog. Thanks for proving such a wonderful content. best astrologer 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

Rajeshshrimali said...

Excellent information providing by your post, thank you for taking the time to share with us such nice.
best astrologer in jaipur

David Smith said...

Get Expert share market tips only With Sharetipsinfo guide you best and provide you with great stock tips, commodity tips, share market tips and much more. Visit us now!

Rajeshshrimali said...

Great Article. Keep Up The Good Work. Love to read such Great Content which provides quality Knowledge as well as interesting facts. Best Astrologer In Jodhpur

Unknown said...

Good Article, keep writing more,

Digital Marketing, Digital Marketing Online Training, Digital Marketing Training Programs, Women Entrepreneurship, Women Entrepreneurship Training Programs, Digital marketing online video course, Women Entrepreneurship Online Certification Course, Business coaching, Training for Business owners, Business coaching for women, young entrepreneurs training

https://www.eminentdigitalacademy.com

Digital Marketing Online Training

바카라사이트 said...

First of all, thank you for letting me see this information. I think this article can give me a lot of inspiration. I would appreciate 바카라사이트 if you could post more good contents in the future.

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

bes unn said...

Hey friend, it is very well written article, thank you for the valuable and useful information you provide in this post. Keep up the good work! FYI, Pet Care adda
Credit card processing, wimpy kid books free
,science a blessing or curse essay

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.

AchieversIT said...

read this post your post so nice and very informative post thanks for sharing this post
Thanks for sharing information. COntinue doing this
form for imformation visit our website: https://www.achieversit.com/

Unknown 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

top computer coaching said...

BIIT(Brahmanand Institute Of Information & Technology) is one of the very well known Best digital marketing institute in east delhi. BIIT New Delhi computer coaching contains the highly professional trainees. You can call us on 9311441524 or can visit to our address A-115 , First Floor , Near Panna Sweet, Shakarpur, Vikas Marg, Laxmi Nagar, Computer Institute, Opposite Metro Piller No. 33, Delhi, 110092 or can directly visit to our official site http://www.biitnewdelhi.com/.

Vikas Bisht said...

Thank you for this wonderful post, great article, keep up the excellent work. Check out our blog Best DU LLB Coaching in Delhi

Unogeeks said...

Are you interested in becoming an Oracle Fusion HCM Certified Consultant?
Unogeeks is offering the Best Oracle Best Oracle Fusion HCM Online Training

Sam Curran 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

Unknown 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.

Unogeeks said...

Want to become Oracle Recruiting Cloud Certified Specialist or Consultant? Attend this Best Oracle Recruiting Cloud Training course offered by the Unogeeks (Rated as Top Oracle Recruiting Cloud Training Institute in the market)

bahu said...

One of the best article read so far!

Alteryx Training in Chennai said...

python course in chennai|
rprogramming training in chennai
clinical sas course in chennai

T20 world cup said...


watch-new-zealand-vs-pakistan-2nd-test-match