### comparison env/lib/python3.9/site-packages/networkx/algorithms/shortest_paths/tests/test_astar.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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()
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
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 ]
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)]
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 ]
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()
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()
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()
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()