Creating a static "map" (graph)
I'm writing a toy pathfinder in Rust, using the Eve Online static data export as a "map".
It's been interesting downloading the export, streaming the zip files to memory, extracting the data needed and constructing enough to eventually do some pathfinding on (still todo).
My main current data-structure looks like this:
#[derive(Debug)]
pub struct SolarSystem {
pub name: String,
pub solar_system_id: SolarSystemId,
pub constellation_id: u64,
pub region_id: u64,
neighbours: once_cell::unsync::OnceCell<Vec<Weak<SolarSystem>>>,
}
contained in a Vec.
I needed a once-cell/RefCell etc to do the linking of the solarsystems (trying to avoid just faking things with storing offset IDs). You can't link with references to other solarsystems that you might not have created yet, and you run into issues with mutating elements of the vec with a mutable borrow and immutable at the same time (advice here appreciated too).
At the moment, I have no particular need to make things parallel, but in principle, once it's created and done, this structure won't change and the systems in it won't go away unless the whole map does and should be able to be used simultaneously with the only requirement being that the whole map does not drop before you finish (ref-counting systems shouldn't really be needed).
It leaves me a little unsatisfied that if I try to solve this, I probably need to move over to Arc and a sync once-cell and pay some costs that don't feel strictly necessary, but I don't feel confident about other patterns for this.
There's a slight temptation to use something like bumpalo, and allocate an arena for the map to almost codify that this whole data-structure has a single lifetime.
Anyway, looking for suggestions / techniques / patterns that might work here, because I feel like those sorts of things are the tools that you put in your belt for solving other issues later.
Thanks in advance.
Posted Nov 13, 2022, 2:53 PM UTC
General graphs like this are fairly difficult to construct in Rust. They are (in essence) complex linked lists. However, I would recommend using Rc instead of the once cells here. Assuming you are constructing the graph in a single thread (which you should be doing), you can probably get away with the
unsafemethod on Rcget_mut_uncheckedwhen adding on neighbors.From there, the ergonomics of traversing the graph should be far better.
This uses Rc, with a strong reference from the vec, and a weak reference between the neighbours to avoid cycle issues keeping them alive.
get_mut_unchecked sounds like it might be helpful, thanks!
Ya, weak references might be good. However, I imagine you want to keep the whole graph around for the life of the program, so leaks are really a concern.
At any rate, the once cell is not needed because you can construct an empty Vec and populate it later.
So like: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=a0383aee1aab69739b479420ca209738
Downside, this requires nightly at the moment, and
get_mut_uncheckeddoesn't at a glance look like it's getting stabilized any time soon due to challenges with it.Interior mutability seems like a better way to avoid needing nightly and unsafe?
Ah, I didn't realize that was a nightly feature. What you have would work. To avoid using unsafe and nightly, you could use a
RefCell. This would come at a (probably minor) performance hit, but would work well for what you're doing.You will want to wrap the cells in an RC, still though.