AuD Übung 09 (Graphen)

Gruppennummer und Namen der Gruppenmitglieder (Zeilenformat!)

Punkte:

Total

Abgabe: 31.1.2025

Es dürfen keine Standard Java Packages verwendet werden mit Ausnahme von System und String.

Der Java Code wird separat als klassisches natives Java Projekt abgegeben. Die wesentlichen Teile sollen aber zum Zwecke der Dokumentation hier in den Code Snippets eingetragen werden (unabhängig ob sie damit ausführbar sind oder nicht).

In dieser Übung soll eine einfache topologische Graphenklasse implementiert werden.

Knoten entsprechen Orten die durch einen Namen eindeutig identifizierbar sind (Schlüssel).
Jeder Knoten trägt Daten: Die Einwohnerzahl.
Es wird die Listenklasse aus der Übung 06 benötigt.
Es sollen Adjazenz und Erreichbarkeitsmatrizen berechnet werden.

Die Daten

Nodes:
Koblenz     115298
Bonn        335789
Mainz       222889
Siegen      102560
Koeln       1087353
Remagen     7965

Edges:
(Koblenz,Mainz)   84
(Mainz,Koblenz)   76
(Siegen,Koblenz)  79
(Koeln,Bonn)      28
(Bonn,Remagen)    22
(Remagen,Koblenz) 40
(Mainz,Bonn)      138
(Siegen,Koeln)    85

Die Graph Klasse

Implementiere den Graphen mit verketteten Listen. Dabei werden die Knoten in der Reihenfolge des Einfügens verkettet (Liste N) und dann abgehend von jedem Knoten die Kantenliste (Liste E).

Zu Beginn ist der Graph leer (new Graph()).
Es werden schrittweise neue Knoten mittels addNode(String name.int Einwohnerzahl) hinzugefügt.
Es werden schrittweise neue Kanten mittels addEdge(String from, String to, int distance) hinzugefügt.
Es können Kanten und Knoten entfernt werden (removeNode,`removeEdge*).

Aufgabe 1. Erstelle die Klasse Graph und füge den Programmkode unten ein.

Klasse Graph

public class Graph {
  int [][] A;
  int [][] E;
  int [][] Emin;

  Node nodes;

  public Graph () {
  }
  public void print () {
  }
  public void addNode(String name,int einwohnerzahl) {
  }
  public void addEdge(String from, String to,int distance) {
  }
  public void removeNode(String name) {
  }
  public void removeEdge(String fro, String to) {
  }
  public void updateA() {
    int n = edges.length();
    A=new int[n][n]; 
  }
  public void updateE() {
    int n = edges.length();
    E=new int[n][n];   
  }
  public void updateEmin() {
    int n = edges.length();
    Emin=new int[n][n]; 
  }
  public int getEinwohnerzahl() {

  }
}

Wir haben zwei Listenelemente: Knoten und Kante. Es werden hier doppelt verkettete Listen eingesetzt. Das vereinfacht die Listenmanipulation. Die Listen werden daher mit Methoden der Listenelemente verarbeitet.

Lösung.

VEJB

Aufgabe 2. Erstelle die Klassen Node und Edge und füge den Programmkode unten ein.

Klasse Node und Edge für Knoten- und Kantenlisten

public class Edge   {
  Edge rev;
  Edge next;
  Node from;
  Node to;
  int weight;
  public Edge (Node from, Node to, int weight) { 
  }
  public void addNext(Edge edge) {
  }
  public void addPrev(Edge edge) {
  }
  public void remove() {
    // remove this edge
  }
}
public class Node   {
  Node prev;
  Node next;
  Edge edge;
  publuc Node (String name,int einwohnerzahl) {
  }
  public void addNext(Node node) {
  }
  public void addPrev(Node node) {
  }
  public void remove() {
    // remove this node
  }
}

Tipp: Das Attribut from kann entfallen da die Edge Liste in Node eingebunden ist und der Knoten selber der Startpunkt jeder Kante ist.

Lösung.

VEJB

Die Adjazenzmatrix

Aus den Knoten- und Kantenlisten soll (zu jedem Zeitpunkt) eine Adjazenzmatrix erstellt werden (createA). Dieser Vorgang kann nach geänderten Graphen wiederholt werden und erzeugt eine neue Matrix A-

Die Adjazenzmatrix wird dynamisch beim Aufruf der updateA Methode mit aktueller Anzahl von Knoten n erzeugt

Eine Zeile ist der Startknoten, eine Spalte der Zielknoten.

Die Erreichbarkeitsmatrix

Neben der A Matrix soll auch die Erreichbarkeitsmatrix E und E_min berechnet werden.

\[ {E}={\sum_{{{i}={1}}}^{{n}}}{A}^{{i}}\\ {A}^{{i}}={\prod_{{{j}={1}}}^{{{i}}}}{A} \]

Es wird die Matrixalgebra aus Übung 3 für das Skalaraprodukt von Matrizen benötigt.

Zur Berechnung der kürzesten Pfade zwischen zwei Knoten i und j wird der Floyd-Warshall Algorithmus verwendet mit E_min als Ergebnis. Nicht erreichbare Pfade werden schließlich mit einen Null Wert in den Matrizen versehen.

Algorithmus 1. Die Initialisierung der Erreichbarkeitsmatrix mit den minimalsten Pfadlängen geschieht durch Kopieren von A und Ersetzung von 0 Werten mit Infinity.

a=[
[0,5,3,8],
[0,0,0,5],
[0,0,0,1],
[0,0,2,0]
]
e=copy(a)
for(i=0;i<n;i++) 
  for(j=0;j<n;j++)
    if (e[i][j]==0) e[i][j]=Infinity
n=4
for(k=0;k<n;k++)
 for(i=0;i<n;i++)
   for(j=0;j<n;j++) {
     if ((e[i][k]+e[k][j]) < e[i][j])
       e[i][j]=e[i][k]+e[k][j]
}

Aufgabe 3. Teste nun die Implementierung mit obigen Beispielen. Füge Knoten und Kanten ein. Erstelle die A, E und Emin Matrizen und gebe diese Aus. Trage die Matrixwerte unten ein. Gibt es nicht erreichbare Städte?

Lösung.

Created by the NoteBook Compiler Ver. 1.35.1 (c) Dr. Stefan Bosse (Fri Jan 31 2025 18:27:29 GMT+0100 (Central European Standard Time))