import numpy as np
import networkx as nx
from matplotlib import pyplot as plt
%matplotlib inline
import warnings
warnings.filterwarnings( 'ignore' )

def fw( A, pi = None ) :
    if pi is None :
        pi = A.copy( )
        pi[ A == 0 ] = np.inf
        np.fill_diagonal( pi, 0 )
    for k in xrange( A.shape[ 0 ] ) : 
        pi = np.minimum( pi, pi[ :, k ] + pi[ k, : ] )
    return pi

"""
Explanation: <center>Structural Analysis and Visualization of Networks</center>
<center>Final Mid-term Assignment</center>
<center>Student: Nazarov Ivan</center>
<hr/>
End of explanation
"""


G = nx.gml.read_gml( './data/ha5/huge_100004196072232_2015_03_21_22_33_65c744356ffedcfa83bf49b64a76445a.gml' )

fig = plt.figure( figsize = (16,12) )
axs = fig.add_subplot( 1,1,1, axisbg = 'black' )
nx.draw( G, pos = nx.spring_layout( G ), ax = axs, node)

nx.is_connected(G)

nx.to_numpy_matrix( G )

A = nx.to_numpy_matrix( G )

def spectral( A, T = 10, _index = None ) :
    if _index is None :
        _index = np.arange( A.shape[ 0 ], dtype = np.int )
## Get the vertex degrees
    deg = A.sum( axis = 1, dtype = np.float ).getA1( )
## Check for isolated vertices
    if np.any( deg == 0 ) :
## Find nonisolated
        nz = np.where( deg != 0 )[ 0 ]
        return np.concatenate( ( np.where( deg == 0 )[ 0 ],
            nz[ spectral( A[:,nz][nz,:], T = T, _index = _index[ nz ] ) ] ) )
## Assume the matrix A has no isolated vertices
    D = np.diag( 1.0 / deg )
    L = np.eye( *A.shape, dtype = np.float ) - D.dot( A )
    l, v = np.linalg.eig( L )
    e = v[ :, np.argsort( l )[ 1 ] ].real.getA1()
    n, p = np.where( e < 0 )[ 0 ], np.where( e >= 0 )[ 0 ]
    if len( p ) > T :
        p = p[ spectral( A[:,p][p,:], T = T, _index = _index[ p ] ) ]
    if len( n ) > T :
        n = n[ spectral( A[:,n][n,:], T = T, _index = _index[ n ] ) ]
    if len( p ) > len( n ) :
        p, n = n, p
    return np.concatenate( ( n, p ) )

pi = fw( A )
I = nx.spectral_ordering( G )
J = spectral( A )
plt.subplot( 121 )
plt.imshow( pi[:,I][I,:] )
plt.subplot( 122 )
plt.imshow( pi[:,J][J,:] )

nx.spectral_ordering()

plt.plot(e[n])
plt.plot(e[p], '-r')

i = np.argsort( l )[ :10 ]
# print v[ :, i ].real
print l[ i ]

np.isclose( l[ i ], 0 )

"""
Explanation: <hr/>
End of explanation
"""


def assortativity( G, X ) :
## represent the graph in an adjacency matrix form
    A = nx.to_numpy_matrix( G, dtype = np.float, nodelist = G.nodes( ) )
## Convert x -- dictionary to a numpy vector
    x = np.array( [ X[ n ] for n in G.nodes( ) ] , dtype = np.float )
## Compute the x'Ax part
    xAx = np.dot( x, np.array( A.dot( x ) ).flatten( ) )
##  and the x'\text{diag}(D)x part. Note that left-multiplying a vector
##  by a diagonal matrix is equivalent to element-wise multiplication.
    D = np.array( A.sum( axis = 1 ), dtype = np.float ).flatten( )
    xDx = np.dot( x, np.multiply( D, x ) )
## numpy.average( ) actually normalizes the weights.
    x_bar = np.average( x, weights = D )
    D_sum = np.sum( D, dtype = np.float )
    return ( xAx - D_sum * x_bar * x_bar ) / ( xDx - D_sum * x_bar * x_bar )

"""
Explanation: The mixing coefficient for a numerical node attribute $X = \big(x_i\big)$ in an undirected graph $G$, with the adjacency matrix $A$, is defined as
$$\rho(x) = \frac{\text{cov}}{\text{var}} = \frac{\sum_{ij}A_{ij}(x_i-\bar{x})(x_j-\bar{x})}{\sum_{ij}A_{ij}(x_i-\bar{x})^2} $$
where $\bar{x} = \frac{1}{2m}\sum_i \delta_i x_i$ is the mean value of $X$ weighted by vertex degree. Note that $A$ is necessarily symmetric. This coefficient can be represented in the matrix notation as  
$$\rho(x) = \frac{X'AX - 2m \bar{x}^2}{X'\text{diag}(D)X - 2m \bar{x}^2} $$
where the diagonal matrix $\text{diag}(D)$ is the matrix of vertex degrees, and the value $\bar{x}$ is the sample mean of the numerical node attribute $X$.
End of explanation
"""


