src/work/athos/obsolete
author athos
Mon, 10 May 2004 16:40:16 +0000
changeset 599 26d6c7b5c367
permissions -rw-r--r--
Bocs, veletlen volt.
     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 #include <iostream>
    10 #include <dijkstra.h>
    11 #include <graph_wrapper.h>
    12 #include <maps.h>
    13 #include <vector.h>
    14 
    15 
    16 namespace hugo {
    17 
    18 /// \addtogroup galgs
    19 /// @{
    20 
    21   ///\brief Implementation of an algorithm for finding k paths between 2 nodes 
    22   /// of minimal total length 
    23   ///
    24   /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
    25   /// an algorithm for finding k edge-disjoint paths
    26   /// from a given source node to a given target node in an
    27   /// edge-weighted directed graph having minimal total weigth (length).
    28   ///
    29   ///\author Attila Bernath
    30   template <typename Graph, typename LengthMap>
    31   class MinLengthPaths {
    32 
    33     typedef typename LengthMap::ValueType Length;
    34     
    35     typedef typename Graph::Node Node;
    36     typedef typename Graph::NodeIt NodeIt;
    37     typedef typename Graph::Edge Edge;
    38     typedef typename Graph::OutEdgeIt OutEdgeIt;
    39     typedef typename Graph::template EdgeMap<int> EdgeIntMap;
    40 
    41     typedef ConstMap<Edge,int> ConstMap;
    42 
    43     typedef ResGraphWrapper<const Graph,int,ConstMap,EdgeIntMap> ResGraphType;
    44 
    45     class ModLengthMap {   
    46       typedef typename ResGraphType::template NodeMap<Length> NodeMap;
    47       const ResGraphType& G;
    48       const EdgeIntMap& rev;
    49       const LengthMap &ol;
    50       const NodeMap &pot;
    51     public :
    52       typedef typename LengthMap::KeyType KeyType;
    53       typedef typename LengthMap::ValueType ValueType;
    54 	
    55       ValueType operator[](typename ResGraphType::Edge e) const {     
    56 	//if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
    57 	//  std::cout<<"Negative length!!"<<std::endl;
    58 	//}
    59 	return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
    60       }     
    61 	
    62       ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, 
    63 		   const LengthMap &o,  const NodeMap &p) : 
    64 	G(_G), rev(_rev), ol(o), pot(p){}; 
    65     };//ModLengthMap
    66 
    67 
    68     
    69 
    70     const Graph& G;
    71     const LengthMap& length;
    72 
    73     //auxiliary variables
    74 
    75     //The value is 1 iff the edge is reversed. 
    76     //If the algorithm has finished, the edges of the seeked paths are 
    77     //exactly those that are reversed 
    78     EdgeIntMap reversed; 
    79     
    80     //Container to store found paths
    81     std::vector< std::vector<Edge> > paths;
    82     //typedef DirPath<Graph> DPath;
    83     //DPath paths;
    84 
    85 
    86     Length total_length;
    87 
    88   public :
    89 
    90 
    91     MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), 
    92       length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
    93 
    94     
    95     ///Runs the algorithm.
    96 
    97     ///Runs the algorithm.
    98     ///Returns k if there are at least k edge-disjoint paths from s to t.
    99     ///Otherwise it returns the number of found edge-disjoint paths from s to t.
   100     int run(Node s, Node t, int k) {
   101       ConstMap const1map(1);
   102 
   103 
   104       //We need a residual graph, in which some of the edges are reversed
   105       ResGraphType res_graph(G, const1map, reversed);
   106 
   107       //Initialize the copy of the Dijkstra potential to zero
   108       typename ResGraphType::template NodeMap<Length> dijkstra_dist(res_graph);
   109       ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
   110 
   111       Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
   112 
   113       int i;
   114       for (i=0; i<k; ++i){
   115 	dijkstra.run(s);
   116 	if (!dijkstra.reached(t)){
   117 	  //There are no k paths from s to t
   118 	  break;
   119 	};
   120 	
   121 	{
   122 	  //We have to copy the potential
   123 	  typename ResGraphType::NodeIt n;
   124 	  for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) {
   125 	      dijkstra_dist[n] += dijkstra.distMap()[n];
   126 	  }
   127 	}
   128 
   129 
   130 	//Reversing the sortest path
   131 	Node n=t;
   132 	Edge e;
   133 	while (n!=s){
   134 	  e = dijkstra.pred(n);
   135 	  n = dijkstra.predNode(n);
   136 	  reversed[e] = 1-reversed[e];
   137 	}
   138 
   139 	  
   140       }
   141       
   142       //Let's find the paths
   143       //We put the paths into stl vectors (as an inner representation). 
   144       //In the meantime we lose the information stored in 'reversed'.
   145       //We suppose the lengths to be positive now.
   146 
   147       //Meanwhile we put the total length of the found paths 
   148       //in the member variable total_length
   149       paths.clear();
   150       total_length=0;
   151       paths.resize(k);
   152       for (int j=0; j<i; ++j){
   153 	Node n=s;
   154 	OutEdgeIt e;
   155 
   156 	while (n!=t){
   157 
   158 
   159 	  G.first(e,n);
   160 	  
   161 	  while (!reversed[e]){
   162 	    G.next(e);
   163 	  }
   164 	  n = G.head(e);
   165 	  paths[j].push_back(e);
   166 	  total_length += length[e];
   167 	  reversed[e] = 1-reversed[e];
   168 	}
   169 	
   170       }
   171 
   172       return i;
   173     }
   174 
   175     ///This function gives back the total length of the found paths.
   176     ///Assumes that \c run() has been run and nothing changed since then.
   177     Length totalLength(){
   178       return total_length;
   179     }
   180 
   181     ///This function gives back the \c j-th path in argument p.
   182     ///Assumes that \c run() has been run and nothing changed since then.
   183     /// \warning It is assumed that \c p is constructed to be a path of graph \c G. If \c j is greater than the result of previous \c run, then the result here will be an empty path.
   184     template<typename DirPath>
   185     void getPath(DirPath& p, int j){
   186       p.clear();
   187       typename DirPath::Builder B(p);
   188       for(typename std::vector<Edge>::iterator i=paths[j].begin(); 
   189 	  i!=paths[j].end(); ++i ){
   190 	B.pushBack(*i);
   191       }
   192 
   193       B.commit();
   194     }
   195 
   196   }; //class MinLengthPaths
   197 
   198   ///@}
   199 
   200 } //namespace hugo
   201 
   202 #endif //HUGO_MINLENGTHPATHS_H