Attraversamento grafico con Networkx (Python)

Question

Sto giocando un po 'con Networkx per gestire un grafico delle dipendenze. Diciamo che ho questo grafico che ogni lettera rappresenta un server

>>> G = nx.Graph() 
>>> G.add_edge("A","B") 
>>> G.add_edge("A","H") 
>>> G.add_edge("H","C") 
>>> G.add_edge("B","C") 
>>> G.add_edge("B","D") 

      A 
     / \ 
     H  B 
    / /\ 
    C   C  D 

Così qui possiamo vedere che prima di iniziare un Abbiamo bisogno di iniziare H e B e per avviare H dobbiamo cominciare C e poi per avviare B wee necessità di avviare C e D

con giocherellare un po 'con NetworkX ho scoperto che posso ottenere che facendo un attraversamento DFS

print nx.dfs_successors(G,"A") 
{A:[H,B], H:[C], B:[D] } 

Ma ho un problema con questo metodo. Come puoi vedere quando ci sono due stesse lettere nell'albero, Networkx ha scelto di metterne solo uno nella struttura finale (che è corretta) Ma ho bisogno di avere la struttura completa Come posso forzare l'aggiunta di Networkx nella struttura B: [D, C] ??

voglio precisa che facendo

>>> nx.dfs_successors(G,"B") 
{'B': ['C', 'D']} 

Quindi tutto è "internamente" corretto, è solo le dfs_successors che visualizza non nel modo in cui voglio.

Grazie

Answer 1

Prendendo il codice, il grafico non viene fuori come ci si aspetterebbe. Se lo fai:

import pylab as p 
import networkx as nx 

G = nx.Graph() 
G.add_edge("A","B") 
G.add_edge("A","H") 
G.add_edge("H","C") 
G.add_edge("B","C") 
G.add_edge("B","D") 

nx.draw(G) 
p.show() 

vedrete il vostro grafico come:

Ciò è dovuto alla logica della G.add_edge("A", "B"):

1. Se G ha nessun nodo di id "A", aggiungilo.
2. Se G ha nessun nodo di id "B", aggiungerlo.
3. Collegare "A" a "B" con un nuovo bordo.

Così, si crea solo cinque nodi, non sei come nella vostra immagine.

Modifica NetworkX può assumere qualsiasi hashable come valore per un nodo, e nel grafico che utilizza str (nodo) di etichettare ogni cerchio. Quindi possiamo semplicemente definire la nostra classe Node (che forse vorresti chiamare Server?) E dargli il comportamento desiderato.

import pylab as p 
import networkx as nx 


class Node(object): 
    nodes = [] 

    def __init__(self, label): 
     self._label = label 

    def __str__(self): 
     return self._label 

nodes = [Node(l) for l in ["A","B","C","C","D","H"]] 
edges = [(0,1),(0,5),(5,2),(1,3),(1,4)] 

G = nx.Graph() 
for i,j in edges: 
    G.add_edge(nodes[i], nodes[j]) 

nx.draw(G) 
p.show() 

ci dà e così quello che si voleva.

Answer 2

penso che quello che stai cercando è una sorta topologico http://networkx.github.com/documentation/latest/reference/generated/networkx.algorithms.dag.topological_sort.html

Questo funziona solo se si dispone di un (grafo orientato aciclico) DAG. Se è così è possibile disegnare l'albero si desidera anche - come questo:

import uuid 
import networkx as nx 
import matplotlib.pyplot as plt 
G = nx.DiGraph() 
G.add_edge("A","B") 
G.add_edge("A","H") 
G.add_edge("H","C") 
G.add_edge("B","C") 
G.add_edge("B","D") 

order = nx.topological_sort(G) 
print "topological sort" 
print order 

# build tree 
start = order[0] 
nodes = [order[0]] # start with first node in topological order 
labels = {} 
print "edges" 
tree = nx.Graph() 
while nodes: 
    source = nodes.pop() 
    labels[source] = source 
    for target in G.neighbors(source): 
     if target in tree: 
      t = uuid.uuid1() # new unique id 
     else: 
      t = target 
     labels[t] = target 
     tree.add_edge(source,t) 
     print source,target,source,t 
     nodes.append(target) 

nx.draw(tree,labels=labels) 
plt.show() 

Il disegno utilizza una mappatura un'etichetta per mappare gli id ​​del nodo per le etichette originali.