Ticket #11804: edge_disjoint_ksp.4.hpp

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

the implementation - v4

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/dijkstra_shortest_paths.hpp>
27#include <boost/graph/filtered_graph.hpp>
28#include <boost/graph/visitors.hpp>
29#include <boost/optional.hpp>
30#include <boost/property_map/vector_property_map.hpp>
31#include <boost/utility/value_init.hpp>
32
33#include "custom_dijkstra_call.hpp"
34#include "exclude_filter.hpp"
35
36namespace boost {
37
38 //========================================================================
39 // The implementation of the k-shortest paths algorithm.
40 //========================================================================
41
42 template <typename Graph, typename WeightMap, typename IndexMap>
43 std::list<std::pair<typename WeightMap::value_type,
44 std::list<typename Graph::edge_descriptor>>>
45 edge_disjoint_ksp(const Graph& g,
46 typename Graph::vertex_descriptor s,
47 typename Graph::vertex_descriptor t,
48 WeightMap wm, IndexMap im,
49 optional<unsigned> K)
50 {
51 typedef typename Graph::vertex_descriptor vertex_descriptor;
52 typedef typename Graph::edge_descriptor edge_descriptor;
53 typedef typename WeightMap::value_type weight_type;
54 typedef std::list<edge_descriptor> path_type;
55 typedef std::pair<weight_type, path_type> kr_type;
56 typedef exclude_filter<edge_descriptor> eef_type;
57
58 // The result.
59 std::list<std::pair<weight_type, path_type>> result;
60
61 // The set of excluded edges.
62 std::set<edge_descriptor> excluded;
63 // The filter for excluding edges.
64 eef_type f(&excluded);
65 // The filtered graph type.
66 typedef filtered_graph<Graph, eef_type> fg_type;
67 // The filtered graph.
68 fg_type fg(g, f);
69
70 // In each iteration, we try to find a shortest path.
71 do
72 {
73 // If required, stop at the K-th shortest path.
74 if (K && result.size() == K.get())
75 break;
76
77 // This is the optional k-th result.
78 optional<kr_type> okr = custom_dijkstra_call(fg, s, t, wm, im);
79
80 if (!okr)
81 break;
82
83 // This is the k-th result.
84 const kr_type &kr = okr.get();
85
86 // Exclude the edges from the k-th result found.
87 for(auto const &e: kr.second)
88 excluded.insert(e);
89
90 result.push_back(kr);
91
92 } while(true);
93
94 return result;
95 }
96
97 //========================================================================
98 // A helper function to figure out the default weight map of the graph.
99 //========================================================================
100
101 template <typename Graph>
102 std::list<std::pair<typename property_map<Graph, edge_weight_t>::value_type,
103 std::list<typename Graph::edge_descriptor>>>
104 edge_disjoint_ksp(const Graph& g,
105 typename Graph::vertex_descriptor s,
106 typename Graph::vertex_descriptor t,
107 optional<unsigned> K = optional<unsigned>())
108 {
109 return edge_disjoint_ksp(g, s, t, get(edge_weight_t(), g),
110 get(vertex_index_t(), g), K);
111 }
112
113} // boost
114
115#endif /* BOOST_GRAPH_EDGE_DISJOINT_KSP */