import matplotlib
import matplotlib.pylab as pl
import matplotlib.pyplot as plt
import numpy as np
import scipy.io
import networkx as nx


def print_divider(separator='-', length=80):
    print(''.join([separator for _ in range(length)]))
    print()
    
def print_heading(msg='', separator='-'):
    print(' ')
    print(msg)
    print_divider(separator=separator, length=len(msg))
    

plt.style.use('ggplot')
matplotlib.rcParams['figure.figsize'] = [12., 8.]

"""
Explanation: Übung 7
End of explanation
"""


# https://docs.scipy.org/doc/scipy/reference/tutorial/io.html
mat = scipy.io.loadmat('matrix.mat')

print('loadmat:\n%s' % str(mat))

# 'A': <4039x4039 sparse matrix of type '<class 'numpy.float64'>'
# with 176468 stored elements in Compressed Sparse Column format>
sparse_matrix = mat['A']

print('\nShape:\n%s' % str(sparse_matrix.shape))
print('\nType:\n%s' % type(sparse_matrix))
print('\nSparse Matrix:\n%s' % sparse_matrix)
print('\nCoordinate Matrix:\n%s' % sparse_matrix.tocoo())

"""
Explanation: Aufbau der Basisdaten
Laden der Matlab Daten
End of explanation
"""


# http://stackoverflow.com/questions/18651869/scipy-equivalent-for-matlab-spy
pl.spy(sparse_matrix, precision=0.01, markersize=.1)
pl.show()

# https://jakevdp.github.io/blog/2012/10/14/scipy-sparse-graph-module-word-ladders/
# from scipy.sparse import csgraph

# bft = csgraph.breadth_first_tree(sparse_matrix, 0, directed=False)
# print(bft)

graph = nx.from_scipy_sparse_matrix(sparse_matrix, create_using=nx.MultiGraph())

"""
Explanation: Darstellung in einer Adjazenzmatrix
Zur Erinnerung, innerhalb einer Adjazenzmatrix wird für jede Kante zwischen zwei Knoten eine 1 eingetragen, ansonsten eine 0. 
In der folgenden Grafik sind einige große Rechtecke zu sehen. D.h. dass es in der Matrix einige Bereiche gibt in denen die Knoten stark untereinander verbunden sind. In den jeweiligen Ecken befinden sich wenige Knoten, die eine "Verbindung" zum nächsten Bereich besitzen. Das bedeutet, dass es in dem zu Grunde liegenden Graph einige wenige Knoten gibt, die als Verbindungsstück zu einem anderen Bereich fungieren. Tendenziell wird viel Datenverkehr über diese Knoten laufen, wenn Knoten aus unterschiedlichen Bereichen miteinander kommunizieren wollen. Diese Knoten sind ein Nadelöhr im gesamten Graph. Wenn Sie wegfallen entstehen einzelne Inseln die untereinander nicht kommunizieren können.
End of explanation
"""


nx.draw(graph, node_shape='o', node_size=12, node_color='#000000', edge_color='#aaaaaa')
plt.show()

"""
Explanation: Darstellung als Graph
Im folgenden Graph sind die einzelnen Inseln ganz gut zu erkennen.
End of explanation
"""


root_id = 42
print_heading('Wurzel %d' % root_id, separator='=')
print('Nachbarn: %s\n' % nx.neighbors(graph, root_id))
print_heading('``nx.dfs_successors`` der Wurzel')
node = nx.dfs_successors(graph, root_id)
for _id in sorted(node.keys())[:10]:
    print('        id: %d' % _id)
    print('successors: %s' % node[_id])

"""
Explanation: nx.dfs_successors
In den Aufgaben wird als Wurzel immer die 42 verwendet. Über die Funktion nx.dfs_successors wird aus dem ursprünglichen ungereichteten nx.MultiGraph ein gerichteter nx.DiGraph erzeugt. Die der Wurzel folgenden Knoten usw. enthalten deren Nachfolger nach depth first search-Mechanik. Die Datenstruktur ist ein dict mit den Ids der Knoten und einer Liste der Nachfolger.
End of explanation
"""


dfs_tree = nx.dfs_tree(graph, 42)
print_heading('Knoten des Baums der Tiefensuche')
print(dfs_tree.nodes()[:10])

root_id = 42
dfs_tree = nx.dfs_tree(graph, root_id)
edges = dfs_tree.edges()[:10]

print_heading('Kanten des Baums der Tiefensuche')
for edge in edges:
    print(edge)

"""
Explanation: nx.dfs_tree
Im Gegensatz zu nx.dfs_successors liefert diese Methode kein dict sondern den eigentlichen Graphen. Wichtige Methoden zu Analyse sind an dieser Stelle:

G.nodes()
G.edges()

nodes liefert alle Knoten des Graphen. edges liefert alle Kanten. Natürlich kann der Fall eintreten, dass ausgehend von einem Knoten keine weitere Verbindung zu anderen Knoten existiert, da es sich um einen gerichteten Graphen handelt. Sollte also eine Analyse der Nachbarn erfolgen (nx.neighbors(graph, node) muss diese Analyse auf dem ursprünglich geladenen Graphen erfolgen.
End of explanation
"""


neighbor_count = 0
def neighbor_counter(node, debug=False):
    global neighbor_count
    if debug:
        print('node {:5d}, neighbors: {:5d}'.format(node, len(nx.neighbors(graph, node))))
    neighbor_count += len(nx.neighbors(graph, node))

"""
Explanation: Zähler der Nachbarn
Die folgende Methode dient zum Zählen der Nachbarn, wenn der Graph rekursiv durchgegangen wird.
End of explanation
"""


import sys
sys.setrecursionlimit(2000)

"""
Explanation: Limit der Rekursionstiefe
Zum aktuellen Zeitpunkt ist der Standardwert der Rekursionstiefe auf 1000 begrenzt. In der folgenden Beispielen wird eine höhere Tiefe erforderlich.
End of explanation
"""


from datetime import datetime

root_id = 42
max_visits = (100, 200, 400, 800, 1600)

def timed(func):
    start = datetime.now()
    def wrapper(*args, **kwargs):
        func(*args, **kwargs)
        end = datetime.now()
        print('  Dauer: %s' % str(end - start), end='\n\n')
    return wrapper

def crawl_dfs(edges: list, node: int, max_visits: int, S: set, callback):
    """Crawlt einen Graph anhand seiner Kanten mit Hilfe von
    depth first search in rekursiver Variante.
    
    :param edges: Liste mit 2-Tupeln, die alle Kanten des Graphen beinhalten
    :param node: Id des Ausgangsknotens
    :param max_visits: Anzahl der maximal zu besuchenden Knoten
    :param S: Menge an Knoten, die bereits besucht wurden
    :param callback: Funktion mit einem Parameter, der bei Aufruf
        den besuchten Knoten enthält
    """
    S.add(node)
    callback(node)
    neighbors = [e[1] for e in edges if e[0] == node]
    for neighbor in neighbors:
        if neighbor not in S and len(S) < max_visits:
            crawl_dfs(edges, neighbor, max_visits, S, callback)


print_heading('Crawl des Graphs über Tiefensuche')

g = nx.dfs_tree(graph, root_id)
edges = g.edges()

@timed
def timed_crawl_dfs(max_visits):
    global neighbor_count
    neighbor_count = 0
    crawl_dfs(edges, root_id, max_visits=count, S=set(), callback=neighbor_counter)
    print('Knotengrad {:.4f} bei {:5d} besuchten Knoten'.format((neighbor_count / count), count))
    
for count in max_visits:
    timed_crawl_dfs(count)

def crawl_dfs_iter(edges, root, max_visits=10):
    """Generator der einen Graph anhand seiner Kanten mit Hilfe von
    depth first search in iterativer Variante crawlt. Die Id des
    besuchten Knoten wird dabei geliefert.
    
    :param edges: Liste mit 2-Tupeln, die alle Kanten des Graphen beinhalten
    :param root: Id des Ausgangsknotens
    :param max_visits: Anzahl der maximal zu besuchenden Knoten
    """
    visited = 0
    S = set()
    Q = [] 
    Q.append(root)
    while Q and visited < max_visits:
        
        node = Q.pop()
        yield node
        visited += 1
        if node not in S and visited < max_visits:
            S.add(node)
            neighbors = [e[1] for e in edges if e[0] == node]
            
            # umdrehen der nachbarn, damit diese in der richtigen
            # reihenfolge durch pop wieder entnommen werden
            neighbors.reverse()
            for neighbor in neighbors:
                Q.append(neighbor)

print_heading('Crawl des Graphs über iterative Tiefensuche')

g = nx.dfs_tree(graph, root_id)
edges = g.edges()

@timed
def timed_crawl_dfs_iter(max_visits):
    neighbor_count = 0
    for node in crawl_dfs_iter(edges, root_id, max_visits=count):
        # print('node {:5d}, neighbors: {:5d}'.format(node, len(nx.neighbors(graph, node))))
        neighbor_count += len(nx.neighbors(graph, node))
        
    msg = 'Knotengrad {:.4f} bei {:5d} besuchten Knoten'
    print(msg.format((neighbor_count / count), count))

for count in max_visits:
    timed_crawl_dfs_iter(count)

def crawl_bfs(edges, Q=[], S=set(), max_visits=10, callback=lambda x: x):
    next_q = []
    while len(S) < max_visits:
        for node in Q:
            if node not in S and len(S) < max_visits:
                S.add(node)
                callback(node)
                neighbors = [n[1] for n in edges if n[0] == node and n[1] not in S]
                next_q += neighbors
        crawl_bfs(edges, next_q, S, max_visits, callback)
        
print_heading('Crawl des Graphs über Breitensuche')

g = nx.bfs_tree(graph, root_id)
edges = g.edges()

@timed
def timed_crawl_bfs(max_visits):
    global neighbor_count
    neighbor_count = 0

    crawl_bfs(edges, [root_id], max_visits=count, S=set(), callback=neighbor_counter)
    print('Knotengrad {:10,.4f} bei {:5d} besuchten Knoten'.format((neighbor_count / count), count))

for count in max_visits:
    timed_crawl_bfs(count)

def crawl_bfs_iter(edges, root, max_visits=10):
    visited = 0
    # Verwendung von Q als Queue (FIFO)
    Q = []
    S = set()
    
    Q.append(root)
    S.add(root)
    
    while Q and visited < max_visits:
        node = Q.pop(0)
        yield node
        visited += 1
        neighbors = [e[1] for e in edges if e[0] == node]
        for neighbor in neighbors:
            if neighbor not in S:
                S.add(neighbor)
                Q.append(neighbor)
                
print_heading('Crawl des Graphs über iterative Breitensuche')

g = nx.bfs_tree(graph, root_id)
edges = g.edges()

@timed
def timed_crawl_bfs_iter(max_visits):
    neighbor_count = 0

    for node in crawl_bfs_iter(edges, root_id, max_visits=count):
        # print('node {:5d}, neighbors: {:5d}'.format(node, len(nx.neighbors(graph, node))))
        neighbor_count += len(nx.neighbors(graph, node))
        
    print('Knotengrad {:10,.4f} bei {:5d} besuchten Knoten'.format((neighbor_count / count), count))

for count in max_visits:
    timed_crawl_bfs_iter(count)

"""
Explanation: Aufgabe 7.1 Crawlen unstrukturierter Netze
7.1.1 Vergleich der mittleren Knotengrade
Implementierung der Algorithmen
An dieser Stelle sind zunächst Tiefen- und Breitensuche implementiert und erklärt. Der reine Vergleich folgt später im Dokument.
End of explanation
"""


sum([len(nx.neighbors(graph, n)) for n in graph.nodes()]) / len(graph.nodes())

"""
Explanation: Man kann an den einzeln ermittelten Knotengraden sehen, dass selbst bei einer hohen Anzahl an Knoten (>= 800) ein ungenaues Vergleichsergebnis zum tatsächlichen mittleren Knotengrad ergibt. Eine Annäherung ist trotzdem zu erkennen.
Neben der Ermittlung der Knotengrade kann man sehen, dass ein Crawling mittels BFS schneller ist als die DFS Umsetzung. Bei einer sehr hohen Anzahl an durchsuchten Knoten empfiehlt sich die iterative Implementierung, da ansonsten wieder Heap-Probleme bei einer Rekursion auftreten.
Der tatsächliche mittlere Knotengrad berechnet sich auch der Summe aller Nachbarn aller Knoten des ungerichteten Graphs $g$ durch die Anzahl der Knoten.
$\dfrac{\sum_{i=0}^{n} neighbors(g[i])}{n}$
End of explanation
"""


def ecdf(values):
    """Liefert eine Liste an 2-Tupeln, die die x- und y-Werte von
    Punkten innerhalb einer empirischen Distributionsfunktion darstellen.
    
    Beispiel:
    Gegeben sei die Menge (2, 3, 3, 5, 8, 9, 9, 10).
    
    Geliefert wird 
    [(2, 0.12), (3, 0.38), (5, 0.5), (8, 0.62), (9, 0.88), (10, 1.0)]
    
    12% aller Werte sind <= 2
    38% aller Werte sind <= 3
    50% aller Werte sind <= 5
    ...
    """
    # 1. sortieren der werte
    values = sorted(values)

    # 2. reduzieren der werte auf eindeutigkeit
    unique_values = sorted(list(set(values)))

    # 3. ermittlung wie viele werte <= x sind fuer jede eindeutige zeit
    cumsum_values = []
    for u in unique_values:
        cumsum_values.append((u, len([1 for _ in values if _ <= u])))

    # 4. ermittlung der prozentualen anteile wie viele werte <= x sind
    y = np.round([c / len(values) for t, c in cumsum_values], decimals=2)
        
    return list(zip(unique_values, y))
    
def plot_ecdf(points, complementary=False, plotter=plt, 
              point_color='#e53935', line_color='#1e88e5', 
              title=None, xlabel=None, label=''):
    x = np.array([p[0] for p in points])
    y = np.array([p[1] for p in points])
    
    # das komplement einer cdf ist CCDF(x) = 1 - CDF(x)
    if complementary:
        y = 1 - y # numpy array
    
    # plot mit spezifischer punktefarbe ansonsten wird die farbe von pyplot gewaehlt
    if point_color:
        plotter.plot(x, y, color=point_color, linestyle=' ', marker='.', label=label)
    else:
        plotter.plot(x, y, linestyle=' ', marker='.', label=label)
    
    # entweder ist hier pyplot oder eine achse gegeben
    if plotter == plt:
        plotter.title(title)
        plotter.xlabel(xlabel)
    else:
        plotter.set_title(title)
        plotter.set_xlabel(xlabel)
    
    # rand hinzufuegen
    x_min, x_max, y_min, y_max = plotter.axis()
    plotter.axis((x_min - 10, x_max + 10, y_min - .02, y_max + .02))

    # von x bis x + 1 wird ein einzelner strich geplottet
    if line_color:
        for i in range(len(x)):
            x_0 = x[i]
            x_1 = x[i + 1] if i < len(x) - 1 else x[i] + 1
            plotter.plot([x_0, x_1], [y[i], y[i]], color=line_color, linestyle='-', label=label)

# enthaelt das anzahl nachbarn jedes knoten des ungerichteten graphen
neighbor_count = [len(nx.neighbors(graph, n)) for n in graph.nodes()]

f, axes = plt.subplots(ncols=2, nrows=1, figsize=(12, 3))
ax1, ax2 = axes.ravel()

plot_ecdf(ecdf(neighbor_count), 
          plotter=ax1, 
          title='CDF über die Anzahl Nachbarn', 
          xlabel='Anzahl Nachbarn')
plot_ecdf(ecdf(neighbor_count), 
          plotter=ax2, 
          title='CCDF über die Anzahl Nachbarn', 
          xlabel='Anzahl Nachbarn', 
          complementary=True)

plt.show()

"""
Explanation: Plot der (C)CDF
End of explanation
"""


print_heading('Höchste Anzahlen an Nachbarn')
print(sorted(neighbor_count)[-10:], end='\n\n')

border = 250
print_heading('Begrenzung zwischen %d' % border)
print('Knoten mit weniger als %d Nachbarn: %d' % (border, len([n for n in neighbor_count if n < border])))
print('Knoten mit mehr als %d Nachbarn: %d' % (border, len([n for n in neighbor_count if n >= border])))

# enthaelt das anzahl nachbarn jedes knoten des ungerichteten graphen
# bis zu einer maximalen anzahl von ``border``
clipped_neighbor_count = [n for n in neighbor_count if n < border]

f, axes = plt.subplots(ncols=2, nrows=1, figsize=(12, 3))
ax1, ax2 = axes.ravel()

def plot_log_cdf(values, ax, title, xlabel, complementary=False):
    """Plottet die gegebenen Werte als CDF auf einer logarithmischen
    x-Achse."""
    points = ecdf(values)

    x_min, x_max, y_min, y_max = ax.axis()
    ax.axis((x_min - 10, x_max + 10, y_min - .02, y_max + .02))

    ax.set_title(title)
    ax.set_xlabel(xlabel)
    ax.set_xscale('log')
    ax.set_xlim(1e0, 1e3)

    plot_ecdf(points, plotter=ax, line_color=None, complementary=complementary, title=title, xlabel=xlabel)

# CDF der Nachbarn
plot_log_cdf(clipped_neighbor_count, 
             ax1, 
             'CDF über die Anzahl Nachbarn', 
             'Anzahl Nachbarn')

# CCDF der Nachbarn
plot_log_cdf(clipped_neighbor_count, 
             ax2, 
             'CCDF über die Anzahl Nachbarn', 
             'Anzahl Nachbarn', 
             complementary=True)

plt.show()

"""
Explanation: Man kann im obigen Beispiel sehen, dass es nur wenige Knoten gibt, die mehr als ca. 250 Nachbarn besitzen. Daher ist die Grenze von 100% schnell erreicht und verfälscht den Bereich 0 < x < 250. Dieser soll näher betrachtet werden.
End of explanation
"""


def plot_log_log_cdf(values, ax, title, xlabel, complementary=False):
    
    plot_log_cdf(values, ax, title, xlabel, complementary=complementary)
    ax.set_yscale('log')
    ax.set_ylim(0, 1e0)

f, axes = plt.subplots(ncols=2, nrows=1, figsize=(12, 3))
ax1, ax2 = axes.ravel()

# CDF der Nachbarn
plot_log_log_cdf(clipped_neighbor_count, 
                 ax1, 
                 'CDF über die Anzahl Nachbarn', 
                 'Anzahl Nachbarn')

# CCDF der Nachbarn
plot_log_log_cdf(clipped_neighbor_count, 
                 ax2, 
                 'CCDF über die Anzahl Nachbarn', 
                 'Anzahl Nachbarn', 
                 complementary=True)

plt.show()

"""
Explanation: Hier kann man sehen, dass noch rund 80% aller Knoten weniger als 70 Nachbarn besitzen. Das plotten in einem doppelt logarithmischen Maßstab macht an dieser Stelle keinen Sinn.
End of explanation
"""


def plot_multi_ecdf(values, legend, title='', xlabel=''):
    """Plottet alle in ``values`` gegebenen Arrays in ein CDF-Diagram.
    Es muss eine Legende gegeben sein, die alle Label-Elemente beinhaltet, die
    fuer ein einzelnes Array gelten.
    """
    for i in range(len(values)):
        arr = values[i]
        points = ecdf(arr)
        plot_ecdf(points, label=legend[i], point_color=None, line_color=None)
        
    plt.title(title)
    plt.xlabel(xlabel)

# alle daten, die fuer die berechnung der einzelnen
# cdfs benoetigt werden
data = {
    'root_id': 42,
    'counts': (800, 1600),
    'crawler': {
        'BFS': {
            'func': crawl_bfs_iter
        },
        'DFS': {
            'func': crawl_dfs_iter
        }
    }
}

# ermittlung beider baeume
dfs_tree = nx.dfs_tree(graph, data['root_id'])
bfs_tree = nx.dfs_tree(graph, data['root_id'])

# die baeume werden ueber ihre kanten geprueft
data['crawler']['BFS']['edges'] = bfs_tree.edges()
data['crawler']['DFS']['edges'] = dfs_tree.edges()

# enthaelt alle nachbarwerte mit einem label, das in der
# legende ausgegeben wird, Bsp.: 'BFS 800'
neighbors = []

# fuer jede anzahl
for count in data['counts']:
    
    # und jeden algorithmus
    for _id in data['crawler'].keys():
        crawler = data['crawler'][_id]
        crawler[str(count)] = []
        
        # markiere den beginn des crawlings
        print('crawle {:s} mit {:5d} besuchen'.format(_id, count), end=' ')
        
        # equivalent zu z.B. 
        # for node in crawl_bfs_iter(bfs_tree.edges(), 42, max_visits=800):
        #     crawler['800'].append(len(nx.neighbors(graph, node)))
        # len(nx.neighbors(graph, node)) = Anzahl Nachbarn eines Knoten
        # Hier werden die Nachbarn eines Knotens des ungerichteten Graphen gezaehlt!
        for node in crawler['func'](crawler['edges'], data['root_id'], max_visits=count):
            crawler[str(count)].append(len(nx.neighbors(graph, node)))
        print(' ..fertig')  
        
        # hinzufuegen der anzahlen an nachbarn mit entsprechendem label
        # hier wird die grenze wieder verwendet
        neighbors.append({
            'values': [el for el in crawler[str(count)] if el < border],
            'label': '%s %d' % (_id, count)})

print('crawle den gesamten graph', end=' ')
# berechnung der anzahl an nachbarn fuer den gesamten ungerichteten graph
snapshot = [len(nx.neighbors(graph, node)) 
            for node in crawl_bfs_iter(bfs_tree.edges(),
                                       data['root_id'], 
                                       max_visits=len(graph.nodes()))]

neighbors.append({
    'values': [el for el in snapshot if el < border],
    'label': 'BFS unbegrenzt'
})
print(' ..fertig')

plot_multi_ecdf([n['values'] for n in neighbors], 
                title='CDF der Nachbarverteilung', 
                xlabel='Anzahl Nachbarn',
                legend=[n['label'] for n in neighbors])

plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
plt.show()

"""
Explanation: Der folgende Code ist definitiv verbesserungswürdig. Es sollen die einzelnen Anzahlen an Nachbarn, über Breiten- und Tiefensuche mit einer maximalen Anzahl von 800 und 1600 und des gesamte Graphs ermittelt werden. Danach erfolgt eine Darstellung der CDFs nebeneinander.
Vergleich der Knotengrade der einzelnen Algorithmen
End of explanation
"""


import random

def random_walk(graph, root, max_visits=10):
    """Generator der einen Graph anhand seiner Kanten mit Hilfe von
    random walk in iterativer Variante crawlt. Die Id des
    besuchten Knoten wird dabei geliefert.
    
    :param graph: Graph ueber den der random walk ausgefuehrt werden soll
    :param root: Id des Ausgangsknotens
    :param max_visits: Anzahl der maximal zu besuchenden Knoten
    """
    visited = 0
    S = set()
    
    # die queue enthaelt im gegensatz zu den anderen implementierungen
    # den pfad, der im random walk gelaufen wurde
    Q = []
    Q.append(root)
    while Q and visited < max_visits:
        
        node = Q[-1]
        # print('{:>10s}: {:d}'.format('yield', node))
        yield node
        visited += 1
        if node not in S and visited < max_visits:
            S.add(node)
            
            # nachbarn die noch nicht besucht wurden
            neighbors = [n for n in nx.neighbors(graph, node) if n not in S]
            
            # sollten keine nachbarn vorhanden sein muessen die vorigen
            # knoten abgefragt werden (up[-1] ist der aktuelle knoten)
            up = -2
            
            # solange alle nachbarn des gewaehlten knotens besucht wurden
            # wird der knoten von der queue entfernt und neue nachbarn
            # gesucht
            while not neighbors:
                node = Q[up]
                neighbors = [n for n in nx.neighbors(graph, node) if n not in S]
                up -= 1
            
            # ansonsten waehle einen zufaelligen nachbar aus
            # und schiebe ihn auf die queue
            neighbor = random.choice(neighbors)
            Q.append(neighbor)
                

node_count = (100, 200, 400, 800, 1600)

data = []
for c in node_count:
    
    # ermittlung der anzahl an nachbarn fuer jeden dieser knoten
    count = [len(nx.neighbors(graph, node)) for node in random_walk(graph, 42, c)]
    data.append({
        'label': c,
        'neighbor_count': [i for i in count if i < border]
    })
    
plot_multi_ecdf([n['neighbor_count'] for n in data], 
                title='CDF der Nachbarverteilung mit Random Walk',
                xlabel='Anzahl Nachbarn',
                legend=[n['label'] for n in data])

plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
plt.show()

"""
Explanation: 7.1.2 Random Walk
Hier wird der Graph nicht mehr anhand seiner Struktur durchlaufen, sondern es werden zufällig Knoten ausgewählt und deren Nachbarn untersucht.
End of explanation
"""


numbers = [1, 10, 50, 100, 200, 500]

for i in range(5):
    print_heading('Test #%d' % (i + 1))
    for number in numbers:
        g = nx.MultiGraph()
        g.add_nodes_from(graph.nodes())
        g.add_edges_from(graph.edges())

        for _ in range(number + 1):
            node = random.choice(g.nodes())
            g.remove_node(node)

        print('{:3d} entfernt => {:2d} Komponenten'.format(number, nx.number_connected_components(g)))

import random

numbers = [1, 10, 50, 100, 200]
component_counts = {}
for n in numbers:
    component_counts[n] = []

print('arbeite', end='')
runs, steps, step = 50, 5, 0
for i in range(runs):
        
    for number in numbers:
        H = graph.copy()

        for _ in range(number + 1):
            node = random.choice(H.nodes())
            H.remove_node(node)
        component_counts[number].append(nx.number_connected_components(H))
        
    step += 1
    
    if step % steps == 0:
        print('..%d%%' % (step / runs * 100), end='')

print_heading('\nDurchschnittliche Anzahl an Komponenten')
for number in sorted(component_counts.keys()):
    print('# {:<3d} entfernt => {:8,.2f}'.format(number, np.average(component_counts[number])))

"""
Explanation: 7.2 Angriffe auf unstrukturierte Overlays
End of explanation
"""


G = nx.Graph()
G.add_nodes_from([i for i in range(1, 13)])
G.add_edges_from([
    (1, 2),
    (1, 3),
    (3, 4),
    (3, 8),
    (3, 11),
    (4, 5),
    (4, 6),
    (4, 7),
    (4, 8),
    (6, 11),
    (7, 8),
    (7, 11),
    (7, 10),
    (8, 9),
    (9, 10),
    (9, 12),
])

# positions for all nodes
pos = nx.spring_layout(G)

nx.draw_networkx_nodes(G, pos, node_size=500, alpha=0.8)
nx.draw_networkx_edges(G, pos, width=1.0, alpha=0.5)
nx.draw_networkx_labels(G, pos)

plt.show()

"""
Explanation: 7.3 Graphen-Metriken
End of explanation
"""


# Cluster coefficient fuer einzelne Knoten
nx.clustering(G)

"""
Explanation: 7.3.1 Globaler Cluster Koeffizient
Siehe NetworkX API Doc
Wenn man den Clustering Koeffizienten eines einzelnen Knotens per Hand ausrechnen möchte benötigt man die Anzahl an Nachbarn des Knoten (Knotengrad) und die Anzahl der Verbindungen unter diesen Nachbarn $N_v$.
$CC(v)$:
$v$: Knoten
$K_v$: Knotengrad
$N_v$: Anzahl Verbindungen unter den Knoten von $v$
$CC(v) = \dfrac{2 N_v}{K_v(K_v - 1)}$
End of explanation
"""


# Cluster coefficient fuer den Graph
nx.average_clustering(G)

"""
Explanation: Beispiel für den Knoten 3.
4 Nachbarn: [1, 4, 8, 11]
1 Verbindung: [(4, 8)]
=> $\dfrac{2 * 1}{4 * 3} = \dfrac{2}{12} = \dfrac{1}{6} = 0.166$
Der globale Clustering Koeffizient ist lediglich der Durchschnitt aller lokalen Clustering Koeffizienten.
End of explanation
"""


nx.betweenness_centrality(G, normalized=False)

"""
Explanation: 7.3.2 Betweenness Centrality
Siehe NetworkX API Doc
Zur Berechnung der Betweenness Centrality eines einzelnen Knotens $v$, müssen zunächst alle kürzesten Pfade gefunden werden, die durch diesen Knoten $v$ verlaufen. 

Man bildet die Paare der kürzesten Pfade. 
Für jedes Paar $(s, t)$ werden die Anzahlen der kürzesten Pfade $\sigma_{(s, t)}$ zueinander gezählt. 
Davon werden die Anzahl der kürzesten Pfade, die durch den gewählten Knoten verlaufen $\sigma_{(s, t|v)}$ geteilt durch die Anzahl der kürzestens Pfade zwischen den Knoten = $betweenness_i$.

Den Ablauf 2. und 3. nimmt man für jedes in 1. ermittelte Paar vor. Die Summe aus den einzelnen Ergebnissen aus 3. bildet die Betweenness Centrality des Knotens $betweenness = \sum_{i = 0}^{n} betweenness_i$, wobei $n$ die Anzahl der Paare ist.
Siehe auch:

8 -7 Betweenness centrality Part I
8 - 8 Betweenness centrality Part II
End of explanation
"""


from collections import OrderedDict

def print_shortest_paths(paths):
    for start, end in paths:
        print('%d -- %d:' % (start, end))
        for path in paths[(start, end)]:
            print('  %s' % path)

paths = OrderedDict()

for start in G.nodes():
    for end in G.nodes():
        
        # der Graph ist bidirektional, daher muss nur in
        # eine Richtung geschaut werden (1 -> 4, 4 -> 1 unnoetig)
        if start < end:
            
            # Bilden eines Knotenpaares
            pair = (start, end)
            if pair not in paths:
                paths[pair] = []
            
            # hinzufuegen aller kuerzesten pfade zwischen start und end
            for path in nx.all_shortest_paths(G, start, end):
                paths[pair].append(path)

# ausgabe aller kuerzesten pfade im graph
print_shortest_paths(paths)

"""
Explanation: Im folgenden werden alle kürzesten Pfade gesammelt.
End of explanation
"""


def betweenness_relevants(paths, target):
    """Liefert die Paare inklusive Pfade die relevant 
    fuer die Berechnung der betweenness centrality sind.
    
    :param paths: dict and 2-Tupeln die Start und Ziel 
        bilden inklusive der Liste an kuerzesten Pfaden
    :param target: Objekt dessen betweenness centrality
        berechnet werden soll
    :return: gefilterte menge an pfaden
    """
    target_paths = paths.copy()
    for pair in paths:
        is_in = False
        targets = [p[1:len(p) - 1] for p in paths[pair]]
        for t in targets:
            if target in t:
                is_in = True
        if not is_in:
            del target_paths[pair]
    return target_paths

target = 7
targets = betweenness_relevants(paths, target)
print_shortest_paths(targets)

"""
Explanation: Beispiel für Knoten 7
Kürzeste Pfade durch den Knoten:
End of explanation
"""


def calc_betweenness_i(paths, target):
    """Berechnet die einzelnen Summanden zur Ermittlung
    der Betweenness centrality eines Knotens.
    
    :param paths: gefilterte Menge an Pfaden, die relevant
        sind zur Berechnung der Betweenness centrality
    """
    betweenness_i = []
    for pair in paths:
        denominator = len(paths[pair])
        nominator = sum([1 for p in paths[pair] if target in p])
        betweenness_i.append(nominator / denominator)
    return betweenness_i

betweenness_i = calc_betweenness_i(targets, target)
print(' + '.join(['{:.2f}'.format(i) for i in betweenness_i]))
print_heading('Betweenness centrality = {:.2f}'.format(sum(betweenness_i)))

"""
Explanation: Ermittlung der einzelnen Summanden zur Betweenness centrality
End of explanation
"""


target = 8
targets = betweenness_relevants(paths, target)
print_shortest_paths(targets)

betweenness_i = calc_betweenness_i(targets, target)
print(' + '.join(['{:.2f}'.format(i) for i in betweenness_i]))
print_heading('Betweenness centrality = {:.2f}'.format(sum(betweenness_i)))

"""
Explanation: Beispiel für Knoten 8
Kürzeste Pfade durch den Knoten:
End of explanation
"""


target = 6
targets = betweenness_relevants(paths, target)
print_shortest_paths(targets)

betweenness_i = calc_betweenness_i(targets, target)
print(' + '.join(['{:.2f}'.format(i) for i in betweenness_i]))
print_heading('Betweenness centrality = {:.2f}'.format(sum(betweenness_i)))

"""
Explanation: Beispiel für Knoten 6
Kürzeste Pfade durch den Knoten:
End of explanation
"""


