c++ write data with cyclic dependencies in binary file using flatbuffers

Question

I'm trying to write a Graph into a binary file by using flatbuffers. A graph consists of nodes and edges. Every node has at least one edge and every edge consists of two nodes.

Excerpt from MyGraph.fbs:

namespace MyGraph;

table Node {
  edges:[Edge];
}

table Edge {
  startNode:Node;
  endNode:Node;
}

table Graph {
  allNodes:[Node];
}

root_type Graph;

Now I want to create a simple graph and write it into a bytefile:

FlatBufferBuilder fbb;
// create first node
auto node1mloc = DG::CreateNode(fbb, 0, 0);

// create second node
auto node2mloc = DG::CreateNode(fbb, 0, 0);

// create edge between first and second node
auto edgeloc = DG::CreateEdge(fbb, node1mloc, node2mloc);


// ???
// store the edge in the edges-vector of node1 and node2
// ???

// store nodes in graph
flatbuffers::Offset<Node> nodes[] = {node1mloc, node2mloc};

auto allNodes = fbb.CreateVector(nodes, 2);

auto graphloc = DG::CreateGraph(fbb, allNodes);

DG::FinishGraphBuffer(fbb, graphloc);


// write graph into file
auto buffer_pointer = fbb.GetBufferPointer();
SaveFile("myfile2.bin", reinterpret_cast<const char *>(buffer_pointer), fbb.GetSize(), true);



// load graph from file
string binData;
LoadFile("myfile2.bin", true, &binData);

auto graph = DG::GetGraph(binData.data());
cout << graph->allNodes()->size() << endl;
assert(graph->allNodes()->size() == 2);

The Problem is, that after creating the nodes, I can't add the edge to the edges-vector of node1 and node2. Is there a solution for that kind of cyclic dependencies between two types.

Aardappel Aardappel · Accepted Answer · 2015-12-03T17:35:57

You cannot store cyclic structures in a FlatBuffer (it enforces that children always come before parents, using unsigned offsets).

You can store DAGs, however.

To encode a cyclic structure, you'll have to use indices for either Nodes or Edge references, e.g.

table Edge {
  startNode:uint;
  endNode:uint;
}

This means these node references are an index into allNodes.

Note that there's very few serialization formats that allow graphs, e.g. Protocol Buffers and JSON both only allow trees.

c++ write data with cyclic dependencies in binary file using flatbuffers

2 Answers