Ticket #11804: custom_dijkstra_call.2.hpp

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

the implementation of the custom dijkstra call - v2

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// of edges along with the cost of the path. The search is stopped
13// when the 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
21#include <boost/graph/dijkstra_shortest_paths.hpp>
22#include <boost/graph/visitors.hpp>
23#include <boost/optional.hpp>
24#include <boost/property_map/property_map.hpp>
25#include <boost/utility/value_init.hpp>
26
27namespace boost {
28
29 //========================================================================
30 // Finish the search when a given node is examined, i.e. when the
31 // shortest path to that node is found.
32 // ========================================================================
33
34 // The type of the exception thrown by the cdc_visitor.
35 struct cdc_exception {};
36
37 template <class Graph>
38 struct cdc_visitor
39 {
40 typedef typename Graph::vertex_descriptor vertex_descriptor;
41 typedef on_examine_vertex event_filter;
42 cdc_visitor(vertex_descriptor t): m_t(t) {}
43 void operator()(vertex_descriptor v, const Graph& g) {
44 if (v == m_t)
45 throw cdc_exception();
46 }
47 vertex_descriptor m_t;
48 };
49
50 //========================================================================
51 // The function.
52 //=======================================================================+
53
54 template <typename Graph, typename WeightMap, typename IndexMap>
55 optional<std::pair<typename WeightMap::value_type,
56 std::list<typename Graph::edge_descriptor>>>
57 custom_dijkstra_call(const Graph &g,
58 typename Graph::vertex_descriptor s,
59 typename Graph::vertex_descriptor t,
60 WeightMap wm, IndexMap im)
61 {
62 typedef typename Graph::vertex_descriptor vertex_descriptor;
63 typedef typename Graph::edge_descriptor edge_descriptor;
64 typedef typename std::list<typename Graph::edge_descriptor> path_type;
65 typedef typename WeightMap::value_type weight_type;
66 typedef typename std::pair<weight_type, path_type> kr_type;
67
68 std::vector<edge_descriptor> pred_vec(num_vertices(g));
69 auto pred = make_iterator_property_map(pred_vec.begin(), im);
70 auto rep = record_edge_predecessors(pred, on_edge_relaxed());
71 auto qat = cdc_visitor<Graph>(t);
72 auto dv = make_dijkstra_visitor(std::make_pair(rep, qat));
73
74 try
75 {
76 dijkstra_shortest_paths(g, s,
77 weight_map(wm).vertex_index_map(im).
78 visitor(dv));
79 }
80 catch (cdc_exception) {}
81
82 optional<kr_type> result;
83
84 // Was the solution found?
85 if (pred[t] != edge_descriptor())
86 {
87 // The cost of the shortest path.
88 value_initialized<weight_type> cost;
89 // The path found.
90 path_type path;
91
92 // Trace the solution to the source.
93 vertex_descriptor c = t;
94 while (c != s)
95 {
96 const edge_descriptor &e = pred[c];
97 // Build the path.
98 path.push_front(e);
99 // Calculate the cost of the path.
100 cost += get(wm, e);
101 // Find the predecessing vertex.
102 c = source(e, g);
103 }
104
105 result = std::make_pair(cost, path);
106 }
107
108 return result;
109 }
110
111} // boost
112
113#endif /* BOOST_GRAPH_CUSTOM_DIJKSTRA_CALL */