Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_wiener.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 """Unit tests for the :mod:`networkx.algorithms.wiener` module.""" | |
2 | |
3 | |
4 from networkx import complete_graph | |
5 from networkx import DiGraph | |
6 from networkx import empty_graph | |
7 from networkx import path_graph | |
8 from networkx import wiener_index | |
9 | |
10 | |
11 class TestWienerIndex: | |
12 """Unit tests for computing the Wiener index of a graph.""" | |
13 | |
14 def test_disconnected_graph(self): | |
15 """Tests that the Wiener index of a disconnected graph is | |
16 positive infinity. | |
17 | |
18 """ | |
19 assert wiener_index(empty_graph(2)) == float("inf") | |
20 | |
21 def test_directed(self): | |
22 """Tests that each pair of nodes in the directed graph is | |
23 counted once when computing the Wiener index. | |
24 | |
25 """ | |
26 G = complete_graph(3) | |
27 H = DiGraph(G) | |
28 assert (2 * wiener_index(G)) == wiener_index(H) | |
29 | |
30 def test_complete_graph(self): | |
31 """Tests that the Wiener index of the complete graph is simply | |
32 the number of edges. | |
33 | |
34 """ | |
35 n = 10 | |
36 G = complete_graph(n) | |
37 assert wiener_index(G) == (n * (n - 1) / 2) | |
38 | |
39 def test_path_graph(self): | |
40 """Tests that the Wiener index of the path graph is correctly | |
41 computed. | |
42 | |
43 """ | |
44 # In P_n, there are n - 1 pairs of vertices at distance one, n - | |
45 # 2 pairs at distance two, n - 3 at distance three, ..., 1 at | |
46 # distance n - 1, so the Wiener index should be | |
47 # | |
48 # 1 * (n - 1) + 2 * (n - 2) + ... + (n - 2) * 2 + (n - 1) * 1 | |
49 # | |
50 # For example, in P_5, | |
51 # | |
52 # 1 * 4 + 2 * 3 + 3 * 2 + 4 * 1 = 2 (1 * 4 + 2 * 3) | |
53 # | |
54 # and in P_6, | |
55 # | |
56 # 1 * 5 + 2 * 4 + 3 * 3 + 4 * 2 + 5 * 1 = 2 (1 * 5 + 2 * 4) + 3 * 3 | |
57 # | |
58 # assuming n is *odd*, this gives the formula | |
59 # | |
60 # 2 \sum_{i = 1}^{(n - 1) / 2} [i * (n - i)] | |
61 # | |
62 # assuming n is *even*, this gives the formula | |
63 # | |
64 # 2 \sum_{i = 1}^{n / 2} [i * (n - i)] - (n / 2) ** 2 | |
65 # | |
66 n = 9 | |
67 G = path_graph(n) | |
68 expected = 2 * sum(i * (n - i) for i in range(1, (n // 2) + 1)) | |
69 actual = wiener_index(G) | |
70 assert expected == actual |