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