我正在尝试通过使用 FlatBuffers 将图写入二进制文件。图由节点和边组成。每个节点至少有一个边缘,每个边缘由两个节点组成。
摘自MyGraph.fbs:
namespace MyGraph;
table Node {
edges:[Edge];
}
table Edge {
startNode:Node;
endNode:Node;
}
table Graph {
allNodes:[Node];
}
root_type Graph;
现在,我想创建一个简单的图并将其写入字节文件:
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);
问题是,在创建节点之后,我无法将边缘添加到node1和node2的edges-vector中。是否有针对两种类型之间的这种循环依赖的解决方案。
最佳答案
您不能将循环结构存储在FlatBuffer中(它使用无符号偏移量强制子代始终位于父代之前)。
但是,您可以存储DAG。
要编码循环结构,您必须为节点或边缘引用使用索引,例如
table Edge {
startNode:uint;
endNode:uint;
}
这意味着这些节点引用是
allNodes
的索引。请注意,几乎没有允许图的序列化格式,例如 Protocol Buffer 和JSON都只允许树。