6 # redef fun debug_a_star do return true
9 # Simple node with a name
13 redef type N
: NamedNode
17 init(graph
: Graph[N
, Link], name
: String)
23 redef fun to_s
do return "node:{name}"
26 # Node with a name and position
27 class PositionedNamedNode
30 redef type N
: PositionedNamedNode
35 init(graph
: Graph[N
, Link], name
: String, x
, y
: Int)
43 redef fun to_s
do return "{super}-at-({x},{y})"
45 fun dist_with
(o
: PositionedNamedNode): Int
49 var d2
= dx
*dx
+ dy
*dy
54 # Link for nodes with a position
58 redef type N
: PositionedNamedNode
61 # Context for a graph with positions
62 class PositionPathContext
65 redef type N
: PositionedNamedNode
66 redef type L
: PositionedLink
68 init(graph
: Graph[N
,L
])
72 for l
in graph
.links
do
73 var this_cost
= cost
(l
)
74 if this_cost
> worst_cost
then worst_cost
= this_cost
78 redef var worst_cost
= 0
80 redef fun cost
(link
) do return link
.from
.dist_with
(link
.to
)
82 redef fun is_blocked
(link
) do return false
84 redef fun heuristic_cost
(a
, b
)
86 var cost
= a
.dist_with
(b
)
87 if cost
> 100 then return 100
91 redef fun worst_heuristic_cost
do return 100
94 fun print_path
(path
: nullable Path[NamedNode]) do if path
== null then
97 var names
= new Array[String]
98 while not path
.at_end_of_path
do
102 print names
.join
(", ")
111 var graph
= new Graph[NamedNode, Link]
113 var na
= new NamedNode(graph
, "a")
114 var nb
= new NamedNode(graph
, "b")
115 var nc
= new NamedNode(graph
, "c")
116 var nd
= new NamedNode(graph
, "d")
117 var ne
= new NamedNode(graph
, "e")
119 var lab
= new Link(graph
, na
, nb
)
120 var lac
= new Link(graph
, na
, nc
)
121 var lbd
= new Link(graph
, nb
, nd
)
122 var lcd
= new Link(graph
, nc
, nd
)
123 var lde
= new Link(graph
, nd
, ne
)
125 var context
= new ConstantPathContext(graph
)
127 var path
= na
.path_to
(ne
, 100, context
)
137 var graph
= new Graph[NamedNode,Link]
139 var na
= new NamedNode(graph
, "a")
140 var nb
= new NamedNode(graph
, "b")
141 var nc
= new NamedNode(graph
, "c")
142 var nd
= new NamedNode(graph
, "d")
143 var ne
= new NamedNode(graph
, "e")
145 var lab
= new Link(graph
, na
, nb
)
146 var lac
= new Link(graph
, na
, nc
)
147 var lbd
= new Link(graph
, nb
, nd
)
148 var lcd
= new Link(graph
, nc
, nd
)
150 var context
= new ConstantPathContext(graph
)
152 var path
= na
.path_to
(ne
, 100, context
)
164 var graph
= new Graph[NamedNode,WeightedLink]
166 var na
= new NamedNode(graph
, "a")
167 var nb
= new NamedNode(graph
, "b")
168 var nc
= new NamedNode(graph
, "c")
169 var nd
= new NamedNode(graph
, "d")
170 var ne
= new NamedNode(graph
, "e")
172 var lab
= new WeightedLink(graph
, na
, nb
, 2)
173 var lac
= new WeightedLink(graph
, na
, nc
, 3)
174 var lbd
= new WeightedLink(graph
, nb
, nd
, 1)
175 var lcd
= new WeightedLink(graph
, nc
, nd
, 3)
176 var lde
= new WeightedLink(graph
, nd
, ne
, 8)
178 var context
= new WeightedPathContext(graph
)
180 var path
= na
.path_to
(ne
, 100, context
)
190 fun case_weighted_too_long
192 var graph
= new Graph[NamedNode,WeightedLink]
194 var na
= new NamedNode(graph
, "a")
195 var nb
= new NamedNode(graph
, "b")
196 var nc
= new NamedNode(graph
, "c")
197 var nd
= new NamedNode(graph
, "d")
198 var ne
= new NamedNode(graph
, "e")
200 var lab
= new WeightedLink(graph
, na
, nb
, 2)
201 var lac
= new WeightedLink(graph
, na
, nc
, 3)
202 var lbd
= new WeightedLink(graph
, nb
, nd
, 1)
203 var lcd
= new WeightedLink(graph
, nc
, nd
, 3)
204 var lde
= new WeightedLink(graph
, nd
, ne
, 8)
206 var context
= new WeightedPathContext(graph
)
208 var path
= na
.path_to
(ne
, 5, context
)
212 # "Big" weighted graph
214 # a -2- b -1- f -1- g
218 # c -3- d -8- e -2- h -2- i -3- j
220 fun case_weighted_big
222 var graph
= new Graph[NamedNode,WeightedLink]
224 var na
= new NamedNode(graph
, "a")
225 var nb
= new NamedNode(graph
, "b")
226 var nc
= new NamedNode(graph
, "c")
227 var nd
= new NamedNode(graph
, "d")
228 var ne
= new NamedNode(graph
, "e")
229 var nf
= new NamedNode(graph
, "f")
230 var ng
= new NamedNode(graph
, "g")
231 var nh
= new NamedNode(graph
, "h")
232 var ni
= new NamedNode(graph
, "i")
233 var nj
= new NamedNode(graph
, "j")
235 var lab
= new WeightedLink(graph
, na
, nb
, 2)
236 var lac
= new WeightedLink(graph
, na
, nc
, 3)
237 var lbd
= new WeightedLink(graph
, nb
, nd
, 1)
238 var lcd
= new WeightedLink(graph
, nc
, nd
, 3)
239 var lde
= new WeightedLink(graph
, nd
, ne
, 8)
240 var lbf
= new WeightedLink(graph
, nb
, nf
, 1)
241 var lfg
= new WeightedLink(graph
, nf
, ng
, 1)
242 var leh
= new WeightedLink(graph
, ne
, nh
, 2)
243 var lhi
= new WeightedLink(graph
, nh
, ni
, 2)
244 var lij
= new WeightedLink(graph
, ni
, nj
, 3)
245 var lfh
= new WeightedLink(graph
, nf
, nh
, 4)
246 var lgh
= new WeightedLink(graph
, ng
, nh
, 1)
248 var context
= new WeightedPathContext(graph
)
250 var path
= na
.path_to
(nj
, 100, context
)
254 # Double-edge graph with coordinates on nodes
260 fun cases_with_positions_and_heuristic
262 var graph
= new Graph[PositionedNamedNode,PositionedLink]
264 var na
= new PositionedNamedNode(graph
, "a", 0, 0)
265 var nb
= new PositionedNamedNode(graph
, "b", 2, 0)
266 var nc
= new PositionedNamedNode(graph
, "c", 2, 2)
267 var nd
= new PositionedNamedNode(graph
, "d", 5, 0)
268 var ne
= new PositionedNamedNode(graph
, "e", 8, 0)
269 var nf
= new PositionedNamedNode(graph
, "f", 8, 2)
271 var lab
= new PositionedLink(graph
, na
, nb
)
272 var lac
= new PositionedLink(graph
, na
, nc
)
273 var lbd
= new PositionedLink(graph
, nb
, nd
)
274 var lde
= new PositionedLink(graph
, nd
, ne
)
275 var lef
= new PositionedLink(graph
, ne
, nf
)
276 var lcf
= new PositionedLink(graph
, nc
, nf
)
279 var lba
= new PositionedLink(graph
, nb
, na
)
280 var lca
= new PositionedLink(graph
, nc
, na
)
281 var ldb
= new PositionedLink(graph
, nd
, nb
)
282 var led
= new PositionedLink(graph
, ne
, nd
)
283 var lfe
= new PositionedLink(graph
, nf
, ne
)
284 var lfc
= new PositionedLink(graph
, nf
, nc
)
286 var context
= new PositionPathContext(graph
)
288 print_path
(na
.path_to
(nf
, 100, context
))
289 print_path
(nf
.path_to
(na
, 100, context
))
290 print_path
(nc
.path_to
(ne
, 100, context
))
291 print_path
(nd
.path_to
(nc
, 100, context
))
297 case_weighted_too_long
299 cases_with_positions_and_heuristic