Graph and .g-files

The Graph data structure started out rather normal, as a typical graph data structure where nodes are any-type (their value can be of any C++ type). As nodes also have a key, the data structure was also an any-type dictionary (as in Python). This turned out so useful that it is now used equally as dictionary, as graph, or a mix of both. Further, a node can have a sub-graph (or sub-dictionary) as value, making the data structure hierarchical and ideal to represent XML or YAML kind of data. I use this data structure to read XML, YAML, JSON. The .g file format is one-to-one with the Graph data structure and is the only structured file format used in rai (for configuration files, kinematic model descriptions, logic, factor graphs, optimization problems, etc).

The best way to understand the Graph class is to first understand the file format, which clarifies what is actually represented. Here is the example.g from test/Core/graph, hopefully the comments are self-explanatory:

## a trivial graph (all boolean-valued nodes)
x            # a vertex: key=x, value=true, parents=none
y            # another vertex: key=y, value=true, parents=none
(x y)        # an edge: key=none, value=true, parents=x y
(-1 -2)      # a hyperedge: key=none, value=true, parents=the previous edge and the y-node

## nodes with subgraphs as value
A { color:blue }         # key=A, value=<Graph>, parents=none
B { color:red, value:5 } # key=B, value=<Graph>, parents=none
C(A,B) { width:2 }       # key=C, value=<Graph>, parents=A B
hyperedge(A B C) : 5     # key=hyperedge, value=5, parents=A B C

## standard value types
a:string      # MT::String (except for keywords 'true' and 'false' and 'Mod' and 'Include')
b:"STRING"    # MT::String (does not require a ':')
c:'file.txt'  # MT::FileToken (does not require a ':')
d:-0.1234     # double
e:[1 2 3 0.5] # MT::arr (does not require a ':')
#f:(c d e)    # DEPRECATED!! MT::Array<*Node> (list of other nodes in the Graph)
g!            # bool (default: true, !means false)
h:true        # bool
i:false       # bool
j:{ a:0 }     # sub-Graph (special: does not require a ':')

## parsing: : {..} (..) , and \n are separators for parsing key-value-pairs
b0:false b1, b2() b3    # 4 boolean nodes with keys 'b0', 'b1', 'b2', 'b3'
k:{ a, b:0.2 x:"hallo"     # sub-Graph with 6 nodes
  y
  z():filename.org x }

## special Node Keys

# editing: after reading all nodes, the Graph takes all Edit nodes, deletes the Edit tag, and calls a edit()
# this example will modify/append the respective attributes of k
Edit k { y:false, z:otherString, b:7, c:newAttribute }

# including
Include: 'example_include.g'   # first creates a normal FileToken node then opens and includes the file directly

## strange notations
a()       # key=a, value=true, parents=none
()        # key=none, value=true, parents=none
[1 2 3 4] # key=none, value=MT::arr, parents=none

Subgraphs may contain nodes that have parents from the containing graph, or from other subgraphs of the containing graph. Some methods of the Graph class (to find nodes by key or type) allow to specify whether also nodes in subgraphs or parentgraphs are to be searched. This connectivity across (sub)-graphs e.g. allows to represent logic knowledge bases.