graph - graph6 格式如何工作？

Question

我一直在到处寻找 .g6 或 graph6 格式的工作原理，但我什至不知道它是如何工作的，我发誓它就像魔术一样。

F?B~w

那是以 ASCII 形式表示的图形。它可以由 Wolfram Mathematica、Sage 和 Maple 解释，仅举几例，并为我们提供视觉效果。然而，在深入研究 Sage 的开源代码数小时后，我终生无法弄清楚他们如何将其解读为图表。

我想知道是否可以在上面的图中搜索哈密顿循环而不必将它们转换为邻接矩阵？或者，如果这是不可能的，我们如何将其转换为邻接矩阵？

任何帮助，将不胜感激。

Answer 1

reference to the format description Oliver Charlesworth 已经提供了，但简而言之，基本思想是用 ASCII 可打印字符对图形大小和邻接矩阵的上三角形进行编码。

从原始无向图中，计算邻接矩阵。
这保证是对称的，所以我们关心的是上部
该矩阵的三角形，不包括对角线
同样为零。

接下来，构建一个大小为 n*(n-1)/2 的位向量通过穿越上层
矩阵的三角形逐行。例如，对于 4x4 矩阵，
遍历将是 (1,2),(1,3),(1,4),(2,3),(2,4),(3,4)。

在您的位向量前面加上图形大小 n(作为一个二进制字)，并将生成的位向量分解为每个 6 位的块。

将每个 6 位块转换为 63 到 126 范围内的整数，然后将每个转换为相应的 ASCII 字符并将它们连接起来。

请注意，graph6 格式不支持有向图或加权图。我相信它是由 Brendan McKay 创建的(在 nauty source 中有它的实现)并且有两种相关的格式:sparse6(用于稀疏图)和 digraph6(用于有向图)。

digraph6 格式似乎相当新(在 nauty 2.6 中添加)并且类似于 graph6，除了为了处理有向图，该格式编码整个邻接矩阵减去对角线，而不仅仅是上三角形。