/*
* 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
* übergebene Referenz gesetzt.
*/
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äre in diesem
* Falle <I>null</I>.
*/
public Vector shortestPath (GraphNode start,GraphNode end) {
if (start==null) return null;
if (end==null) return shortestPath(start.getNode(),null);
return shortestPath(start.getNode(),end.getNode());
}
/** 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 darf der Knoten <i>end</I> auch null sein.
* Der Startknoten darf nicht null sein. Das Ergebnis wäre in diesem
* Falle <I>null</I>.
*/
public Vector shortestPath (Node start,Node end) {
source = new Node(start);
if (end!=null) destination = new Node(end);
else destination=null;
compare_counter=0;
last_inspected_node = new Node();
used_time=getTimeInMillis();
if (!(source==null) ) {
initialiseBellmanFordMoore();
// ermittle den kü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 = (Edge) tmp_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ü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äre in diesem
* Falle <I>null</I>.
*/
public Vector startShortestPathStepModus (GraphNode start,GraphNode end) {
if (start==null) return null;
if (end==null) return startShortestPathStepModus(start.getNode(),null);
return startShortestPathStepModus(start.getNode(),end.getNode());
}
/** Startet den Algorithmus im Step Modus, 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äre in diesem
* Falle <I>null</I>. Es wird nur die Initialisierung des Algorithmus ausgeführt.
*/
public Vector startShortestPathStepModus (Node start,Node end) {
source = new Node(start);
if (end!=null) destination = 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öglicht.
*/
public Heap getHeap() {
return h;
}
/** Methode, die die Vorgängerliste des Algorithmus zurückgibt, damit diese
* angezeigt werden kann.
*/
public int[] getPredecessor() {
return vorgaenger;
}
/** Methode, die die Länge des Vorgängerarrays zurückgibt.
*/
public int getPredecessorLength() {
return vorgaenger.length;
}
/** Gibt den zuletzt untersuchten Knoten zurü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ötigt hat. Dies kann der Ablauf des ganzen
* Algorithmus gewesen sein, oder aber ein einzelner Algorithmusschritt.
*/
public long getUsedTime(){
return used_time;
}
/** Gibt zurück, wie viele Vergleiche der Algorithmus bisher benötigt hat.
*/
public int getCompareCounter() {
int rc=compare_counter;
return rc;
}
/** Fü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 = (Edge) tmp_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ück, der die Kanten des kürzesten Weges,
* bzgl. der Vorganben enthält.
*/
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 bei der kürzesten Wege- Berechnung kein Zielknoten vorgegeben
* wird diese Routine die kürzesten Wege zu allen Knoten zurü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ürzesten Weg von <i>source</I> nach <i>node</I> zurü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!=null) kw.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ürzeste Weg vom Startnoten zu sich selber ist 0
while (heap_enum.hasMoreElements()) {
Object tmp_element=heap_enum.nextElement();
Node tmp_node = (Node) tmp_element;
// Knoten zum heap hinzufü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
}
}
}
}
|