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

Question

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

例如，对于这样的图表，我想减少它

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

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

a->d
a->d

我找不到使用networkx的方法。有人知道如何在网络中这样做吗？谢谢。

标签： pythonnetworkx

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)