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