Topologische Sortierung - Topological sorting

In der Informatik , eine topologische Sortierung oder topologischen Anordnung eines gerichteten Graphen eine lineare Ordnung ihrer Eckpunkte , so dass für jede gerichtete Kante uv von Vertex u zu Eckpunkt v , u vor kommt v in der Reihenfolge. Zum Beispiel können die Scheitelpunkte des Graphen auszuführende Aufgaben darstellen, und die Kanten können Beschränkungen darstellen, dass eine Aufgabe vor einer anderen ausgeführt werden muss; in dieser Anwendung ist eine topologische Ordnung nur eine gültige Reihenfolge für die Aufgaben. Genau genommen ist eine topologische Sortierung eine Graphendurchquerung, bei der jeder Knoten v erst besucht wird, nachdem alle seine Abhängigkeiten besucht wurden . Eine topologische Ordnung ist genau dann möglich, wenn der Graph keine gerichteten Zyklen hat , also ein gerichteter azyklischer Graph (DAG) ist. Jeder DAG hat mindestens eine topologische Ordnung, und es sind Algorithmen zum Konstruieren einer topologischen Ordnung eines beliebigen DAG in linearer Zeit bekannt . Topologisches Sortieren hat viele Anwendungen, insbesondere bei Rangordnungsproblemen, wie z. B. Feedback-Arc-Sets . Eine topologische Sortierung ist auch dann möglich, wenn der DAG getrennte Komponenten hat .

Beispiele

Die kanonische Anwendung der topologischen Sortierung besteht darin, eine Folge von Jobs oder Tasks basierend auf ihren Abhängigkeiten zu planen . Die Jobs werden durch Scheitelpunkte dargestellt, und es gibt eine Kante von x nach y, wenn Job x abgeschlossen sein muss, bevor Job y gestartet werden kann (zum Beispiel beim Waschen von Kleidung muss die Waschmaschine fertig sein, bevor wir die Kleidung in den Trockner geben). . Dann gibt eine topologische Sortierung eine Reihenfolge an, in der die Jobs ausgeführt werden. Eine eng verwandte Anwendung topologischer Sortieralgorithmen wurde erstmals Anfang der 1960er Jahre im Kontext der PERT- Technik für die Planung im Projektmanagement untersucht . In dieser Anwendung stellen die Scheitelpunkte eines Diagramms die Meilensteine ​​eines Projekts dar und die Kanten stellen Aufgaben dar, die zwischen einem Meilenstein und einem anderen ausgeführt werden müssen. Die topologische Sortierung bildet die Grundlage von Linearzeitalgorithmen, um den kritischen Pfad des Projekts zu finden, eine Abfolge von Meilensteinen und Aufgaben, die die Länge des gesamten Projektzeitplans steuert.

In der Informatik Anwendungen dieser Art entstehen in Befehlseinplanung , der Formel Zellbeurteilung der Bestellung , wenn Werte in Formel Neuberechnen Kalkulationstabellen , Logiksynthese , die Bestimmung der Reihenfolge der Kompilierung Aufgaben auszuführen Makefiles , Daten Serialisierung und Symbol Abhängigkeiten bei der Lösung Linkern . Es wird auch verwendet, um zu entscheiden, in welcher Reihenfolge Tabellen mit Fremdschlüsseln in Datenbanken geladen werden.

Gerichteter azyklischer Graph 2.svg
Der links gezeigte Graph hat viele gültige topologische Sortierungen, einschließlich:
  • 5, 7, 3, 11, 8, 2, 9, 10 (visuell von oben nach unten, von links nach rechts)
  • 3, 5, 7, 8, 11, 2, 9, 10 (kleinster verfügbarer Vertex zuerst)
  • 5, 7, 3, 8, 11, 10, 9, 2 (wenigste Kanten zuerst)
  • 7, 5, 11, 3, 10, 8, 9, 2 (größter verfügbarer Scheitelpunkt zuerst)
  • 5, 7, 11, 2, 3, 8, 9, 10 (Versuch von oben nach unten, von links nach rechts)
  • 3, 7, 8, 5, 11, 10, 2, 9 (beliebig)

Algorithmen

Die üblichen Algorithmen zur topologischen Sortierung haben eine Laufzeit linear in der Anzahl der Knoten plus der Anzahl der Kanten, asymptotisch,

Kahns Algorithmus

Einer dieser Algorithmen, der zuerst von Kahn (1962) beschrieben wurde , arbeitet, indem er Knoten in der gleichen Reihenfolge wie die letztendliche topologische Sortierung wählt. Suchen Sie zunächst eine Liste von "Startknoten", die keine eingehenden Kanten haben, und fügen Sie sie in eine Menge S ein; mindestens ein solcher Knoten muss in einem nicht leeren azyklischen Graphen vorhanden sein. Dann:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge

while S is not empty do
    remove a node n from S
    add n to L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else 
    return L   (a topologically sorted order)

Wenn der Graph ein DAG ist , wird eine Lösung in der Liste L enthalten sein (die Lösung ist nicht unbedingt eindeutig). Andernfalls muss der Graph mindestens einen Kreis haben und daher ist eine topologische Sortierung unmöglich.

Die Nichteindeutigkeit der resultierenden Sortierung widerspiegelnd, kann die Struktur S einfach ein Satz oder eine Warteschlange oder ein Stapel sein. Abhängig von der Reihenfolge, in der Knoten n aus der Menge S entfernt werden, wird eine andere Lösung erstellt. Eine Variation von Kahns Algorithmus, die lexikographisch Verbindungen aufbricht, bildet eine Schlüsselkomponente des Coffman-Graham-Algorithmus für paralleles Scheduling und das Zeichnen von geschichteten Graphen .

Tiefensuche

Ein alternativer Algorithmus zur topologischen Sortierung basiert auf der Tiefensuche . Der Algorithmus durchläuft jeden Knoten des Graphen in einer willkürlichen Reihenfolge und leitet eine Tiefensuche ein, die endet, wenn er einen Knoten trifft, der bereits seit Beginn der topologischen Sortierung besucht wurde oder der Knoten keine ausgehenden Kanten hat (dh a Blattknoten):

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then
        return
    if n has a temporary mark then
        stop   (not a DAG)

    mark n with a temporary mark

    for each node m with an edge from n to m do
        visit(m)

    remove temporary mark from n
    mark n with a permanent mark
    add n to head of L

Jeder Knoten n wird der Ausgabeliste L erst vorangestellt , nachdem alle anderen Knoten berücksichtigt wurden, die von n abhängen (alle Nachkommen von n im Graphen). Insbesondere wenn der Algorithmus den Knoten n hinzufügt , wird garantiert, dass alle Knoten, die von n abhängen, bereits in der Ausgabeliste L enthalten sind: Sie wurden entweder durch den rekursiven Aufruf von visit(), der vor dem Aufruf von visit n endete, zu L hinzugefügt , oder durch einen Aufruf von visit(), der noch vor dem Aufruf von visit n gestartet wurde . Da jede Kante und jeder Knoten einmal besucht wird, läuft der Algorithmus in linearer Zeit. Dieser auf Tiefensuche basierende Algorithmus ist der von Cormen et al. (2001) ; es scheint 1976 von Tarjan erstmals in gedruckter Form beschrieben worden zu sein.

Parallele Algorithmen

Auf einer parallelen Maschine mit wahlfreiem Zugriff kann eine topologische Ordnung in O (log 2 n ) Zeit unter Verwendung einer polynomialen Anzahl von Prozessoren konstruiert werden , wodurch das Problem in die Komplexitätsklasse NC 2 eingeordnet wird . Eine Methode, dies zu tun, besteht darin, die Adjazenzmatrix des gegebenen Graphen wiederholt logarithmisch viele Male zu quadrieren, wobei Min-Plus-Matrixmultiplikation mit Maximierung anstelle von Minimierung verwendet wird. Die resultierende Matrix beschreibt die längsten Wegstrecken im Graphen. Das Sortieren der Scheitelpunkte nach den Längen ihrer längsten eingehenden Pfade erzeugt eine topologische Ordnung.

Ein Algorithmus zum parallelen topologischen Sortieren auf verteilten Speichermaschinen parallelisiert den Algorithmus von Kahn für einen DAG . Auf einer hohen Ebene entfernt der Algorithmus von Kahn wiederholt die Ecken des In-Grades 0 und fügt sie der topologischen Sortierung in der Reihenfolge hinzu, in der sie entfernt wurden. Da die ausgehenden Kanten der entfernten Ecken ebenfalls entfernt werden, gibt es einen neuen Satz von Ecken mit In-Grad 0, wo die Prozedur wiederholt wird, bis keine Ecken mehr übrig sind. Dieser Algorithmus führt Iterationen durch, wobei D der längste Pfad in G ist . Jede Iteration kann parallelisiert werden, was die Idee des folgenden Algorithmus ist.

Im Folgenden wird davon ausgegangen, dass die Graphpartition auf p Verarbeitungselementen (PE) gespeichert ist, die mit gekennzeichnet sind . Jedes PE i initialisiert einen Satz lokaler Scheitelpunkte mit In- Grad 0, wobei der obere Index die aktuelle Iteration repräsentiert. Da alle Knoten in den lokalen Mengen Ingrad 0 haben, also nicht benachbart sind, können sie für eine gültige topologische Sortierung in beliebiger Reihenfolge angegeben werden. Um jedem Scheitelpunkt einen globalen Index zuzuweisen, wird eine Präfixsumme über die Größen von berechnet . Bei jedem Schritt werden also Knoten zur topologischen Sortierung hinzugefügt.

Ausführung des parallelen topologischen Sortieralgorithmus auf einem DAG mit zwei Verarbeitungselementen.

Im ersten Schritt weist PE j die Indizes den lokalen Knoten in zu . Diese Scheitelpunkte werden zusammen mit ihren entsprechenden ausgehenden Kanten entfernt. Für jede abgehende Kante mit Endpunkt v in einem anderen PE , die Nachricht wird auf PE geschrieben l . Nachdem alle Scheitelpunkte entfernt wurden, werden die geposteten Nachrichten an ihr entsprechendes PE gesendet. Jede empfangene Nachricht aktualisiert den Grad des lokalen Scheitelpunkts v . Fällt der Ingrad auf null, wird v zu addiert . Dann beginnt die nächste Iteration.

In Schritt k weist PE j die Indizes zu , wobei die Gesamtmenge der verarbeiteten Scheitelpunkte nach Schritt ist . Dieser Vorgang wiederholt sich, bis keine Knoten mehr zu verarbeiten sind, daher . Nachfolgend finden Sie eine Übersicht über den Pseudocode eines einzelnen Programms mit mehreren Daten auf hoher Ebene dieses Algorithmus.

Beachten Sie, dass die Präfixsumme für die lokalen Offsets effizient parallel berechnet werden kann.

p processing elements with IDs from 0 to p-1
Input: G = (V, E) DAG, distributed to PEs, PE index j = 0, ..., p - 1
Output: topological sorting of G

function traverseDAGDistributed
    δ incoming degree of local vertices V
    Q = {vV | δ[v] = 0}                     // All vertices with indegree 0
    nrOfVerticesProcessed = 0

    do                 
        global build prefix sum over size of Q     // get offsets and total amount of vertices in this step
        offset = nrOfVerticesProcessed + sum(Qi, i = 0 to j - 1)          // j is the processor index
        foreach u in Q                                       
            localOrder[u] = index++;
            foreach (u,v) in E do post message (u, v) to PE owning vertex v
        nrOfVerticesProcessed += sum(|Qi|, i = 0 to p - 1)
        deliver all messages to neighbors of vertices in Q  
        receive messages for local vertices V
        remove all vertices in Q
        foreach message (u, v) received:
            if --δ[v] = 0
                add v to Q
    while global size of Q > 0

    return localOrder

Die Kommunikationskosten hängen stark von der gegebenen Graphpartition ab. Was die Laufzeit betrifft , so läuft dieser Algorithmus auf einem CRCW-PRAM- Modell, das Abrufen und Dekrementieren in konstanter Zeit ermöglicht, in , wobei D wiederum der längste Pfad in G und Δ der maximale Grad ist.

Anwendung bei der kürzesten Wegfindung

Die topologische Ordnung kann auch verwendet werden, um kürzeste Pfade durch einen gewichteten gerichteten azyklischen Graphen schnell zu berechnen . Sei V die Liste der Knoten in einem solchen Graphen in topologischer Reihenfolge. Dann berechnet der folgende Algorithmus den kürzesten Weg von einem Quellknoten s zu allen anderen Knoten:

  • Sei d ein Array der gleichen Länge wie V ; dies hält die kürzesten Wegstrecken von s . Setze d [ s ] = 0 , alle anderen d [ u ] = ∞ .
  • Sei p ein Array der gleichen Länge wie V , wobei alle Elemente auf nil initialisiert sind . Jedes p [ u ] hält den Vorgänger von u auf dem kürzesten Weg von s nach u .
  • Schleife über die Scheitelpunkte u, wie in V geordnet , beginnend mit s :
    • Für jede Ecke v, die direkt auf u folgt (dh es existiert eine Kante von u nach v ):
      • Sei w das Gewicht der Kante von u nach v .
      • Entspanne die Kante: wenn d [ v ] > d [ u ] + w , setze
        • d [ v ] ← d [ u ] + w ,
        • p [ v ] ← u .

Äquivalent:

  • Sei d ein Array der gleichen Länge wie V ; dies hält die kürzesten Wegstrecken von s . Setze d [ s ] = 0 , alle anderen d [ u ] = ∞ .
  • Sei p ein Array der gleichen Länge wie V , wobei alle Elemente auf nil initialisiert sind . Jedes p [ u ] hält den Vorgänger von u auf dem kürzesten Weg von s nach u .
  • Schleife über die Scheitelpunkte u, wie in V geordnet , beginnend mit s :
    • Für jede Ecke v in u (dh es existiert eine Kante von v nach u ):
      • Sei w das Gewicht der Kante von v nach u .
      • Entspanne die Kante: wenn d [ u ] > d [ v ] + w , setze
        • d [ u ] ← d [ v ] + w ,
        • p [ u ] v .

Auf einem Graphen mit n Knoten und m Kanten benötigt dieser Algorithmus Θ( n + m ) , dh lineare Zeit.

Einzigartigkeit

Wenn eine topologische Sortierung die Eigenschaft hat, dass alle Paare aufeinander folgender Knoten in der sortierten Reihenfolge durch Kanten verbunden sind, dann bilden diese Kanten einen gerichteten Hamilton-Weg im DAG . Wenn ein Hamilton-Pfad existiert, ist die topologische Sortierreihenfolge eindeutig; keine andere Reihenfolge respektiert die Kanten des Pfades. Umgekehrt, wenn eine topologische Sortierung keinen Hamilton-Pfad bildet, hat der DAG zwei oder mehr gültige topologische Ordnungen, denn in diesem Fall ist es immer möglich, eine zweite gültige Ordnung zu bilden, indem zwei aufeinanderfolgende Knoten vertauscht werden, die nicht durch eine Kante verbunden sind zueinander. Daher ist es möglich, trotz der NP-Härte des Hamilton-Wegproblems für allgemeinere gerichtete Graphen (dh zyklisch gerichtete Graphen) in linearer Zeit zu testen, ob eine eindeutige Ordnung existiert und ob ein Hamilton-Pfad existiert .

Bezug zu Teilaufträgen

Topologische Ordnungen sind auch eng mit dem Konzept einer linearen Erweiterung einer Teilordnung in der Mathematik verbunden. Eine teilweise geordnete Menge ist nur eine Menge von Objekten zusammen mit einer Definition der "≤"-Ungleichungsbeziehung, die die Axiome der Reflexivität ( x  ≤  x ), Antisymmetrie (wenn x  ≤  y und y  ≤  x dann x  =  y ) und Transitivität erfüllt (wenn x  ≤  y und y  ≤  z , dann x  ≤  z ). Ein Gesamtauftrag ist eine teilweise , in welche Reihenfolge, für jeweils zwei Objekte x und y in dem Satz entweder x  ≤  y oder y  ≤  x . Gesamtordnungen sind in der Informatik als Vergleichsoperatoren bekannt, die zum Ausführen von Vergleichssortierungsalgorithmen erforderlich sind . Für endliche Mengen können Gesamtordnungen mit linearen Folgen von Objekten identifiziert werden, wobei die "≤"-Beziehung immer dann wahr ist, wenn das erste Objekt dem zweiten Objekt in der Ordnung vorangeht; ein Vergleichssortieralgorithmus kann verwendet werden, um auf diese Weise eine Gesamtordnung in eine Sequenz umzuwandeln. Eine lineare Verlängerung einer Teilordnung ist eine Gesamtordnung , die mit ihm in dem Sinne kompatibel ist , dass, wenn x  ≤  y in der Teilordnung, dann x  ≤  y in dem Gesamtauftrag als auch.

Man kann eine partielle Ordnung von jedem DAG definieren, indem man die Menge von Objekten die Ecken des DAG sein lässt und x  ≤  y für zwei beliebige Ecken x und y als wahr definiert , wenn immer ein gerichteter Pfad von x nach y existiert ; das heißt, immer dann , wenn y ist erreichbar von x . Mit diesen Definitionen ist eine topologische Ordnung des DAG dasselbe wie eine lineare Erweiterung dieser Teilordnung. Umgekehrt kann jede Teilordnung als Erreichbarkeitsbeziehung in einem DAG definiert werden. Eine Möglichkeit, dies zu tun, besteht darin, einen DAG zu definieren, der für jedes Objekt in der teilweise geordneten Menge einen Scheitelpunkt hat und eine Kante xy für jedes Objektpaar, für das x  ≤  y ist . Eine alternative Möglichkeit dazu ist die transitive Reduktion der Teilbestellung; im Allgemeinen erzeugt dies DAGs mit weniger Kanten, aber die Erreichbarkeitsbeziehung in diesen DAGs ist immer noch dieselbe Teilordnung. Unter Verwendung dieser Konstruktionen kann man topologische Ordnungsalgorithmen verwenden, um lineare Erweiterungen von Teilordnungen zu finden.

Siehe auch

Verweise

Weiterlesen

Externe Links