#
root/sandbox/orkney/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.