00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_SUURBALLE_H
00020 #define LEMON_SUURBALLE_H
00021
00025
00026
00027 #include <lemon/maps.h>
00028 #include <vector>
00029 #include <lemon/min_cost_flow.h>
00030
00031 namespace lemon {
00032
00035
00059 template <typename Graph, typename LengthMap>
00060 class Suurballe{
00061
00062
00063 typedef typename LengthMap::Value Length;
00064
00065 typedef typename Graph::Node Node;
00066 typedef typename Graph::NodeIt NodeIt;
00067 typedef typename Graph::Edge Edge;
00068 typedef typename Graph::OutEdgeIt OutEdgeIt;
00069 typedef typename Graph::template EdgeMap<int> EdgeIntMap;
00070
00071 typedef ConstMap<Edge,int> ConstMap;
00072
00073 const Graph& G;
00074
00075 Node s;
00076 Node t;
00077
00078
00079
00080 ConstMap const1map;
00081
00082 MinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
00083
00084
00085 std::vector< std::vector<Edge> > paths;
00086
00087 public :
00088
00089
00097 Suurballe(Graph& _G, LengthMap& _length, Node _s, Node _t) :
00098 G(_G), s(_s), t(_t), const1map(1),
00099 min_cost_flow(_G, _length, const1map, _s, _t) { }
00100
00102
00110 int run(int k) {
00111 int i = min_cost_flow.run(k);
00112
00113
00114
00115
00116
00117
00118
00119
00120 EdgeIntMap reversed(G);
00121
00122 for(typename Graph::EdgeIt e(G); e!=INVALID; ++e)
00123 reversed[e] = min_cost_flow.getFlow()[e];
00124
00125 paths.clear();
00126 paths.resize(k);
00127 for (int j=0; j<i; ++j){
00128 Node n=s;
00129
00130 while (n!=t){
00131
00132 OutEdgeIt e(G, n);
00133
00134 while (!reversed[e]){
00135 ++e;
00136 }
00137 n = G.target(e);
00138 paths[j].push_back(e);
00139 reversed[e] = 1-reversed[e];
00140 }
00141
00142 }
00143 return i;
00144 }
00145
00146
00148
00150 Length totalLength(){
00151 return min_cost_flow.totalLength();
00152 }
00153
00155
00157 const EdgeIntMap &getFlow() const { return min_cost_flow.flow;}
00158
00160
00163 const EdgeIntMap &getPotential() const { return min_cost_flow.potential;}
00164
00166
00171 bool checkComplementarySlackness(){
00172 return min_cost_flow.checkComplementarySlackness();
00173 }
00174
00176
00187 template<typename Path>
00188 void getPath(Path& p, size_t j){
00189
00190 p.clear();
00191 if (j>paths.size()-1){
00192 return;
00193 }
00194 typename Path::Builder B(p);
00195 for(typename std::vector<Edge>::iterator i=paths[j].begin();
00196 i!=paths[j].end(); ++i ){
00197 B.pushBack(*i);
00198 }
00199
00200 B.commit();
00201 }
00202
00203 };
00204
00206
00207 }
00208
00209 #endif //LEMON_SUURBALLE_H