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