Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

suurballe.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/suurballe.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
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     //Auxiliary variables
00077     //This is the capacity map for the mincostflow problem
00078     ConstMap const1map;
00079     //This MinCostFlow instance will actually solve the problem
00080     MinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
00081 
00082     //Container to store found paths
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       //Let's find the paths
00112       //We put the paths into stl vectors (as an inner representation). 
00113       //In the meantime we lose the information stored in 'reversed'.
00114       //We suppose the lengths to be positive now.
00115 
00116       //We don't want to change the flow of min_cost_flow, so we make a copy
00117       //The name here suggests that the flow has only 0/1 values.
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       //total_length=0;
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           //total_length += length[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 Sat Mar 19 10:58:41 2005 for LEMON by  doxygen 1.4.1