/*
* 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
*
* @(#)BellmanFordMooreViewer.java 1.0 04/03/09
*/
import javax.swing.*;
import java.*;
import java.awt.*;
import java.awt.event.*;
import java.util.Vector;
import java.util.Enumeration;
import java.lang.Math;
import java.util.Collections;
import java.awt.geom.*;
import java.awt.print.PrinterJob;
import java.awt.print.*;
/** Der BellmanFordMooreViewer dient zur Anzeige auf einem Tabbed Pane. Die Darstellung des
* Graphen wird in der Grundform vom Graph geerbt, wobei einige Methoden natürlich
* überschrieben werden.
*/
class BellmanFordMooreViewer
extends Graph
implements MouseListener, MouseMotionListener {
/** Startknoten für die Berechnung des kürzesten Weges.
*/
GraphNode startNode = null;
/** Zielknoten für die Berechnung des kürzesten Weges.
*/
GraphNode zielNode = null;
/** Status, mit dem geschaltet wird, ob der Start- oder Zielknoten gesetzt werden muss
*/
boolean setzeStartKnoten = true;
/** Das AbstractTableModel für die Anzeige der Kanten.
*/
DijkstraEdgeTableModel etmodel = null;
/** Die Farbe des Startknotens, wenn er festgelegt ist.
*/
Color startFarbe = Color.red;
/** Die Farbe des Zielknotens, wenn er festgelegt ist.
*/
Color zielFarbe = Color.green;
/** Die Linienfarbe der Kante.
*/
Color linienFarbe = Color.blue;
/** Farbe der Kanten, die auf dem kürzesten Weg liegen.
*/
Color zuerzesterWegFarbe = Color.orange;
/** Farbe der Kosten.
*/
Color schriftFarbe = Color.black;
/** Knotenfarbe, von Knoten, die nicht selektiert oder gefüllt sind.
*/
Color knotenFarbe = Color.blue;
/** Farbe der Kanten, die im letzten Schritt untersucht wurden.
*/
Color inspectionFarbe = Color.magenta;
/** Kanten, die auf dem kürzesten Weg liegen werden in dem Vector gespeichert.
*/
Vector kuerzester_weg = new Vector();
BellmanFordMoore bfm= null;
PredecessorTableModel predtablemodel;
PredecessorTable predtable;
HeapTableModel heaptablemodel;
HeapTable heaptable;
Vector inspected_edges = new Vector();
int comp_anzahl = 0;
JLabel compAnzahl = new JLabel("Vergleiche: "+comp_anzahl);
/** Konstruktor, der die Adjazenzliste al, und die Knotenliste
* übernimmt.
*/
public BellmanFordMooreViewer(Adjazenzliste al,GraphNodeList gnl) {
super();
init();
adlist = al;
graphDaten=gnl;
heaptablemodel = new HeapTableModel();
heaptable= new HeapTable(heaptablemodel);
predtablemodel = new PredecessorTableModel();
predtable= new PredecessorTable(predtablemodel);
compAnzahl.setAlignmentX(Component.CENTER_ALIGNMENT);
eastpanel.add(compAnzahl);
JLabel ueb_pred = new JLabel("Vorgängerliste");
ueb_pred.setAlignmentX(Component.CENTER_ALIGNMENT);
eastpanel.add(ueb_pred);
predtablemodel.addTableModelListener(this);
JScrollPane predscrollPane = new JScrollPane(predtable);
eastpanel.add(predscrollPane);
JLabel ueb_heap = new JLabel("Heap");
ueb_heap.setAlignmentX(Component.CENTER_ALIGNMENT);
eastpanel.add(ueb_heap);
heaptablemodel.addTableModelListener(this);
JScrollPane heapscrollPane = new JScrollPane(heaptable);
eastpanel.add(heapscrollPane);
JLabel legende = new JLabel(new ImageIcon(getClass().getResource("resources/legende.gif")));
legende.setAlignmentX(Component.CENTER_ALIGNMENT);
eastpanel.add(legende);
ueberschrift.setText("kürzester Weg");
}
/** Initialisiere die Tabellen.
*/
public void initHeapPredecessorTable() {
heaptablemodel.removeRows();
predtablemodel.removeRows();
}
/** Initialisiere die globalen Variabeln.
*/
public void init(){
comp_anzahl = 0;
compAnzahl = new JLabel("Vergleiche: "+comp_anzahl);
startNode = null;
zielNode = null;
etmodel = new DijkstraEdgeTableModel();
etable.setModel(etmodel);
}
/** Mit dieser Methode kann die Adjazenzliste gesetzt werden.
*/
public void setAdjazenzliste(Adjazenzliste al) {
adlist = al;
}
/** Das Drucken der Knotenliste wird hier nur überschrieben und enthält noch
* keine Funktionalität.
*/
public void printNodeList(Graphics2D g2d,PageFormat pf) {
}
/** Die Knotenliste wird neu gesetzt.
*/
public void setGraphNodeList(GraphNodeList gnl) {
graphDaten=gnl;
}
/** Eventhandling für das Ziehen der Maus.
*/
public void mouseDragged(MouseEvent e) {
}
/** Eventhandling für das Bewegen der Maus.
*/
public void mouseMoved(MouseEvent e) {
}
/** Eventhandling für das Drücken der Maustaste.
*/
public void mousePressed(MouseEvent e) {
e.consume();
Rectangle nr = new Rectangle(e.getX()-radius/2,e.getY()-radius/2,radius,radius);
GraphNode intersectsNode=graphDaten.intersectsWith(nr);
if (intersectsNode!=null) {
if (setzeStartKnoten) {
startNode=intersectsNode;
startNode.setColor(startFarbe);
graphDaten.add(startNode);
setzeStartKnoten=false;
} else {
zielNode=intersectsNode;
zielNode.setColor(zielFarbe);
graphDaten.add(zielNode);
setzeStartKnoten=true;
}
}
repaint();
}
/** Eventhandling für das Loslassen der Maustaste.
*/
public void mouseReleased(MouseEvent e) {
}
/** Eventhandling für das Bewegen der Mausin einen bestimmten Bereich.
*/
public void mouseEntered(MouseEvent e) {
}
/** Eventhandling für das Verlassen der Maus aus einem bestimmten
* Bereich.
*/
public void mouseExited(MouseEvent e) {
}
/** Eventhandling für das Klicken der Maus.
*/
public void mouseClicked(MouseEvent e) {
}
/** Methode zum Zeichnen der Komponenten. Zusätzlich zu der
* Methode der Elternklasse <i>Graph</I> wird der Start- und Zielkonten
* gefärbt.
*/
public void paintComponent(Graphics g) {
// male Knoten aus Vector und selektierten Knoten
super.paintComponent(g);
Graphics2D g2d=(Graphics2D) g;
if (startNode!=null) {
paintGraphNode(startNode,g2d,true);
}
if (zielNode!=null) {
paintGraphNode(zielNode,g2d,true);
}
}
/** BellmanFordMoore wird gestartet und das Ergebnis dargestellt.
*/
public void startBellmanFordMoore() {
kuerzester_weg.removeAllElements();
inspected_edges.removeAllElements();
bfm = new BellmanFordMoore(adlist);
if (!(startNode==null)) {
kuerzester_weg = bfm.shortestPath(startNode,zielNode);
showBellmanFordMooreResult();
} else {
YAV.status.setText("Bitte erst den Start- und ggf. Zielknoten festlegen...");
}
repaint();
}
/** BellmanFordMoore wird im Step Modus gestartet und das Ergebnis
* dieses Schrittes dargestellt.
*/
public void startBellmanFordMooreStepMode() {
kuerzester_weg.removeAllElements();
inspected_edges.removeAllElements();
bfm = new BellmanFordMoore(adlist);
if (!(startNode==null)) {
kuerzester_weg=bfm.startShortestPathStepModus(startNode,zielNode);
showBellmanFordMooreResult();
} else {
YAV.status.setText("Bitte erst Start- und ggf. Zielknoten festlegen...");
}
repaint();
}
/** BellmanFordMoore führt einen Schritt aus und das entsprechende Ergebnis
* wird angezeigt.
*/
public void nextBellmanFordMooreStep () {
if (!(startNode==null) ) {
kuerzester_weg=bfm.stepShortestPath();
showBellmanFordMooreResult();
}
}
/** Das Ergebnis des Algorithmus wird angezeigt.
*/
public void showBellmanFordMooreResult() {
heaptablemodel.setRows(bfm.getHeap());
predtablemodel.setRows(bfm.getPredecessor());
Node zuletzt_benutzter_knoten = new Node (bfm.getLastInspectedNode());
if (!(zuletzt_benutzter_knoten.getValue()==-1)) inspected_edges = adlist.getEdgesWithTail(zuletzt_benutzter_knoten);
else inspected_edges.removeAllElements();
showShortestPath();
String statustext = YAV.status.getText();
if (heapIsEmpty()) {
YAV.status.setText("Bellman-Ford-Moore ist beendet! " + statustext);
}
YAV.status.setText(statustext+" ("+bfm.getUsedTime()+" Millisekunden benötigt)");
compAnzahl.setText("Vergleiche: "+bfm.getCompareCounter());
}
/** Methode die den kürzesten Weg in der Statuszeile anzeigt.
*/
public void showShortestPath() {
if (startNode==null) {
YAV.status.setText("Ein kürzester Weg wird nicht angezeigt, da kein Start-"
+ "und Zielknoten gewählt wurde!");
} else {
int laenge=0;
Enumeration tmp_enum = kuerzester_weg.elements();
etmodel.removeRows();
while (tmp_enum.hasMoreElements()) { // solange noch Kanten in der Liste aufgeführt sind
Edge tmp_element=(Edge) tmp_enum.nextElement();
etmodel.addRow(tmp_element);
laenge+=tmp_element.getCost();
}
if (kuerzester_weg.size()==0) {
YAV.status.setText("Es gibt keinen kürzesten Weg.");
} else if (zielNode!=null) {
YAV.status.setText("Der kürzeste Weg von "+startNode.getNode()
+ " nach "+zielNode.getNode()+" hat eine Länge von "
+ laenge );
} else {
YAV.status.setText("Alle markierten Kanten, liegen auf einem der "
+ "kürzesten Wegen von "+startNode.getNode()
+ " zu einem anderen Knoten.");
} }
}
/** Methode, die prüft, ob der Heap leer ist.
*/
public boolean heapIsEmpty() {
if (bfm==null) return true;
return bfm.heapIsEmpty();
}
/** Methode, die die Kanten des kürzesten Weges färbt. Kanten, die
* im letzten Algorithmusschritt untersucht wurden, werden ebenso
* mit der entsprechenden Farbe markiert.
*/
void paintEdge(Edge tmp_kante,Graphics2D g2d) {
if (kuerzester_weg.isEmpty()) {
linienFarbe=Color.blue;
} else {
if (kuerzester_weg.contains((Object) tmp_kante)) {
super.linienFarbe=zuerzesterWegFarbe;
}
}
if (!(inspected_edges.isEmpty())) {
if (inspected_edges.contains((Object) tmp_kante)) {
super.linienFarbe=inspectionFarbe;
}
}
super.paintEdge(tmp_kante,g2d);
super.linienFarbe=Color.blue;
}
}
|