DijkstraViewer.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
 *
 *  @(#)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=(Graphics2Dg;
    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=(Edgetmp_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&uuml;ckgegeben,
   * andernfalls <i>false</I>.
   */
  public boolean heapIsEmpty() {
    if (dijkstra==nullreturn 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((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;
  }
  
}