FloydWarshall.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
 *
 *  @(#)FloydWarshall.java  1.0 04/03/09
 */
/* Floyd Warshall Algorithmus zur Ermittlung kürzester Wege in Graphen */
import java.*;
import java.util.Vector;
import java.util.Enumeration;
import java.io.*;
import java.util.Calendar;

/** Diese Klasse dient zur Ermittlung der kürzesten Wege zwischen allen Knoten.
 * Als Datenbasis wird die Adjazenzmatrix (Elternklasse) genutzt. Den Algorithmus 
 * kann man im Step Modus ablaufen lassen, oder man hat die Möglichkeit diesen 
 * einmal durchlaufen zu lasse. Grundvorraussetzung für die Matrizendarstellung 
 * ist, dass die Knoten fortlaufend nummeriert sind.
 */
public class FloydWarshall
extends Adjazenzmatrix {
  
  int knotenanzahl = 0;
  long used_time;
  Matrix pred_matrix = new Matrix()// Vorgängermatrix
  // die Adjazenzmatrix wird hinterher zur Distanzmatrix und enthält nach
  // ablauf des Algorithmus die Distanzen der kürzesten Wege
  int compare_counter=0;
  // Variable, die angibt, ob der Algorithmus seinen letzten Schritt
  // ausgeführt hat
  boolean reached_end=true
  
  Adjazenzliste adlist = null;
  
  Node source  = new Node();
  Node destination = new Node();
  Node last_inspected_node=new Node();
  
  int i=0;
  int j=0;
  int k=0;

  /** Konstruktor, der die Werte initialisiert.
   */  
  public FloydWarshall() {
    super();
    initialiseFloydWarshall();
  }
  
  /** Konstruktor, der den Inhalt der Adjazenzliste in die 
   * Adjazenzmatrix übernimmt.
   */
  public FloydWarshall(Adjazenzliste al) {
    super();
    setAdjazenzmatrix(al);
  }
    

  /** Setzen der Adjazenzmatrix anhand der Adjazenzliste.
   */
  public void setAdjazenzmatrix(Adjazenzliste al) {
    super.setAdjazenzmatrix(al);
    adlist=al;
    initialiseFloydWarshall();
  }

    
  /** 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 d&uuml;rfen die Knoten <i>start</i> und <i>end</I> 
   * auch null sein, da der Algorithmus die k&uuml;rzesten Wege zwischen allen 
   * Knoten ermittelt.
   */    
  public Vector shortestPath (GraphNode start,GraphNode end,Adjazenzliste al) {    
    if (start!=null)source = new Node(start.getNode());
    else source=null;
    if (end!=nulldestination = new Node(end.getNode());
    else destination=null;

    if (al==nullreturn new Vector();

    return shortestPath(source,destination,al);
  }
    
  /** 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 d&uuml;rfen die Knoten <i>start</i> und <i>end</I> 
   * auch null sein, da der Algorithmus die k&uuml;rzesten Wege zwischen allen 
   * Knoten ermittelt.
   */    
  public Vector shortestPath (Node start,Node end,Adjazenzliste al) {    
    if (start!=null)source = new Node(start);
    else source=null;
    if (end!=nulldestination = new Node(end);
    else destination=null;

    compare_counter=0;
    used_time=getTimeInMillis();
    setAdjazenzmatrix(al);
    for (j=0; j<knotenanzahl;j++) {
      for (i=0; i<knotenanzahl;i++) {
        for (k=0;k<knotenanzahl;k++) {
          compare_counter++;
          // ist der Vergleich unendlich + x => kein &auml;ndern n&ouml;tig
          if ((getValue(i,j)!=Integer.MAX_VALUE&& (getValue(j,k)!=Integer.MAX_VALUE)) { 
            if ((long)getValue(i,k)>(long)getValue(i,j)+(long)getValue(j,k)) {
              setValue(i,k,getValue(i,j)+getValue(j,k));
              pred_matrix.setValue(i,k,pred_matrix.getValue(j,k));
            }
          }
        
      }
    }
    reached_end=true;
    used_time=getTimeInMillis()-used_time;
    if (!(source==null|| (destination==null)) return getShortestPathEdgeVector();  
    else return null;
  }
  
  /** 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) im Step Modus. Dabei d&uuml;rfen die Knoten <i>start</i> und <i>end</I> 
   * auch null sein, da der Algorithmus die k&uuml;rzesten Wege zwischen allen 
   * Knoten ermittelt.
   */    
  public Vector startShortestPathStepModus (GraphNode start,GraphNode end, Adjazenzliste al) {    
    if (start!=null)source = new Node(start.getNode());
    else source=null;
    if (end!=nulldestination = new Node(end.getNode());
    else destination=null;

    if (al==nullreturn new Vector();

    return startShortestPathStepModus(source,destination,al);
  }

  /** 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) im Step Modus. Dabei d&uuml;rfen die Knoten <i>start</i> und <i>end</I> 
   * auch null sein, da der Algorithmus die k&uuml;rzesten Wege zwischen allen 
   * Knoten ermittelt.
   */    
  public Vector startShortestPathStepModus (Node start,Node end, Adjazenzliste al) {    
    if (start!=null)source = new Node(start);
    else source=null;
    if (end!=nulldestination = new Node(end);
    else destination=null;
    
    compare_counter=0;

    used_time=getTimeInMillis();
    reached_end=false;
    setAdjazenzmatrix(al);
    
    used_time=getTimeInMillis()-used_time;
    return getShortestPathEdgeVector();
  }

  /** Gibt den zuletzt untersuchten Knoten zur&uuml;ck.
   */
  public Node getLastInspectedNode() {
    return last_inspected_node;
  }

  /** Gibt die Zeit in Millisekunden zur&uuml;ck, die der Algorithmus in dem letzen Lauf 
   * gebraucht hat. 
   */
  public long getUsedTime(){
    return used_time;
  }  

  /** Gibt die Anzahl der Vergleiche zur&uuml;ck, die bislang im Algorithmus 
   * ben&ouml;tigt wurden. Nach einem einzelnen Algorithmusschritt werden diese
   * aufsummiert. Bei einem Neustart des Algorithmus wird der Z&auml;hler wieder 
   * auf 0 gestetzt.
   */
  public int getCompareCounter() {
    int rc=compare_counter;
    return rc;
  }

  /** Zur&uuml;ckgabe der Vorg&auml;ngermatrix.
   */
  public Matrix getPredecessorMatrix() {
    return pred_matrix;  
  }

  /** Berechnen der Zeit in Millisekunden.
   */
   private long getTimeInMillis() {
     Calendar cal = Calendar.getInstance();
     return cal.getTimeInMillis();
   }

  /** Pr&uuml;fung, ob das Ende des Algorithmus erreicht ist.
   */
  public boolean reachedEnd() {
    return reached_end;
  }
  
  /** Einen Algorithmusschritt ausf&uuml;hren. Zuvor muss jedoch der 
   * Algorithmus gestartet worden sein.
   */
  public Vector stepShortestPath (){

    if (j<knotenanzahl) { // &auml;ußere Schleife
      if (i<knotenanzahl) { // innere Schleife
          last_inspected_node=new Node(i);
          for (k=0;k<knotenanzahl;k++) {
            // ist der Vergleich unendlich + x => kein &auml;ndern n&ouml;tig
            compare_counter++;
            if ((getValue(i,j)!=Integer.MAX_VALUE&& (getValue(j,k)!=Integer.MAX_VALUE)) { 
              if ((long)getValue(i,k)>(long)getValue(i,j)+(long)getValue(j,k)) {
                setValue(i,k,getValue(i,j)+getValue(j,k));
                pred_matrix.setValue(i,k,pred_matrix.getValue(j,k));
              }
            }
          
          i++;
      else {
        i=0;
        j++;
      }
    else {
      reached_end=true;
    }
     // ende j wird nicht auf 0 gesetzt, sondern nur einmal von 0 bis 
    // knotenanzahl erh&ouml;ht
    return getShortestPathEdgeVector();
  }

  /** Vorbereitung der R&uuml;ckgabe des k&uuml;rzesten Weges zwischen den vorgegebenen
   * Knoten. Wurden keine Knoten vorgegeben, dann wird ein leerer Vector 
   * zur&uuml;ckgegeben. 
   */
  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 nur ein Startknoten vorgegeben, dann werden alle k&uuml;rzesten
   * Wege von diesem Startknoten zur&uuml;ckgegeben. Der Vector enth&auml;lt die Kanten
   * dieser Wege.
   */
  private Vector getShortestPathEdgeVectorForSource() {
    Vector kuerzester_weg = new Vector();
    int maxnnum = knotenanzahl;      
    for (int i=0;i<maxnnum+1;i++) {
      kuerzester_weg.addAll(getShortestPathEdgeVectorForDestination(i));
    }
    return kuerzester_weg;    
  }

  /** Gibt den k&uuml;rzesten Weg zu dem Knoten <I>node</I> zur&uuml;ck.
   */
  private Vector getShortestPathEdgeVectorForDestination(int node) {
    Vector kw=new Vector();
    int lauf_knoten = node;
    int matrix_index=node;
    while (lauf_knoten!=source.getValue() && lauf_knoten>=&& lauf_knoten!=Integer.MAX_VALUE) {
      lauf_knoten=pred_matrix.getValue(source.getValue(),matrix_index);
      Edge tmp_e=adlist.find(lauf_knoten,matrix_index)//Kante holen
      matrix_index=lauf_knoten;
      if (tmp_e!=nullkw.add(tmp_e);
    }
    return kw;
  }

  /** Initialisierungen f&uuml;r den Algorithmus.
   */
  private void initialiseFloydWarshall() {
    // variablen initialisieren
    knotenanzahl = getColumns();
    pred_matrix.setDimension(knotenanzahl,knotenanzahl);
    // initialisieren der Vorg&auml;ngermatrix
    // alle Eintr&auml;ge auf Integer.MIN_VALUE, f&uuml;r Kanten (i,j) jedoch auf i an der Stelle (i,j)
    for (int i=0; i<knotenanzahl;i++) {
      for (int j=0; j<knotenanzahl;j++) {
        if (getValue(i,j)!=Integer.MIN_VALUEpred_matrix.setValue(i,j,i);
        else pred_matrix.setValue(i,j,Integer.MIN_VALUE);
        if (i==jsetValue(i,i,0)// einfache Schlingen '&uuml;berspringen'
         // Hier kann der Vorg&auml;nger nicht auf 0 gesetzt werden, da 0 ein 
         // erlaubter Knotenname ist    
      }
    }
    
  }

}