import simpleio.*; //aus audlib
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
/**
* Stadplan
* Diese Klasse kapselt die Orte und Strassen eines Stadplanes
* @author IFIS
* @version 1.1
*/
public class Stadtplan {
private List<Ort> orte; // Menge der Orte
private List<Strasse> strassen; // Menge der Strassen
private boolean[][] A; // Adjazenzmatrix
private List<Ort> bereitsBesuchteOrte;
/**
* Implementierung zu Aufgabe 1.a)
* Gibt alle direkten Nachfolger des uebergebenen Knotens in einer Liste zurueck.
* @param startOrt der Startknoten
*/
public List<Ort> getDirekteNachfolger(Ort startOrt) {
List<Ort> nachfolger = new LinkedList<Ort>();
Iterator<Strasse> it = strassen.iterator();
Strasse s;
while (it.hasNext()) {
s = it.next();
if (s.getStartOrt() == startOrt) {
nachfolger.add(s.getZielOrt());
} else if (s.getZielOrt() == startOrt && !s.isGerichtet()) {
nachfolger.add(s.getStartOrt());
}
}
return nachfolger;
}
/**
* Implementierung zu Aufgabe 1.b)
* Gibt alle direkten Vorgaenger des uebergebenen Knotens in einer Liste zurueck.
* @param zielOrt der Zielknoten
*/
public List<Ort> getDirekteVorgaenger(Ort zielOrt) {
List<Ort> vorgaenger = new LinkedList<Ort>();
Iterator<Strasse> it = strassen.iterator();
Strasse s;
while (it.hasNext()) {
s = it.next();
if (s.getZielOrt() == zielOrt) {
vorgaenger.add(s.getStartOrt());
} else if (s.getStartOrt() == zielOrt && !s.isGerichtet()) {
vorgaenger.add(s.getZielOrt());
}
}
return vorgaenger;
}
/**
* Berechnet die Adjazenzmatrix und speichert sie in dem privaten Attribut A
*/
private void calcAdjazenzmatrix() {
int knotenzahl = orte.size();
A = new boolean[knotenzahl][knotenzahl];
for (int i = 0; i < knotenzahl; i++) {
List<Ort> direkteNachfolger = getDirekteNachfolger(orte.get(i));
Iterator<Ort> itNachfolger = direkteNachfolger.iterator();
Ort nachfolger;
while (itNachfolger.hasNext()) {
nachfolger = itNachfolger.next();
A[i][nachfolger.getNummer()-1] = true;
}
A[i][i] = true;
}
for (int j = 0; j < knotenzahl; j++) {
for (int i = 0; i < knotenzahl; i++) {
if (A[i][j]) {
for (int k = 0; k < knotenzahl; k++) {
if (A[j][k]) {
A[i][k] = true;
}
}
}
}
}
}
/**
* Implementierung zu Aufgabe 1.c)
* Gibt alle von dem uebergebenen Knoten erreichbaren Orte in einer Liste zurueck.
* @param startOrt der Startknoten
* @return alle erreichbaren Orte
*/
public List<Ort> getErreichbarOrte(Ort startOrt) {
calcAdjazenzmatrix();
List<Ort> erreichbareOrte = new LinkedList<Ort>();
int ortnummer = startOrt.getNummer()-1;
int knotenzahl = orte.size();
for (int j = 0; j < knotenzahl; j++) {
if (A[ortnummer][j]) {
erreichbareOrte.add(orte.get(j));
}
}
return erreichbareOrte;
}
/**
* Implementierung zu Aufgabe 1.d)
* Gibt zurueck, ob ein Weg von startOrt zu zielOrt existiert.
* @param startOrt der Startknoten
* @param zielOrt der Zielknoten
* @return ob ein Weg existiert
*/
public boolean existiertWeg(Ort startOrt, Ort zielOrt) {
calcAdjazenzmatrix();
return A[startOrt.getNummer()-1][zielOrt.getNummer()-1];
}
/**
* Gibt das Ergebnis der Tiefensuche von Knoten startOrt zurueck
* @param startOrt der Startknoten
* @return das Ergebnis der Tiefensuche
*/
private List<Ort> recTiefensuche(Ort startOrt) {
List<Ort> rueckgabe = new LinkedList<Ort>();
List<Ort> nachfolger = getDirekteNachfolger(startOrt);
Iterator<Ort> it = nachfolger.iterator();
bereitsBesuchteOrte.add(startOrt);
rueckgabe.add(startOrt);
Ort ort;
while (it.hasNext()) {
ort = it.next();
if (!bereitsBesuchteOrte.contains(ort)) {
rueckgabe.addAll(recTiefensuche(ort));
}
}
return rueckgabe;
}
/**
* Implementierung zu Aufgabe 1.e)
* @param a
*/
public void tiefensuche(Ort a) {
bereitsBesuchteOrte = new LinkedList<Ort>();
List<Ort> DFS = recTiefensuche(a);
System.out.println("Tiefensuche von Ort " + a + ":");
Iterator<Ort> itDFS = DFS.iterator();
while (itDFS.hasNext()) {
System.out.println(itDFS.next());
}
}
/**
* Main-Methode als Einstiegspunkt.
*/
public static void main(String[] args) {
//Stadtplan erzeugen und aus Datei einlesen
Stadtplan plan = new Stadtplan();
plan.einlesen("luebeck_city.txt");
/**
* Testen der zu implementierenden Methoden
*/
Ort ort9 = plan.getOrt(9);
/**
* Aufgabe 1.a)
*/
List<Ort> direkteNachfolger = plan.getDirekteNachfolger(ort9);
System.out.println("Direkte Nachfolger von " + ort9 + " sind:");
Iterator<Ort> itNachfolger = direkteNachfolger.iterator();
Ort nachfolger;
while (itNachfolger.hasNext()) {
nachfolger = itNachfolger.next();
System.out.println(nachfolger);
}
/*
* Direkte Nachfolger von Theater Combinale (9) sind:
* Marke13 (42)
* Hüx (18)
* Sporthalle (47)
*/
System.out.println();
/**
* Aufgabe 1.b)
*/
List<Ort> direkteVorgaenger = plan.getDirekteVorgaenger(ort9);
System.out.println("Direkte Vorgaenger von " + ort9 + " sind:");
Iterator<Ort> itVorgaenger = direkteVorgaenger.iterator();
Ort vorgaenger;
while (itVorgaenger.hasNext()) {
vorgaenger = itVorgaenger.next();
System.out.println(vorgaenger);
}
/*
* Direkte Vorgaenger von Theater Combinale (9) sind:
* Hüx (18)
* Cafe Calma (48)
*/
System.out.println();
/**
* Aufgabe 1.c)
*/
List<Ort> erreichbarOrte = plan.getErreichbarOrte(ort9);
System.out.println("Erreichbare Orte von " + ort9 + " sind:");
Iterator<Ort> itErreichbar = erreichbarOrte.iterator();
Ort ort;
while (itErreichbar.hasNext()) {
ort = itErreichbar.next();
System.out.println(ort);
}
/*
* Erreichbare Orte von Theater Combinale (9) sind:
* Theater Combinale (9)
* Hauptpost (12)
* Hüx (18)
* Sternschnuppe (24)
* Marke13 (42)
* Sporthalle (47)
* Marke18 (49)
* Marke19 (50)
*/
System.out.println();
/**
* Aufgabe 1.d)
*/
Ort ort49 = plan.getOrt(49);
System.out.println("Existiert ein Weg von " + ort9 + " nach " + ort49 + ": " + plan.existiertWeg(ort9, ort49));
Ort ort10 = plan.getOrt(10);
Ort ort36 = plan.getOrt(36);
System.out.println("Existiert ein Weg von " + ort10 + " nach " + ort36 + ": " + plan.existiertWeg(ort10, ort36));
/*
* Existiert ein Weg von Theater Combinale (9) nach Marke18 (49): true
* Existiert ein Weg von Johannis-Kloster (10) nach Marke7 (36): false
*/
System.out.println();
/**
* Aufgabe 1.e)
*/
plan.tiefensuche(ort10);
/*
* Tiefensuche von Ort Johannis-Kloster (10):
* Johannis-Kloster (10)
* Marke19 (50)
* Sternschnuppe (24)
* Marke18 (49)
* Hauptpost (12)
* Ordnungsamt (11)
*/
}
/**
* Die Methode liest die übergebene Definition eines Stadplanes ein und generiert
* Ort- und Strasse-Objekte. Die Datei muss existieren und ein gültiges Format
* besitzen.
* @param dateiname der Dateiname
*/
public void einlesen(String dateiname) {
orte = new LinkedList<Ort>();
strassen = new LinkedList<Strasse>();
Eingabe def = Eingabe.oeffnen(dateiname);
int anzOrte = Integer.parseInt(def.readString()); // Anzahl der Orte
int anzStrassen = Integer.parseInt(def.readString()); // Anzahl der Strassen
for (int i = 0; i < anzOrte; i++) { // Schleife über alle Orte
String zeile = def.readString();
int semikolon = zeile.indexOf(';'); // Position des ersten Semikolons
String nummer = zeile.substring(0, semikolon); // Extraktion der Nummer
String name = zeile.substring(semikolon + 1, zeile.length()); // Extraktion des Namens
Ort ort = new Ort(Integer.parseInt(nummer), name); // Ort generieren
orte.add(ort); // Ort in Liste einfügen
}
for (int j = 0; j < anzStrassen; j++) {
String zeile = def.readString();
int semikolon = zeile.indexOf(';'); // Position des ersten Semikolons
String nummer = zeile.substring(0, semikolon); // Extraktion der Nummer
zeile = zeile.substring(semikolon + 1, zeile.length()); // Zeile verkürzen
semikolon = zeile.indexOf(';'); // Position des ersten Semikolons
String name = zeile.substring(0, semikolon); // Extraktion des Namens
zeile = zeile.substring(semikolon + 1, zeile.length()); // Zeile verkürzen
semikolon = zeile.indexOf(';'); // Position des ersten Semikolons
String start = zeile.substring(0, semikolon); // Extraktion des Startortes
zeile = zeile.substring(semikolon + 1, zeile.length()); // Zeile verkürzen
semikolon = zeile.indexOf(';'); // Position des ersten Semikolons
String ziel = zeile.substring(0, semikolon); // Extraktion des Zielortes
zeile = zeile.substring(semikolon + 1, zeile.length()); // Zeile verkürzen
semikolon = zeile.indexOf(';'); // Position des ersten Semikolons
String richtung = zeile.substring(0, semikolon); // Extraktion der Richtung
String gewicht = zeile.substring(semikolon + 1, zeile.length()); // Extraktion der Länge
Strasse strasse = new Strasse(Integer.parseInt(nummer), name); // Strasse erzeugen
int startOrtNr = Integer.parseInt(start);
Ort startOrt = orte.get(startOrtNr - 1); // Startort aus Liste holen
strasse.setBeginn(startOrt);
int zielOrtNr = Integer.parseInt(ziel);
Ort zielOrt = orte.get(zielOrtNr - 1); // Zielort aus Liste holen
strasse.setZiel(zielOrt);
strasse.setGerichtet(richtung.toLowerCase().equals("gerichtet")); // Richtung wird gesetzt
strasse.setGewicht(Integer.parseInt(gewicht));
strassen.add(strasse); // Strasse zu Liste hinzufügen
}
}
/**
* liefert der Ort zu einer gegebenen Nummer zurück
* @param nummer die Nummer des Ortes
* @return der zugehörige Ort
*/
public Ort getOrt(int nummer) {
return orte.get(nummer - 1);
}
}
Comments