Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_similarity.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 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)