Python案例如何用Networkx做子图同构

wen python案例 2026-07-16 208

本文目录导读：

基础子图同构检测
带节点属性匹配
带边属性匹配
多子图匹配（查找所有形状）
可视化匹配结果
实际应用：分子结构匹配
性能优化技巧

我来详细介绍如何使用NetworkX进行子图同构检测。

基础子图同构检测

import networkx as nx
import matplotlib.pyplot as plt
# 创建目标图（大图）
G_target = nx.Graph()
G_target.add_edges_from([
    (1, 2), (2, 3), (3, 4), (4, 1),  # 正方形
    (1, 5), (2, 6), (3, 7), (4, 8),  # 向外连接
    (5, 6), (6, 7), (7, 8), (8, 5)   # 外圈
])
# 创建子图（要查找的模式）
G_pattern = nx.Graph()
G_pattern.add_edges_from([
    ('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'A')  # 正方形
])
# 检测子图同构
matcher = nx.algorithms.isomorphism.GraphMatcher(G_target, G_pattern)
is_isomorphic = matcher.subgraph_is_isomorphic()
print(f"是否找到子图同构: {is_isomorphic}")
# 查找所有匹配
if is_isomorphic:
    matches = list(matcher.subgraph_isomorphisms_iter())
    print(f"找到 {len(matches)} 个匹配:")
    for i, match in enumerate(matches[:3]):  # 只显示前3个
        print(f"匹配 {i+1}: {match}")

带节点属性匹配

# 创建带属性的图
G1 = nx.Graph()
G1.add_nodes_from([
    (1, {'color': 'red', 'label': 'A'}),
    (2, {'color': 'blue', 'label': 'B'}),
    (3, {'color': 'red', 'label': 'A'}),
    (4, {'color': 'green', 'label': 'C'})
])
G1.add_edges_from([(1, 2), (2, 3), (3, 4)])
G2 = nx.Graph()
G2.add_nodes_from([
    ('a', {'color': 'red', 'label': 'A'}),
    ('b', {'color': 'blue', 'label': 'B'}),
    ('c', {'color': 'red', 'label': 'A'}),
    ('d', {'color': 'green', 'label': 'C'})
])
G2.add_edges_from([('a', 'b'), ('b', 'c'), ('c', 'd')])
# 自定义节点匹配函数
def node_match(n1_attrs, n2_attrs):
    return n1_attrs['color'] == n2_attrs['color'] and n1_attrs['label'] == n2_attrs['label']
# 使用自定义匹配函数
matcher = nx.algorithms.isomorphism.GraphMatcher(
    G1, G2, node_match=node_match
)
print(f"带属性匹配结果: {matcher.is_isomorphic()}")
if matcher.is_isomorphic():
    print(f"节点映射: {list(matcher.mapping.items())}")

带边属性匹配

# 创建带边属性的图
G3 = nx.Graph()
G3.add_edge(1, 2, weight=1.0)
G3.add_edge(2, 3, weight=2.0)
G3.add_edge(3, 4, weight=1.0)
G4 = nx.Graph()
G4.add_edge('A', 'B', weight=1.0)
G4.add_edge('B', 'C', weight=2.0)
G4.add_edge('C', 'D', weight=1.0)
# 自定义边匹配函数
def edge_match(e1_attrs, e2_attrs):
    return e1_attrs['weight'] == e2_attrs['weight']
matcher = nx.algorithms.isomorphism.GraphMatcher(
    G3, G4, edge_match=edge_match
)
print(f"带边属性匹配结果: {matcher.is_isomorphic()}")

多子图匹配（查找所有形状）

# 创建复杂图
G_big = nx.Graph()
G_big.add_edges_from([
    (0, 1), (1, 2), (2, 3), (3, 0),  # 方形
    (0, 4), (4, 5), (5, 0),          # 三角形
    (2, 6), (6, 7), (7, 2),          # 另一个三角形
    (3, 8), (8, 9), (9, 10), (10, 3) # 另一个方形
])
# 定义多个子图模式
patterns = {
    'triangle': nx.Graph([('a', 'b'), ('b', 'c'), ('c', 'a')]),
    'square': nx.Graph([('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'a')]),
    'path_3': nx.Graph([('a', 'b'), ('b', 'c')])
}
# 查找每种模式
for name, pattern in patterns.items():
    matcher = nx.algorithms.isomorphism.GraphMatcher(G_big, pattern)
    count = sum(1 for _ in matcher.subgraph_isomorphisms_iter())
    print(f"找到 {count} 个 {name} 形状")

可视化匹配结果

def visualize_subgraph_matches(G, pattern):
    """可视化子图匹配结果"""
    matcher = nx.algorithms.isomorphism.GraphMatcher(G, pattern)
    fig, axes = plt.subplots(1, 2, figsize=(12, 5))
    # 绘制原图
    pos = nx.spring_layout(G)
    nx.draw(G, pos, ax=axes[0], with_labels=True, node_color='lightblue',
            node_size=500, font_size=10)
    axes[0].set_title("Original Graph")
    # 绘制第一个匹配结果
    match = next(matcher.subgraph_isomorphisms_iter(), None)
    if match:
        matched_nodes = list(match.keys())
        pos_pattern = nx.spring_layout(pattern)
        nx.draw(pattern, pos_pattern, ax=axes[1], with_labels=True,
                node_color='lightgreen', node_size=500, font_size=10)
        axes[1].set_title(f"Matched Pattern\n$\\rightarrow$ {matched_nodes}")
    plt.tight_layout()
    plt.show()
# 测试可视化
G_test = nx.Graph()
G_test.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 1), (1, 5), (2, 6)])
pattern_test = nx.Graph([('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'A')])
visualize_subgraph_matches(G_test, pattern_test)

实际应用：分子结构匹配

def find_molecular_patterns(molecule_graph, functional_groups):
    """
    在分子图中查找功能团
    参数:
    - molecule_graph: 分子图
    - functional_groups: 功能团字典 {name: graph}
    """
    results = {}
    for group_name, group_graph in functional_groups.items():
        matcher = nx.algorithms.isomorphism.GraphMatcher(
            molecule_graph, group_graph
        )
        matches = list(matcher.subgraph_isomorphisms_iter())
        if matches:
            results[group_name] = matches
            print(f"找到 {group_name}: {len(matches)} 个")
    return results
# 示例：查找苯环和羧基
benzene = nx.Graph([(1,2), (2,3), (3,4), (4,5), (5,6), (6,1)])
carboxyl = nx.Graph([(1,2), (2,3), (2,4)])  # C(=O)OH
molecule = nx.Graph()
molecule.add_edges_from([
    (1,2), (2,3), (3,4), (4,5), (5,6), (6,1),  # 苯环
    (1,7), (7,8), (7,9), (7,10)                 # 取代基
])
functional_groups = {
    'benzene': benzene,
    'carboxyl': carboxyl
}
results = find_molecular_patterns(molecule, functional_groups)

性能优化技巧

def optimized_subgraph_matching(G_large, G_small, max_matches=10):
    """
    优化的子图匹配，限制匹配数量
    """
    matcher = nx.algorithms.isomorphism.GraphMatcher(G_large, G_small)
    matches = []
    for i, match in enumerate(matcher.subgraph_isomorphisms_iter()):
        if i >= max_matches:
            break
        matches.append(match)
    return matches
# 使用节点标签加速匹配
def fast_match_with_labels(G_target, G_pattern, node_labels):
    """
    使用节点标签加速子图匹配
    参数:
    - node_labels: 字典 {node: label}
    """
    def node_match_func(n1_attrs, n2_attrs):
        return n1_attrs.get('label') == n2_attrs.get('label')
    # 添加标签属性
    nx.set_node_attributes(G_target, node_labels, 'label')
    nx.set_node_attributes(G_pattern, node_labels, 'label')
    matcher = nx.algorithms.isomorphism.GraphMatcher(
        G_target, G_pattern, node_match=node_match_func
    )
    return list(matcher.subgraph_isomorphisms_iter())

基础API: GraphMatcher 和 subgraph_isomorphisms_iter()
自定义匹配: 通过 node_match 和 edge_match 参数
性能考虑:
- 子图同构是NP完全问题
- 对于大图,考虑使用标签或属性加速
- 可以使用VF2算法（NetworkX默认使用）
应用场景:
- 分子结构匹配
- 社交网络模式检测
- 电路设计验证
- 知识图谱查询