Ticket #11838: yen_ksp.2.hpp

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

the implementation - v2

Line 
1//=======================================================================
2// Copyright 2015 by Ireneusz Szcześniak
3// Authors: Ireneusz Szcześniak <www.irkos.org>
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// This is the implementation of the Yen algorithm:
12//
13// Jin Y. Yen, Finding the k shortest loopless paths in a network,
14// Management Science, vol. 17, no. 11, July 1971, pages 712-716
15//
16// But actually, I found the following explanation better:
17//
18// https://en.wikipedia.org/wiki/Yen%27s_algorithm
19//=======================================================================
20
21#ifndef BOOST_GRAPH_YEN_KSP
22#define BOOST_GRAPH_YEN_KSP
23
24#include <list>
25#include <set>
26#include <map>
27
28#include <boost/graph/dijkstra_shortest_paths.hpp>
29#include <boost/graph/filtered_graph.hpp>
30#include <boost/optional.hpp>
31#include <boost/range/adaptor/reversed.hpp>
32#include <boost/utility/value_init.hpp>
33
34#include "custom_dijkstra_call.hpp"
35
36namespace boost {
37
38 template <typename Graph, typename WeightMap, typename IndexMap>
39 std::list<std::pair<typename WeightMap::value_type,
40 std::list<typename Graph::edge_descriptor>>>
41 yen_ksp(const Graph& g,
42 typename Graph::vertex_descriptor s,
43 typename Graph::vertex_descriptor t,
44 WeightMap wm, IndexMap im, optional<unsigned> K)
45 {
46 typedef typename Graph::vertex_descriptor vertex_descriptor;
47 typedef typename Graph::edge_descriptor edge_descriptor;
48 typedef typename WeightMap::value_type weight_type;
49 typedef std::set<edge_descriptor> es_type;
50 typedef std::set<vertex_descriptor> vs_type;
51 typedef filtered_graph<Graph, is_not_in_subset<es_type>,
52 is_not_in_subset<vs_type>> fg_type;
53 typedef std::list<edge_descriptor> path_type;
54 typedef std::pair<weight_type, path_type> kr_type;
55
56 // The results.
57 std::list<kr_type> A;
58 // The tentative results.
59 std::multimap<weight_type, path_type> B;
60
61 // The set of excluded edges.
62 es_type exe;
63 // The set of excluded vertexes.
64 vs_type exv;
65
66 // The edge predicate.
67 is_not_in_subset<es_type> ep(exe);
68 // The vertex predicate.
69 is_not_in_subset<vs_type> vp(exv);
70
71 // The filtered graph.
72 fg_type fg(g, ep, vp);
73
74 optional<kr_type> okr = custom_dijkstra_call(g, s, t, wm, im);
75
76 if (okr)
77 {
78 A.push_back(okr.get());
79
80 for (int k = 1; !K || k < K.get(); ++k)
81 {
82 // The previous shortest result.
83 const kr_type &psr = A.back();
84 const path_type &psp = psr.second;
85
86 // Iterate over the edges of the previous shortest path.
87 for(auto i = psp.begin(); i != psp.end(); ++i)
88 {
89 // The spur vertex.
90 vertex_descriptor sv = source(*i, g);
91 // The root path.
92 path_type rp = path_type(psp.begin(), i);
93
94 // Iterate over the previous shortest paths.
95 for(const auto &kr: A)
96 {
97 const path_type &kp = kr.second;
98 typename path_type::const_iterator i1, i2;
99
100 // Iterate as long as possible, and as long as
101 // paths are equal.
102 for(tie(i1, i2) = std::make_pair(kp.begin(), rp.begin());
103 i1 != kp.end() && i2 != rp.end() && *i1 == *i2;
104 ++i1, ++i2);
105
106 // Make sure we didn't reach the end of kp. If we
107 // did, there is no next edge in kp, which we
108 // could exclude. Also, make sure we reached the
109 // end of rp, i.e., the kp begins with rp.
110 if (i1 != kp.end() && i2 == rp.end())
111 exe.insert(*i1);
112 }
113
114 // Remove the vertexes that belong to the root path,
115 // except the last vertex, i.e., the spur node.
116 for (const auto &e: rp)
117 exv.insert(source(e, g));
118
119 // Optional spur result.
120 optional<kr_type> osr = custom_dijkstra_call(fg, sv, t, wm, im);
121
122 if (osr)
123 {
124 // The tentative result.
125 kr_type tr = osr.get();
126 for(const auto &e: boost::adaptors::reverse(rp))
127 {
128 tr.second.push_front(e);
129 tr.first += get(wm, e);
130 }
131 B.insert(tr);
132 }
133
134 // Clear the excluded edges and vertexes.
135 exe.clear();
136 exv.clear();
137 }
138
139 // Stop searching when there are no tentative paths.
140 if (B.empty())
141 break;
142
143 // Take the shortest tentative path and make it the next
144 // shortest path.
145 A.push_back(*B.begin());
146 B.erase(B.begin());
147 }
148 }
149
150 return A;
151 }
152
153 template <typename Graph>
154 std::list<std::pair<typename property_map<Graph, edge_weight_t>::value_type,
155 std::list<typename Graph::edge_descriptor>>>
156 yen_ksp(Graph& g,
157 typename Graph::vertex_descriptor s,
158 typename Graph::vertex_descriptor t,
159 optional<unsigned> K = optional<unsigned>())
160 {
161 return yen_ksp(g, s, t, get(edge_weight_t(), g),
162 get(vertex_index_t(), g), K);
163 }
164
165} // boost
166
167#endif /* BOOST_GRAPH_YEN_KSP */