Animations Beispielprogramm : Dijkstra - Algorithmus

// Animierter Dijkstra 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.*;


public class AnimatedDijkstra 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 colorNotVisited = Color.black;  // Kanten sind schwarz falls nicht betrachtet
  static final Color colorCurrent = Color.red;       // Farbe der Knoten falls gerade betrachtet
  static final Color colorInTree = Color.orange;     // Knoten und Kanten im aktuellen KW-Baum
  static final Color colorNotInTree = Color.black;   // Kante die nicht im KW-Baum sind
  
  // Konstruktor der die Daten aus dem Bundle einliest.
  AnimatedDijkstra(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:
    // hier die Anzahl der Kanten + die Anzahl der Knoten
    manager.setProgressBarLength(D.getNumberOfEdges()+D.getNumberOfVertices());
    
    // Zuerst die Animation abstellen, damit die Farben geaendert werden koennen:
    anim.setAnimationEnabled(false);
    VertexIterator vit=D.createVertexIterator();
    for (; ! vit.atEnd(); vit.increment())
    {
       anim.setVertexColor(vit.getVertex(), Color.white);    // alle Knoten normal faerben
       anim.setVertexLabel(vit.getVertex(), "");             // Jeder Knoten ohne Label
    }
    
    EdgeIterator eit=D.createEdgeIterator();
    for(; !eit.atEnd(); eit.increment()) 
    {
       anim.setEdgeWidth(eit.getEdge(), 2);
       anim.setEdgeColor(eit.getEdge(), colorNotVisited);    // 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() 
  {
    // Rufe den Dijsktra-Algorithmus auf (mit beliebigen Startknoten)
    Dijkstra(D.createVertexIterator().getVertex(),this.D,this.C);
  }
  
  
  
  public void Dijkstra (Vertex s,Digraph D,EdgeRProperty C)
  {
    VertexProperty  l = GraphPropertyFactory.createVertexProperty(D, "distance"); 
    VertexProperty  treeEdge = GraphPropertyFactory.createVertexProperty(D, "treeEdge",null); 
    VertexProperty  heapItem = GraphPropertyFactory.createVertexProperty(D, "heapItem",null); 
    VertexProperty  visited = GraphPropertyFactory.createVertexProperty(D, "visited", Boolean.FALSE); 
    
    PairingHeap     heap = new PairingHeap(new VertexIntPropComparator(l));
    
    
    l.set(s, new Integer(0));
    heapItem.set(s, heap.add(s));
    
    Vertex oldv=s;
    anim.setVertexLabel(s, "0");    // setze Label auf Entfernung
    while(! heap.isEmpty())
    {
       Vertex v = (Vertex) heap.removeMin();
       heapItem.set(v, null);
       anim.setVertexColor(oldv, colorInTree); // markiere abgearbeiteten Knoten
       oldv=v;
       anim.setVertexColor(v, colorCurrent);   // markiere betrachteten Knoten
       manager.stepProgressBar();              // ein Schritt im Algorithmus abgeschlossen
       manager.pause("betrachte Knoten: " + D.toString(v));  // Nachricht zur Information
       
       EdgeIterator eit = D.createOutEdgeIterator(v);
       for (; !eit.atEnd(); eit.increment()) 
       {
	  Vertex w = D.getTarget(eit);
	  if (! ((Boolean) visited.get(w)).booleanValue() )
	  {
	     Edge e = eit.getEdge();
	     int newDist = ((Integer)l.get(v)).intValue() + ((Integer)C.get(e)).intValue();
	     Object oldDist = l.get(w);
	     
	     if (oldDist == null)
	     {
		treeEdge.set(w, e);
		l.set(w, new Integer(newDist));
		heapItem.set(w, heap.add(w));
		treeEdge.set(w, e);
		
		anim.setVertexLabel(w, "" + newDist);
		anim.setVertexColor(w, colorInTree);   // Knoten im Heap
		anim.setEdgeColor(e, colorInTree);     // dazugehoerige Kante
		manager.stepProgressBar();             // ein Schritt im Algorithmus abgeschlossen
		manager.pause("neuer Knoten im Heap: " + D.toString(w) + "  Distanz: " + newDist);
	     }
	     else
	     {
		if (newDist < ((Integer)oldDist).intValue())
		{
		   anim.setEdgeColor((Edge) treeEdge.get(w), colorNotInTree);
		   treeEdge.set(w, e);
		   l.set(w, new Integer(newDist));
		   heap.decreaseKey((Iterator)heapItem.get(w));
		   
		   anim.setVertexLabel(w, "" + newDist);    // setze Label auf entfernung
		   anim.setEdgeColor(e, colorInTree);       // Kante im KW-Baum
		   manager.stepProgressBar();               // ein Schritt im Algorithmus abgeschlossen
		   manager.pause("Knoten aktualisiert: " + D.toString(w) + " Distanz: " + newDist);
		}
	     }
	  }
       }
       visited.set(v, Boolean.TRUE);
    }
  }


  // ---------------------------------------------
  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);
       AnimatedDijkstra instance = new AnimatedDijkstra(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();
    }
  }
}