python - 创建子图，其中删除了从某些节点下降的节点

Question

我想生成一个子图，其中仅包含最终不是具有特定属性的节点的后继节点，skip.

考虑到下图节点b的skip属性设置为True，我想生成它下面显示的子图。在子图中，因为d和f是 的最终后继者b，所以b不包括它们。

使用蛮力方法，我可以递归地找到继任者b并将其从节点列表中删除，然后将它们传递networkx.DiGraph.subgraph()给这感觉就像将包含在图形库中的那种东西）：

def noskip_subgraph(g):
    # All nodes in g.
    nodes = set(g.nodes)

    for node, skip in g.nodes(data="skip"):
        if not skip:
            continue

        # Remove nodes and all descendants where `skip` is set to True.    
        nodes.remove(node)
        nodes.difference_update(nx.algorithms.dag.descendants(g, node))

    # Return subraph of g with `skip` nodes and their descendants removed.
    return g.subgraph(nodes)

作为参考，这里是用于生成上述图表的代码：

import networkx as nx
from networkx.drawing.nx_pydot import graphviz_layout
import matplotlib.pyplot as plt

g1 = nx.DiGraph()
g1.add_node("b", skip=True)
g1.add_edge("a", "b")
g1.add_edge("a", "c")
g1.add_edge("b", "d")
g1.add_edge("c", "e")
g1.add_edge("d", "f")
g1.add_edge("e", "f")

layout = graphviz_layout(g1, prog="dot")

labels = dict(zip(g1.nodes, g1.nodes))
labels["b"] += " (skip=True)"

#nx.draw(g1, pos=layout, labels=labels)
#plt.savefig("graph1.png")

g2 = nx.DiGraph()
g2.add_edge("a", "c")
g2.add_edge("c", "e")

layout = graphviz_layout(g2, prog="dot")

#nx.draw(g2, pos=layout, with_labels=True)
#plt.savefig("graph2.png")

def noskip_subgraph(g):
    nodes = set(g.nodes)

    for node, skip in g.nodes(data="skip"):
        if not skip:
            continue

        # Remove nodes and all descendants where `skip` is set to True.    
        nodes.remove(node)
        nodes.difference_update(nx.algorithms.dag.descendants(g, node))

    return g.subgraph(nodes)

g3 = noskip_subgraph(g1)

layout = graphviz_layout(g2, prog="dot")

nx.draw(g3, pos=layout, with_labels=True)
plt.savefig("graph3.png")

标签： pythonmatplotlibnetworkxgraph-theory

Answer 1

您可以利用集合来提高效率。

def noskip_subgraph(g):
    nodes_to_rm = set()
    for node, skip in g.nodes(data="skip"):
        if not skip:
            continue

        nodes_to_rm.update(nx.descendants(g, node))

    return g.subgraph(g.nodes - nodes_to_rm)