Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/shortest_paths/tests/test_dense.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 import networkx as nx | |
3 | |
4 | |
5 class TestFloyd: | |
6 @classmethod | |
7 def setup_class(cls): | |
8 pass | |
9 | |
10 def test_floyd_warshall_predecessor_and_distance(self): | |
11 XG = nx.DiGraph() | |
12 XG.add_weighted_edges_from( | |
13 [ | |
14 ("s", "u", 10), | |
15 ("s", "x", 5), | |
16 ("u", "v", 1), | |
17 ("u", "x", 2), | |
18 ("v", "y", 1), | |
19 ("x", "u", 3), | |
20 ("x", "v", 5), | |
21 ("x", "y", 2), | |
22 ("y", "s", 7), | |
23 ("y", "v", 6), | |
24 ] | |
25 ) | |
26 path, dist = nx.floyd_warshall_predecessor_and_distance(XG) | |
27 assert dist["s"]["v"] == 9 | |
28 assert path["s"]["v"] == "u" | |
29 assert dist == { | |
30 "y": {"y": 0, "x": 12, "s": 7, "u": 15, "v": 6}, | |
31 "x": {"y": 2, "x": 0, "s": 9, "u": 3, "v": 4}, | |
32 "s": {"y": 7, "x": 5, "s": 0, "u": 8, "v": 9}, | |
33 "u": {"y": 2, "x": 2, "s": 9, "u": 0, "v": 1}, | |
34 "v": {"y": 1, "x": 13, "s": 8, "u": 16, "v": 0}, | |
35 } | |
36 | |
37 GG = XG.to_undirected() | |
38 # make sure we get lower weight | |
39 # to_undirected might choose either edge with weight 2 or weight 3 | |
40 GG["u"]["x"]["weight"] = 2 | |
41 path, dist = nx.floyd_warshall_predecessor_and_distance(GG) | |
42 assert dist["s"]["v"] == 8 | |
43 # skip this test, could be alternate path s-u-v | |
44 # assert_equal(path['s']['v'],'y') | |
45 | |
46 G = nx.DiGraph() # no weights | |
47 G.add_edges_from( | |
48 [ | |
49 ("s", "u"), | |
50 ("s", "x"), | |
51 ("u", "v"), | |
52 ("u", "x"), | |
53 ("v", "y"), | |
54 ("x", "u"), | |
55 ("x", "v"), | |
56 ("x", "y"), | |
57 ("y", "s"), | |
58 ("y", "v"), | |
59 ] | |
60 ) | |
61 path, dist = nx.floyd_warshall_predecessor_and_distance(G) | |
62 assert dist["s"]["v"] == 2 | |
63 # skip this test, could be alternate path s-u-v | |
64 # assert_equal(path['s']['v'],'x') | |
65 | |
66 # alternate interface | |
67 dist = nx.floyd_warshall(G) | |
68 assert dist["s"]["v"] == 2 | |
69 | |
70 # floyd_warshall_predecessor_and_distance returns | |
71 # dicts-of-defautdicts | |
72 # make sure we don't get empty dictionary | |
73 XG = nx.DiGraph() | |
74 XG.add_weighted_edges_from( | |
75 [("v", "x", 5.0), ("y", "x", 5.0), ("v", "y", 6.0), ("x", "u", 2.0)] | |
76 ) | |
77 path, dist = nx.floyd_warshall_predecessor_and_distance(XG) | |
78 inf = float("inf") | |
79 assert dist == { | |
80 "v": {"v": 0, "x": 5.0, "y": 6.0, "u": 7.0}, | |
81 "x": {"x": 0, "u": 2.0, "v": inf, "y": inf}, | |
82 "y": {"y": 0, "x": 5.0, "v": inf, "u": 7.0}, | |
83 "u": {"u": 0, "v": inf, "x": inf, "y": inf}, | |
84 } | |
85 assert path == { | |
86 "v": {"x": "v", "y": "v", "u": "x"}, | |
87 "x": {"u": "x"}, | |
88 "y": {"x": "y", "u": "x"}, | |
89 } | |
90 | |
91 def test_reconstruct_path(self): | |
92 with pytest.raises(KeyError): | |
93 XG = nx.DiGraph() | |
94 XG.add_weighted_edges_from( | |
95 [ | |
96 ("s", "u", 10), | |
97 ("s", "x", 5), | |
98 ("u", "v", 1), | |
99 ("u", "x", 2), | |
100 ("v", "y", 1), | |
101 ("x", "u", 3), | |
102 ("x", "v", 5), | |
103 ("x", "y", 2), | |
104 ("y", "s", 7), | |
105 ("y", "v", 6), | |
106 ] | |
107 ) | |
108 predecessors, _ = nx.floyd_warshall_predecessor_and_distance(XG) | |
109 | |
110 path = nx.reconstruct_path("s", "v", predecessors) | |
111 assert path == ["s", "x", "u", "v"] | |
112 | |
113 path = nx.reconstruct_path("s", "s", predecessors) | |
114 assert path == [] | |
115 | |
116 # this part raises the keyError | |
117 nx.reconstruct_path("1", "2", predecessors) | |
118 | |
119 def test_cycle(self): | |
120 path, dist = nx.floyd_warshall_predecessor_and_distance(nx.cycle_graph(7)) | |
121 assert dist[0][3] == 3 | |
122 assert path[0][3] == 2 | |
123 assert dist[0][4] == 3 | |
124 | |
125 def test_weighted(self): | |
126 XG3 = nx.Graph() | |
127 XG3.add_weighted_edges_from( | |
128 [[0, 1, 2], [1, 2, 12], [2, 3, 1], [3, 4, 5], [4, 5, 1], [5, 0, 10]] | |
129 ) | |
130 path, dist = nx.floyd_warshall_predecessor_and_distance(XG3) | |
131 assert dist[0][3] == 15 | |
132 assert path[0][3] == 2 | |
133 | |
134 def test_weighted2(self): | |
135 XG4 = nx.Graph() | |
136 XG4.add_weighted_edges_from( | |
137 [ | |
138 [0, 1, 2], | |
139 [1, 2, 2], | |
140 [2, 3, 1], | |
141 [3, 4, 1], | |
142 [4, 5, 1], | |
143 [5, 6, 1], | |
144 [6, 7, 1], | |
145 [7, 0, 1], | |
146 ] | |
147 ) | |
148 path, dist = nx.floyd_warshall_predecessor_and_distance(XG4) | |
149 assert dist[0][2] == 4 | |
150 assert path[0][2] == 1 | |
151 | |
152 def test_weight_parameter(self): | |
153 XG4 = nx.Graph() | |
154 XG4.add_edges_from( | |
155 [ | |
156 (0, 1, {"heavy": 2}), | |
157 (1, 2, {"heavy": 2}), | |
158 (2, 3, {"heavy": 1}), | |
159 (3, 4, {"heavy": 1}), | |
160 (4, 5, {"heavy": 1}), | |
161 (5, 6, {"heavy": 1}), | |
162 (6, 7, {"heavy": 1}), | |
163 (7, 0, {"heavy": 1}), | |
164 ] | |
165 ) | |
166 path, dist = nx.floyd_warshall_predecessor_and_distance(XG4, weight="heavy") | |
167 assert dist[0][2] == 4 | |
168 assert path[0][2] == 1 | |
169 | |
170 def test_zero_distance(self): | |
171 XG = nx.DiGraph() | |
172 XG.add_weighted_edges_from( | |
173 [ | |
174 ("s", "u", 10), | |
175 ("s", "x", 5), | |
176 ("u", "v", 1), | |
177 ("u", "x", 2), | |
178 ("v", "y", 1), | |
179 ("x", "u", 3), | |
180 ("x", "v", 5), | |
181 ("x", "y", 2), | |
182 ("y", "s", 7), | |
183 ("y", "v", 6), | |
184 ] | |
185 ) | |
186 path, dist = nx.floyd_warshall_predecessor_and_distance(XG) | |
187 | |
188 for u in XG: | |
189 assert dist[u][u] == 0 | |
190 | |
191 GG = XG.to_undirected() | |
192 # make sure we get lower weight | |
193 # to_undirected might choose either edge with weight 2 or weight 3 | |
194 GG["u"]["x"]["weight"] = 2 | |
195 path, dist = nx.floyd_warshall_predecessor_and_distance(GG) | |
196 | |
197 for u in GG: | |
198 dist[u][u] = 0 | |
199 | |
200 def test_zero_weight(self): | |
201 G = nx.DiGraph() | |
202 edges = [(1, 2, -2), (2, 3, -4), (1, 5, 1), (5, 4, 0), (4, 3, -5), (2, 5, -7)] | |
203 G.add_weighted_edges_from(edges) | |
204 dist = nx.floyd_warshall(G) | |
205 assert dist[1][3] == -14 | |
206 | |
207 G = nx.MultiDiGraph() | |
208 edges.append((2, 5, -7)) | |
209 G.add_weighted_edges_from(edges) | |
210 dist = nx.floyd_warshall(G) | |
211 assert dist[1][3] == -14 |