如何解读Pynauty中certificate返回的字节串形式图信息？

背景 #

Pynauty是基于Brendan McKay的Nauty包开发的Python/C扩展模块，其中的certificate函数会根据顶点的规范标号计算图的证书，返回结果为字节串格式。

示例代码 #

g = Graph(number_of_vertices=19, directed=False,
          adjacency_dict={
              0: [1, 7, 11, 14, 17, 18],
              1: [2, 3, 4, 5, 6],
              7: [8, 9, 10],
              11: [12, 13],
              14: [15, 16],
              12: [13],
              13: [17],
              17: [18],
              18: [8],
              8: [9],
              9: [10],
              10: [15],
              15: [16],
              16: [2],
              2: [3],
              3: [4],
              4: [5],
              5: [6],
              6: [12],
          },
          vertex_coloring=[],
)
g1 = certificate(g)

执行结果 #

b'\x00\x00\x00\x00\x00\x80\x01 \x00\x00\x00\x00\x00\x80\x02 \x00\x00\x00\x00\x00\x80\x00\xc0\x00\x00\x00\x00\x00 \x04\x01\x00\x00\x00\x00\x00 \x08\x02\x00\x00\x00\x00\x00 \x00\x03\x00\x00\x00\x00\x00 \x00\x0c\x00\x00\x00\x00\x00 \x00\x14\x00\x00\x00\x00\x00@"\\x00\\x00\\x00\\x00\\x00\\x00@\\t\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x94\\x00\\x00\\x00\\x00\\x00\\x00@$\\x00\\x00\\x00\\x00\\x00\\x00\\x00A\\x08\\x00\\x00\\x00\\x00\\x00\\x000\\x10\\x00\\x00\\x00\\x00\\x00@\\x80@\\x00\\x00\\x00\\x00\\x00\\x00H\\x80\\x00\\x00\\x00\\x00\\x00@\\x00\\xe0\\x00\\x00\\x00\\x00\\x00\\xa0\\xd2\\x00\\x00\\x00\\x00\\x00\\x00@\\x00\\x1f'

问题1：返回的证书是不是输入图的另一种形式？ #

是，但它不是图的完整结构表示。这个证书是图的规范形式的压缩哈希表示，核心用途是快速判断图同构：同构的图会生成完全一致的证书，不同构的图证书必然不同。它只保留了图的同构不变量，并非图的结构编码。

问题2：该过程是否可逆？ #

不可逆。Pynauty返回的字节串证书是经过压缩和哈希处理的结果，丢失了图的具体结构细节，无法从证书还原出原始图或其规范形式的图。如果需要可逆的规范形式，应该使用canon_label函数获取规范标号后的图结构，而非certificate。

问题3：能否转换为graph6格式？ #

可以通过以下步骤实现：

1. 调用canon_label函数获取图的规范标号排列，得到规范形式的图；
2. 将Pynauty的Graph对象转换为NetworkX图（或其他支持graph6的库的图对象）；
3. 使用对应库的工具生成graph6格式数据（比如NetworkX的nx.readwrite.graph6.to_graph6_bytes方法）。

生成的graph6格式文件可直接用showg等工具打开，便于后续操作。

内容的提问来源于stack exchange，提问作者licheng