/*
* 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[0] = null;
}
/** Prü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.length) return false;
Enumeration tmp_enum = adlist[e.getTailValue()].elements();
while (tmp_enum.hasMoreElements()) { // solange noch Kanten in der Liste aufgeführt sind
Edge tmp_edge=new Edge();
Object tmp_element=tmp_enum.nextElement();
if (tmp_element.getClass().isInstance((Object)tmp_edge)) {
tmp_edge = (Edge) tmp_element;
if ((tmp_edge.getTailValue()==e.getTailValue()) && (tmp_edge.getHeadValue()==e.getHeadValue())) rc=true;
}
}
return rc;
}
/** Überprü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ückgegeben. Wurde die Kante nicht gefunden wird <i>null</i> zurückgegeben.
*/
public Edge find(int tail,int head) {
Edge e = null;
if (tail >= adlist.length) return e;
Enumeration tmp_enum = adlist[tail].elements();
while (tmp_enum.hasMoreElements()) { // solange noch Kanten in der Liste aufgeführt sind
Edge tmp_edge=new Edge();
Object tmp_element=tmp_enum.nextElement();
if (tmp_element.getClass().isInstance((Object)tmp_edge)) {
tmp_edge = (Edge) tmp_element;
if ((tmp_edge.getTailValue()==tail) && (tmp_edge.getHeadValue()==head)) e=tmp_edge;
}
}
return e;
}
/** Prüft, ob ein Knoten (durch einen Integer Wert reprä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ü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ü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üft, ob ein Knoten (Node Object)
* in der Adjazenzliste vorkommt (true) oder nicht (false).
*/
public boolean contains (Node n) {
return contains(n.value);
}
/** Prü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ück.
*/
public Vector getEdgesWithTail (int tailvalue) {
if (tailvalue < 0) return null;
if (tailvalue>=adlist.length) return null;
if (adlist[tailvalue]==null) return null;
Vector ewt = new Vector (adlist[tailvalue]);
return ewt;
}
/** gibt den Kantenvetor zu dem vorgegebenen Knoten (tail) zurück.
*/
public Vector getEdgesWithTail (Node tail) {
return getEdgesWithTail(tail.value);
}
/** fü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ü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öß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]==null) adlist[e.tail.value]=new Vector();
boolean test = contains(e);
// ist Kante noch nicht in der Adjazenzliste, dann füge den hinzu
if (!test) {
adlist[e.tail.value].addElement(e);
if (!contains(e.head)) add(e.head);
}
}
/** Fü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öß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]==null) adlist[n]=new Vector();
}
/** Fü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ü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ührt sind
Edge tmp_edge=new Edge();
Object tmp_element=tmp_enum.nextElement();
if (tmp_element.getClass().isInstance((Object)tmp_edge)) {
tmp_edge = (Edge) tmp_element; // Hole Element aus Vector
if (tmp_edge.equal(e)) adlist[e.getTailValue()].remove(tmp_edge);
}
}
}
}
}
/** Löscht einen Knoten, indem die Kantenliste auf null gesetzt wird.
* Weiterhin werden alle Kanten, die den Knoten beinhalten gelöscht.
*/
public void remove (Node n) {
remove(n.value);
}
/** Lö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ö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ührt sind
Edge tmp_edge=new Edge();
Object tmp_element=tmp_enum.nextElement();
if (tmp_element.getClass().isInstance((Object)tmp_edge)) {
tmp_edge = (Edge) tmp_element; // Hole Element aus Vector
if (tmp_edge.hasNode(n)) {
remove(tmp_edge);
}
}
}
}
}
}
}
/** Gibt die höchste Knotennummer zurück. Sind z.B. die Knoten
* 0,1,2,6,7,8 in der Adjazenzliste enthalten, dann wird die 8 zurückgegeben.
* Diese Methode gibt nicht die Anzahl der Knoten zurück!
*/
public int getMaxNodeNumber() {
int maxnode=-1;
int i;
for (i=adlist.length-1;i>=0 && maxnode==-1;i--) {
if (adlist[i]!=null) maxnode=i;
}
return maxnode;
}
/** Gibt einen Vector zurück, der die Knoten enthä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]!=null) v.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ü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ählt
Enumeration tmp_enum = adlist[i].elements();
while (tmp_enum.hasMoreElements()) { // solange noch Kanten in der Liste aufgeführt sind
Edge tmp_edge=new Edge();
Object tmp_element=tmp_enum.nextElement();
tmp_edge = (Edge) tmp_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öß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ück.
*/
public String toHtml() {
String rc=""; // bereite die Rü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ählt
Enumeration tmp_enum = adlist[i].elements();
while (tmp_enum.hasMoreElements()) { // solange noch Kanten in der Liste aufgeführt sind
rc = rc + "<font color=\"##005F00\">";
Edge tmp_edge = (Edge) tmp_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 FileOutputStream( filename );
ObjectOutputStream o = new ObjectOutputStream( file );
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ührt sind
Edge tmp_edge = (Edge) tmp_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 FileOutputStream( filename );
String string_adlist = new String();
string_adlist = this.toString();
fos.write( string_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ür jeden Knoten die Lä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 FileInputStream( filename );
ObjectInputStream o = new ObjectInputStream( file );
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((Edge) o.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ü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ält nur Routinen, die die Funktionalitä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ügen der Kante 0,1");
al.add(eins);
System.out.println("Adjazenzliste: \n" + al.toString() + "\n");
System.out.println("Hinzufügen der Kante 1,2");
al.add(zwei);
System.out.println("Adjazenzliste: \n" + al.toString() + "\n");
System.out.println("Hinzufü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ü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);
}
}
|