python - 如何通过用连接路径起点和终点的边替换每条最长的非分支路径来减少 DAG？

Question

我想通过用连接路径起点和终点的边替换每条最长的非分支路径来减少 DAG。

例如，对于这样的图表，我想缩小它

a->b->c->d
a->d

到以下。当然，真正的 DAG 可能比这更复杂。

a->d
a->d

我找不到使用 networkx 来实现此目的的方法。有谁知道如何在网络中这样做？谢谢。

Answer 1

据我所知，Networkx 不支持开箱即用。然而，实现起来并不太复杂。您可以简单地迭代图中的节点，然后按照以下步骤操作:

1. 删除仅具有一条传入边和一条传出边的每个节点。
2. 使用新边将传入边的源节点连接到传出边的目标节点。

这似乎有效:

def should_remove_node(graph, node):
    return graph.in_degree(node) == 1 and graph.out_degree(node) == 1

for node in list(G.nodes()):
    if should_remove_node(G, node):
        in_node = list(G.in_edges(node))[0][0]
        out_node = list(G.out_edges(node))[0][1]
        G.add_edge(in_node, out_node)
        G.remove_node(node)