/*
* 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
*
* @(#)DijkstraViewer.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 DijkstraViewer 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 DijkstraViewer
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; // startknotenfarbe
/** Die Farbe des Zielknotens, wenn er festgelegt ist.
*/
Color zielFarbe = Color.green; // zielknotenfarbe
Color linienFarbe = Color.blue; // linienfarbe
Color zuerzesterWegFarbe = Color.orange; // kantenfarbe einer Kante auf dem kürzesten Weges
Color schriftFarbe = Color.black; // schriftfarbe für Kosten
Color knotenFarbe = Color.blue; // normale unselektierte Knotenfarbe
Color inspectionFarbe = Color.magenta; // Farbe der Kanten, die im letzten Schritt untersucht wurden
Vector kuerzester_weg = new Vector();
Dijkstra dijkstra = 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);
// für die Anzeige wird benötigt Vorgänger, Heap und seLketierter Knoten
/** Konstruktor, der die Adjazenzliste und die Knotenliste übernimmt.
*/
public DijkstraViewer(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");
}
/** Heap und Vorgängertabelle initialisieren.
*/
public void initHeapPredecessorTable() {
heaptablemodel.removeRows();
predtablemodel.removeRows();
}
/** Variablen initialisieren.
*/
public void init(){
comp_anzahl = 0;
compAnzahl = new JLabel("Vergleiche: "+comp_anzahl);
startNode = null;
zielNode = null;
etmodel = new DijkstraEdgeTableModel();
etable.setModel(etmodel);
}
/** Knotenliste drucken wird heri überschrieben. Zur Zeit noch nicht implementiert.
*/
public void printNodeList(Graphics2D g2d,PageFormat pf) {
}
/** Setzen der Adjazenzliste.
*/
public void setAdjazenzliste(Adjazenzliste al) {
adlist = al;
}
/** Knotenliste kann hier explizit noch einmal gesetzt werden.
*/
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;
if (zielNode!=null) {
if (startNode.getValue()==zielNode.getValue()) zielNode=null;
}
} else {
zielNode=intersectsNode;
zielNode.setColor(zielFarbe);
graphDaten.add(zielNode);
setzeStartKnoten=true;
if (startNode!=null) {
if (startNode.getValue()==zielNode.getValue()) startNode=null;
}
}
}
repaint();
}
/** Eventhandling für das Loslassen der Maustaste.
*/
public void mouseReleased(MouseEvent e) {
}
/** Eventhandling für das Bewegen der Maus in einem 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) {
}
/** Routine um die Daten zu visualisieren.
*/
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);
}
}
/** Routine, die Dijkstra startet.
*/
public void startDijkstra() {
kuerzester_weg.removeAllElements();
inspected_edges.removeAllElements();
dijkstra = new Dijkstra(adlist);
if (!(startNode==null)) {
kuerzester_weg = dijkstra.shortestPath(startNode,zielNode);
showDijkstraResult();
} else {
YAV.status.setText("Bitte erst Start- und ggf. Zielknoten festlegen...");
}
repaint();
}
/** Methode, die Dijkstra im Step Modus startet.
*/
public void startDijkstraStepMode() {
kuerzester_weg.removeAllElements();
inspected_edges.removeAllElements();
dijkstra = new Dijkstra(adlist);
//if (!((startNode==null) || (zielNode==null))) {
if (!(startNode==null) ) {
kuerzester_weg=dijkstra.startShortestPathStepModus(startNode,zielNode);
showDijkstraResult();
} else {
YAV.status.setText("Bitte erst Start- und ggf. Zielknoten festlegen...");
}
repaint();
}
/** Führt einen Schritt des Algorithmus aus.
*/
public void nextDijkstraStep () {
if (!(startNode==null)) {
kuerzester_weg=dijkstra.stepShortestPath();
showDijkstraResult();
}
}
/** Zeigt das Ergebnis des Algorithmus, bzw. Algorithmusschritts.
*/
public void showDijkstraResult() {
heaptablemodel.setRows(dijkstra.getHeap());
predtablemodel.setRows(dijkstra.getPredecessor());
Node zuletzt_benutzter_knoten = new Node (dijkstra.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("Dijkstra beendet! " + statustext);
}
YAV.status.setText(statustext+" ("+dijkstra.getUsedTime()+" Millisekunden benötigt)");
compAnzahl.setText("Vergleiche: "+dijkstra.getCompareCounter());
}
/** Zeigt in der Statuszeile Informationen über den kürzesten Weg an.
*/
public void showShortestPath() {
if (startNode==null) {
YAV.status.setText("Ein kürzester Weg wird nicht angezeigt, da kein "
+"Startknoten 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.");
}
}
}
/** Ist der Heap leer, dann wird <i>true</I> zurückgegeben,
* andernfalls <i>false</I>.
*/
public boolean heapIsEmpty() {
if (dijkstra==null) return true;
return dijkstra.heapIsEmpty();
}
/** Methode, die die Kanten malt.
*/
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;
}
}
|