1 # This file is part of NIT (http://www.nitlanguage.org).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 module test_a_star
is test
28 fun case_simple
is test
do
29 var graph
= new Graph[NamedNode, Link]
31 var na
= new NamedNode(graph
, "a")
32 var nb
= new NamedNode(graph
, "b")
33 var nc
= new NamedNode(graph
, "c")
34 var nd
= new NamedNode(graph
, "d")
35 var ne
= new NamedNode(graph
, "e")
37 var lab
= new Link(graph
, na
, nb
)
38 var lac
= new Link(graph
, na
, nc
)
39 var lbd
= new Link(graph
, nb
, nd
)
40 var lcd
= new Link(graph
, nc
, nd
)
41 var lde
= new Link(graph
, nd
, ne
)
43 var context
= new ConstantPathContext(graph
)
45 var path
= na
.path_to
(ne
, 100, context
)
46 assert path_to_string
(path
) == "c, d, e"
55 fun case_failed
is test
do
56 var graph
= new Graph[NamedNode,Link]
58 var na
= new NamedNode(graph
, "a")
59 var nb
= new NamedNode(graph
, "b")
60 var nc
= new NamedNode(graph
, "c")
61 var nd
= new NamedNode(graph
, "d")
62 var ne
= new NamedNode(graph
, "e")
64 var lab
= new Link(graph
, na
, nb
)
65 var lac
= new Link(graph
, na
, nc
)
66 var lbd
= new Link(graph
, nb
, nd
)
67 var lcd
= new Link(graph
, nc
, nd
)
69 var context
= new ConstantPathContext(graph
)
71 var path
= na
.path_to
(ne
, 100, context
)
72 assert path_to_string
(path
) == null
83 fun case_weighted
is test
do
84 var graph
= new Graph[NamedNode,WeightedLink]
86 var na
= new NamedNode(graph
, "a")
87 var nb
= new NamedNode(graph
, "b")
88 var nc
= new NamedNode(graph
, "c")
89 var nd
= new NamedNode(graph
, "d")
90 var ne
= new NamedNode(graph
, "e")
92 var lab
= new WeightedLink(graph
, na
, nb
, 2)
93 var lac
= new WeightedLink(graph
, na
, nc
, 3)
94 var lbd
= new WeightedLink(graph
, nb
, nd
, 1)
95 var lcd
= new WeightedLink(graph
, nc
, nd
, 3)
96 var lde
= new WeightedLink(graph
, nd
, ne
, 8)
98 var context
= new WeightedPathContext(graph
)
100 var path
= na
.path_to
(ne
, 100, context
)
101 assert path_to_string
(path
) == "b, d, e"
112 fun case_weighted_too_long
is test
do
113 var graph
= new Graph[NamedNode,WeightedLink]
115 var na
= new NamedNode(graph
, "a")
116 var nb
= new NamedNode(graph
, "b")
117 var nc
= new NamedNode(graph
, "c")
118 var nd
= new NamedNode(graph
, "d")
119 var ne
= new NamedNode(graph
, "e")
121 var lab
= new WeightedLink(graph
, na
, nb
, 2)
122 var lac
= new WeightedLink(graph
, na
, nc
, 3)
123 var lbd
= new WeightedLink(graph
, nb
, nd
, 1)
124 var lcd
= new WeightedLink(graph
, nc
, nd
, 3)
125 var lde
= new WeightedLink(graph
, nd
, ne
, 8)
127 var context
= new WeightedPathContext(graph
)
129 var path
= na
.path_to
(ne
, 5, context
)
130 assert path_to_string
(path
) == null
133 # "Big" weighted graph
136 # a -2- b -1- f -1- g
140 # c -3- d -8- e -2- h -2- i -3- j
142 fun case_weighted_big
is test
do
143 var graph
= new Graph[NamedNode,WeightedLink]
145 var na
= new NamedNode(graph
, "a")
146 var nb
= new NamedNode(graph
, "b")
147 var nc
= new NamedNode(graph
, "c")
148 var nd
= new NamedNode(graph
, "d")
149 var ne
= new NamedNode(graph
, "e")
150 var nf
= new NamedNode(graph
, "f")
151 var ng
= new NamedNode(graph
, "g")
152 var nh
= new NamedNode(graph
, "h")
153 var ni
= new NamedNode(graph
, "i")
154 var nj
= new NamedNode(graph
, "j")
156 var lab
= new WeightedLink(graph
, na
, nb
, 2)
157 var lac
= new WeightedLink(graph
, na
, nc
, 3)
158 var lbd
= new WeightedLink(graph
, nb
, nd
, 1)
159 var lcd
= new WeightedLink(graph
, nc
, nd
, 3)
160 var lde
= new WeightedLink(graph
, nd
, ne
, 8)
161 var lbf
= new WeightedLink(graph
, nb
, nf
, 1)
162 var lfg
= new WeightedLink(graph
, nf
, ng
, 1)
163 var leh
= new WeightedLink(graph
, ne
, nh
, 2)
164 var lhi
= new WeightedLink(graph
, nh
, ni
, 2)
165 var lij
= new WeightedLink(graph
, ni
, nj
, 3)
166 var lfh
= new WeightedLink(graph
, nf
, nh
, 4)
167 var lgh
= new WeightedLink(graph
, ng
, nh
, 1)
169 var context
= new WeightedPathContext(graph
)
171 var path
= na
.path_to
(nj
, 100, context
)
172 assert path_to_string
(path
) == "b, f, g, h, i, j"
175 # Double-edge graph with coordinates on nodes
182 fun cases_with_positions_and_heuristic
is test
do
183 var graph
= new Graph[PositionedNamedNode,PositionedLink]
185 var na
= new PositionedNamedNode(graph
, "a", 0, 0)
186 var nb
= new PositionedNamedNode(graph
, "b", 2, 0)
187 var nc
= new PositionedNamedNode(graph
, "c", 2, 2)
188 var nd
= new PositionedNamedNode(graph
, "d", 5, 0)
189 var ne
= new PositionedNamedNode(graph
, "e", 8, 0)
190 var nf
= new PositionedNamedNode(graph
, "f", 8, 2)
192 var lab
= new PositionedLink(graph
, na
, nb
)
193 var lac
= new PositionedLink(graph
, na
, nc
)
194 var lbd
= new PositionedLink(graph
, nb
, nd
)
195 var lde
= new PositionedLink(graph
, nd
, ne
)
196 var lef
= new PositionedLink(graph
, ne
, nf
)
197 var lcf
= new PositionedLink(graph
, nc
, nf
)
200 var lba
= new PositionedLink(graph
, nb
, na
)
201 var lca
= new PositionedLink(graph
, nc
, na
)
202 var ldb
= new PositionedLink(graph
, nd
, nb
)
203 var led
= new PositionedLink(graph
, ne
, nd
)
204 var lfe
= new PositionedLink(graph
, nf
, ne
)
205 var lfc
= new PositionedLink(graph
, nf
, nc
)
207 var context
= new PositionPathContext(graph
)
209 assert path_to_string
(na
.path_to
(nf
, 100, context
)) == "c, f"
210 assert path_to_string
(nf
.path_to
(na
, 100, context
)) == "c, a"
211 assert path_to_string
(nc
.path_to
(ne
, 100, context
)) == "f, e"
212 assert path_to_string
(nd
.path_to
(nc
, 100, context
)) == "b, a, c"
215 fun path_to_string
(path
: nullable AStarPath[NamedNode]): nullable String do
219 var names
= new Array[String]
220 while not path
.at_end_of_path
do
224 return names
.join
(", ")
230 # redef fun debug_a_star do return true
233 # Simple node with a name
237 redef type N
: NamedNode
241 redef fun to_s
do return "node:{name}"
244 # Node with a name and position
245 class PositionedNamedNode
248 redef type N
: PositionedNamedNode
253 redef fun to_s
do return "{super}-at-({x},{y})"
255 fun dist_with
(o
: PositionedNamedNode): Int
259 var d2
= dx
*dx
+ dy
*dy
264 # Link for nodes with a position
268 redef type N
: PositionedNamedNode
271 # Context for a graph with positions
272 class PositionPathContext
275 redef type N
: PositionedNamedNode
276 redef type L
: PositionedLink
281 for l
in graph
.links
do
282 var this_cost
= cost
(l
)
283 if this_cost
> worst_cost
then worst_cost
= this_cost
287 redef var worst_cost
= 0
289 redef fun cost
(link
) do return link
.from
.dist_with
(link
.to
)
291 redef fun is_blocked
(link
) do return false
293 redef fun heuristic_cost
(a
, b
)
295 var cost
= a
.dist_with
(b
)
296 if cost
> 100 then return 100
300 redef fun worst_heuristic_cost
do return 100