Ticket #11804: edge_disjoint_ksp.5.hpp

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

the implementation - v5

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