Are Graphs Hard in Rust? - Payas Rajan

"Graphs are hard in Rust due to the strict borrow checking rules." In this talk, I argue otherwise. I use examples from popular libraries including Boost Graph, OSRM and petgraph to show that implementing graphs and graph libraries in C++ and Rust, in fact, have very similar levels of difficulty. Moreover, the Rust's traits-based type system makes certain operations simpler and can save programmers a lot of time and cryptic error messages.
github.com/PayasR
Payas is a PhD Candidate at the University of California - Riverside where he studies route planning algorithms in transportation networks and other geospatial problems.

[@heater5979]

Nobody told me graphs were hard in Rust. Over a recent rainy weekend afternoon I just implemented one. It generates graphs of 20 vertices of valance 3 and 30 edges, randomly connected. And then does some traversal around the graph. It could easily be much bigger. These graphs are as per the famous old "Hunt the Wumpus" game from the early days of Unix.
Being an old school C programmer who avoids malloc as much as possible my Rust graph was created as elements of Vectors. The links simply being indices to other elements.
No worries with the borrow checker there :)
Great talk by the way. Thanks.

[@pragmacpp5518]

Can you share your code via gist?

[@RD-fb6ei]

Ok. Now try a doubly linked list, using your same vector backed method. You see the issue? You fuck up the time complexity. Like everything in rust, it’s not actually zero overhead, the compiler just forces YOU to add the overhead by disallowing everything under the sun.

[@heater5979]

@@RD-fb6ei I don't think so. If you really want to write a doubly linked list using good old fashioned raw pointers you can do it. Did you hear of the "unsafe" keyword?
Personally I have never used the "unsafe" keyword, and yet on my road to learning Rust I found myself recreating little programs in Rust that I had in C already. In all cases performance matched or surpassed that of C. If it had not I would not have continue pushing Rust.

[@joe_hoeller_chicago]

Graphs are driven by graph theory in mathematics. These math formulas that are specific to graph types (Bipartate graph, DAGs, etc) can be recreated in any programming language.