Context Navigation

shooting_star_search.hpp

Revision 82, 18.2 KB (checked in by anton, 3 years ago)

Line
1	/*
2	* Copyright (c) 2007 Anton A. Patrushev, Orkney, Inc.
3	*
4	* This program is free software; you can redistribute it and/or modify
5	* it under the terms of the GNU General Public License as published by
6	* the Free Software Foundation; either version 2 of the License, or
7	* (at your option) any later version.
8	*
9	* This program is distributed in the hope that it will be useful,
10	* but WITHOUT ANY WARRANTY; without even the implied warranty of
11	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12	* GNU General Public License for more details.
13	*
14	* You should have received a copy of the GNU General Public License
15	* along with this program; if not, write to the Free Software
16	* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17	*
18	*/
19
20	#ifndef BOOST_GRAPH_SHOOTING_STAR_SEARCH_HPP
21	#define BOOST_GRAPH_SHOOTING_STAR_SEARCH_HPP
22
23	#define MAX_RULE_LENGTH 5
24
25	#include <functional>
26	#include <boost/limits.hpp>
27	#include <boost/graph/named_function_params.hpp>
28	#include <boost/pending/mutable_queue.hpp>
29	#include <boost/pending/relaxed_heap.hpp>
30	#include <boost/pending/indirect_cmp.hpp>
31	#include <boost/graph/exception.hpp>
32	#include <boost/graph/breadth_first_search.hpp>
33
34	#include "edge_visitors.hpp"
35	#include "shooting_star_relax.hpp"
36
37
38	namespace boost
39	{
40
41	template <class Visitor, class Graph>
42	struct ShootingStarVisitorConcept {
43	void constraints()
44	{
45	function_requires< CopyConstructibleConcept<Visitor> >();
46	vis.initialize_vertex(u, g);
47	vis.discover_vertex(u, g);
48	vis.examine_vertex(u, g);
49	vis.examine_edge(e, g);
50	vis.black_target(e, pe, g, e_max_id);
51	vis.gray_target(e, pe, g, e_max_id);
52	vis.finish_vertex(u, g);
53
54	vis.tree_edge(e, pe, g, e_max_id);
55
56	vis.initialize_edge(e, g);
57	vis.discover_edge(e, g);
58	vis.finish_edge(e, g);
59
60	}
61	Visitor vis;
62	Graph g;
63	typename graph_traits<Graph>::vertex_descriptor u;
64	typename graph_traits<Graph>::edge_descriptor e, pe;
65	int e_max_id;
66	};
67
68
69	template <class IncidenceGraph, class Buffer, class BFSVisitor,
70	class ColorMap, class EdgeColorMap/, class HistoryMap/>
71	void shooting_star_edges_visit (const IncidenceGraph& g,
72	typename graph_traits<IncidenceGraph>::edge_descriptor s,
73	Buffer& Q, BFSVisitor vis, ColorMap color, EdgeColorMap edge_color,
74	int e_max_id)
75	{
76	function_requires< IncidenceGraphConcept<IncidenceGraph> >();
77	typedef graph_traits<IncidenceGraph> GTraits;
78	typedef typename GTraits::vertex_descriptor Vertex;
79	typedef typename GTraits::edge_descriptor Edge;
80	function_requires< ShootingStarVisitorConcept<BFSVisitor, IncidenceGraph> >();
81	function_requires< ReadWritePropertyMapConcept<EdgeColorMap, Edge> >();
82
83	typedef typename property_traits<ColorMap>::value_type ColorValue;
84	typedef color_traits<ColorValue> Color;
85
86	typedef typename property_traits<EdgeColorMap>::value_type EdgeColorValue;
87	typedef color_traits<EdgeColorValue> EdgeColor;
88
89	typename GTraits::out_edge_iterator ei, ei_end;
90
91	put(edge_color, s, EdgeColor::gray());
92	vis.discover_edge(s, g);
93
94	Q.push(s);
95
96	while (! Q.empty())
97	{
98	Edge e = Q.top(); Q.pop();
99
100	vis.examine_edge(e, g);
101
102	for (tie(ei, ei_end) = out_edges(target(e, g), g); ei != ei_end; ++ei)
103	{
104	EdgeColorValue e_color = get(edge_color, *ei);
105
106	if (e_color == EdgeColor::white())
107	{
108	vis.tree_edge(*ei, e, g, e_max_id);
109	put(edge_color, *ei, EdgeColor::gray());
110	vis.discover_edge(*ei, g);
111	Q.push(*ei);
112	}
113	else
114	{
115	vis.non_tree_edge(*ei, g);
116	if (e_color == EdgeColor::gray())
117	{
118	vis.gray_target(*ei, e, g, e_max_id);
119	}
120	else
121	{
122	vis.black_target(*ei, e, g, e_max_id);
123	}
124	}
125
126	} // end for
127
128	put(edge_color, e, EdgeColor::black());
129	vis.finish_edge(e, g);
130
131	} // end while
132	}
133
134
135	template <class Visitors = null_visitor>
136	class shooting_star_visitor : public bfs_visitor<Visitors>
137	{
138	public:
139	shooting_star_visitor() {}
140	shooting_star_visitor(Visitors vis)
141	: bfs_visitor<Visitors>(vis) {}
142
143	template <class Edge, class Graph>
144	void edge_relaxed(Edge e, Graph& g)
145	{
146	invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
147	}
148	template <class Edge, class Graph>
149	void edge_not_relaxed(Edge e, Graph& g)
150	{
151	invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());
152	}
153	template <class Edge, class Graph>
154	void initialize_edge(Edge e, Graph& g)
155	{
156	invoke_visitors(this->m_vis, e, g, on_initialize_edge());
157	}
158
159	private:
160	template <class Edge, class Graph>
161	void tree_edge(Edge e, Edge pe, Graph& g) {}
162	template <class Edge, class Graph>
163	void non_tree_edge(Edge e, Graph& g) {}
164	};
165
166	template <class Visitors>
167	shooting_star_visitor<Visitors>
168	make_shooting_star_visitor(Visitors vis)
169	{
170	return shooting_star_visitor<Visitors>(vis);
171	}
172
173	typedef shooting_star_visitor<> default_shooting_star_visitor;
174
175
176	namespace detail {
177
178	template <class AStarHeuristic, class UniformCostVisitor,
179	class UpdatableQueue, class PredecessorMap,
180	class CostMap,
181	class DistanceMap, class WeightMap,
182	class EdgeMap,
183	class ColorMap, class EdgeColorMap,
184	class BinaryFunction,
185	class BinaryPredicate>
186	struct shooting_star_bfs_visitor
187	{
188
189	typedef typename property_traits<CostMap>::value_type C;
190	typedef typename property_traits<ColorMap>::value_type ColorValue;
191	typedef color_traits<ColorValue> Color;
192
193	typedef typename property_traits<EdgeColorMap>::value_type EdgeColorValue;
194	typedef color_traits<ColorValue> EdgeColor;
195
196	typedef typename property_traits<DistanceMap>::value_type distance_type;
197
198	shooting_star_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis,
199	UpdatableQueue& Q, PredecessorMap& p,
200	CostMap c, DistanceMap d, WeightMap w, EdgeMap em,
201	ColorMap col, EdgeColorMap ecol, //HistoryMap his,
202	BinaryFunction combine,
203	BinaryPredicate compare, C zero)
204	: m_h(h), m_vis(vis), m_Q(Q), m_predecessor(p), m_cost(c),
205	m_distance(d), m_weight(w), m_edge(em), m_color(col),
206	m_ecolor(ecol), //m_history(his),
207	m_combine(combine), m_compare(compare), m_zero(zero) {}
208
209	shooting_star_bfs_visitor(const shooting_star_bfs_visitor &v)
210	: m_h(v.m_h), m_vis(v.m_vis), m_Q(v.m_Q), m_predecessor(v.m_predecessor), m_cost(v.m_cost),
211	m_distance(v.m_distance), m_weight(v.m_weight), m_edge(v.m_edge), m_color(v.m_color),
212	m_ecolor(v.m_ecolor), //m_history(his),
213	m_combine(v.m_combine), m_compare(v.m_compare), m_zero(v.m_zero) {}
214
215	~shooting_star_bfs_visitor() {}
216
217	template <class Vertex, class Graph>
218	void initialize_vertex(Vertex u, Graph& g)
219	{
220	m_vis.initialize_vertex(u, g);
221	}
222	template <class Edge, class Graph>
223	void initialize_edge(Edge e, Graph& g)
224	{
225	m_vis.initialize_edge(e, g);
226	}
227	template <class Vertex, class Graph>
228	void discover_vertex(Vertex u, Graph& g)
229	{
230	m_vis.discover_vertex(u, g);
231	}
232	template <class Edge, class Graph>
233	void discover_edge(Edge e, Graph& g)
234	{
235	m_vis.discover_vertex(e, g);
236	}
237	template <class Vertex, class Graph>
238	void examine_vertex(Vertex u, Graph& g)
239	{
240	m_vis.examine_vertex(u, g);
241	}
242	template <class Vertex, class Graph>
243	void finish_vertex(Vertex u, Graph& g)
244	{
245	m_vis.finish_vertex(u, g);
246	}
247	template <class Edge, class Graph>
248	void examine_edge(Edge e, Graph& g)
249	{
250	if (m_compare(get(m_weight, e), m_zero))
251	throw negative_edge();
252	m_vis.examine_edge(e, g);
253	}
254	template <class Edge, class Graph>
255	void non_tree_edge(Edge, Graph&) {}
256
257	template <class Edge, class Graph>
258	void finish_edge(Edge e, Graph& g)
259	{
260	m_vis.finish_edge(e, g);
261	}
262
263
264	template <class Edge, class Graph>
265	void tree_edge(Edge e, Edge pe, Graph& g, int e_max_id)
266	{
267	m_decreased = relax(e, pe, g, m_weight, m_edge, m_predecessor, m_distance,
268	m_cost, m_combine, m_compare, e_max_id);
269
270	if(m_decreased)
271	{
272	m_vis.edge_relaxed(e, g);
273
274	put(m_cost, e,
275	m_combine(get(m_distance, e),
276	m_h(e)));
277
278	}
279	else
280	m_vis.edge_not_relaxed(e, g);
281	}
282
283
284	template <class Edge, class Graph>
285	void gray_target(Edge e, Edge pe, Graph& g, int e_max_id)
286	{
287	m_decreased = relax(e, pe, g, m_weight, m_edge, m_predecessor, m_distance,
288	m_cost, m_combine, m_compare, e_max_id);
289
290	if(m_decreased)
291	{
292	put(m_cost, e,
293	m_combine(get(m_distance, e),
294	m_h(e)));
295
296	m_Q.update(e);
297
298	m_vis.edge_relaxed(e, g);
299	}
300	else
301	m_vis.edge_not_relaxed(e, g);
302	}
303
304
305	template <class Edge, class Graph>
306	void black_target(Edge e, Edge pe, Graph& g, int e_max_id)
307	{
308
309	m_decreased = relax(e, pe, g, m_weight, m_edge, m_predecessor, m_distance,
310	m_cost, m_combine, m_compare, e_max_id);
311
312	if(m_decreased)
313	{
314	m_vis.edge_relaxed(e, g);
315	put(m_cost, e, m_combine(get(m_distance, e), m_h(e)));
316
317	m_Q.push(e);
318	put(m_ecolor, e, EdgeColor::gray());
319	m_vis.black_target(e, g);
320	}
321	else
322	m_vis.edge_not_relaxed(e, g);
323	}
324
325	AStarHeuristic m_h;
326	UniformCostVisitor m_vis;
327	UpdatableQueue& m_Q;
328	PredecessorMap& m_predecessor;
329	CostMap m_cost;
330	EdgeMap m_edge;
331	DistanceMap m_distance;
332	WeightMap m_weight;
333	ColorMap m_color;
334	EdgeColorMap m_ecolor;
335	BinaryFunction m_combine;
336	BinaryPredicate m_compare;
337	bool m_decreased;
338	C m_zero;
339	};
340
341	} // namespace detail
342
343	template <typename VertexAndEdgeListGraph, typename AStarHeuristic,
344	typename ShootingStarVisitor, typename PredecessorMap,
345	typename CostMap,
346	typename DistanceMap,
347	typename WeightMap,
348	typename EdgeMap,
349	typename ColorMap, typename EdgeColorMap,
350	typename IndexMap,
351	typename CompareFunction, typename CombineFunction,
352	typename CostInf, typename CostZero>
353	inline void
354	shooting_star_search_no_init
355	(VertexAndEdgeListGraph &g,
356	typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
357	AStarHeuristic h, ShootingStarVisitor vis,
358	PredecessorMap &predecessor, CostMap cost,
359	DistanceMap distance, WeightMap weight, EdgeMap edge_map,
360	ColorMap color, EdgeColorMap edge_color,
361	IndexMap index_map, CompareFunction compare, CombineFunction combine,
362	CostInf inf, CostZero zero, int e_max_id)
363	{
364	typedef indirect_cmp<CostMap, CompareFunction> IndirectCmp;
365	IndirectCmp icmp(cost, compare);
366
367	typedef typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor
368	Edge;
369
370	typedef mutable_queue<Edge, std::vector<Edge>, IndirectCmp, IndexMap>
371	MutableQueue;
372	MutableQueue Q(num_edges(g), icmp, index_map);
373
374	detail::shooting_star_bfs_visitor<AStarHeuristic, ShootingStarVisitor,
375	MutableQueue, PredecessorMap, CostMap, DistanceMap,
376	WeightMap, EdgeMap, ColorMap, EdgeColorMap, /HistoryMap,/ CombineFunction, CompareFunction>
377	bfs_vis(h, vis, Q, predecessor, cost, distance, weight,
378	edge_map, color, edge_color, combine, compare, zero);
379
380	shooting_star_edges_visit(g, s, Q, bfs_vis, color, edge_color, e_max_id);
381	}
382
383	// Non-named parameter interface
384	template <typename VertexAndEdgeListGraph, typename AStarHeuristic,
385	typename ShootingStarVisitor, typename PredecessorMap,
386	typename CostMap, typename DistanceMap,
387	typename WeightMap, typename EdgeMap,
388	typename IndexMap,
389	typename ColorMap, typename EdgeColorMap,
390	//typename HistoryMap,
391	typename CompareFunction, typename CombineFunction,
392	typename CostInf, typename CostZero>
393	inline void
394	shooting_star_search
395	(VertexAndEdgeListGraph &g,
396	typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
397	AStarHeuristic h, ShootingStarVisitor vis,
398	PredecessorMap &predecessor, CostMap cost,
399	DistanceMap distance, WeightMap weight,
400	EdgeMap edge_map, IndexMap index_map, ColorMap color, EdgeColorMap edge_color,
401	CompareFunction compare, CombineFunction combine,
402	CostInf inf, CostZero zero, int e_max_id)
403	{
404
405	typedef typename property_traits<ColorMap>::value_type ColorValue;
406	typedef color_traits<ColorValue> Color;
407
408	typedef typename property_traits<EdgeColorMap>::value_type EdgeColorValue;
409	typedef color_traits<EdgeColorValue> EdgeColor;
410
411	typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator ui, ui_end;
412	typename graph_traits<VertexAndEdgeListGraph>::edge_iterator ei, ei_end;
413
414	for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
415	{
416	vis.initialize_vertex(*ui, g);
417	}
418
419	for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
420	{
421	put(distance, *ei, inf);
422	put(edge_color, *ei, EdgeColor::white());
423	predecessor[g[ei].id] = ei;
424	put(cost, *ei, inf);
425	}
426
427	put(distance, s, zero);
428
429	put(cost, s, h(s));
430
431	shooting_star_search_no_init
432	(g, s, h, vis, predecessor, cost, distance, weight, edge_map,
433	color, edge_color, index_map, compare, combine, inf, zero, e_max_id);
434
435	}
436
437	namespace detail
438	{
439	template <class VertexAndEdgeListGraph, class AStarHeuristic,
440	class CostMap, class DistanceMap, class WeightMap, class EdgeMap,
441	class IndexMap,
442	class PredecessorMap,
443	class ColorMap, class EdgeColorMap,
444	class Params>
445	inline void
446	shooting_star_dispatch2
447	(VertexAndEdgeListGraph& g,
448	typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
449	AStarHeuristic h, CostMap cost, DistanceMap distance,
450	WeightMap weight, EdgeMap edge_map, IndexMap index_map,
451	PredecessorMap& predecessor, ColorMap color,
452	EdgeColorMap edge_color, const Params& params,
453	int e_max_id)
454	{
455	dummy_property_map p_map;
456	typedef typename property_traits<CostMap>::value_type C;
457	shooting_star_search
458	(g, s, h,
459	choose_param(get_param(params, graph_visitor),
460	make_shooting_star_visitor(null_visitor())),
461	predecessor,
462	cost, distance, weight, edge_map, index_map, color, edge_color, //history,
463	choose_param(get_param(params, distance_compare_t()),
464	std::less<C>()),
465	choose_param(get_param(params, distance_combine_t()),
466	closed_plus<C>()),
467	choose_param(get_param(params, distance_inf_t()),
468	std::numeric_limits<C>::max BOOST_PREVENT_MACRO_SUBSTITUTION ()),
469	choose_param(get_param(params, distance_zero_t()),
470	C()),
471	e_max_id
472	);
473	}
474
475	template <class VertexAndEdgeListGraph, class AStarHeuristic,
476	class CostMap, class DistanceMap, class WeightMap,
477	class EdgeMap, class IndexMap,
478	class PredecessorMap,
479	class ColorMap, class EdgeColorMap,
480	class Params>
481	inline void
482	shooting_star_dispatch1
483	(VertexAndEdgeListGraph& g,
484	typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
485	AStarHeuristic h, CostMap cost, DistanceMap distance,
486	WeightMap weight, EdgeMap edge_map, IndexMap index_map, PredecessorMap& predecessor,
487	ColorMap color, EdgeColorMap edge_color, const Params& params,
488	int e_max_id)
489	{
490	typedef typename property_traits<WeightMap>::value_type D;
491	typename std::vector<D>::size_type
492	n = is_default_param(distance) ? num_vertices(g) : 1;
493	std::vector<D> distance_map(n);
494	n = is_default_param(cost) ? num_vertices(g) : 1;
495	std::vector<D> cost_map(n);
496
497	std::vector<default_color_type> color_map(num_vertices(g));
498	default_color_type c = white_color;
499
500	detail::shooting_star_dispatch2
501	(g, s, h,
502	choose_param(cost, make_iterator_property_map
503	(cost_map.begin(), index_map,
504	cost_map[0])),
505	choose_param(distance, make_iterator_property_map
506	(distance_map.begin(), index_map,
507	distance_map[0])),
508	weight, edge_map, index_map,
509	predecessor,
510	choose_param(color, make_iterator_property_map
511	(color_map.begin(), index_map, c)),
512	edge_color,
513	params,
514	e_max_id);
515	}
516	} // namespace detail
517
518	// Named parameter interface
519	template <typename VertexAndEdgeListGraph,
520	typename AStarHeuristic,
521	typename P, typename T, typename R,
522	typename IndexMap,
523	typename DistanceMap,
524	typename CostMap,
525	typename PredecessorMap>
526	void
527	shooting_star_search
528	(VertexAndEdgeListGraph &g,
529	typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
530	AStarHeuristic h, const bgl_named_params<P, T, R>& params,
531	IndexMap edge_index,
532	DistanceMap distance,
533	CostMap cost,
534	PredecessorMap &pre_map,
535	int e_max_id)
536	{
537	typedef typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor tEdge;
538
539	detail::shooting_star_dispatch1
540	(g, s, h,
541	cost,
542	distance,
543	choose_const_pmap(get_param(params, edge_weight), g, edge_weight), //weight
544	choose_const_pmap(get_param(params, edge_weight2), g, edge_weight2), //adjacent edges cost
545	edge_index,
546	pre_map, //predecessors
547	get_param(params, vertex_color), //vertex color (deprecated)
548	get_param(params, edge_color), //edge color
549	params,
550	e_max_id
551	);
552	}
553
554	} // namespace boost
555
556	#endif // BOOST_GRAPH_SHOOTING_STAR_SEARCH_HPP

Note: See TracBrowser for help on using the browser.

Context Navigation

root/sandbox/orkney/shooting_star_search.hpp

Download in other formats: