Python bietet diverse Funktionen, um grundlegende Konzepte aus der Kombinatorik umzusetzen.
Zum Beispiel lassen sich alle Kombinationen von zwei oder mehr Mengen mittels der Funktion product
bilden, oder geordnete Auswahlen aus einer Liste mit oder ohne zurücklegen treffen.
Dokumentation: itertools
Für die folgenden Beispiele definieren wir uns die folgenden zwei diskrete Mengen (eine Liste ist OK)
animals = ["cat", "dog", "fish"]
owners = ["susi", "tim", "franziska", "henry"]
Alle Kombinationen durchprobieren
from itertools import product
for animal, owner in product(animals, owners):
print("%-5s belongs to %-10s" % (animal, owner))
cat belongs to susi cat belongs to tim cat belongs to franziska cat belongs to henry dog belongs to susi dog belongs to tim dog belongs to franziska dog belongs to henry fish belongs to susi fish belongs to tim fish belongs to franziska fish belongs to henry
# Ziehe 1 ...
from itertools import combinations
for owner1 in combinations(owners, 1):
print("%-10s" % (owner1))
susi tim franziska henry
# ... ziehe 2 ...
from itertools import combinations
for owner1, owner2 in combinations(owners, 2):
print("%-10s %-10s" % (owner1, owner2))
susi tim susi franziska susi henry tim franziska tim henry franziska henry
# ... oder 3 ....
from itertools import combinations
for owner1, owner2, owner3 in combinations(owners, 3):
print("%-10s %-10s %-10s" % (owner1, owner2, owner3))
susi tim franziska susi tim henry susi franziska henry tim franziska henry
# ... oder gar 4!
from itertools import combinations
for owner1, owner2, owner3, owner4 in combinations(owners, 4):
print("%-10s %-10s %-10s %-10s" % (owner1, owner2, owner3, owner4))
susi tim franziska henry
from itertools import combinations_with_replacement
for owner1, owner2 in combinations_with_replacement(owners, 2):
print("%-10s %-10s" % (owner1, owner2))
susi susi susi tim susi franziska susi henry tim tim tim franziska tim henry franziska franziska franziska henry henry henry
from itertools import permutations
for owner1, owner2 in permutations(owners, 2):
print("%-10s %-10s" % (owner1, owner2))
susi tim susi franziska susi henry tim susi tim franziska tim henry franziska susi franziska tim franziska henry henry susi henry tim henry franziska
from itertools import permutations
for owner1, owner2, owner3 in permutations(owners, 3):
print("%-10s %-10s %-10s" % (owner1, owner2, owner3))
susi tim franziska susi tim henry susi franziska tim susi franziska henry susi henry tim susi henry franziska tim susi franziska tim susi henry tim franziska susi tim franziska henry tim henry susi tim henry franziska franziska susi tim franziska susi henry franziska tim susi franziska tim henry franziska henry susi franziska henry tim henry susi tim henry susi franziska henry tim susi henry tim franziska henry franziska susi henry franziska tim
NetworkX ist eine der am weitesten verbreiteten Python-Bibliotheken für Graphentheorie mit einer Menge von Algorithmen.
(Eine andere Pythonbibliothek wäre SageMath / Graph Theory)
Ein Graph ist eine Menge von Knoten und Kanten (Vertices and Edges), wobei die Kanten für Verbindungen zwischen den Knoten stehen. Es gibt ungerichtete und gerichtete Verbindungen -- letzteres ist dann ein "gerichteter Graph". Eine Implementierung im Computer besteht nun darin, in einer Datenstruktur diese Kanten und Knoten effizient zu verwalten und dann darauf aufbauend Algorithmen aus der Graphentheorie anzuwenden.
Bemerkung: Falls die Bibliothek networkx
nicht installiert sein sollte, so kann man dies entweder in der Kommandozeile oder in Canopy unter Tools → Canopy Terminal mittels
pip install networkx
nachholen.
import networkx as nx
%matplotlib inline
nx.__version__
'1.11'
Hier wird ein einfacher Graph instanziert. Die Knoten sind einige Hauptstädte, die Kanten stellen (Zug-) Verbindungen zwischen ihnen dar.
g1 = nx.Graph()
g1.add_node("Wien")
g1.add_node("Graz")
g1.add_node("Linz")
g1.add_node("Salzburg")
g1.add_node("Innsbruck")
g1.add_node("Villach")
g1.add_node("St. Pölten")
g1.add_edge("Graz", "Salzburg")
g1.add_edge("Wien", "Salzburg")
g1.add_path(["Wien", "Graz", "Linz", "Salzburg", "Innsbruck"])
g1.add_path(["St. Pölten", "Villach", "Graz"])
Plot des Graphen, wobei mit spring_layout
eine gleichmäßig verteilte Positionierung der Knoten berechnet wird.
Anschließend werden nicht nur die Knoten und Kanten,
sondern auch die Namen der Knoten geplottet.
%matplotlib inline
pos = nx.spring_layout(g1)
nx.draw_networkx_labels(g1, pos, font_size = 12)
nx.draw(g1, pos)
Ausgehend von diesem Graph lassen sich einige Kennzahlen und Parameter ausrechnen:
Ist er zusammenhängend?
nx.is_connected(g1)
True
Grad von Graz
nx.degree(g1, "Graz")
4
Durchmesser des ganzen Graphs
nx.diameter(g1)
4
Exzentrizität
nx.eccentricity(g1)
{'Graz': 2, 'Innsbruck': 4, 'Linz': 3, 'Salzburg': 3, 'St. Pölten': 4, 'Villach': 3, 'Wien': 3}
Kürzester Weg von Linz nach Innsbruck
nx.shortest_path(g1, "Linz", "Innsbruck")
['Linz', 'Salzburg', 'Innsbruck']
Es gibt außerdem eine große Bibliothek für Graphen. Hier wird ein Dodekaedergraph geladen und der 10-te Knoten entfernt.
g2=nx.dodecahedral_graph()
g2.remove_node(10)
nx.draw(g2)
Durchmesser
nx.diameter(g2)
5
Vergleich der Dichte beider Graphen:
nx.density(g1), nx.density(g2)
(0.38095238095238093, 0.15789473684210525)
Histogramdaten für die Grade aller Knoten:
nx.degree_histogram(g2)
[0, 0, 3, 16]
Ein gerichteter Graph für die Wörter in einem Text.
text = '''11:15 Restate my assumptions:
1. Mathematics is the language of nature.
2. Everything around us can be represented and understood through numbers.
3. If you graph these numbers, patterns emerge.
Therefore: There are patterns everywhere in nature.'''
import re
words = re.compile(r'[a-zA-Z]+')
tokens = words.findall(text)
text_digraph = nx.MultiDiGraph()
for t1, t2 in zip(tokens[:-1], tokens[1:]):
text_digraph.add_edge(t1, t2)
%matplotlib inline
nx.draw(text_digraph, with_labels = True)
nx.shortest_path(text_digraph, "Everything", "numbers")
['Everything', 'around', 'us', 'can', 'be', 'represented', 'and', 'understood', 'through', 'numbers']
Ein Baum startet bei einem Wurzelknoten und verästelt sich ohne Schleifen zu bilden. Knoten ohne Kinder werden Blätter genannt.
rtree = nx.balanced_tree(2, 3)
%matplotlib inline
nx.draw(rtree)
nx.is_tree(rtree)
True
Liste der Blätter-Knoten (Grad ist 1)
[ k for k, v in nx.degree(rtree).items() if v == 1]
[7, 8, 9, 10, 11, 12, 13, 14]