import java.awt.*;


/** Die Klasse TGraph beinhaltet einen Grafen <BR><BR>
Sprache:  Java
Autor  :  Fabian Wleklinski */

public class TGraph extends TGraphicContainer implements java.io.Serializable {
  /** Der Konstruktor 
  @param PaintSettings Der Kontext für dieses Grafikelement
  */
  public TGraph( TPaintSettings PaintSettings ) {
    super ( PaintSettings );
    FItems = new TList();
    FWay = new TList();
    FWay.duplicates = true;
  }

  /** Liefert die Länge des Animationsweges zurück, wenn vorhanden. Anderenfalls -1. */
  public double getAnimationLength() {
    if ((FSTree != 3) && (FSTree != 4)) {
      return -1;
    }
    double result = 0;
    TGraphNode lastNode = null;
    TGraphNode curNode;
    for (int i=1; i<=FWay.count(); i++) {
      curNode = (TGraphNode) FWay.item(i-1);
      result = result + curNode.distanceTo( lastNode );
      lastNode = curNode;
    }

    return result;
  }

  /** Überprüft ob die beiden übergebenen Elemente direkt verbunden sind */
  public boolean isRelated( TGraphic item1, TGraphic item2 ) {
    // Wenn eines der Elemente null ist -> raus
    if ((item1 == null) || (item2==null)) {
      return false;
    }
    // Symmetrie ist nicht erlaubt
    if (item1 == item2) {
      return true;
    }

    // Hält den Container des ersten Elementes
    TGraphNode item1Container = null;
    // Hält den Container des zweiten Elementes
    TGraphNode item2Container = null;

    // Nach dem ersten Element suchen
    for (int i=0; i<count(); i++) {
      if (item1 == ((TGraphNode) FItems.item( i )).getItem() ) {
        item1Container = ((TGraphNode) FItems.item( i ));
        break;
      }
    }
    // Wenn das erste Element nicht gefunden wurde -> raus
    if (item1Container == null) {
      return false;
    }
    // Nach dem zweiten Element suchen
    for (int i=0; i<count(); i++) {
      if (item2 == ((TGraphNode) FItems.item( i )).getItem() ) {
        item2Container = ((TGraphNode) FItems.item( i ));
        break;
      }
    }
    // Wenn das zweite Element nicht gefunden wurde -> raus
    if (item2Container == null) {
      return false;
    }
    // Checken, ob verbunden
    for (int i=0; i<item1Container.count(); i++) {
      if (item1Container.getNextNode(i) == item2Container) {
        return true;
      }
    }
    return false;
  }

  /** Liefert den Spannbaum-Status zurück 
  @return Spannbaum-Status siehe @see SetSTree
  */
  public int getSTree() {
    return FSTree;
  }

  /** Setzt den Spannbaum-Status 
  @param state (0,1,2,3,4,5) = (0:=Kein Spannbaum, 1:=Spannbaum den in Parameter @param param angegebenen Teilgrafen, 2:=Wald,
  3:=Route vom in @param param angegebenen Standpunkt, 4:=Route vom in @param param angegebenen Standpunkt im kantenlosen Modus,
  5:=Kantenloser Modus
  @param param Abhängig von dem Parameter @param state
  */
  public void setSTree( int state, TGraphic param ) {
    FSTree = state;
    FSParam = param;

    // Den Container für den Spannbaum-Parameter suchen, sofern vorhanden
    TGraphNode paramContainer = null;
    for (int i=0; i<count(); i++) {
      if (FSParam == ((TGraphNode) FItems.item( i )).getItem() ) {
        paramContainer = ((TGraphNode) FItems.item( i ));
        break;
      }
    }
    if (paramContainer == null) { return; }

    double min = 0;
    TGraphNode node1 = null;

    // Jetzt Fallunterscheidung, je nach Modus
    if (FSTree == 3) {
      FWay.clear();

      // Sicherheit ...
      if (paramContainer == null) { return; }

      TGraphNode curNode = paramContainer;

      // Die Anzahl der Elemente in diesem Subgrafen in subGrafsCount speichern, und die Elemente selber in subGrafs
      TList subGrafs = new TList();
      int subGrafsCount = 0;
      for (int i=1; i<=count(); i++) {
        if (((TGraphNode) container(i-1)).isRelatedToNodeEx( paramContainer, false ) ) { 
          // Den Startknoten nehmen wir nicht in die Liste auf ...
          if (((TGraphNode) container(i-1)) != curNode) {
            subGrafs.add( (TGraphNode) container(i-1) );
            subGrafsCount++; 
          }
        }
      }

      // Der erste Knoten steht natürlich am Anfang des Weges ...
      FWay.add( curNode );

      // Eine Liste anlegen, in der vermerkt ist, welche Knoten wir bereits erreicht haben
      TList nodes = new TList();

      // Hält den Knoten wo wir als nächstes hinwollen
      TGraphNode targetNode;
      // Hält den nächsten Knoten auf den wir springen
      TGraphNode nextNode;

      // Solange wiederholen, bis alle Knoten abgearbeitet sind
      while (subGrafs.count() > 0) {

        // Von allen Knoten, die noch vorhanden sind, suchen wir uns den mit der niedrigsten Distanz
        min = -1;
        targetNode = null;
        int minTarget = 0;
        for (int i=1; i<=subGrafs.count(); i++) {
          double d = ((TGraphNode) subGrafs.item(i-1)).distanceTo( curNode );
          if ((min == -1) || ((d != -1) && (d < min))) {
            minTarget = i-1;
            targetNode = (TGraphNode) subGrafs.item(i-1);
            min = d;
          }
        }
        if (targetNode != null) {

          // Solange wiederholen, bis wir an diesem Zielknoten angekommen sind
          while (curNode != targetNode) {
            min = -1;
            nextNode = null;
            for (int i=1; i<=curNode.FNext.count(); i++) {
              double d = ((TGraphNode) curNode.FNext.item(i-1)).distanceTo( targetNode );
              if ((min == -1) || ((d != -1) && (d < min))) {
                nextNode = (TGraphNode) curNode.FNext.item(i-1);
                min = d;
              }
            }
            // Knoten verbinden
            if ( nextNode != null) {

              nextNode.FSNext.add( curNode );
              curNode.FSNext.add( nextNode );
              curNode = nextNode;
            }

            if (curNode != targetNode) {FWay.add( curNode );}

          }

          FWay.add( targetNode );

          // Jetzt sind wir am Zielknoten angelangt ... Den Zielknoten aus der Liste löschen
          subGrafs.delete( minTarget );
        }
      }
    }

    // Jetzt Fallunterscheidung, je nach Modus
    if (FSTree == 4) {
      FWay.clear();

      // Sicherheit ...
      if (paramContainer == null) { return; }

      TGraphNode curNode = paramContainer;

      min = 0;
      while (min != -1) {
        min = -1;
        node1 = null;

        // Alle Elemente durchlaufen, und die kürzeste Distanz suchen ...
        for (int i=1; i <= count(); i++) {
          TGraphNode tempNode1 = (TGraphNode) FItems.item( i-1 );

          // Die horizontale und vertikale Differenz ermitteln
          double deltaX = (tempNode1.getItem().getLeft() + (tempNode1.getItem().getWidth() / 2)) - (curNode.getItem().getLeft() + (curNode.getItem().getWidth() / 2));
          double deltaY = (tempNode1.getItem().getTop() + (tempNode1.getItem().getHeight() / 2)) - (curNode.getItem().getTop() + (curNode.getItem().getHeight() / 2));
          // Die Distanz zwischen den Elementen ermitteln (Pythagoras)
          double distance = Math.sqrt( deltaX * deltaX + deltaY * deltaY );

          if (((min==-1) || (distance < min)) && (tempNode1 != curNode)) {
            // Hat das Element noch keine Verbindung zu sich selber???
            if (! (tempNode1.isRelatedToNodeEx( curNode, true ))) {
              min = distance;
              node1 = tempNode1;
            }
          }
        }
        // Wenn zwei Knoten gefunden wurden -> verbinden
        FWay.add( curNode );
        if (min != -1) {

          node1.FSNext.add( curNode );
          curNode.FSNext.add( node1 );
          curNode = node1;
        }
      }
    }


  }

  /** Zeichnet den Spannbaum für diesen Grafen auf den übergebenen Kontext */
  private void paintSTree( Graphics g ) {
    // Alle Verbindungen in dem Spannbaum löschen
    for (int i=1; i<=count(); i++) {
      ((TGraphNode) container( i-1 )).FSNext.clear();
    }

    // Wenn kein Spannbaum -> raus
    if (FSTree == 0) {
      return;
    }

    TGraphNode paramContainer = null;

    // Den Container für den Spannbaum-Parameter suchen, sofern vorhanden
    for (int i=0; i<count(); i++) {
      if (FSParam == ((TGraphNode) FItems.item( i )).getItem() ) {
        paramContainer = ((TGraphNode) FItems.item( i ));
        break;
      }
    }
    // Wenn das erste Element nicht gefunden wurde -> raus
    if ((FSTree == 1) || (FSTree == 3) || (FSTree == 4)) {
      if (paramContainer == null) {
        return;
      }
    }
    
    // Hält die bislang gefundene, kürzeste Distanz zu einem Knoten
    double min;
    // Hält die Indizes der Knoten mit der kürzesten Distanz
    TGraphNode node1, node2;

    // Jetzt Fallunterscheidung, je nach Modus
    if ((FSTree == 1) || (FSTree == 5)) {
      // "Spannbaum für einen bestimmten Teilgrafen zeichnen" bzw. "Kantenloser Modus"

      // Für n Elemente benötigen wir n-1 Linien
      for (int linieI = 1; linieI <= count()-1; linieI++) {
        min = -1;
        node1 = null;
        node2 = null;

        // Alle Kombination von zwei Elementen durchlaufen, und die Kombination mit der niedrigsten Distanz merken
        for (int i=1; i <= count(); i++) {
          TGraphNode tempNode1 = (TGraphNode) container( i-1 );

          for (int j=i+1; j<=count(); j++) {
            TGraphNode tempNode2 = (TGraphNode) container( j-1 );


            // Nur bearbeiten, wenn kantenloser Modus, oder wenn im gleichen Teilgrafen
            if ((FSTree == 5) || (FSTree == 4) || (     (tempNode1.isRelatedToNodeEx(paramContainer,false)) && (tempNode2.isRelatedToNodeEx(paramContainer,false)) && (tempNode2.isRelatedToNode(tempNode1))   ) ) {

              // Die horizontale und vertikale Differenz ermitteln
              double deltaX = (tempNode1.getItem().getLeft() + (tempNode1.getItem().getWidth() / 2)) - (tempNode2.getItem().getLeft() + (tempNode2.getItem().getWidth() / 2));
              double deltaY = (tempNode1.getItem().getTop() + (tempNode1.getItem().getHeight() / 2)) - (tempNode2.getItem().getTop() + (tempNode2.getItem().getHeight() / 2));
              // Die Distanz zwischen den Elementen ermitteln (Pythagoras)
              double distance = Math.sqrt( deltaX * deltaX + deltaY * deltaY );
              // Ist es die niedrigste Distanz??
              if ((distance < min) || (min == -1)) {
                // Hat das Element noch keine Verbindung zu sich selber???
                if (! (tempNode2.isRelatedToNodeEx( tempNode1, true ))) {
                  // Diese Distanz merken
                  min = distance;
                  // Diese Knoten merken
                  node1 = tempNode1;
                  node2 = tempNode2;
                }
              }
            }
          }
        }
        // Wenn zwei Knoten gefunden wurden -> verbinden
        if (min != -1) {
          node1.FSNext.add( node2 );
          node2.FSNext.add( node1 );
        }
      }
      
    }

    // Jetzt Fallunterscheidung, je nach Modus
    if (FSTree == 2) {
      // "Wald zeichnen"

      // Wir benötigen eine Liste, in der für jeden Teilgrafen ein Knoten als Repräsentant abgelgt wird
      TList subGrafs = new TList();

      // Jetzt alle Teilgrafen abarbeiten
      for (int x=1; x<=count(); x++) {

        // Dieser Knoten ist ein Repräsentant für den aktuellen Teilgraf
        // Zugriff auf ein Element holen
        TGraphNode subGraf = (TGraphNode) container( x-1 );

        // Testen, ob in der Liste schon ein Repräsentant für diesen Teilgraf existiert
        boolean alreadyDone = false;
        for (int i=1; i<=subGrafs.count(); i++) {
          if (((TGraphNode) subGrafs.item(i-1)).isRelatedToNodeEx( subGraf, false )) {
            alreadyDone = true;
            break;
          }
        }
        if (! alreadyDone) {
          // den Knoten ale Repräsentant die Liste aufnehmen
          subGrafs.add( subGraf );
        }

        min = -1;
        node1 = null;
        node2 = null;

        // Jetzt in einer zweiten und dritten Schleife alle Knoten bearbeiten, die im selben Teilgrafen sind
        for (int i=1; i<=count(); i++) {
          // Zugriff auf ein Element holen
          TGraphNode tempNode1 = (TGraphNode) container( i-1 );

          // Nur weiter, wenn im richtigen Teilgrafen
          if (tempNode1.isRelatedToNodeEx(subGraf,false)) {

            for (int j=1; j<=count(); j++) {
              // Zugriff auf ein Element holen
              TGraphNode tempNode2 = (TGraphNode) container( j-1 );

              // Nur weiter, wenn nicht identisch, und im selben Teilgrafen
              if ((tempNode1 != tempNode2) && (tempNode2.isRelatedToNode(tempNode1))) {

                // Die horizontale und vertikale Differenz ermitteln
                double deltaX = (tempNode1.getItem().getLeft() + (tempNode1.getItem().getWidth() / 2)) - (tempNode2.getItem().getLeft() + (tempNode2.getItem().getWidth() / 2));
                double deltaY = (tempNode1.getItem().getTop() + (tempNode1.getItem().getHeight() / 2)) - (tempNode2.getItem().getTop() + (tempNode2.getItem().getHeight() / 2));
                // Die Distanz zwischen den Elementen ermitteln (Pythagoras)
                double distance = Math.sqrt( deltaX * deltaX + deltaY * deltaY );

                // Ist es die niedrigste Distanz bisher??
                if ((distance < min) || (min == -1)) {
                  // Hat das Element noch keine Verbindung zu sich selber???
                  if (! (tempNode2.isRelatedToNodeEx( tempNode1, true ))) {
                    // Diese Distanz merken
                    min = distance;
                    // Diese Knoten merken
                    node1 = tempNode1;
                    node2 = tempNode2;
                  }
                }
              }
            }
          }
        }
        // Wenn zwei Knoten gefunden wurden -> verbinden
        if (min != -1) {
          node1.FSNext.add( node2 );
          node2.FSNext.add( node1 );
        }
      }

      // Was bisher geschehen ist, ist, daß für jeden Teilgraf der Spannbaum erstellt wurde. Jetzt müssen Verbindungen
      // geschaffen werden, die die verschiedenen Spannbäume miteinander verbinden

      // Für jeden Teilgraf existiert jetzt ein Repräsentant in "subGrafs". Diese Elemente werden jetzt alle der Reihe nach
      // abgearbeitet.
      TGraphNode lastNode = null;
      for (int i=1; i<=subGrafs.count(); i++) {
        // Zugriff auf den Repräsentanten eines speziellen Teilgrafen
        TGraphNode subGraf = (TGraphNode) subGrafs.item(i-1);
        TGraphNode node = null;
        // Jetzt alle Elemente durcharbeiten, die in demselben Teilgrafen sind
        min = -1;
        TGraphNode tempNode = null;
        for (int j=1; j<=count(); j++) {
          // Gesucht ist das Element mit der nierigsten Y-Koordinate
          tempNode = (TGraphNode) container( j-1 );
          if (subGraf.isRelatedToNodeEx( tempNode , false ) ) {
            if ((min == -1) || (tempNode.getItem().getTop() < min)) {
              min = tempNode.getItem().getTop();
              node = tempNode;
            }
          }
        }
        // Jetzt dieses Element mit dem letzten Element verbinden ...
        if (lastNode != null) {
          lastNode.FSNext.add( node );
          node.FSNext.add( lastNode );
        }
        lastNode = node;
      }
    }

    // Jetzt Fallunterscheidung, je nach Modus
    if ((FSTree == 3) || (FSTree == 4)) {
      // Alle Elemente nicht highlighten
      for (int i=1; i<=count(); i++) {
        ((TGraphNode) container( i-1 )).getItem().setHighlighted( false );
      }

      // Wenn leer -> raus
      if (count() == 0) { return; }

      // Sonderbehandlung, wenn -1 ...

      // die ersten n Elemente highlighten, wobei n dem Animationsschritt entspricht. Zu diesem Zeitpunkt kann davon
      // ausgegangen werden, daß bereits der Spannbaum besteht.

      int j = FAnimationStep;
      if ((j != -1) && (j >= FWay.count())) { j=FWay.count()-1; }

      /* Dieser Code markiert alle Elemente BIS ZU dem aktuellen */
      /*
      for (int i=1; i<=j; i++) {
        ((TGraphNode) FWay.item(i-1)).getItem().setHighlighted( true );
      } */

      /* Dieser Code markiert NUR das aktuelle Element */
      if (j != -1) {
        ((TGraphNode) FWay.item(j)).getItem().setHighlighted( true );
      }

      // Dafür sorgen, daß die ersten n Elemente verbunden sind ...     
      TGraphNode lastNode = null;
      TGraphNode curNode = null;
      int k = j;
      if (k == -1) { k = FWay.count()-1; }
      for (int i=1; i<=k+1; i++) {
        curNode = (TGraphNode) FWay.item(i-1);
        if (lastNode != null) {
          curNode.FSNext.add( lastNode );
          lastNode.FSNext.add( curNode );
        }
        lastNode = curNode;
      } 
    }

    // Jetzt alle Verbindungen, die vorhanden sind, zeichnen
    g.setColor (Color.red);
    for (int i=0; i<count(); i++) {
      for (int j=i; j<count(); j++) {
        if (((TGraphNode) container(i)).FSNext.indexOf( container(j) ) >= 0) {
          g.drawLine( 
            PaintSettings().double2pixX( item(i).getLeft()+item(i).getWidth()/2 ), 
            PaintSettings().double2pixY( item(i).getTop()+item(i).getHeight()/2 ),
            PaintSettings().double2pixX( item(j).getLeft()+item(j).getWidth()/2 ),
            PaintSettings().double2pixY( item(j).getTop()+item(j).getHeight()/2 ) 
          );
        }
      }
    }
  }

  /** Liefert den Animationsschritt zurück */
  public int getAnimationStep() {
    return FAnimationStep;
  }

  /** Setzt den Animationsschritt auf den übergebenen Wert */
  public void setAnimationStep( int step ) {
    FAnimationStep = 0;
    if ((step >=0) && (step < animationSteps())) {
      FAnimationStep = step;
    }
    if ((step == -1) && ((FSTree==3) || (FSTree==4)) ) {
      FAnimationStep = step;
    }
  }

  /** Liefert die Anzahl der Animationsschritte für den aktuell eingestellten Spannbaum-Modus zurück */
  public int animationSteps() {
    int result = 0;
    if ((FSTree == 3) || (FSTree == 4)) {
      result = FWay.count();
    }
    return result;
  }

  /** Verbindet jedes Element mit jedem */
  public void connectAll() {
    for (int linieI = 1; linieI <= count()-1; linieI++) {
      // Alle Elemente durchlaufen
      for (int i=1; i <= count(); i++) {
        for (int j=i+1; j<=count(); j++) {
          ((TGraphNode) container( i-1 )).FNext.add( container(j-1) );
          ((TGraphNode) container( j-1 )).FNext.add( container(i-1) );
        }
      }
    }
  }

  /** Löscht das angegebene Element aus dem Container.
  @param item Das zu löschende Element
  @return int 0, wenn Element gefunden und gelöscht
  */
  public int delete( TGraphic item ) {
    // Sicherheit ...
    if (item == null) {
      return -1;
    }

    // die Querverweise / Referenzen löschen
    killReferences( item );

    int result = -1;

    for (int i=0; i<count(); i++) {
      if (item(i) == item) {
        FItems.delete( i );
        result = 0;
      }
    }

    if (count() == 0) {
      result = 1;
    }
    return result;
  }

  /** Prüft, ob das angegebene Element im Tree enthalten ist, true bei Fund
  @param TGraphic Das zu suchende Element 
  */
  public boolean isItemOf ( TGraphic item ) {
    if (this == item) {
      return true;
    }
    for (int i=0; i<count(); i++) {
      if (item(i) == item) {
        return true;
      }
    }
    return false;
  }


  /* Diese Methode ist nötig, um nach der Methode "add()" noch Aktionen ausführen zu können. (wegen Rekursion) */
  private void addInternal( TGraphic newItem ) {
    // Wenn das Element leer ist -> raus
    if (newItem == null) {
      return; 
    }

    // Fallunterscheidung: Wenn Container -> Sonderbehandlung
    if (newItem instanceof TGraphicContainer) {

      TGraphicContainer graphicContainer = (TGraphicContainer) newItem;
      for (int i=0; i < graphicContainer.count(); i++) {
        addInternal( graphicContainer.item(i) );
      }
      // Jetzt Verbindungen, so gut wie möglich, restaurieren
      for (int i=0; i < graphicContainer.count(); i++) {
        TGraphic src = graphicContainer.item( i );
        for (int j=0; j < graphicContainer.container(i).count(); j++) {
          TGraphic target = graphicContainer.container(i).getNext( j );
          // Jetzt versuchen, src und target zu verbinden
          connect( src, target );
        }
      }
      return;
    }

    // Wenn das Element schon in dem Verband existiert -> raus
    if (isItemOf( newItem )) {
      return;
    }

    // Ein neues Listen-Element erzeugen
    TGraphNode newGraphNode = new TGraphNode();
    newGraphNode.setItem( newItem );

    // In die Liste aufnehmen
    FItems.add( newGraphNode );
  }

  /** Fügt ein Element hinzu. Das neue Element wird in den Grafen aufgenommen, sofern es nicht NULL ist. Elemente
  dürfen doppelt in dem Grafen existieren.
  @param item Das hinzuzufügende Element
  */
  public void add( TGraphic newItem ) {
    // Alle (Unter-)Elemente hinzufügen
    addInternal( newItem );
  }

  /** Versucht, die beiden übergebenen Elemente zu verbinden
  @param item1 Das erste der zu verbindenden Elemente
  @param item2 Das zweite der zu verbindenden Elemente
  @return TRUE wenn erfolgreich
  */
  public boolean connect( TGraphic item1, TGraphic item2 ) {
    // Wenn eines der Elemente null ist -> raus
    if ((item1 == null) || (item2==null)) {
      return false;
    }
    // Symmetrie ist nicht erlaubt
    if (item1 == item2) {
      return false;
    }

    // Hält den Container des ersten Elementes
    TGraphNode item1Container = null;
    // Hält den Container des zweiten Elementes
    TGraphNode item2Container = null;

    // Nach dem ersten Element suchen
    for (int i=0; i<count(); i++) {
      if (item1 == ((TGraphNode) FItems.item( i )).getItem() ) {
        item1Container = ((TGraphNode) FItems.item( i ));
        break;
      }
    }
    // Wenn das erste Element nicht gefunden wurde -> raus
    if (item1Container == null) {
      return false;
    }
    // Nach dem zweiten Element suchen
    for (int i=0; i<count(); i++) {
      if (item2 == ((TGraphNode) FItems.item( i )).getItem() ) {
        item2Container = ((TGraphNode) FItems.item( i ));
        break;
      }
    }
    // Wenn das zweite Element nicht gefunden wurde -> raus
    if (item2Container == null) {
      return false;
    }
    // Wenn entgegen allen Erwartungen die Container identisch sind -> raus
    if (item1Container == item2Container) {
      return false;
    }
    // Die Verknüpfung vornehmen.
    item1Container.connect( item2Container );
    item2Container.connect( item1Container );

    return true;
  }

  /** Versucht, die Verbindung zwischen den beiden übergebenen Elemente zu löschen
  @param item1 Das erste Element
  @param item2 Das zweite Element
  @return TRUE wenn erfolgreich
  */
  public boolean deconnect( TGraphic item1, TGraphic item2 ) {
    // Wenn eines der Elemente null ist -> raus
    if ((item1 == null) || (item2==null)) {
      return false;
    }
    // Symmetrie ist nicht erlaubt
    if (item1 == item2) {
      return false;
    }

    // Hält den Container des ersten Elementes
    TGraphNode item1Container = null;
    // Hält den Container des zweiten Elementes
    TGraphNode item2Container = null;

    // Nach dem ersten Element suchen
    for (int i=0; i<count(); i++) {
      if (item1 == ((TGraphNode) FItems.item( i )).getItem() ) {
        item1Container = ((TGraphNode) FItems.item( i ));
        break;
      }
    }
    // Wenn das erste Element nicht gefunden wurde -> raus
    if (item1Container == null) {
      return false;
    }
    // Nach dem zweiten Element suchen
    for (int i=0; i<count(); i++) {
      if (item2 == ((TGraphNode) FItems.item( i )).getItem() ) {
        item2Container = ((TGraphNode) FItems.item( i ));
        break;
      }
    }
    // Wenn das zweite Element nicht gefunden wurde -> raus
    if (item2Container == null) {
      return false;
    }
    // Wenn entgegen allen Erwartungen die Container identisch sind -> raus
    if (item1Container == item2Container) {
      return false;
    }
    // Die Verknüpfungen löschen
    item1Container.deconnect( item2Container );
    item2Container.deconnect( item1Container );
    return true;
  }

  /** Löscht für alle enthaltenen Elemente die Verweise auf das übergebene Element 
  @param target Das Element, auf das die Verweise gelöscht werden sollen */
  public void killReferences( TGraphic target ) {
    if (target == null) {
      return;
    }

    // Hält den Container des ersten Elementes
    TGraphNode item1Container = null;

    // Den Container für das Element bestimmen
    // Nach dem Element suchen
    for (int i=0; i<count(); i++) {
      if (target == ((TGraphNode) FItems.item( i )).getItem() ) {
        item1Container = ((TGraphNode) FItems.item( i ));
        break;
      }
    }
    // Wenn das Element nicht gefunden wurde -> raus
    if (item1Container == null) {
      return;
    }
    // Die Beziehungen (rückwärts) löschen
    for (int i=0; i < item1Container.count(); i++) {
      ((TGraphNode) item1Container.getNextNode( i )).FNext.delete( item1Container );
    }
    // Die Beziehungen (vorwärts) löschen
    item1Container.FNext.clear();
  }

  /** Gibt ein Element aus der Liste zurück. Ist der Index außerhalb der Grenzen, wird eine Exception erzeugt.
  @param index Der Index des Elementes
  */
  public TGraphic item( int index ) {
    // Den Rückgabewert
    return container( index ).getItem();
  }

  /** Gibt den Container eines Element aus der Liste zurück. Ist der Index außerhalb der Grenzen, wird eine Exception erzeugt.
  @param index Der Index des Elementes
  */
  public TNode container( int index ) {
    // Bounds-Check
    if (! validIndex( index )) { throw new IndexOutOfBoundsException(); }

    // Den Rückgabewert
    return ((TGraphNode) FItems.item( index ));
  }

  /** Liefert TRUE wenn die übergebene Koordinate innerhalb des gezeichneten Bereiches liegt */
  public boolean isInside( int sx, int sy ) {
    for (int i=0; i<FItems.count(); i++) {
      if (item( i ).isInside( sx, sy )) {
        return true;
      }
    }

    return false;
  }

  /** Ruft für alle untergeordneten Grafikelemente die Methode isInside auf, und liefert die Instanz
      des ersten Elementes zurück, welches TRUE zurückgibt.
      @param x Horizontale Koordinate des Punktes
      @param y Vertikale Koordinate des Punktes
   */ 
  public TGraphic getObjectAt( int x, int y ) {
    for (int i=0; i<FItems.count(); i++) {
      if (item( i ).isInside( x, y )) {
        return item( i );
      }
    }

    return null;
  }

  /** Liefert TRUE zurück wenn der übergebene Index gültig ist
  @param index Der Index, der überprüft werden soll 
  */
  public boolean validIndex( int index ) {
    return ((index >= 0) && (index < count()));
  }

  /** Liefert die Anzahl der Elemente zurück
   */
  public int count() {
    return FItems.count();
  }

  /** Zeichnet das Element auf Graphics g neu 
    * @param Graphics Der zu verwendende Context
    */
  public void paint( Graphics g ) {
     // Ohne Kontext kein Zeichnen!
     if (PaintSettings()==null) { return; }

     // Jetzt die Linien zu den Nachbarn zeichnen. Dies kann nicht in dem Element an sich geschehen, da ansonsten
     // Linien doppelt gezeichnet werden würden 
     // -> macht doch nix, maximal wird 2x gezeichnet... so sind die Linien immer drüber und das sieht auch nicht so toll aus
     g.setColor (Color.black);
     for (int i=0; i<count(); i++) {
       for (int j=i; j<count(); j++) {
         if (container(i).isRelatedToNode(container(j))) {
           g.drawLine( 
             PaintSettings().double2pixX( item(i).getLeft()+item(i).getWidth()/2 ), 
             PaintSettings().double2pixY( item(i).getTop()+item(i).getHeight()/2 ),
             PaintSettings().double2pixX( item(j).getLeft()+item(j).getWidth()/2 ),
             PaintSettings().double2pixY( item(j).getTop()+item(j).getHeight()/2 ) 
           );
         }
       }
     }

     // Evtl. einen Spannbaum zeichnen
     paintSTree( g );

     // Für alle untergeordneten Elemente die Paint-Methode aufrufen
     for (int i=0; i<count(); i++) {
       container(i).paint( g );  // vormals item(i).paint...
     }

  }

  /** In dieser Liste sind alle Elemente des Grafen enthalten. Das bedeutet, daß auch alle Elemente, die den Nachbar
      eines Elementes aus dem Grafen darstellen, in dieser Liste enthalten sein können. Es handelt sich hierbei also um
      redundante Informationen. Aufgrund des Interfaces dieser Klasse sollten aber dennoch keine Inkonsistenzen entstehen
      können.
      @serial
   */
  private TList FItems;

  /** Der aktuelle Animationsschritt */
  int FAnimationStep;

  /** Der Spannbaum-Status */
  int FSTree;
  TGraphic FSParam;

  /** Diese Liste ist eine Hilfskonstruktion, um sich im Animationsmodus den Weg zu merken */
  TList FWay;

  // Ein Container für ein Element aus der Liste. Diese Klasse ist nur für den internen Gebrauch bestimmt.
  private class TGraphNode extends TNode implements java.io.Serializable {
    /** Der Konstruktor */
    public TGraphNode() {
      FNext = new TList();
      FSNext = new TList();
    }    
    /** Liefert die Anzahl der direkten Nachbarn zurück */
    public int count() {
      return FNext.count();
    }

    /** Der rekursive Teil von "isRelatedToNodeEx"
    @param source Das erste Element, mit dem auf eine Verbindung geprüft werden soll 
    @param target Das zweite Element, mit dem auf eine Verbindung geprüft werden soll 
    @param doneNodes eine Liste mit den Knoten die schon bearbeitet worden sind
    */
    private boolean internalIsRelatedToNodeEx( TGraphNode source, TGraphNode target, TList doneNodes, boolean STreeConnections ) {
      // Wenn diese Elemente schon verglichen wurden -> raus
      if (doneNodes.indexOf( source ) >= 0) {
        return false;
      }

      // Merken, daß diese beiden Nodes schon verglichen worden sind
      doneNodes.add( source );

      // Wenn die übergebenen Elemente identisch sind -> positiv beenden
      if (source == target) {
        return true;
      }
      // Für alle Nachbarelemente aufrufen
      if (STreeConnections) {
        for (int i=0; i<source.FSNext.count(); i++) {
          if (internalIsRelatedToNodeEx( (TGraphNode) source.FSNext.item( i ), target, doneNodes, STreeConnections )) {
            return true;
          }
        }
      } else {
        for (int i=0; i<source.FNext.count(); i++) {
          if (internalIsRelatedToNodeEx( (TGraphNode) source.FNext.item( i ), target, doneNodes, STreeConnections )) {
            return true;
          }
        }
      }
      return false;
    }

    /** Überprüft, ob zwei Elemente eine direkte oder eine indirekte Verbindung zueinander
    besitzen. Diese Methode arbeitet rekursiv und ist bei großen Strukturen auch etwas
    rechenzeitintensiv. Wenn es nicht unbedingt erforderlich ist, sollte statt dessen die
    Methode zum prüfen auf direkte Nachbarschaft "isRelatedTo" verwendet werden. 
    @param target Das Element, mit dem auf eine Verbindung geprüft werden soll 
    */
    private boolean isRelatedToNodeEx( TGraphNode target, boolean STreeConnections ) {
      // Sicherheit ...
      if ((this == null) || (target == null)) {
        return false;
      }

      // Symmetrie
      if (this == target) {
        return true;
      }

      // Eine Liste, in der die Knoten abgelegt werden, die abgearbeitet sind
      TList list = new TList();

      // rekursiv aufrufen
      return internalIsRelatedToNodeEx( this, target, list, STreeConnections );
    }

    /** Der rekursive Teil von "distanceTo"
    @param source Das erste Element
    @param target Das zweite Element
    @param doneNodes eine Liste mit den Knoten die schon bearbeitet worden sind
    */
    private double internalDistanceTo( TGraphNode source, TGraphNode target, TList doneNodes ) {
      // Wenn diese Elemente schon bearbeitet wurden -> raus
      if (doneNodes.indexOf( source ) >= 0) {
        return -1;
      }

      // Merken, daß diese beiden Nodes schon bearbeitet worden sind
      doneNodes.add( source );

      // Falls diese beiden Knoten direkt verbunden sind, den Abstand berechnen und zurückkehren
      for (int i=1; i<=source.FNext.count(); i++) {

        if (((TGraphNode) source.FNext.item(i-1)) == target) {

          TGraphNode tempNode1 = source;
          TGraphNode tempNode2 = target;

          // Die horizontale und vertikale Differenz ermitteln
          double deltaX = (tempNode1.getItem().getLeft() + (tempNode1.getItem().getWidth() / 2)) - (tempNode2.getItem().getLeft() + (tempNode2.getItem().getWidth() / 2));
          double deltaY = (tempNode1.getItem().getTop() + (tempNode1.getItem().getHeight() / 2)) - (tempNode2.getItem().getTop() + (tempNode2.getItem().getHeight() / 2));
          // Die Distanz zwischen den Elementen ermitteln (Pythagoras)
          double distance = Math.sqrt( deltaX * deltaX + deltaY * deltaY );
          return distance;
        }
      }

      // Falls diese beiden Knoten nicht direkt verbunden sind, die Methode rekursiv aufrufen und das Minimum zurückgeben

      // Das Minimum finden
      double min = -1;
      for (int i=1; i<=source.FNext.count(); i++) {
        TGraphNode tempNode1 = source;
        TGraphNode tempNode2 = (TGraphNode) source.FNext.item(i-1);

        // Die horizontale und vertikale Differenz ermitteln
        double deltaX = (tempNode1.getItem().getLeft() + (tempNode1.getItem().getWidth() / 2)) - (tempNode2.getItem().getLeft() + (tempNode2.getItem().getWidth() / 2));
        double deltaY = (tempNode1.getItem().getTop() + (tempNode1.getItem().getHeight() / 2)) - (tempNode2.getItem().getTop() + (tempNode2.getItem().getHeight() / 2));
        // Die Distanz zwischen den Elementen ermitteln (Pythagoras)
        double distance = Math.sqrt( deltaX * deltaX + deltaY * deltaY );

        double res = internalDistanceTo( tempNode2, target, doneNodes );

        if ((res != -1) && ((res + distance < min) || (min == -1))) {
          min = res + distance;
        }
      }

      return min;
    }

    /** Berechnet die minimale Entfernung von sich selber zu dem übergebenen Knoten. Diese Methode arbeitet rekursiv und 
    ist bei großen Strukturen auch etwas rechenzeitintensiv. 
    @param target Das Element, zu dem die minmimale Entfernung berechnet werden soll
    @return -1 wenn keine Verbindung existiert, anderenfalls die Entfernung der kürzesten Verbindung
    */
    private double distanceTo( TGraphNode target ) {
      // Sicherheit ...
      if ((this == null) || (target == null)) {
        return -1;
      }

      // Symmetrie
      if (this == target) {
        return 0;
      }

      // Eine Liste, in der die Knoten abgelegt werden, die abgearbeitet sind
      TList list = new TList();

      // rekursiv aufrufen
      return internalDistanceTo( this, target, list );
    }

    /** Setzt den Selected-Status für alle (!) Nachbarn auf den übergebenen Wert. 
    @param isSelected Der neue Status für die Elemente
    */
    public void setSelected( boolean isSelected ) {
      for (int i = 0; i < count(); i++) {
        getNext( i ).setSelected( isSelected );
      }
    }

    /** Liefert einen Nachbarknoten zurück 
    @param index Der Index des gewünschten Nachbarn (0 < index < count)
    */
    public TGraphic getNext( int index ) {
      return getNextNode( index ).getItem();
    }

    /** Liefert den Container (!) einen Nachbarknoten zurück 
    @param index Der Index des gewünschten Nachbarn (0 < index < count)
    */
    protected TNode getNextNode( int index ) {
      return (TNode) FNext.item( index );
    }

    /** Liefert TRUE zurück wenn das Element mit dem übergebenen Element direkt verbunden ist */
    public boolean isRelatedTo( TGraphic target ) {
      // Alle Nachbarn durchgehen und checken
      for (int i = 0; i < count(); i++) {
        if (getNext( i ) == target) {
          return true;
        }
      }
      return false;
    }
  
    /** Liefert TRUE zurück wenn das der Knoten mit dem übergebenen Knoten direkt verbunden ist */
    protected boolean isRelatedToNode( TNode target ) {
      // Alle Nachbarn durchgehen und checken
      for (int i = 0; i < count(); i++) {
        if (getNextNode( i ) == target) {
          return true;
        }
      }
      return false;
    }

    /** Setzt die Verbindung zu dem übergebenen Element. Es geschieht nichts, wenn der Verweis bereits existiert, oder
    auf sich selber zeigt.
    @param target Der Container für das Element, auf das verwiesen werden soll
    */
    public void connect( TGraphNode target ) {
      if ((target == null) || (target == this)) {
        return;
      }
      FNext.add( target );
      target.FNext.add( this );
    }

    /** Entfernt die Verbindung zu dem übergebenen Element, wenn sie besteht. Anderenfalls geschieht nichts.
    @param target Der Container für das Element, zu dem die Verbindung ggf. entfernt werden soll
    */
    public void deconnect( TGraphNode target ) {
      for (int i=0; i<count(); i++) {
        if (  (TNode) FNext.item( i ) == target  ) {
          FNext.delete( i );
          break;
        }
      }
      for (int i=0; i<target.count(); i++) {
        if (  (TNode) target.FNext.item( i ) == this  ) {
          target.FNext.delete( i );
          break;
        }
      }
    }

    /* Entfernt alle Verbindungen zu benachbarten Elementen, und zwar in beiden Richtungen,
    damit keine Inkonsistenzen entstehen 
    public void clearReferences() {
    }*/

    /** Nimmt einen Knoten in die Liste der Nachbarelemente auf. Wenn er bereits in der Liste existiert, geschieht nichts.
    @param next Der neue Nachbarknoten
    */
    public void addNode( TGraphNode next ) {
      FNext.add( next );
    }

    /** Zeichnet den Nodeauf Graphics g neu 
      * @param Graphics Der zu verwendende Context
      */
    public void paint (Graphics g) {
      // Dieses Element zeichnen
      getItem().examineSpace( g );

      // Dieses Element zeichnen (nochmal, kicher...)
      getItem().paint( g );
    }

    /** Entfernt Seperatoren Space aus String
      * @param String Der u. U. mit Space besetzte String
      * @return String Der von Space befreite String
      */
    private String textWithoutSeperator ( String ts ) {
 
       if ( ts.indexOf (" ") == -1 ) { return (ts); }
 
       String os = new String();
       for (int i = 0; i < ts.length(); i++) {
          if (ts.charAt(i) != ' ') { os += ts.charAt(i); }
       }
 
       return (os);
    }

    /** getSaveString() liefert die Werte des Containers und des enthaltenen Elements zusammengepackt in einem String
      * @return String Gepackte Information
      */
    public String getSaveString() {
       String ts = new String();
  
      // Hier Werte in ts einfügen 
       ts += (new Integer (index)).toString();
       ts += " "; // Anderer Feldtrenner bei Vorgabeformat!!!
 
       if (getItem() instanceof TTextbox) {
          ts += textWithoutSeperator ( ((TTextbox)getItem()).text );
       } else {
          ts += textWithoutSeperator ( getItem().getSaveString() );
       }
       ts += " ";  

       ts += (new Double (getItem().getLeft())).toString();
       ts += " ";  
       ts += (new Double (getItem().getTop())).toString();

       if (FNext.count()!=0) {

          for (int i = 0; i < FNext.count(); i++) {
             ts += " ";
             ts += (new Integer (getNextNode(i).index)).toString();
          }
       }      
 
       return (ts);
    }

    // Die Liste mit den Nachbarelementen
     public TList FNext;

    // Die Liste mit den Nachbarelementen für den Spannbaum
     protected TList FSNext;
   }

}