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