FloydWarshallViewer.java

/*
 *     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==jdata[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&auml;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&auml;ngermatrix");
    pred_table.setColumnModel(pdtcm);
    
  }

  /** Setzen der Knotenliste.
   */
  public void setGraphNodeList(GraphNodeList gnl) {
    graphDaten=gnl;
  }

  /** Eventhandling wenn die Maus einen Drag ausf&uuml;hrt.
   */
    public void mouseDragged(MouseEvent e) {
    }

  /** Eventhandling, wenn die Maus bewegt wurde.
   */
    public void mouseMoved(MouseEvent e) {
    }

  /** Eventhandling, wenn die Maustaste ged&uuml;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&auml;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=(Graphics2Dg;
    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&uuml;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&ouml;tigt)");
    compAnzahl.setText("Vergleiche: "+fw.getCompareCounter());
    repaint();
  }

  /** Anzeigen von Statusinformationen bzgl. des k&uuml;rzesten Weges.
   */
  public void showShortestPath() {
    if ((startNode==null)) {
      YAV.status.setText("Ein k&uuml;rzester Weg wird nicht angezeigt, da kein "
                +"Startknoten gew&auml;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&uuml;hrt sind
        Edge tmp_element=(Edgetmp_enum.nextElement();
        etmodel.addRow(tmp_element);
        laenge+=tmp_element.getCost();
      }
      if (kuerzester_weg.size()==0) {
        YAV.status.setText("Es gibt keinen k&uuml;rzesten Weg.");
      else if (zielNode!=null) {
        YAV.status.setText("Der k&uuml;rzeste Weg von "+startNode.getNode()
                " nach "+zielNode.getNode()+" hat eine L&auml;nge von "
                + laenge );
      else {
        YAV.status.setText("Alle markierten Kanten, liegen auf einem der "
                  "k&uuml;rzesten Wegen von "+startNode.getNode()
                  " zu einem anderen Knoten.");
                
      }
    }
  }
  
  /** Pr&uuml;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((Objecttmp_kante)) { 
        super.linienFarbe=zuerzesterWegFarbe; 
      }
    }
    if (!(inspected_edges.isEmpty())) {
      if (inspected_edges.contains((Objecttmp_kante)) {
        super.linienFarbe=inspectionFarbe;
      }
    }
    super.paintEdge(tmp_kante,g2d);
    super.linienFarbe=Color.blue;
  }

  /** Die Knotenliste drucken (wird hier leer &uuml;berschrieben).
   */ 
  public void printNodeList(Graphics2D g2d,PageFormat pf) {
  }

  
}