Algorithmen für Feedback-Arc-Set

Berger and Shor, 1990

Saab, Seite 236
Einfache Heuristik, die das FAS anhand der Anzahl ein- und ausgehender Kanten eines Knoten aufbaut
Einschränkung: Laut Paper nur auf planaren Graphen korrekt
Implementierung: src/fas/simple_heuristic.rs

Saab, Seite 238/239
Divide-And-Conquer Heuristik, die
- den Graphen in Supgraphen zerlegt (1. und 2. Hälfte der topologischen Sortierung)
- sich zu Nutze macht, dass in einer topologischen Sortierung die linksgerichteten Kanten ein FAS bilden
Qualität abhängig von gewählter Sortierung
Verwendete Unter-Algorithmen:
- Topologische Sortierung nach Anzahl eingehender Knoten (order/topological_sort.rs)
Implementierung: src/fas/divide_and_conquer_by_order_heuristic.rs

Saab, Seite 241
Divide-And-Conquer Heuristik, die
- den Graphen in Supgraphen (Strongly Connected Components) zerlegt
- auf SCCs eine ausgeglichene Bisektion bildet und Kanten, welche von B2 nach B1 verlaufen, in das FAS aufnimmt
Qualität abhängig von Kosten der Bisektion (Anzahl Kanten zwischen beiden)
Verwendete Unter-Algorithmen:
- Tarjan's SCC (scc/tarjan.rs)
- Bisektion durch Annäherung an Optimum niedriger Kosten (bisection/stochastical_evolution.rs)
Enschränkungen:
- Fehler im Paper auf Seite 243: Statt Cpre = cost(V1, V2) muss Cpre = cost(B1, B2) sein, da die Kosten ja immmer besser werden sollen!
- Fehler im Paper auf Seite 241: Der Algorithmus macht einen endlosen rekursiven Abstieg. Der Code fas(G[V1 ]) ∪ fas(G[V2 ]) ist unserer Meinung nach überflüssig, da V1 und V2 die Bisektion einer SCC sind und somit keinen Zyklus haben KÖNNEN.
- Der Algorithmus funktioniert dennoch nicht korrekt. Daher Tests deaktiviert und keine Benchmarks durchgeführt! Vermutlich weiterer Logik-Fehler
- Implementierung: src/fas/divide_and_conquer_by_bisection.rs

Saab, Seite 238/239
Grundversion mit zufälliger Knotenauswahl auch in Saab, Seite 238 beschrieben
Greedy Heuristik, die
- Sinks, Sources und - falls nicht vorhanden - Knoten mit maximalen Delta zwischen Anzahl ein-/ausgehender Kanten betrachtet
- sich zu Nutze macht, dass in einer topologischen Sortierung die linksgerichteten Kanten ein FAS bilden
Qualität abhängig von Auswahl gewählten Knotens, wenn keine Sinks/Sources vorhanden
Implementierung: src/fas/greedy_heuristic.rs

cargo test

Tests der Unter-Algorithmen in gleicher Datei wie Implementierung
Alle FAS-Algorithmen durchlaufen die gleichen Tests
- Definiert in src/fas/feedback_arc_set.rs

Benchmark System

cargo bench

Achtung! Die Benchmarks laufen nicht parallel, sondern nur auf *einer CPU
Gemessen wird die Laufzeit.
Die Güte des Ergebnis (Größe des FAS) im Verhältnis zur Laufzeit wäre ein weiteres Merkmal, wird jedoch nicht gemessen.
Definition: benches/benchmark.rs

Ergebnisse in GitHub unter Actions -> Benchmark Workflow -> Neuesten Run auswählen -> Download unter "Artifacts"
Ergebnisse abgelegt im Quellcode unter benches/report/index.html