Inhaltsverzeichnis

1  Einleitung  1

2  Graphen und Netzwerke  3

2.1  Definitionen  3

2.1.1  Graph  3

2.1.2  Digraph  3

2.1.3  Weg  4

2.1.4  Netzwerk  4

2.1.5  Pr afluß  5

2.1.6  Fluß  5

2.1.7  maximaler Fluß  6

2.1.8  Restgraph  6

2.2  DIMACS  6

2.2.1  DIMACS Speicherformat  7

3  Algorithmen  9

3.1  MK-MAlgorithmus  9

3.2  Preflow-Push-Algorithmus  11

4  Grafische Darstellung  15

4.1  Visualisierung  15

4.1.1  Definition von Visualisierung  15

4.1.2  Ziele von Visualisierung  15

4.1.3  Datencharakteristik  16

4.1.3.1  Nominal, Ordinal, Quantitativ  16

4.1.3.2  Punkt, Skalar, Vektor  17

4.2  Software Visualisierung  18

4.2.1  Programm Visualisierung  18

4.2.2  Algorithmen Visualisierung  18

I

5  Implementation  21

5.1  Wahl der Programmiersprache JAVA  21

5.2  Graph-Generator und Darstellung  22

5.2.1  Vor uberlegungen  22

5.2.2  Klassen von Graphen  23

5.2.3  Nachtr agliche Modifikation eines Graphen  25

5.2.4  Visuelle Darstellung der Graphen  25

5.2.5  Visualisierungstechnik  27

5.2.5.1  Attribute  27

5.2.5.2  Farbauswahl  28

5.2.6  Erweiterung des DIMACS Speicherformats  32

5.3  Animation  34

5.3.1  Vor uberlegungen  34

5.3.2  Realisierung mit Threads  34

5.3.2.1  Die JAVA-Klasse HauptFrame  34

5.3.2.2  Die JAVA-Klasse UpdateThread  35

5.3.2.3  Die JAVA-Klasse ThreadAlgo  35

5.3.3  Darstellung der Animation  36

6  Zusammenfassung und Ausblick  38

6.1  Zusammenfassung  38

6.2  Ausblick  39

A  Anhang: Installation und Bedienung  40

A.1  Installation  40

A.2  Bedienungsanleitung  41

A.2.1  Men upunkt Graph  41

A.2.2  Men upunkt Knoten  42

A.2.3  Men upunkt Algorithmus  43

A.2.4  Men upunkt Farbschema  44

A.2.5  Men upunkt Beenden  44

A.2.6  Einstellungen der Graphtypen  44

II

A.2.7  Der Knopf ZOOM  46

A.2.8  Der Knopf CHANGE  46

III

1 EINLEITUNG 1

1 Einleitung

Das Ziel meiner Diplomarbeit ist es, die Arbeitsweise von maximalen Fluß-Algorithmen zu visualisieren und zu veranschaulichen. Folgendes Beispiel soll zeigen, daß solche Probleme auch in der Praxis relevant sind:

Ein Unternehmen transportiert Waren von einer Produktionsst¨ atte zu einem Distributionszentrum. Es werden daf¨ ur Transportunternehmen beauftragt, die feste planm¨ aßige Routen fahren und die maximale Kapazit¨ aten transportieren k¨ onnen.

Es stellt sich nun sowohl die Frage, wie die Menge der transportierten G¨ uter maximiert werden kann als auch die Frage, wieviele Fahrzeuge/h durch eine Stadt mit vorgegebenen Straßenkapazit¨ aten maximal gelangen k¨ onnen. In der Informatik sind solche Probleme als maximale Fluß Probleme auf gerichteten gewichteten Graphen bekannt.

Bei dem Studium von Algorithmen, die zur L¨ osung von maximalen Fluß Problemen bekannt sind, entstand die Idee, solche Algorithmen grafisch animiert darzustellen. Bei der Suche nach schon fertigen Programmen, die diese Idee verwirklichen, habe ich einige gefunden, die aber nur eine ” nahe“ Sicht auf

einem Graphen animieren, um die Funktionsweise im Detail zu zeigen. Das Ziel meiner Diplomarbeit ist es dagegen, eine weiter entfernte Sicht auf Graphen und Algorithmen zu realisieren, um deren Verhalten zu visualisieren. Um dieses umzusetzen war es n¨ otig, Visualisierungstechniken und Verfahren zu finden und auszuw¨ ahlen, die das Ziel einer m¨ oglichst expressiven und effektiven Visualisierung erreichen lassen.

Dabei wird zuerst ein Graph-Generator entwickelt, mit dem es erm¨ oglicht werden soll, verschiedene Klassen von Graphen zu generieren. Auf diesen verschiedenartigen Graphen sollen dann exemplarisch zwei Algorithmen ani- miert werden k¨ onnen. Dies wird im zweiten Teil der Arbeit realisiert werden.

1 EINLEITUNG 2

Außerdem war es bei der Darstellung von großen Graphen n¨ otig, durch geeignete Verfahren das Problem des ” zu kleinen Bildschirms“ zu l¨ osen.

Die Intention der Arbeit ist nicht die Implementierung eines m¨ oglichst effizienten, schnellen Algorithmus, sondern die Visualisierung der Arbeitsweise der Algorithmen. Die dabei von mir realisierte Software kann und sollte auch insbesondere zu Lehrzwecken eingesetzt werden, um Studierenden einen sehr anschaulichen Zugang zu diesem komplexen Thema zu erm¨ oglichen. Bei den beiden Implementierungen handelt es sich um zwei unterschiedliche Ans¨ atze zum L¨ osen des maximalen Fluß Problems.

2 GRAPHEN UND NETZWERKE 3

2 Graphen und Netzwerke

In diesem Abschnitt werden grundlegende Definitionen und Erl¨ auterungen, die zum Verst¨ andnis der nachfolgenden Ausf¨ uhrungen n¨ otig sind, dargestellt (siehe [COR90] und [HAU93]).

2.1 Definitionen

2.1.1 Graph

• Ein Graph ist ein Paar G = (V, E), wobei V (Knoten) eine endliche Menge und E (Kanten) eine Teilmenge aller ungeordneten Paare aus V ist. Die Anzahl der Knoten entspricht |V | = n und die Anzahl der Kanten |E| = m.

• Eine Kante e = [v i , v j ] ∈ E heißt inzident mit v i (bzw v j ) mit v i , v j ∈ V . Ist e = [v i , v j ] ⊂ E, so heißen v i und v j adjazent.

• Der Grad eines Knotens deg(v) ist die Anzahl der inzidenten Kanten aus E.

2.1.2 Digraph

• Ein Digraph oder auch gerichteter Graph ist ein Graph mit der zus¨ atzlichen Eigenschaft, daß die Menge der Kanten E eine Teilmenge der geordneten Paare (V × V ) ist. e = (v i , v j ) ∈ E.

• e ist inzident von v i und e ist inzident nach v j .

• v i ist adjazent nach v j und v j ist adjazent von v i wobei e = (v i , v j ) ∈ E.

• Bei einem Digraph wird zwischen Eingangsgrad indeg(v) und Aus- gangsgrad outdeg(v) unterschieden.

2 GRAPHEN UND NETZWERKE 4

2.1.3 Weg

• Ein Weg ist eine Folge von Knoten [v 1 , . . . , v k ] mit [v i−1 , v i ] ∈ E f¨ ur alle 1 < i ≤ k.

• k heißt L¨ ange des Weges.

2.1.4 Netzwerk

• Ein Netzwerk N = (V, E, c) ist ein gerichteter Graph G = (V, E) zusammen mit einer Kapazit¨ atzfunktion c : E → IR ⁺ o = [0, ∞[.

• Es gibt zwei besondere Knoten s(=Quelle) und t(=Senke) mit indeg(s) = 0 und outdeg(t) = 0. • Falls (u, v) / ∈ E folgt daraus c(u, v) = 0.

• Zu einer Funktion f : V × V → IR heißt

der ¨ Uberschuß im Knoten v. v heißt aktiv, falls e f (v) > 0.

2 GRAPHEN UND NETZWERKE 5

2.1.5 Pr¨ afluß

Ein Pr¨ afluß auf einem Netzwerk N ist eine reellwertige Funktion f : V ×V → IR ⁺ , die die folgenden Bedingungen erf¨ ullt:

• F¨ ur alle (u, v) ∈ V × V gilt: f (u, v) ≤ c(u, v).

Der Fluß von einem Knoten zu einem anderen Knoten darf die maximale Kapazit¨ at nicht ¨ uberschreiten.

• F¨ ur alle (u, v) ∈ V × V gilt: f (u, v) = −f (u, v).

Der Fluß von einem Knoten u zu einem Knoten v entspricht genau dem negativen Fluß in der entgegengesetzten Richtung.

• F¨ ur alle u ∈ V − {s, t} gilt:

Der ¨ Uberschuß in einem Knoten v (außer Quelle und Senke) ist gr¨ oßer Null, d.h. es geht kein Fluß verloren.

2.1.6 Fluß

• Gilt f¨ ur einen Pr¨ afluß die Bedingung e f (v) = 0 f¨ ur alle v ∈ V − {s, t}, so heißt der Pr¨ afluß f Fluß.

• F¨ ur einen Fluß f gilt:

• e f (t) = |f | heißt Wert von f.

Der Unterschied zum Pr¨ afluß besteht darin, daß es an keinem Knoten einen ¨ Uberschuß gibt. Alles, was aus der Quelle herausfließt, kommt auch in der Senke an.

2 GRAPHEN UND NETZWERKE 6

2.1.7 maximaler Fluß

• Ein Fluß heißt maximal, wenn |f | maximal ist.

Bei dem Problem des maximalen Flusses stellt sich folgende Aufgabe: Wieviel kann man in einem Netzwerk maximal von einer Quelle s zu einer Senke t unter Ber¨ ucksichtigung von gegebenen Kapazit¨ aten transportieren?

2.1.8 Restgraph

• Die Restkapazit¨ at c f einer Kante (v, w) wird folgendermaßen definiert:

c f (v, w) := c(v, w) − f (v, w) ≥ 0

• Damit kann man den Restgraphen G f definieren:

G f = (V, E f ) mit E f = {(v, w); c f (v, w) > 0}

2.2 DIMACS

Folgendes ist auf der DIMACS Homepage zu finden:

The Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) is a collaborative effort of Rutgers and Princeton Universities, AT&T Labs - Research, Bell Labs, Telcordia Technologies and NEC Research Institute and their scientific personnel, as well as their colleagues nationwide, working together to play a national leadership role in the development, application and dissemination of discrete mathematics (dm) and theoretical computer science (tcs)[...] http://dimacs.rutgers.edu/About/mission.html Seit 1990 werden bei DIMACS j¨ ahrlich die sogenannten ” Implementation

Challenges“ durchgef¨ uhrt. Dabei geht es darum, zu einem Thema effiziente

2 GRAPHEN UND NETZWERKE 7

und pfiffige Algorithmen zu implementieren. Bei dem ersten ” tion Challenges“ 1990/1991 gab es das Thema ”

ching“. Hier wurden viele bekannte Algorithmen zur L¨ osung des maximalen Fluß Problems entwickelt. Außerdem wurde das DIMACS Speicherformat f¨ ur Fluß Probleme definiert, das heute ein Standard zum Speichern von Graphen geworden ist.

2.2.1 DIMACS Speicherformat

Ich beschreibe hier nur die Definition des Speicherformats, das f¨ ur ein maximales Fluß Problem benutzt werden sollte. Die Definition der Formate f¨ ur kosteniminimale Fl¨ usse“ und ” Zuordnungsproblem“ k¨ onnen in

”

ftp://dimacs.rutgers.edu/pub/netflow/general-info/specs.tex nachgelesen werden.

• Eingabedateien:

Dateien mit Daten f¨ ur Probleme, die sich mit maximalem Fluß besch¨ aftigen, haben die Endung .max.

• Kommentare:

Kommentare beginnen mit einem kleinen c. Beispiel: c dies ist eine Kommentarzeile • Problemzeile:

Diese einmalige Zeile beginnt mit einem kleinen p gefolgt von der Art des Problems(hier max). Dann folgen noch die Anzahl der Knoten(als Integer) und die Anzahl der Kanten(als Integer). Beispiel: p max 60 100 • Knotenbeschreibung:

Die Zeilen werden durch ein kleines n angegeben. Dann folgt die