Inkrementeller, gerichteter, azyklischer Graph
-
Hallo da,
bislang löste ich meine Zyklen-Tests in einem gerichteten Graph in einem nachgelagerten Verarbeitungsschritt, praktisch durch die topologische Sortierung der Knoten.
Ich würde jetzt gerne darauf umsteigen, dass das auch inkrementell beim Erzeugen des Graphen funktioniert. Irgendwie erscheint es mir intuitiv möglich, den Test, ob die nächste Kante einen Zyklus hinzufügen würde, in ein kleineres Problem zu überführen, als jedes Mal wieder die gesamte Topologie zu "lösen".
Eigentlich kann man ja den Graph in "Ebenen" aufteilen und für jeden Knoten die minimale und maximale Ebene abspeichern, um dann bei einer neuen Verbindung zu überprüfen, ob es durch die hinzugefügte Ebenen-"Einschränkung" zu einem Konflikt der Intervalle kommt. Ich bin allmählich aber etwas müde und habe noch nicht vollends durchdacht, ob die Führung und das Aktualisieren eines solchen Min-Max-Ebenen-Intervalls pro Knoten eventuell bei anderen Graph-Operationen zu Schwierigkeiten führt.Deshalb meine Frage: Kennt ihr eine fertig durchdachte inkrementelle Datenstruktur für einen gerichteten, azyklischen Graphen?
-
Okay, den hier habe ich gerade aufgetan, ackere ich mal durch: http://www.siam.org/proceedings/soda/2009/SODA09_120_benderm.pdf
-
-
Danke Jester, das packe ich mal zu meiner Liste.
Während meiner Anfrage wusste ich die Nomenklatur noch nicht so recht und nahm an, wenn es inkrementell ist, dann meint das inkrementelle Veränderungen, aber gemeint ist mit inkrementell wirklich nur "hinzufügen". Offenbar sind die meisten Algorithmen auch nur für's Hinzufügen gedacht. Ich habe über die Referenzen jetzt http://www.doc.ic.ac.uk/~phjk/Publications/DynamicTopoSortAlg-JEA-07.pdf gefunden, in dem insgesamt drei voll dynamische Algorithmen angesprochen werden. Scheint ja noch ein umforschtes Gebiet zu sein, irgendwie habe ich ein Riecher dafür
Wird eine gute Schmökerzeit morgen!
-
Ja, normalerweise unterscheidet man zwischen "incremental", "decremental" und "fully dynamic". Eventuell findest Du mit diesen Stichwörtern noch mehr.