Hallo,
ich sitz jetzt hier schon so lang an einer Aufgabe, aber ich komme irgendwie nicht weiter.
Das ist die Aufgabe:
[SPOILER]Implementieren Sie eine Klasse DirectedGraph, die einen gerichteten, gewichteten Graphen in Adjazenzlistendarstellung repräsentiert.
Sämtliche Knoten sollen in Ihrer Klasse in einen Container gespeichert werden, der bei gegebener numerischer ID in konstanter Zeit ein Knotenobjekt liefert. Zur Darstellung der Knoten sollen Sie eine eigene Klasse Node verwenden, Kanten sollen Sie als Objekte vom Typ Edge modellieren. Als Adjazenzlisten sollen Sie einen Container vom Typ Set verwenden. Dabei müssen Sie in jedem Knoten eine Menge von Edge-Objekten speichern, die wiederum
einen Verweis auf den entsprechenden Nachbarn des Knotens,
ein Gewicht und
ein Label
enthalten. Jeder Knoten speichert also diejenigen Knoten, die entlang einer gerichteten Kante direkt erreichbar sind. Verwenden Sie die entsprechenden Container aus dem Java Collections Framework!
Überlegen Sie sich, welche zugrundeliegende Implementierung Sie jeweils für die Containerklassen verwenden.
Implementieren Sie zum Zugriff auf den Graphen folgende getter-Methoden in Ihren Klassen:
DirectedGraph
public Node getNode(int id), Zugriff auf einen Knoten mit gegebener ID
Node
public int getId(), Ermitteln der ID eines Knotens
public String getLabel(), Ermitteln des Labels eines Knotens
Iteratoren
Implementieren Sie das Interface Iterable, damit Sie in einer for-each-Schleife über alle Knoten des Graphen iterieren können. Ebenso sollen Ihre Knoten das Interface Iterable implementieren, wobei hier über die Menge der Kanten iteriert werden soll. Für beide Implementierungen können Sie direkt die von den Containern gelieferten Iteratoren nutzen.
import java.util.Set;
import java.util.HashSet;
public class IterationDemo implements Iterable<Node> {
private Set<Node> data = new HashSet<Node>();
@Override
public Iterator<Node> iterator() {
return data.iterator();
}
public static void main(String[] args) {
IterationDemo demo = new IterationDemo();
[...]
for (Node node : demo) // for-each-loop
System.out.println(node);
}
}```
File I/O
Implementieren Sie Methoden, um Ihren Graphen
aus einer Datei einzulesen sowie
in eine Datei zu speichern.
Dabei soll folgendes Format (TGF) verwendet werden:
= | "
"
= | | | “”
= “#”
= [ ]
= [ ]
= ganze Zahl
= Fließkommazahl
= Whitespace
Nachfolgend sehen Sie ein Beispiel für einen Graphen im TGF sowie eine Zeichnung des selben Graphen.
Example: Graph in TGF
Vertices
0 A
1 B
2 C
3 D
4 E
5 F
Edges (directed, all weights set to 1.0)
0 1 1.0 AB
1 0 1.0
1 2 1.0 BC
2 1 1.0
3 2 1.0 CD
3 4 1.0 DE
4 5 1.0 EF
5 4 1.0
1 5 1.0 BF
2 4 1.0 CE
Erstellen Sie einen Konstruktor, der es erlaubt, den Graphen aus einem InputStream zu lesen, sowie eine Methode, um den Graphen in einen OutputStream zu schreiben:
public DirectedGraph(InputStream is) throws IOException;
public void print(OutputStream os) throws IOException;
Die beim Lesen des Streams möglicherweise auftretenden Exceptions sollen Sie weiterleiten, also nicht in Ihrer Graphklasse behandeln.
Überlegen Sie sich zusätzlich passende Exceptions, die bei fehlerhaftem Input ausgelöst werden!
Erstellen Sie anschließend eine minimalistische Klasse GraphUtils, die statische Methoden anbietet, um Graphen aus Dateien zu lesen sowie in Dateien zu schreiben.
public static DirectedGraph read(String filename) throws IOException;
public static void write(DirectedGraph graph, String filename) throws IOException;
Dabei können Sie folgendes Beispiel entsprechend adaptieren:
```import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
public class FileDemo {
public static void main(String[] args) {
try {
String filename = "FileDemo.java";
File file = new File(filename);
InputStream is = new FileInputStream(file);
Reader reader = new InputStreamReader(is);
BufferedReader br = new BufferedReader(reader);
try {
while (br.ready()) {
String line = br.readLine();
System.out.println(line);
}
} finally {
br.close();
}
} catch (FileNotFoundException e) {
// Handle file not found
} catch (IOException e) {
// Handle I/O Errors
}
}
}```
Ähnlich können Sie Daten über BufferedWriter in den OutputStream schreiben:
```File file = new File([...]);
OutputStream os = new FileOutputStream(file);
Writer writer = new OutputStreamWriter(os);
BufferedWriter bw = new BufferedWriter(writer);
bw.write([...]);
bw.close();
Parsen der Zeilen
Eine sehr einfache Möglichkeit, die eingelesenen Zeilen zu parsen, besteht darin, die regulären Ausdrücke (Regular Expressions) im java.util.regex-Package zu benutzen. Kompilieren Sie dazu ein Pattern-Objekt, indem Sie die statische Factory-Methode Pattern.compile(String) benutzen. Anschließend können Sie einen Matcher für einen eingegebenen String erzeugen. Dieser beantwortet Ihnen wiederum einerseits die Frage, ob der eingegebene String den regulären Ausdruck erfüllt, erlaubt Ihnen aber auch andererseits auf die passenden Teilstrings direkt zuzugreifen, denn matcher.group(i) liefert jeweils die i-te Klammer (beginnend mit Index 1) im regulären Ausdruck.
import java.util.regex.Pattern;
public class RegExpDemo {
public static void main(String[] args) {
String[] data = {
"1 2 Hallo!", // OK
"3 4", // OK, matcher.group(3) is null
"1 2 xy", // OK
"1234 5678 neun zehn.", // OK
"a b c d F" // Not OK
};
Pattern pattern = Pattern.compile("^([0-9]+)\\s+([0-9]+)\\s*(.+)?$");
for (String input : data) {
Matcher matcher = pattern.matcher(input);
if (matcher.matches()) {
System.out.println(matcher.group(1) + " " + matcher.group(2) + " " + matcher.group(3));
}
}
}
}```
Geben Sie Ihre Implementierungen als DirectedGraph.java, Node.java, Edge.java und GraphUtils.java ab!
[/SPOILER]
Ich kapier das noch nicht mit dem Benutzen der Container und weiß nicht, wie ich an die Aufgabe herangehen soll.
Könnt ihr mir weiterhelfen? Ich brauche keinen ganzen fertigen Code, sondern nur ein paar Hilfestellungen und vielleicht ein paar Code-Bruchstücke.
Ich wäre euch wirklich sehr dankbar dafür!
LG
el-flaco