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();
	}
    }
}