1.1 --- a/src/work/athos/minlengthpaths.h	Mon Apr 05 17:25:40 2004 +0000
     1.2 +++ b/src/work/athos/minlengthpaths.h	Mon Apr 05 17:33:04 2004 +0000
     1.3 @@ -1,108 +1,129 @@
     1.4  // -*- c++ -*-
     1.5 -#ifndef HUGO_SUURBALLE_H
     1.6 -#define HUGO_SUURBALLE_H
     1.7 +#ifndef HUGO_MINLENGTHPATHS_H
     1.8 +#define HUGO_MINLENGTHPATHS_H
     1.9  
    1.10  ///\file
    1.11 -///\brief Suurballe algorithm.
    1.12 +///\brief An algorithm for finding k paths of minimal total length.
    1.13  
    1.14  #include <iostream>
    1.15  #include <dijkstra.h>
    1.16  #include <graph_wrapper.h>
    1.17 +#include <maps.h>
    1.18 +
    1.19  namespace hugo {
    1.20  
    1.21  
    1.22 -///\brief Implementation of Suurballe's algorithm
    1.23 +///\brief Implementation of an algorithm for finding k paths between 2 nodes 
    1.24 +  /// of minimal total length 
    1.25  ///
    1.26 -/// The class \ref hugo::Suurballe "Suurballe" implements
    1.27 -/// Suurballe's algorithm which seeks for k edge-disjoint paths
    1.28 +/// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
    1.29 +/// an algorithm which finds k edge-disjoint paths
    1.30  /// from a given source node to a given target node in an
    1.31 -/// edge-weighted directed graph having minimal total cost.
    1.32 +/// edge-weighted directed graph having minimal total weigth (length).
    1.33  /// 
    1.34  /// 
    1.35  
    1.36    template <typename Graph, typename T, 
    1.37      typename LengthMap=typename Graph::EdgeMap<T> >
    1.38 -  class Suurballe {
    1.39 +  class MinLengthPaths {
    1.40  
    1.41  
    1.42 -    //Writing maps 
    1.43 -    class ConstMap {
    1.44 -    public :
    1.45 -      typedef int ValueType;
    1.46 -      typedef typename Graph::Edge KeyType;
    1.47 +//      class ConstMap {
    1.48 +//      public :
    1.49 +//        typedef int ValueType;
    1.50 +//        typedef typename Graph::Edge KeyType;
    1.51  
    1.52 -      int operator[](typename Graph::Edge e) const { 
    1.53 -	return 1;
    1.54 -      } 
    1.55 -    };
    1.56 -    /*
    1.57 -    //    template <typename Graph, typename T>
    1.58 -    class ModLengthMap {   
    1.59 -      typedef typename Graph::EdgeMap<T> EdgeMap;
    1.60 -      typedef typename Graph::NodeMap<T> NodeMap;
    1.61 -
    1.62 -      const EdgeMap &ol;   
    1.63 -      const NodeMap &pot;     
    1.64 -    public :
    1.65 -      typedef typename EdgeMap::KeyType KeyType;
    1.66 -      typedef typename EdgeMap::ValueType ValueType;
    1.67 -
    1.68 -      double operator[](typename Graph::EdgeIt e) const {     
    1.69 -	return 10;//ol.get(e)-pot.get(v)-pot.get(u);   
    1.70 -      }     
    1.71 -
    1.72 -      ModLengthMap(const EdgeMap &o,
    1.73 -		   const NodeMap &p) : 
    1.74 -	ol(o), pot(p){}; 
    1.75 -    };
    1.76 -    */
    1.77 +//        int operator[](typename Graph::Edge e) const { 
    1.78 +//  	return 1;
    1.79 +//        } 
    1.80 +//      };
    1.81  
    1.82  
    1.83      typedef typename Graph::Node Node;
    1.84      typedef typename Graph::NodeIt NodeIt;
    1.85      typedef typename Graph::Edge Edge;
    1.86      typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.87 +    typedef typename Graph::EdgeMap<int> EdgeIntMap;
    1.88 +
    1.89 +    typedef ConstMap<Edge,int> ConstMap;
    1.90 +
    1.91      typedef TrivGraphWrapper<const Graph> TrivGraphType;
    1.92 -    typedef ResGraphWrapper<TrivGraphType,int,typename Graph::EdgeMap<int>,
    1.93 +    typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap,
    1.94        ConstMap> ResGraphType;
    1.95  
    1.96 +
    1.97 +    //template <typename Graph, typename T>
    1.98 +    class ModLengthMap {   
    1.99 +      typedef typename ResGraphType::NodeMap<T> NodeMap;
   1.100 +      const ResGraphType& G;
   1.101 +      const EdgeIntMap& rev; 
   1.102 +      const LengthMap &ol;   
   1.103 +      const NodeMap &pot;     
   1.104 +    public :
   1.105 +      typedef typename LengthMap::KeyType KeyType;
   1.106 +      typedef typename LengthMap::ValueType ValueType;
   1.107 +
   1.108 +      ValueType operator[](typename ResGraphType::Edge e) const {     
   1.109 +	if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
   1.110 +	  ///\TODO This has to be removed
   1.111 +	  std::cout<<"Negative length!!"<<std::endl;
   1.112 +	}
   1.113 +	return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
   1.114 +      }     
   1.115 +
   1.116 +      ModLengthMap(  const ResGraphType& _G, const EdgeIntMap& _rev, 
   1.117 +		     const LengthMap &o,  const NodeMap &p) : 
   1.118 +	G(_G), rev(_rev), ol(o), pot(p){}; 
   1.119 +    };
   1.120 +    
   1.121 +
   1.122      const Graph& G;
   1.123      const LengthMap& length;
   1.124  
   1.125 +    //auxiliary variable
   1.126 +    //The value is 1 iff the edge is reversed
   1.127 +    EdgeIntMap reversed; 
   1.128  
   1.129 -    //auxiliary variables
   1.130 -    
   1.131 -    typename Graph::EdgeMap<int> reversed; 
   1.132 -    typename Graph::NodeMap<T> dijkstra_dist; 
   1.133      
   1.134    public :
   1.135      
   1.136  
   1.137 -    Suurballe(Graph& _G, LengthMap& _length) : G(_G), 
   1.138 -      length(_length), reversed(_G), dijkstra_dist(_G){ }
   1.139 +    MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), 
   1.140 +      length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
   1.141  
   1.142 -    ///Runs Suurballe's algorithm
   1.143 +    ///Runs the algorithm
   1.144      
   1.145 -    ///Runs Suurballe's algorithm
   1.146 -    ///Returns true iff there are k edge-disjoint paths from s to t
   1.147 -    bool run(Node s, Node t, int k) {
   1.148 +    ///Runs the algorithm
   1.149 +    ///Returns k if there are at least k edge-disjoint paths from s to t.
   1.150 +    ///Otherwise it returns the number of edge-disjoint paths from s to t.
   1.151 +    int run(Node s, Node t, int k) {
   1.152 +      ConstMap const1map(1);
   1.153  
   1.154 -      LengthMap mod_length_c = length;
   1.155 -      ConstMap const1map;
   1.156 -      //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap> 
   1.157 -      TrivGraphType ize(G);
   1.158 -      ResGraphType res_graph(ize, reversed, const1map);
   1.159 -      //ModLengthMap modified_length(length, dijkstra_dist);
   1.160 -      //Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, modified_length);
   1.161 -      //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
   1.162 -      Dijkstra<ResGraphType, LengthMap> dijkstra(res_graph, mod_length_c);
   1.163 +      ResGraphType res_graph(G, reversed, const1map);
   1.164 +
   1.165 +      //Initialize the copy of the Dijkstra potential to zero
   1.166 +      typename ResGraphType::NodeMap<T> dijkstra_dist(G);
   1.167 +      ModLengthMap mod_length( res_graph, reversed, length, dijkstra_dist);
   1.168 +
   1.169 +      Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
   1.170        
   1.171        for (int i=0; i<k; ++i){
   1.172  	dijkstra.run(s);
   1.173  	if (!dijkstra.reached(t)){
   1.174  	  //There is no k path from s to t
   1.175 -	  return false;
   1.176 +	  return ++i;
   1.177  	};
   1.178 +	
   1.179 +	{
   1.180 +	  //We have to copy the potential
   1.181 +	  typename ResGraphType::NodeIt n;
   1.182 +	  for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) {
   1.183 +	      dijkstra_dist[n] += dijkstra.distMap()[n];
   1.184 +	  }
   1.185 +	}
   1.186 +
   1.187 +
   1.188 +	/*
   1.189  	{
   1.190  	  //We have to copy the potential
   1.191  	  typename ResGraphType::EdgeIt e;
   1.192 @@ -113,7 +134,8 @@
   1.193  	      dijkstra.distMap()[res_graph.tail(e)];
   1.194  	  }
   1.195  	}
   1.196 -	
   1.197 +	*/
   1.198 +
   1.199  	//Reversing the sortest path
   1.200  	Node n=t;
   1.201  	Edge e;
   1.202 @@ -125,18 +147,18 @@
   1.203  
   1.204  	  
   1.205        }
   1.206 -      return true;
   1.207 +      return k;
   1.208      }
   1.209             
   1.210        
   1.211  
   1.212  
   1.213  
   1.214 -  };//class Suurballe
   1.215 +  };//class MinLengthPaths
   1.216  
   1.217  
   1.218  
   1.219  
   1.220  } //namespace hugo
   1.221  
   1.222 -#endif //HUGO_SUURBALLE_H
   1.223 +#endif //HUGO_MINLENGTHPATHS_H

     2.1 --- a/src/work/athos/suurballe.cc	Mon Apr 05 17:25:40 2004 +0000
     2.2 +++ b/src/work/athos/suurballe.cc	Mon Apr 05 17:33:04 2004 +0000
     2.3 @@ -4,7 +4,7 @@
     2.4  //#include <string>
     2.5  
     2.6  #include <list_graph.h>
     2.7 -#include <suurballe.h>
     2.8 +#include <minlengthpaths.h>
     2.9  
    2.10  using namespace hugo;
    2.11  
    2.12 @@ -119,7 +119,7 @@
    2.13  
    2.14    
    2.15    int k=3;
    2.16 -  Suurballe<ListGraph, int> surb_test(graph, length);
    2.17 +  MinLengthPaths<ListGraph, int> surb_test(graph, length);
    2.18    std::cout << surb_test.run(s,t,k)<<std::endl;
    2.19  
    2.20    return 0;