Efficient way to store undirected graph?

Hello,
I’m trying to store an undirected graph of nodes, something like this:
image
But without edge weights or anything like that (basically a “this connects to this” type of thing, but undirected). I’m thinking of using a linked list type structure, because being able to rearrange items very quickly is essential (the graph is dynamic) and the connections are sparse (there are about 200 elements, but each element has about 4-6 connections on average). Right now, implementing something like this is awkward (it’s like a doubly linked list, but harder). Any ideas on how to implement this in safe rust (still starting rust, wanna stick to “safe” rust first)? Would a different data structure be better suited, or is the linked list structure fine?

For graphs you can always use the fantastic petgraph crate

If you want something more custom you could do something like this

use std::hash::{Hash, Hasher};

use std::collections::HashSet;

struct Connection(usize, usize);

impl Eq for Connection {}
impl PartialEq for Connection {
    fn eq(&self, other: &Self) -> bool {
        self.0 == other.0 && self.1 == other.1 ||
        self.0 == other.1 && self.1 == other.0
    }
}

// This will make it easier to find the right connections
impl PartialEq<usize> for Connection {
    fn eq(&self, &other: &usize) -> bool {
        self.0 == other || self.1 == other
    }
}

impl Hash for Connection {
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        hasher.write_usize(self.0 + self.1)
    }
}

pub struct Graph(HashSet<Connection>);

With the appropriate functions to insert and remove items. This is fast and you can link this up to a Vec<Element> that holds all of your elements. This way changing the structure of your graph doesn’t need to touch your elements. Of course you will have to iterate through all of the connections to find all of the connections to a node, if that speed is important to you then you can use

pub struct Graph(Vec<HashSet<usize>>);

This is much simpler and will allow you to iterate through all of the connections to a node very quickly.
To use this you can make a graph like so Graph(vec![Vec::new(), N]) where N is the maximum number of nodes that you will have. (You can grow this number if you need to) and then when you add connections, be sure to insert the connection on both sides of the graph to made sure it is undirected.

1 Like

How about representing your graph as a sparse (upper triangular, symmetric) matrix, for example using sprs crate? and if you can translate your ops to linalg ops you could potentially gain a lot!

For 4-6 edges per node a Vec would most likely be a lot faster than a linked list, and definitely simpler. Did you already try that?

2 Likes

A vec? So a multidimensional (or “flattened”) vector? The problem is that I have to be able to rearrange cells at will… wait nvm yeah a vec would work, I could swap cells.

I would recommend one vector holding all nodes, and using indexes instead of pointers. I also echo the recommendation to use a HashMap, though I think it can be simple:

transitions: HashMap<(NodeIndex, NodeIndex), ()>

If you have a node and want to know every node it points to, or every node pointing to it, I’d recommend ancillary data structures. If that’s a use case you have, please be specific.

1 Like

Aright, thank you!

This is the same as HashSet<(NodeIndex, NodeIndex)> and HashSet provides a more ergonomic api for working with sets.

4 Likes

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.