如何通过用连接路径起点和终点的边缘代替每个最长的非分支路径来减少DAG? [英] How to reduce a DAG by replacing each longest non-branching path by an edge connecting the start and the end of the path?

问题描述

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

I'd like to reduce a DAG by replacing each longest non-branching path by an edge connecting the start and the end of the path.

例如，对于这样的图形，我想将其缩小

For example, for a graph like this, I'd like to reduce it

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

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

to the following. Of course, a real DAG can be more complex than this.

a->d
a->d

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

I don't find a way to do so with networkx. Does anybody know how to do so in network? Thanks.

推荐答案

据我所知，Networkx不支持开箱即用.但是，实现起来并不太复杂.您可以简单地遍历图中的节点，然后执行以下步骤:

As far as I know, Networkx doesn't support it out of the box. However it isn't too complicated to implement. You can simply iterate over the nodes in the graph, and follow the next steps:

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)

这篇关于如何通过用连接路径起点和终点的边缘代替每个最长的非分支路径来减少DAG?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！