BellmanFordMoore.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
 *
 *  @(#)BellmanFordMoore.java  1.0 04/03/09
 */
 
import java.*;
import java.util.Vector;
import java.util.Enumeration;
import java.io.*;
import java.util.Calendar;

/** Diese Klasse stellt den BellmanFordMoore Algorithmus zur Ermittlung 
 * kürzester Wege in Graphen auf Basis der Adjazenzliste zur Verfügung.
 * Es stehen 2 Modis zur Verfügung. Der Step und der Startmodus. Der Stepmodus
 * führt einen Schritt im Algorithmus aus. Dazu müssen sich bestimmte Eigenschaften
 * gemerkt werden, wie z.B. wie der Heap aussieht. 
 */
public class BellmanFordMoore
extends Adjazenzliste {
  
  int knotenanzahl = 0;
  int[] vorgaenger = new int[knotenanzahl+1];
  Vector knotenvektor = new Vector();
  Heap h = new Heap();
  HeapElement[] ha = null;
  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 BellmanFordMoore() {
    super();
    last_inspected_node = new Node();
  }
  
  /** Konstruktor, der die Adjazenzliste mit der übergebenen
   * Liste initialisiert.
   */
  public BellmanFordMoore(Adjazenzliste al) {
    super();
    adlist = al.getAdlist();
    last_inspected_node = new Node();
  }
  
  /** Methode, die zurückgibt, ob der Heap (ein Objekt der Klasse Heap)
   * leer ist. Ergebnis ist <I>true</I>, wenn h leer ist und <I>false</i> 
   * sonst.
   */
  public boolean heapIsEmpty() {
    return h.isEmpty();
  }
    
  /** Methode, die die Adjazenzliste neu setzt. Diese wird auf die 
   * &uuml;bergebene Referenz gesetzt.
   */
  public void updateAdjazenzliste(Adjazenzliste al) {
    adlist = al.getAdlist();
  }

  /** 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 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) ) {
      initialiseBellmanFordMoore();
      // ermittle den k&uuml;rzesten Weg von start Knoten 
       while (!(h.isEmpty())) {       
        HeapElement fe=h.findAndRemoveFirstElement();
        int c=((HeapElement)ha[fe.getNodeValue()]).getKey();
        Vector kanten = getEdgesWithTail(fe.getNode());
        if (kanten!=null) { // sind Kanten, also Nachbarn vorhanden           Enumeration kanten_enum = kanten.elements();
           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 = fe.getNode() !
             Node head = tmp_edge.getHead();
    
             int cost = (ha[fe.getNodeValue()]).getKey()+tmp_edge.getCost();
             compare_counter++;
             if (cost<((HeapElement)ha[head.getValue()]).getKey()) {
               vorgaenger[head.getValue()]=fe.getNodeValue();
               h.addOrReplace(new HeapElement(head,cost));
               ha[head.getValue()]=new HeapElement(head,cost);
             }
           }
        }  
        kanten=null;    
      }
    }
    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) ) {
      initialiseBellmanFordMoore();  
    }
    used_time=getTimeInMillis()-used_time;
    return getShortestPathEdgeVector();  
  }

  /** Methode, die den Zugriff auf den Heap erm&ouml;glicht.
   */
  public Heap getHeap() {
    return h;
  }
  
  /** Methode, die die Vorg&auml;ngerliste des Algorithmus zur&uuml;ckgibt, damit diese
   * angezeigt werden kann.
   */
  public int[] getPredecessor() {
    return vorgaenger;
  }
  
  /** Methode, die die L&auml;nge des Vorg&auml;ngerarrays zur&uuml;ckgibt.
   */
  public int getPredecessorLength() {
    return vorgaenger.length;
  }

  /** Gibt den zuletzt untersuchten Knoten zur&uuml;ck, dessen Kanten in dem 
   * Algorithmusschritt untersucht wurden.
   */
  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())) { 
        HeapElement fe=h.findAndRemoveFirstElement();
        last_inspected_node = new Node(fe.getNode());
        int c=((HeapElement)ha[fe.getNodeValue()]).getKey();
        Vector kanten = getEdgesWithTail(fe.getNode());
        if (kanten!=null) { // sind Kanten, also Nachbarn vorhanden           Enumeration kanten_enum = kanten.elements();
           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 = fe.getNode() !
             Node head = tmp_edge.getHead();
    
             int cost = (ha[fe.getNodeValue()]).getKey()+tmp_edge.getCost();
             compare_counter++;
             if (cost<((HeapElement)ha[head.getValue()]).getKey()) {
               vorgaenger[head.getValue()]=fe.getNodeValue();
               h.addOrReplace(new HeapElement(head,cost));
               ha[head.getValue()]=new HeapElement(head,cost);
             }
           }

        }  
      }  
    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 initialiseBellmanFordMoore() {
    // variablen initialisieren
    knotenanzahl = getMaxNodeNumber();
    vorgaenger= new int[knotenanzahl+1];
    ha = new HeapElement[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
    h.add(new HeapElement(source,0))// der k&uuml;rzeste Weg vom Startnoten zu sich selber ist 0
     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))) {
         ha[tmp_node.getValue()] new HeapElement(tmp_node,Integer.MAX_VALUE);
       else {
         ha[tmp_node.getValue()] new HeapElement(tmp_node,0);// startknoten mit 0 einfuegen
       }
    }
    
  }

}