import numpy as np
from graph_tools import DiGraph
g0 = DiGraph([[0, 1], [1, 0]])
g0.period
2
g1 = DiGraph([[1, 0], [0, 1]])
g1.period
--------------------------------------------------------------------------- NotImplementedError Traceback (most recent call last) <ipython-input-5-fcb438375d72> in <module>() ----> 1 g1.period /Users/oyama/Dropbox/Development/graph_tools/graph_tools.pyc in period(self) 234 def period(self): 235 if self._period is None: --> 236 self._compute_period() 237 return self._period 238 /Users/oyama/Dropbox/Development/graph_tools/graph_tools.pyc in _compute_period(self) 195 if not self.is_strongly_connected: 196 raise NotImplementedError( --> 197 'Not defined for a non strongly-connected digraph' 198 ) 199 NotImplementedError: Not defined for a non strongly-connected digraph
g1.is_strongly_connected
False
g1.strongly_connected_components
[array([0]), array([1])]
g1.sink_strongly_connected_components
[array([0]), array([1])]
A = np.zeros((11, 11))
A[0, [1, 5]] = 1
A[1, [2, 10]] = 1
A[2, 7] = 1
A[3, 4] = 1
A[4, 5] = 1
A[5, [2, 6]] = 1
A[6, [7, 8]] = 1
A[7, 4] = 1
A[8, 0] = 1
A[9, 4] = 1
A[10, [3, 8, 9]] = 1
A
array([[ 0., 1., 0., 0., 0., 1., 0., 0., 0., 0., 0.], [ 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 1.], [ 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0.], [ 0., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0.], [ 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.], [ 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 0.], [ 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0.], [ 0., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0.], [ 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.], [ 0., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0.], [ 0., 0., 0., 1., 0., 0., 0., 0., 1., 1., 0.]])
g2 = DiGraph(A)
g2.period
4
cyclic_components = g2.cyclic_components
print cyclic_components
[array([0, 4]), array([1, 5]), array([ 2, 6, 10]), array([3, 7, 8, 9])]
permutation = [i for cyclic_component in cyclic_components for i in cyclic_component]
print permutation
[0, 4, 1, 5, 2, 6, 10, 3, 7, 8, 9]
g2._cyclic_components_proj
array([0, 1, 2, 3, 0, 1, 2, 3, 3, 3, 2])
g2._cyclic_components_proj.argsort()
array([ 0, 4, 1, 5, 2, 6, 10, 3, 7, 8, 9])
# Cyclic normal form of A
A[permutation, :][:, permutation]
array([[ 0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 0.], [ 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0.], [ 0., 0., 0., 0., 1., 0., 1., 0., 0., 0., 0.], [ 0., 0., 0., 0., 1., 1., 0., 0., 0., 0., 0.], [ 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0.], [ 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0.], [ 0., 0., 0., 0., 0., 0., 0., 1., 0., 1., 1.], [ 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0.], [ 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0.], [ 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.], [ 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0.]])
# Make A be a stochastic matrix
B = A[permutation, :][:, permutation]
B /= np.sum(B, axis=1, keepdims=True)
np.set_printoptions(precision=2)
print B
[[ 0. 0. 0.5 0.5 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0. 0.5 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.5 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 0.5 0.5 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0.33 0. 0.33 0.33] [ 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. ]]
print np.linalg.matrix_power(B, 5)
[[ 0. 0. 0.1 0.9 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0.12 0.88 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.46 0.04 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.44 0.06 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 0.75 0.25 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0.04 0.69 0.23 0.04] [ 0. 0. 0. 0. 0. 0. 0. 0.03 0.71 0.24 0.03] [ 0.25 0.75 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0.25 0.75 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0.21 0.79 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0.25 0.75 0. 0. 0. 0. 0. 0. 0. 0. 0. ]]
C = np.linalg.matrix_power(B, 8)
for k in range(5):
C = C.dot(B)
print 'B^{0} ='.format(9 + k)
print C, '\n'
B^9 = [[ 0. 0. 0.12 0.88 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0.12 0.88 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.44 0.06 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.44 0.06 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0.02 0.72 0.24 0.02] [ 0. 0. 0. 0. 0. 0. 0. 0.02 0.72 0.24 0.02] [ 0. 0. 0. 0. 0. 0. 0. 0.02 0.72 0.24 0.02] [ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ]] B^10 = [[ 0. 0. 0. 0. 0.5 0.44 0.06 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.44 0.06 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0.02 0.72 0.24 0.02] [ 0. 0. 0. 0. 0. 0. 0. 0.02 0.72 0.24 0.02] [ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0.12 0.88 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0.12 0.88 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0.12 0.88 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0.12 0.88 0. 0. 0. 0. 0. 0. 0. ]] B^11 = [[ 0. 0. 0. 0. 0. 0. 0. 0.02 0.72 0.24 0.02] [ 0. 0. 0. 0. 0. 0. 0. 0.02 0.72 0.24 0.02] [ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0.12 0.88 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0.12 0.88 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0.12 0.88 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.44 0.06 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.44 0.06 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.44 0.06 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.44 0.06 0. 0. 0. 0. ]] B^12 = [[ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0.12 0.88 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0.12 0.88 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.44 0.06 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.44 0.06 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.44 0.06 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0.02 0.72 0.24 0.02] [ 0. 0. 0. 0. 0. 0. 0. 0.02 0.72 0.24 0.02] [ 0. 0. 0. 0. 0. 0. 0. 0.02 0.72 0.24 0.02] [ 0. 0. 0. 0. 0. 0. 0. 0.02 0.72 0.24 0.02]] B^13 = [[ 0. 0. 0.12 0.88 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0.12 0.88 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.44 0.06 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.44 0.06 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0.02 0.72 0.24 0.02] [ 0. 0. 0. 0. 0. 0. 0. 0.02 0.72 0.24 0.02] [ 0. 0. 0. 0. 0. 0. 0. 0.02 0.72 0.24 0.02] [ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0.24 0.76 0. 0. 0. 0. 0. 0. 0. 0. 0. ]]
g3 = DiGraph(B)
g3.csgraph
<11x11 sparse matrix of type '<type 'numpy.bool_'>' with 17 stored elements in Compressed Sparse Row format>
print g3.csgraph.todense()
[[False False True True False False False False False False False] [False False False True False False False False False False False] [False False False False True False True False False False False] [False False False False True True False False False False False] [False False False False False False False False True False False] [False False False False False False False False True True False] [False False False False False False False True False True True] [False True False False False False False False False False False] [False True False False False False False False False False False] [ True False False False False False False False False False False] [False True False False False False False False False False False]]
g4 = DiGraph(B, weighted=True)
g4.csgraph
<11x11 sparse matrix of type '<type 'numpy.float64'>' with 17 stored elements in Compressed Sparse Row format>
print g4.csgraph.todense()
[[ 0. 0. 0.5 0.5 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0. 0.5 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0.5 0.5 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0. 0.5 0.5 0. ] [ 0. 0. 0. 0. 0. 0. 0. 0.33 0. 0.33 0.33] [ 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. ] [ 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. ]]