from graphviz import Graph
G = Graph(format='png', filename='Steiner_Tree')
G.body.extend(['layout=neato'])
#G.node_attr.update(color='lightblue2', style='filled')


nodes_v = ['v1', 'v2', 'v3', 'v4', 'v5']
nodes_u = ['u1', 'u2']
# Add nodes to the graph
for no in nodes_v+nodes_u:
    
    G.node(no, shape='circle',fontname='Times-Italic',
            xlabel=no, label='', width='0.2')
    
for no in nodes_v:
    G.node(no, style='filled', color='black')

edges=[('v1','u1',2),
       ('v2','u1',2),
       ('v3','u2',4),
       ('v4','u2',3),
       ('v5','u2',5),
       ('u1','u2',1)]
# Add edges to the graph
for ed in edges:
    G.edge(ed[0],ed[1],label=str(ed[2]))

G

"""
Explanation: Question I
End of explanation
"""


import numpy as np
ten_points = np.matrix([[1,1,0,0,0,0,0,1,1,1],
                        [1,1,1,0,0,0,1,1,1,1],
                        [0,1,1,1,1,1,1,1,0,0],
                        [0,0,1,1,1,1,1,0,0,0],
                        [0,0,1,1,1,1,1,0,0,0],
                        [0,0,1,1,1,1,1,0,0,0],
                        [0,1,1,1,1,1,1,1,0,0],
                        [1,1,1,0,0,0,1,1,1,1],
                        [1,1,0,0,0,0,0,1,1,1],
                        [1,1,0,0,0,0,0,1,1,1]])

def markov_cluster(ad_matrix, power, inflation, verbose=False):
    np.fill_diagonal(ad_matrix, 1)
    #Initialize variable
    old_ad_matrix = np.matrix([[2]])
    verbose_output = [ad_matrix]
    while not((ad_matrix == old_ad_matrix).all()):
        old_ad_matrix = ad_matrix
        # Take matrix to the power of "power"
        ad_matrix = np.linalg.matrix_power(ad_matrix, power)
        # Inflation step
        for cell in np.nditer(ad_matrix, op_flags = ['readwrite']):
            cell[...] = cell ** inflation
        # Normalization
        ad_matrix = ad_matrix/np.sum(ad_matrix, axis = 0)
        verbose_output.append(ad_matrix)
        
    if verbose:
        return verbose_output
    else:
        return ad_matrix

markov_cluster(ten_points, 2,2, True)[:3]

"""
Explanation: Question II
(a) Implement the Markov Clustering Algorithm
End of explanation
"""


from graphviz import Graph
G = Graph(format='png', filename='Graph')
G.body.extend(['layout=neato'])
#G.node_attr.update(color='lightblue2', style='filled')


nodes_v = ['v1', 'v2', 'v3', 'v4', 'v5']
nodes_u = ['u1', 'u2', 'u3', 'u4']
# Add nodes to the graph
for no in nodes_v+nodes_u:
    G.node(no, shape='circle',fontname='Times-Italic',
            xlabel=no, label='', width='0.2')
    
for no in nodes_v:
    G.node(no, style='filled', color='black')

edges=[('v1','v2',8), ('v1','v3',9), ('v1','u3',2), ('v1','u1',2),
       ('v2','v5',5), ('v2','u1',2), ('v2','u4',8),
       ('v3','v4',8), ('v3','u2',4),('v3','u3',8),
       ('v4','u2',3),
       ('v5','u2',5), ('v5','u4',8),
       ('u1','u2',1)]
# Add edges to the graph
for ed in edges:
    G.edge(ed[0],ed[1],label=str(ed[2]))

G

"""
Explanation: (b) Graph visualisation
End of explanation
"""


x = markov_cluster(ten_points,2,2)


import networkx as nx
import matplotlib.pyplot as plt

g = nx.from_numpy_matrix(x)
nx.draw_networkx(g)
plt.show()

"""
Explanation: (c) Calculate the final clustering for the ten points
End of explanation
"""


import networkx as nx
import matplotlib.pyplot as plt

G = nx.barabasi_albert_graph(100,2)

nx.draw(G, node_size=40)
plt.show()

from networkx.algorithms import (closeness_centrality,
                                 betweenness_centrality,
                                 google_matrix)

#Computation of closeness, betweennes and page_rank
closeness = closeness_centrality(G)
betweenness = betweenness_centrality(G)
page_rank = google_matrix(G)

x = range(100)

%matplotlib inline
import matplotlib.pyplot as plt
plt.style.use('seaborn-ticks')
#plt.plot(x,sorted_closeness, label='closeness')
#plt.plot(x, sorted_betweenness, 'o', label='betweenness')
plt.plot(x, list(closeness.values()), 'o', label='closeness')
plt.plot(x, list(betweenness.values()), 'o', label='betweenness')
#plt.bar(x, list(closeness.values()), label='closeness')
#plt.bar(x, list(betweenness.values()), label='betweenness', color='r')
plt.legend(loc=1)


"""
Explanation: Question III
(a) Generate 100 vertices of a graph using the Barbasi-Albert Model
End of explanation
"""


G2 = nx.barabasi_albert_graph(10000,2)

from collections import Counter
counts = Counter(G2.degree().values())
x,y = zip(*sorted(counts.items()))
y= [e/10000 for e in y]
plt.style.use('seaborn-ticks')
plt.loglog(x,y,'o')
plt.xlabel('Degree')
plt.ylabel('Fraction of Nodes')

"""
Explanation: (b) Generate 10000 vertices of a scale free network. Show that it follows Power Law and Small World property.
End of explanation
"""


from networkx.algorithms.distance_measures import diameter
import math
print('Diameter:\t{}'.format(diameter(G2)))
print('Ln(|V|):\t{}'.format(math.log(10000, math.e)))

"""
Explanation: The node degree distribution follows a power law.
End of explanation
"""


