子图

示例：将一个带有节点标记为支持和非支持节点的有向图 分割成一个只包含完全支持或完全非支持节点的子图列表。 改编自 lobpcg/python_examples

import networkx as nx
import matplotlib.pyplot as plt


def graph_partitioning(G, plotting=True):
    """将一个有向图分割成一系列子图，每个子图仅包含完全受支持或完全不受支持的节点。
"""
    # 根据节点的node_type属性对节点进行分类
    supported_nodes = {n for n, d in G.nodes(data="node_type") if d == "supported"}
    unsupported_nodes = {n for n, d in G.nodes(data="node_type") if d == "unsupported"}

    # Make a copy of the graph.
    H = G.copy()
    # 移除所有连接支持节点和不支持节点的边。
    H.remove_edges_from(
        (n, nbr, d)
        for n, nbrs in G.adj.items()
        if n in supported_nodes
        for nbr, d in nbrs.items()
        if nbr in unsupported_nodes
    )
    H.remove_edges_from(
        (n, nbr, d)
        for n, nbrs in G.adj.items()
        if n in unsupported_nodes
        for nbr, d in nbrs.items()
        if nbr in supported_nodes
    )

    # 收集所有被移除的边以便重建。
    G_minus_H = nx.DiGraph()
    G_minus_H.add_edges_from(set(G.edges) - set(H.edges))

    if plotting:
        # 绘制去除边后的简化图。
        _node_colors = [c for _, c in H.nodes(data="node_color")]
        _pos = nx.spring_layout(H)
        plt.figure(figsize=(8, 8))
        nx.draw_networkx_edges(H, _pos, alpha=0.3, edge_color="k")
        nx.draw_networkx_nodes(H, _pos, node_color=_node_colors)
        nx.draw_networkx_labels(H, _pos, font_size=14)
        plt.axis("off")
        plt.title("The stripped graph with the edges removed.")
        plt.show()
        # Plot the edges removed.
        _pos = nx.spring_layout(G_minus_H)
        plt.figure(figsize=(8, 8))
        ncl = [G.nodes[n]["node_color"] for n in G_minus_H.nodes]
        nx.draw_networkx_edges(G_minus_H, _pos, alpha=0.3, edge_color="k")
        nx.draw_networkx_nodes(G_minus_H, _pos, node_color=ncl)
        nx.draw_networkx_labels(G_minus_H, _pos, font_size=14)
        plt.axis("off")
        plt.title("The removed edges.")
        plt.show()

    # 找出剥离无向图中的连通分量。
    # 并使用集合，指定组件，进行分区
    # 将原始有向图转换为一系列有向子图列表
    # 仅包含完全支持或完全不支持的节点。
    subgraphs = [
        H.subgraph(c).copy() for c in nx.connected_components(H.to_undirected())
    ]

    return subgraphs, G_minus_H

创建一个示例有向图。

这个有向图有一个输入节点，标记为 in，并以蓝色绘制 并且有一个标记为 out 的输出节点，并以品红色绘制。 其余六个节点被分类为四个以绿色绘制的`支持`节点 并以红色绘制两个 不支持 的图。目标是计算一个列表 包含仅由完全“支持”或“不支持”节点组成的子图的数量。

G_ex = nx.DiGraph()
G_ex.add_nodes_from(["In"], node_type="input", node_color="b")
G_ex.add_nodes_from(["A", "C", "E", "F"], node_type="supported", node_color="g")
G_ex.add_nodes_from(["B", "D"], node_type="unsupported", node_color="r")
G_ex.add_nodes_from(["Out"], node_type="output", node_color="m")
G_ex.add_edges_from(
    [
        ("In", "A"),
        ("A", "B"),
        ("B", "C"),
        ("B", "D"),
        ("D", "E"),
        ("C", "F"),
        ("E", "F"),
        ("F", "Out"),
    ]
)

Plot the original graph.

node_color_list = [nc for _, nc in G_ex.nodes(data="node_color")]
pos = nx.spectral_layout(G_ex)
plt.figure(figsize=(8, 8))
nx.draw_networkx_edges(G_ex, pos, alpha=0.3, edge_color="k")
nx.draw_networkx_nodes(G_ex, pos, alpha=0.8, node_color=node_color_list)
nx.draw_networkx_labels(G_ex, pos, font_size=14)
plt.axis("off")
plt.title("The original graph.")
plt.show()

计算子图并绘制所有中间步骤的结果。

subgraphs_of_G_ex, removed_edges = graph_partitioning(G_ex, plotting=True)

• 
• 

绘制结果：列表中的每个子图。

for subgraph in subgraphs_of_G_ex:
    _pos = nx.spring_layout(subgraph)
    plt.figure(figsize=(8, 8))
    nx.draw_networkx_edges(subgraph, _pos, alpha=0.3, edge_color="k")
    node_color_list_c = [nc for _, nc in subgraph.nodes(data="node_color")]
    nx.draw_networkx_nodes(subgraph, _pos, node_color=node_color_list_c)
    nx.draw_networkx_labels(subgraph, _pos, font_size=14)
    plt.axis("off")
    plt.title("One of the subgraphs.")
    plt.show()

• 
• 
• 

从子图列表中恢复图

G_ex_r = nx.DiGraph()
# 组合所有子图。
for subgraph in subgraphs_of_G_ex:
    G_ex_r = nx.compose(G_ex_r, subgraph)
# 添加之前存储的边。
G_ex_r.add_edges_from(removed_edges.edges())

检查原始图和重建图是否同构。

assert nx.is_isomorphic(G_ex, G_ex_r)

绘制重建的图。

node_color_list = [nc for _, nc in G_ex_r.nodes(data="node_color")]
pos = nx.spectral_layout(G_ex_r)
plt.figure(figsize=(8, 8))
nx.draw_networkx_edges(G_ex_r, pos, alpha=0.3, edge_color="k")
nx.draw_networkx_nodes(G_ex_r, pos, alpha=0.8, node_color=node_color_list)
nx.draw_networkx_labels(G_ex_r, pos, font_size=14)
plt.axis("off")
plt.title("The reconstructed graph.")
plt.show()