Ticket #11804: edge_disjoint_ksp.hpp

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

the implementation

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