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