Ticket #11804: edge_disjoint_ksp.2.hpp

File edge_disjoint_ksp.2.hpp, 3.8 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
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#ifndef BOOST_GRAPH_EDGE_DISJOINT_KSP
11#define BOOST_GRAPH_EDGE_DISJOINT_KSP
12
13#include <list>
14#include <set>
15
16#include <boost/graph/dijkstra_shortest_paths.hpp>
17#include <boost/graph/filtered_graph.hpp>
18#include <boost/graph/visitors.hpp>
19#include <boost/property_map/vector_property_map.hpp>
20#include <boost/utility/value_init.hpp>
21
22namespace boost {
23
24 // Exclude edge filter
25 template <typename Graph>
26 struct edksp_filter
27 {
28 typedef typename Graph::edge_descriptor edge_descriptor;
29 typedef typename std::set<edge_descriptor> edge_set;
30
31 // The filter must be default-constructible, so it is.
32 edksp_filter(): m_excluded() {};
33
34 edksp_filter(const edge_set *excluded): m_excluded(excluded) {};
35
36 inline bool operator()(const edge_descriptor &e) const
37 {
38 return m_excluded->count(e) == 0;
39 }
40
41 const edge_set *m_excluded;
42 };
43
44 template <typename Graph, typename Weight>
45 std::list<std::pair<typename Weight::value_type,
46 std::list<typename Graph::edge_descriptor>>>
47 edge_disjoint_ksp(const Graph& g,
48 typename graph_traits<Graph>::vertex_descriptor s,
49 typename graph_traits<Graph>::vertex_descriptor t,
50 Weight wm)
51 {
52 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
53 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
54 typedef typename std::list<typename Graph::edge_descriptor> path_type;
55 typedef typename Weight::value_type weight_type;
56
57 // The result.
58 std::list<std::pair<weight_type, path_type>> result;
59
60 // The set of excluded edges.
61 std::set<edge_descriptor> excluded;
62 // The filter for excluding edges.
63 edksp_filter<Graph> f(&excluded);
64 // The filtered graph type.
65 typedef boost::filtered_graph<Graph, edksp_filter<Graph> > fg_type;
66 // The filtered graph.
67 fg_type fg(g, f);
68
69 // In each iteration, we try to find a shortest path.
70 do
71 {
72 boost::vector_property_map<edge_descriptor> pred(num_vertices(g));
73
74 boost::dijkstra_shortest_paths
75 (fg, s,
76 visitor(make_dijkstra_visitor(record_edge_predecessors(pred, on_edge_relaxed()))));
77
78 // Break the loop if no solution was found.
79 if (pred[t] == edge_descriptor())
80 break;
81
82 // The cost of the shortest path.
83 value_initialized<weight_type> cost;
84 // The path found.
85 path_type path;
86
87 // Trace the solution to the source.
88 vertex_descriptor c = t;
89 while (c != s)
90 {
91 const edge_descriptor &e = pred[c];
92 // Build the path.
93 path.push_front(e);
94 // Exclude the edge, so that it's not used in the next
95 // shortest paths.
96 excluded.insert(e);
97 // Calculate the cost of the path.
98 cost += get(wm, e);
99 // Find the predecessing vertex.
100 c = source(e, g);
101 }
102
103 result.push_back(std::make_pair(cost, path));
104
105 } while(true);
106
107 return result;
108 }
109
110 template <typename Graph>
111 std::list<std::pair<typename property_map<Graph, edge_weight_t>::value_type,
112 std::list<typename Graph::edge_descriptor>>>
113 edge_disjoint_ksp(Graph& g,
114 typename graph_traits<Graph>::vertex_descriptor s,
115 typename graph_traits<Graph>::vertex_descriptor t)
116 {
117 return edge_disjoint_ksp(g, s, t, get(edge_weight_t(), g));
118 }
119
120} // boost
121
122#endif /* BOOST_GRAPH_EDGE_DISJOINT_KSP */