Fehler mit networx.descendants() wenn Knoten Tags haben

Question

Ich benutze networkx mit Python 3.4, und ich bekomme einen seltsamen Fehler, wenn ich versuche, die erreichbaren Knoten zu finden. Ich denke, es hat etwas mit einer optionalen Eigenschaft der Knoten zu tun, die ich vorher gesetzt habe. Dieser minimale Code repliziert den Fehler:

import networkx as nx 

G = nx.Graph() 
nodes = ["A", "B", "C", "D", "E"]          
G.add_nodes_from(nodes)             
G.add_edge("A", "B") 
G.add_edge("A", "C")             
G.add_edge("A", "D")             
G.add_edge("B", "E") 

for node in nodes : 
     G[node]['occurrences'] = 1          

print("Now computing nodes reachable from \"A\"...") 
reachableNodes = nx.descendants(G, "A")         
print("List of reachable nodes:", reachableNodes) 

Die Ausgabe lautet:

Now computing nodes reachable from "A"... 
Traceback (most recent call last): 
    File "exampleStackOverflow.py", line 17, in <module> 
    reachableNodes = nx.descendants(G, "A") 
    File "/usr/local/lib/python3.4/dist-packages/networkx/algorithms/dag.py", line 42, in descendants 
    des = set(nx.shortest_path_length(G, source=source).keys()) - set([source]) 
    File "/usr/local/lib/python3.4/dist-packages/networkx/algorithms/shortest_paths/generic.py", line 239, in shortest_path_length 
    paths=nx.single_source_shortest_path_length(G,source) 
    File "/usr/local/lib/python3.4/dist-packages/networkx/algorithms/shortest_paths/unweighted.py", line 63, in single_source_shortest_path_length 
    nextlevel.update(G[v]) # add neighbors of v 
    File "/usr/local/lib/python3.4/dist-packages/networkx/classes/graph.py", line 407, in __getitem__ 
    return self.adj[n] 
KeyError: 'occurrences' 

Nun, wenn ich die Zeilen kommentieren, wenn ich den Tag ‚Ereignisse‘ gesetzt, ich habe das erwartete Ergebnis:

Now computing nodes reachable from "A"... 
List of reachable nodes: {'B', 'D', 'C', 'E'} 

Mache ich etwas falsch?

Answer 1

@ Gerrats Ansatz mit einer benutzerdefinierten Knoten-Klasse funktioniert. Die empfohlene Methode ist jedoch die Verwendung von G.node zum Speichern von Knotendaten. Du hast es fast richtig verstanden. Dies ist das Problem Code

for node in nodes : 
    G[node]['occurrences'] = 1 # INCORRECT, corrupts data structure 

for node in nodes : 
    G.node[node]['occurrences'] = 1 # CORRECT 

Arbeitsbeispiel

import networkx as nx 

G = nx.Graph() 
nodes = ["A", "B", "C", "D", "E"] 
G.add_nodes_from(nodes) 
G.add_edge("A", "B") 
G.add_edge("A", "C") 
G.add_edge("A", "D") 
G.add_edge("B", "E") 

for n in nodes : 
     G.node[n]['occurrences'] = 1 

print("Now computing nodes reachable from \"A\"...") 
reachableNodes = nx.descendants(G, "A") 
print("List of reachable nodes:", reachableNodes) 

for n in reachableNodes: 
    print n,G.node[n] 


#OUTPUT 
Now computing nodes reachable from "A"... 
('List of reachable nodes:', set(['C', 'B', 'E', 'D'])) 
C {'occurrences': 1} 
B {'occurrences': 1} 
E {'occurrences': 1} 
D {'occurrences': 1} 

Es gibt weitere Informationen auf, wie https://networkx.readthedocs.org/en/stable/tutorial/tutorial.html#adding-attributes-to-graphs-nodes-and-edges Graphen einzustellen, wird der Knoten, und Kanten Attributen.

Answer 2

Wenn Sie untersuchen, was ein Knoten ein wenig näher ist:

for node in nodes : 
    print(node, type(G[node]), G[node].keys()) 

Sie erhalten:

('A', <type 'dict'>, ['C', 'B', 'D']) 
('B', <type 'dict'>, ['A', 'E']) 
('C', <type 'dict'>, ['A']) 
('D', <type 'dict'>, ['A']) 
('E', <type 'dict'>, ['B']) 

Sie können sehen, dass G[node] ein Wörterbuch mit Schlüssel ist zu anderen Knoten entspricht, teilt eine Kante mit. Sie umgehen die normale Node-Erstellungsroutine und fügen einen Knoten mit der Bezeichnung occurrences in den Mix ein, der durch einen Edge-Knoten verbunden ist. Der Grund, warum ich trying to sage, ist, dass dieser Knoten nicht richtig eingerichtet ist und nicht korrekt funktioniert, wenn er auf diese Weise hinzugefügt wird.

Wenn Sie zusätzliche Eigenschaften auf Ihrem Knoten speichern möchten, könnten Sie eine Node-Klasse-Setup, zum Beispiel:

class Node(object): 
    def __init__(self, letter): 
     self.letter = letter 

    def __str__(self): 
     return self.letter 

... dann:

nodes = [Node(l) for l in ["A", "B", "C", "D", "E"]] 

Sie können nun jede Eigenschaft anhängen Sie mögen diese Knoten (aber nicht zu G[node]).