如何在保留 NetworkX 网络的同时编写算法来切割节点？

Question

假设我有一个简单的网络如下，我想在保留整体结构的同时删除小写节点。我怎么做？这是一些示例代码：

import networkx as nx
G = nx.DiGraph();
G.add_edge("A","b")
G.add_edge("b","C")
G.add_edge("b","D")
G.add_edge("D","e")
G.add_edge("e","F")


def printHackyDot(x):
    for n in x.nodes():
        for pre in x.predecessors(n):
            print(pre + " -> " + n)

printHackyDot(G)
badNodes = [n for n in G.nodes if str.islower(n)]

运行这将产生：

A -> b
b -> C
b -> D
D -> e
e -> F

即

如何编写 f(G) 以获得类似的、简化的图形，少了小写节点：

A -> C
A -> D
D -> F

我尝试了以下方法，但是当连续出现两个小写字母时失败了：

for badNode in [x for x  in list(G.nodes) if str.islower(x)]:
    R.remove_node(badNode)
    for predNode in G.predecessors(badNode):
        for succNode in G.successors(badNode):
            R.add_edge(predNode,succNode)

Answer 1

我假设 R 开始时是 G 的副本？

如果您替换

，这将起作用

for badNode in [x for x  in list(G.nodes) if str.islower(x)]:
    R.remove_node(badNode)
    for predNode in G.predecessors(badNode):
        for succNode in G.successors(badNode):
            R.add_edge(predNode,succNode)

with (编辑错误删除 badNode 过早)

for badNode in [x for x  in list(R.nodes) if str.islower(x)]:
    for predNode in R.predecessors(badNode):
        for succNode in R.successors(badNode):
            R.add_edge(predNode,succNode)
    R.remove_node(badNode)

问题是，当您处理连续两个小写节点中的第一个时，它会删除该节点。但是当你处理另一个节点时，它会在 G 中看到那个节点有一个小写的邻居，它把边缘放回去。如果你看看它在 R 中的邻居，你就会正确处理它。

Answer 2

这做到了，当且仅当该图是一个 DAG。聪明的人可以解决这个问题。

def isBadNode(x):
    return str.islower(x)

def goodPreds(X,node):
    return [n for n in X.predecessors(node) if not isBadNode(n)]+[gn for n in X.predecessors(node) for gn in goodPreds(X,n) if isBadNode(n)]

def goodSuccs(X,node):
    return [n for n in X.successors(node) if not isBadNode(n)]+[gn for n in X.successors(node) for gn in goodSuccs(X,n) if isBadNode(n)]

R= G.copy()
for badNode in [x for x  in list(R.nodes) if isBadNode(x)]:
    for predNode in goodPreds(G,badNode):
        for succNode in goodSuccs(G,badNode):
            R.add_edge(predNode,succNode)
    R.remove_node(badNode)

如何在保留 NetworkX 网络的同时编写算法来切割节点？

How do I write an algorithm to cut nodes while preserving a NetworkX network?

graph-theory

networkx