Graph Format Design

by Andrew on Jul.13, 2009, under Uncategorized

Today I spent a while outlining the format of my graph storage files. There were a couple concerns I wanted to tackle in terms of both functionality and data types. The first one I solved was the storage medium which I decided to just go with XML. I suppose that decision meant the rest just became an XML schema definition but I know very little about the high level concepts so just refer to it as “making a file to hold my graph data.”

The XML formatting gave me an idea that had been working it’s way through my head for a while. Originally I was building graphs with the concept of 3 node types, generators, operators and exporters. The important note for these is that the applications would have had to retrieve the specific nodes from my library and manually set and get data values from the nodes. What I have come up with for the redesign is input and output elements that are fixed tables with named parameters. This means the application only ever deals with the input and output tables and nodes internal to graphs can retrieve values or set values in those tables. This I believe makes the procedures that the graphs represent much more application friendly.

On top of the new IO tables I’ve designed in a simple name space system. This is done in an attempt to allow extension modules a fair bit of freedom with their data types and functions without clashing too badly with other modules. When registering a module to the system it is given a name or a title which becomes it’s root level namespace. This name will be guaranteed by the system to be unique, I intend to ensure that the system has a way of avoiding loading the same module under a different name as well. Once the module is loaded with it’s title, the node and data types it contains are referenced using the title followed by a ‘::’ symbol. So a module named ‘Maths’ with a node called ‘Add’ would reference that node as ‘Maths::Add.’

So with the conceptual components mostly done I tackled the actual design of the XML itself. I tried to keep it fairly simple, clean, understandable and ideally flexible. For the purposes, I am quite happy with the results.

The first part is the “graph” element that wraps the entire definition. It contains a “name” attribute which will be used to reference the graph within the engine.

The first sub section is the “modules” section. This is where the graph identifies to the system what modules it references or needs loaded. There are sub elements within this tagged as “module” each of which contain the attributes “name” and “file.” The “module” elements are loaded based on their file attribute and use the name attribute as that modules namespace.

Following this are the “input” and “output” elements. These represent the named input and output tables associated with the graph. The sub elements in these sections are tagged “parameters” which contain a “name”, “type” and “default” attribute. The name attribute identifies the parameter for referencing by both the system and the nodes withing the graph. The type attribute identifies what kind of data the parameter holds and the default attribute is able to pass an initial value to the parameter.

The next section of the file is the “nodes” element. It is what identifies all the nodes that will exist in the graph. Individual nodes are handled by the “node” element handle, which contains “name” and “type” attributes. Nodes can also contain “parameter” elements to initialize internal data. Declaring parameters in this section means that are most likely not going to change for the life span of the graph.

The final element in the file is the “connections” element. This is where the links between nodes are made to define data flow when a graph is operating. The sub element that defines a single connection is tagged “connection.” The connection element contains sub elements tagged “to” and “from.” These sub elements contain the attributes “node” and “socket.” Essentially they define which output parameter on a node gets connected to which input parameter on another node.

At the end of the post is a simple example of a stored graph, however first I want to have a brief conclusion. I believe this format is fairly portable and quite simple to manage. The user interface for creating them isn’t as big a priority as I had originally thought so I believe any developer application would be able to create an exporter to this format. I also believe the new system design will benefit any user applications and games since it gives them a cleaner interface with the graphs and also hopefully allows for more straight forward management of various types.

My next step will hopefully to be recode bits of the engine that need to be changed to match this new design, possibly a little redesign of the engine as well, and to get a parser written for this file format. The parser will need to generate the run time graphs with loaded modules, connected inputs and outputs and all that good stuff.

This final section will probably be quite long due to the formatting but here it is. This is an example graph saved out to my format. It is a simple graph that has 2 named inputs of type “Float” which the graph uses with 2 other constant float values to create 2 addition functions and the results of those get multiplied and output to a named output parameter.