# coding: utf-8

# # Matrices for graph traversal

# In[1]:

import numpy as np


# In[2]:


n = 5

# Make a sparsely populated random matrix
A = np.zeros((n, n))

from random import randrange, uniform
for i in range(n*n//2):
    i, j = randrange(n), randrange(n)
    w = round(uniform(0, 1), 1)
    A[i, j] = w
    
A


# For a reason that will become clear in a minute, we need the columns of $A$ to be normalized to sum to 1:

# In[3]:

A_cols = np.sum(A, axis=0)
A_cols[A_cols == 0] = 1
A = A/A_cols

print(A)
print(np.sum(A, axis=0))


# This short piece of code exports the matrix in a format that's readable to the [dot](http://graphviz.org) graph drawing tool.

# In[4]:

def to_dot(A, vec=None):
    lines = ['digraph mygraph { size="2,2";']
    for i in range(n):
        for j in range(n):
            if A[i, j]:
                lines.append("%d -> %d [label=\"%0.1f\"];" % (j, i, A[i, j]))
    if vec is not None:
        for i, vec_i in enumerate(vec):
            assert 0<=vec_i<=1
            lines.append(
                '%d [style="filled", fillcolor="#ff%02xff"];'
                % (i, int(255*(1-vec_i))))
    lines.append("}")
    return "\n".join(lines)


# See?

# In[5]:

print(to_dot(A))


# In[6]:

get_ipython().magic(u'load_ext gvmagic')


# In[7]:

get_ipython().magic(u'dotstr to_dot(A)')


# Another thing we can do is plot distributions on the graph:

# In[9]:

d = np.zeros((n,))
d[0] = 1
get_ipython().magic(u'dotstr to_dot(A, d)')


# In[10]:

d


# Now, how would we model the spread of this distribution across the graph?

# In[73]:

d = A.dot(d)
print(d)
get_ipython().magic(u'dotstr to_dot(A, d)')


# In[47]:

d


# More questions:
# 
# * How would you find the steady state of this traversal?
# * Any predictions about `np.sum(d)`?