/*
* 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ürfen die Knoten <i>start</i> und <i>end</I>
* auch null sein, da der Algorithmus die kü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!=null) destination = new Node(end.getNode());
else destination=null;
if (al==null) return new Vector();
return shortestPath(source,destination,al);
}
/** 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 Node). Dabei dürfen die Knoten <i>start</i> und <i>end</I>
* auch null sein, da der Algorithmus die kü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!=null) destination = 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 ändern nö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ür die Berechnung eines kürzesten Weges
* von dem Knoten <i>start</I> nach <i>end</I> (beides Objekte der
* Klasse GraphNode) im Step Modus. Dabei dürfen die Knoten <i>start</i> und <i>end</I>
* auch null sein, da der Algorithmus die kü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!=null) destination = new Node(end.getNode());
else destination=null;
if (al==null) return new Vector();
return startShortestPathStepModus(source,destination,al);
}
/** 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 Node) im Step Modus. Dabei dürfen die Knoten <i>start</i> und <i>end</I>
* auch null sein, da der Algorithmus die kü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!=null) destination = 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ück.
*/
public Node getLastInspectedNode() {
return last_inspected_node;
}
/** Gibt die Zeit in Millisekunden zurück, die der Algorithmus in dem letzen Lauf
* gebraucht hat.
*/
public long getUsedTime(){
return used_time;
}
/** Gibt die Anzahl der Vergleiche zurück, die bislang im Algorithmus
* benötigt wurden. Nach einem einzelnen Algorithmusschritt werden diese
* aufsummiert. Bei einem Neustart des Algorithmus wird der Zähler wieder
* auf 0 gestetzt.
*/
public int getCompareCounter() {
int rc=compare_counter;
return rc;
}
/** Zurückgabe der Vorgängermatrix.
*/
public Matrix getPredecessorMatrix() {
return pred_matrix;
}
/** Berechnen der Zeit in Millisekunden.
*/
private long getTimeInMillis() {
Calendar cal = Calendar.getInstance();
return cal.getTimeInMillis();
}
/** Prüfung, ob das Ende des Algorithmus erreicht ist.
*/
public boolean reachedEnd() {
return reached_end;
}
/** Einen Algorithmusschritt ausführen. Zuvor muss jedoch der
* Algorithmus gestartet worden sein.
*/
public Vector stepShortestPath (){
if (j<knotenanzahl) { // ä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 ändern nö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öht
return getShortestPathEdgeVector();
}
/** Vorbereitung der Rückgabe des kürzesten Weges zwischen den vorgegebenen
* Knoten. Wurden keine Knoten vorgegeben, dann wird ein leerer Vector
* zurückgegeben.
*/
private Vector getShortestPathEdgeVector () {
Vector kuerzester_weg = new Vector();
if (source==null) return kuerzester_weg;
if (destination==null) {
return getShortestPathEdgeVectorForSource();
}
if (destination.getValue()==-1) {
return getShortestPathEdgeVectorForSource();
}
// hier ist source!=null und destination !=null
// kürzesten Weg fü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ürzesten
* Wege von diesem Startknoten zurückgegeben. Der Vector enthä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ürzesten Weg zu dem Knoten <I>node</I> zurü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>=0 && 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!=null) kw.add(tmp_e);
}
return kw;
}
/** Initialisierungen für den Algorithmus.
*/
private void initialiseFloydWarshall() {
// variablen initialisieren
knotenanzahl = getColumns();
pred_matrix.setDimension(knotenanzahl,knotenanzahl);
// initialisieren der Vorgängermatrix
// alle Einträge auf Integer.MIN_VALUE, fü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_VALUE) pred_matrix.setValue(i,j,i);
else pred_matrix.setValue(i,j,Integer.MIN_VALUE);
if (i==j) setValue(i,i,0); // einfache Schlingen 'überspringen'
// Hier kann der Vorgänger nicht auf 0 gesetzt werden, da 0 ein
// erlaubter Knotenname ist
}
}
}
}
|