Home > Programming > Graph Design Blues

Graph Design Blues

August 10th, 2011

I’m having second-thoughts on how to manage the dependency graph(s). I’ve been experimenting with a “directed multigraph”, but I worry that it adds too much complexity when it comes to determining what portions of it are connected when only a certain type of edge is considered, and whether I’m over-complicating things. Actually, I’m pretty sure I am over-complicating things, but freedom to experiment is part of what makes an independent project fun.

The real problem is this: What kind of information might be needed to analyze a node and add its children, and in what order do you do that? Every node needs to be visited, but what about every incoming edge, or every path? Using a multi-graph is making it difficult to reason out a correct and deterministic traversal order, particularly when it comes to preventing cycles. In particular,  cycles which may be valid in the graph as long as they require two-or-more edge types to exist!

I’m wondering now if–despite being an interesting experiment–I ought to restructure things as a collection of graphs bound together in a “Graph Project”. The unifying project would serve to de-duplicate nodes, provided nodes are all immutable data-holders.

You may be wondering why de-duplication is important, if nodes are immutable and have a good equals() implementation. The answer is Weak References. I want to allow NodeHandler implementations to store arbitrary information about what nodes they’ve already seen, so that they can avoid duplication of effort when necessary. For example, the same material file may have the same texture dependencies, whether it occurs in the graph for Map A or the one for Map B. If there are two separate Node instances which are equal() to one another,  WeakHashMap can only reliably store one of them.

To solve this problem, I’m considering setting up a system where NodeHandler instances register themselves as listeners to a Graph Project, so that they can store a hard reference instead, and are informed when they can safely forget it due to the Node being removed.

Tags:
Comments are closed.