Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_sparsifiers.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 sparsifier computation functions.""" | |
2 import pytest | |
3 import networkx as nx | |
4 from networkx.utils import py_random_state | |
5 | |
6 | |
7 _seed = 2 | |
8 | |
9 | |
10 def _test_spanner(G, spanner, stretch, weight=None): | |
11 """Test whether a spanner is valid. | |
12 | |
13 This function tests whether the given spanner is a subgraph of the | |
14 given graph G with the same node set. It also tests for all shortest | |
15 paths whether they adhere to the given stretch. | |
16 | |
17 Parameters | |
18 ---------- | |
19 G : NetworkX graph | |
20 The original graph for which the spanner was constructed. | |
21 | |
22 spanner : NetworkX graph | |
23 The spanner to be tested. | |
24 | |
25 stretch : float | |
26 The proclaimed stretch of the spanner. | |
27 | |
28 weight : object | |
29 The edge attribute to use as distance. | |
30 """ | |
31 # check node set | |
32 assert set(G.nodes()) == set(spanner.nodes()) | |
33 | |
34 # check edge set and weights | |
35 for u, v in spanner.edges(): | |
36 assert G.has_edge(u, v) | |
37 if weight: | |
38 assert spanner[u][v][weight] == G[u][v][weight] | |
39 | |
40 # check connectivity and stretch | |
41 original_length = dict(nx.shortest_path_length(G, weight=weight)) | |
42 spanner_length = dict(nx.shortest_path_length(spanner, weight=weight)) | |
43 for u in G.nodes(): | |
44 for v in G.nodes(): | |
45 if u in original_length and v in original_length[u]: | |
46 assert spanner_length[u][v] <= stretch * original_length[u][v] | |
47 | |
48 | |
49 @py_random_state(1) | |
50 def _assign_random_weights(G, seed=None): | |
51 """Assigns random weights to the edges of a graph. | |
52 | |
53 Parameters | |
54 ---------- | |
55 | |
56 G : NetworkX graph | |
57 The original graph for which the spanner was constructed. | |
58 | |
59 seed : integer, random_state, or None (default) | |
60 Indicator of random number generation state. | |
61 See :ref:`Randomness<randomness>`. | |
62 """ | |
63 for u, v in G.edges(): | |
64 G[u][v]["weight"] = seed.random() | |
65 | |
66 | |
67 def test_spanner_trivial(): | |
68 """Test a trivial spanner with stretch 1.""" | |
69 G = nx.complete_graph(20) | |
70 spanner = nx.spanner(G, 1, seed=_seed) | |
71 | |
72 for u, v in G.edges: | |
73 assert spanner.has_edge(u, v) | |
74 | |
75 | |
76 def test_spanner_unweighted_complete_graph(): | |
77 """Test spanner construction on a complete unweighted graph.""" | |
78 G = nx.complete_graph(20) | |
79 | |
80 spanner = nx.spanner(G, 4, seed=_seed) | |
81 _test_spanner(G, spanner, 4) | |
82 | |
83 spanner = nx.spanner(G, 10, seed=_seed) | |
84 _test_spanner(G, spanner, 10) | |
85 | |
86 | |
87 def test_spanner_weighted_complete_graph(): | |
88 """Test spanner construction on a complete weighted graph.""" | |
89 G = nx.complete_graph(20) | |
90 _assign_random_weights(G, seed=_seed) | |
91 | |
92 spanner = nx.spanner(G, 4, weight="weight", seed=_seed) | |
93 _test_spanner(G, spanner, 4, weight="weight") | |
94 | |
95 spanner = nx.spanner(G, 10, weight="weight", seed=_seed) | |
96 _test_spanner(G, spanner, 10, weight="weight") | |
97 | |
98 | |
99 def test_spanner_unweighted_gnp_graph(): | |
100 """Test spanner construction on an unweighted gnp graph.""" | |
101 G = nx.gnp_random_graph(20, 0.4, seed=_seed) | |
102 | |
103 spanner = nx.spanner(G, 4, seed=_seed) | |
104 _test_spanner(G, spanner, 4) | |
105 | |
106 spanner = nx.spanner(G, 10, seed=_seed) | |
107 _test_spanner(G, spanner, 10) | |
108 | |
109 | |
110 def test_spanner_weighted_gnp_graph(): | |
111 """Test spanner construction on an weighted gnp graph.""" | |
112 G = nx.gnp_random_graph(20, 0.4, seed=_seed) | |
113 _assign_random_weights(G, seed=_seed) | |
114 | |
115 spanner = nx.spanner(G, 4, weight="weight", seed=_seed) | |
116 _test_spanner(G, spanner, 4, weight="weight") | |
117 | |
118 spanner = nx.spanner(G, 10, weight="weight", seed=_seed) | |
119 _test_spanner(G, spanner, 10, weight="weight") | |
120 | |
121 | |
122 def test_spanner_unweighted_disconnected_graph(): | |
123 """Test spanner construction on a disconnected graph.""" | |
124 G = nx.disjoint_union(nx.complete_graph(10), nx.complete_graph(10)) | |
125 | |
126 spanner = nx.spanner(G, 4, seed=_seed) | |
127 _test_spanner(G, spanner, 4) | |
128 | |
129 spanner = nx.spanner(G, 10, seed=_seed) | |
130 _test_spanner(G, spanner, 10) | |
131 | |
132 | |
133 def test_spanner_invalid_stretch(): | |
134 """Check whether an invalid stretch is caught.""" | |
135 with pytest.raises(ValueError): | |
136 G = nx.empty_graph() | |
137 nx.spanner(G, 0) |