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