I am currently working on kind of multi-graph structure. The thing is that two graphs are needed for my application which span the same vertices but with two distinct set of edges (i.e., a multi-graph). The first graph is a binary search tree, while the second graph must be general (directed / undirected, or bidirectional, possibly with cycles, etc.). The B-tree is used for fast queries of nearest nodes, while the second graph is needed for path-planning (e.g., in the style of shortest-path algorithms). Both graphs have to be completely mutable (reconnections, moving nodes around, adding/removing nodes and edges to either graphs). So far it's simple enough, just a multi-graph. A typical implementation of such a multi-graph (and similarly, a multi-index) would have all the nodes in one array (or list) and the two edge-sets as adjacency lists within the nodes, or, it would have two graphs that indirectly point to nodes in an array. This is simple to deal with because the nodes remain in fixed locations (or indices) in the array or list, and edges are easy to rewire and keep consistent with the node list.

However, for efficiency reasons (i.e., to solve locality of reference issues), I want to use specific memory layouts that are suitable for the binary search tree. In particular, I have an implementation of a breadth-first layout for the tree (i.e., BF-tree), as well as a cache-oblivious B-tree (or COB-tree) which have both proved to be orders of magnitude more efficient than a general adjacency list implementation (or linked-list style implementations). Also, the work to be done on the overlaid graph (the general adjacency-list graph) is expected to be local with respect to the partition of B-tree nodes, giving me even more locality of reference performance benefits. So, it is natural to use the B-tree as primary storage with adjacency-lists at the nodes to represent the overlaid graph. Now, of course, this becomes complicated when you allow both graphs to be mutable because nodes have to physically move around when restructuring (or rewiring) the B-tree (by self-balancing algorithms), and then the overlaid adjacency-list graph has to be kept consistent with the movements of the nodes. I anticipate quite a bit of trouble getting this to work correctly (let alone provably so by formal methods).

So, here's the question: I'm sure I'm not the first guy to get this idea and that it has been done before, but I have no idea what this is called in CS literature, does anyone know? Has anyone seen algorithms (or libraries) that implement this kind of pattern?

Thanks in advance.

BTW, I use C++ and I use the Boost.Graph Library as the basis for my additional graph algorithms and data structures.