[SOLVED] CS algorithm hadoop ER Programmierung

Programmierung
Graphen
Michael Goedicke
[email protected] auf der Basis von Folien von V Gruhn

Einfuhrung: Graphen
Listen dienen zur sequentiellen Speicherung von Daten: Jeder Knoten (auer dem letzten) hat genau einen Nachfolger.
Beispiel: Medienliste einer Bibliothek
Baume dienen zur hierarchischen Speicherung von Daten: Jeder Knoten (auer den Blattern) kann mehrere Sohne haben, die wiederum Wurzeln von Unterbaumen sein konnen.
Beispiel: Verzeichnisstruktur eines Dateisystems
Graphen dienen zur Speicherung von Daten, die in beliebigen Beziehungen zueinander stehen konnen, ohne dass bestimmte Knoten eine ausgezeichnete Rolle spielen.
Beispiel: Straenverbindungen in einem Navigationssystem
M. Goedicke Programmierung WiSe 2020/2021
2

Grundeigenschaften von Graphen
Nicht nur die Knoten eines Graphen, sondern auch die Kanten zwischen ihnen konnen Informationen tragen. In diesem Fall spricht man von attributierten Graphen.
Beispiel: Entfernungen zwischen Orten
Gilt eine Beziehung zwischen zwei Knoten in beide Richtungen, so verwendet man ungerichtete Kanten. Gilt die Beziehung nur in eine Richtung, so verwendet man gerichtete Kanten.
Beispiel: Verbindung zwischen Orten uber normale Strae oder Einbahnstrae
I.d.R. sind entweder alle Kanten gerichtet oder alle ungerichtet, daher spricht man von gerichteten bzw. ungerichteten Graphen.
M. Goedicke Programmierung WiSe 2020/2021
3

Definition Graph
G=(V,E) heit gerichteter Graph mit der Knotenmenge V und Kantenmenge E, falls gilt
V(vertices) ist eine endliche Menge und
E(edges)EVV
M. Goedicke Programmierung WiSe 2020/2021
4

Beispiel eines gerichteten Graphen
G = (V, E) mit
V = {A, B, C, D, E, F, G, H} und E = {(A, D), (D, A), (A, B),
(B, C), (C, A), (B, E), (A, E), (F, G), (F, F)}
M. Goedicke Programmierung WiSe 2020/2021
5

Definition Pfad/Weg, Zyklus
Def.: Sei G = (V, E) ein gerichteter Graph,
so besteht ein Pfad / Weg aus Knoten (p0, p1,, pk) von p0 nach pk fur k > 0 aus Knoten p0, , pk V,
so dass jedes Paar aufeinanderfolgender Knoten (pi, pi+1)
eine Kante bildet. Dies gilt fur 0 i k-1.
Def.: Ein Weg ist ein einfacher Weg, wenn kein Knoten ofter als einmal vorkommt,
Def.: Ein Semiweg ist ein Weg, wobei von der Richtung der Kanten abgesehen wird.
Def.: Ein Zyklus ist ein Pfad von einem Knoten zu sich selbst.
M. Goedicke Programmierung WiSe 2020/2021
6

Beispiele Weg / Zyklus
G = (V, E) mit
V = {A, B, C, D, E, F, G, H} und E = {(A, D), (D, A), (A, B),
(B, C), (C, A), (B, E), (A, E), (F, G), (F, F)}
M. Goedicke Programmierung WiSe 2020/2021
7

Definition Zusammenhang
Def.: Ein gerichteter Graph heit stark zusammenhangend, wenn es zwischen je zwei Knoten des Graphen einen Pfad gibt.
Ein gerichteter Graph heit schwach zusammenhangend, wenn es zwischen zwei Knoten immer einen Semiweg gibt.
M. Goedicke Programmierung WiSe 2020/2021
8

Definition Zusammenhang
Def.: Ein Teilgraph heit Zusammenhangskomponente, wenn er bzgl. der Zusammenhangseigenschaft (stark oder schwach) maximal ist, d.h. der Teilgraph kann nicht durch einen oder mehrere Knoten und/oder eine oder mehrere Kanten des Graphen erweitert werden, ohne diese Eigenschaft zu verlieren.
M. Goedicke Programmierung WiSe 2020/2021
9

Adjazenz von Knoten
Graphen werden durch Adjazenzlisten oder Adjazenzmatrizen dargestellt werden.
Sind n, p V Knoten im gerichteten Graphen (V, E), so heit {p V; (n, p) E}
die Adjazenzliste zum Knoten n.
Eine Alternative zu dieser Darstellung ist die Darstellung uber Boolesche Matrizen:
Man definiere eine Matrix (ak,l)k,l V und setze:
ak,l :=((k,l) E)
M. Goedicke Programmierung WiSe 2020/2021
10

Beispiel: Adjazenzmatrix zu attributiertem Graph
M. Goedicke Programmierung WiSe 2020/2021
11

Beispiel: Adjazenzliste zu attributiertem Graph
M. Goedicke Programmierung WiSe 2020/2021
12

Effizienzbetrachtungen zur Adjazenzdarstellung
Adjazenzmatrizen:
Der Platzverbrauch ist unabhangig von der Zahl der Kanten pro Knoten: Bei n
Knoten werden n2 Speicherplatze benotigt.
Es lasst sich schnell prufen, ob eine Kante vorhanden ist (indizierter Zugriff
auf zweidimensionales Array). Adjazenzlisten:
Benotigen Speicherplatz pro Kante. Wenn wenig Kanten vorkommen, dann
wird auch wenig Platz gebraucht.
Bei vielen Kanten muss man beim Suchen nach einer Kante erst eine ggf.
lange Kantenliste durchlaufen.
Daumenregel:
Adjazenzlisten sind fur Graphen mit wenigen Kanten pro Knoten geeignet.
Adjazenzmatrizen sind fur dichte Graphen geeignet.
Groe Matrizen werden seit Google/Yahoo etc auf verteilten Rechnern
dargestellt (siehe sog. Frameworks Hadoop, Spark . . . )
M. Goedicke Programmierung WiSe 2020/2021
13

Adjazenzlisten-Realisierung: Modell
Fachlicher Entwurf:
Knoten
-nummer
Graph
1 0..*
1
0..*
Kante
Technischer Entwurf:
ersterKnoten Knoten 1 0..1
ersteKante 1 0..1 zielKnoten 11
-attribut
Graph
-ersterKnoten: Knoten
Kante
-attribut: int -zielKnoten: Knoten -naechsteKante: Kante
-nummer: int
-ersteKante: Kante -naechsterKnoten: Knoten
11
naechster Knoten
0..1
naechste Kante
0..1
M. Goedicke Programmierung WiSe 2020/2021
14

Adjazenzlisten-Realisierung: Beispiel
6
erster Knoten
1
2
4
3
5
7
8
9
M. Goedicke Programmierung WiSe 2020/2021
15

Adjazenzlisten-Realisierung: Klassen
public class Graph {
private Knoten ersterKnoten;

class Knoten {
private int nummer;
private VType knotenAttribut; private Kante ersteKante; private Knoten naechsterKnoten;
}
class Kante {
private int attribut; private EType kantenAttribut; private Knoten zielKnoten; private Kante naechsteKante;
} }
M. Goedicke Programmierung WiSe 2020/2021
16

Typische strukturelle Methoden
strukturelle Methoden:
Erzeugen eines neuen Graphen
Einfugen eines Knotens
Loschen eines Knotens
Prufen, ob ein Knoten vorhanden ist
Einfugen einer Kante
Loschen einer Kante
Prufen, ob eine Kante zwischen zwei Knoten vorhanden ist
fachliche Methoden:
Traversierung (Durchlauf) des gesamten Graphen
Prufen, ob ein Pfad zwischen zwei Knoten vorhanden ist Finden des kurzesten Pfads zwischen zwei Knoten
Konstruktion des minimalen Spannbaums des Graphen
M. Goedicke Programmierung WiSe 2020/2021
17

Realisierung der Methoden
Das Erzeugen eines neuen Graphen erfolgt durch den Aufruf eines Konstruktors.
Das Hinzufugen eines Knotens ist eine Listenoperation auf der Liste der Knoten.
Das Entfernen eines Knotens ist eine Listenoperation auf der Liste der Knoten und auf all den Adjazenzlisten, die einen Zeiger auf den zu entfernenden Knoten besitzen.
Aufwand!
Der Test, ob ein Knoten vorhanden ist, stellt eine Operation auf der Liste aller Knoten dar.
M. Goedicke Programmierung WiSe 2020/2021
18

Realisierung der Methoden
Das Hinzufugen einer Kante ist eine Operation auf den Adjazenzlisten.
Das Entfernen einer Kante ist eine Operation auf den Adjazenzlisten.
Der Test, ob eine Kante vorhanden ist, stellt zunachst eine Operation auf der Liste aller Knoten (Ausgangsknoten der Kante finden) und anschlieend auf der entsprechenden Adjazenzliste dar.
M. Goedicke Programmierung WiSe 2020/2021
19

Coderahmen der Klasse Graph public class Graph {
private Knoten ersterKnoten;
public Graph() {}
public void knotenEinfuegen(int nummer, VType vAttr) {}
public void knotenLoeschen(int nummer) {}
public boolean knotenExistiert(int nummer) {}
public void kanteEinfuegen(int start, int ziel, EType eAttr) {}
public void kanteLoeschen(int start, int ziel) {}
public boolean kanteExistiert(int start, int ziel) {}
}
M. Goedicke Programmierung WiSe 2020/2021
20

Typische fachliche Methoden
strukturelle Methoden:
Erzeugen eines neuen Graphen
Einfugen eines Knotens
Loschen eines Knotens
Prufen, ob ein Knoten vorhanden ist
Einfugen einer Kante
Loschen einer Kante
Prufen, ob eine Kante zwischen zwei Knoten vorhanden ist
fachliche Methoden:
Traversierung (Durchlauf) des gesamten Graphen
Prufen, ob ein Pfad zwischen zwei Knoten vorhanden ist Finden des kurzesten Pfads zwischen zwei Knoten
Konstruktion des minimalen Spannbaums des Graphen
M. Goedicke Programmierung WiSe 2020/2021
21

Graphdurchlauf mit einmaligem Besuch
Gelegentlich sollen alle Knoten des Graphen einmal durchlaufen werden, um etwas mit ihnen zu tun, d.h. eine Besuchsmethode auf sie anzuwenden
hier einfach: Ausgabe der Knotennummer
Da Graphen keine vergleichbar regulare Struktur haben wie Baume, kann man keine vergleichbaren Durchlaufstrategien angeben.
Eine ganz einfache Ausgabestrategie ware das Durchlaufen der Knotenliste, allerdings verliert man dann jeden Aufschluss uber die Graphenstruktur.
Deshalb wird oft ein Tiefen- oder Breitendurchlauf benotigt. Hierdurch werden zusammenhangende Teilgraphen auch zusammenhangend ausgegeben.
M. Goedicke Programmierung WiSe 2020/2021
22

Besuchsmarkierung
Problem: Durch Zyklen kann man auf bereits besuchte Knoten kommen.
Losung: Markierung in jedem Knoten, die Besuchstatus angibt. Erweiterung von Knoten um boolesches Attribut besucht.
Problem: Was passiert, wenn der Durchlauf wiederholt werden soll?
Idee: Invertieren der Werte
Die Einfugemethode muss dann aber entsprechend arbeiten und das
besucht-Attribut auf den derzeit als unbesucht geltenden Wert setzen.
M. Goedicke Programmierung WiSe 2020/2021
23

Klasse Knoten mit Besuchsmarkierung
class Knoten {
private int nummer;
private VType knotenAttribut; private Kante ersteKante; private Knoten naechsterKnoten;
private boolean besucht;
void setBesucht(boolean besucht) { this.besucht = besucht;
}
boolean getBesucht() {
return besucht;
}
}
M. Goedicke Programmierung WiSe 2020/2021
24

Tiefendurchlauf (Depth First Search)
Ansatz: Wir versuchen von einem Knoten aus alle erreichbaren Knoten zu finden.
Dabei folgen wir zunachst immer der ersten abgehenden Kante.
Falls es keine Kante mehr gibt, die zu einem unbesuchten Knoten
fuhrt, kehren wir zuruck zum Vorgangerknoten und verfolgen von dort die nachste Kante.
Bei nicht zusammenhangenden Graphen:
Erst wenn in einem Teilgraph alle Knoten besucht sind, wird zu einem
Knoten des nachsten Teilgraphen gesprungen.
M. Goedicke Programmierung WiSe 2020/2021
25

Tiefendurchlauf: Beispiel
M. Goedicke Programmierung WiSe 2020/2021
26

Tiefendurchlauf: Algorithmus
Durchlaufmethode:
fur jeden Knoten in der Knotenliste des Graphen:
wenn Knoten noch nicht besucht: besuche den Knoten
Besuchsmethode:
markiere Knoten als besucht
fuhre Besuchsoperation aus (hier: Ausgabe der Knotennummer) fur jede Kante in der Kantenliste des Knotens:
wenn Zielknoten der Kante noch nicht besucht: besuche den Zielknoten
M. Goedicke Programmierung WiSe 2020/2021
27

Durchlaufmethode in Graph
public class Graph {

public void tiefendurchlauf() {
// Besuchsmarkierung fur diesen Durchlauf bestimmen boolean marke = !ersterKnoten.getBesucht();
// Knotenliste durchlaufen und unbesuchte besuchen Knoten knoten = ersterKnoten;
while (knoten != null) {
if (knoten.getBesucht() != marke) {
knoten.tiefendurchlauf(marke);
}
knoten = knoten.getNaechsterKnoten();
}
} }
M. Goedicke Programmierung WiSe 2020/2021
28

Besuchsmethode in Knoten
class Knoten {

void tiefendurchlauf(boolean marke) {
// Besuchsmarkierung setzen und Besuchsoperation ausfuhren besucht = marke;
System.out.println(nummer);
// Kantenliste durchlaufen und unbesuchte Zielkn. besuchen Kante kante = ersteKante;
while (kante != null) {
Knoten knoten = kante.getZielKnoten(); if (knoten.getBesucht() != marke) {
knoten.tiefendurchlauf(marke); }
kante = kante.getNaechsteKante(); }
} }
M. Goedicke Programmierung WiSe 2020/2021
29

Breitendurchlauf (Breadth First Search)
Ansatz wie bei Breitendurchlauf durch Baume: Speichere Knoten in Besuchsreihenfolge in FIFO-Queue Durchlaufmethode:
initialisiere Queue mit Startknoten solange die Queue nicht leer ist:
hole nachsten Knoten aus der Queue wenn Knoten noch nicht besucht:
markiere Knoten als besucht
fuhre Besuchsoperation aus (hier: Namen ausgeben)
fur jede vom Knoten abgehende Kante: hange Zielknoten an die Queue an
Bei nicht zusammenhangenden Graphen:
Bearbeitung mehrerer Teilgraphen mit zusatzlicher Schleife moglich
M. Goedicke Programmierung WiSe 2020/2021
30

Breitendurchlauf: Beispiel
M. Goedicke Programmierung WiSe 2020/2021
31

Realisierung mit Adjazenzmatrix
M. Goedicke Programmierung WiSe 2020/2021
32

Breitendurchlauf: Implementierung
M. Goedicke Programmierung WiSe 2020/2021
33

Definition: Transitive Hulle
Frage: Existiert ein Pfad zwischen zwei beliebigen Knoten?
Beantwortung durch Traversierung des Graphen aufwandig
Gunstiger: Einmalige Konstruktion der transitiven Hulle
Antwort kann unmittelbar daraus abgelesen werden
H(G) = (V, E) ist transitive Hulle von G = (V, E) gdw.
E = {(v, w) | v, w V und Pfad von v nach w existiert in E}
G H(G)
M. Goedicke Programmierung WiSe 2020/2021
34

Konstruktion der transitiven Hulle
Ansatz: Prufe fur jeden Knoten y, ob er Mittelteil eines Zwei-Kanten- Pfades von x nach z ist
wenn ja, fuge eine Kante unmittelbar von x nach z hinzu schrittweiser Ausbau des Graphen zur transitiven Hulle
M. Goedicke Programmierung WiSe 2020/2021
35

Warshalls Algorithmus
gegeben sei die Adjazenzmatrix A eines Graphen:
Ausbau zur transitiven Hulle dann wie folgt:
Nachteil: Laufzeitverhalten im Worst Case O(N3)
M. Goedicke Programmierung WiSe 2020/2021
36

Kurzeste Entfernung zweier Knoten
Frage: Wie lang ist der kurzeste Pfad zwischen zwei Knoten u und v?
Ansatz: Die kurzeste Entfernung von u zu den Knoten k1 einer
Untermenge S von V sei bereits bekannt.
Initial enthalte S dabei nur den Startknoten u.
In jedem Schritt: Betrachte alle Randknoten von S und ihre auerhalb von S liegenden Nachbarn (d.h. solche Knoten
k1 S, die eine Kante zu einem Knoten k2 S haben).
Fuge den Nachbarn k2 zu S hinzu,
bei dem die Summe der Entfernung vom Startknoten u zum Randknoten k1 und der Kantenlange von k1 zu k2 minimal ist.
M. Goedicke Programmierung WiSe 2020/2021
37

Beispiel: Kurzester Pfad
M. Goedicke Programmierung WiSe 2020/2021
38