/*
* 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
*
* @(#)FloydWarshallViewer.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.*;
import javax.swing.table.*;
/** Der FloydWarshallViewer 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 FloydWarshallViewer
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();
// FloydWarshall fw= null;
Vector inspected_edges = new Vector();
int comp_anzahl = 0;
JLabel compAnzahl = new JLabel("Vergleiche: "+comp_anzahl);
AdjazenzmatrixTable ad_table = null;
AdjazenzmatrixTableModel ad_table_model = new AdjazenzmatrixTableModel();
FloydWarshall fw = new FloydWarshall();
AdjazenzmatrixTable pred_table = null;
AdjazenzmatrixTableModel pred_table_model = new AdjazenzmatrixTableModel();
Adjazenzmatrix pred_matrix = new Adjazenzmatrix();
Object[][] data = null;
Object[][] pred_data = null;
Object[] colnames = null;
DefaultTableColumnModel dtcm = null;
DefaultTableColumnModel pdtcm = null;
/** Konstruktor, der die Adjazenzliste in der Adjazenzmatrix übernimmt.
* Die Vorgängermatrix wird auch initialisiert. Die Knotenliste wird
* übernommen.
*/
public FloydWarshallViewer(Adjazenzliste al,GraphNodeList gnl) {
super();
init();
adlist = al;
graphDaten=gnl;
//eastpanel.setLayout(new BoxLayout(eastpanel,BoxLayout.Y_AXIS));
// Schrittzähler
compAnzahl.setAlignmentX(Component.CENTER_ALIGNMENT);
eastpanel.add(compAnzahl);
// adjazenzmatrix einbinden
ad_table= new AdjazenzmatrixTable(ad_table_model);
ad_table.setToolTipText("Adjazenzmatrixdarstellung");
JScrollPane ad_scrollPane = new JScrollPane(ad_table);
ad_scrollPane.setAlignmentX(Component.CENTER_ALIGNMENT);
JLabel l_dism=new JLabel("Distanzmatrix");
l_dism.setAlignmentX(Component.CENTER_ALIGNMENT);
eastpanel.add(l_dism);
eastpanel.add(ad_scrollPane);//,BorderLayout.SOUTH);
pred_table= new AdjazenzmatrixTable(pred_table_model);
pred_table.setToolTipText("Adjazenzmatrixdarstellung");
//pred_table_model.addTableModelListener(pred_table);
setAdjazenzPredecessorMatrix(al);
JScrollPane pred_scrollPane = new JScrollPane(pred_table);
pred_scrollPane.setAlignmentX(Component.CENTER_ALIGNMENT);
JLabel l_predm=new JLabel("Vorgängermatrix");
l_predm.setAlignmentX(Component.CENTER_ALIGNMENT);
eastpanel.add(l_predm);
eastpanel.add(pred_scrollPane);//,BorderLayout.SOUTH);
}
/** Initialisierung der Variablen.
*/
public void init(){
startNode = null;
zielNode = null;
etmodel = new DijkstraEdgeTableModel();
etable.setModel(etmodel);
}
/** Setzen der Adjazenzliste.
*/
public void setAdjazenzliste(Adjazenzliste al) {
adlist = al;
}
/** Die Vorgängermatrix wird anhand der Adjazenzliste gesetzt.
*/
public void setAdjazenzPredecessorMatrix(Adjazenzliste al) {
fw.setAdjazenzmatrix(al);
pred_matrix.setAdjazenzmatrix(al);
setModelMatrix();
setPredecessorMatrix();
}
/** Die Matrix des JTableModels wird anhand der schon übergebenen
* Adjazenzliste gesetzt.
*/
public void setModelMatrix() {
int maxnnum =fw.getColumns();//.getMaxNodeNumber();
dtcm=new DefaultTableColumnModel();
colnames=new String[maxnnum];
for (int i = 0; i < maxnnum; ++i) {
TableColumn tc= new TableColumn(i,25);
tc.setHeaderValue(""+i);
dtcm.addColumn(tc);
colnames[i]=new String (""+i);
}
data = new Object[fw.getRows()][fw.getColumns()];
for (int i=0;i<fw.getRows();i++) {
for (int j=0;j<fw.getColumns();j++) {
if (fw.getValue(i,j)!=Integer.MAX_VALUE) {
data[i][j]=new Integer(fw.getValue(i,j));
} else {
if (i==j) data[i][j]=new Integer(0);
else data[i][j]="~";
}
}
}
ad_table_model.setDataVector(data, colnames);
ad_table.setColumnModel(dtcm);
ad_table.setColumnSelectionAllowed(false);
ad_table.setToolTipText("Distanzmatrix");
}
/** Die Vorgängermatrix wird anhand der aktuellen Adjazenzliste
* erzeugt.
*/
public void setPredecessorMatrix() {
int maxnnum =fw.getColumns();//.getMaxNodeNumber();
pdtcm=new DefaultTableColumnModel();
Matrix pred_matrix=fw.getPredecessorMatrix();
colnames=new String[maxnnum];
for (int i = 0; i < maxnnum; ++i) {
TableColumn ptc= new TableColumn(i,25);
ptc.setHeaderValue(""+i);
pdtcm.addColumn(ptc);
colnames[i]=new String (""+i);
}
pred_data = new Object[fw.getRows()][fw.getColumns()];
for (int i=0;i<fw.getRows();i++) {
for (int j=0;j<fw.getColumns();j++) {
if (fw.getValue(i,j)!=Integer.MAX_VALUE) {
pred_data[i][j]=new Integer(pred_matrix.getValue(i,j));
} else {
pred_data[i][j]="";
}
}
}
pred_table_model.setDataVector(pred_data, colnames);
pred_table.setColumnSelectionAllowed(false);
pred_table.setToolTipText("Vorgängermatrix");
pred_table.setColumnModel(pdtcm);
}
/** Setzen der Knotenliste.
*/
public void setGraphNodeList(GraphNodeList gnl) {
graphDaten=gnl;
}
/** Eventhandling wenn die Maus einen Drag ausführt.
*/
public void mouseDragged(MouseEvent e) {
}
/** Eventhandling, wenn die Maus bewegt wurde.
*/
public void mouseMoved(MouseEvent e) {
}
/** Eventhandling, wenn die Maustaste gedürckt wurde.
*/
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, wenn die Maustaste losgelassen wurde.
*/
public void mouseReleased(MouseEvent e) {
}
/** Eventhandling, wenn die Maus einen Bereich betritt.
*/
public void mouseEntered(MouseEvent e) {
}
/** Eventhandling, wenn die Maus einen Bereich verlässt.
*/
public void mouseExited(MouseEvent e) {
}
/** Eventhandling, wenn die Maustaste geklickt wird.
*/
public void mouseClicked(MouseEvent e) {
}
/** Zeichnen des FloydWarshall Panels.
*/
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);
}
}
/** Starten des FloydWarshall Algorithmus und anzeigen des Ergebnisses.
*/
public void startFloydWarshall() {
//kuerzester_weg.removeAllElements();
//inspected_edges.removeAllElements();
fw = new FloydWarshall(adlist);
kuerzester_weg = fw.shortestPath(startNode,zielNode,adlist);
showFloydWarshallResult();
repaint();
}
/** Starten des Algorithmus in dem Step Modus und anzeigen des Ergebnisses.
*/
public void startFloydWarshallStepMode() {
kuerzester_weg.removeAllElements();
inspected_edges.removeAllElements();
fw = new FloydWarshall(adlist);
kuerzester_weg=fw.startShortestPathStepModus(startNode,zielNode,adlist);
showFloydWarshallResult();
repaint();
}
/** Ausführen eines Algorithmusschritts und anzeigen des Ergebnisses.
*/
public void nextFloydWarshallStep () {
kuerzester_weg=fw.stepShortestPath();
showFloydWarshallResult();
}
/** Anzeigen des Ergebnisses des letzten Algorithmusdurchlaufs.
*/
public void showFloydWarshallResult() {
Node zuletzt_benutzter_knoten = fw.getLastInspectedNode();
if (!(zuletzt_benutzter_knoten.getValue()==-1)) inspected_edges = adlist.getEdgesWithTail(zuletzt_benutzter_knoten);
else inspected_edges.removeAllElements();
showShortestPath();
setModelMatrix();
setPredecessorMatrix();
String statustext = YAV.status.getText();
if (fw.reachedEnd()) YAV.status.setText("Floyd-Warshall ist beendet! " + statustext);
YAV.status.setText(statustext+" ("+fw.getUsedTime()+" Millisekunden benötigt)");
compAnzahl.setText("Vergleiche: "+fw.getCompareCounter());
repaint();
}
/** Anzeigen von Statusinformationen bzgl. des kürzesten Weges.
*/
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.");
}
}
}
/** Prüfen, ob das Algorithmusende erreicht wurde.
*/
public boolean reachedEnd() {
return fw.reachedEnd();
}
/** Eine Kante zeichnen.
*/
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;
}
/** Die Knotenliste drucken (wird hier leer überschrieben).
*/
public void printNodeList(Graphics2D g2d,PageFormat pf) {
}
}
|