Effizienter Algorithmus zur Auflösung von Schleifen in gerichteten Graphen

[danjou]

Hallo zusammen,

folgende Problemstellung:

Ich habe einen (beliebigen) gerichteten, zyklischen Graphen. Mittels der topologischen Sortierung und Tiefensuche (DFS) ist es möglich diese Zyklen zu detektieren (Zyklus genau dann, wenn Rückwärtszweig gefunden).

Nun bin ich auf der Suche nach einem effizienten Algorithmus zum Auflösen der Schleifen. Dabei sollen durch das Aufbrechen einer Kante möglichst viele Schleifen beseitigt werden.

Optimal wäre ein Algorithmus, dessen Zeitkomplexität proportional zur Knotenanzahl n wächst ( O(n) ).

Hat irgendjemand vielleicht von einem Algorithmus gehört, der diese Aufgabe erfüllt oder hat möglicherweise sogar eine eigene, gute Idee, wie man die Kanten am effiziensten aufbrechen kann?

Ich bin über jeden Vorschlag dankbar.

Lg danjou

Bearbeitet 30. Juni 2010 von danjou

[flashpixx]

Nun bin ich auf der Suche nach einem effizienten Algorithmus zum Auflösen der Schleifen.

Verstehe ich das richtig, dass Du einen schleifenlosen Graph haben willst, d.h. müsstest doch nur die Kante, die Du eh schon dedektiert hast und die zur Schleife führt nicht übernehmen.

Mir ist leider nicht so ganz klar, was Du genau machen willst, Du hast einen Graph in dem Schleifen sind, diese hast Du schon gefunden, d.h. Du musst eben nur eine Kante entfernen, um die Redundanz zu beseitigen

Aber interessantes Problem

[danjou]

Ja ich möchte einen schleifenlosen Graphen. Aber ich möchte nicht sofort alle Rückwärtszweige löschen, da es sich in Wahrheit um einen Signalflussgraphen handelt. Daher müssen die gelöschten Kanten später durch andere Elemente ersetzt werden. Aber das ist hier weitestgehend unwichtig.

Tatsache ist, dass so wenig Kanten wie möglich gelöscht werden sollen.

Sieh dir mal das angehängte triviale Beispiel an. Hier kann man natürlich die Rückwärtszeige 5 und 3 löschen. Dann wären die Schleifen weg. Man kann aber auch, und so ist es am effiziensten nur die Kante 2 löschen. Dann sind sofort alle Zyklen eliminiert. Sowohl der äußere als auch der innere.

Ein Ansatz ist über die Schnittmenge der beiden Zyklen zu gehen. Also {2,3} und {1,2,4,5}. Die Schnittmenge ist dabei 2 --> Kante 2 löschen. Das unangenehme dabei ist, dass die Zeitkomplexität O(exp) ist, wächst also exponentiell. Daher bin ich auch der Suche nach einem effizienteren Algorithmus.

Lg

Bearbeitet 30. Juni 2010 von danjou

[flashpixx]

Tatsache ist, dass so wenig Kanten wie möglich gelöscht werden sollen.

Okay, das ist eine wichtige Nebenbedingung, d.h. Du willst letztendlich die "minimale" Kantenanzahl, die notwendig ist, um alle Schleifen zu beseitigen

Hier kann man natürlich die Rückwärtszeige 5 und 3 löschen. Dann wären die Schleifen weg. Man kann aber auch, und so ist es am effiziensten nur die Kante 2 löschen. Dann sind sofort alle Zyklen eliminiert.

Eigentlich müsstest Du 3 löschen und nicht 2 !?

Die Schnittmenge ist dabei 2 --> Kante 2 löschen. Das unangenehme dabei ist, dass die Zeitkomplexität O(exp) ist, wächst also exponentiell.

ist halt Graphenproblem, die sind fast alle NP-hart....

Also an oben angeknüpft: Ich würde das mit einem Ameisenalgo machen. Vorteil ist, Du kannst das ganze gute parallelisieren und das Ergebnis ist zwar nicht "optimal", aber im Hinblick auf den Rechenaufwand durchaus brauchbar.

Im Grunde suchst Du ja die Kante, die am meisten "benutzt" wird, d.h. ein Großteil der Ameisen wird über Kanten laufen, die zu "vielen" Zyklen gehören. Wobei Du dabei aufpassen musst, dass die Ameise nicht den Zyklus ständig abläuft (kann man z.B. durch eine Tabuliste verhinden).

Was evtl Arbeit spart wäre, dass Du den Graphen verkleinerst, d.h. die Kanten zwischen den Zyklen verkürzt, so dass Du nur die Zyklen absuchst. Ich würde halt eine gewisse Zeit die Ameisen durch den Graph laufen lassen, und schauen, welche Kanten häufiger genutzt werden und diese würde ich entfernen.

Okay rein technisch bräuchtest Du die Zyklen nicht erst suchen, sondern könntest direkt den Ameisenalgo laufen lassen und während dessen die Zyklen entfernen.

Evtl wären auch noch Ideen mit dem Pagerank, SALSA oder HITS zu arbeiten und im Grunde die "Link-Struktur" des Graphen zu bewerten, wobei ja dort eher die Knoten und nicht die Kanten bewertet.

Bearbeitet 30. Juni 2010 von flashpixx