BellmanFordMooreViewer.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
 *
 *  @(#)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&auml;rbt.
   */
    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);
    }  
    }
     
  /** 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&uuml;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&ouml;tigt)");
    compAnzahl.setText("Vergleiche: "+bfm.getCompareCounter());
  }

  /** Methode die den k&uuml;rzesten Weg in der Statuszeile anzeigt.
   */
  public void showShortestPath() {
    if (startNode==null)  {
      YAV.status.setText("Ein k&uuml;rzester Weg wird nicht angezeigt, da kein Start-"
                "und Zielknoten 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.");
                
      }    }
  }
  
  /** Methode, die pr&uuml;ft, ob der Heap leer ist.
   */
  public boolean heapIsEmpty() {
    if (bfm==nullreturn true;
    return bfm.heapIsEmpty();
  }
  
  /** Methode, die die Kanten des k&uuml;rzesten Weges f&auml;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((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;
  }
  
}