Getötet: 9 Erstellen eines Graphen aus einer Liste von Knoten und einer Liste von Links

Question

Ich verwende iGraph, um ein Netzwerk aus einer Liste von nodes und einer Liste von links aufzubauen. Es gibt 200.000 Knoten und 450.000 Links. Für jeden node gibt es einige zugehörige Metadaten und für jeden link das gleiche.

Die Knotenliste sieht wie folgt aus:

[{u'toid': u'osgb4000000031043205', u'index': 1, u'point': [508180.748, 195333.973]}, {u'toid': u'osgb4000000031043206', u'index': 2, u'point': [508163.122, 195316.627]}, {u'toid': u'osgb4000000031043207', u'index': 3, u'point': [508172.075, 195325.719]}, {u'toid': u'osgb4000000031043208', u'index': 4, u'point': [508513, 196023]}] 

Die links Liste sieht wie folgt aus:

[{u'index': 1, u'term': u'Private Road - Restricted Access', u'nature': u'Single Carriageway', u'negativeNode': u'osgb4000000023183407', u'toid': u'osgb4000000023296573', u'polyline': [492019.481, 156567.076, 492028, 156567, 492041.667, 156570.536, 492063.65, 156578.067, 492126.5, 156602], u'positiveNode': u'osgb4000000023183409'}, {u'index': 2, u'term': u'Private Road - Restricted Access', u'nature': u'Single Carriageway', u'negativeNode': u'osgb4000000023763485', u'toid': u'osgb4000000023296574', u'polyline': [492144.493, 156762.059, 492149.35, 156750, 492195.75, 156630], u'positiveNode': u'osgb4000000023183408'}, {u'index': 3, u'term': u'Private Road - Restricted Access', u'nature': u'Single Carriageway', u'negativeNode': u'osgb4000000023183650', u'toid': u'osgb4000000023296638', u'polyline': [492835.25, 156873.5, 493000, 156923, 493018.061, 156927.938], u'positiveNode': u'osgb4000000023183652'}, {u'index': 4, u'term': u'Local Street', u'nature': u'Single Carriageway', u'negativeNode': u'osgb4000000023181163', u'toid': u'osgb4000000023388466', u'polyline': [498136.506, 149148.313, 498123.784, 149143.969, 498119.223, 149143.411, 498116.43, 149143.318, 498113.638, 149145.179], u'positiveNode': u'osgb4000000023806248'}] 

ich versuche, um die Grafik zu bauen:

g = Graph() 

# Add nodes (and associated data) 
for node in nodes: 
    g.add_vertices(node['toid']) 
# Add links (and associated data) 
for link in links: 
    g.add_edges([(link['negativeNode'],link['positiveNode'])]) 

Die Links-Datei enthält eine kleine Anzahl von Fällen, in denen ein negativer Knoten oder ein positiver Knoten in der Knotenliste nicht gefunden wird. Als solche führt IGRAPH den folgenden Fehler:

ValueError: no such vertex: u'osgb4000000019779815' 

ich die nodes aus der Link-Datei hinzuzufügen versucht, die nicht in der Liste nodes noch nicht gab.

for node in nodes: 
    for link in links: 
     if link['negativeNode'] not in node['toid']: 
      missing_dict = { 
      "toid": link['negativeNode'] 
      } 
      nodes.append(missing_dict) 
     if link['positiveNode'] not in node['toid']: 
      missing_dict = { 
      "toid": link['negativeNode'] 
      } 
      nodes.append(missing_dict) 

Dies führte jedoch in dem folgenden Fehler:

Killed: 9 

Ich glaube, der Prozess zu viel Speicher verwendet hat. Wie soll ich das korrigieren?

Answer 1

Zunächst würde Ihr zweiter Versuch versuchen, den gleichen Link mehrmals hinzuzufügen; Im schlimmsten Fall kann die letzte Verbindung in Ihrem links Vektor so oft hinzugefügt werden, wie Knoten im Vektor nodes vorhanden sind. Also, dieser Ansatz wird nicht funktionieren.

Zweitens ist igigraph nicht sehr effizient, wenn Sie Knoten oder Kanten einzeln hinzufügen (aufgrund der Indexierungsoperation, die nach jedem Hinzufügen oder Entfernen eines Knotens ausgeführt wird). Es ist am besten, sie in "Stapeln" hinzuzufügen, d. H. Mehrere Knoten oder Kanten zum Hinzufügen vorzubereiten und sie dann auf einmal mit einem einzigen Aufruf zu add_vertices() oder add_edges() hinzuzufügen. Die Methode Graph.DictList() ist drittens explizit für Ihren Zweck entwickelt: Sie benötigt zwei Listen von Wörterbüchern, eine für die Knoten und eine für die Kanten, und erstellt dann aus ihnen eine Grafik, vorausgesetzt Sie sagen ihr, welche Mitglieder von das Wörterbuch speichern die Vertex-Namen und die Endpunkte der Kanten:

g = Graph.DictList(vertices=nodes, edges=links, vertex_name_attr="toid", edge_foreign_keys=("positiveNode", "negativeNode") 

alles, was Sie benötigen, um sicherzustellen, bevor Graph.DictList() Aufruf ist, dass alle Knoten, die in der Kantenliste auftreten, werden in der Knotenliste gefunden:

all_node_ids = set(edge["positiveNode"] for edge in links) | set(edge["negativeNode"] for edge in links) 
known_node_ids = set(node["toid"] for node in nodes) 
for node in all_node_ids - known_node_ids: 
    nodes.append({u'toid': node})