Was ist die effizienteste Graphdatenstruktur in Python?

stimmen
63

Ich muss in der Lage , eine große zu manipulieren (10 ^ 7 Knoten) Graphen in Python. Die Daten werden an jedem Knoten / Kante entspricht , ist minimal, sagen wir, eine kleine Anzahl von Strings. Was ist der effizienteste in Bezug auf Speicher und Geschwindigkeit , Art und Weise , dies zu tun?

Ein dict von dicts ist flexibler und einfacher zu implementieren, aber ich erwarte, intuitiv eine Liste von Listen, schneller zu sein. Die Liste Option würde auch verlangen, dass ich immer die Daten aus der Struktur zu trennen, während dicts für etwas Derartiges erlauben würde:

graph[I][J][Property]=value

Was würdest du vorschlagen?


Ja, ich hätte etwas klarer sein auf das, was ich von Effizienz bedeuten. In diesem speziellen Fall meine ich es in Bezug auf den Random Access Retrieval.

die Daten in dem Speicher zu laden ist kein großes Problem. Das ist ein für allemal erledigt. Die zeitraubende Teil ist den Besuch der Knoten, damit ich die Informationen extrahieren und die Metriken messen mich interessiert.

Ich hatte als nicht jeder Knoten eine Klasse zu machen (Eigenschaften sind die gleichen für alle Knoten), aber es scheint so, dass eine zusätzliche Schicht von Overhead hinzufügen würde? Ich hatte gehofft, jemand etwas direkte Erfahrung mit einem ähnlichen Fall haben würde, die sie teilen könnten. Immerhin Graphen sind eine der häufigsten Abstraktionen in CS.

Veröffentlicht am 04/08/2008 um 13:00
quelle vom benutzer
In anderen Sprachen...                            


7 antworten

stimmen
51

Ich würde stark befürworten Sie betrachten NetworkX . Es ist ein kampferprobter Schlachtross und das erste Werkzeug , die meisten ‚Forschung‘ Typen greifen nach , wenn sie benötigen Analyse von Netzwerk - basierten Daten zu tun. Ich habe Diagramme mit 100s von Tausenden von Kanten ohne Problem auf einem Notebook manipuliert. Seine Eigenschaft reiche und sehr einfach zu bedienen. Sie finden sich mehr auf das Problem bei der Hand konzentrieren , anstatt die Details in der zugrunde liegenden Implementierung.

Beispiel Erdős-Rényi Zufallsgraphen Erzeugung und Analyse


"""
Create an G{n,m} random graph with n nodes and m edges
and report some properties.

This graph is sometimes called the Erd##[m~Qs-Rényi graph
but is different from G{n,p} or binomial_graph which is also
sometimes called the Erd##[m~Qs-Rényi graph.
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
__credits__ = """"""
#    Copyright (C) 2004-2006 by 
#    Aric Hagberg 
#    Dan Schult 
#    Pieter Swart 
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html

from networkx import *
import sys

n=10 # 10 nodes
m=20 # 20 edges

G=gnm_random_graph(n,m)

# some properties
print "node degree clustering"
for v in nodes(G):
    print v,degree(G,v),clustering(G,v)

# print the adjacency list to terminal 
write_adjlist(G,sys.stdout)

Visualisierungen sind auch ganz einfach:

Geben Sie hier image description

Mehr Visualisierung: http://jonschull.blogspot.com/2008/08/graph-visualization.html

Beantwortet am 26/08/2008 um 18:43
quelle vom benutzer

stimmen
12

Auch wenn diese Frage jetzt schon recht alt ist, ich denke , es lohnt sich , mein eigenes Python - Modul für Graph Manipulation genannt zu erwähnen Graph-Tool . Es ist sehr effizient, da die Datenstrukturen und Algorithmen in C ++ implementiert sind, mit Vorlage metaprograming, die Boost - Graph - Bibliothek verwenden. Daher seine Leistung (sowohl in der Speichernutzung und Laufzeit) ist vergleichbar mit einer reinen C ++ Bibliothek und kann um Größenordnungen besser als die typischen Python - Code, ohne Benutzerfreundlichkeit zu opfern. Ich benutze es , mich ständig mit sehr großen Graphen zu arbeiten.

Beantwortet am 27/11/2010 um 15:10
quelle vom benutzer

stimmen
6

Wie bereits erwähnt, ist NetworkX sehr gut, mit einer anderen Option zu sein IGRAPH . Beide Module haben die meisten (wenn nicht alle) die Analyse Tools , die Sie voraussichtlich benötigen sind, und beide Bibliotheken werden routinemäßig mit großen Netzwerken verwendet.

Beantwortet am 27/08/2008 um 11:01
quelle vom benutzer

stimmen
4

Ein Wörterbuch kann auch Overhead enthalten, abhängig von der tatsächlichen Umsetzung. Eine Hash-Tabelle in der Regel eine gewisse Primzahl der verfügbaren Knoten enthalten zu beginnen, auch wenn Sie nur ein paar der Knoten verwenden können.

Gemessen an Ihrem Beispiel „Eigentum“, würden Sie besser sein mit einem Class-Ansatz für die letzte Stufe und reale Eigenschaften? Oder ist der Name der Eigenschaften viel von Knoten Knoten zu ändern?

Ich würde sagen, dass das, was „effizient“ Mittel auf eine Menge Dinge abhängt, wie:

  • Geschwindigkeit von Updates (Einfügen, Aktualisieren, Löschen)
  • Geschwindigkeit von Random Access Retrieval
  • Geschwindigkeit der sequentiellen Abruf
  • Speicher verwendet

Ich denke, dass Sie werden feststellen, dass eine Datenstruktur, die schnelle wird in der Regel mehr Speicher verbrauchen als eine, die langsam ist. Dies ist nicht immer der Fall, aber die meisten Datenstrukturen scheinen dies zu folgen.

Ein Wörterbuch könnte sein, einfach zu bedienen, und geben Sie relativ gleichmäßig schnellen Zugriff, wird es wahrscheinlich mehr Speicher, als, wie Sie vorschlagen, Listen. Listen, neigen jedoch dazu, im Allgemeinen mehr Aufwand enthalten, wenn Sie Daten in sie einfügen, es sei denn, sie X Knoten preallocate, in dem sie wieder mehr Speicherplatz.

Mein Vorschlag in der Regel wäre nur um die Methode zu verwenden, die die natürlichste Sie scheint, und dann einen „Stresstest“ des Systems zu tun, eine erhebliche Menge an Daten, die ihn das Hinzufügen und sehen, ob es ein Problem wird.

Sie könnten auch erwägen eine Abstraktionsschicht zu Ihrem System hinzufügen, so dass Sie die Programmierschnittstelle nicht später benötigen, wenn Sie ändern müssen, um die interne Datenstruktur zu ändern.

Beantwortet am 04/08/2008 um 13:09
quelle vom benutzer

stimmen
3

Wie ich es, einen Direktzugriffs verstehe für beide Python dicts und Listen in konstanter Zeit ist, ist der Unterschied, dass Sie nur mit wahlfreiem Zugriff von Integer-Indizes mit Listen tun. Ich gehe davon aus, dass Sie einen Knoten, der durch das Etikett zum Nachschlagen benötigen, so dass Sie wollen ein dict von dicts.

Doch auf der Performance vorne in den Speicher geladen kann kein Problem sein, aber wenn Sie zu viel verwenden, werden Sie auf die Festplatte am Ende tauschen, die die Leistung sogar Python hocheffiziente dicts töten. Versuchen Sie, die Speicherauslastung niedrig halten, so viel wie möglich. Auch RAM ist erstaunlich günstig im Augenblick; Wenn Sie diese Art der Sache viel zu tun, gibt es keinen Grund, nicht zu mindestens 4 GB zu haben.

Wenn Sie Rat Speichernutzung möchten sich auf zu halten, geben mehr Informationen über die Art von Informationen für jeden Knoten sind Tracking Sie.

Beantwortet am 06/08/2008 um 06:37
quelle vom benutzer

stimmen
2

würde eine klassenbasierte Struktur macht wahrscheinlich mehr Aufwand als die dict-basierte Struktur, da in Python Klassen tatsächlich dicts verwenden, wenn sie umgesetzt werden.

Beantwortet am 04/08/2008 um 13:41
quelle vom benutzer

stimmen
1

Kein Zweifel NetworkX ist die beste Datenstruktur bis jetzt für Graphen. Es kommt mit Utilities wie Hilfsfunktionen, Datenstrukturen und Algorithmen, Zufallsfolgengeneratoren, Dekorateure, Cuthill-McKee-Bestellung, Context Manager

NetworkX ist groß, weil es für Graphen wowrs, Digraphe und Multigraphen. Adjazenzliste, mehrzeilige Adjazenzliste, Kantenliste, GEXF, GML: Es kann Graphen mit mehreren Möglichkeiten, schreiben. Es arbeitet mit Pickle, GraphML, JSON, SparseGraph6 usw.

Es hat implimentation verschiedene radimade Algorithmen einschließlich: Angleichung, Bipartite, Begrenzung, Zentralität, Clique, Clustering, Färbung, Komponenten, Verbindungen, Cycles, Directed azyklische Graphen, Abstandsmaß, dominierende Mengen, Eulersche, Isomorphie, Link-Analyse, Link-Prediction, Passende , Minimum Spanning Tree, Reich-Club, Kürzeste Wege, Traversal, Baum.

Beantwortet am 18/01/2016 um 09:08
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more