%matplotlib inline
import numpy as np
import networkx as nx
import seaborn as sns
sns.set_style('ticks')
sns.set_context('poster')

"""
Explanation: This is the common problem set for Homework 1 from the spring quarter Network Theory class at UC Davis taught by Prof. Raissa D'Souza. The original assignment is at http://mae.engr.ucdavis.edu/dsouza/Classes/253-S16/hw1.pdf. Source code for this notebook is on github at https://github.com/camillescott/ucd-ecs253.
End of explanation
"""


A_directed = np.array( [[0, 1, 0, 0, 1],
                        [0, 0, 1, 0, 0],
                        [1, 0, 0, 1, 1],
                        [0, 1, 1, 0, 0],
                        [0, 0, 0, 0, 0]] )
print(A_directed)

"""
Explanation: Adjacency Matrices
The Matrix
End of explanation
"""


nx.draw_networkx(nx.DiGraph(data=A_directed.T), 
                 labels=dict(zip(range(len(A_directed)), range(1, len(A_directed)+1))),
                 node_size=600, 
                 node_color=sns.xkcd_rgb["pale orange"])

"""
Explanation: A little visualization, just to double check.
End of explanation
"""


def calc_steady_state(A, i=100):
    M = A / A.sum(axis=0)
    M = np.linalg.matrix_power(M, i)
    return M

def print_probs(probs):
    print('\n'.join('Node {0}: {1:.4f}'.format(node, p) for node, p in \
                zip(range(1, len(probs)+1), probs)))

"""
Explanation: Steady-State Probability of Random Walker
We can calculate the steady state probabilities quite simply by dividing out the column sums of the adjacency matrix $A$ to convert it into a state transition matrix $M$ and then computing the matrix power $M^i$. With $i$ as a reasonably high number, the result will converge to the steady state probabilities.
End of explanation
"""


probs = calc_steady_state(A_directed)[:,0]
print_probs(probs)

"""
Explanation: The resulting probabilities:
End of explanation
"""


A_undirected = np.array( [[0, 1, 1, 0, 1],
                          [1, 0, 1, 1, 0],
                          [1, 1, 0, 1, 1],
                          [0, 1, 1, 0, 0],
                          [1, 0, 1, 0, 0]] )
print(A_undirected)

probs = calc_steady_state(A_undirected)[:,0]
print_probs(probs)

"""
Explanation: Steady-State Probabilities for Undirected Graph
For the undirected variant, we just mirror across the diagonal.
End of explanation
"""


