Animations Beispielprogramm : Kruskal - Algorithmus
// Animierter Kruskal Algorithmus
import gabl.export.*;
import gabl.graph.*;
import gabl.prop.*;
import gabl.data.*;
import gabl.anim.*;
import java.io.*;
import java.util.Comparator;
import java.awt.*;
// Alle animierten Algorithmen von "AnimatedAlgorithm" ableiten.
class AnimatedKruskal implements AnimatedAlgorithm
{
// globale Daten (damit ein Neustart moeglich ist)
AdjGraph G;
EdgeRProperty E;
AnimationManager manager; // Animations-Manager (steuert die Fenster etc.)
AnimatedGraphFrame anim; // verwaltet die visuellen Eigenschaften des Programms
static final Color colorNotVisited = Color.black; // Kanten sind weiss falls nicht betrachtet
static final Color colorInTree = Color.orange; // " " orange falls im Baum
static final Color colorNotInTree = Color.blue; // " " blau falls nicht im Baum
// Konstruktor der die Daten aus dem Bundle einliest.
AnimatedKruskal(GraphBundle bundle, String filename, AnimatedGraphFrame anim)
{
this.G = (AdjGraph)bundle.getGraph();
this.E = 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:
// hier die Anzahl der Kanten
manager.setProgressBarLength(G.getNumberOfEdges());
// Zuerst die Animation abstellen, damit die Farben geaendert werden koennen:
anim.setAnimationEnabled(false);
VertexIterator vit=G.createVertexIterator();
for (; ! vit.atEnd(); vit.increment())
{
anim.setVertexColor(vit.getVertex(), Color.white); // alle Knoten normal faerben
anim.setVertexLabel(vit.getVertex(), G.toString(vit.getVertex())); // Jeder Knoten mit Index
}
EdgeIterator eit=G.createEdgeIterator();
for(; !eit.atEnd(); eit.increment())
{
anim.setEdgeWidth(eit.getEdge(), 2);
anim.setEdgeColor(eit.getEdge(), colorNotVisited); // alle Kanten unbetrachtet
anim.setEdgeLabel(eit.getEdge(), "" + ((Integer) E.get(eit.getEdge())).intValue()); // Kantengewicht
}
// Animation wieder anstellen.
anim.setAnimationEnabled(true);
}
// Vergleichen fuer das Sortieren
public class EdgeIntegerWeightComparator implements Comparator
{
protected EdgeRProperty prop;
public EdgeIntegerWeightComparator(EdgeRProperty P)
{ prop=P; }
public int compare(Object o1, Object o2)
{
Integer w1=(Integer) prop.get((Edge) o1);
Integer w2=(Integer) prop.get((Edge) o2);
return w1.compareTo(w2);
}
}
// Methode jedes animierten Algorithmus: hier laeuft der eigentliche Algorithmus ab
public void run()
{
// Rufe den Kruskal-Algorithmus auf
EdgeList mst = Kruskal(this.G,this.E);
}
public EdgeList Kruskal(AdjGraph G, EdgeRProperty E)
{
int n = G.getNumberOfVertices();
int m = G.getNumberOfEdges();
EdgeList L = new EdgeList();
// Packe Kanten in Array und sortiere
Edge [] edges = new Edge [m];
EdgeIterator eit=G.createEdgeIterator();
for (int i=0; i < m; ++i,eit.increment())
edges[i]=eit.getEdge();
java.util.Arrays.sort(edges, new EdgeIntegerWeightComparator(E));
// Erzeuge Instanz der Set-Union Klasse
DisjointVertexSetUnion U=new DisjointVertexSetUnion(G);
DisjointVertexSetUnion.SetRepresentative r1,r2;
// Nun gehe Kanten der Reihe nach durch
for (int i=0; i < m; ++i)
{
Vertex v1 = G.getSource(edges[i]);
Vertex v2 = G.getTarget(edges[i]);
// falls v1 schon im Wald enthalten ist
if (U.hasSet(v1))
r1=U.find(v1);
else // sonst fuege v1 ein
r1 = U.createSet(v1);
// falls v2 schon im Wald enthalten ist
if (U.hasSet(v2))
r2=U.find(v2);
else // sonst fuege v2 ein
r2 = U.createSet(v2);
// Falls v1 und v2 nicht in der gleichen Komponente enthalten sind
if (! r1.equals(r2))
{
U.union(r1,r2);
L.addLast(edges[i]);
anim.setEdgeColor(edges[i], colorInTree); // Kante im Baum
manager.stepProgressBar(); // ein Schritt im Algorithmus abgeschlossen
manager.pause("eingefuegte Kante: " + G.toString(edges[i])); // Nachricht zur Information
// falls wir einen Baum haben breche ab.
if (L.size() == n-1)
return L;
}
else // anderenfalls wuerde ein Kreis entstehen
{
anim.setEdgeColor(edges[i], colorNotInTree); // Kante nicht im Baum
manager.stepProgressBar(); // ein Schritt im Algorithmus abgeschlossen
manager.pause("nicht eingefuegte Kante: " + G.toString(edges[i])); // Nachricht zur Info
}
}
return L;
}
// ---------------------------------------------
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);
AnimatedKruskal instance = new AnimatedKruskal(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();
}
}
}