如何在python中从有向非循环图中找到边层次结构图

Question

我有以下数据：

我想要一个新的图表如下： 表示上一个图的边缘层次结构。

Answer 1

您想构建原始图中节点之间边缘的图形作为节点，原始图形中的节点作为边缘，我理解。在这种情况下，帖子中的图表不正确。例如：你有节点be，它是ae的继承者，但在原始图中它不是真的，ae和be是平行的。我构造了一个代码来解决这个问题：

import networkx as nx
import random
from itertools import groupby

# Create a random DAG
G = nx.gnp_random_graph(10,0.3,directed=True)
DAG = nx.DiGraph([(u,v) for (u,v) in G.edges() if u<v])

res = nx.DiGraph()
# Create nodes in new DAG as edges in original DAG
res.add_nodes_from(list(DAG.edges()))
sorted_res_nodes = sorted(res.nodes, key=lambda x: x[1])

# Connect all nodes with end of node1 is equal to start of node2
for n1 in sorted_res_nodes:
    for n2 in sorted_res_nodes:
        if n1[1] == n2[0]:
            res.add_edge(n1, n2)

# Draw graphs
nx.draw(
    DAG,
    with_labels=True,
    pos=nx.drawing.nx_agraph.graphviz_layout(
        DAG, prog='dot'
    )
)
nx.draw(
    res,
    with_labels=True,
    pos=nx.drawing.nx_agraph.graphviz_layout(
        res, prog='dot'
    )
)

对于此图：

将构建新图：

请注意，原始DAG中根的所有边都转换为新DAG中的根。另请注意，对于每个边，起始节点的末尾等于结束节点的起点。