1.1 --- a/src/work/athos/obsolete Mon May 10 16:40:16 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,202 +0,0 @@
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