Adjazenzliste.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
 *
 *  @(#)Adjazenzliste.java  1.0 04/03/09
 */

/* ToDo:
 * - Eingangsgrad- und Ausgangsgradberechnung
 */

import java.*;
import java.util.*;
import java.util.Enumeration;
import java.io.*;


/** Für die Verwaltung der Adjazenzliste wird vorrausgesetzt, 
 * dass die Knoten alle mit 0 starten und mit einser Schritten
 * also die Reihe 0,1,2,3,... enthält. Dieser Umstand vereinfacht die 
 * Verwaltung und verbessert die Performance, da nur der Index des Arrays
 * angesprungen werden muss, um die Kanten zu diesem Knoten zu erhalten. 
 * Hat ein Knoten keine Kanten, so ist die Kantenliste leer. Eine Kante 
 * darf nur einmal enthalten sein.
 */
 
public class Adjazenzliste {
  
  public Vector[] adlist; // Array von Vectoren
  
  /** Konstruktor, der eine leere Adjazenzliste erzeugt. In der leeren Adjazenzliste ist 
   * standardmäßig der Knoten 0 schon eingefügt.
   */    
  public Adjazenzliste (){
    adlist = new Vector[1];
    adlist[0null;
  }  
    
  /** Pr&uuml;ft, ob die Kante in der Adjazenzliste vorhanden ist.<br>
   * "false" bedeutet, dass die Kante nicht in der Adjanzenzliste vorhanden ist.<br>
   * "true" bedeutet, dass die Kante in der Adjazenzliste enthalten ist.<br>
   */  
  public boolean contains (Edge e) {
    boolean rc=false;
    if (e.tail.value >= adlist.lengthreturn false;
     Enumeration tmp_enum = adlist[e.getTailValue()].elements();
       
     while (tmp_enum.hasMoreElements()) { // solange noch Kanten in der Liste aufgef&uuml;hrt sind
        Edge tmp_edge=new Edge();
       Object tmp_element=tmp_enum.nextElement();

      if (tmp_element.getClass().isInstance((Object)tmp_edge))  {
        tmp_edge = (Edgetmp_element; 
        if ((tmp_edge.getTailValue()==e.getTailValue()) && (tmp_edge.getHeadValue()==e.getHeadValue())) rc=true;
      }
    }
     return rc;
  }
  
  /** &Uuml;berpr&uuml;ft, ob eine Kante in der Adjazenzliste enthalten ist, die von tail
   * nach head geht. Ist die Kante enthalten, wird eine Kopie der Kante 
   * zur&uuml;ckgegeben. Wurde die Kante nicht gefunden wird <i>null</i> zur&uuml;ckgegeben.
   */
  public Edge find(int tail,int head) {
    Edge e = null;
    if (tail >= adlist.lengthreturn e;
     Enumeration tmp_enum = adlist[tail].elements();
       
     while (tmp_enum.hasMoreElements()) { // solange noch Kanten in der Liste aufgef&uuml;hrt sind
        Edge tmp_edge=new Edge();
       Object tmp_element=tmp_enum.nextElement();

      if (tmp_element.getClass().isInstance((Object)tmp_edge))  {
        tmp_edge = (Edgetmp_element; 
        if ((tmp_edge.getTailValue()==tail&& (tmp_edge.getHeadValue()==head)) e=tmp_edge;
      }
    }
     return e;
  }
  
  /** Pr&uuml;ft, ob ein Knoten (durch einen Integer Wert repr&auml;sentiert)
   * in der Adjazenzliste vorkommt (true) oder nicht (false).
   */      
  public boolean contains (int n) {
    boolean enthaelt=false;
    if (n < adlist.length) {
      if (adlist[n].contains(new Node(n))) enthaelt=true;
    }
    return enthaelt;
  }
  
  /** Gibt die Kosten einer Kante zur&uuml;ck, die durch die Knoten tail und head
   * bestimmt ist.
   */
  public int getCost(Node tail,Node head) {
    int cost=0;
    if ((tail.getValue()!=-1)  || (head.getValue()!=-1)) {    
      if (tail.getValue()<=getMaxNodeNumber()) {
         Enumeration tmp_enum = adlist[tail.getValue()].elements();
         boolean kosten_gefunden=false;
         while ((tmp_enum.hasMoreElements()) && (kosten_gefunden!=true)) { // solange noch Kanten in der Liste aufgef&uuml;hrt sind
           Edge tmp_edge=(Edge)tmp_enum.nextElement();
           if ((tail.getValue()==tmp_edge.getTailValue()) && (head.getValue()==tmp_edge.getHeadValue())) {
             cost = tmp_edge.getCost();
             kosten_gefunden=true;
           }
         }
      }
    }
    return cost;
  }
  
  /** Pr&uuml;ft, ob ein Knoten (Node Object)
   * in der Adjazenzliste vorkommt (true) oder nicht (false).
   */      
  public boolean contains (Node n) {
    return contains(n.value);
  }

  /** Pr&uuml;ft, ob ein (Object)
   * in der Kantenliste von n vorkommt (true) oder nicht (false).
   */      
  public boolean contains (Object o,int n) {
    boolean enthaelt=false;
    if (n <= adlist.length) {
      if (adlist[n].contains(o)) enthaelt=true;
    }
    return enthaelt;
  }

  /** gibt den Kantenvetor zu dem vorgegebenen Knoten 
   * (tail durch Integer Wert dargestellt) zur&uuml;ck.
   */
  public Vector getEdgesWithTail (int tailvalue) {
    if (tailvalue < 0return null;
    if (tailvalue>=adlist.lengthreturn null;
    if (adlist[tailvalue]==nullreturn null;
    Vector ewt = new Vector (adlist[tailvalue]);
    return ewt;
  }
  
  /** gibt den Kantenvetor zu dem vorgegebenen Knoten (tail) zur&uuml;ck.
   */  
  public Vector getEdgesWithTail (Node tail) {
    return getEdgesWithTail(tail.value);
  }

  /** f&uuml;gt eine Kante in die Adjazenzliste ein, die durch die Knoten tail 
   * (Schwanz, bzw. Quelle) und head (Kopf, bzw. Ziel)  vorgegeben ist
   */
  public void add (Node tail, Node head,int cost) {
    Edge e = new Edge (tail,head,cost);
    add(e);
  }
  
  /** F&uuml;gt eine Kante e in die Adjazenzliste ein.
   */
  public void add (Edge e) {
    Vector[] tmp_adlist;
    // wenn der Knoten noch nicht in die Liste aufgenommen wurde
    if (e.tail.value > adlist.length - 1) {
      // kopiere Array in neues, das eine gr&ouml;ßere Dimension hat
      tmp_adlist = new Vector [e.tail.value + 1];
      System.arraycopy(adlist,0,tmp_adlist,0,adlist.length);
      adlist=new Vector [e.tail.value + 1];
      adlist=tmp_adlist;
      adlist[e.tail.value]=new Vector();
    }
    // Knoten ist nun in die Liste aufgenommen und es gibt adlist[e.tail.value]
    // Knoten in den Vector zu adlist[e.tail.value] eintragen, damit wird 
    // gekennzeichnet, dass dieser Knoten in dem Graohen existiert
    if (adlist[e.tail.value]==nulladlist[e.tail.value]=new Vector();
    boolean test = contains(e);
    // ist Kante noch nicht in der Adjazenzliste, dann f&uuml;ge den hinzu
    if (!test) {
      adlist[e.tail.value].addElement(e);
      if (!contains(e.head)) add(e.head);
    }
    
  }
    
  /** F&uuml;gt einen Knoten in die Adjazenzliste ein. Die Kantenliste des Knotens, 
   * der durch die Zahl n dargestellt, ist ein leerer Vector. 
   */
  public void add (int n) {
    Vector[] tmp_adlist;
    if (n > adlist.length - 1) {
      // kopiere Array in neues, das eine gr&ouml;ßere Dimension hat
      tmp_adlist = new Vector [n + 1];
      System.arraycopy(adlist,0,tmp_adlist,0,adlist.length);
      adlist=new Vector [n + 1];
      adlist=tmp_adlist;
      adlist[n]=new Vector();
    }
    if (adlist[n]==nulladlist[n]=new Vector();
    
  }

  /** F&uuml;gt einen Knoten in die Adjazenzliste ein. Die Kantenliste des Knotens 
   * n hat ist ein leerer Vector. 
   */
  public void add (Node n) {
    add(n.value);
  }

  /** Entfernt eine Kante aus der Kantenliste zu der Kante Edge, wobei die 
   * Kosten nicht gepr&uuml;ft werden.
   */
  public void remove (Edge e) {
    if (e.getTailValue()<adlist.length) {
      if (adlist[e.getTailValue()]!=null) {
        Enumeration tmp_enum = adlist[e.getTailValue()].elements();
          while (tmp_enum.hasMoreElements()) { // solange noch Kanten in der Liste aufgef&uuml;hrt sind
           Edge tmp_edge=new Edge();
           Object tmp_element=tmp_enum.nextElement();
           if (tmp_element.getClass().isInstance((Object)tmp_edge))  {    
            tmp_edge = (Edgetmp_element; // Hole Element aus Vector
            if (tmp_edge.equal(e)) adlist[e.getTailValue()].remove(tmp_edge);
           }
         }
       }
     }
  }

  /** L&ouml;scht einen Knoten, indem die Kantenliste auf null gesetzt wird.
   * Weiterhin werden alle Kanten, die den Knoten beinhalten gel&ouml;scht.
   */
   public void remove (Node n) {
     remove(n.value);
   }
   
  /** L&ouml;scht einen Knoten, den der Integerwert n representiert,
   *  indem die Kantenliste auf null gesetzt wird.
   *  Weiterhin werden alle Kanten, zu und von dem Knoten gel&ouml;scht.
   */
   public void remove (int n) {
    if (n < adlist.length) {   
      adlist[n]=null;
      int i;
      for (i=0; i<adlist.length;i++) {
        if (adlist[i]!=null) {
           Enumeration tmp_enum = adlist[i].elements();
            while (tmp_enum.hasMoreElements()) { // solange noch Kanten in der Liste aufgef&uuml;hrt sind
             Edge tmp_edge=new Edge();
             Object tmp_element=tmp_enum.nextElement();
             if (tmp_element.getClass().isInstance((Object)tmp_edge))  {
              tmp_edge = (Edgetmp_element; // Hole Element aus Vector
              if (tmp_edge.hasNode(n)) {
                remove(tmp_edge);
              }
            }
           }
        }
      }
    }
   }

  /** Gibt die h&ouml;chste Knotennummer zur&uuml;ck. Sind z.B. die Knoten 
   * 0,1,2,6,7,8 in der Adjazenzliste enthalten, dann wird die 8 zur&uuml;ckgegeben.
   * Diese Methode gibt nicht die Anzahl der Knoten zur&uuml;ck!
   */   
  public int getMaxNodeNumber() {
    int maxnode=-1;
    int i;
    for (i=adlist.length-1;i>=&& maxnode==-1;i--) {
      if (adlist[i]!=nullmaxnode=i;
    }
    
    return maxnode;
  }

  /** Gibt einen Vector zur&uuml;ck, der die Knoten enth&auml;lt, die in
   * der Adjazenzliste enthalten sind.
   */
  public Vector getNodeVector() {
    Vector v = new Vector();

    for (int i=0;i < adlist.length;i++) {
      if (adlist[i]!=nullv.add(new Node(i));
    }
    return v;
  }
  
  /** gibt die Adjazenzliste in ein String aus. Beispiel:<br>
   * 0: [ 1,3 ] <br>
   * 1: [ 2,4 3,5 ]
   */
  public String toString() {
    String rc=""// bereite die R&uuml;ckgabevariable vor
    for (int i=0;i<adlist.length;i++) { // solange Knoten existieren
      if (adlist[i]!=null) {
         rc = rc + i +": [ "// i ist der Tail in [] werden die Kanten aufgez&auml;hlt
       
         Enumeration tmp_enum = adlist[i].elements();
       
         while (tmp_enum.hasMoreElements()) { // solange noch Kanten in der Liste aufgef&uuml;hrt sind
           Edge tmp_edge=new Edge();
           Object tmp_element=tmp_enum.nextElement();

          tmp_edge = (Edgetmp_element; // Hole Element aus Vector
          rc = rc + tmp_edge.headCost2String()" "// Forme Head und Kosten in String um
         }
       
         rc = rc + "]\n"// Ende der Kantenliste
       }
    }
    return rc;
  }

  /** Ermittelt die Ordnung des Graphen, der durch diese Adjazenzliste dargestellt wird.
   * Ergebnis ist also die Anzahl der Knoten des Graphen.
   */
  public int ordnung() {
    int ord=0;
    for (int i=0;i<adlist.length;i++) { // solange Knoten existieren
      if (adlist[i]!=null) {
        ord++;
        System.out.println("Ordnung:"+ord);
       }
    }
    return ord;
  }
  
  /** Ermittelt die Gr&ouml;ße des Graphen. Der Rückgabewert entspricht der Anzahl der Kanten.
   */
  public int size() {
    int size=0;
    for (int i=0;i<adlist.length;i++) { // solange Knoten existieren
      if (adlist[i]!=null) {
        size+=adlist[i].size();
       }
    }    
    return size;
  }
  
  /** Gibt einen String in HTML Syntax zur&uuml;ck.
   */
  public String toHtml() {
    String rc=""// bereite die R&uuml;ckgabevariable vor
    for (int i=0;i<adlist.length;i++) { // solange Knoten existieren
      if (adlist[i]!=null) {
         rc = rc + "<font color=\"#0000BF\">"+i+"</font>" +": [ "// i ist der Tail in [] werden die Kanten aufgez&auml;hlt
         Enumeration tmp_enum = adlist[i].elements();
         while (tmp_enum.hasMoreElements()) { // solange noch Kanten in der Liste aufgef&uuml;hrt sind
           rc = rc + "<font color=\"##005F00\">";
           Edge tmp_edge = (Edgetmp_enum.nextElement()// Hole Element aus Vector
           rc = rc + tmp_edge.headCost2String()" "// Forme Head und Kosten in String um
         }
       
         rc = rc + "</font> ]<br>"// Ende der Kantenliste
       }
    }
    return rc;
  }

  /** Schreibt die Adjazenzliste in den Dateinamen 'filename'. Die Ausgabe erfolgt als 
   * Textdatei. Das Ergebnis von toString() sollte mit dem Dateninhalt identisch sein.
   */  
   public void writeTo (String filename) {    
    try {
        FileOutputStream file = new FileOutputStreamfilename );
        ObjectOutputStream o = new ObjectOutputStreamfile );  
        int listenlaenge = adlist.length;
        o.writeInt(listenlaenge);
        for (int i=0;i<listenlaenge;i++) {
          int vectorlaenge=-1;
          if (!(adlist[i]==null)) vectorlaenge = adlist[i].size();
          o.writeInt(vectorlaenge);
          if (vectorlaenge>0) {
             Enumeration tmp_enum = adlist[i].elements();
           while (tmp_enum.hasMoreElements()) { // solange noch Kanten in der Liste aufgef&uuml;hrt sind
              Edge tmp_edge = (Edgetmp_enum.nextElement();
            o.writeObject(tmp_edge)// schreibe Vector in den Stream    
           }
          }
        }
        o.close();
      catch (IOException e) {
        System.err.println(e);
      }
  }

   
  public void writeAsText (String filename) {
    
    try {
      FileOutputStream fos = new FileOutputStreamfilename );
      String string_adlist = new String();
      string_adlist = this.toString();
          fos.writestring_adlist.getBytes() );
          fos.close();
        catch (FileNotFoundException e) {
          
        catch (IOException e) {
        }
  }
  
  /** Liest aus der Datei <i>filename</i> die Adjazenzliste. Diese ist 
   * so abgescheichert, dass f&uuml;r jeden Knoten die L&auml;nge der Kantenliste,
   * bzw. die Anzahl der Kanten, abgespeichert ist. Anschliessend folgen dann 
   * Kantenelemente.<br>
   * Beispiel: <Kantenanzahl Knoten 0><1. Kante Knoten 0>,
   <2. Kante Knoten 0>,...,<n. Kante Knoten 0>,<Kantenanzahl Knoten 1>
   <1. Kante Knoten 0><2. Kante Knoten 0>,...
   */
    public void readFrom (String filename) {
      try  {
          FileInputStream file = new FileInputStreamfilename );
          ObjectInputStream o = new ObjectInputStreamfile );
          int listenlaenge = o.readInt();
          adlist=new Vector[listenlaenge];
          for (int i=0;i<listenlaenge;i++) {
            int vectorlaenge=o.readInt();
            if (vectorlaenge>=0) {
              adlist[i]=new Vector();
              for (int j=0;j<vectorlaenge;j++) {
                adlist[i].add((Edgeo.readObject());
              }
            }
          }
          o.close();
      catch IOException e ) { 
        YAV.status.setText(e.getMessage());
      catch ClassNotFoundException e ) { 
        YAV.status.setText(e.getMessage());
      

   }

  /** Gibt eine Referenz auf das Adjazenzlistenarray zur&uuml;ck.
   */
  public Vector[] getAdlist() {
    return adlist;
  

  /** Sortiert die Kantenliste zu Knoten <i>node</i>.
   */
  public void sortEdgeList(int node) {
    if (adlist[node]!=null) {
      Collections.sort(adlist[node]);
    
  }
  
  /** Sortiert die Kantenliste zu Knoten <i>node</i>.
   */  
  public void sortEdgeList(Node node) {
    sortEdgeList(node.getValue());
  }

  /** Sortiert die Kantenlisten zu allen Knoten.
   */
  public void sortEdgeLists() {
    int maxnnum = getMaxNodeNumber();
    for (int i=0;i<=maxnnum;i++) {
      sortEdgeList(i);
    }
  }

  /** Main enth&auml;lt nur Routinen, die die Funktionalit&auml;t der Klasse testen und zeigen.
   */
  public static void main(String[] args) {
    // test
     
    System.out.println("Testen einer Adjazenzliste.\n");
    
    System.out.println("Erzeugen einer Adjazenzliste.");    
    Adjazenzliste al = new Adjazenzliste ();
    System.out.println("Adjazenzliste: " + al.toString() "\n");    
    
    System.out.println("Erzeugen der Kanten 0,1 und 1,2 \n");    
    Edge eins = new Edge (0,1,3);
    Edge zwei = new Edge (1,2,4);
    Edge drei = new Edge (1,3,5);
    
    System.out.println("eins.toString() " + eins.toString());
    System.out.println("zwei.toString() " + zwei.toString()+"\n");
        
    System.out.println("Hinzuf&uuml;gen der Kante 0,1");
    al.add(eins);
    System.out.println("Adjazenzliste: \n" + al.toString() "\n");    
    
    System.out.println("Hinzuf&uuml;gen der Kante 1,2");
    al.add(zwei);
    System.out.println("Adjazenzliste: \n" + al.toString() "\n");    

    System.out.println("Hinzuf&uuml;gen der Kante 1,3");
    al.add(drei);
    System.out.println("Adjazenzliste: \n" + al.toString() "\n");    
      
    System.out.println("Schreibe in Datei c:/tmp/adlist.txt");
    al.writeTo("c:/tmp/adlist.txt");
    System.out.println("Lese aus Datei c:/tmp/adlist.txt");
    al.readFrom("c:/tmp/adlist.txt");
    System.out.println("Gelesene Adjazenzliste: \n" + al);

    System.out.println("Erzeugen einer Adjazenzliste ali.");    
    Adjazenzliste ali = new Adjazenzliste ();
    System.out.println("Adjazenzliste: " + ali.toString() "\n");    

    System.out.println("Schreibe in Datei c:/tmp/adli.txt");
    ali.writeTo("c:/tmp/adli.txt");
    System.out.println("Lese aus Datei c:/tmp/adli.txt");
    ali.readFrom("c:/tmp/adli.txt");
    System.out.println("Gelesene Adjazenzliste: \n" + ali);

    System.out.println("Erzeugen einer Adjazenzliste al.");    
    al = new Adjazenzliste ();
    System.out.println("Adjazenzliste: " + al.toString() "\n");    
    System.out.println("Hinzuf&uuml;gen der Knoten 1,4,5 \n");
    al.add(1);
    al.add(4);
    al.add(6);
    System.out.println("Lese aus Datei c:/tmp/adlist.txt");
    al.readFrom("c:/tmp/adlist.txt");
    System.out.println("Gelesene Adjazenzliste: \n" + al);
    al.add(10);
    al.remove(1);
    System.out.println("Adjazenzliste +  Knoten 10 - Knoten 1: \n" + al);

    System.out.println("Schreibe in Datei c:/tmp/adlist.txt");
    al.writeTo("c:/tmp/adlist.txt");
    System.out.println("Lese aus Datei c:/tmp/adlist.txt");
    al.readFrom("c:/tmp/adlist.txt");
    System.out.println("Gelesene Adjazenzliste: \n" + al);
  }


}