Dijkstra.java

/*
 *     YAV (Yet another Visualiser)
 *     (c) 2004 by Robin Quast
 *    Version 1.0 (04.03.2004)
 *    
 *  erstellt im Rahmen der Diplomarbeit
 * "Theorie und Java- Realisierung
 *  ausgewählter Algorithmen zur
 *  Bestimmung kürzester Wege in Graphen"
 *
 *  betreut durch Prof. Dr. Lenze
 *  an der Fachhochschule Dortmund
 *  im SS 2003/ WS 2003/2004
 *
 *  @(#)Dijkstra.java  1.1 04/03/09
 */

import java.*;
import java.util.Vector;
import java.util.Enumeration;
import java.io.*;
import java.util.Calendar;

/** Diese Klasse stellt Routinen zur Verfügung, die Anhand einer Adjazenzliste
 * den kürzesten Weg von einem Startknoten berechnet. Optional kann
 * ein Zielknoten vorgegeben werden.
 */
public class Dijkstra 
extends Adjazenzliste {
  
  int knotenanzahl = 0;
  int[] vorgaenger = new int[knotenanzahl+1];
  Vector knotenvektor = new Vector();
  Heap h = new Heap();
  Enumeration heap_enum = knotenvektor.elements();
  Node source  = new Node();
  Node destination = new Node();
  Node last_inspected_node;
  long used_time;
  int compare_counter=0;
  
  /** Konstruktor, der initiale Werte vergibt. 
   */
  public Dijkstra() {
    super();
    last_inspected_node = new Node();
  }

  /** Konstruktor, der initiale Werte vergibt und die Adjazenzliste übernimmt.
   */  
  public Dijkstra(Adjazenzliste al) {
    super();
    adlist = al.getAdlist();
    last_inspected_node = new Node();
  }
  
  /** Methode, die prüft, ob der Heap leer ist.
   */
  public boolean heapIsEmpty() {
    return h.isEmpty();
  }
    
  /** Methode, die die Adjazenzliste neu zuordnet.
   */
  public void updateAdjazenzliste(Adjazenzliste al) {
    adlist = al.getAdlist();
  }
  
  /** Startet den Algorithmus, für die Berechnung eines kürzesten Weges
   * von dem Knoten <i>start</I> nach <i>end</I> (beides Objekte der 
   * Klasse GraphNode). Dabei darf der Knoten <i>end</I> auch null sein.
   * Der Startknoten darf nicht null sein. Das Ergebnis w&auml;re in diesem 
   * Falle <I>null</I>.
   */
   public Vector shortestPath (GraphNode start,GraphNode end) {    
    if (start==nullreturn null;
    if (end==nullreturn shortestPath(start.getNode(),null);
    return shortestPath(start.getNode(),end.getNode());
  }
  
  /** Startet den Algorithmus, f&uuml;r die Berechnung eines k&uuml;rzesten Weges
   * von dem Knoten <i>start</I> nach <i>end</I> (beides Objekte der 
   * Klasse Node). Dabei darf der Knoten <i>end</I> auch null sein.
   * Der Startknoten darf nicht null sein. Das Ergebnis w&auml;re in diesem 
   * Falle <I>null</I>.
   */
  public Vector shortestPath (Node start,Node end) {    
    source = new Node(start);
    if (end!=nulldestination = new Node(end)
    else destination = null;
    
    compare_counter=0;
    last_inspected_node = new Node();  
    used_time=getTimeInMillis();
    //if (!(source==null) || (destination==null)) {
      if (!(source==null)) {
      initialiseDijkstra();
      // ermittle den k&uuml;rzesten Weg von start Knoten 
       while (!(h.isEmpty())) {       
        HeapElement min=h.findAndRemoveMin();
        Vector kanten = getEdgesWithTail(min.getNode());
        if (!(min.getKey()==Integer.MAX_VALUE)) {
           Enumeration kanten_enum = kanten.elements();
                          
           while (kanten_enum.hasMoreElements()) { 
             Object tmp_element=kanten_enum.nextElement();
             Edge tmp_edge = (Edgetmp_element;  // Kante hat den Knoten tail = min.getNode() !
             Node head = tmp_edge.getHead();
    
             int cost = min.getKey()+tmp_edge.getCost();
             compare_counter++;
             if (cost<h.getCost(head)) {
               h.setCost(head,cost);
               vorgaenger[head.getValue()]=min.getNodeValue();
             }
           }
           //compare_counter++;
        }      
      }
    }
    used_time=getTimeInMillis()-used_time;
    return getShortestPathEdgeVector();  
  }

  /** Liefert die Zeit in Millisekunden, damit die Dauer der letzten
   *  Algorithmusaktion gemessen werden kann.
   */
   private long getTimeInMillis() {
     Calendar cal = Calendar.getInstance();
     return cal.getTimeInMillis();
   }

  /** Startet den Algorithmus im Step Modus, f&uuml;r die Berechnung eines k&uuml;rzesten Weges
   * von dem Knoten <i>start</I> nach <i>end</I> (beides Objekte der 
   * Klasse GraphNode). Dabei darf der Knoten <i>end</I> auch null sein.
   * Der Startknoten darf nicht null sein. Das Ergebnis w&auml;re in diesem 
   * Falle <I>null</I>.
   */
  public Vector startShortestPathStepModus (GraphNode start,GraphNode end) {    
    if (start==nullreturn null;
    if (end==nullreturn startShortestPathStepModus(start.getNode(),null);
    return startShortestPathStepModus(start.getNode(),end.getNode());
  }

  /** Startet den Algorithmus im Step Modus, f&uuml;r die Berechnung eines k&uuml;rzesten Weges
   * von dem Knoten <i>start</I> nach <i>end</I> (beides Objekte der 
   * Klasse GraphNode). Dabei darf der Knoten <i>end</I> auch null sein.
   * Der Startknoten darf nicht null sein. Das Ergebnis w&auml;re in diesem 
   * Falle <I>null</I>. Es wird nur die Initialisierung des Algorithmus ausgef&uuml;hrt.
   */
  public Vector startShortestPathStepModus (Node start,Node end) {    
    source = new Node(start);
    if (end!=nulldestination = new Node(end);
    else destination=null;
    last_inspected_node = new Node();
    compare_counter=0;
    
    used_time=getTimeInMillis();
    if (!(source==null)) {
      initialiseDijkstra();  
    }
    used_time=getTimeInMillis()-used_time;
    return getShortestPathEdgeVector();  
  }

  /** Methode, die den Zugriff auf den Heap erm&ouml;glicht.
   */
  public Heap getHeap() {
    return h;
  }
  
  /** Liefert die Vorg&auml;ngerliste.
   */
  public int[] getPredecessor() {
    return vorgaenger;
  }
  
  /** Gibt die L&auml;nger der Vorg&auml;ngerliste zur&uuml;ck.
   */
  public int getPredecessorLength() {
    return vorgaenger.length;
  }

  /** Gibt den Knoten zur&uuml;ck, dessen Kanten zuletzt untersucht wurden. Dieser
   * Knoten wurde im letzten Algorithmusschritt aus dem Heap genommen.
   */
  public Node getLastInspectedNode() {
    return last_inspected_node;
  }

  /** Gibt die verbrauchte Zeit in Millisekunden an, die der letzte 
   * Algorithmusschritt ben&ouml;tigt hat. Dies kann der Ablauf des ganzen 
   * Algorithmus gewesen sein, oder aber ein einzelner Algorithmusschritt.
   */
  public long getUsedTime(){
    return used_time;
  }  

  /** Gibt zur&uuml;ck, wie viele Vergleiche der Algorithmus bisher ben&ouml;tigt hat.
   */
  public int getCompareCounter() {
    int rc=compare_counter;
    return rc;
  }
  
  /** F&uuml;hrt einen Schritt im Algorithmus aus. Dabei werden die einzelnen 
   * Variablen, wie die Anzahl der Vergleiche oder die verbrauchte Zeit 
   * aktualisiert.
   */   
  public Vector stepShortestPath (){
       if (!(h.isEmpty())) { 
         used_time=getTimeInMillis();
        HeapElement min=h.findAndRemoveMin();
        last_inspected_node = new Node(min.getNode());
        if (!(min.getKey()==Integer.MAX_VALUE)) {
          Vector kanten = getEdgesWithTail(min.getNode());
  
           Enumeration kanten_enum = kanten.elements();
                          
           while (kanten_enum.hasMoreElements()) { 
             Object tmp_element=kanten_enum.nextElement();
             Edge tmp_edge = (Edgetmp_element;  // Kante hat den Knoten tail = min.getNode() !
             Node head = tmp_edge.getHead();
    
             int cost = min.getKey()+tmp_edge.getCost();
             compare_counter++;
             if (cost<h.getCost(head)) {
               h.setCost(head,cost);
               vorgaenger[head.getValue()]=min.getNodeValue();
             }
           }
        }
        used_time=getTimeInMillis()-used_time;
        //compare_counter++;
      }  
    return getShortestPathEdgeVector();
  }

  /** Diese Methode gibt einen Vector zur&uuml;ck, der die Kanten des k&uuml;rzesten Weges,
   * bzgl. der Vorganben enth&auml;lt.
   */
  private Vector getShortestPathEdgeVector () {
    Vector kuerzester_weg = new Vector();
    if (source==nullreturn kuerzester_weg;
    if (destination==null) {
      return getShortestPathEdgeVectorForSource();
    }
    if (destination.getValue()==-1) {
      return getShortestPathEdgeVectorForSource();
    }
    // hier ist source!=null und destination !=null
    // k&uuml;rzesten Weg f&uuml;r die Ausgabe aufbereiten
    int i_knoten = destination.getValue();
    kuerzester_weg.addAll(getShortestPathEdgeVectorForDestination(i_knoten));
    return kuerzester_weg;
  }

  /** Wurde bei der k&uuml;rzesten Wege- Berechnung kein Zielknoten vorgegeben
   * wird diese Routine die k&uuml;rzesten Wege zu allen Knoten zur&uuml;ckgeben.
   */
  private Vector getShortestPathEdgeVectorForSource() {
      Vector kuerzester_weg = new Vector();
      int maxnnum = getMaxNodeNumber();      
      for (int i=0;i<maxnnum+1;i++) {
        kuerzester_weg.addAll(getShortestPathEdgeVectorForDestination(i));
      }
      return kuerzester_weg;      
    
  }

  /** Gibt den k&uuml;rzesten Weg von <i>source</I> nach <i>node</I> zur&uuml;ck.
   */
  private Vector getShortestPathEdgeVectorForDestination(int node) {
    Vector kw=new Vector();
    while (node!=source.getValue() && vorgaenger[node]!=-1) {
      Edge tmp_e=find(vorgaenger[node],node);
      if (tmp_e!=nullkw.add(tmp_e);
      node=vorgaenger[node];
    }
    return kw;
  }

  /** Initialisiert die Algorithmuseinstellungen. Z.B. leeren des Heaps, 
   * setzen der Knotenliste,...
   */
  private void initialiseDijkstra() {
    // variablen initialisieren
    knotenanzahl = getMaxNodeNumber();
    vorgaenger= new int[knotenanzahl+1];
    
    for (int i=0; i<knotenanzahl+1;i++vorgaenger[i]=-1;
    
    knotenvektor = getNodeVector();
    h = new Heap();
     heap_enum = knotenvektor.elements();
     
     //   Vorgaenger der Knoten und heap initialisieren
     while (heap_enum.hasMoreElements()) { 
       Object tmp_element=heap_enum.nextElement();
       Node tmp_node = (Nodetmp_element;
       // Knoten zum heap hinzuf&uuml;gen
       if (tmp_node.equal(source)) h.add(new HeapElement(tmp_node,0))// der k&uuml;rzeste Weg vom Startnoten zu sich selber ist 0
       else h.add(new HeapElement(tmp_node,Integer.MAX_VALUE));// Integer.MAX_VALUE bedeutet hier, dass der Weg zu diesem Element noch nicht berechnet wurde, bzw. es wurde noch kein Weg gefunden, unter Umst&auml;nden gibt es auch zu diesem Knoten keinen Weg
    }
  }

}