Python 3 - Lernen und professionell anwenden

Kapitel 7

Sequenzen, Mengen und Generatoren

228

Für veränderbare Mengen vom Typ set sind einige weitere Operationen definiert, mit

denen Elemente hinzugefügt oder entfernt werden können.

7.6.2 Modellieren mit Mengen – Beispiel: Graphen

Viele Algorithmen lassen sich mit Mengen sehr knapp und elegant formulieren. Ein typi-

scher Anwendungsbereich ist die Verarbeitung von Graphen. Ein ungerichteter Graph

besteht aus einer Menge von Knoten

V = {v1, v2, ..., vn} und einer Menge von Kanten

E = {e1, e2, ..., em}. Eine Kante kann man sich als Verbindungslinie zwischen zwei

Knoten vorstellen. Die Kante

e, die zwei Knoten a und b verbindet, schreibt man als Menge

e = {a, b} auf.

Abbildung 7.4 zeigt einige Raumpläne, die die Anordnung von Räumen in einer Hausetage

wiedergeben. Die ersten beiden Raumpläne sind Ausschnitte aus einem größeren Plan. Sie

überlappen etwas, die Räume 4 und 5 gehören zu beiden Plänen.

s.copy() Liefert eine flache Kopie der Menge s

s.difference(t) s - t

Liefert die Differenz der Mengen s und t

s.intersection(t) s & t

Liefert den Durchschnitt der Mengen s und t

s.issubset(t) s <= t

Liefert True, falls s eine Teilmenge von t ist, und

False sonst

s.issuperset(t) s >= t

Liefert True, falls s eine Obermenge von t ist, und

False sonst

s.union(t) s | t

Liefert die Vereinigung der Mengen s und t

Operation Erklärung

s.add(x)

Der Menge s wird ein neues Element x hinzugefügt.

s.clear()

Alle Elemente der Menge s werden entfernt.

s.discard(x)

Aus der Menge s wird das Element x entfernt, sofern es existiert.

s.pop()

Gibt ein willkürlich ausgewähltes Element aus der Menge s

zurück und entfernt es aus der Menge. Wenn

s leer ist, gibt es

einen

KeyError.

s.remove(x)

Aus der Menge s wird das Element x entfernt, sofern es existiert.

Wenn

x nicht in der Menge enthalten ist, gibt es einen KeyError.

Tabelle 7.5: Zusätzliche Operationen für set-Objekte

Operation Operator Erklärung

Tabelle 7.4: Operationen für set- und frozenset-Objekte (Forts.)

229

7.6

Mengen

Abb. 7.4: Raumpläne. Oben zwei Fragmente, unten ein Gesamtplan als Vereinigung der

Fragmente

Die logische Struktur eines Raumplans kann man durch einen Graphen modellieren (siehe

Abbildung 7.5). Die Räume werden durch Knoten repräsentiert, die wir mit natürlichen

Zahlen benannt haben. Die Türen stellen wir durch Kanten dar, die zwei Knoten (Räume)

miteinander verbinden.

Abb. 7.5: Graphen, die Räume mit Türen modellieren

Raumplan 1

Raumplan 2

1 2 3

4

5

7

6

Raumplan 1 vereinigt mit Raumplan 2

5

4

1 2 3

4

5

7

6

1 2 3

4

7

6

5

Raumplan 1 Raumplan 2

4 5

1 2 3

4 5

7

6

Raumplan 1 vereinigt mit Raumplan 2

Kapitel 7

Sequenzen, Mengen und Generatoren

230

Wir schreiben nun ein kleines Skript mit zwei Funktionen, die folgende Probleme lösen:

쐽 Finde für einen beliebigen Raum alle Nachbarräume.

쐽 Vereinige zwei Raumpläne (die sich möglicherweise überschneiden) zu einem größeren

Gesamtplan.

Die Funktionen werden mithilfe der Beispielgraphen aus Abbildung 7.5 getestet. Vielleicht

überrascht es Sie, wie kurz und knapp die Funktionsdefinitionen sind.

Mit den Klassen

set, frozenset und tuple können wir einen Graphen praktisch genauso

aufschreiben wie in der Mathematik:

쐽 Eine Kante stellen wir als frozenset-Objekt dar, das die Nummern der beiden verbun-

denen Knoten enthält. Die Kantenmenge

E ist ein set-Objekt, das Kanten (frozenset-

Objekte) enthält.

쐽 Die Knotenmenge V ist ein set-Objekt, das Zahlen enthält.

쐽 Der Graph G ist ein Tupel (V, E) aus zwei set-Objekten.

Skript:

def findeNachbarraeume(plan, raum):

""" Menge aller Nachbarräume"""

raeume, tueren = plan

t_raum = set(t for t in tueren if raum in t) #1

na c h bar r aeum e = se t () #2

for t in t_raum:

nachbarraeume = nachbarraeume | t #3

return nachbarraeume - set([raum]) #4

def vereinige (plan1, plan2):

""" füge zwei Pläne zusammen """

return (plan1[0] | plan2[0], plan1[1] | plan2[1]) #5

V1 = {1, 2, 3, 4, 5}

E1 = s et( f r oze n s et(t ) #6

for t in [(1, 2),(2, 3), (2, 4),(3, 4),(4, 5)])

rau m p lan 1 = (V 1 , E1) #7

V2 = {4, 5, 6, 7}

E2 = set(frozenset(t)

for t in [(5, 4), (5, 6),(5 ,7), (6, 7)])

raumplan2 = (V2, E2)

gesamtplan = vereinige(raumplan1, raumplan2)

nachbarraeume = findeNachbarraeume(gesamtplan, 2)

print("Räume des Gesamtplans:")