<s> from apgl . util import * <EOL> from apgl . graph . VertexList import VertexList <EOL> from apgl . graph . GeneralVertexList import GeneralVertexList <EOL> from apgl . graph . SparseGraph import SparseGraph <EOL> from apgl . graph . DenseGraph import DenseGraph <EOL> from apgl . graph . GraphUtils import GraphUtils <EOL> from apgl . generator . BarabasiAlbertGenerator import BarabasiAlbertGenerator <EOL> import unittest <EOL> import numpy <EOL> import scipy . sparse <EOL> import numpy . testing as nptst <EOL> class AbstractMatrixGraphTest ( unittest . TestCase ) : <EOL> def setUp ( self ) : <EOL> pass <EOL> def testTreeDepth ( self ) : <EOL> numVertices = <NUM_LIT:4> <EOL> numFeatures = <NUM_LIT:1> <EOL> vList = VertexList ( numVertices , numFeatures ) <EOL> graph = SparseGraph ( vList , False ) <EOL> graph . addEdge ( <NUM_LIT:0> , <NUM_LIT:1> ) <EOL> graph . addEdge ( <NUM_LIT:0> , <NUM_LIT:2> ) <EOL> graph . addEdge ( <NUM_LIT:2> , <NUM_LIT:3> ) <EOL> self . assertEquals ( GraphUtils . treeDepth ( graph ) , <NUM_LIT:2> ) <EOL> numVertices = <NUM_LIT:5> <EOL> vList = VertexList ( numVertices , numFeatures ) <EOL> graph = SparseGraph ( vList , False ) <EOL> graph . addEdge ( <NUM_LIT:0> , <NUM_LIT:1> ) <EOL> graph . addEdge ( <NUM_LIT:0> , <NUM_LIT:2> ) <EOL> graph . addEdge ( <NUM_LIT:2> , <NUM_LIT:3> ) <EOL> graph . addEdge ( <NUM_LIT:3> , <NUM_LIT:4> ) <EOL> self . assertEquals ( GraphUtils . treeDepth ( graph ) , <NUM_LIT:3> ) <EOL> def testVertexLabelPairs ( self ) : <EOL> numVertices = <NUM_LIT:6> <EOL> numFeatures = <NUM_LIT:1> <EOL> vList = VertexList ( numVertices , numFeatures ) <EOL> vList . setVertices ( numpy . array ( [ numpy . arange ( <NUM_LIT:0> , <NUM_LIT:6> ) ] ) . T ) <EOL> graph = DenseGraph ( vList , True ) <EOL> graph . addEdge ( <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:0.1> ) <EOL> graph . addEdge ( <NUM_LIT:1> , <NUM_LIT:3> , <NUM_LIT:0.1> ) <EOL> graph . addEdge ( <NUM_LIT:0> , <NUM_LIT:2> , <NUM_LIT> ) <EOL> graph . addEdge ( <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT:0.5> ) <EOL> graph . addEdge ( <NUM_LIT:0> , <NUM_LIT:4> , <NUM_LIT:0.1> ) <EOL> graph . addEdge ( <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT:0.1> ) <EOL> tol = <NUM_LIT:10> ** - <NUM_LIT:6> <EOL> edges = graph . getAllEdges ( ) <EOL> X = GraphUtils . vertexLabelPairs ( graph , edges ) <EOL> self . assertTrue ( numpy . linalg . norm ( X - edges ) < tol ) <EOL> X = GraphUtils . vertexLabelPairs ( graph , edges [ [ <NUM_LIT:5> , <NUM_LIT:2> , <NUM_LIT:1> ] , : ] ) <EOL> self . assertTrue ( numpy . linalg . norm ( X - edges [ [ <NUM_LIT:5> , <NUM_LIT:2> , <NUM_LIT:1> ] , : ] ) < tol ) <EOL> numVertices = <NUM_LIT:6> <EOL> numFeatures = <NUM_LIT:2> <EOL> vList = VertexList ( numVertices , numFeatures ) <EOL> vList . setVertices ( numpy . random . randn ( numVertices , numFeatures ) ) <EOL> graph = DenseGraph ( vList , True ) <EOL> graph . addEdge ( <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:0.1> ) <EOL> graph . addEdge ( <NUM_LIT:1> , <NUM_LIT:3> , <NUM_LIT:0.1> ) <EOL> edges = graph . getAllEdges ( ) <EOL> X = GraphUtils . vertexLabelPairs ( graph , edges ) <EOL> self . assertTrue ( numpy . linalg . norm ( X [ <NUM_LIT:0> , <NUM_LIT:0> : numFeatures ] - vList . getVertex ( <NUM_LIT:1> ) ) < tol ) <EOL> self . assertTrue ( numpy . linalg . norm ( X [ <NUM_LIT:0> , numFeatures : numFeatures * <NUM_LIT:2> ] - vList . getVertex ( <NUM_LIT:0> ) ) < tol ) <EOL> self . assertTrue ( numpy . linalg . norm ( X [ <NUM_LIT:1> , <NUM_LIT:0> : numFeatures ] - vList . getVertex ( <NUM_LIT:3> ) ) < tol ) <EOL> self . assertTrue ( numpy . linalg . norm ( X [ <NUM_LIT:1> , numFeatures : numFeatures * <NUM_LIT:2> ] - vList . getVertex ( <NUM_LIT:1> ) ) < tol ) <EOL> graph = DenseGraph ( vList , False ) <EOL> graph . addEdge ( <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:0.1> ) <EOL> graph . addEdge ( <NUM_LIT:1> , <NUM_LIT:3> , <NUM_LIT:0.1> ) <EOL> edges = graph . getAllEdges ( ) <EOL> X = GraphUtils . vertexLabelPairs ( graph , edges ) <EOL> self . assertTrue ( numpy . linalg . norm ( X [ <NUM_LIT:0> , <NUM_LIT:0> : numFeatures ] - vList . getVertex ( <NUM_LIT:0> ) ) < tol ) <EOL> self . assertTrue ( numpy . linalg . norm ( X [ <NUM_LIT:0> , numFeatures : numFeatures * <NUM_LIT:2> ] - vList . getVertex ( <NUM_LIT:1> ) ) < tol ) <EOL> self . assertTrue ( numpy . linalg . norm ( X [ <NUM_LIT:1> , <NUM_LIT:0> : numFeatures ] - vList . getVertex ( <NUM_LIT:1> ) ) < tol ) <EOL> self . assertTrue ( numpy . linalg . norm ( X [ <NUM_LIT:1> , numFeatures : numFeatures * <NUM_LIT:2> ] - vList . getVertex ( <NUM_LIT:3> ) ) < tol ) <EOL> def testModularity ( self ) : <EOL> numVertices = <NUM_LIT:6> <EOL> graph = SparseGraph ( GeneralVertexList ( numVertices ) ) <EOL> graph . addEdge ( <NUM_LIT:0> , <NUM_LIT:0> ) <EOL> graph . addEdge ( <NUM_LIT:1> , <NUM_LIT:1> ) <EOL> graph . addEdge ( <NUM_LIT:2> , <NUM_LIT:2> ) <EOL> graph . addEdge ( <NUM_LIT:0> , <NUM_LIT:1> ) <EOL> graph . addEdge ( <NUM_LIT:0> , <NUM_LIT:2> ) <EOL> graph . addEdge ( <NUM_LIT:2> , <NUM_LIT:1> ) <EOL> graph . addEdge ( <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT:2> ) <EOL> graph . addEdge ( <NUM_LIT:3> , <NUM_LIT:5> , <NUM_LIT:2> ) <EOL> graph . addEdge ( <NUM_LIT:4> , <NUM_LIT:5> , <NUM_LIT:2> ) <EOL> graph . addEdge ( <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:2> ) <EOL> graph . addEdge ( <NUM_LIT:4> , <NUM_LIT:4> , <NUM_LIT:2> ) <EOL> graph . addEdge ( <NUM_LIT:5> , <NUM_LIT:5> , <NUM_LIT:2> ) <EOL> W = graph . getWeightMatrix ( ) <EOL> clustering = numpy . array ( [ <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> ] ) <EOL> Q = GraphUtils . modularity ( W , clustering ) <EOL> self . assertEquals ( Q , <NUM_LIT> / <NUM_LIT> ) <EOL> Ws = scipy . sparse . csr_matrix ( W ) <EOL> Q = GraphUtils . modularity ( Ws , clustering ) <EOL> self . assertEquals ( Q , <NUM_LIT> / <NUM_LIT> ) <EOL> W = numpy . ones ( ( numVertices , numVertices ) ) <EOL> Q = GraphUtils . modularity ( W , clustering ) <EOL> self . assertEquals ( Q , <NUM_LIT:0.0> ) <EOL> Ws = scipy . sparse . csr_matrix ( W ) <EOL> Q = GraphUtils . modularity ( Ws , clustering ) <EOL> self . assertEquals ( Q , <NUM_LIT:0.0> ) <EOL> def testKwayNormalisedCut ( self ) : <EOL> numVertices = <NUM_LIT:6> <EOL> graph = SparseGraph ( GeneralVertexList ( numVertices ) ) <EOL> graph . addEdge ( <NUM_LIT:0> , <NUM_LIT:1> ) <EOL> graph . addEdge ( <NUM_LIT:0> , <NUM_LIT:2> ) <EOL> graph . addEdge ( <NUM_LIT:2> , <NUM_LIT:1> ) <EOL> graph . addEdge ( <NUM_LIT:3> , <NUM_LIT:4> ) <EOL> graph . addEdge ( <NUM_LIT:3> , <NUM_LIT:5> ) <EOL> graph . addEdge ( <NUM_LIT:5> , <NUM_LIT:4> ) <EOL> W = graph . getWeightMatrix ( ) <EOL> clustering = numpy . array ( [ <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> ] ) <EOL> self . assertEquals ( GraphUtils . kwayNormalisedCut ( W , clustering ) , <NUM_LIT:0.0> ) <EOL> Ws = scipy . sparse . csr_matrix ( W ) <EOL> self . assertEquals ( GraphUtils . kwayNormalisedCut ( Ws , clustering ) , <NUM_LIT:0.0> ) <EOL> graph . addEdge ( <NUM_LIT:2> , <NUM_LIT:3> ) <EOL> W = graph . getWeightMatrix ( ) <EOL> self . assertEquals ( GraphUtils . kwayNormalisedCut ( W , clustering ) , <NUM_LIT:1.0> / <NUM_LIT:7> ) <EOL> Ws = scipy . sparse . csr_matrix ( W ) <EOL> self . assertEquals ( GraphUtils . kwayNormalisedCut ( Ws , clustering ) , <NUM_LIT:1.0> / <NUM_LIT:7> ) <EOL> clustering = numpy . array ( [ <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:2> ] ) <EOL> self . assertEquals ( GraphUtils . kwayNormalisedCut ( W , clustering ) , <NUM_LIT> / <NUM_LIT> ) <EOL> self . assertEquals ( GraphUtils . kwayNormalisedCut ( Ws , clustering ) , <NUM_LIT> / <NUM_LIT> ) <EOL> W = numpy . zeros ( ( <NUM_LIT:2> , <NUM_LIT:2> ) ) <EOL> clustering = numpy . array ( [ <NUM_LIT:0> , <NUM_LIT:1> ] ) <EOL> self . assertEquals ( GraphUtils . kwayNormalisedCut ( W , clustering ) , <NUM_LIT:0.0> ) <EOL> Ws = scipy . sparse . csr_matrix ( W ) <EOL> self . assertEquals ( GraphUtils . kwayNormalisedCut ( Ws , clustering ) , <NUM_LIT:0.0> ) <EOL> def testShiftLaplacian ( self ) : <EOL> numVertices = <NUM_LIT:10> <EOL> numFeatures = <NUM_LIT:0> <EOL> vList = VertexList ( numVertices , numFeatures ) <EOL> graph = SparseGraph ( vList ) <EOL> ell = <NUM_LIT:2> <EOL> m = <NUM_LIT:2> <EOL> generator = BarabasiAlbertGenerator ( ell , m ) <EOL> graph = generator . generate ( graph ) <EOL> k = <NUM_LIT:10> <EOL> W = graph . getSparseWeightMatrix ( ) <EOL> L = GraphUtils . shiftLaplacian ( W ) <EOL> L2 = <NUM_LIT:2> * numpy . eye ( numVertices ) - graph . normalisedLaplacianSym ( ) <EOL> tol = <NUM_LIT:10> ** - <NUM_LIT:6> <EOL> self . assertTrue ( numpy . linalg . norm ( L - L2 ) < tol ) <EOL> def testNormalisedLaplacianSym ( self ) : <EOL> numVertices = <NUM_LIT:10> <EOL> numFeatures = <NUM_LIT:0> <EOL> vList = VertexList ( numVertices , numFeatures ) <EOL> graph = SparseGraph ( vList ) <EOL> ell = <NUM_LIT:2> <EOL> m = <NUM_LIT:2> <EOL> generator = BarabasiAlbertGenerator ( ell , m ) <EOL> graph = generator . generate ( graph ) <EOL> k = <NUM_LIT:10> <EOL> W = graph . getSparseWeightMatrix ( ) <EOL> L = GraphUtils . shiftLaplacian ( W ) <EOL> L2 = graph . normalisedLaplacianSym ( ) <EOL> tol = <NUM_LIT:10> ** - <NUM_LIT:6> <EOL> self . assertTrue ( numpy . linalg . norm ( L + L2 - <NUM_LIT:2> * numpy . eye ( numVertices ) ) < tol ) <EOL> W = scipy . sparse . csr_matrix ( ( <NUM_LIT:5> , <NUM_LIT:5> ) ) <EOL> W [ <NUM_LIT:1> , <NUM_LIT:0> ] = <NUM_LIT:1> <EOL> W [ <NUM_LIT:0> , <NUM_LIT:1> ] = <NUM_LIT:1> <EOL> L = GraphUtils . normalisedLaplacianSym ( W ) <EOL> for i in range ( <NUM_LIT:2> , <NUM_LIT:5> ) : <EOL> self . assertEquals ( L [ i , i ] , <NUM_LIT:0> ) <EOL> def testNormalisedLaplacianRw ( self ) : <EOL> numVertices = <NUM_LIT:10> <EOL> numFeatures = <NUM_LIT:0> <EOL> vList = VertexList ( numVertices , numFeatures ) <EOL> graph = SparseGraph ( vList ) <EOL> ell = <NUM_LIT:2> <EOL> m = <NUM_LIT:2> <EOL> generator = BarabasiAlbertGenerator ( ell , m ) <EOL> graph = generator . generate ( graph ) <EOL> k = <NUM_LIT:10> <EOL> W = graph . getSparseWeightMatrix ( ) <EOL> L = GraphUtils . normalisedLaplacianRw ( W ) <EOL> L2 = graph . normalisedLaplacianRw ( ) <EOL> tol = <NUM_LIT:10> ** - <NUM_LIT:6> <EOL> self . assertTrue ( numpy . linalg . norm ( L - L2 ) < tol ) <EOL> W = scipy . sparse . csr_matrix ( ( <NUM_LIT:5> , <NUM_LIT:5> ) ) <EOL> W [ <NUM_LIT:1> , <NUM_LIT:0> ] = <NUM_LIT:1> <EOL> W [ <NUM_LIT:0> , <NUM_LIT:1> ] = <NUM_LIT:1> <EOL> L = GraphUtils . normalisedLaplacianRw ( W ) <EOL> for i in range ( <NUM_LIT:2> , <NUM_LIT:5> ) : <EOL> self . assertEquals ( L [ i , i ] , <NUM_LIT:0> ) <EOL> def testRandIndex ( self ) : <EOL> clustering1 = numpy . array ( [ <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:2> , <NUM_LIT:2> ] ) <EOL> clustering2 = numpy . array ( [ <NUM_LIT:2> , <NUM_LIT:2> , <NUM_LIT:2> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> ] ) <EOL> self . assertEquals ( GraphUtils . randIndex ( clustering1 , clustering2 ) , <NUM_LIT:0.0> ) <EOL> clustering2 = numpy . array ( [ <NUM_LIT:2> , <NUM_LIT:2> , <NUM_LIT:2> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:2> ] ) <EOL> self . assertEquals ( GraphUtils . randIndex ( clustering1 , clustering2 ) , <NUM_LIT:1> / <NUM_LIT> ) <EOL> clustering2 = numpy . array ( [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:2> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:2> ] ) <EOL> self . assertEquals ( GraphUtils . randIndex ( clustering1 , clustering2 ) , <NUM_LIT:16> / <NUM_LIT> ) <EOL> @ unittest . skip ( "<STR_LIT>" ) <EOL> def testModularityMatrix ( self ) : <EOL> W = scipy . sparse . csr_matrix ( ( <NUM_LIT:5> , <NUM_LIT:5> ) ) <EOL> W [ <NUM_LIT:1> , <NUM_LIT:0> ] = <NUM_LIT:1> <EOL> W [ <NUM_LIT:0> , <NUM_LIT:1> ] = <NUM_LIT:1> <EOL> W [ <NUM_LIT:2> , <NUM_LIT:3> ] = <NUM_LIT:1> <EOL> W [ <NUM_LIT:3> , <NUM_LIT:2> ] = <NUM_LIT:1> <EOL> B = GraphUtils . modularityMatrix ( W ) <EOL> B2 = numpy . zeros ( ( <NUM_LIT:5> , <NUM_LIT:5> ) ) <EOL> d = numpy . array ( W . sum ( <NUM_LIT:0> ) . ravel ( ) ) . ravel ( ) <EOL> m = W . getnnz ( ) / <NUM_LIT:2> <EOL> for i in range ( <NUM_LIT:5> ) : <EOL> for j in range ( <NUM_LIT:5> ) : <EOL> B2 [ i , j ] = W [ i , j ] - d [ i ] * d [ j ] / <NUM_LIT:2> * m <EOL> self . assertEquals ( B2 [ i , j ] , B [ i , j ] ) <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> unittest . main ( ) </s>
