k-Weisfeiler-Lehman同构测试Python实现

以下是一个简单的Python实现示例：

import networkx as nx

def kwl_graph_hash(graph, k):
    labels = nx.get_node_attributes(graph, 'label')
    node_hashes = {node: labels[node] for node in graph.nodes}
    
    for _ in range(k):
        new_node_hashes = {}
        for node in graph.nodes:
            neighbors = sorted(graph.neighbors(node))
            neighbor_hashes = [node_hashes[neighbor] for neighbor in neighbors]
            node_hash = str(labels[node]) + ''.join(neighbor_hashes)
            new_node_hashes[node] = hash(node_hash)
        node_hashes = new_node_hashes
    
    return node_hashes

def kwl_isomorphism_test(graph1, graph2, k):
    hash1 = kwl_graph_hash(graph1, k)
    hash2 = kwl_graph_hash(graph2, k)
    return hash1 == hash2

# 创建两个图
graph1 = nx.Graph()
graph1.add_nodes_from([1, 2, 3])
graph1.add_edges_from([(1, 2), (2, 3)])

graph2 = nx.Graph()
graph2.add_nodes_from([1, 2, 3])
graph2.add_edges_from([(1, 2), (1, 3)])

# 进行同构测试
is_isomorphic = kwl_isomorphism_test(graph1, graph2, 2)
print("Graphs are isomorphic: ", is_isomorphic)

在这个例子中，kwl_graph_hash函数用于计算给定图的K-Weisfeiler-Lehman哈希。它使用图的节点标签和邻居节点的哈希来计算每个节点的哈希值。kwl_isomorphism_test函数使用kwl_graph_hash函数来比较两个图的哈希值，判断它们是否同构。最后，我们创建两个图并进行同构测试。