Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/linalg/tests/test_laplacian.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author shellac
date Mon, 22 Mar 2021 18:12:50 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:4f3585e2f14b
1 import pytest
2
3 np = pytest.importorskip("numpy")
4 npt = pytest.importorskip("numpy.testing")
5 pytest.importorskip("scipy")
6
7 import networkx as nx
8 from networkx.generators.degree_seq import havel_hakimi_graph
9 from networkx.generators.expanders import margulis_gabber_galil_graph
10
11
12 class TestLaplacian:
13 @classmethod
14 def setup_class(cls):
15 deg = [3, 2, 2, 1, 0]
16 cls.G = havel_hakimi_graph(deg)
17 cls.WG = nx.Graph(
18 (u, v, {"weight": 0.5, "other": 0.3}) for (u, v) in cls.G.edges()
19 )
20 cls.WG.add_node(4)
21 cls.MG = nx.MultiGraph(cls.G)
22
23 # Graph with clsloops
24 cls.Gsl = cls.G.copy()
25 for node in cls.Gsl.nodes():
26 cls.Gsl.add_edge(node, node)
27
28 def test_laplacian(self):
29 "Graph Laplacian"
30 # fmt: off
31 NL = np.array([[3, -1, -1, -1, 0],
32 [-1, 2, -1, 0, 0],
33 [-1, -1, 2, 0, 0],
34 [-1, 0, 0, 1, 0],
35 [0, 0, 0, 0, 0]])
36 # fmt: on
37 WL = 0.5 * NL
38 OL = 0.3 * NL
39 npt.assert_equal(nx.laplacian_matrix(self.G).todense(), NL)
40 npt.assert_equal(nx.laplacian_matrix(self.MG).todense(), NL)
41 npt.assert_equal(
42 nx.laplacian_matrix(self.G, nodelist=[0, 1]).todense(),
43 np.array([[1, -1], [-1, 1]]),
44 )
45 npt.assert_equal(nx.laplacian_matrix(self.WG).todense(), WL)
46 npt.assert_equal(nx.laplacian_matrix(self.WG, weight=None).todense(), NL)
47 npt.assert_equal(nx.laplacian_matrix(self.WG, weight="other").todense(), OL)
48
49 def test_normalized_laplacian(self):
50 "Generalized Graph Laplacian"
51 # fmt: off
52 G = np.array([[ 1. , -0.408, -0.408, -0.577, 0.],
53 [-0.408, 1. , -0.5 , 0. , 0.],
54 [-0.408, -0.5 , 1. , 0. , 0.],
55 [-0.577, 0. , 0. , 1. , 0.],
56 [ 0. , 0. , 0. , 0. , 0.]])
57 GL = np.array([[1.00, -0.408, -0.408, -0.577, 0.00],
58 [-0.408, 1.00, -0.50, 0.00, 0.00],
59 [-0.408, -0.50, 1.00, 0.00, 0.00],
60 [-0.577, 0.00, 0.00, 1.00, 0.00],
61 [0.00, 0.00, 0.00, 0.00, 0.00]])
62 Lsl = np.array([[0.75, -0.2887, -0.2887, -0.3536, 0.],
63 [-0.2887, 0.6667, -0.3333, 0., 0.],
64 [-0.2887, -0.3333, 0.6667, 0., 0.],
65 [-0.3536, 0., 0., 0.5, 0.],
66 [0., 0., 0., 0., 0.]])
67 # fmt: on
68
69 npt.assert_almost_equal(
70 nx.normalized_laplacian_matrix(self.G, nodelist=range(5)).todense(),
71 G,
72 decimal=3,
73 )
74 npt.assert_almost_equal(
75 nx.normalized_laplacian_matrix(self.G).todense(), GL, decimal=3
76 )
77 npt.assert_almost_equal(
78 nx.normalized_laplacian_matrix(self.MG).todense(), GL, decimal=3
79 )
80 npt.assert_almost_equal(
81 nx.normalized_laplacian_matrix(self.WG).todense(), GL, decimal=3
82 )
83 npt.assert_almost_equal(
84 nx.normalized_laplacian_matrix(self.WG, weight="other").todense(),
85 GL,
86 decimal=3,
87 )
88 npt.assert_almost_equal(
89 nx.normalized_laplacian_matrix(self.Gsl).todense(), Lsl, decimal=3
90 )
91
92 def test_directed_laplacian(self):
93 "Directed Laplacian"
94 # Graph used as an example in Sec. 4.1 of Langville and Meyer,
95 # "Google's PageRank and Beyond". The graph contains dangling nodes, so
96 # the pagerank random walk is selected by directed_laplacian
97 G = nx.DiGraph()
98 G.add_edges_from(
99 (
100 (1, 2),
101 (1, 3),
102 (3, 1),
103 (3, 2),
104 (3, 5),
105 (4, 5),
106 (4, 6),
107 (5, 4),
108 (5, 6),
109 (6, 4),
110 )
111 )
112 # fmt: off
113 GL = np.array([[0.9833, -0.2941, -0.3882, -0.0291, -0.0231, -0.0261],
114 [-0.2941, 0.8333, -0.2339, -0.0536, -0.0589, -0.0554],
115 [-0.3882, -0.2339, 0.9833, -0.0278, -0.0896, -0.0251],
116 [-0.0291, -0.0536, -0.0278, 0.9833, -0.4878, -0.6675],
117 [-0.0231, -0.0589, -0.0896, -0.4878, 0.9833, -0.2078],
118 [-0.0261, -0.0554, -0.0251, -0.6675, -0.2078, 0.9833]])
119 # fmt: on
120 L = nx.directed_laplacian_matrix(G, alpha=0.9, nodelist=sorted(G))
121 npt.assert_almost_equal(L, GL, decimal=3)
122
123 # Make the graph strongly connected, so we can use a random and lazy walk
124 G.add_edges_from(((2, 5), (6, 1)))
125 # fmt: off
126 GL = np.array([[1., -0.3062, -0.4714, 0., 0., -0.3227],
127 [-0.3062, 1., -0.1443, 0., -0.3162, 0.],
128 [-0.4714, -0.1443, 1., 0., -0.0913, 0.],
129 [0., 0., 0., 1., -0.5, -0.5],
130 [0., -0.3162, -0.0913, -0.5, 1., -0.25],
131 [-0.3227, 0., 0., -0.5, -0.25, 1.]])
132 # fmt: on
133 L = nx.directed_laplacian_matrix(
134 G, alpha=0.9, nodelist=sorted(G), walk_type="random"
135 )
136 npt.assert_almost_equal(L, GL, decimal=3)
137
138 # fmt: off
139 GL = np.array([[0.5, -0.1531, -0.2357, 0., 0., -0.1614],
140 [-0.1531, 0.5, -0.0722, 0., -0.1581, 0.],
141 [-0.2357, -0.0722, 0.5, 0., -0.0456, 0.],
142 [0., 0., 0., 0.5, -0.25, -0.25],
143 [0., -0.1581, -0.0456, -0.25, 0.5, -0.125],
144 [-0.1614, 0., 0., -0.25, -0.125, 0.5]])
145 # fmt: on
146 L = nx.directed_laplacian_matrix(
147 G, alpha=0.9, nodelist=sorted(G), walk_type="lazy"
148 )
149 npt.assert_almost_equal(L, GL, decimal=3)
150
151 def test_directed_combinatorial_laplacian(self):
152 "Directed combinatorial Laplacian"
153 # Graph used as an example in Sec. 4.1 of Langville and Meyer,
154 # "Google's PageRank and Beyond". The graph contains dangling nodes, so
155 # the pagerank random walk is selected by directed_laplacian
156 G = nx.DiGraph()
157 G.add_edges_from(
158 (
159 (1, 2),
160 (1, 3),
161 (3, 1),
162 (3, 2),
163 (3, 5),
164 (4, 5),
165 (4, 6),
166 (5, 4),
167 (5, 6),
168 (6, 4),
169 )
170 )
171 # fmt: off
172 GL = np.array([[0.0366, -0.0132, -0.0153, -0.0034, -0.0020, -0.0027],
173 [-0.0132, 0.0450, -0.0111, -0.0076, -0.0062, -0.0069],
174 [-0.0153, -0.0111, 0.0408, -0.0035, -0.0083, -0.0027],
175 [-0.0034, -0.0076, -0.0035, 0.3688, -0.1356, -0.2187],
176 [-0.0020, -0.0062, -0.0083, -0.1356, 0.2026, -0.0505],
177 [-0.0027, -0.0069, -0.0027, -0.2187, -0.0505, 0.2815]])
178 # fmt: on
179
180 L = nx.directed_combinatorial_laplacian_matrix(G, alpha=0.9, nodelist=sorted(G))
181 npt.assert_almost_equal(L, GL, decimal=3)
182
183 # Make the graph strongly connected, so we can use a random and lazy walk
184 G.add_edges_from(((2, 5), (6, 1)))
185
186 # fmt: off
187 GL = np.array([[0.1395, -0.0349, -0.0465, 0, 0, -0.0581],
188 [-0.0349, 0.0930, -0.0116, 0, -0.0465, 0],
189 [-0.0465, -0.0116, 0.0698, 0, -0.0116, 0],
190 [0, 0, 0, 0.2326, -0.1163, -0.1163],
191 [0, -0.0465, -0.0116, -0.1163, 0.2326, -0.0581],
192 [-0.0581, 0, 0, -0.1163, -0.0581, 0.2326]])
193 # fmt: on
194
195 L = nx.directed_combinatorial_laplacian_matrix(
196 G, alpha=0.9, nodelist=sorted(G), walk_type="random"
197 )
198 npt.assert_almost_equal(L, GL, decimal=3)
199
200 # fmt: off
201 GL = np.array([[0.0698, -0.0174, -0.0233, 0, 0, -0.0291],
202 [-0.0174, 0.0465, -0.0058, 0, -0.0233, 0],
203 [-0.0233, -0.0058, 0.0349, 0, -0.0058, 0],
204 [0, 0, 0, 0.1163, -0.0581, -0.0581],
205 [0, -0.0233, -0.0058, -0.0581, 0.1163, -0.0291],
206 [-0.0291, 0, 0, -0.0581, -0.0291, 0.1163]])
207 # fmt: on
208
209 L = nx.directed_combinatorial_laplacian_matrix(
210 G, alpha=0.9, nodelist=sorted(G), walk_type="lazy"
211 )
212 npt.assert_almost_equal(L, GL, decimal=3)
213
214 E = nx.DiGraph(margulis_gabber_galil_graph(2))
215 L = nx.directed_combinatorial_laplacian_matrix(E)
216 # fmt: off
217 expected = np.array(
218 [[ 0.16666667, -0.08333333, -0.08333333, 0. ],
219 [-0.08333333, 0.16666667, 0. , -0.08333333],
220 [-0.08333333, 0. , 0.16666667, -0.08333333],
221 [ 0. , -0.08333333, -0.08333333, 0.16666667]]
222 )
223 # fmt: on
224 npt.assert_almost_equal(L, expected, decimal=6)
225
226 with pytest.raises(nx.NetworkXError):
227 nx.directed_combinatorial_laplacian_matrix(
228 G, walk_type="pagerank", alpha=100
229 )
230 with pytest.raises(nx.NetworkXError):
231 nx.directed_combinatorial_laplacian_matrix(G, walk_type="silly")