40 template <
class Graph,
41 class WMap,
class WLazyMap,
class IsEvaledMap,
42 class IncSP,
class EvalStrategy,
class LazySPVisitor>
43 bool lazysp(Graph & g,
44 typename boost::graph_traits<Graph>::vertex_descriptor v_start,
45 typename boost::graph_traits<Graph>::vertex_descriptor v_goal,
46 WMap wmap, WLazyMap wlazymap, IsEvaledMap isevaledmap,
47 std::vector<
typename boost::graph_traits<Graph>::edge_descriptor> & path,
48 IncSP incsp, EvalStrategy evalstrategy, LazySPVisitor visitor)
50 typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
51 typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
52 typedef typename boost::property_traits<WLazyMap>::value_type weight_type;
56 std::vector<Edge> incsp_path;
58 visitor.search_begin();
59 weight_type pathlen = incsp.solve(g, v_start, v_goal, wlazymap, incsp_path);
62 if (pathlen == incsp.inf)
69 std::vector<Vertex> vpath;
70 std::vector< std::pair<Edge,bool> > eepath;
71 bool path_evaled =
true;
72 vpath.push_back(source(incsp_path[0],g));
73 for (
unsigned int ui=0; ui<incsp_path.size(); ui++)
75 Edge & e = incsp_path[ui];
76 vpath.push_back(target(e,g));
77 bool is_evaled =
get(isevaledmap, e);
80 eepath.push_back(std::make_pair(e, is_evaled));
83 visitor.lazy_path(pathlen, vpath, eepath);
88 for (
unsigned int ui=0; ui<eepath.size(); ui++)
89 path.push_back(eepath[ui].first);
94 std::vector<Edge> to_evaluate;
95 visitor.selector_begin();
96 evalstrategy.get_to_evaluate(g, eepath, to_evaluate);
97 visitor.selector_end();
98 BOOST_ASSERT(to_evaluate.size());
102 for (
unsigned int ui=0; ui<to_evaluate.size(); ui++)
104 Edge & e = to_evaluate[ui];
107 visitor.eval_begin();
108 std::pair<weight_type, std::vector<Edge> > eval_result =
get(wmap,e);
111 visitor.edge_evaluate(e, eval_result.first);
112 put(wlazymap, e, eval_result.first);
114 for (
unsigned int ui2=0; ui2<eval_result.second.size(); ui2++)
116 incsp.update_notify(eval_result.second[ui2]);
119 visitor.selector_notify_begin();
120 for (
unsigned int ui2=0; ui2<eval_result.second.size(); ui2++)
121 evalstrategy.update_notify(eval_result.second[ui2], incsp.inf);
122 visitor.selector_notify_end();
136 template <
class Vertex,
class Edge>
137 inline void lazy_path(
double length,
138 std::vector<Vertex> & vpath,
139 std::vector< std::pair<Edge,bool> > & eepath)
143 inline void search_begin() {}
144 inline void search_end() {}
146 inline void eval_begin() {}
147 inline void eval_end() {}
149 inline void no_path() {}
150 inline void path_found() {}
152 template <
class Edge>
153 inline void edge_evaluate(Edge & e,
double e_weight) {}
155 inline void selector_begin() {}
156 inline void selector_end() {}
158 inline void selector_notify_begin() {}
159 inline void selector_notify_end() {}
165 template <
class A,
class B>
173 template <
class Vertex,
class Edge>
174 inline void lazy_path(
double length,
175 std::vector<Vertex> & vpath,
176 std::vector< std::pair<Edge,bool> > & eepath)
178 visA.lazy_path(length, vpath, eepath);
179 visB.lazy_path(length, vpath, eepath);
182 inline void search_begin()
188 inline void search_end()
194 inline void eval_begin()
200 inline void eval_end()
206 inline void no_path()
212 inline void path_found()
218 template <
class Edge>
219 inline void edge_evaluate(Edge & e,
double e_weight)
221 visA.edge_evaluate(e, e_weight);
222 visB.edge_evaluate(e, e_weight);
225 inline void selector_begin()
227 visA.selector_begin();
228 visB.selector_begin();
231 inline void selector_end()
237 inline void selector_notify_begin()
239 visA.selector_notify_begin();
240 visB.selector_notify_begin();
243 inline void selector_notify_end()
245 visA.selector_notify_end();
246 visB.selector_notify_end();
251 template <
class A,
class B>
253 make_lazysp_visitor_pair(A visA, B visB)
263 template <
class Graph>
264 void get_to_evaluate(
266 const std::vector< std::pair<
typename boost::graph_traits<Graph>::edge_descriptor,
bool> > & path,
267 std::vector<
typename boost::graph_traits<Graph>::edge_descriptor> & to_evaluate)
270 for (ui=0; ui<path.size(); ui++)
271 if (path[ui].second ==
false)
274 to_evaluate.push_back(path[ui].first);
276 template <
class Edge,
class WeightType>
277 void update_notify(Edge e, WeightType e_weight_old) {}
285 template <
class Graph>
286 void get_to_evaluate(
288 const std::vector< std::pair<
typename boost::graph_traits<Graph>::edge_descriptor,
bool> > & path,
289 std::vector<
typename boost::graph_traits<Graph>::edge_descriptor> & to_evaluate)
292 for (i=path.size()-1; 0<=i; i--)
293 if (path[i].second ==
false)
296 to_evaluate.push_back(path[i].first);
298 template <
class Edge,
class WeightType>
299 void update_notify(Edge e, WeightType e_weight_old) {}
311 template <
class Graph>
312 void get_to_evaluate(
314 const std::vector< std::pair<
typename boost::graph_traits<Graph>::edge_descriptor,
bool> > & path,
315 std::vector<
typename boost::graph_traits<Graph>::edge_descriptor> & to_evaluate)
318 fwd.get_to_evaluate(g, path, to_evaluate);
320 rev.get_to_evaluate(g, path, to_evaluate);
323 template <
class Edge,
class WeightType>
324 void update_notify(Edge e, WeightType e_weight_old) {}
332 template <
class Graph>
333 void get_to_evaluate(
335 const std::vector< std::pair<
typename boost::graph_traits<Graph>::edge_descriptor,
bool> > & path,
336 std::vector<
typename boost::graph_traits<Graph>::edge_descriptor> & to_evaluate)
338 unsigned int ui, idx;
339 for (ui=0; ui<path.size(); ui++)
344 idx = path.size() - (ui+1)/2;
345 if (path[idx].second ==
false)
349 to_evaluate.push_back(path[idx].first);
351 template <
class Edge,
class WeightType>
352 void update_notify(Edge e, WeightType e_weight_old) {}
360 template <
class Graph>
361 void get_to_evaluate(
363 const std::vector< std::pair<
typename boost::graph_traits<Graph>::edge_descriptor,
bool> > & path,
364 std::vector<
typename boost::graph_traits<Graph>::edge_descriptor> & to_evaluate)
370 std::vector<int> dists(path.size());
372 for (i=0; i<(int)path.size(); i++)
380 fwd_dist = dists[i-1] + 1;
384 for (i=path.size()-1; i>=0; i--)
389 else if (i==(
int)path.size()-1)
392 rev_dist = dists[i+1] + 1;
393 if (rev_dist < dists[i])
399 for (i=0; i<(int)path.size(); i++)
409 printf(
"error with max!\n");
412 to_evaluate.push_back(path[max_i].first);
414 template <
class Edge,
class WeightType>
415 void update_notify(Edge e, WeightType e_weight_old) {}
423 template <
class Graph>
424 void get_to_evaluate(
426 const std::vector< std::pair<
typename boost::graph_traits<Graph>::edge_descriptor,
bool> > & path,
427 std::vector<
typename boost::graph_traits<Graph>::edge_descriptor> & to_evaluate)
430 for (ui=0; ui<path.size(); ui++)
431 if (path[ui].second ==
false)
433 if (!(ui<path.size()))
435 typename boost::graph_traits<Graph>::out_edge_iterator ei, ei_end;
436 for (boost::tie(ei,ei_end)=out_edges(source(path[ui].first,g),g); ei!=ei_end; ++ei)
437 to_evaluate.push_back(*ei);
439 template <
class Edge,
class WeightType>
440 void update_notify(Edge e, WeightType e_weight_old) {}
Forward selector for pr_bgl::lazysp.
Definition: lazysp.h:260
Bisect selector for pr_bgl::lazysp.
Definition: lazysp.h:357
Reverse selector for pr_bgl::lazysp.
Definition: lazysp.h:282
FwdExpand selector for pr_bgl::lazysp.
Definition: lazysp.h:420
Even selector for pr_bgl::lazysp.
Definition: lazysp.h:329
Null visitor for pr_bgl::lazysp.
Definition: lazysp.h:130
Pair visitor for pr_bgl::lazysp.
Definition: lazysp.h:166
Alternate selector for pr_bgl::lazysp.
Definition: lazysp.h:304