alpar@896
|
1 |
// -*- c++ -*-
|
alpar@896
|
2 |
#ifndef HUGO_MINLENGTHPATHS_H
|
alpar@896
|
3 |
#define HUGO_MINLENGTHPATHS_H
|
alpar@896
|
4 |
|
alpar@896
|
5 |
///\ingroup flowalgs
|
alpar@896
|
6 |
///\file
|
alpar@896
|
7 |
///\brief An algorithm for finding k paths of minimal total length.
|
alpar@896
|
8 |
|
alpar@896
|
9 |
|
alpar@896
|
10 |
#include <hugo/maps.h>
|
alpar@896
|
11 |
#include <vector>
|
alpar@896
|
12 |
#include <hugo/min_cost_flows.h>
|
alpar@896
|
13 |
|
alpar@896
|
14 |
namespace hugo {
|
alpar@896
|
15 |
|
alpar@896
|
16 |
/// \addtogroup flowalgs
|
alpar@896
|
17 |
/// @{
|
alpar@896
|
18 |
|
alpar@896
|
19 |
///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes
|
alpar@896
|
20 |
/// of minimal total length
|
alpar@896
|
21 |
///
|
alpar@896
|
22 |
/// The class \ref hugo::MinLengthPaths implements
|
alpar@896
|
23 |
/// an algorithm for finding k edge-disjoint paths
|
alpar@896
|
24 |
/// from a given source node to a given target node in an
|
alpar@896
|
25 |
/// edge-weighted directed graph having minimal total weight (length).
|
alpar@896
|
26 |
///
|
alpar@896
|
27 |
///\warning Length values should be nonnegative.
|
alpar@896
|
28 |
///
|
alpar@896
|
29 |
///\param Graph The directed graph type the algorithm runs on.
|
alpar@896
|
30 |
///\param LengthMap The type of the length map (values should be nonnegative).
|
alpar@896
|
31 |
///
|
alpar@896
|
32 |
///\author Attila Bernath
|
alpar@896
|
33 |
template <typename Graph, typename LengthMap>
|
alpar@896
|
34 |
class MinLengthPaths{
|
alpar@896
|
35 |
|
alpar@896
|
36 |
|
alpar@896
|
37 |
typedef typename LengthMap::ValueType Length;
|
alpar@896
|
38 |
|
alpar@896
|
39 |
typedef typename Graph::Node Node;
|
alpar@896
|
40 |
typedef typename Graph::NodeIt NodeIt;
|
alpar@896
|
41 |
typedef typename Graph::Edge Edge;
|
alpar@896
|
42 |
typedef typename Graph::OutEdgeIt OutEdgeIt;
|
alpar@896
|
43 |
typedef typename Graph::template EdgeMap<int> EdgeIntMap;
|
alpar@896
|
44 |
|
alpar@896
|
45 |
typedef ConstMap<Edge,int> ConstMap;
|
alpar@896
|
46 |
|
alpar@896
|
47 |
//Input
|
alpar@896
|
48 |
const Graph& G;
|
alpar@896
|
49 |
|
alpar@896
|
50 |
//Auxiliary variables
|
alpar@896
|
51 |
//This is the capacity map for the mincostflow problem
|
alpar@896
|
52 |
ConstMap const1map;
|
alpar@896
|
53 |
//This MinCostFlows instance will actually solve the problem
|
alpar@896
|
54 |
MinCostFlows<Graph, LengthMap, ConstMap> mincost_flow;
|
alpar@896
|
55 |
|
alpar@896
|
56 |
//Container to store found paths
|
alpar@896
|
57 |
std::vector< std::vector<Edge> > paths;
|
alpar@896
|
58 |
|
alpar@896
|
59 |
public :
|
alpar@896
|
60 |
|
alpar@896
|
61 |
|
alpar@896
|
62 |
/// The constructor of the class.
|
alpar@896
|
63 |
|
alpar@896
|
64 |
///\param _G The directed graph the algorithm runs on.
|
alpar@896
|
65 |
///\param _length The length (weight or cost) of the edges.
|
alpar@896
|
66 |
MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
|
alpar@896
|
67 |
const1map(1), mincost_flow(_G, _length, const1map){}
|
alpar@896
|
68 |
|
alpar@896
|
69 |
///Runs the algorithm.
|
alpar@896
|
70 |
|
alpar@896
|
71 |
///Runs the algorithm.
|
alpar@896
|
72 |
///Returns k if there are at least k edge-disjoint paths from s to t.
|
alpar@896
|
73 |
///Otherwise it returns the number of found edge-disjoint paths from s to t.
|
alpar@896
|
74 |
///
|
alpar@896
|
75 |
///\param s The source node.
|
alpar@896
|
76 |
///\param t The target node.
|
alpar@896
|
77 |
///\param k How many paths are we looking for?
|
alpar@896
|
78 |
///
|
alpar@896
|
79 |
int run(Node s, Node t, int k) {
|
alpar@896
|
80 |
|
alpar@896
|
81 |
int i = mincost_flow.run(s,t,k);
|
alpar@896
|
82 |
|
alpar@896
|
83 |
|
alpar@896
|
84 |
//Let's find the paths
|
alpar@896
|
85 |
//We put the paths into stl vectors (as an inner representation).
|
alpar@896
|
86 |
//In the meantime we lose the information stored in 'reversed'.
|
alpar@896
|
87 |
//We suppose the lengths to be positive now.
|
alpar@896
|
88 |
|
alpar@896
|
89 |
//We don't want to change the flow of mincost_flow, so we make a copy
|
alpar@896
|
90 |
//The name here suggests that the flow has only 0/1 values.
|
alpar@896
|
91 |
EdgeIntMap reversed(G);
|
alpar@896
|
92 |
|
alpar@896
|
93 |
for(typename Graph::EdgeIt e(G); e!=INVALID; ++e)
|
alpar@896
|
94 |
reversed[e] = mincost_flow.getFlow()[e];
|
alpar@896
|
95 |
|
alpar@896
|
96 |
paths.clear();
|
alpar@896
|
97 |
//total_length=0;
|
alpar@896
|
98 |
paths.resize(k);
|
alpar@896
|
99 |
for (int j=0; j<i; ++j){
|
alpar@896
|
100 |
Node n=s;
|
alpar@896
|
101 |
OutEdgeIt e;
|
alpar@896
|
102 |
|
alpar@896
|
103 |
while (n!=t){
|
alpar@896
|
104 |
|
alpar@896
|
105 |
|
alpar@896
|
106 |
G.first(e,n);
|
alpar@896
|
107 |
|
alpar@896
|
108 |
while (!reversed[e]){
|
alpar@896
|
109 |
++e;
|
alpar@896
|
110 |
}
|
alpar@896
|
111 |
n = G.head(e);
|
alpar@896
|
112 |
paths[j].push_back(e);
|
alpar@896
|
113 |
//total_length += length[e];
|
alpar@896
|
114 |
reversed[e] = 1-reversed[e];
|
alpar@896
|
115 |
}
|
alpar@896
|
116 |
|
alpar@896
|
117 |
}
|
alpar@896
|
118 |
return i;
|
alpar@896
|
119 |
}
|
alpar@896
|
120 |
|
alpar@896
|
121 |
|
alpar@896
|
122 |
///Returns the total length of the paths
|
alpar@896
|
123 |
|
alpar@896
|
124 |
///This function gives back the total length of the found paths.
|
alpar@896
|
125 |
///\pre \ref run() must
|
alpar@896
|
126 |
///be called before using this function.
|
alpar@896
|
127 |
Length totalLength(){
|
alpar@896
|
128 |
return mincost_flow.totalLength();
|
alpar@896
|
129 |
}
|
alpar@896
|
130 |
|
alpar@896
|
131 |
///Returns the found flow.
|
alpar@896
|
132 |
|
alpar@896
|
133 |
///This function returns a const reference to the EdgeMap \c flow.
|
alpar@896
|
134 |
///\pre \ref run() must
|
alpar@896
|
135 |
///be called before using this function.
|
alpar@896
|
136 |
const EdgeIntMap &getFlow() const { return mincost_flow.flow;}
|
alpar@896
|
137 |
|
alpar@896
|
138 |
/// Returns the optimal dual solution
|
alpar@896
|
139 |
|
alpar@896
|
140 |
///This function returns a const reference to the NodeMap
|
alpar@896
|
141 |
///\c potential (the dual solution).
|
alpar@896
|
142 |
/// \pre \ref run() must be called before using this function.
|
alpar@896
|
143 |
const EdgeIntMap &getPotential() const { return mincost_flow.potential;}
|
alpar@896
|
144 |
|
alpar@896
|
145 |
///Checks whether the complementary slackness holds.
|
alpar@896
|
146 |
|
alpar@896
|
147 |
///This function checks, whether the given solution is optimal.
|
alpar@896
|
148 |
///It should return true after calling \ref run()
|
alpar@896
|
149 |
///Currently this function only checks optimality,
|
alpar@896
|
150 |
///doesn't bother with feasibility
|
alpar@896
|
151 |
///It is meant for testing purposes.
|
alpar@896
|
152 |
///
|
alpar@896
|
153 |
bool checkComplementarySlackness(){
|
alpar@896
|
154 |
return mincost_flow.checkComplementarySlackness();
|
alpar@896
|
155 |
}
|
alpar@896
|
156 |
|
alpar@896
|
157 |
///Read the found paths.
|
alpar@896
|
158 |
|
alpar@896
|
159 |
///This function gives back the \c j-th path in argument p.
|
alpar@896
|
160 |
///Assumes that \c run() has been run and nothing changed since then.
|
alpar@896
|
161 |
/// \warning It is assumed that \c p is constructed to
|
alpar@896
|
162 |
///be a path of graph \c G.
|
alpar@896
|
163 |
///If \c j is not less than the result of previous \c run,
|
alpar@896
|
164 |
///then the result here will be an empty path (\c j can be 0 as well).
|
alpar@896
|
165 |
///
|
alpar@896
|
166 |
///\param Path The type of the path structure to put the result to (must meet hugo path concept).
|
alpar@896
|
167 |
///\param p The path to put the result to
|
alpar@896
|
168 |
///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively)
|
alpar@896
|
169 |
template<typename Path>
|
alpar@896
|
170 |
void getPath(Path& p, size_t j){
|
alpar@896
|
171 |
|
alpar@896
|
172 |
p.clear();
|
alpar@896
|
173 |
if (j>paths.size()-1){
|
alpar@896
|
174 |
return;
|
alpar@896
|
175 |
}
|
alpar@896
|
176 |
typename Path::Builder B(p);
|
alpar@896
|
177 |
for(typename std::vector<Edge>::iterator i=paths[j].begin();
|
alpar@896
|
178 |
i!=paths[j].end(); ++i ){
|
alpar@896
|
179 |
B.pushBack(*i);
|
alpar@896
|
180 |
}
|
alpar@896
|
181 |
|
alpar@896
|
182 |
B.commit();
|
alpar@896
|
183 |
}
|
alpar@896
|
184 |
|
alpar@896
|
185 |
}; //class MinLengthPaths
|
alpar@896
|
186 |
|
alpar@896
|
187 |
///@}
|
alpar@896
|
188 |
|
alpar@896
|
189 |
} //namespace hugo
|
alpar@896
|
190 |
|
alpar@896
|
191 |
#endif //HUGO_MINLENGTHPATHS_H
|