graphlib — Funktionalitet för att arbeta med graf-liknande strukturer

Källkod: Lib/graphlib.py

class graphlib.TopologicalSorter(graph=None)

Tillhandahåller funktionalitet för att topologiskt sortera en graf med hashable-noder.

En topologisk ordning är en linjär ordning av hörnen i en graf så att för varje riktad kant u -> v från hörn u till hörn v kommer hörn u före hörn v i ordningen. Exempelvis kan topparna i grafen representera uppgifter som ska utföras och kanterna kan representera begränsningar som innebär att en uppgift måste utföras före en annan; i det här exemplet är en topologisk ordning bara en giltig sekvens för uppgifterna. En fullständig topologisk ordning är möjlig om och endast om grafen inte har några riktade cykler, det vill säga om den är en riktad acyklisk graf.

Om det valfria argumentet graph anges måste det vara en ordbok som representerar en riktad acyklisk graf där nycklarna är noder och värdena är iterabler av alla föregångare till den noden i grafen (de noder som har kanter som pekar på värdet i nyckeln). Ytterligare noder kan läggas till i grafen med hjälp av metoden add().

I det allmänna fallet är de steg som krävs för att utföra sorteringen av en given graf följande:

  • Skapa en instans av TopologicalSorter med en valfri initial graf.

  • Lägg till ytterligare noder i grafen.

  • Anropa prepare() på grafen.

  • Medan is_active() är True, iterera över de noder som returneras av get_ready() och bearbeta dem. Anropa done() på varje nod när den är färdigbehandlad.

Om det bara krävs en omedelbar sortering av noderna i grafen och ingen parallellism är inblandad, kan bekvämlighetsmetoden TopologicalSorter.static_order() användas direkt:

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

Klassen är utformad för att enkelt stödja parallell bearbetning av noderna när de blir klara. Till exempel:

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)

Lägger till en ny nod och dess föregångare i grafen. Både node och alla element i predecessors måste vara hashable.

Om den anropas flera gånger med samma nodargument kommer uppsättningen beroenden att vara en sammanslagning av alla beroenden som skickats in.

Det är möjligt att lägga till en nod utan beroenden (predecessors anges inte) eller att ange ett beroende två gånger. Om en nod som inte har tillhandahållits tidigare ingår bland predecessors kommer den automatiskt att läggas till i grafen utan egna predecessors.

Utlöser ValueError om den anropas efter prepare().

prepare()

Markera grafen som färdig och kontrollera om det finns cykler i grafen. Om någon cykel upptäcks kommer CycleError att anges, men get_ready() kan fortfarande användas för att få så många noder som möjligt tills cyklerna blockerar mer framsteg. Efter ett anrop till denna funktion kan grafen inte modifieras och därför kan inga fler noder läggas till med add().

Ett ValueError kommer att uppstå om sorteringen har startats av static_order() eller get_ready().

Ändrad i version 3.14: prepare() kan nu anropas mer än en gång så länge som sorteringen inte har startat. Tidigare gav detta upphov till ValueError.

is_active()

Returnerar True om fler framsteg kan göras och False annars. Framsteg kan göras om cykler inte blockerar upplösningen och antingen finns det fortfarande noder redo som ännu inte har returnerats av TopologicalSorter.get_ready() eller så är antalet noder som markerats med TopologicalSorter.done() mindre än antalet som har returnerats av TopologicalSorter.get_ready().

Metoden __bool__() i denna klass defererar till denna funktion, så istället för:

om ts.is_active():
    ...

är det möjligt att helt enkelt göra:

om ts:
    ...

Utlöser ValueError om den anropas utan att tidigare ha anropat prepare().

done(*nodes)

Markerar en uppsättning noder som returnerats av TopologicalSorter.get_ready() som bearbetade, vilket frigör eventuella efterföljare till varje nod i nodes för att returneras i framtiden genom ett anrop till TopologicalSorter.get_ready().

Utlöser ValueError om någon nod i nodes redan har markerats som bearbetad av ett tidigare anrop till denna metod eller om en nod inte lades till i grafen med hjälp av TopologicalSorter.add(), om den anropades utan anrop till prepare() eller om noden ännu inte har returnerats av get_ready().

get_ready()

Returnerar en tuple med alla noder som är klara. Initialt returneras alla noder utan föregångare, och när dessa har markerats som bearbetade genom att anropa TopologicalSorter.done(), kommer ytterligare anrop att returnera alla nya noder som har alla sina föregångare redan bearbetade. När inga fler framsteg kan göras returneras tomma tupler.

Utlöser ValueError om den anropas utan att tidigare ha anropat prepare().

static_order()

Returnerar ett iteratorobjekt som itererar över noder i en topologisk ordning. När denna metod används ska prepare() och done() inte anropas. Denna metod är likvärdig med:

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

Den särskilda ordning som returneras kan bero på den särskilda ordning i vilken posterna infogades i grafen. Till exempel:

>>> 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]

Detta beror på att ”0” och ”2” befinner sig på samma nivå i grafen (de skulle ha returnerats i samma anrop till get_ready()) och ordningen mellan dem bestäms av den ordning i vilken de infogades.

Om någon cykel upptäcks kommer CycleError att tas upp.

Tillagd i version 3.9.

Undantag

Modulen graphlib definierar följande undantagsklasser:

exception graphlib.CycleError

Underklass till ValueError som orsakas av TopologicalSorter.prepare() om det finns cykler i arbetsgrafen. Om flera cykler finns, kommer endast ett odefinierat val bland dem att rapporteras och inkluderas i undantaget.

Den upptäckta cykeln kan nås via det andra elementet i attributet args i undantagsinstansen och består av en lista med noder, så att varje nod i grafen är en omedelbar föregångare till nästa nod i listan. I den rapporterade listan kommer den första och den sista noden att vara desamma, för att klargöra att den är cyklisk.