我一直在到处寻找 .g6 或 graph6 格式的工作原理,但我不知道它是如何工作的,我发誓它就像魔法一样。
F?B~w
这是一个以 ASCII 形式表示的图表。它可以由 Wolfram Mathematica、Sage 和 Maple 等进行解释,并为我们提供视觉效果。然而,在深入研究 Sage 的开源代码几个小时后,我无法弄清楚他们如何将其视为图表。
我想知道是否可以在上图中搜索哈密顿循环而不必将它们转换为邻接矩阵?或者,如果这是不可能的,我们如何将其转换为邻接矩阵?
任何帮助,将不胜感激。
The 参考格式说明 http://users.cecs.anu.edu.au/~bdm/data/formats.txtOliver 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 创建的(在航海来源 http://pallini.di.uniroma1.it/)并且有两种相关格式:sparse6(用于稀疏图)和 digraph6(用于有向图)。
digraph6 格式似乎相当新(在 nauty 2.6 中添加),与 graph6 类似,只是为了处理有向图,该格式编码减去对角线的整个邻接矩阵,而不仅仅是上三角形。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)