Appropriate way to model mutable directed graph, for realtime dataflow computation

Hello everyone, as the title says, I'm trying to model a data flow like system. i.e. a system where data flows between nodes that do computation on the data. I want to be able to change the graph in place, hence why it needs to be mutable.

I have already tried a few methods, but my main sticking point is getting references from objects owned by a struct, to another object owned by the same struct. I can do this with Rc<RefCell<_>> types but an issue I have with that is firstly, I cannot seem to make an immutable reference to something with this type, that doesn't have the same properties as a normal reference. And secondly, there is only a single owner of the data (the top level structure), so this feels uneccesary, and there will be a slight performance overhead associated with this setup due to RefCell.

Any advice would be appreciated.

The standard suggestion for graph structures is to use indexes into a vector instead of references.

Thanks, that is what I've ended up doing. is there a blog post or something that explains the pros and cons of that approach? Like things to watch out for?

I don't know of any blog posts, but the main pitfall is that removing nodes from the graph becomes difficult. One option is to just give up on trying to reuse the memory. Another option is to use swap_remove to limit the number of indexes you need to update and go update that one index that got changed. Another one is to use a more sophisticated data structure such as slab.

Of course, this assumes you even know when to remove a node, so you also need to figure that out somehow.

removing nodes would be something that happens explicitly, and arbitrarily. The idea is that a user would be editing the graph. The nodes can exist independently of being connected to anything else, but edges might be removed if a node is removed. I am using generational_arena to control reallocating deleted nodes, slab seems to not take care of invalidating old references, unless I am mistaken.

what I'd really like to be honest, is something like Rc, but with only one owner (i.e. an Rc with only Weak references) so that the owner could still modify the value of the owned object. Not sure if this would actually work, but that's what I'd really like.

You need exclusive access to mutate something without using a cell, and what you're proposing would not allow for exclusive access (you could still access it through the weak pointers).

Ah yes, well maybe there's a way to convert a RefCell into something that only allows immutable access, but still participates in the runtime borrow checking done by the cell?

The type of a reference into a ref cell is Ref, which has a map method. If your type is copy, you can also use Cell which has a much simpler api than RefCell.

but Ref implies that the value has already been borrowed right? I tried using Ref, and I got exactly the same issues I had when using standard references. If I used RefCell, those problems went away, but I don't want to be able to call borrow_mut on the RefCell in the location where it was being used.

You can wrap it in an api that doesn't provide a borrow_mut function.

ah of course. Okay, I think I will still end up using indexes becuase it actually allows greater control over where things can be accessed from. Thanks for all your help :slight_smile:

1 Like

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