5

假设我在 NetworkX 中制作了有向图：

import networkx as nx

G = nx.DiGraph()

n = ["A","B","C","D","E","F","H","I","J","K","L","X","Y","Z"]

e = [("A","Z"),("Z","B"),("B","Y"),("Y","C"),("C","G"),("G","H"),("G","I"),("I","J"),("K","J"),("J","L"),("F","E"),("E","D"),("D","X"),("X","C")]

G.add_nodes_from(n)

G.add_edges_from(e)

我将如何删除所有入度和出度等于 1 的节点，以便我的图表看起来像这样？：

import networkx as nx

G = nx.DiGraph()

n = ["A","C","F","G","H","J","K","L"]

e = [("A","C"),("C","G"),("G","H"),("G","J"),("K","J"),("J","L")

G.add_nodes_from(n)

G.add_edges_from(e)

这个想法是删除“流通”节点并保持连接性。

4

2 回答 2

7

以下代码可以满足您的需求，尽管我看不到最终结果中您会从 ("A", "C") 和 ("G", "J") 获得边的位置。

import networkx as nx

def remove_edges(g, in_degree=1, out_degree=1):
    g2=g.copy()
    d_in=g2.in_degree(g2)
    d_out=g2.out_degree(g2)
    print(d_in)
    print(d_out)
    for n in g2.nodes():
        if d_in[n]==in_degree and d_out[n] == out_degree: 
            g2.remove_node(n)
    return g2

G_trimmed = remove_edges(G)
G_trimmed.edges()
#outputs [('C', 'G'), ('G', 'H'), ('K', 'J'), ('J', 'L')]
G_trimmed.nodes()
#outputs ['A', 'C', 'G', 'F', 'H', 'K', 'J', 'L']
于 2013-07-22T09:15:29.117 回答
4

本质上，只需遍历节点并检查它们是否是“流通节点”，使用remove_node和add_edge重新连接图形。定义一个函数：

def remove_flow_through(graph):
    for n in graph.nodes():
        pred = graph.predecessors(n)
        succ = graph.successors(n)
        if len(pred) == len(succ) == 1:
            graph.remove_node(n)
            graph.add_edge(pred[0], succ[0])

该函数会就地修改图形，因此如果需要，请处理图形的副本。

现在remove_flow_through重复调用，直到图中的节点数不再减少：

while True:
    prev_len = len(G)
    remove_flow_through(G)
    if len(G) == prev_len:
        break

示例图具有所有流通节点，只需调用remove_flow_through. 然而，有可能移除一个节点来重现一条现有的边，这会导致一个带有剩余流通节点的图。这方面的一个例子是：

dg = nx.DiGraph([(1,2), (2,3), (3,4), (2,5), (5,3)])
于 2013-07-30T11:08:32.520 回答