Animations Beispielprogramm : Goldberg-Tarjan - Algorithmus
// Animierter Goldberg-Tarjan Algorithmus (Push-Relabel) zum Berechnen eines maximalen Flusses
//
// Marc Pfetsch
//
// Programmieraufgabe Nr. 4
// ADM I : Graphen- und Netzwerkalgorithmen, SS 2001
//
import gabl.graph.*;
import gabl.prop.*;
import gabl.data.*;
import gabl.util.*;
import gabl.export.*;
import gabl.flow.*;
import gabl.anim.*;
import gabl.util.arith.*;
import java.io.*;
import java.awt.*;
public class AnimatedPushRelabelMaxFlow implements AnimatedAlgorithm
{
// f : Praefluss
// C : Kapazitaeten
// excess : Ueberfluss in den Knoten
// psi : Labeling der Knoten
// iter : speichert den aktuellen Adjazenz-Iterator bei einem Knoten
// Q : Liste der aktiven Knoten
// inQ : Speichert ob ein Knoten in Q ist
// D : Original-Digraph
// R : Residual-Netzwerk
// name : Namen der Knoten
Digraph D;
EdgeRProperty C;
Vertex s;
Vertex t;
ArithmeticTraits traits;
VertexRProperty name;
AnimationManager manager; // Animations-Manager (steuert die Fenster etc.)
AnimatedGraphFrame anim; // verwaltet die visuellen Eigenschaften des Programms
static final Color colorVertexNormal = Color.white;
static final Color colorVertexMarked = Color.red; // falls Discharge des Knotens betrachtet wird
static final Color colorVertexST = Color.gray; // Farbe fuer s und t
static final Color colorVertexQ = Color.orange; // falls der knoten aktiv ist
static final Color colorArcPush = Color.red; // Kante zum Schieben
static final Color colorArcNormal = Color.black;
AnimatedPushRelabelMaxFlow(Digraph D, EdgeRProperty C, Vertex s, Vertex t,
AnimatedGraphFrame anim, VertexRProperty name)
{
this.traits = new IntegerInfinityArithmeticTraits();
this.D = D;
this.C = C;
this.s = s;
this.t = t;
this.name = name;
this.anim = anim;
this.manager = new AnimationManager(); // erzeuge neuen Manager
this.manager.setAnimatedAlgorithm(this); // Dies muss immer der letzte Aufruf sein!!!!
}
public void init()
{
int n = D.getNumberOfVertices();
manager.setProgressBarLength(n * n * n); // hoechstens n^3 Operationen!
// Zuerst die Animation abstellen (damit nicht jedesmal ein Repaint geschieht)
anim.setAnimationEnabled(false);
VertexIterator vit = D.createVertexIterator();
for (; ! vit.atEnd(); vit.increment())
{
Vertex v = vit.getVertex();
if (s.equals(v))
{
anim.setVertexColor(v, colorVertexST);
anim.setVertexLabel(v,"s");
}
else
if (t.equals(v))
{
anim.setVertexColor(v, colorVertexST);
anim.setVertexLabel(v, "t");
}
else
{
anim.setVertexColor(v, colorVertexNormal); // alle anderen Knoten normal faerben
anim.setVertexLabel(v, (String)name.get(v));
}
}
EdgeIterator eit = D.createEdgeIterator();
for(; !eit.atEnd(); eit.increment())
{
anim.setEdgeWidth(eit.getEdge(), 2);
anim.setEdgeColor(eit.getEdge(), colorArcNormal); // alle Kanten unbetrachtet
anim.setEdgeLabel(eit.getEdge(), "" + ((Integer) C.get(eit)).intValue()); // Kantengewicht
}
// Animation wieder anstellen.
anim.setAnimationEnabled(true);
anim.repaint();
}
// Methode jedes animierten Algorithmus: hier laeuft der eigentliche Algorithmus ab
public void run()
{
manager.pause("initialisiert.");
// initialisiere mit dem 0-Praefluss
EdgeProperty f = GraphPropertyFactory.createEdgeProperty(D, "Fluss", new Integer(0));
ResidualNetwork N = new ResidualNetwork(D, f, C, this.traits);
computeMaxFlow(this.D, this.s, this.t, this.C, N, f);
}
// ----------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------
// Schiebt moeglichst viel Fluss ueber die Kante r
protected boolean push(ResidualNetwork R, Edge r, VertexProperty excess, EdgeProperty f,
VertexQueue Q, VertexProperty inQ)
{
Vertex v = R.getSource(r);
Vertex w = R.getTarget(r);
// Finde Bottleneckkap. = Minimum von Kap. und Ueberfluss
boolean saturated = false;
int gamma = ((Integer)excess.get(v)).intValue();
int res = ((Integer)R.getResidualCapacity(r)).intValue();
if (gamma >= res)
{
gamma = res;
saturated = true;
}
// Und schieben ....
Edge e = R.getOriginalEdge(r);
anim.setEdgeColor(e, colorArcPush); // faerbe Kante rot
manager.stepProgressBar();
manager.pause("Push: Kante " + (String)name.get(v) + "," + (String)name.get(w) + " um " + gamma);
anim.setEdgeColor(e, colorArcNormal);
int flow = ((Integer)f.get(e)).intValue();
if (R.isForwardEdge(r))
f.set(e, new Integer(flow + gamma));
else
f.set(e, new Integer(flow - gamma));
// Aktualisiere die Ueberfluesse
int ex = ((Integer)excess.get(v)).intValue();
excess.set(v, new Integer(ex - gamma));
ex = ((Integer)excess.get(w)).intValue();
excess.set(w, new Integer(ex + gamma));
// Falls Knoten w noch nicht in Q ist fuege w ein
if ( ! ((Boolean)inQ.get(w)).booleanValue() )
{
if ( (! s.equals(w)) && (! t.equals(w)) )
{
Q.push(w);
inQ.set(w, new Boolean(true));
anim.setVertexColor(w, colorVertexQ);
}
}
return(saturated);
}
// Relabeled den Knoten v
protected void relabel(ResidualNetwork R, Vertex v, VertexProperty psi)
{
// Finde minimales Label auf den adjazenten Knoten (plus 1):
EdgeIterator eit = R.createOutEdgeIterator(v);
Object psi_value = new PlusInfinity();
for (; !eit.atEnd(); eit.increment())
{
Vertex w = R.getTarget(eit);
psi_value = traits.min( psi_value, psi.get(w));
}
psi.set(v, traits.plus( psi_value, new Integer(1)) );
manager.pause("Relabel: Knoten " + (String)name.get(v) + " auf " + traits.toString(psi.get(v)));
}
// Discharge Knoten v
//
// ACHTUNG: damit das Abspeicheren der Iteratoren funktioniert (siehe unten) muss der in
// "iter" abgespeicherte Iterator noch gueltig sein. Dies gilt in der aktuellen Implementation
// (auch wenn sich der Fluss geaendert hat), da bei Konstruktion des Iterators eine Liste der
// monentan im Residual-Netzwerk enthaltenen Kanten erstellt wird. Solange v nicht relabeled
// wird kann dann nichts schlimmes passieren: alte Kanten sind noch zulaessig (sie koennen nur
// von v aus "zerstoert" werden. Neue Kanten sind uninteressant, da sie nicht zulaessig sind
// (v wurde nicht relabeled).
protected void discharge(ResidualNetwork R, Vertex v, EdgeRProperty C, VertexProperty psi,
VertexProperty excess, EdgeProperty f, VertexQueue Q, VertexProperty inQ,
VertexProperty iter)
{
anim.setVertexColor(v, colorVertexMarked);
inQ.set(v, new Boolean(false));
Object psi_v = psi.get(v);
EdgeIterator eit = null;
if (iter.get(v) == null)
eit = R.createOutEdgeIterator(v);
else
eit = ((EdgeIterator) iter.get(v));
// Bemerkung: es gibt immer eine Auskante bei einem aktiven Knoten
boolean saturated = false;
for (; ! eit.atEnd(); eit.increment())
{
Edge e = eit.getEdge();
Edge orig = R.getOriginalEdge(e);
// Falls die Kante e zulaessig ist, schiebe ...
Vertex w = R.getTarget(eit);
Object psi_w = traits.plus(psi.get(w), new Integer(1));
if ( traits.equal(psi_v, psi_w) )
{
saturated = push(R, e, excess, f, Q, inQ);
anim.setVertexLabel(v, "" + traits.toString(excess.get(v)) + "|" + traits.toString(psi_v));
anim.setVertexLabel(w, "" + traits.toString(excess.get(w)) + "|" + traits.toString(psi.get(w)));
anim.setEdgeLabel(orig, "" + traits.toString(f.get(orig)) + "|" + traits.toString(C.get(orig)));
}
if (((Integer)excess.get(v)).intValue() <= 0)
{
if (saturated)
eit.increment();
break;
}
}
// falls alle Auskanten betrachtet worden sind
if ( eit.atEnd() )
iter.set(v, null);
else
iter.set(v, eit); // sonst ... speichere Iterator
// falls v noch aktiv ist fuege Knoten v wieder in Q ein
if (((Integer)excess.get(v)).intValue() > 0)
{
// falls alle Kanten betrachtet wurden -> relabel
if (eit.atEnd())
{
relabel(R, v, psi);
anim.setVertexLabel(v, "" + traits.toString(excess.get(v)) + "|" + traits.toString(psi.get(v)));
}
Q.push(v);
inQ.set(v, new Boolean(true));
anim.setVertexColor(v, colorVertexQ);
}
else
anim.setVertexColor(v, colorVertexNormal);
}
// ----------------------------------------------------------------------
// Hauptroutine
public void computeMaxFlow(Digraph D, Vertex s, Vertex t, EdgeRProperty C, ResidualNetwork R, EdgeProperty f)
{
VertexProperty iter = GraphPropertyFactory.createVertexProperty(R, "iterator", null);
VertexProperty inQ = GraphPropertyFactory.createVertexProperty(D, "in Q", new Boolean(false));
VertexProperty psi = GraphPropertyFactory.createVertexProperty(D, "Label", new Integer(0));
VertexProperty excess = GraphPropertyFactory.createVertexProperty(D, "excess", new Integer(0));
// Liste der aktiven Knoten:
VertexQueue Q = new VertexQueueListImpl();
// Schiebe moeglichst viel Fluss von s zu den adjazenten Knoten
EdgeIterator eit = D.createOutEdgeIterator(s);
for (; ! eit.atEnd(); eit.increment() )
{
int c = ((Integer)C.get(eit)).intValue();
f.set(eit, new Integer(c));
Vertex v = D.getTarget(eit);
int ex = ((Integer) excess.get(v)).intValue();
excess.set(v, new Integer(ex + c));
Q.push(v);
inQ.set(v, new Boolean(true));
anim.setVertexColor(v, colorVertexQ);
}
// Setze Label von s auf Anzahl der Knoten:
int n = D.getNumberOfVertices();
psi.set(s, new Integer(n));
// Initialisiere die Animation ...
anim.setAnimationEnabled(false);
VertexIterator vit = D.createVertexIterator();
for (; ! vit.atEnd(); vit.increment())
{
int ex = ((Integer)excess.get(vit)).intValue();
int psi_v = ((Integer)psi.get(vit)).intValue();
anim.setVertexLabel(vit.getVertex(), "" + ex + "|" + psi_v);
}
eit = D.createEdgeIterator();
for (; ! eit.atEnd(); eit.increment())
{
Edge e = eit.getEdge();
int flow = ((Integer)f.get(e)).intValue();
int cap = ((Integer)C.get(e)).intValue();
anim.setEdgeLabel(e, "" + flow + "|" + cap );
}
anim.setAnimationEnabled(true);
anim.repaint();
manager.pause("Präfluß initialisiert.");
// Nun arbeite solange es aktive Knoten gibt.
while ( ! Q.isEmpty() )
{
Vertex v = Q.pop();
discharge(R, v, C, psi, excess, f, Q, inQ, iter);
}
manager.pause("Präfluß ist zulässig (und optimal). Flusswert: " + traits.toString(excess.get(t)));
}
// ---------------------------------------------
public static void main ( String[] argv )
{
if (argv.length != 1)
{
System.err.println("Error: need filename");
return;
}
GraphFactory factory = new GraphFactory();
String filename = argv[0];
File infile = new File(filename);
try
{
GraphBundle bundle = GraphFormatGML.readGraph(infile, factory);
Digraph D = (Digraph)bundle.getGraph();
EdgeRProperty C = bundle.getEdgeIntegerRProperty("capacity");
VertexRProperty name = bundle.getVertexRProperty("label");
VertexProperty coord = bundle.getVertexProperty("graphics.coords");
// find s and t:
VertexIterator vit = D.createVertexIterator();
Vertex s = null;
Vertex t = null;
for (; ! vit.atEnd(); vit.increment())
{
if ( ((String)name.get(vit)).equals("s") )
s = vit.getVertex();
if ( ((String)name.get(vit)).equals("t") )
t = vit.getVertex();
}
if ( s == null || t == null)
{
System.err.println("Error: could not find s and t in file");
return;
}
AnimatedGraphFrame anim = new AnimatedGraphFrame(bundle);
AnimatedPushRelabelMaxFlow instance = new AnimatedPushRelabelMaxFlow(D, C, s, t, anim, name);
}
catch (NoSuchGraphImplementationException e) {
System.err.println(e.toString());
}
catch (ClassCastException e) {
System.err.println("Error: graph has wrong type '" + e.toString() + "'");
e.printStackTrace();
}
catch (IOException e) {
System.err.println("Error: reading file '" + infile + "' failed.\n" + e);
e.printStackTrace();
}
}
}