#!/usr/bin/env python
# coding: utf-8

# # Diskrete Mathematik
# 
# 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](https://docs.python.org/2/library/itertools.html)

# Für die folgenden Beispiele definieren wir uns die folgenden zwei diskrete Mengen (eine Liste ist OK)

# In[1]:


animals = ["cat", "dog", "fish"]
owners = ["susi", "tim", "franziska", "henry"]


# ## Produktbildung
# 
# Alle Kombinationen durchprobieren

# In[2]:


from itertools import product
for animal, owner in product(animals, owners):
    print("%-5s belongs to %-10s" % (animal, owner))


# ## Kombinationen aus einer Menge ziehen

# In[3]:


# Ziehe 1 ...
from itertools import combinations
for owner1 in combinations(owners, 1):
    print("%-10s" % (owner1))


# In[4]:


# ... ziehe 2 ...
from itertools import combinations
for owner1, owner2 in combinations(owners, 2):
    print("%-10s %-10s" % (owner1, owner2))


# In[5]:


# ... oder 3 ....
from itertools import combinations
for owner1, owner2, owner3 in combinations(owners, 3):
    print("%-10s %-10s %-10s" % (owner1, owner2, owner3))


# In[6]:


# ... 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))


# ## Kombinationen mit Zurücklegen

# In[7]:


from itertools import combinations_with_replacement
for owner1, owner2 in combinations_with_replacement(owners, 2):
    print("%-10s %-10s" % (owner1, owner2))


# ## Permutationen

# In[8]:


from itertools import permutations
for owner1, owner2 in permutations(owners, 2):
    print("%-10s %-10s" % (owner1, owner2))


# In[9]:


from itertools import permutations
for owner1, owner2, owner3 in permutations(owners, 3):
    print("%-10s %-10s %-10s" % (owner1, owner2, owner3))


# ## Graphen
# 
# [NetworkX](https://networkx.github.io/) ist eine der am weitesten verbreiteten Python-Bibliotheken für Graphentheorie
# mit einer [Menge von Algorithmen](http://networkx.github.io/documentation/latest/reference/algorithms.html).
# 
# 
# [NetworkX Dokumentation](http://networkx.github.io/documentation/networkx-1.9.1/)
# 
# (Eine andere Pythonbibliothek wäre [SageMath / Graph Theory](http://doc.sagemath.org/html/en/reference/graphs/index.html))
# 
# 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.

# In[10]:


import networkx as nx
get_ipython().run_line_magic('matplotlib', 'inline')
nx.__version__


# Hier wird ein einfacher Graph instanziert. Die Knoten sind einige Hauptstädte, die Kanten stellen (Zug-) Verbindungen zwischen ihnen dar. 

# In[11]:


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.

# In[12]:


get_ipython().run_line_magic('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?

# In[13]:


nx.is_connected(g1)


# Grad von Graz

# In[14]:


nx.degree(g1, "Graz")


# Durchmesser des ganzen Graphs

# In[15]:


nx.diameter(g1)


# Exzentrizität

# In[16]:


nx.eccentricity(g1)


# Kürzester Weg von Linz nach Innsbruck

# In[17]:


nx.shortest_path(g1, "Linz", "Innsbruck")


# Es gibt außerdem eine große Bibliothek für Graphen.
# Hier wird ein Dodekaedergraph geladen und der 10-te Knoten entfernt.

# In[18]:


g2=nx.dodecahedral_graph()
g2.remove_node(10)
nx.draw(g2)


# Durchmesser

# In[19]:


nx.diameter(g2)


# Vergleich der Dichte beider Graphen:

# In[20]:


nx.density(g1), nx.density(g2)


# Histogramdaten für die Grade aller Knoten:

# In[21]:


nx.degree_histogram(g2)


# ### Gerichteter Graph
# 
# Ein **gerichteter Graph** für die Wörter in einem Text.

# In[22]:


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.'''


# In[23]:


import re
words = re.compile(r'[a-zA-Z]+')
tokens = words.findall(text)


# In[24]:


text_digraph = nx.MultiDiGraph()
for t1, t2 in zip(tokens[:-1], tokens[1:]):
    text_digraph.add_edge(t1, t2)


# In[25]:


get_ipython().run_line_magic('matplotlib', 'inline')
nx.draw(text_digraph, with_labels = True)


# In[26]:


nx.shortest_path(text_digraph, "Everything", "numbers")


# ### Baum (Tree)
# 
# Ein Baum startet bei einem Wurzelknoten und verästelt sich ohne Schleifen zu bilden.
# Knoten ohne Kinder werden Blätter genannt.

# In[27]:


rtree = nx.balanced_tree(2, 3)
get_ipython().run_line_magic('matplotlib', 'inline')
nx.draw(rtree)


# In[28]:


nx.is_tree(rtree)


# Liste der Blätter-Knoten (Grad ist 1)

# In[29]:


[ k for k, v in nx.degree(rtree).items() if v == 1]


# In[ ]: