Как найти граф иерархии ребер из ориентированного ациклического графа в питоне - PullRequest
5 голосов
/ 13 марта 2019

У меня есть следующие данные:
enter image description here

Я хочу новый график следующим образом:
enter image description here
Который представляет иерархию ребер предыдущего графа.

1 Ответ

0 голосов
/ 29 марта 2019

Вы хотите построить граф с ребрами между узлами в исходном графе как узлами, а узлы в исходных графах как ребрами, как я понимаю. В этом случае ваш график в посте неверен. Например: у вас есть узел 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'
    )
)

Для этого графика:

enter image description here

Будет построен новый граф:

enter image description here

Обратите внимание, что все ребра от корней в оригинальном DAG превращаются в корни в новом DAG. Также обратите внимание, что для каждого ребра конец начального узла равен началу конечного узла.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...