00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef LEMON_SUURBALLE_H
00018 #define LEMON_SUURBALLE_H
00019
00023
00024
00025 #include <lemon/maps.h>
00026 #include <vector>
00027 #include <lemon/min_cost_flow.h>
00028
00029 namespace lemon {
00030
00033
00057 template <typename Graph, typename LengthMap>
00058 class Suurballe{
00059
00060
00061 typedef typename LengthMap::Value Length;
00062
00063 typedef typename Graph::Node Node;
00064 typedef typename Graph::NodeIt NodeIt;
00065 typedef typename Graph::Edge Edge;
00066 typedef typename Graph::OutEdgeIt OutEdgeIt;
00067 typedef typename Graph::template EdgeMap<int> EdgeIntMap;
00068
00069 typedef ConstMap<Edge,int> ConstMap;
00070
00071 const Graph& G;
00072
00073 Node s;
00074 Node t;
00075
00076
00077
00078 ConstMap const1map;
00079
00080 MinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
00081
00082
00083 std::vector< std::vector<Edge> > paths;
00084
00085 public :
00086
00087
00095 Suurballe(Graph& _G, LengthMap& _length, Node _s, Node _t) :
00096 G(_G), s(_s), t(_t), const1map(1),
00097 min_cost_flow(_G, _length, const1map, _s, _t) { }
00098
00100
00108 int run(int k) {
00109 int i = min_cost_flow.run(k);
00110
00111
00112
00113
00114
00115
00116
00117
00118 EdgeIntMap reversed(G);
00119
00120 for(typename Graph::EdgeIt e(G); e!=INVALID; ++e)
00121 reversed[e] = min_cost_flow.getFlow()[e];
00122
00123 paths.clear();
00124
00125 paths.resize(k);
00126 for (int j=0; j<i; ++j){
00127 Node n=s;
00128
00129 while (n!=t){
00130
00131 OutEdgeIt e(G, n);
00132
00133 while (!reversed[e]){
00134 ++e;
00135 }
00136 n = G.target(e);
00137 paths[j].push_back(e);
00138
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