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 |
|
---|
22 | namespace 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 */
|
---|