Ticket #11804: custom_dijkstra_call.hpp

File custom_dijkstra_call.hpp, 3.8 KB (added by Irek Szcześniak <irek@…>, 7 years ago)

the implementation of the custom dijkstra call - v1

Line 
1//=======================================================================
2// Copyright 2015 by Ireneusz Szcześniak
3// Authors: Ireneusz Szcześniak
4//
5// Distributed under the Boost Software License, Version 1.0. (See
6// accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8//=======================================================================
9
10//=======================================================================
11// The custom Dijkstra call, which returns the optional path as a list
12// along with the cost of the path. The search is stopped when the
13// destination node is reached.
14//=======================================================================
15
16#ifndef BOOST_GRAPH_CUSTOM_DIJKSTRA_CALL
17#define BOOST_GRAPH_CUSTOM_DIJKSTRA_CALL
18
19#include <list>
20#include <set>
21
22#include <boost/graph/dijkstra_shortest_paths.hpp>
23#include <boost/graph/visitors.hpp>
24#include <boost/optional.hpp>
25#include <boost/property_map/vector_property_map.hpp>
26#include <boost/utility/value_init.hpp>
27
28namespace boost {
29
30 //========================================================================
31 // Finish the search when a given node is examined, i.e. when the
32 // shortest path to that node is found.
33 // ========================================================================
34
35 // The type of the exception thrown by the cdc_visitor.
36 struct cdc_exception {};
37
38 template <class Graph>
39 struct cdc_visitor
40 {
41 typedef typename Graph::vertex_descriptor vertex_descriptor;
42 typedef on_examine_vertex event_filter;
43 cdc_visitor(vertex_descriptor t): m_t(t) {}
44 void operator()(vertex_descriptor v, const Graph& g) {
45 if (v == m_t)
46 throw cdc_exception();
47 }
48 vertex_descriptor m_t;
49 };
50
51 //========================================================================
52 // The function.
53 //=======================================================================+
54
55 template <typename Graph, typename WeightMap, typename IndexMap>
56 optional<std::pair<typename WeightMap::value_type,
57 std::list<typename Graph::edge_descriptor>>>
58 custom_dijkstra_call(const Graph &g,
59 typename Graph::vertex_descriptor s,
60 typename Graph::vertex_descriptor t,
61 WeightMap wm, IndexMap im)
62 {
63 typedef typename Graph::vertex_descriptor vertex_descriptor;
64 typedef typename Graph::edge_descriptor edge_descriptor;
65 typedef typename std::list<typename Graph::edge_descriptor> path_type;
66 typedef typename WeightMap::value_type weight_type;
67 typedef typename std::pair<weight_type, path_type> kr_type;
68
69 std::vector<edge_descriptor> pred_vec(num_vertices(g));
70 auto pred = make_iterator_property_map(pred_vec.begin(), im);
71 auto rep = record_edge_predecessors(pred, on_edge_relaxed());
72 auto qat = cdc_visitor<Graph>(t);
73 auto dv = make_dijkstra_visitor(std::make_pair(rep, qat));
74
75 try
76 {
77 dijkstra_shortest_paths(g, s,
78 weight_map(wm).vertex_index_map(im).
79 visitor(dv));
80 }
81 catch (cdc_exception) {}
82
83 optional<kr_type> result;
84
85 // Was the solution found?
86 if (pred[t] != edge_descriptor())
87 {
88 // The cost of the shortest path.
89 value_initialized<weight_type> cost;
90 // The path found.
91 path_type path;
92
93 // Trace the solution to the source.
94 vertex_descriptor c = t;
95 while (c != s)
96 {
97 const edge_descriptor &e = pred[c];
98 // Build the path.
99 path.push_front(e);
100 // Calculate the cost of the path.
101 cost += get(wm, e);
102 // Find the predecessing vertex.
103 c = source(e, g);
104 }
105
106 result = std::make_pair(cost, path);
107 }
108
109 return result;
110 }
111
112} // boost
113
114#endif /* BOOST_GRAPH_CUSTOM_DIJKSTRA_CALL */