Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/shortest_paths/tests/test_astar.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 | |
3 import networkx as nx | |
4 from networkx.utils import pairwise | |
5 | |
6 | |
7 class TestAStar: | |
8 @classmethod | |
9 def setup_class(cls): | |
10 edges = [ | |
11 ("s", "u", 10), | |
12 ("s", "x", 5), | |
13 ("u", "v", 1), | |
14 ("u", "x", 2), | |
15 ("v", "y", 1), | |
16 ("x", "u", 3), | |
17 ("x", "v", 5), | |
18 ("x", "y", 2), | |
19 ("y", "s", 7), | |
20 ("y", "v", 6), | |
21 ] | |
22 cls.XG = nx.DiGraph() | |
23 cls.XG.add_weighted_edges_from(edges) | |
24 | |
25 def test_multiple_optimal_paths(self): | |
26 """Tests that A* algorithm finds any of multiple optimal paths""" | |
27 heuristic_values = {"a": 1.35, "b": 1.18, "c": 0.67, "d": 0} | |
28 | |
29 def h(u, v): | |
30 return heuristic_values[u] | |
31 | |
32 graph = nx.Graph() | |
33 points = ["a", "b", "c", "d"] | |
34 edges = [("a", "b", 0.18), ("a", "c", 0.68), ("b", "c", 0.50), ("c", "d", 0.67)] | |
35 | |
36 graph.add_nodes_from(points) | |
37 graph.add_weighted_edges_from(edges) | |
38 | |
39 path1 = ["a", "c", "d"] | |
40 path2 = ["a", "b", "c", "d"] | |
41 assert nx.astar_path(graph, "a", "d", h) in (path1, path2) | |
42 | |
43 def test_astar_directed(self): | |
44 assert nx.astar_path(self.XG, "s", "v") == ["s", "x", "u", "v"] | |
45 assert nx.astar_path_length(self.XG, "s", "v") == 9 | |
46 | |
47 def test_astar_multigraph(self): | |
48 G = nx.MultiDiGraph(self.XG) | |
49 G.add_weighted_edges_from((u, v, 1000) for (u, v) in list(G.edges())) | |
50 assert nx.astar_path(G, "s", "v") == ["s", "x", "u", "v"] | |
51 assert nx.astar_path_length(G, "s", "v") == 9 | |
52 | |
53 def test_astar_undirected(self): | |
54 GG = self.XG.to_undirected() | |
55 # make sure we get lower weight | |
56 # to_undirected might choose either edge with weight 2 or weight 3 | |
57 GG["u"]["x"]["weight"] = 2 | |
58 GG["y"]["v"]["weight"] = 2 | |
59 assert nx.astar_path(GG, "s", "v") == ["s", "x", "u", "v"] | |
60 assert nx.astar_path_length(GG, "s", "v") == 8 | |
61 | |
62 def test_astar_directed2(self): | |
63 XG2 = nx.DiGraph() | |
64 edges = [ | |
65 (1, 4, 1), | |
66 (4, 5, 1), | |
67 (5, 6, 1), | |
68 (6, 3, 1), | |
69 (1, 3, 50), | |
70 (1, 2, 100), | |
71 (2, 3, 100), | |
72 ] | |
73 XG2.add_weighted_edges_from(edges) | |
74 assert nx.astar_path(XG2, 1, 3) == [1, 4, 5, 6, 3] | |
75 | |
76 def test_astar_undirected2(self): | |
77 XG3 = nx.Graph() | |
78 edges = [(0, 1, 2), (1, 2, 12), (2, 3, 1), (3, 4, 5), (4, 5, 1), (5, 0, 10)] | |
79 XG3.add_weighted_edges_from(edges) | |
80 assert nx.astar_path(XG3, 0, 3) == [0, 1, 2, 3] | |
81 assert nx.astar_path_length(XG3, 0, 3) == 15 | |
82 | |
83 def test_astar_undirected3(self): | |
84 XG4 = nx.Graph() | |
85 edges = [ | |
86 (0, 1, 2), | |
87 (1, 2, 2), | |
88 (2, 3, 1), | |
89 (3, 4, 1), | |
90 (4, 5, 1), | |
91 (5, 6, 1), | |
92 (6, 7, 1), | |
93 (7, 0, 1), | |
94 ] | |
95 XG4.add_weighted_edges_from(edges) | |
96 assert nx.astar_path(XG4, 0, 2) == [0, 1, 2] | |
97 assert nx.astar_path_length(XG4, 0, 2) == 4 | |
98 | |
99 """ Tests that A* finds correct path when multiple paths exist | |
100 and the best one is not expanded first (GH issue #3464) | |
101 """ | |
102 | |
103 def test_astar_directed3(self): | |
104 heuristic_values = {"n5": 36, "n2": 4, "n1": 0, "n0": 0} | |
105 | |
106 def h(u, v): | |
107 return heuristic_values[u] | |
108 | |
109 edges = [("n5", "n1", 11), ("n5", "n2", 9), ("n2", "n1", 1), ("n1", "n0", 32)] | |
110 graph = nx.DiGraph() | |
111 graph.add_weighted_edges_from(edges) | |
112 answer = ["n5", "n2", "n1", "n0"] | |
113 assert nx.astar_path(graph, "n5", "n0", h) == answer | |
114 | |
115 """ Tests that that parent is not wrongly overridden when a | |
116 node is re-explored multiple times. | |
117 """ | |
118 | |
119 def test_astar_directed4(self): | |
120 edges = [ | |
121 ("a", "b", 1), | |
122 ("a", "c", 1), | |
123 ("b", "d", 2), | |
124 ("c", "d", 1), | |
125 ("d", "e", 1), | |
126 ] | |
127 graph = nx.DiGraph() | |
128 graph.add_weighted_edges_from(edges) | |
129 assert nx.astar_path(graph, "a", "e") == ["a", "c", "d", "e"] | |
130 | |
131 # >>> MXG4=NX.MultiGraph(XG4) | |
132 # >>> MXG4.add_edge(0,1,3) | |
133 # >>> NX.dijkstra_path(MXG4,0,2) | |
134 # [0, 1, 2] | |
135 | |
136 def test_astar_w1(self): | |
137 G = nx.DiGraph() | |
138 G.add_edges_from( | |
139 [ | |
140 ("s", "u"), | |
141 ("s", "x"), | |
142 ("u", "v"), | |
143 ("u", "x"), | |
144 ("v", "y"), | |
145 ("x", "u"), | |
146 ("x", "w"), | |
147 ("w", "v"), | |
148 ("x", "y"), | |
149 ("y", "s"), | |
150 ("y", "v"), | |
151 ] | |
152 ) | |
153 assert nx.astar_path(G, "s", "v") == ["s", "u", "v"] | |
154 assert nx.astar_path_length(G, "s", "v") == 2 | |
155 | |
156 def test_astar_nopath(self): | |
157 with pytest.raises(nx.NodeNotFound): | |
158 nx.astar_path(self.XG, "s", "moon") | |
159 | |
160 def test_cycle(self): | |
161 C = nx.cycle_graph(7) | |
162 assert nx.astar_path(C, 0, 3) == [0, 1, 2, 3] | |
163 assert nx.dijkstra_path(C, 0, 4) == [0, 6, 5, 4] | |
164 | |
165 def test_unorderable_nodes(self): | |
166 """Tests that A* accommodates nodes that are not orderable. | |
167 | |
168 For more information, see issue #554. | |
169 | |
170 """ | |
171 # Create the cycle graph on four nodes, with nodes represented | |
172 # as (unorderable) Python objects. | |
173 nodes = [object() for n in range(4)] | |
174 G = nx.Graph() | |
175 G.add_edges_from(pairwise(nodes, cyclic=True)) | |
176 path = nx.astar_path(G, nodes[0], nodes[2]) | |
177 assert len(path) == 3 |