Animations Beispielprogramm : Minimum Mean-Cycle - Algorithmus



// Animierter MinimumMeanCycle-Algorithmus zum Berechnen eines Zykels mit minimalem mittlerem Gewicht
//
// Marc Pfetsch
//
// Programmieraufgabe Nr. 3
// ADM I : Graphen- und Netzwerkalgorithmen, SS 2001
//

import gabl.graph.*;
import gabl.prop.*;
import gabl.data.*;
import gabl.util.*;
import gabl.export.*;
import gabl.anim.*;
import gabl.util.arith.*;

import java.io.*;
import java.awt.*;



public class AnimatedMinimumMeanCycle implements AnimatedAlgorithm
{
    Digraph         D;
    EdgeRProperty   C;
  
    AnimationManager manager;   // Animations-Manager (steuert die Fenster etc.)
    AnimatedGraphFrame anim;    // verwaltet die visuellen Eigenschaften des Programms
  
    static final Color colorNormal  = Color.white;
    static final Color colorProcess = Color.orange;
    static final Color colorArcParent = Color.red;
    static final Color colorArcNormal = Color.black;
    
    // Konstruktor der die Daten aus dem Bundle einliest.
    AnimatedMinimumMeanCycle(GraphBundle bundle, String filename, AnimatedGraphFrame anim)
    {
	// Digraphen einlesen geht genauso wie bei ungerichteten Graphen
	// man muss nur anders casten:
	this.D = (Digraph)bundle.getGraph();
	this.C = bundle.getEdgeIntegerRProperty("weight"); 
	this.anim = anim;
	this.manager = new AnimationManager();   // erzeuge neuen Manager
	this.manager.setAnimatedAlgorithm(this); // Dies muss immer der letzte Aufruf sein!!!!
    }
  
    // Methode jedes animierten Algorithmus zum Initialisieren (setzen der Farben ...)
    public void init() 
    {
	// Im Fenster der Animationssteuerung ist unten eingeblendet wie lange der
	// Algorithmus voraussichtlich noch braucht. Hier setzt man die maximale
	// Anzahl von Schritten die der Algorithmus braucht:
	manager.setProgressBarLength(D.getNumberOfVertices());
    
	// Zuerst die Animation abstellen (damit es schneller geht)
	anim.setAnimationEnabled(false);
	VertexIterator vit=D.createVertexIterator();
	for (; ! vit.atEnd(); vit.increment())
	{
	   anim.setVertexColor(vit.getVertex(), colorNormal);    // alle Knoten normal faerben
	   anim.setVertexLabel(vit.getVertex(), D.toString(vit.getVertex())); 
	}
    
	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.getEdge())).intValue()); // Kantengewicht
	}
	// Animation wieder anstellen.
	anim.setAnimationEnabled(true);
    }
  
    // Methode jedes animierten Algorithmus: hier laeuft der eigentliche Algorithmus ab
    public void run() 
    {
	manager.pause("initialisiert.");
	// Rufe den Minimum Mean Cycle-Algorithmus auf
	EdgeList L=minimumMeanCycle(this.D,this.C);
    }
  
    
    // Die eigentliche Routine.
    public EdgeList minimumMeanCycle(Digraph D,EdgeRProperty C)
    {
	// Benutze Traits um sicher mit unendlich rechnen zu koennen:
	ArithmeticTraits intTraits = new IntegerInfinityArithmeticTraits();   // fuer die Integer Operationen
	ArithmeticTraits doubleTraits = new DoubleInfinityArithmeticTraits(); // fuer die Double Operationen

	int n = D.getNumberOfVertices();
	VertexProperty [] P = new VertexProperty [n+1];
	VertexProperty [] F = new VertexProperty [n+1];
	F[0] = GraphPropertyFactory.createVertexProperty(D, "F",new Integer(0));
	for (int i=1; i <= n; ++i)
	{
	   F[i] = GraphPropertyFactory.createVertexProperty(D, "F",new PlusInfinity());
	   P[i] = GraphPropertyFactory.createVertexProperty(D, "P",null);
	}

	// Zeige erste Iteration an:
	VertexIterator vit = D.createVertexIterator();
	for (; ! vit.atEnd(); vit.increment())
	    anim.setVertexLabel(vit.getVertex(),"0");

	boolean acyclic = true;
	for (int k=1;k <= n;++k)
	{
	   vit=D.createVertexIterator();
	   for (; ! vit.atEnd(); vit.increment())
	   {
	      Vertex x = vit.getVertex();
	      EdgeIterator eit = D.createInEdgeIterator(x);
	      for (; ! eit.atEnd(); eit.increment())
	      {
		 Vertex w = D.getSource(eit);
		 Edge e = eit.getEdge();
		 Object value = intTraits.plus( F[k-1].get(w), C.get(e) );
		 if ( intTraits.lessThan(value, F[k].get(x)) )
		 {
		    F[k].set(x,value);
		    P[k].set(x,e);
		    acyclic = false;
		 }
	      }
	   }
	   // Animation:
	   EdgeIterator eit = D.createEdgeIterator();
	   for (; ! eit.atEnd(); eit.increment())
	       anim.setEdgeColor( eit.getEdge(), colorArcNormal );
	   vit = D.createVertexIterator();
	   for (; ! vit.atEnd(); vit.increment())
	   {
	      Vertex x = vit.getVertex();
	      if (P[k].get(vit) != null)
		  anim.setEdgeColor((Edge)P[k].get(x), colorArcParent);
	      anim.setVertexLabel(x, intTraits.toString(F[k].get(x)));
	      anim.setVertexColor(x, colorProcess);
	   }
	   manager.stepProgressBar();
	   manager.pause("Iteration " + k);
	}

	if ( acyclic )
	{
	   manager.pause("Digraph is acyclic");
	   return null;
	}

	// Finde Knoten x:
	Object infinity = new PlusInfinity();
	Object minw = new PlusInfinity();
	Vertex x = null;
	vit=D.createVertexIterator();
	for (; ! vit.atEnd(); vit.increment())
	{
	   Vertex v = vit.getVertex();
	   Object maxw = new MinusInfinity();
	   if ( ! intTraits.equal(F[n].get(v), infinity ) )
	   {
	      int fn = ((Integer) F[n].get(v)).intValue();
	      for (int k=0;k < n;++k)
	      {
		 if ( ! intTraits.equal(F[k].get(v), infinity) )
		 {
		    int fk = ((Integer) F[k].get(v)).intValue();
		    double numerator = fn - fk;
		    double denominator = n - k;
		    Double w = new Double(numerator / denominator);
		    if ( doubleTraits.lessThan(maxw, w) )
			maxw = w;
		 }
	      }
	      if ( doubleTraits.greaterThan(minw,maxw) )
	      {
		 minw = maxw;
		 x = v;
	      }
	   }
	   manager.setMessage("Knoten " + D.toString(v) + " hat Wert " + doubleTraits.toString(maxw));
	}
	manager.pause("minimalem (endlichen) Wert " + doubleTraits.toString(minw) + " hat Knoten " +  D.toString(x));

	// Konstruiere Zykel:
	VertexProperty seen=GraphPropertyFactory.createVertexProperty(D, "seen", null);
	int k=n;
	seen.set(x, new Integer(k));
	// suche nach dem ersten Knoten der doppelt auftritt
	while ( true )
	{
	   Edge p = (Edge) P[k].get(x);
	   x = D.getSource(p);
	   if (seen.get(x) != null)
	       break;
	   seen.set(x, new Integer(k));
	   --k;
	}
	// konstruiere Zykel
	EdgeList Cycle = new EdgeList();

	int i=((Integer) seen.get(x)).intValue();
	for (; i >= k;--i)
	{
	   Edge p = (Edge) P[i].get(x);
	   x = D.getSource(p);
	   Cycle.addLast(p);
	}

	EdgeIterator eit=D.createEdgeIterator();
	for(; !eit.atEnd(); eit.increment()) 
	    anim.setEdgeColor(eit.getEdge(), colorArcNormal);
	eit=Cycle.createIterator();
	for (; ! eit.atEnd(); eit.increment())
	    anim.setEdgeColor(eit.getEdge(), colorArcParent);
	manager.pause("Zykel mit minimalem mittlerem Gewicht wird angezeigt!");

	return Cycle;
    }


    // ---------------------------------------------
    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);	  
	   AnimatedGraphFrame anim = new AnimatedGraphFrame(bundle);
	   AnimatedMinimumMeanCycle instance = new AnimatedMinimumMeanCycle(bundle, filename, anim);
	}
	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();
	}
    }
}