Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_similarity.py @ 0:4f3585e2f14b draft default tip
"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 import networkx as nx | |
4 from networkx.algorithms.similarity import ( | |
5 graph_edit_distance, | |
6 optimal_edit_paths, | |
7 optimize_graph_edit_distance, | |
8 ) | |
9 from networkx.generators.classic import ( | |
10 circular_ladder_graph, | |
11 cycle_graph, | |
12 path_graph, | |
13 wheel_graph, | |
14 ) | |
15 | |
16 | |
17 def nmatch(n1, n2): | |
18 return n1 == n2 | |
19 | |
20 | |
21 def ematch(e1, e2): | |
22 return e1 == e2 | |
23 | |
24 | |
25 def getCanonical(): | |
26 G = nx.Graph() | |
27 G.add_node("A", label="A") | |
28 G.add_node("B", label="B") | |
29 G.add_node("C", label="C") | |
30 G.add_node("D", label="D") | |
31 G.add_edge("A", "B", label="a-b") | |
32 G.add_edge("B", "C", label="b-c") | |
33 G.add_edge("B", "D", label="b-d") | |
34 return G | |
35 | |
36 | |
37 class TestSimilarity: | |
38 @classmethod | |
39 def setup_class(cls): | |
40 global numpy | |
41 global scipy | |
42 numpy = pytest.importorskip("numpy") | |
43 scipy = pytest.importorskip("scipy") | |
44 | |
45 def test_graph_edit_distance_roots_and_timeout(self): | |
46 G0 = nx.star_graph(5) | |
47 G1 = G0.copy() | |
48 pytest.raises(ValueError, graph_edit_distance, G0, G1, roots=[2]) | |
49 pytest.raises(ValueError, graph_edit_distance, G0, G1, roots=[2, 3, 4]) | |
50 pytest.raises(nx.NodeNotFound, graph_edit_distance, G0, G1, roots=(9, 3)) | |
51 pytest.raises(nx.NodeNotFound, graph_edit_distance, G0, G1, roots=(3, 9)) | |
52 pytest.raises(nx.NodeNotFound, graph_edit_distance, G0, G1, roots=(9, 9)) | |
53 assert graph_edit_distance(G0, G1, roots=(1, 2)) == 0 | |
54 assert graph_edit_distance(G0, G1, roots=(0, 1)) == 8 | |
55 assert graph_edit_distance(G0, G1, roots=(1, 2), timeout=5) == 0 | |
56 assert graph_edit_distance(G0, G1, roots=(0, 1), timeout=5) == 8 | |
57 assert graph_edit_distance(G0, G1, roots=(0, 1), timeout=0.0001) is None | |
58 # test raise on 0 timeout | |
59 pytest.raises(nx.NetworkXError, graph_edit_distance, G0, G1, timeout=0) | |
60 | |
61 def test_graph_edit_distance(self): | |
62 G0 = nx.Graph() | |
63 G1 = path_graph(6) | |
64 G2 = cycle_graph(6) | |
65 G3 = wheel_graph(7) | |
66 | |
67 assert graph_edit_distance(G0, G0) == 0 | |
68 assert graph_edit_distance(G0, G1) == 11 | |
69 assert graph_edit_distance(G1, G0) == 11 | |
70 assert graph_edit_distance(G0, G2) == 12 | |
71 assert graph_edit_distance(G2, G0) == 12 | |
72 assert graph_edit_distance(G0, G3) == 19 | |
73 assert graph_edit_distance(G3, G0) == 19 | |
74 | |
75 assert graph_edit_distance(G1, G1) == 0 | |
76 assert graph_edit_distance(G1, G2) == 1 | |
77 assert graph_edit_distance(G2, G1) == 1 | |
78 assert graph_edit_distance(G1, G3) == 8 | |
79 assert graph_edit_distance(G3, G1) == 8 | |
80 | |
81 assert graph_edit_distance(G2, G2) == 0 | |
82 assert graph_edit_distance(G2, G3) == 7 | |
83 assert graph_edit_distance(G3, G2) == 7 | |
84 | |
85 assert graph_edit_distance(G3, G3) == 0 | |
86 | |
87 def test_graph_edit_distance_node_match(self): | |
88 G1 = cycle_graph(5) | |
89 G2 = cycle_graph(5) | |
90 for n, attr in G1.nodes.items(): | |
91 attr["color"] = "red" if n % 2 == 0 else "blue" | |
92 for n, attr in G2.nodes.items(): | |
93 attr["color"] = "red" if n % 2 == 1 else "blue" | |
94 assert graph_edit_distance(G1, G2) == 0 | |
95 assert ( | |
96 graph_edit_distance( | |
97 G1, G2, node_match=lambda n1, n2: n1["color"] == n2["color"] | |
98 ) | |
99 == 1 | |
100 ) | |
101 | |
102 def test_graph_edit_distance_edge_match(self): | |
103 G1 = path_graph(6) | |
104 G2 = path_graph(6) | |
105 for e, attr in G1.edges.items(): | |
106 attr["color"] = "red" if min(e) % 2 == 0 else "blue" | |
107 for e, attr in G2.edges.items(): | |
108 attr["color"] = "red" if min(e) // 3 == 0 else "blue" | |
109 assert graph_edit_distance(G1, G2) == 0 | |
110 assert ( | |
111 graph_edit_distance( | |
112 G1, G2, edge_match=lambda e1, e2: e1["color"] == e2["color"] | |
113 ) | |
114 == 2 | |
115 ) | |
116 | |
117 def test_graph_edit_distance_node_cost(self): | |
118 G1 = path_graph(6) | |
119 G2 = path_graph(6) | |
120 for n, attr in G1.nodes.items(): | |
121 attr["color"] = "red" if n % 2 == 0 else "blue" | |
122 for n, attr in G2.nodes.items(): | |
123 attr["color"] = "red" if n % 2 == 1 else "blue" | |
124 | |
125 def node_subst_cost(uattr, vattr): | |
126 if uattr["color"] == vattr["color"]: | |
127 return 1 | |
128 else: | |
129 return 10 | |
130 | |
131 def node_del_cost(attr): | |
132 if attr["color"] == "blue": | |
133 return 20 | |
134 else: | |
135 return 50 | |
136 | |
137 def node_ins_cost(attr): | |
138 if attr["color"] == "blue": | |
139 return 40 | |
140 else: | |
141 return 100 | |
142 | |
143 assert ( | |
144 graph_edit_distance( | |
145 G1, | |
146 G2, | |
147 node_subst_cost=node_subst_cost, | |
148 node_del_cost=node_del_cost, | |
149 node_ins_cost=node_ins_cost, | |
150 ) | |
151 == 6 | |
152 ) | |
153 | |
154 def test_graph_edit_distance_edge_cost(self): | |
155 G1 = path_graph(6) | |
156 G2 = path_graph(6) | |
157 for e, attr in G1.edges.items(): | |
158 attr["color"] = "red" if min(e) % 2 == 0 else "blue" | |
159 for e, attr in G2.edges.items(): | |
160 attr["color"] = "red" if min(e) // 3 == 0 else "blue" | |
161 | |
162 def edge_subst_cost(gattr, hattr): | |
163 if gattr["color"] == hattr["color"]: | |
164 return 0.01 | |
165 else: | |
166 return 0.1 | |
167 | |
168 def edge_del_cost(attr): | |
169 if attr["color"] == "blue": | |
170 return 0.2 | |
171 else: | |
172 return 0.5 | |
173 | |
174 def edge_ins_cost(attr): | |
175 if attr["color"] == "blue": | |
176 return 0.4 | |
177 else: | |
178 return 1.0 | |
179 | |
180 assert ( | |
181 graph_edit_distance( | |
182 G1, | |
183 G2, | |
184 edge_subst_cost=edge_subst_cost, | |
185 edge_del_cost=edge_del_cost, | |
186 edge_ins_cost=edge_ins_cost, | |
187 ) | |
188 == 0.23 | |
189 ) | |
190 | |
191 def test_graph_edit_distance_upper_bound(self): | |
192 G1 = circular_ladder_graph(2) | |
193 G2 = circular_ladder_graph(6) | |
194 assert graph_edit_distance(G1, G2, upper_bound=5) is None | |
195 assert graph_edit_distance(G1, G2, upper_bound=24) == 22 | |
196 assert graph_edit_distance(G1, G2) == 22 | |
197 | |
198 def test_optimal_edit_paths(self): | |
199 G1 = path_graph(3) | |
200 G2 = cycle_graph(3) | |
201 paths, cost = optimal_edit_paths(G1, G2) | |
202 assert cost == 1 | |
203 assert len(paths) == 6 | |
204 | |
205 def canonical(vertex_path, edge_path): | |
206 return ( | |
207 tuple(sorted(vertex_path)), | |
208 tuple(sorted(edge_path, key=lambda x: (None in x, x))), | |
209 ) | |
210 | |
211 expected_paths = [ | |
212 ( | |
213 [(0, 0), (1, 1), (2, 2)], | |
214 [((0, 1), (0, 1)), ((1, 2), (1, 2)), (None, (0, 2))], | |
215 ), | |
216 ( | |
217 [(0, 0), (1, 2), (2, 1)], | |
218 [((0, 1), (0, 2)), ((1, 2), (1, 2)), (None, (0, 1))], | |
219 ), | |
220 ( | |
221 [(0, 1), (1, 0), (2, 2)], | |
222 [((0, 1), (0, 1)), ((1, 2), (0, 2)), (None, (1, 2))], | |
223 ), | |
224 ( | |
225 [(0, 1), (1, 2), (2, 0)], | |
226 [((0, 1), (1, 2)), ((1, 2), (0, 2)), (None, (0, 1))], | |
227 ), | |
228 ( | |
229 [(0, 2), (1, 0), (2, 1)], | |
230 [((0, 1), (0, 2)), ((1, 2), (0, 1)), (None, (1, 2))], | |
231 ), | |
232 ( | |
233 [(0, 2), (1, 1), (2, 0)], | |
234 [((0, 1), (1, 2)), ((1, 2), (0, 1)), (None, (0, 2))], | |
235 ), | |
236 ] | |
237 assert {canonical(*p) for p in paths} == {canonical(*p) for p in expected_paths} | |
238 | |
239 def test_optimize_graph_edit_distance(self): | |
240 G1 = circular_ladder_graph(2) | |
241 G2 = circular_ladder_graph(6) | |
242 bestcost = 1000 | |
243 for cost in optimize_graph_edit_distance(G1, G2): | |
244 assert cost < bestcost | |
245 bestcost = cost | |
246 assert bestcost == 22 | |
247 | |
248 # def test_graph_edit_distance_bigger(self): | |
249 # G1 = circular_ladder_graph(12) | |
250 # G2 = circular_ladder_graph(16) | |
251 # assert_equal(graph_edit_distance(G1, G2), 22) | |
252 | |
253 def test_selfloops(self): | |
254 G0 = nx.Graph() | |
255 G1 = nx.Graph() | |
256 G1.add_edges_from((("A", "A"), ("A", "B"))) | |
257 G2 = nx.Graph() | |
258 G2.add_edges_from((("A", "B"), ("B", "B"))) | |
259 G3 = nx.Graph() | |
260 G3.add_edges_from((("A", "A"), ("A", "B"), ("B", "B"))) | |
261 | |
262 assert graph_edit_distance(G0, G0) == 0 | |
263 assert graph_edit_distance(G0, G1) == 4 | |
264 assert graph_edit_distance(G1, G0) == 4 | |
265 assert graph_edit_distance(G0, G2) == 4 | |
266 assert graph_edit_distance(G2, G0) == 4 | |
267 assert graph_edit_distance(G0, G3) == 5 | |
268 assert graph_edit_distance(G3, G0) == 5 | |
269 | |
270 assert graph_edit_distance(G1, G1) == 0 | |
271 assert graph_edit_distance(G1, G2) == 0 | |
272 assert graph_edit_distance(G2, G1) == 0 | |
273 assert graph_edit_distance(G1, G3) == 1 | |
274 assert graph_edit_distance(G3, G1) == 1 | |
275 | |
276 assert graph_edit_distance(G2, G2) == 0 | |
277 assert graph_edit_distance(G2, G3) == 1 | |
278 assert graph_edit_distance(G3, G2) == 1 | |
279 | |
280 assert graph_edit_distance(G3, G3) == 0 | |
281 | |
282 def test_digraph(self): | |
283 G0 = nx.DiGraph() | |
284 G1 = nx.DiGraph() | |
285 G1.add_edges_from((("A", "B"), ("B", "C"), ("C", "D"), ("D", "A"))) | |
286 G2 = nx.DiGraph() | |
287 G2.add_edges_from((("A", "B"), ("B", "C"), ("C", "D"), ("A", "D"))) | |
288 G3 = nx.DiGraph() | |
289 G3.add_edges_from((("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"))) | |
290 | |
291 assert graph_edit_distance(G0, G0) == 0 | |
292 assert graph_edit_distance(G0, G1) == 8 | |
293 assert graph_edit_distance(G1, G0) == 8 | |
294 assert graph_edit_distance(G0, G2) == 8 | |
295 assert graph_edit_distance(G2, G0) == 8 | |
296 assert graph_edit_distance(G0, G3) == 8 | |
297 assert graph_edit_distance(G3, G0) == 8 | |
298 | |
299 assert graph_edit_distance(G1, G1) == 0 | |
300 assert graph_edit_distance(G1, G2) == 2 | |
301 assert graph_edit_distance(G2, G1) == 2 | |
302 assert graph_edit_distance(G1, G3) == 4 | |
303 assert graph_edit_distance(G3, G1) == 4 | |
304 | |
305 assert graph_edit_distance(G2, G2) == 0 | |
306 assert graph_edit_distance(G2, G3) == 2 | |
307 assert graph_edit_distance(G3, G2) == 2 | |
308 | |
309 assert graph_edit_distance(G3, G3) == 0 | |
310 | |
311 def test_multigraph(self): | |
312 G0 = nx.MultiGraph() | |
313 G1 = nx.MultiGraph() | |
314 G1.add_edges_from((("A", "B"), ("B", "C"), ("A", "C"))) | |
315 G2 = nx.MultiGraph() | |
316 G2.add_edges_from((("A", "B"), ("B", "C"), ("B", "C"), ("A", "C"))) | |
317 G3 = nx.MultiGraph() | |
318 G3.add_edges_from((("A", "B"), ("B", "C"), ("A", "C"), ("A", "C"), ("A", "C"))) | |
319 | |
320 assert graph_edit_distance(G0, G0) == 0 | |
321 assert graph_edit_distance(G0, G1) == 6 | |
322 assert graph_edit_distance(G1, G0) == 6 | |
323 assert graph_edit_distance(G0, G2) == 7 | |
324 assert graph_edit_distance(G2, G0) == 7 | |
325 assert graph_edit_distance(G0, G3) == 8 | |
326 assert graph_edit_distance(G3, G0) == 8 | |
327 | |
328 assert graph_edit_distance(G1, G1) == 0 | |
329 assert graph_edit_distance(G1, G2) == 1 | |
330 assert graph_edit_distance(G2, G1) == 1 | |
331 assert graph_edit_distance(G1, G3) == 2 | |
332 assert graph_edit_distance(G3, G1) == 2 | |
333 | |
334 assert graph_edit_distance(G2, G2) == 0 | |
335 assert graph_edit_distance(G2, G3) == 1 | |
336 assert graph_edit_distance(G3, G2) == 1 | |
337 | |
338 assert graph_edit_distance(G3, G3) == 0 | |
339 | |
340 def test_multidigraph(self): | |
341 G1 = nx.MultiDiGraph() | |
342 G1.add_edges_from( | |
343 ( | |
344 ("hardware", "kernel"), | |
345 ("kernel", "hardware"), | |
346 ("kernel", "userspace"), | |
347 ("userspace", "kernel"), | |
348 ) | |
349 ) | |
350 G2 = nx.MultiDiGraph() | |
351 G2.add_edges_from( | |
352 ( | |
353 ("winter", "spring"), | |
354 ("spring", "summer"), | |
355 ("summer", "autumn"), | |
356 ("autumn", "winter"), | |
357 ) | |
358 ) | |
359 | |
360 assert graph_edit_distance(G1, G2) == 5 | |
361 assert graph_edit_distance(G2, G1) == 5 | |
362 | |
363 # by https://github.com/jfbeaumont | |
364 def testCopy(self): | |
365 G = nx.Graph() | |
366 G.add_node("A", label="A") | |
367 G.add_node("B", label="B") | |
368 G.add_edge("A", "B", label="a-b") | |
369 assert ( | |
370 graph_edit_distance(G, G.copy(), node_match=nmatch, edge_match=ematch) == 0 | |
371 ) | |
372 | |
373 def testSame(self): | |
374 G1 = nx.Graph() | |
375 G1.add_node("A", label="A") | |
376 G1.add_node("B", label="B") | |
377 G1.add_edge("A", "B", label="a-b") | |
378 G2 = nx.Graph() | |
379 G2.add_node("A", label="A") | |
380 G2.add_node("B", label="B") | |
381 G2.add_edge("A", "B", label="a-b") | |
382 assert graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch) == 0 | |
383 | |
384 def testOneEdgeLabelDiff(self): | |
385 G1 = nx.Graph() | |
386 G1.add_node("A", label="A") | |
387 G1.add_node("B", label="B") | |
388 G1.add_edge("A", "B", label="a-b") | |
389 G2 = nx.Graph() | |
390 G2.add_node("A", label="A") | |
391 G2.add_node("B", label="B") | |
392 G2.add_edge("A", "B", label="bad") | |
393 assert graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch) == 1 | |
394 | |
395 def testOneNodeLabelDiff(self): | |
396 G1 = nx.Graph() | |
397 G1.add_node("A", label="A") | |
398 G1.add_node("B", label="B") | |
399 G1.add_edge("A", "B", label="a-b") | |
400 G2 = nx.Graph() | |
401 G2.add_node("A", label="Z") | |
402 G2.add_node("B", label="B") | |
403 G2.add_edge("A", "B", label="a-b") | |
404 assert graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch) == 1 | |
405 | |
406 def testOneExtraNode(self): | |
407 G1 = nx.Graph() | |
408 G1.add_node("A", label="A") | |
409 G1.add_node("B", label="B") | |
410 G1.add_edge("A", "B", label="a-b") | |
411 G2 = nx.Graph() | |
412 G2.add_node("A", label="A") | |
413 G2.add_node("B", label="B") | |
414 G2.add_edge("A", "B", label="a-b") | |
415 G2.add_node("C", label="C") | |
416 assert graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch) == 1 | |
417 | |
418 def testOneExtraEdge(self): | |
419 G1 = nx.Graph() | |
420 G1.add_node("A", label="A") | |
421 G1.add_node("B", label="B") | |
422 G1.add_node("C", label="C") | |
423 G1.add_node("C", label="C") | |
424 G1.add_edge("A", "B", label="a-b") | |
425 G2 = nx.Graph() | |
426 G2.add_node("A", label="A") | |
427 G2.add_node("B", label="B") | |
428 G2.add_node("C", label="C") | |
429 G2.add_edge("A", "B", label="a-b") | |
430 G2.add_edge("A", "C", label="a-c") | |
431 assert graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch) == 1 | |
432 | |
433 def testOneExtraNodeAndEdge(self): | |
434 G1 = nx.Graph() | |
435 G1.add_node("A", label="A") | |
436 G1.add_node("B", label="B") | |
437 G1.add_edge("A", "B", label="a-b") | |
438 G2 = nx.Graph() | |
439 G2.add_node("A", label="A") | |
440 G2.add_node("B", label="B") | |
441 G2.add_node("C", label="C") | |
442 G2.add_edge("A", "B", label="a-b") | |
443 G2.add_edge("A", "C", label="a-c") | |
444 assert graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch) == 2 | |
445 | |
446 def testGraph1(self): | |
447 G1 = getCanonical() | |
448 G2 = nx.Graph() | |
449 G2.add_node("A", label="A") | |
450 G2.add_node("B", label="B") | |
451 G2.add_node("D", label="D") | |
452 G2.add_node("E", label="E") | |
453 G2.add_edge("A", "B", label="a-b") | |
454 G2.add_edge("B", "D", label="b-d") | |
455 G2.add_edge("D", "E", label="d-e") | |
456 assert graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch) == 3 | |
457 | |
458 def testGraph2(self): | |
459 G1 = getCanonical() | |
460 G2 = nx.Graph() | |
461 G2.add_node("A", label="A") | |
462 G2.add_node("B", label="B") | |
463 G2.add_node("C", label="C") | |
464 G2.add_node("D", label="D") | |
465 G2.add_node("E", label="E") | |
466 G2.add_edge("A", "B", label="a-b") | |
467 G2.add_edge("B", "C", label="b-c") | |
468 G2.add_edge("C", "D", label="c-d") | |
469 G2.add_edge("C", "E", label="c-e") | |
470 assert graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch) == 4 | |
471 | |
472 def testGraph3(self): | |
473 G1 = getCanonical() | |
474 G2 = nx.Graph() | |
475 G2.add_node("A", label="A") | |
476 G2.add_node("B", label="B") | |
477 G2.add_node("C", label="C") | |
478 G2.add_node("D", label="D") | |
479 G2.add_node("E", label="E") | |
480 G2.add_node("F", label="F") | |
481 G2.add_node("G", label="G") | |
482 G2.add_edge("A", "C", label="a-c") | |
483 G2.add_edge("A", "D", label="a-d") | |
484 G2.add_edge("D", "E", label="d-e") | |
485 G2.add_edge("D", "F", label="d-f") | |
486 G2.add_edge("D", "G", label="d-g") | |
487 G2.add_edge("E", "B", label="e-b") | |
488 assert graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch) == 12 | |
489 | |
490 def testGraph4(self): | |
491 G1 = getCanonical() | |
492 G2 = nx.Graph() | |
493 G2.add_node("A", label="A") | |
494 G2.add_node("B", label="B") | |
495 G2.add_node("C", label="C") | |
496 G2.add_node("D", label="D") | |
497 G2.add_edge("A", "B", label="a-b") | |
498 G2.add_edge("B", "C", label="b-c") | |
499 G2.add_edge("C", "D", label="c-d") | |
500 assert graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch) == 2 | |
501 | |
502 def testGraph4_a(self): | |
503 G1 = getCanonical() | |
504 G2 = nx.Graph() | |
505 G2.add_node("A", label="A") | |
506 G2.add_node("B", label="B") | |
507 G2.add_node("C", label="C") | |
508 G2.add_node("D", label="D") | |
509 G2.add_edge("A", "B", label="a-b") | |
510 G2.add_edge("B", "C", label="b-c") | |
511 G2.add_edge("A", "D", label="a-d") | |
512 assert graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch) == 2 | |
513 | |
514 def testGraph4_b(self): | |
515 G1 = getCanonical() | |
516 G2 = nx.Graph() | |
517 G2.add_node("A", label="A") | |
518 G2.add_node("B", label="B") | |
519 G2.add_node("C", label="C") | |
520 G2.add_node("D", label="D") | |
521 G2.add_edge("A", "B", label="a-b") | |
522 G2.add_edge("B", "C", label="b-c") | |
523 G2.add_edge("B", "D", label="bad") | |
524 assert graph_edit_distance(G1, G2, node_match=nmatch, edge_match=ematch) == 1 | |
525 | |
526 def test_simrank_no_source_no_target(self): | |
527 G = nx.cycle_graph(5) | |
528 expected = { | |
529 0: { | |
530 0: 1, | |
531 1: 0.3951219505902448, | |
532 2: 0.5707317069281646, | |
533 3: 0.5707317069281646, | |
534 4: 0.3951219505902449, | |
535 }, | |
536 1: { | |
537 0: 0.3951219505902448, | |
538 1: 1, | |
539 2: 0.3951219505902449, | |
540 3: 0.5707317069281646, | |
541 4: 0.5707317069281646, | |
542 }, | |
543 2: { | |
544 0: 0.5707317069281646, | |
545 1: 0.3951219505902449, | |
546 2: 1, | |
547 3: 0.3951219505902449, | |
548 4: 0.5707317069281646, | |
549 }, | |
550 3: { | |
551 0: 0.5707317069281646, | |
552 1: 0.5707317069281646, | |
553 2: 0.3951219505902449, | |
554 3: 1, | |
555 4: 0.3951219505902449, | |
556 }, | |
557 4: { | |
558 0: 0.3951219505902449, | |
559 1: 0.5707317069281646, | |
560 2: 0.5707317069281646, | |
561 3: 0.3951219505902449, | |
562 4: 1, | |
563 }, | |
564 } | |
565 actual = nx.simrank_similarity(G) | |
566 assert expected == actual | |
567 | |
568 # For a DiGraph test, use the first graph from the paper cited in | |
569 # the docs: https://dl.acm.org/doi/pdf/10.1145/775047.775126 | |
570 G = nx.DiGraph() | |
571 G.add_node(0, label="Univ") | |
572 G.add_node(1, label="ProfA") | |
573 G.add_node(2, label="ProfB") | |
574 G.add_node(3, label="StudentA") | |
575 G.add_node(4, label="StudentB") | |
576 G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 4), (4, 2), (3, 0)]) | |
577 | |
578 expected = { | |
579 0: {0: 1, 1: 0.0, 2: 0.1323363991265798, 3: 0.0, 4: 0.03387811817640443}, | |
580 1: {0: 0.0, 1: 1, 2: 0.4135512472705618, 3: 0.0, 4: 0.10586911930126384}, | |
581 2: { | |
582 0: 0.1323363991265798, | |
583 1: 0.4135512472705618, | |
584 2: 1, | |
585 3: 0.04234764772050554, | |
586 4: 0.08822426608438655, | |
587 }, | |
588 3: {0: 0.0, 1: 0.0, 2: 0.04234764772050554, 3: 1, 4: 0.3308409978164495}, | |
589 4: { | |
590 0: 0.03387811817640443, | |
591 1: 0.10586911930126384, | |
592 2: 0.08822426608438655, | |
593 3: 0.3308409978164495, | |
594 4: 1, | |
595 }, | |
596 } | |
597 # Use the importance_factor from the paper to get the same numbers. | |
598 actual = nx.algorithms.similarity.simrank_similarity(G, importance_factor=0.8) | |
599 assert expected == actual | |
600 | |
601 def test_simrank_source_no_target(self): | |
602 G = nx.cycle_graph(5) | |
603 expected = { | |
604 0: 1, | |
605 1: 0.3951219505902448, | |
606 2: 0.5707317069281646, | |
607 3: 0.5707317069281646, | |
608 4: 0.3951219505902449, | |
609 } | |
610 actual = nx.simrank_similarity(G, source=0) | |
611 assert expected == actual | |
612 | |
613 # For a DiGraph test, use the first graph from the paper cited in | |
614 # the docs: https://dl.acm.org/doi/pdf/10.1145/775047.775126 | |
615 G = nx.DiGraph() | |
616 G.add_node(0, label="Univ") | |
617 G.add_node(1, label="ProfA") | |
618 G.add_node(2, label="ProfB") | |
619 G.add_node(3, label="StudentA") | |
620 G.add_node(4, label="StudentB") | |
621 G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 4), (4, 2), (3, 0)]) | |
622 | |
623 expected = {0: 1, 1: 0.0, 2: 0.1323363991265798, 3: 0.0, 4: 0.03387811817640443} | |
624 # Use the importance_factor from the paper to get the same numbers. | |
625 actual = nx.algorithms.similarity.simrank_similarity( | |
626 G, importance_factor=0.8, source=0 | |
627 ) | |
628 assert expected == actual | |
629 | |
630 def test_simrank_source_and_target(self): | |
631 G = nx.cycle_graph(5) | |
632 expected = 1 | |
633 actual = nx.simrank_similarity(G, source=0, target=0) | |
634 | |
635 # For a DiGraph test, use the first graph from the paper cited in | |
636 # the docs: https://dl.acm.org/doi/pdf/10.1145/775047.775126 | |
637 G = nx.DiGraph() | |
638 G.add_node(0, label="Univ") | |
639 G.add_node(1, label="ProfA") | |
640 G.add_node(2, label="ProfB") | |
641 G.add_node(3, label="StudentA") | |
642 G.add_node(4, label="StudentB") | |
643 G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 4), (4, 2), (3, 0)]) | |
644 | |
645 expected = 0.1323363991265798 | |
646 # Use the importance_factor from the paper to get the same numbers. | |
647 # Use the pair (0,2) because (0,0) and (0,1) have trivial results. | |
648 actual = nx.algorithms.similarity.simrank_similarity( | |
649 G, importance_factor=0.8, source=0, target=2 | |
650 ) | |
651 assert expected == actual | |
652 | |
653 def test_simrank_numpy_no_source_no_target(self): | |
654 G = nx.cycle_graph(5) | |
655 expected = numpy.array( | |
656 [ | |
657 [ | |
658 1.0, | |
659 0.3947180735764555, | |
660 0.570482097206368, | |
661 0.570482097206368, | |
662 0.3947180735764555, | |
663 ], | |
664 [ | |
665 0.3947180735764555, | |
666 1.0, | |
667 0.3947180735764555, | |
668 0.570482097206368, | |
669 0.570482097206368, | |
670 ], | |
671 [ | |
672 0.570482097206368, | |
673 0.3947180735764555, | |
674 1.0, | |
675 0.3947180735764555, | |
676 0.570482097206368, | |
677 ], | |
678 [ | |
679 0.570482097206368, | |
680 0.570482097206368, | |
681 0.3947180735764555, | |
682 1.0, | |
683 0.3947180735764555, | |
684 ], | |
685 [ | |
686 0.3947180735764555, | |
687 0.570482097206368, | |
688 0.570482097206368, | |
689 0.3947180735764555, | |
690 1.0, | |
691 ], | |
692 ] | |
693 ) | |
694 actual = nx.simrank_similarity_numpy(G) | |
695 numpy.testing.assert_allclose(expected, actual, atol=1e-7) | |
696 | |
697 def test_simrank_numpy_source_no_target(self): | |
698 G = nx.cycle_graph(5) | |
699 expected = numpy.array( | |
700 [ | |
701 1.0, | |
702 0.3947180735764555, | |
703 0.570482097206368, | |
704 0.570482097206368, | |
705 0.3947180735764555, | |
706 ] | |
707 ) | |
708 actual = nx.simrank_similarity_numpy(G, source=0) | |
709 numpy.testing.assert_allclose(expected, actual, atol=1e-7) | |
710 | |
711 def test_simrank_numpy_source_and_target(self): | |
712 G = nx.cycle_graph(5) | |
713 expected = 1.0 | |
714 actual = nx.simrank_similarity_numpy(G, source=0, target=0) | |
715 numpy.testing.assert_allclose(expected, actual, atol=1e-7) |