Topologische Sortierung

Verschiedene Objekte können nach messbaren Größen, zum Beispiel Städte nach Einwohnerzahlen, Schuhe nach Schuhgrößen, aber auch alphabetisch nach Namen eindeutig sortiert werden. Dies gilt nicht mehr, wenn nur Abhängigkeiten der Form Vorgänger/Nachfolger angegeben werden können, da oftmals nicht jedes Objekt von jedem abhängen muss. Dann kann man nur noch eine topologische Sortierung finden, die eine der möglichen „korrekten“ Reihenfolgen darstellt.

Die Bezeichnung topologisch leitet sich vom griechischen topos (Platz) und logos (Lehre) ab. Topologisches Sortieren bedeutet daher eher in eine richtige Reihenfolge bringen oder einen richtigen Platz finden.

Je nachdem, wie viele und welche Beziehungen bestehen, sind nur eine oder auch mehrere verschiedene topologische Sortierungen möglich. Wenn gegenseitige (zyklische) Abhängigkeiten bestehen, ist eine topologische Sortierung nicht möglich. In der Tat ist ein Anwendungsgebiet der topologischen Sortierung die Überprüfung, ob zyklische Abhängigkeiten bestehen.

Beispiel: Anziehreihenfolge von Kleidungsstücken

Beim Anziehen von Kleidungsstücken müssen manche Teile unbedingt vor anderen angezogen werden. Beispielsweise muss ein Pullover vor dem Mantel angezogen werden.

Hat man zum Beispiel eine Hose, ein Unterhemd, Pullover, Mantel, Socken, eine Unterhose und ein paar Schuhe, so kann man die folgenden Beziehungen für das Anziehen angeben.

Das Unterhemd vor dem Pullover
Die Unterhose vor der Hose
Den Pullover vor dem Mantel
Die Hose vor dem Mantel
Die Hose vor den Schuhen
Die Socken vor den Schuhen

Um eine sinnvolle Reihenfolge zu bestimmen, müssen die sechs Kleidungsstücke topologisch sortiert werden, also etwa

Erst die Unterhose, dann die Socken, Hose, Unterhemd, Pullover, Mantel, Schuhe.

Aber auch

Erst das Unterhemd, dann die Unterhose, dann Pullover, Socken, Hose, Schuhe, Mantel.

Jedoch nicht

Erst den Pullover, da das Unterhemd vorher angezogen werden muss!

Darstellung als gerichteter Graph

Stellt man eine Beziehung als Pfeil zwischen zwei Elementen dar, entsteht ein gerichteter Graph:

Die Kleidungsstücke kann man topologisch sortieren, indem man sie linear anordnet und darauf achtet, dass alle Pfeile nur von links nach rechts weisen:

Dass die Socken hier allein stehen, stört nicht. Sie können an einer beliebigen Stelle eingeordnet werden.

Sortierbare Graphen

Datei:Topsortierbar1.png

Graph 1

Graph 1 ist topologisch sortierbar. Es existieren mehrere Lösungen (zum Beispiel A B C G D E F). Dabei spielt es keine Rolle, dass zwei Elemente ohne Vorgänger existieren (A und G), dass manche Elemente mehrere Nachfolger haben (B hat zum Beispiel drei Nachfolger) und manche mehrere Vorgänger (D und E).

Datei:Topsortierbar2.png

Graph 2

Graph 2 ist ebenfalls topologisch sortierbar (zum Beispiel A C B D E), obwohl er nicht zusammenhängend ist.

Alle Graphen, die keine Zyklen enthalten (so genannte azyklische Graphen, siehe auch Baum (Graphentheorie)), sind topologisch sortierbar.

Nicht sortierbare Graphen

Datei:Topnichtsortierbar1.png

Graph 3

Graph 3 ist nicht topologisch sortierbar, da er einen Zyklus, also eine gegenseitige Abhängigkeit enthält (Elemente B, C, E und D).

Datei:Topnichtsortierbar2.png

Graph 4

Auch wenn wie in Graph 4 nur zwei Elemente gegenseitig voneinander abhängen oder wenn ein Element sich auf sich selbst bezieht (Graph 5), ist eine topologische Sortierung unmöglich.

Datei:Topnichtsortierbar3.png

Graph 5

Alle Graphen, die zyklische Abhängigkeiten enthalten, sind nicht topologisch sortierbar. Die topologische Sortierung kann daher auch zur Prüfung eines gerichteten Graphen auf Zyklen verwendet werden.

Mathematische Ordnungsrelation

Die zu sortierenden Objekte müssen bezüglich der Beziehung teilweise angeordnet werden können, damit sie topologisch sortierbar sind. Mathematisch bilden die Objekte die Elemente einer Menge $M$ , die bezüglich der Relation (Beziehung) $R$ die folgenden Eigenschaften hat:

Für jeweils beliebige Elemente $a,b,c$ der Menge $M$ und der Relation $R$ gilt:

Irreflexivität: $\neg (a\,R\,a)$ ( $a$ steht nicht mit $a$ in Relation)
Transitivität: Wenn $a\,R\,b$ und $b\,R\,c$ , dann gilt $a\,R\,c$ .

Übersetzt heißt dies:

Ich kann die Hose nicht vor der Hose anziehen.
Wenn ich das Unterhemd vor dem Pullover anziehen muss und den Pullover vor dem Mantel, so folgt daraus, dass ich das Unterhemd vor dem Mantel anziehen muss.

Die Menge $M$ bildet dann bezüglich der Relation $R$ eine strenge Halbordung (siehe auch Ordnungsrelation). Oft schreibt man statt $R$ auch einfach $<$ , weil die Relation ähnliche Eigenschaften hat wie die Kleiner-Relation für Zahlen.

Algorithmus

Repräsentation im Rechner

Die Objekte (Elemente) selbst werden normalerweise in die

Datenstruktur einer Liste mit Objektattributen (Name, Index, ...)

eingetragen. Um die Beziehungen darzustellen, genügt für jedes Element jeweils eine zusätzliche

Liste mit Verweisen (Referenzen oder Zeiger) auf die Nachfolger eines Objekts. Die Objekte enthalten einen Verweis auf ihre jeweilige Nachfolgerliste.

Für den Sortieralgorithmus wird Platz für weitere Daten benötigt, die vom Algorithmus beschrieben und verwendet werden:

Für jedes Objekt Platz für eine Zahl, die die Anzahl der Vorgänger aufnimmt.
Optional eine Hilfsliste, die Objekte ohne Vorgänger aufnimmt.

Beispiel:

Für das Ankleidebeispiel weiter oben sähe die Objektliste z.B. folgendermaßen aus:

Hose
Mantel
Pullover
Schuhe
Socken
Unterhemd
Unterhose

Die Nachfolgerlisten sähen dann folgendermaßen aus:

2, 4
(leere Liste)
2
(leere Liste)
4
3
1

Dabei besagt die erste Liste (für die Hose), dass Mantel (Objekt 2) und Schuhe (objekt 4) erst nach der Hose angezogen werden können. Die zweite Liste (für den Mantel) besagt, dass es kein Kleidungsstück gibt, das erst nach dem Mantel angezogen werden kann.

Die Liste der Vorgängerzahlen hat 7 Elemente (eins pro Objekt), anfänglich sind alle Elemente 0.

Algorithmus für das Topologische Sortieren

Der Sortieralgorithmus benötigt die Information, wie viele Vorgänger ein Element enthält (Vorgängeranzahl). Bereits gefundene Elemente müssen aus der Liste entfernt oder markiert werden. Man kann Elemente dadurch markieren, indem man die Vorgängeranzahl auf –1 setzt.

1. Berechne die Vorgängeranzahlen:

Setze die Vorgängeranzahl aller Elemente auf 0.
Für alle Elemente durchlaufe die Nachfolgerliste und erhöhe die Vorgängeranzahl jedes dieser Elemente um 1.
(Jetzt sind alle Vorgängerzahlen berechnet)

Im Beispiel hat z.B. die Hose (Element 1) nur einen Vorgänger (die Unterhose), daher taucht die 1 nur einmal in den Nachfolgerlisten auf. Der Mantel (Element 2) hat hingegen 2 Vorgänger (Pullover und Hose), weshalb die 2 zweimal in den Nachfolgerlisten auftaucht. Insgesamt ergibt sich also für die Vorgängerliste:

1
2
1
2
0
0
0

2. Solange (nicht markierte) Elemente in der Liste sind:

Suche ein Element mit Vorgängeranzahl 0.
Falls kein solches Element gefunden wird, ist eine topologische Sortierung nicht möglich, da gegenseitige Abhängigkeiten (Zyklen) bestehen. Der Algorithmus bricht mit einem Fehler ab.
Gib das gefundene Elemente aus und entferne es aus der Liste oder markiere es (Setze zum Beispiel die Vorgängeranzahl gleich –1 als Markierung)
Gehe die Liste der Nachfolger des gefundenen Elements durch und verringere die Vorgängeranzahl um 1. Das Element ist jetzt effektiv aus der Elementliste entfernt. Durch die Verringerung der Vorgängeranzahl können neue Elemente ohne Vorgänger entstehen.

Sind alle Elemente ausgegeben bzw. markiert, so war die topologische Sortierung erfolgreich.

Im Beispiel ist Element 5 (Socken) ein solches vorgängerloses Element. Daher wird dieses Element ausgegeben und mit –1 markiert (wir hätten aber genausogut mit Element 6 oder 7 anfangen können). Einziges Nachfolgerobjekt der Socken sind die Schuhe (Element 4), daher wird Element 4 in der Vorgängerzahlliste verringert. Nach diesem Schritt lautet diese Liste also

1
2
1
1
–1
0
0

und die bisherige Ausgabe lautet: Socken

Im nächsten Schritt stellen wir fest, dass auch Element 6 (Unterhemd) keine Vorgänger hat. Wiederum gibt es nur ein einziges Nachfolgerelement, den Pullover (Nummer 3). Somit lautet die Vorgängerzahlliste nach den zweiten Schritt:

1
2
0
1
–1
–1
0

und die Ausgabe bis hierhin lautet: Socken, Unterhemd

Durch die Verringerung um 1 wurde die Vorgängerzahl des Pullovers (Element 3) zu 0. Nehmen wir also als nächstes den Pullover, so finden wir in seiner Nachfolgerliste nur Element 2 (den Mantel), dessen Vorgängerzahl wir somit ebenfalls verringern müssen, so dass die Liste nun

1
1
–1
1
–1
–1
0

lautet, und die bisherige Ausgabe: Socken, Unterhemd, Pullover.

Jetzt haben wir zum ersten Mal keine Wahl mehr über das nächste Element: Nur die Unterhose hat jetzt die Vorgängerzahl 0. Deren Entfernung führt dann im nächsten Schritt zu einer 0 bei der Hose (Element 1), und deren Entfernung führt schließlich dazu, dass sowohl Element 2 (Mantel) als auch Element 4 (Schuhe) keine Vorgänger mehr haben. Wählen wir nun den Mantel vor den Schuhen, so ergibt sich insgesamt die Sortierung

Socken, Unterhemd, Pullover, Unterhose, Hose, Mantel, Schuhe,

die unschwer als korrekte topologische Sortierung dieser Elemente erkannt werden kann

Verwendung einer zusätzlichen Hilfsliste

Um Elemente ohne Vorgänger schnell zu finden, kann eine zusätzliche Hilfsliste erzeugt werden. Diese wird nach der Berechnung der Vorgängerzahlen mit allen anfangs vorgängerlosen Elementen, also mit Vorgängerzahl gleich Null, gefüllt. In Phase 2 wird anstatt der Suche eines Elements mit Vorgängeranzahl Null einfach eines aus der Hilfsliste entnommen. Wird die Vorgängerzahl eines Elements während der Phase 2 bei der Verringerung um 1 gleich Null, so wird es in die Hilfsliste eingefügt. Der Algorithmus endet, wenn keine Elemente mehr in der Hilfsliste sind. Auf die Markierung kann dann ebenfalls verzichtet werden.

Zeitverhalten (Komplexität)

Die Komplexität des Algorithmus beschreibt das zeitliche Verhalten bei großen Datenmengen, genauer das Verhältnis der Ausführungsdauern bei Vergrößerung der Eingabedaten, zum Beispiel von 10.000 auf 100.000 Einträge (Faktor 10). Beträgt das Zeitverhältnis etwa 10, so ist die Zeitabhängigkeit linear ( $O(n)$ ), bei etwa 100 dagegen quadratisch ( $O(n^{2})$ ). Die Ausführungsdauer kann auch unabhängig von der Datenmenge, also konstant sein ( $O(1)$ ).

Elemente und Beziehungen

Beim topologischen Sortieren mit n Elementen und m Beziehungen zwischen diesen gilt für "normale" Probleme $O(m)=O(n)$ , da jedes Element im Schnitt nur eine konstante Zahl von Beziehungen hat. Im Extremfall können jedoch $m=n^{2}$ Beziehungen auftreten. Bei 6 Elementen kann theoretisch jedes von jedem abhängen; insgesamt wären das also 36 ( $=6^{2}$ ) Beziehungen. Dann ist $O(m)=O(n^{2})$ .

Erste Phase: Aufbau der Vorgängerzahlen

Die erste Phase setzt die Vorgängerzahlen auf 0 und benötigt n Schleifendurchläufe ( $O(n)$ ). Für das Durchlaufen der m Nachfolger benötigt sie eine Zeit der Größenordnung $O(m)$ , insgesamt also $O(n)+O(m)=\max(O(n),O(m))$ .

Hilfsliste für vorgängerlose Elemente

Vor der zweiten Phase wird eine Hilfsliste aufgebaut, die alle vorgängerlosen Elemente enthält ( $O(n)$ ). Danach werden nur noch neue vorgängerlose in die Hilfsliste eingefügt ( $O(1)$ ) und entnommen ( $O(1)$ ). Die Suche nach vorgängerlosen Elementen beeinflusst das Zeitverhalten dann nicht. Gleiches kann man erreichen, indem man gefundene vorgängerlose Elemente "nach vorne" verlagert (mit $O(1)$ möglich).

Zweite Phase: Entnahme von vorgängerlosen Elementen

Die zweite Phase behandelt im Erfolgsfall alle n Elemente und verringert die Vorgängerzahl von im Schnitt ${\frac {m}{n}}$ Nachfolgern, das Zeitverhalten ist also $O(n)\cdot O({\frac {m}{n}})$ .

Gesamtverhalten

Die erste Phase und der Aufbau der Hilfsliste haben ein lineares Zeitverhalten und sind damit ebenso gut oder besser als die zweite Phase. Das Gesamtverhalten wird daher von der letzten Phase bestimmt. Insgesamt ergibt sich:

	Beziehungen m und Objekte n	Zeitverhalten (mit Hilfsliste)
Standardprobleme	$O(m)=O(n)$	$O(n)$ bzw. $O(m)$
Viele Beziehungen	$O(m)=O(n^{2})$	$O(n^{2})$ bzw. $O(m)$

Ungünstiger Aufbau der Listen

Der Algorithmus in Wirths Buch (siehe Literatur) enthält eine Einlesephase, in der er die Beziehungspaare in eine Liste einfügt, die wiederum Listen für die Nachfolger enthalten. Die jeweilige Nachfolgerliste ermittelt er durch eine lineare Suche ( $O(n)$ ), die für jedes eingelesene Paar ( $O(m)$ ) durchgeführt wird, insgesamt also $O(n)\cdot O(m)$ (quadratisch). Dies verschlechtert das gesamte Zeitverhalten. Der Aufbau der Listen könnte zum Beispiel über einen Bucketsort-Algorithmus aber auch in linearer Zeit $O(m)$ bewerkstelligt werden.

Weitere Beispiele

Unterprogrammaufrufe und Rekursion

In Computerprogrammen können Unterprogramme weitere Unterprogramme aufrufen. Falls keine gegenseiten Aufrufe oder Selbstaufrufe auftreten, kann eine eindeutige Reihenfolge mit Hilfe der topologischen Sortierung ermittelt werden. Andernfalls rufen sich Unterprogramme rekursiv auf.

Unterprogramme mit Rekursion

Unterprogramme ohne Rekursion

  Prozedur a()
  { Aufruf von b()
    Aufruf von c()
  }
  Prozedur b()
  { Aufruf von c()
  }
  Prozedur c()
  { Aufruf von b()
    Aufruf von d()
  }

  Prozedur a()
  { Aufruf von b()
    Aufruf von c()
  }
  Prozedur b()
  { Aufruf von d()
  }
  Prozedur c()
  { Aufruf von b()
    Aufruf von d()
  }

Topologisches Sortieren nicht möglich, da Prozedur b die Prozedur c aufruft und Prozedur c die Prozedur b (Zyklus).

Topologische Sortierung: 'a c b d

Hauptkategorien und Unterkategorien

Manche Kategoriensysteme sind hierarchisch angeordnet. Die oberste Ebene enthält die Hauptkategorien, die wiederum Unterkategorien enthalten. Unterkategorien können weitere Unterkategorien, bis zu einer beliebigen Tiefe. Normalerweise fügt man eine neue Kategorie in eine bestehende ein, wenn die Anzahl der Objekte in einer Kategorie eine bestimmte Grenze überschreitet. Andere, bereits bestehende Kategorien werden in die neue Kategorie eingeordnet. Dabei kann versehentlich eine übergeordnete Kategorie oder eine Kategorie aus einer anderen Hauptkategorie in die neue Kategorie eingeordnet werden, wodurch gegenseitige Abhängigkeiten entstehen und die Hierarchie des Systems zerstört wird. Ein Benutzer, der durch den (vermeintlichen) Kategoriebaum navigiert, kann sich unter Umständen ewig "im Kreis" drehen, was durch die geforderte Hierarchie ja verhindert werden soll.

Durch topologisches Sortieren des Kategorienbaums kann man nachweisen, dass keine Zyklen vorhanden sind. Alle Hauptkategorien werden dazu zunächst in einen hypothetischen Wurzelbaum eingeordnet. Die Beziehung ist die Bedingung, dass eine Kategorie direkte Unterkategorie einer anderen Kategorie ist, die Information ist ohnehin vorhanden. Schlägt der topologische Sortieralgorithmus fehl, sind zyklische Abhängigkeiten vorhanden und das System ist nicht mehr hierarchisch.

tsort-Kommando unter Unix und Linux

Unix-ähnliche Betriebssystemen besitzen oft ein Programm namens tsort, das eine topologische Sortierung durchführt. Es war früher nötig, um übersetzte Objektdateien, die voneinander abhängen, in korrekter Reihenfolge in eine Programmbibliothek einzufügen, kann aber auch für andere Zwecke eingesetzt werden:

  $ tsort <<Ende
  > Unterhemd Pullover
  > Unterhose Hose
  > Socken Socken
  > Pullover Mantel
  > Hose Mantel
  > Ende
  Socken
  Unterhemd
  Unterhose
  Pullover
  Hose
  Mantel

Aufruf des tsort-Programms unter Unix/Linux

Eingabe sind die Abhängigkeiten in der Form vor nach. Elemente ohne Abhängigkeiten (Socken) gibt man doppelt ein. Ausgabe ist eine topologische Sortierung der Elemente.

Literatur

Niklaus Wirth: Algorithmen und Datenstukturen, Pascal Version. 4. Aufl. Teubner Verlag, Stuttgart 1995 ISBN 3519122502
Donald Knuth: The Art of Computer Programming. Vol.1: Fundamental Algorithms. 3. Aufl. Addison Wesley 1997 ISBN 0201896834