diff options
Diffstat (limited to 'lib/python2.7/site-packages/setoolsgui/networkx/linalg/tests/test_laplacian.py')
| -rw-r--r-- | lib/python2.7/site-packages/setoolsgui/networkx/linalg/tests/test_laplacian.py | 101 |
1 files changed, 101 insertions, 0 deletions
diff --git a/lib/python2.7/site-packages/setoolsgui/networkx/linalg/tests/test_laplacian.py b/lib/python2.7/site-packages/setoolsgui/networkx/linalg/tests/test_laplacian.py new file mode 100644 index 0000000..87725fe --- /dev/null +++ b/lib/python2.7/site-packages/setoolsgui/networkx/linalg/tests/test_laplacian.py @@ -0,0 +1,101 @@ +from nose import SkipTest + +import networkx as nx +from networkx.generators.degree_seq import havel_hakimi_graph + +class TestLaplacian(object): + numpy=1 # nosetests attribute, use nosetests -a 'not numpy' to skip test + @classmethod + def setupClass(cls): + global numpy + global assert_equal + global assert_almost_equal + try: + import numpy + from numpy.testing import assert_equal,assert_almost_equal + except ImportError: + raise SkipTest('NumPy not available.') + + def setUp(self): + deg=[3,2,2,1,0] + self.G=havel_hakimi_graph(deg) + self.WG=nx.Graph( (u,v,{'weight':0.5,'other':0.3}) + for (u,v) in self.G.edges_iter() ) + self.WG.add_node(4) + self.MG=nx.MultiGraph(self.G) + + # Graph with selfloops + self.Gsl = self.G.copy() + for node in self.Gsl.nodes(): + self.Gsl.add_edge(node, node) + + + def test_laplacian(self): + "Graph Laplacian" + NL=numpy.array([[ 3, -1, -1, -1, 0], + [-1, 2, -1, 0, 0], + [-1, -1, 2, 0, 0], + [-1, 0, 0, 1, 0], + [ 0, 0, 0, 0, 0]]) + WL=0.5*NL + OL=0.3*NL + assert_equal(nx.laplacian_matrix(self.G),NL) + assert_equal(nx.laplacian_matrix(self.MG),NL) + assert_equal(nx.laplacian_matrix(self.G,nodelist=[0,1]), + numpy.array([[ 1, -1],[-1, 1]])) + assert_equal(nx.laplacian_matrix(self.WG),WL) + assert_equal(nx.laplacian_matrix(self.WG,weight=None),NL) + assert_equal(nx.laplacian_matrix(self.WG,weight='other'),OL) + + def test_normalized_laplacian(self): + "Generalized Graph Laplacian" + GL=numpy.array([[ 1.00, -0.408, -0.408, -0.577, 0.00], + [-0.408, 1.00, -0.50, 0.00 , 0.00], + [-0.408, -0.50, 1.00, 0.00, 0.00], + [-0.577, 0.00, 0.00, 1.00, 0.00], + [ 0.00, 0.00, 0.00, 0.00, 0.00]]) + Lsl = numpy.array([[ 0.75 , -0.2887, -0.2887, -0.3536, 0.], + [-0.2887, 0.6667, -0.3333, 0. , 0.], + [-0.2887, -0.3333, 0.6667, 0. , 0.], + [-0.3536, 0. , 0. , 0.5 , 0.], + [ 0. , 0. , 0. , 0. , 0.]]) + + assert_almost_equal(nx.normalized_laplacian_matrix(self.G),GL,decimal=3) + assert_almost_equal(nx.normalized_laplacian_matrix(self.MG),GL,decimal=3) + assert_almost_equal(nx.normalized_laplacian_matrix(self.WG),GL,decimal=3) + assert_almost_equal(nx.normalized_laplacian_matrix(self.WG,weight='other'),GL,decimal=3) + assert_almost_equal(nx.normalized_laplacian_matrix(self.Gsl), Lsl, decimal=3) + + def test_directed_laplacian(self): + "Directed Laplacian" + # Graph used as an example in Sec. 4.1 of Langville and Meyer, + # "Google's PageRank and Beyond". The graph contains dangling nodes, so + # the pagerank random walk is selected by directed_laplacian + G = nx.DiGraph() + G.add_edges_from(((1,2), (1,3), (3,1), (3,2), (3,5), (4,5), (4,6), + (5,4), (5,6), (6,4))) + GL = numpy.array([[ 0.9833, -0.2941, -0.3882, -0.0291, -0.0231, -0.0261], + [-0.2941, 0.8333, -0.2339, -0.0536, -0.0589, -0.0554], + [-0.3882, -0.2339, 0.9833, -0.0278, -0.0896, -0.0251], + [-0.0291, -0.0536, -0.0278, 0.9833, -0.4878, -0.6675], + [-0.0231, -0.0589, -0.0896, -0.4878, 0.9833, -0.2078], + [-0.0261, -0.0554, -0.0251, -0.6675, -0.2078, 0.9833]]) + assert_almost_equal(nx.directed_laplacian_matrix(G, alpha=0.9), GL, decimal=3) + + # Make the graph strongly connected, so we can use a random and lazy walk + G.add_edges_from((((2,5), (6,1)))) + GL = numpy.array([[ 1. , -0.3062, -0.4714, 0. , 0. , -0.3227], + [-0.3062, 1. , -0.1443, 0. , -0.3162, 0. ], + [-0.4714, -0.1443, 1. , 0. , -0.0913, 0. ], + [ 0. , 0. , 0. , 1. , -0.5 , -0.5 ], + [ 0. , -0.3162, -0.0913, -0.5 , 1. , -0.25 ], + [-0.3227, 0. , 0. , -0.5 , -0.25 , 1. ]]) + assert_almost_equal(nx.directed_laplacian_matrix(G, walk_type='random'), GL, decimal=3) + + GL = numpy.array([[ 0.5 , -0.1531, -0.2357, 0. , 0. , -0.1614], + [-0.1531, 0.5 , -0.0722, 0. , -0.1581, 0. ], + [-0.2357, -0.0722, 0.5 , 0. , -0.0456, 0. ], + [ 0. , 0. , 0. , 0.5 , -0.25 , -0.25 ], + [ 0. , -0.1581, -0.0456, -0.25 , 0.5 , -0.125 ], + [-0.1614, 0. , 0. , -0.25 , -0.125 , 0.5 ]]) + assert_almost_equal(nx.directed_laplacian_matrix(G, walk_type='lazy'), GL, decimal=3) |