Topologische Sortierung
Bei einer Menge von Dingen, wie etwa Aufgaben in einem Projekt, ist es oftmals notwendig, diese zu sortieren und eine feste Reihenfolge festzulegen. Dabei hängt die Reihenfolge in der Regel von bestimmten Kriterien ab. Die Aufgabe A muss beispielsweise unbedingt vor Aufgabe B erledigt werden. Hat man eine bestimmte Reihenfolge gefunden, welche diese Kriterien berücksichtigt, nennt man sie eine topologische Sortierung der Menge. Der Name "topologische Sortierung" leitet sich von der mathematischen Disziplin Topologie, der Lehre von Raum/Ort ab (τόπος (tópos) = Ort/Platz, λόγος (lógos) = Lehre).Zu einer Menge mit vorgegebenen Kriterien können mehrere topologische Sortierungen existieren, wenn beispielsweise Aufgabe B und Aufgabe C unabhängig voneinander ausgeführt werden können. Es ist dann egal ob zuerst Aufgabe B und dann Aufgabe C ausgeführt wird, oder andersherum. Wenn gegenseitige Abhängigkeiten bestehen, ist eine topologische Sortierung unmöglich.
Gibt es für jeweils zwei beliebige Dinge eine vorgegebene Beziehung, so ist die topologische Sortierung mit der gewöhnlichen Sortierung identisch. Andernfalls muss man topologisch sortieren, die topologische Sortierung entspricht dann nicht der gewöhnlichen Sortierung.
Die topologische Sortierung ist bei vielen Anwendungen der Informatik ein wichtiges Konzept. Bereits 1961 wurde von Daniel J. Lasser ein Algorithmus entwickelt, mit dem eine topologische Sortierung ganz allgemein erstellt werden kann. Zuvor waren allerdings schon Algorithmen für spezielle Anwendungen bekannt.
Des Weiteren spielt die topologische Sortierung in der Graphentheorie bei der Untersuchung von gerichteten Graphen auf Zyklenfreiheit eine große Rolle. 1930 zeigte Edmund Szpilrajn, dass sich jede partielle Ordnung topologisch sortieren lässt.
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. Oft gelingt dies jedoch nicht mehr, wenn nur Abhängigkeiten der Form Vorgänger/Nachfolger angegeben werden können, und nicht jedes Objekt von jedem abzuhängen braucht. Man kann dann aber versuchen, eine topologische Sortierung zu finden, die eine der möglichen korrekten Reihenfolgen darstellt.
Je nachdem, wie viele und welche Beziehungen bestehen, sind keine, 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.
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.
Für jeweils beliebige Elemente der Menge und der Relation gilt:
Üblicherweise wird jedoch nicht die ganze Relation angegeben, sondern nur eine ausreichende Teilmenge von direkten Vorgänger-Nachfolger-Paaren. Die Relation ist dann über den transitiven Abschluss der durch die übergebenen Paare definierten Relation gegeben. Beispielsweise besagt die komplette Relation für das Beispielproblem auch, dass das Unterhemd vor dem Mantel angezogen werden muss (wegen "Unterhemd vor Pullover" und "Pullover vor Mantel" folgt aus der Transitivität auch "Unterhemd vor Mantel"). Der transitive Abschluss besteht nun darin, diese Paare der Relation R hinzuzufügen. Bei der Implementierung eines entsprechenden Sortieralgorithmus wird allerdings die vollständige Relation nicht explizit generiert.
Eine bestimmte Reihenfolge hingegen wird mathematisch durch eine strenge Totalordnung definiert: Für je zwei verschiedene Elemente aus ist festgelegt, ob vor oder vor kommt (Es steht z.B. fest, ob ich heute morgen zuerst die Unterhose oder zuerst das Unterhemd angezogen habe). Die strenge Totalordnung ist also mathematisch definiert durch das zusätzliche Axiom der
Motiviert durch die Untersuchungen der beiden vorhergehenden Abschnitte kann man nun den mathematischen Begriff einer topologischen Sortierung einführen:
Sei eine Menge und . Eine Menge heißt genau dann eine topologische Sortierung von für , wenn eine strenge Totalordnung auf ist und gilt.
Diese Definition beschränkt den Begriff einer topologischen Sortierung ausdrücklich nicht auf endliche Mengen, obwohl im Zusammenhang mit einer algorithmischen Untersuchung eine solche Beschränkung sinnvoll ist.
Den bereits erwähnten Zusammenhang von topologischen Sortierungen und azyklischen Graphen kann man in folgendem Satz zusammenfassen:
Sei eine endliche Menge und . Dann sind äquivalent:
Stellt man eine Beziehung als Pfeil zwischen zwei Elementen dar, entsteht ein gerichteter Graph:
Alle Graphen, die keine Zyklen enthalten (so genannte azyklische Graphen, siehe auch Baum (Graphentheorie)), sind topologisch sortierbar.
Der Algorithmus geht von einem gerichteten Graph aus. Er entfernt solange Elemente ohne Vorgänger aus dem Graphen, bis keine Elemente mehr übrig sind.
Zunächst werden alle Elemente mit der Vorgängerzahl, also der Anzahl von Pfeilspitzen, die zum jeweiligen Element führen, versehen:
Elemente mit Vorgängerzahl 0 (blau markiert) haben keine anderen Vorgänger. Sie werden aus dem Graph entfernt. Hier können also die Socken, die Unterhose und das Unterhemd mit den zugehörigen Pfeilen entfernt werden. Dadurch ändern sich auch die Vorgängerzahlen von anderen Elementen:
Für das Ankleidebeispiel weiter oben sähe die Objektliste z.B. folgendermaßen aus:
Die Liste der Vorgängerzahlen hat 7 Elemente (eins pro Objekt), anfänglich sind alle Einträge 0.
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.
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:
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 die Vorgängeranzahl von Element 4 verringert. Nach diesem Schritt lautet die Vorgängeranzahlliste also
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:
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
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.
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.
Das Problem
Beispiel: Anziehreihenfolge von Kleidungsstücken
Beim Anziehen von Kleidungsstücken müssen manche Teile unbedingt vor anderen angezogen werden. So muss ein Pullover vor einem Mantel angezogen werden.
Um eine sinnvolle Reihenfolge zu bestimmen, können die sieben Kleidungsstücke topologisch sortiert werden, also etwa
Aber auch
Jedoch nicht
Mathematische Beschreibung des Problems
Die zu sortierende Menge
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 , die bezüglich einer Relation (Beziehung) die folgenden Eigenschaften hat:
Übersetzt heißt dies:
Die Menge bildet dann bezüglich der Relation eine strenge Halbordung (siehe auch Ordnungsrelation). Oft schreibt man statt auch einfach , weil die Relation ähnliche Eigenschaften hat wie die Kleiner-Relation für Zahlen. (Allerdings hat die Kleiner-Relation noch ein paar weitere Eigenschaften, die man hier nicht unbedingt hat. So kann man bei der Kleiner-Relation von zwei verschiedenen Zahlen immer entscheiden, welche der beiden kleiner ist. Hier ist dies nicht verlangt. Im Beispiel wäre dies der Vergleich von Socken und Unterhemd: Man kann nicht sagen, dass eines davon zuerst angezogen werden muss.)Die topologisch sortierte Menge
Die Aufgabe des topologischen Sortierens ist nun, zu einer gegebenen strengen Halbordnung eine Totalordnung zu finden, so dass für alle mit auch gilt .Definition der topologischen Sortierung
Azyklische Graphen und topologische Sortierungen
Darstellung als 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:Sortierbare Graphen
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).
Graph 2 ist ebenfalls topologisch sortierbar (zum Beispiel A C B D E), obwohl er nicht zusammenhängend ist.Nicht sortierbare Graphen
Graph 3 ist nicht topologisch sortierbar, da er einen Zyklus, also eine gegenseitige Abhängigkeit enthält (Elemente B, C, E und D).
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.
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.Algorithmus
Entfernung von Elementen ohne Vorgänger
Jetzt haben der Pullover und die Hose keine Voränger mehr, sie können also entfernt werden:
Nun bleiben nur noch Mantel und Schuhe übrig, die ebenfalls entfernt werden. Die Topologische Sortierung ist fertig, wenn alle Elemente entfernt werden konnten:Repräsentation im Rechner
Die Objekte (Elemente) selbst werden normalerweise in die
eingetragen. Um die Beziehungen darzustellen, genügt für jedes Element jeweils eine zusätzliche
Für den Sortieralgorithmus wird Platz für weitere Daten benötigt, die vom Algorithmus beschrieben und verwendet werden:
Die Nachfolgerlisten sähen dann folgendermaßen aus:
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.Algorithmus für das Topologische Sortieren
Einfache Version mit Markierung von Elementen
(Jetzt sind alle Vorgängerzahlen berechnet)
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.
und die bisherige Ausgabe lautet: Socken
und die Ausgabe bis hierhin lautet: Socken, Unterhemd
lautet, und die bisherige Ausgabe: Socken, Unterhemd, Pullover.Erweiterte Version mit einer zusätzlichen Hilfsliste
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 (), bei etwa 100 dagegen quadratisch (). Die Ausführungsdauer kann auch unabhängig von der Datenmenge, also konstant sein (). Elemente und Beziehungen
Beim topologischen Sortieren mit n Elementen und m Beziehungen zwischen diesen gilt für "normale" Probleme , da jedes Element im Schnitt nur eine konstante Zahl von Beziehungen hat. Im Extremfall können jedoch Beziehungen auftreten. Bei 6 Elementen kann theoretisch jedes von jedem abhängen; insgesamt wären das also 36 () Beziehungen. Dann ist .Erste Phase: Aufbau der Vorgängerzahlen
Die erste Phase setzt die Vorgängerzahlen auf 0 und benötigt n Schleifendurchläufe (). Für das Durchlaufen der m Nachfolger benötigt sie eine Zeit der Größenordnung , insgesamt also .Hilfsliste für vorgängerlose Elemente
Vor der zweiten Phase wird eine Hilfsliste aufgebaut, die alle vorgängerlosen Elemente enthält (). Danach werden nur noch neue vorgängerlose in die Hilfsliste eingefügt () und entnommen (). 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 möglich).
Beziehungen m und Objekte n | Zeitverhalten (mit Hilfsliste) | |
---|---|---|
Standardprobleme | bzw. | |
Viele Beziehungen | bzw. |
Ungünstiger Aufbau der Listen
Der Algorithmus in Wirthss 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 (), die für jedes eingelesene Paar () durchgeführt wird, insgesamt also (quadratisch). Dies verschlechtert das gesamte Zeitverhalten. Der Aufbau der Listen könnte zum Beispiel über einen Bucketsort-Algorithmus aber auch in linearer Zeit bewerkstelligt werden.
In der Programmiersprache Perl können Listen besonders einfach mit Hilfe von dynamisch wachsenden Feldern (zum Beispiel
Programm in der Programmiersprache Perl
@Elemente
) implementiert werden. Das angegebene Programm liest zunächst Beziehungspaare der Form Vorgänger Nachfolger, jeweils in einer Zeile und mit Leerzeichen getrennt, ein:
Katze Hund
Hahn Katze
Hund Esel
Als Ausgabe erhält man Hahn
Katze
Hund
Esel
Beim Einlesen der Beziehungspaare dient ein Perl-Hash zum Auffinden des numerischen Indexes von bestehenden Elementen. Elemente ohne Index werden erzeugt. Dazu wird ein neuer Index vergeben, der Name gespeichert und eine leere Nachfolgerliste angelegt. Diese Liste nimmt dann die Indizes der Nachfolgerelemente für die jeweiligen Vorgänger auf.
Der Algorithmus verwendet nur noch Indizes und läuft wie oben beschrieben. Erst bei der Ausgabe wird der unter dem Index gespeicherte Name wieder verwendet.
Das Perlskript sieht folgendermaßen aus:
#!/usr/bin/perl # Topologisches Sortierprogramm in Perl # Lizenzstatus: GNU FDL, für Wikipedia # # = # Unterprogramm zum Finden bzw. Neuanlegen eines Elements # = sub finde_oder_erzeuge_element { my ($str)=@_; my ($idx)=$hashindex{$str}; if (!defined($idx)) { # Neues Element ... $idx=$objektzahl++; $hashindex{$str}=$idx; $name[$idx]=$str; @{$nachfolgerliste[$idx]}=(); } return $idx; } # = # Einlesen, Aufbau der Elementliste und der Nachfolgerlisten # = $objektzahl=0; %hashindex=(); while (<>) { chomp; /^\\s*(\\S+)\\s*(\\S+)\\s*$/ || die "Bitte \\"Vorgänger Nachfolger\\" eingeben\";
($vorgaenger,$nachfolger)=($1,$2); $v=finde_oder_erzeuge_element($vorgaenger); $n=finde_oder_erzeuge_element($nachfolger); push @{$nachfolgerliste[$v]},$n; } # = # Topsort 1: Berechne Vorgängerzahlen # = for $n (0..$objektzahl-1) { $vorgaengerzahl[$n]=0; } for $v (0..$objektzahl-1) { for $n (@{$nachfolgerliste[$v]}) { ++$vorgaengerzahl[$n]; } } # = # Erzeuge die Hilfsliste für die Elemente mit Vorgängerzahl 0 # = @hilfsliste=(); for $n (0..$objektzahl-1) { push(@hilfsliste,$n) if ($vorgaengerzahl[$n]==0) } # = # Topsort 2: Gib solange möglich ein Element der Hilfsliste aus # Verringere Vorgängerzahl der Nachfolger des Elements # Neue Elemente mit Vorgängerzahl 0 in die Hilfsliste # = $ausgabe=0; while (defined($v=pop(@hilfsliste))) { print "$name[$v]\";
++$ausgabe; for $n (@{$nachfolgerliste[$v]}) { --$vorgaengerzahl[$n]; push(@hilfsliste,$n) if ($vorgaengerzahl[$n]==0); } } die "Zyklen gefunden\" if $ausgabe<$objektzahl;
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 |
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.
Eingabe sind die Abhängigkeiten in der Form vor nach. Ausgabe ist eine topologische Sortierung der Elemente.
Die vorstehend hergeleiteten Algorithmen lassen sich in sinngemäß umgekehrter Reihenfolge auch beim Ausziehen verwenden. Wenn man dabei nicht alleine ist, sollte man jedoch die Regel beachten: never get your pants off before your socks.
Hauptkategorien und Unterkategorien
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
> Pullover Mantel
> Hose Mantel
> Hose Schuhe
> Socken Schuhe
> Ende
Unterhose
Unterhemd
Socken
Pullover
Hose
Mantel
Schuhe
Aufruf des tsort-Programms unter Unix/LinuxTrivia
Weblinks
Literatur
Beurteilung:
Exzellenter Artikel