Bocs, veletlen volt.
authorathos
Mon, 10 May 2004 16:40:16 +0000
changeset 59926d6c7b5c367
parent 598 1faa5bec1717
child 600 09148a2c5ed2
Bocs, veletlen volt.
src/work/athos/obsolete
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/athos/obsolete	Mon May 10 16:40:16 2004 +0000
     1.3 @@ -0,0 +1,202 @@
     1.4 +// -*- c++ -*-
     1.5 +#ifndef HUGO_MINLENGTHPATHS_H
     1.6 +#define HUGO_MINLENGTHPATHS_H
     1.7 +
     1.8 +///\ingroup galgs
     1.9 +///\file
    1.10 +///\brief An algorithm for finding k paths of minimal total length.
    1.11 +
    1.12 +#include <iostream>
    1.13 +#include <dijkstra.h>
    1.14 +#include <graph_wrapper.h>
    1.15 +#include <maps.h>
    1.16 +#include <vector.h>
    1.17 +
    1.18 +
    1.19 +namespace hugo {
    1.20 +
    1.21 +/// \addtogroup galgs
    1.22 +/// @{
    1.23 +
    1.24 +  ///\brief Implementation of an algorithm for finding k paths between 2 nodes 
    1.25 +  /// of minimal total length 
    1.26 +  ///
    1.27 +  /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
    1.28 +  /// an algorithm for finding k edge-disjoint paths
    1.29 +  /// from a given source node to a given target node in an
    1.30 +  /// edge-weighted directed graph having minimal total weigth (length).
    1.31 +  ///
    1.32 +  ///\author Attila Bernath
    1.33 +  template <typename Graph, typename LengthMap>
    1.34 +  class MinLengthPaths {
    1.35 +
    1.36 +    typedef typename LengthMap::ValueType Length;
    1.37 +    
    1.38 +    typedef typename Graph::Node Node;
    1.39 +    typedef typename Graph::NodeIt NodeIt;
    1.40 +    typedef typename Graph::Edge Edge;
    1.41 +    typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.42 +    typedef typename Graph::template EdgeMap<int> EdgeIntMap;
    1.43 +
    1.44 +    typedef ConstMap<Edge,int> ConstMap;
    1.45 +
    1.46 +    typedef ResGraphWrapper<const Graph,int,ConstMap,EdgeIntMap> ResGraphType;
    1.47 +
    1.48 +    class ModLengthMap {   
    1.49 +      typedef typename ResGraphType::template NodeMap<Length> NodeMap;
    1.50 +      const ResGraphType& G;
    1.51 +      const EdgeIntMap& rev;
    1.52 +      const LengthMap &ol;
    1.53 +      const NodeMap &pot;
    1.54 +    public :
    1.55 +      typedef typename LengthMap::KeyType KeyType;
    1.56 +      typedef typename LengthMap::ValueType ValueType;
    1.57 +	
    1.58 +      ValueType operator[](typename ResGraphType::Edge e) const {     
    1.59 +	//if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
    1.60 +	//  std::cout<<"Negative length!!"<<std::endl;
    1.61 +	//}
    1.62 +	return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
    1.63 +      }     
    1.64 +	
    1.65 +      ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, 
    1.66 +		   const LengthMap &o,  const NodeMap &p) : 
    1.67 +	G(_G), rev(_rev), ol(o), pot(p){}; 
    1.68 +    };//ModLengthMap
    1.69 +
    1.70 +
    1.71 +    
    1.72 +
    1.73 +    const Graph& G;
    1.74 +    const LengthMap& length;
    1.75 +
    1.76 +    //auxiliary variables
    1.77 +
    1.78 +    //The value is 1 iff the edge is reversed. 
    1.79 +    //If the algorithm has finished, the edges of the seeked paths are 
    1.80 +    //exactly those that are reversed 
    1.81 +    EdgeIntMap reversed; 
    1.82 +    
    1.83 +    //Container to store found paths
    1.84 +    std::vector< std::vector<Edge> > paths;
    1.85 +    //typedef DirPath<Graph> DPath;
    1.86 +    //DPath paths;
    1.87 +
    1.88 +
    1.89 +    Length total_length;
    1.90 +
    1.91 +  public :
    1.92 +
    1.93 +
    1.94 +    MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), 
    1.95 +      length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
    1.96 +
    1.97 +    
    1.98 +    ///Runs the algorithm.
    1.99 +
   1.100 +    ///Runs the algorithm.
   1.101 +    ///Returns k if there are at least k edge-disjoint paths from s to t.
   1.102 +    ///Otherwise it returns the number of found edge-disjoint paths from s to t.
   1.103 +    int run(Node s, Node t, int k) {
   1.104 +      ConstMap const1map(1);
   1.105 +
   1.106 +
   1.107 +      //We need a residual graph, in which some of the edges are reversed
   1.108 +      ResGraphType res_graph(G, const1map, reversed);
   1.109 +
   1.110 +      //Initialize the copy of the Dijkstra potential to zero
   1.111 +      typename ResGraphType::template NodeMap<Length> dijkstra_dist(res_graph);
   1.112 +      ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
   1.113 +
   1.114 +      Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
   1.115 +
   1.116 +      int i;
   1.117 +      for (i=0; i<k; ++i){
   1.118 +	dijkstra.run(s);
   1.119 +	if (!dijkstra.reached(t)){
   1.120 +	  //There are no k paths from s to t
   1.121 +	  break;
   1.122 +	};
   1.123 +	
   1.124 +	{
   1.125 +	  //We have to copy the potential
   1.126 +	  typename ResGraphType::NodeIt n;
   1.127 +	  for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) {
   1.128 +	      dijkstra_dist[n] += dijkstra.distMap()[n];
   1.129 +	  }
   1.130 +	}
   1.131 +
   1.132 +
   1.133 +	//Reversing the sortest path
   1.134 +	Node n=t;
   1.135 +	Edge e;
   1.136 +	while (n!=s){
   1.137 +	  e = dijkstra.pred(n);
   1.138 +	  n = dijkstra.predNode(n);
   1.139 +	  reversed[e] = 1-reversed[e];
   1.140 +	}
   1.141 +
   1.142 +	  
   1.143 +      }
   1.144 +      
   1.145 +      //Let's find the paths
   1.146 +      //We put the paths into stl vectors (as an inner representation). 
   1.147 +      //In the meantime we lose the information stored in 'reversed'.
   1.148 +      //We suppose the lengths to be positive now.
   1.149 +
   1.150 +      //Meanwhile we put the total length of the found paths 
   1.151 +      //in the member variable total_length
   1.152 +      paths.clear();
   1.153 +      total_length=0;
   1.154 +      paths.resize(k);
   1.155 +      for (int j=0; j<i; ++j){
   1.156 +	Node n=s;
   1.157 +	OutEdgeIt e;
   1.158 +
   1.159 +	while (n!=t){
   1.160 +
   1.161 +
   1.162 +	  G.first(e,n);
   1.163 +	  
   1.164 +	  while (!reversed[e]){
   1.165 +	    G.next(e);
   1.166 +	  }
   1.167 +	  n = G.head(e);
   1.168 +	  paths[j].push_back(e);
   1.169 +	  total_length += length[e];
   1.170 +	  reversed[e] = 1-reversed[e];
   1.171 +	}
   1.172 +	
   1.173 +      }
   1.174 +
   1.175 +      return i;
   1.176 +    }
   1.177 +
   1.178 +    ///This function gives back the total length of the found paths.
   1.179 +    ///Assumes that \c run() has been run and nothing changed since then.
   1.180 +    Length totalLength(){
   1.181 +      return total_length;
   1.182 +    }
   1.183 +
   1.184 +    ///This function gives back the \c j-th path in argument p.
   1.185 +    ///Assumes that \c run() has been run and nothing changed since then.
   1.186 +    /// \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.
   1.187 +    template<typename DirPath>
   1.188 +    void getPath(DirPath& p, int j){
   1.189 +      p.clear();
   1.190 +      typename DirPath::Builder B(p);
   1.191 +      for(typename std::vector<Edge>::iterator i=paths[j].begin(); 
   1.192 +	  i!=paths[j].end(); ++i ){
   1.193 +	B.pushBack(*i);
   1.194 +      }
   1.195 +
   1.196 +      B.commit();
   1.197 +    }
   1.198 +
   1.199 +  }; //class MinLengthPaths
   1.200 +
   1.201 +  ///@}
   1.202 +
   1.203 +} //namespace hugo
   1.204 +
   1.205 +#endif //HUGO_MINLENGTHPATHS_H