graphlib — Funktionalität zur Arbeit mit grafenähnlichen Strukturen

Quellcode: Lib/graphlib.py

class graphlib.TopologicalSorter(graph=None)

Bietet Funktionalität zum topologischen Sortieren eines Graphen von hashbaren Knoten.

Eine topologische Reihenfolge ist eine lineare Anordnung der Knoten in einem Graphen, so dass für jede gerichtete Kante u -> v von Knoten u zu Knoten v der Knoten u in der Anordnung vor dem Knoten v kommt. Beispielsweise können die Knoten des Graphen Aufgaben darstellen, die ausgeführt werden müssen, und die Kanten können Einschränkungen darstellen, dass eine Aufgabe vor einer anderen ausgeführt werden muss; in diesem Beispiel ist eine topologische Anordnung lediglich eine gültige Reihenfolge für die Aufgaben. Eine vollständige topologische Anordnung ist genau dann möglich, wenn der Graph keine gerichteten Zyklen aufweist, d.h. wenn er ein gerichteter azyklischer Graph (DAG) ist.

Wenn das optionale Argument graph bereitgestellt wird, muss es ein Dictionary sein, das einen gerichteten azyklischen Graphen darstellt, bei dem die Schlüssel Knoten sind und die Werte Iterables aller Vorgänger dieses Knotens im Graphen sind (die Knoten, die Kanten haben, die auf den Wert im Schlüssel zeigen). Zusätzliche Knoten können dem Graphen mit der Methode add() hinzugefügt werden.

Im allgemeinen Fall sind die Schritte zur Durchführung der Sortierung eines gegebenen Graphen wie folgt:

  • Erstellen Sie eine Instanz von TopologicalSorter mit einem optionalen initialen Graphen.

  • Fügen Sie dem Graphen zusätzliche Knoten hinzu.

  • Rufen Sie prepare() für den Graphen auf.

  • Solange is_active() True ist, iterieren Sie über die von get_ready() zurückgegebenen Knoten und verarbeiten Sie sie. Rufen Sie done() für jeden Knoten auf, sobald dessen Verarbeitung abgeschlossen ist.

Falls nur eine sofortige Sortierung der Knoten im Graphen erforderlich ist und keine Parallelverarbeitung beteiligt ist, kann die Komfortmethode TopologicalSorter.static_order() direkt verwendet werden.

>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
>>> ts = TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'C', 'B', 'D')

Die Klasse ist so konzipiert, dass sie die Parallelverarbeitung von Knoten, sobald diese verfügbar werden, einfach unterstützt. Zum Beispiel:

topological_sorter = TopologicalSorter()

# Add nodes to 'topological_sorter'...

topological_sorter.prepare()
while topological_sorter.is_active():
    for node in topological_sorter.get_ready():
        # Worker threads or processes take nodes to work on off the
        # 'task_queue' queue.
        task_queue.put(node)

    # When the work for a node is done, workers put the node in
    # 'finalized_tasks_queue' so we can get more nodes to work on.
    # The definition of 'is_active()' guarantees that, at this point, at
    # least one node has been placed on 'task_queue' that hasn't yet
    # been passed to 'done()', so this blocking 'get()' must (eventually)
    # succeed.  After calling 'done()', we loop back to call 'get_ready()'
    # again, so put newly freed nodes on 'task_queue' as soon as
    # logically possible.
    node = finalized_tasks_queue.get()
    topological_sorter.done(node)
add(node, *predecessors)

Fügt einen neuen Knoten und seine Vorgänger zum Graphen hinzu. Sowohl node als auch alle Elemente in predecessors müssen hashbar sein.

Wenn die Methode mehrmals mit demselben Knotenargument aufgerufen wird, ist die Menge der Abhängigkeiten die Vereinigung aller übergebenen Abhängigkeiten.

Es ist möglich, einen Knoten ohne Abhängigkeiten hinzuzufügen (predecessors wird nicht bereitgestellt) oder eine Abhängigkeit doppelt anzugeben. Wenn ein Knoten, der zuvor nicht angegeben wurde, unter predecessors enthalten ist, wird er automatisch zum Graphen hinzugefügt, ohne eigene Vorgänger.

Löst ValueError aus, wenn sie nach dem Aufruf von prepare() aufgerufen wird.

prepare()

Markiert den Graphen als abgeschlossen und prüft auf Zyklen im Graphen. Wenn ein Zyklus erkannt wird, wird CycleError ausgelöst, aber get_ready() kann immer noch verwendet werden, um so viele Knoten wie möglich zu erhalten, bis Zyklen weiteren Fortschritt blockieren. Nach einem Aufruf dieser Funktion kann der Graph nicht mehr geändert werden, und daher können keine weiteren Knoten mit add() hinzugefügt werden.

Ein ValueError wird ausgelöst, wenn die Sortierung durch static_order() oder get_ready() gestartet wurde.

Geändert in Version 3.14: prepare() kann jetzt mehr als einmal aufgerufen werden, solange die Sortierung nicht begonnen hat. Zuvor löste dies ValueError aus.

is_active()

Gibt True zurück, wenn weiterer Fortschritt erzielt werden kann, und False andernfalls. Fortschritt kann erzielt werden, wenn Zyklen die Auflösung nicht blockieren und entweder noch Knoten bereit sind, die noch nicht von TopologicalSorter.get_ready() zurückgegeben wurden, oder die Anzahl der als TopologicalSorter.done() markierten Knoten kleiner ist als die Anzahl, die von TopologicalSorter.get_ready() zurückgegeben wurde.

Die Methode __bool__() dieser Klasse leitet zu dieser Funktion um, so dass anstelle von

if ts.is_active():
    ...

kann einfach Folgendes getan werden:

if ts:
    ...

Löst ValueError aus, wenn sie ohne vorherigen Aufruf von prepare() aufgerufen wird.

done(*nodes)

Markiert eine Menge von Knoten, die von TopologicalSorter.get_ready() zurückgegeben wurden, als verarbeitet und gibt damit alle Nachfolger jedes Knotens in nodes frei, damit sie zukünftig von einem Aufruf von TopologicalSorter.get_ready() zurückgegeben werden können.

Löst ValueError aus, wenn ein Knoten in nodes bereits durch einen früheren Aufruf dieser Methode als verarbeitet markiert wurde oder wenn ein Knoten nicht mit TopologicalSorter.add() zum Graphen hinzugefügt wurde, wenn die Methode ohne Aufruf von prepare() aufgerufen wurde oder wenn der Knoten noch nicht von get_ready() zurückgegeben wurde.

get_ready()

Gibt ein tuple mit allen Knoten zurück, die bereit sind. Anfänglich gibt sie alle Knoten ohne Vorgänger zurück, und sobald diese durch Aufruf von TopologicalSorter.done() als verarbeitet markiert sind, geben nachfolgende Aufrufe alle neuen Knoten zurück, deren Vorgänger bereits verarbeitet sind. Sobald kein weiterer Fortschritt mehr möglich ist, werden leere Tupel zurückgegeben.

Löst ValueError aus, wenn sie ohne vorherigen Aufruf von prepare() aufgerufen wird.

static_order()

Gibt ein Iteratorobjekt zurück, das über die Knoten in topologischer Reihenfolge iteriert. Bei Verwendung dieser Methode sollten prepare() und done() nicht aufgerufen werden. Diese Methode ist äquivalent zu

def static_order(self):
    self.prepare()
    while self.is_active():
        node_group = self.get_ready()
        yield from node_group
        self.done(*node_group)

Die spezifische Reihenfolge, die zurückgegeben wird, kann von der spezifischen Reihenfolge abhängen, in der die Elemente in den Graphen eingefügt wurden. Zum Beispiel:

>>> ts = TopologicalSorter()
>>> ts.add(3, 2, 1)
>>> ts.add(1, 0)
>>> print([*ts.static_order()])
[2, 0, 1, 3]

>>> ts2 = TopologicalSorter()
>>> ts2.add(1, 0)
>>> ts2.add(3, 2, 1)
>>> print([*ts2.static_order()])
[0, 2, 1, 3]

Dies liegt daran, dass "0" und "2" auf derselben Ebene im Graphen liegen (sie wären im selben Aufruf von get_ready() zurückgegeben worden) und die Reihenfolge zwischen ihnen durch die Einfügungsreihenfolge bestimmt wird.

Wenn ein Zyklus erkannt wird, wird CycleError ausgelöst.

Hinzugefügt in Version 3.9.

Ausnahmen

Das Modul graphlib definiert die folgenden Ausnahmeklassen:

exception graphlib.CycleError

Unterklasse von ValueError, ausgelöst von TopologicalSorter.prepare(), wenn Zyklen im Arbeitsgraphen vorhanden sind. Wenn mehrere Zyklen vorhanden sind, wird nur eine undefinierte Wahl unter ihnen gemeldet und in die Ausnahme aufgenommen.

Der erkannte Zyklus kann über das zweite Element des Attributs args der Ausnahmeinstanz abgerufen werden und besteht aus einer Liste von Knoten, so dass jeder Knoten im Graphen ein direkter Vorgänger des nächsten Knotens in der Liste ist. In der gemeldeten Liste sind der erste und der letzte Knoten gleich, um klarzustellen, dass es sich um einen Zyklus handelt.