Поиск преемников преемников в ориентированном графе в NetworkX - PullRequest
Новая
       21

Поиск преемников преемников в ориентированном графе в NetworkX

2 голосов
/ 31 июля 2011

Я работаю над кодом для ориентированного графа в NetworkX и попал в блок, который, вероятно, является результатом моего сомнительного опыта программирования. Я пытаюсь сделать следующее:

У меня есть ориентированный граф G с двумя "родительскими узлами" вверху, из которых вытекают все остальные узлы. При построении графика этой сети я хотел бы построить график для каждого узла, который является потомком «Parent 1» одного цвета, а для всех остальных узлов - другого цвета. Это означает, что мне нужен список наследников Родителя 1.

Прямо сейчас я могу легко получить первый их слой, используя: 

descend= G.successors(parent1)

Проблема в том, что это дает мне только первое поколение преемников. Предпочтительно, чтобы я хотел, чтобы преемники преемников, преемники преемников преемников и т. Д. Произвольно, потому что было бы чрезвычайно полезно иметь возможность выполнять анализ и составлять график, не зная точно, сколько в нем поколений. .

Есть идеи, как к этому подойти?

Ответы [ 5 ]

5 голосов
/ 31 июля 2011

Вам не нужен список потомков, вы просто хотите их раскрасить. Для этого вам просто нужно выбрать алгоритм, который пересекает график и использовать его, чтобы покрасить края.

Например, вы можете сделать 

from networkx.algorithms.traversal.depth_first_search import dfs_edges

G = DiGraph( ... )
for edge in dfs_edges(G, parent1):
    color(edge)

См. http://networkx.lanl.gov/reference/algorithms.traversal.html

1 голос
/ 16 мая 2013

Я думаю, что Networkx изменился с тех пор, как несколько лет назад @Jochen Ritzel ответил.

Теперь выполняется следующее, изменяя только оператор импорта. 

import networkx
from networkx import dfs_edges

G = DiGraph( ... )
for edge in dfs_edges(G, parent1):
    color(edge)
1 голос
/ 31 июля 2011

Чтобы ответ был несколько чище и его легче было найти будущим людям, которые наткнулись на него, вот код, который я использовал в итоге: 

G = DiGraph() # Creates an empty directed graph G
infile = open(sys.argv[1])
for edge in infile:
    edge1, edge2 = edge.split() #Splits data on the space
    node1 = int(edge1) #Creates integer version of the node names 
    node2 = int(edge2)
    G.add_edge(node1,node2) #Adds an edge between two nodes

parent1=int(sys.argv[2])   
parent2=int(sys.argv[3])

data_successors = dfs_successors(G,parent1)
successor_list = data_successors.values()
allsuccessors = [item for sublist in successor_list for item in sublist]

pos = graphviz_layout(G,prog='dot') 
plt.figure(dpi=300)
draw_networkx_nodes(G,pos,node_color="LightCoral")
draw_networkx_nodes(G,pos,nodelist=allsuccessors, node_color="SkyBlue")
draw_networkx_edges(G,pos,arrows=False) 
draw_networkx_labels(G,pos,font_size=6,font_family='sans-serif',labels=labels)
1 голос
/ 31 июля 2011

Ну, преемник наследника - это просто наследник потомков, верно? 

# First successors
descend = G.successors(parent1)
# 2nd level successors
def allDescendants(d1):
   d2 = []
   for d in d1:
       d2 += G.successors(d)
   return d2

descend2 = allDescendants(descend)

Чтобы получить потомков 3-го уровня, вызовите allDescendants (d2) и т. Д.

Edit: Выпуск 1: allDescend = descend + descend2 дает вам два набора вместе, сделайте то же самое для дальнейших уровней потомков.

Issue2: Если у вас есть циклы на графике, вам нужно сначала изменить код, чтобы проверить, посещали ли вы этого потомка раньше, например: 

def allDescendants(d1, exclude):
   d2 = []
   for d in d1:
       d2 += filter(lambda s: s not in exclude, G.successors(d))
   return d2

Таким образом, вы передаете allDescend в качестве второго аргумента вышеупомянутой функции, чтобы он не был включен в будущие потомки. Вы продолжаете делать это до тех пор, пока allDescandants() не вернет пустой массив, и в этом случае вы узнаете, что изучили весь граф, и не остановитесь.

Поскольку это начинает выглядеть как домашнее задание, я дам вам понять, как собрать все это вместе. ;)

0 голосов
/ 07 августа 2017

Если вы хотите получить все последующие узлы, не проходя через ребра, другой способ может быть: 

import networkx as nx
G = DiGraph( ... )
successors = nx.nodes(nx.dfs_tree(G, your_node))

Я заметил, что если вы позвоните вместо: 

successors = list(nx.dfs_successors(G, your_node)

узлы нижнего уровня как-то не включены.

...