I just have to share this little insight: finally, a concise definition. A metagraph is a system of objects where the types of the objects (classes) and the relations between them (e.g. pointers, mappings, containers) can be described in a graph called a pattern. In the C++ implementation, the patterns are metadata, which allows static typing and static polymorphism and moves the abstraction penalty to compile time (when the pattern is known at coding time). Patterns and their implementation code are combined into larger patterns; the "total pattern" is what actually gets instantiated. The library allows implementation of hypergraphs, subgraphs, various nested/mixed/ clustered layout schemes, constraints on graphs, and generally graphs- of-graphs, hence the name metagraph. Can any static analysis fans out there tell me if there's already a name for this? Note that in this definition, metagraph is something which already exists in lots of forms. This library proposes (for now) to implement the data structures in a nicer way and (in the future) to describe and access existing structures in a consistent way. My profuse apologies for continuing to talk about code that doesn't yet exist. Soon, soon. Cheers, Gordon
Gordon Woodhull wrote:
I just have to share this little insight: finally, a concise definition.
A metagraph is a system of objects where the types of the objects (classes) and the relations between them (e.g. pointers, mappings, containers) can be described in a graph called a pattern. In the C++ implementation, the patterns are metadata, which allows static typing and static polymorphism and moves the abstraction penalty to compile time (when the pattern is known at coding time).
I don't know if this is related to what you have in mind, but the Scrap your Boilerplate approach [1] allows to traverse any recursive data structure, given each type is a valid Fusion sequence (i.e. anything tuple-like). It assumes a tree, but the structure could actually perfectly be a graph. [1] http://spirit.sourceforge.net/dl_docs/traversal/html/index.html
On Jul 6, 2008, at 11:28 AM, Mathias Gaunard wrote:
Gordon Woodhull wrote:
I just have to share this little insight: finally, a concise definition.
A metagraph is a system of objects where the types of the objects (classes) and the relations between them (e.g. pointers, mappings, containers) can be described in a graph called a pattern. In the C++ implementation, the patterns are metadata, which allows static typing and static polymorphism and moves the abstraction penalty to compile time (when the pattern is known at coding time).
I don't know if this is related to what you have in mind, but the Scrap your Boilerplate approach [1] allows to traverse any recursive data structure, given each type is a valid Fusion sequence (i.e. anything tuple-like). It assumes a tree, but the structure could actually perfectly be a graph.
Thanks - yeah, I think Dan's and my libraries are on a similar level of abstraction - for one thing, they're both made possible by Fusion's abstraction of heterogeneous containers. My library is mainly concerned with generating heterogeneous graph data structures (more types of nodes or edges, multiple levels of graph, etc.). I expect that Traversal will be helpful for implementing heterogeneous graph algorithms, i.e. when you want to write an algorithm that operates on any metagraph pattern. Graph traversal is a little bit more tricky than hierarchical data traversal, because you have to keep track of where you've been, but otherwise the horizontal and vertical traversals are breadth-first and depth-first search.
participants (2)
-
Gordon Woodhull -
Mathias Gaunard