GoldbergTarjan: Überschuss, direkt nach Source

Moderator: Effiziente Graphenalgorithmen

hanneswernery
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 30. Dez 2012 15:26

GoldbergTarjan: Überschuss, direkt nach Source

Beitrag von hanneswernery » 28. Feb 2015 20:30

Hallo

ich bearbeite gerade die Implementierung des GoldbergTarjan Algorithmus. Mir ist dabei das Problem aufgefallen, dass es zu einem Überschuss an einem Knoten kommen kann, der nicht mehr abfließen kann.

Nach Induktionsbasis wird die Höhe(S) auf |V| gesetzt, alle anderen Höhen auf 0.
Alle herausgehenden Kanten aus S werden auf maximale Kapazität hochgesetzt, alle anderen Kanten auf 0.

Hier mein Problem. Mein "GraphGenerator" setzt die Kantenkapazität von S herausgehend (und in T hereingehend) auf Integer.Max, um einen möglichst hohen Fluss auf dem erstellen Graph zu erlauben. Offensichtlich kann dieser Überschuss am ersten Nachbarn von S (wir nennen ihn v) nicht durch den restlichen Graphen. Und zurückfließen kann er auch nicht, da Höhe(S)=|V| und Höhe(v) ist nicht |V|+1 (Bedingung: genommene Kante(v -> w) muss "erlaubt sein", das heisst Höhe(v) = Höhe(w)+1). Die Höhe der Knoten wird ja auch nicht beliebig hoch gesetzt, sondern nur Min(aller möglicher Nachbarn)+1.

Ich dachte, das ließe sich beheben, indem ich die aus S herausgehenden Kanten auf das normale Kapazitäten-Maximum setze. Der Fluss ist nun aber entweder trivial, da nur eine begrenzte Anzahl Kanten aus S herausgehen und der Gesamtfluss dann X mal Kapazitäten-Maximum (Summe aus S herausgehend) ist, oder es immer noch zu viel Fluss für den restlichen Graphen ist und der Überschuss irgendwo nicht abfließen kann (keine Terminierung)..
Wo ist hier mein Denkfehler? :|

hanneswernery
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 30. Dez 2012 15:26

Re: GoldbergTarjan: Überschuss, direkt nach Source

Beitrag von hanneswernery » 1. Mär 2015 19:29

Ich habe es behoben, indem ich die Berechnung der Höhe an einem Überschussknoten korrigiert habe:
neue Höhe = Min(aller möglicher Nachbarn im Residualgraphen)+1

Um auf mein Problem konkret zu antworten: wenn nun ein Knoten, egal ob direkt nach der Source oder zwischendrin, festhängt und nichts abfließen kann, wird die Höhe nun tatsächlich so angepasst, dass es zumindest irgendwo zurückfließen kann. Vorher hat immer ein Nachbarknoten die Höhe blockiert, obwohl er als Abflusskandidat gar nicht in Frage kommt (war nicht im Residualgraphen). Diese Knoten werden nun nicht mehr bei der Höhenberechnung betrachtet.

Antworten

Zurück zu „Effiziente Graphenalgorithmen“