Functional Graphs

Question

I've been trying to make a functional graph. The graph I'm making doesn't have loops, so it's a bit like a tree where some nodes can have more than one parent.

The problem is when updating. The usual way with a tree is to traverse down to the node to be updated, each step of the way creating a new node which is changed to point to a new child node, until the actual node to modify is reached who's data is then actually changed.

Taking this approach when some nodes have more than one parent breaks because you end up basically "splitting" the node. The node shared between two parents becomes two nodes with a parent each, one (the path you traversed to get to the node) having the new value and the other parent keeping a child with the old value.

So I instead tried storing the parent nodes inside each node, i.e. nodes know who their parents are.

This works, but there's a problem. If I update a node, I have to update its parents. But then for each of its parents, I don't only have to update their parents, but also their children, because their children store their parent node(s), and that parent node has now changed.

So to update one node value, I have to update every node in the graph.

The other idea I had was instead of storing the parent nodes in each node, just storing the "paths" to the parent nodes in each node. That way I shouldn't have to update the parent's children, as the "path" to the parent hasn't changed (even though the node itself has).

But perhaps there's a much better way of building a functional graph? Any ideas? I don't mind if it doesn't handle graphs with loops. I'm coding in Haskell, but a non programming language description would be fine also.

Answer 1

So to update on node value I have to update each node in the entire graph.

Sadly, you have to accept this as a fact. That's basically the reason why you can't implement an efficient functional graph. All the solutions which allow updating without traversal of the whole graph are based on model of tables and indexes as references. The idea is the following: you store all nodes in an indexed table and in edges instead of direct references to nodes you store their indexes. There are some variations, which have different benefits, but basically that's the whole idea.

But thinking deeper about the above, it is nothing more than an emulation of what memory pointers actually do. So basically you end up reimplementing a low-level stuff while greatly losing in performance. So honestly speaking I recommend considering itegrating a mutable graph, which won't share any of those problems.

I've been working on a graph-db project for some time, which is yet to be released. I however have some code published. I think this mutable graph implementation might be of use to you as a source of ideas.