Darstellung von Graphen (Datenstruktur) in Python

104

Wie kann man ein Diagramm in Python übersichtlich darstellen ? (Von vorne anfangen, dh keine Bibliotheken!)
Welche Datenstruktur (z. B. dicts / tuples / dict (tuples)) ist schnell, aber auch speichereffizient?
Man muss in der Lage sein, verschiedene Grafikoperationen durchzuführen .

Wie bereits erwähnt, können die verschiedenen Diagrammdarstellungen hilfreich sein. Wie implementiert man sie in Python?

Was die Bibliotheken betrifft, hat diese Frage ziemlich gute Antworten.

shad0w_wa1k3r
quelle
1
Es gibt bereits viele Bibliotheken: graph-tool.skewed.de/performance , code.google.com/p/python-graph , networkx.github.io
Kassym Dorsel
1
Informationen zur Implementierung eines Diagramms finden Sie im Wikipedia-Artikel, in dem gängige Implementierungen und ihre Effizienz in
Bezug auf
Sie können GitHub.com/thePastor/pangaia ausprobieren. Es muss ein wenig umgeschrieben werden, um das Standarddiktat der Standardbibliothek zu verwenden (das beim Schreiben des Codes nicht veröffentlicht wurde). Es verwendet eine rekursive Datenstruktur, um es eleganter als andere Implementierungen zu machen.
TheDoctor
1
Für gerichtete Graphen schlägt dieser Aufsatz von python.org ein dictvon lists vor. Grundsätzlich so etwas wie {<parent>: [<child>, ...], ...}.
DJVG
Sie können die Verwendung des Wörterbuchs als Adjazenzliste mit Schlüsseln als Knoten und Werten als Liste benachbarter Knoten für jeden Schlüssel implementieren.
Shahrukh Khan

Antworten:

139

Obwohl dies eine etwas alte Frage ist, dachte ich, ich würde jedem, der darüber stolpert, eine praktische Antwort geben.

Angenommen, Sie erhalten Ihre Eingabedaten für Ihre Verbindungen als Liste von Tupeln wie folgt:

[('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'D'), ('E', 'F'), ('F', 'C')]

Die Datenstruktur, die ich für Diagramme in Python als am nützlichsten und effizientesten befunden habe, ist ein Diktat von Mengen . Dies wird die zugrunde liegende Struktur für unsere GraphKlasse sein. Sie müssen auch wissen, ob diese Verbindungen Bögen (gerichtet, in eine Richtung verbunden) oder Kanten (ungerichtet, in beide Richtungen verbunden) sind. Wir werden das behandeln, indem wir directedder Graph.__init__Methode einen Parameter hinzufügen . Wir werden auch einige andere hilfreiche Methoden hinzufügen.

import pprint
from collections import defaultdict


class Graph(object):
    """ Graph data structure, undirected by default. """

    def __init__(self, connections, directed=False):
        self._graph = defaultdict(set)
        self._directed = directed
        self.add_connections(connections)

    def add_connections(self, connections):
        """ Add connections (list of tuple pairs) to graph """

        for node1, node2 in connections:
            self.add(node1, node2)

    def add(self, node1, node2):
        """ Add connection between node1 and node2 """

        self._graph[node1].add(node2)
        if not self._directed:
            self._graph[node2].add(node1)

    def remove(self, node):
        """ Remove all references to node """

        for n, cxns in self._graph.items():  # python3: items(); python2: iteritems()
            try:
                cxns.remove(node)
            except KeyError:
                pass
        try:
            del self._graph[node]
        except KeyError:
            pass

    def is_connected(self, node1, node2):
        """ Is node1 directly connected to node2 """

        return node1 in self._graph and node2 in self._graph[node1]

    def find_path(self, node1, node2, path=[]):
        """ Find any path between node1 and node2 (may not be shortest) """

        path = path + [node1]
        if node1 == node2:
            return path
        if node1 not in self._graph:
            return None
        for node in self._graph[node1]:
            if node not in path:
                new_path = self.find_path(node, node2, path)
                if new_path:
                    return new_path
        return None

    def __str__(self):
        return '{}({})'.format(self.__class__.__name__, dict(self._graph))

Ich werde es als "Übung für den Leser" belassen, eine find_shortest_pathund andere Methoden zu erstellen .

Lassen Sie uns dies in Aktion sehen ...

>>> connections = [('A', 'B'), ('B', 'C'), ('B', 'D'),
                   ('C', 'D'), ('E', 'F'), ('F', 'C')]
>>> g = Graph(connections, directed=True)
>>> pretty_print = pprint.PrettyPrinter()
>>> pretty_print.pprint(g._graph)
{'A': {'B'},
 'B': {'D', 'C'},
 'C': {'D'},
 'E': {'F'},
 'F': {'C'}}

>>> g = Graph(connections)  # undirected
>>> pretty_print = pprint.PrettyPrinter()
>>> pretty_print.pprint(g._graph)
{'A': {'B'},
 'B': {'D', 'A', 'C'},
 'C': {'D', 'F', 'B'},
 'D': {'C', 'B'},
 'E': {'F'},
 'F': {'E', 'C'}}

>>> g.add('E', 'D')
>>> pretty_print.pprint(g._graph)
{'A': {'B'},
 'B': {'D', 'A', 'C'},
 'C': {'D', 'F', 'B'},
 'D': {'C', 'E', 'B'},
 'E': {'D', 'F'},
 'F': {'E', 'C'}}

>>> g.remove('A')
>>> pretty_print.pprint(g._graph)
{'B': {'D', 'C'},
 'C': {'D', 'F', 'B'},
 'D': {'C', 'E', 'B'},
 'E': {'D', 'F'},
 'F': {'E', 'C'}}

>>> g.add('G', 'B')
>>> pretty_print.pprint(g._graph)
{'B': {'D', 'G', 'C'},
 'C': {'D', 'F', 'B'},
 'D': {'C', 'E', 'B'},
 'E': {'D', 'F'},
 'F': {'E', 'C'},
 'G': {'B'}}

>>> g.find_path('G', 'E')
['G', 'B', 'D', 'C', 'F', 'E']
mVChr
quelle
6
Obwohl diese Frage sehr alt ist, denke ich, dass dies genau die Art von Antwort ist, die ich damals erwartet hatte. Das Beispiel hilft wirklich zu erklären, wie man die Implementierung gleichzeitig durchführen kann, um sie wirklich einfach zu halten. Man kann Implementierungen aus verschiedenen Open-Source-Bibliotheken finden, aber die Erklärung wäre nicht gleichwertig. Vielen Dank!
Shad0w_wa1k3r
2
Welche Art von Modifikation ist erforderlich, um den Kanten Gewicht zu verleihen?
Pshirishreddy
3
@pshirishreddy Interessante Frage! Ich hatte nicht darüber nachgedacht, aber mein Instinkt wäre, die heapqBibliothek zu verwenden, um Listen von Tupeln anstelle von Mengen zu häufen. Zum Beispiel wäre das Diagramm ein Diktat von Haufen wie: _graph = {'A': heapify([(0.3, 'D'), (0.5, 'B'), (0.75, 'A'), (0.9, 'C')])}(Hinweis: Sie würden dies nicht wirklich verwenden heapify, lesen Sie die Hilfe für die Bibliothek), dann könnten Sie die heapqFunktionen verwenden, um die gewichteten Kanten einzufügen und abzurufen.
MVChr
@mVChr das würde einen logzeitlichen Zugriff bedeuten . Aber wie kann man das Wörterbuch erweitern, mit dem Sie sowohl die Knoten-ID als auch das Gewicht zugeordnet haben?
Orezvani
Nett ! Die Funktion wird rekursiv aufgerufen. Dies scheint eine DFS zu sein, da sie die Knoten weiter erweitert. Für den kürzesten Pfad können wir die Länge der Pfade vergleichen und am Ende nur den kürzesten zurückgeben.
Jwalant Bhatt
36

NetworkX ist eine großartige Python- Grafikbibliothek . Es wird Ihnen schwer fallen, etwas zu finden, das Sie brauchen und das es noch nicht tut.

Und es ist Open Source, sodass Sie sehen können, wie sie ihre Algorithmen implementiert haben. Sie können auch zusätzliche Algorithmen hinzufügen.

https://github.com/networkx/networkx/tree/master/networkx/algorithms

jterrace
quelle
7
Deshalb ist NetworkX eine fantastische Ressource. Es ist Open Source, sodass Sie sehen können, wie sie ihre Algorithmen implementiert haben. Sie können auch zusätzliche Algorithmen hinzufügen.
Jterrace
2
Über 2000 Codezeilen für die graph.py --> class Graph. Und alles, was ich sehen möchte, ist, wie sie verwenden __iter__.
T. Woody
8

Erstens die Wahl der klassischen Liste vs. hängt Matrixdarstellungen vom Zweck ab (davon, was Sie mit der Darstellung tun möchten). Die bekannten Probleme und Algorithmen hängen mit der Wahl zusammen. Die Wahl der abstrakten Darstellung bestimmt, wie sie implementiert werden soll.

Zweitens stellt sich die Frage, ob die Eckpunkte und Kanten nur als Existenz ausgedrückt werden sollen oder ob sie zusätzliche Informationen enthalten.

Aus Sicht der in Python integrierten Datentypen wird jeder an anderer Stelle enthaltene Wert als (versteckter) Verweis auf das Zielobjekt ausgedrückt. Wenn es sich um eine Variable handelt (dh um eine benannte Referenz), werden der Name und die Referenz immer in einem (internen) Wörterbuch gespeichert. Wenn Sie keine Namen benötigen, kann die Referenz in Ihrem eigenen Container gespeichert werden - hier wird wahrscheinlich immer die Python-Liste für die Liste verwendet als Abstraktion verwendet.

Die Python-Liste ist als dynamisches Referenzarray implementiert. Das Python-Tupel ist als statisches Referenzarray mit konstantem Inhalt implementiert (der Wert der Referenzen kann nicht geändert werden). Aus diesem Grund können sie leicht indiziert werden. Auf diese Weise kann die Liste auch zur Implementierung von Matrizen verwendet werden.

Eine andere Möglichkeit, Matrizen darzustellen, sind die vom Standardmodul implementierten Arrays array - eingeschränkter in Bezug auf den gespeicherten Typ, homogener Wert. Die Elemente speichern den Wert direkt. (In der Liste werden stattdessen die Verweise auf die Wertobjekte gespeichert.) Auf diese Weise ist es speichereffizienter und auch der Zugriff auf den Wert ist schneller.

Manchmal finden Sie nützliche noch eingeschränktere Darstellung wie bytearray.

pepr
quelle
7

Es gibt zwei ausgezeichnete Graphbibliotheken NetworkX und igraph . Sie finden beide Bibliotheksquellcodes auf GitHub. Sie können immer sehen, wie die Funktionen geschrieben sind. Aber ich bevorzuge NetworkX, weil es leicht zu verstehen ist.
Sehen Sie sich ihre Codes an, um zu erfahren, wie sie die Funktionen ausführen. Sie erhalten mehrere Ideen und können dann auswählen, wie Sie mithilfe von Datenstrukturen ein Diagramm erstellen möchten.

Vineet Jain
quelle