suurballe.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
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     //Auxiliary variables
00079     //This is the capacity map for the mincostflow problem
00080     ConstMap const1map;
00081     //This MinCostFlow instance will actually solve the problem
00082     MinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
00083 
00084     //Container to store found paths
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       //Let's find the paths
00114       //We put the paths into stl vectors (as an inner representation). 
00115       //In the meantime we lose the information stored in 'reversed'.
00116       //We suppose the lengths to be positive now.
00117 
00118       //We don't want to change the flow of min_cost_flow, so we make a copy
00119       //The name here suggests that the flow has only 0/1 values.
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   }; //class Suurballe
00204 
00206 
00207 } //namespace lemon
00208 
00209 #endif //LEMON_SUURBALLE_H

Generated on Fri Feb 3 18:39:50 2006 for LEMON by  doxygen 1.4.6