如何为无向NetworkX图生成同构判定哈希以高效存储唯一图？

背景 #

在思考纯文本存储唯一图的高效方案时，我确定了以下流程：

• 按图的节点数量创建对应名称的文件夹
• 存储节点数为n的新图时，加载该文件夹内所有图，检查是否存在同构图

现有问题 #

这种方式的检查复杂度为O(m)（m是节点数为n的非同构图数量）。我想通过为每个图计算一种哈希值，将图以哈希值为文件名存储，这样新图只需计算自身哈希值，通过读取文件名就能直接判断是否已存在（无需读取文件内容），将检查复杂度降为O(1)（实际为O(0)，因为不用加载任何已有图）。

检查说明 #

• 此处的检查指从文件加载图以计算属性的次数
• O(m)中的m为节点数为n的非同构图的数量

前提假设 #

• 图必须以纯文本格式存储
• 加载纯文本图进行检查的开销较高

核心问题 #

能否在Python中为无向NetworkX图x计算一种哈希值，使得另一图y可通过比较哈希值判定二者是否同构？若可以，该如何实现？

可以实现，核心思路是提取图的同构不变量并标准化，再基于这些特征计算哈希——同构图的标准化特征完全一致，哈希值也会相同；非同构图的哈希值大概率不同。

实现步骤 #

1. 提取同构不变量：选择一组能唯一标识同构图的特征，比如排序后的节点度数序列、标准化邻接矩阵、图的全局属性（节点数、边数、直径等）、特征值序列等。
2. 标准化特征：对提取的特征做标准化处理（比如排序），消除节点编号差异带来的特征顺序不同问题，确保同构图的特征完全一致。
3. 计算稳定哈希：将标准化后的特征组合为可哈希对象，用稳定的哈希算法（如SHA256）生成哈希值，避免内置hash()函数的随机性。

具体代码实现 #

import networkx as nx
import hashlib

def graph_isomorphism_hash(G):
    # 1. 提取并标准化节点度数序列
    degree_seq = tuple(sorted(d for n, d in G.degree()))
    
    # 2. 生成标准化邻接矩阵：按节点度数+节点编号排序节点后生成矩阵
    sorted_nodes = sorted(G.nodes(), key=lambda n: (G.degree(n), n))
    adj_matrix = nx.to_numpy_array(G, nodelist=sorted_nodes)
    adj_tuple = tuple(adj_matrix.flatten().astype(int))
    
    # 3. 提取全局同构不变量
    num_nodes = G.number_of_nodes()
    num_edges = G.number_of_edges()
    diameter = nx.diameter(G) if nx.is_connected(G) else -1
    
    # 4. 组合所有不变量为可哈希元组
    invariant_tuple = (degree_seq, adj_tuple, num_nodes, num_edges, diameter)
    
    # 5. 计算SHA256稳定哈希
    hash_input = str(invariant_tuple).encode('utf-8')
    return hashlib.sha256(hash_input).hexdigest()

# 测试示例
G1 = nx.Graph()
G1.add_edges_from([(0,1), (1,2), (2,0)])  # 三角形

G2 = nx.Graph()
G2.add_edges_from([(1,2), (2,3), (3,1)])  # 同构三角形

G3 = nx.Graph()
G3.add_edges_from([(0,1), (1,2)])  # 非同构的链状图

print(graph_isomorphism_hash(G1))  # 与G2哈希一致
print(graph_isomorphism_hash(G2))
print(graph_isomorphism_hash(G3))  # 与前两者哈希不同

注意事项 #

• 哈希冲突：理论上存在不同图哈希值相同的概率，若需绝对严谨，可在哈希值相同时，再调用nx.is_isomorphic()做最终验证，这种情况概率极低，不会影响整体效率。
• 不变量扩展：针对特殊图（如正则图），可补充特征值序列、子图计数等不变量，提升区分度。
• 哈希稳定性：必须使用hashlib中的算法，避免Python内置hash()函数在不同会话中返回不同值的问题。

内容的提问来源于stack exchange，提问作者a.t.