Animations Beispielprogramm : Prim - Algorithmus
// Animierter Prim-Algorithmus
import gabl.graph.*;
import gabl.prop.*;
import gabl.data.*;
import gabl.util.*;
import gabl.export.*;
import gabl.anim.*;
import java.util.Comparator;
import java.io.*;
import java.awt.*;
// Alle animierten Alogrithmen von "AnimatedAlgorithm" ableiten
public class AnimatedPrim 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 schwarz falls nicht betrachtet
static final Color colorCurrent = Color.blue; // Kanten sind blau falls nicht im Baum
static final Color colorInTree = Color.red; // Knoten sind rot falls im Baum
static final Color colorInHeap = Color.orange; // Knoten sind orange falls im Heap
// Konstruktor der die Daten aus dem Bundle einliest.
AnimatedPrim(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()+G.getNumberOfVertices());
// 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 seinem Label
}
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);
}
// Methode jedes animierten Algorithmus: hier laeuft der eigentliche Algorithmus ab
public void run()
{
// Rufe den Prim-Algorithmus auf
EdgeList mst = Prim(this.G,this.E);
}
public class VertexIntegerPropComparator implements Comparator
{
protected VertexProperty prop;
public VertexIntegerPropComparator(VertexProperty P)
{ prop=P; }
public int compare(Object o1, Object o2)
{
Integer w1=(Integer) prop.get((Vertex) o1);
Integer w2=(Integer) prop.get((Vertex) o2);
return w1.compareTo(w2);
}
}
// -----------------------------------------------------------------
public EdgeList Prim(AdjGraph G, EdgeRProperty E)
{
EdgeList mst = new EdgeList();
if (G.getNumberOfVertices() == 0)
return mst;
VertexProperty key = GraphPropertyFactory.createVertexProperty(G, "key",null);
VertexProperty heapItem = GraphPropertyFactory.createVertexProperty(G, "heapItem",null);
VertexProperty parentEdge = GraphPropertyFactory.createVertexProperty(G, "parentEdge",null);
VertexProperty visited = GraphPropertyFactory.createVertexProperty(G, "visited", Boolean.FALSE);
PairingHeap H = new PairingHeap(new VertexIntegerPropComparator(key));
Vertex start = G.createVertexIterator().getVertex();
// init
visited.set(start, Boolean.TRUE);
anim.setVertexColor(start, colorCurrent); // markiere betrachteten Knoten
manager.stepProgressBar(); // ein Schritt im Algorithmus abgeschlossen
manager.pause("wähle Startknoten: " + G.toString(start)); // Nachricht zur Information
AdjacencyIterator ait = G.createAdjacencyIterator(start);
for (; !ait.atEnd(); ait.increment())
{
Vertex w = ait.getVertex();
Edge e = ait.getEdge();
int Key = ((Integer)E.get(e)).intValue();
parentEdge.set(w, e);
key.set(w, new Integer(Key));
heapItem.set(w, H.add(w));
// Animation:
anim.setVertexColor(w, colorInHeap); // Knoten im Heap
anim.setEdgeColor(e, colorInHeap); // dazugehoerige Kante
manager.stepProgressBar(); // ein Schritt im Algorithmus abgeschlossen
manager.pause("neuer Knoten im Heap: " + G.toString(w)); // Nachricht zur Information
}
// now run ...
Vertex oldv=start;
while (! H.isEmpty())
{
Vertex v = (Vertex)H.removeMin();
Edge e = (Edge)parentEdge.get(v);
heapItem.set(v, null); // for debugging reasons
visited.set(v, Boolean.TRUE);
// Animation:
anim.setVertexColor(oldv, colorInTree); // markiere alten Knoten als in den Baum eingefuegt
anim.setVertexColor(v, colorCurrent); // Knoten im Tree
anim.setEdgeColor(e, colorInTree); // Kante im Baum
oldv=v;
manager.stepProgressBar(); // ein Schritt im Algorithmus abgeschlossen
manager.pause("aktueller Knoten: " + G.toString(v)); // Nachricht zur Information
mst.addLast(e);
ait = G.createAdjacencyIterator(v);
for (; ! ait.atEnd(); ait.increment())
{
if ( ! ( (Boolean)visited.get(ait) ).booleanValue())
{
Vertex w = ait.getVertex();
Object oldKey = key.get(w);
int newKey = ((Integer)E.get(ait.getEdge())).intValue();
if (oldKey == null || newKey < ((Integer)oldKey).intValue())
{
if (oldKey == null)
{
parentEdge.set(w, ait.getEdge());
key.set(w, new Integer(newKey));
heapItem.set(w, H.add(w));
anim.setVertexColor(w, colorInHeap); // Knoten im Heap
anim.setEdgeColor(ait.getEdge(), colorInHeap); // dazugehoerige Kante
manager.stepProgressBar(); // ein Schritt im Algorithmus abgeschlossen
manager.pause("neuer Knoten im Heap: " + G.toString(w)); // Nachricht zur Information
}
else
{
anim.setEdgeColor((Edge) parentEdge.get(w), colorNotVisited); // "vergesse" alte Kante
anim.setEdgeColor(ait.getEdge(), colorInHeap); // markiere neue Kante
parentEdge.set(w, ait.getEdge());
key.set(w, new Integer(newKey));
H.decreaseKey((Iterator)heapItem.get(w));
manager.stepProgressBar(); // ein Schritt im Algorithmus abgeschlossen
manager.pause("Knoten aktualisiert: " + G.toString(w) + " mit Distanz " + newKey);
}
}
}
}
}
return mst;
}
// ---------------------------------------------
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);
AnimatedPrim instance = new AnimatedPrim(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();
}
}
}