图编辑距离（GED）和（非）同构图

图编辑距离（Graph Edit Distance，GED）是一种度量两个图之间相似性的方法，它可以衡量将一个图转换为另一个图所需的最小编辑操作（如插入、删除和修改节点或边）的数量。

下面是一个使用NetworkX库和Hungarian算法来计算GED的代码示例：

import networkx as nx
import numpy as np
from scipy.optimize import linear_sum_assignment

def graph_edit_distance(G1, G2):
    num_nodes1 = len(G1)
    num_nodes2 = len(G2)
    cost_matrix = np.zeros((num_nodes1, num_nodes2))

    for i in range(num_nodes1):
        for j in range(num_nodes2):
            if G1.nodes[i]['label'] != G2.nodes[j]['label']:
                cost_matrix[i][j] += 1 # 对节点的编辑代价为1

    for u, v in G1.edges():
        if G1.edges[u, v]['label'] not in G2.edges.data('label'):
            cost_matrix[u][v] += 1 # 对边的编辑代价为1

    row_ind, col_ind = linear_sum_assignment(cost_matrix)
    ged = cost_matrix[row_ind, col_ind].sum()
    return ged

# 创建两个图
G1 = nx.Graph()
G1.add_nodes_from([(0, {'label': 'A'}), (1, {'label': 'B'}), (2, {'label': 'C'})])
G1.add_edges_from([(0, 1, {'label': 'edge1'}), (1, 2, {'label': 'edge2'})])

G2 = nx.Graph()
G2.add_nodes_from([(0, {'label': 'A'}), (1, {'label': 'B'}), (2, {'label': 'D'})])
G2.add_edges_from([(0, 1, {'label': 'edge1'}), (1, 2, {'label': 'edge3'})])

# 计算GED
ged = graph_edit_distance(G1, G2)
print("Graph Edit Distance:", ged)

对于判断两个图是否同构（即结构相同），可以通过比较它们的图同构哈希值来实现。下面是一个使用NetworkX库计算图同构哈希值的代码示例：

import networkx as nx

def isomorphic_graphs(G1, G2):
    hash1 = nx.graph_hash(G1)
    hash2 = nx.graph_hash(G2)
    return hash1 == hash2

# 创建两个图
G1 = nx.Graph()
G1.add_nodes_from([(0, {'label': 'A'}), (1, {'label': 'B'}), (2, {'label': 'C'})])
G1.add_edges_from([(0, 1, {'label': 'edge1'}), (1, 2, {'label': 'edge2'})])

G2 = nx.Graph()
G2.add_nodes_from([(0, {'label': 'A'}), (1, {'label': 'B'}), (2, {'label': 'C'})])
G2.add_edges_from([(0, 1, {'label': 'edge1'}), (1, 2, {'label': 'edge2'})])

# 判断是否同构
isomorphic = isomorphic_graphs(G1, G2)
print("Isomorphic Graphs:", isomorphic)

注意：在比较两个图是否同构之前，需要确保它们的节点和边的标签和连接方式相同。