Ticket #11804: edge_disjoint_ksp.6.hpp

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

the implementation - v6

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// Function edge_disjoint_ksp finds the k-shortest paths which are
12// edge-disjoint, i.e. the paths do not have common edges. The graph
13// can have parallel edges. The algorithm employs the Dijkstra
14// algorithm to find the shortest path. Next the edges of the found
15// path are disabled, and Dijkstra finds the second shortest path.
16// This process is repeated until k paths are found or there are no
17// more paths to be found.
18// =======================================================================
19
20#ifndef BOOST_GRAPH_EDGE_DISJOINT_KSP
21#define BOOST_GRAPH_EDGE_DISJOINT_KSP
22
23#include <list>
24#include <set>
25
26#include <boost/graph/filtered_graph.hpp>
27#include <boost/optional.hpp>
28
29#include "custom_dijkstra_call.hpp"
30
31namespace boost {
32
33 //========================================================================
34 // The implementation of the k-shortest paths algorithm.
35 //========================================================================
36
37 template <typename Graph, typename WeightMap, typename IndexMap>
38 std::list<std::pair<typename WeightMap::value_type,
39 std::list<typename Graph::edge_descriptor>>>
40 edge_disjoint_ksp(const Graph& g,
41 typename Graph::vertex_descriptor s,
42 typename Graph::vertex_descriptor t,
43 WeightMap wm, IndexMap im,
44 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::list<edge_descriptor> path_type;
51 typedef std::pair<weight_type, path_type> kr_type;
52 typedef filtered_graph<Graph, is_not_in_subset<es_type>> fg_type;
53
54 // The result.
55 std::list<std::pair<weight_type, path_type>> result;
56
57 // The set of excluded edges.
58 es_type excluded;
59 // The edge predicate.
60 is_not_in_subset<es_type> ep(excluded);
61 // The filtered graph.
62 fg_type fg(g, ep);
63
64 // In each iteration, we try to find a shortest path.
65 do
66 {
67 // If required, stop at the K-th shortest path.
68 if (K && result.size() == K.get())
69 break;
70
71 // This is the optional k-th result.
72 optional<kr_type> okr = custom_dijkstra_call(fg, s, t, wm, im);
73
74 if (!okr)
75 break;
76
77 // This is the k-th result.
78 const kr_type &kr = okr.get();
79
80 // Exclude the edges from the k-th result found.
81 for(auto const &e: kr.second)
82 excluded.insert(e);
83
84 result.push_back(kr);
85
86 } while(true);
87
88 return result;
89 }
90
91 //========================================================================
92 // A helper function to figure out the default weight map of the graph.
93 //========================================================================
94
95 template <typename Graph>
96 std::list<std::pair<typename property_map<Graph, edge_weight_t>::value_type,
97 std::list<typename Graph::edge_descriptor>>>
98 edge_disjoint_ksp(const Graph& g,
99 typename Graph::vertex_descriptor s,
100 typename Graph::vertex_descriptor t,
101 optional<unsigned> K = optional<unsigned>())
102 {
103 return edge_disjoint_ksp(g, s, t, get(edge_weight_t(), g),
104 get(vertex_index_t(), g), K);
105 }
106
107} // boost
108
109#endif /* BOOST_GRAPH_EDGE_DISJOINT_KSP */