1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/athos/minlengthpaths.h	Mon Apr 05 14:56:32 2004 +0000
     1.3 @@ -0,0 +1,142 @@
     1.4 +// -*- c++ -*-
     1.5 +#ifndef HUGO_SUURBALLE_H
     1.6 +#define HUGO_SUURBALLE_H
     1.7 +
     1.8 +///\file
     1.9 +///\brief Suurballe algorithm.
    1.10 +
    1.11 +#include <iostream>
    1.12 +#include <dijkstra.h>
    1.13 +#include <graph_wrapper.h>
    1.14 +namespace hugo {
    1.15 +
    1.16 +
    1.17 +///\brief Implementation of Suurballe's algorithm
    1.18 +///
    1.19 +/// The class \ref hugo::Suurballe "Suurballe" implements
    1.20 +/// Suurballe's algorithm which seeks for k edge-disjoint paths
    1.21 +/// from a given source node to a given target node in an
    1.22 +/// edge-weighted directed graph having minimal total cost.
    1.23 +/// 
    1.24 +/// 
    1.25 +
    1.26 +  template <typename Graph, typename T, 
    1.27 +    typename LengthMap=typename Graph::EdgeMap<T> >
    1.28 +  class Suurballe {
    1.29 +
    1.30 +
    1.31 +    //Writing maps 
    1.32 +    class ConstMap {
    1.33 +    public :
    1.34 +      typedef int ValueType;
    1.35 +      typedef typename Graph::Edge KeyType;
    1.36 +
    1.37 +      int operator[](typename Graph::Edge e) const { 
    1.38 +	return 1;
    1.39 +      } 
    1.40 +    };
    1.41 +    /*
    1.42 +    //    template <typename Graph, typename T>
    1.43 +    class ModLengthMap {   
    1.44 +      typedef typename Graph::EdgeMap<T> EdgeMap;
    1.45 +      typedef typename Graph::NodeMap<T> NodeMap;
    1.46 +
    1.47 +      const EdgeMap &ol;   
    1.48 +      const NodeMap &pot;     
    1.49 +    public :
    1.50 +      typedef typename EdgeMap::KeyType KeyType;
    1.51 +      typedef typename EdgeMap::ValueType ValueType;
    1.52 +
    1.53 +      double operator[](typename Graph::EdgeIt e) const {     
    1.54 +	return 10;//ol.get(e)-pot.get(v)-pot.get(u);   
    1.55 +      }     
    1.56 +
    1.57 +      ModLengthMap(const EdgeMap &o,
    1.58 +		   const NodeMap &p) : 
    1.59 +	ol(o), pot(p){}; 
    1.60 +    };
    1.61 +    */
    1.62 +
    1.63 +
    1.64 +    typedef typename Graph::Node Node;
    1.65 +    typedef typename Graph::NodeIt NodeIt;
    1.66 +    typedef typename Graph::Edge Edge;
    1.67 +    typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.68 +    typedef TrivGraphWrapper<const Graph> TrivGraphType;
    1.69 +    typedef ResGraphWrapper<TrivGraphType,int,typename Graph::EdgeMap<int>,
    1.70 +      ConstMap> ResGraphType;
    1.71 +
    1.72 +    const Graph& G;
    1.73 +    const LengthMap& length;
    1.74 +
    1.75 +
    1.76 +    //auxiliary variables
    1.77 +    
    1.78 +    typename Graph::EdgeMap<int> reversed; 
    1.79 +    typename Graph::NodeMap<T> dijkstra_dist; 
    1.80 +    
    1.81 +  public :
    1.82 +    
    1.83 +
    1.84 +    Suurballe(Graph& _G, LengthMap& _length) : G(_G), 
    1.85 +      length(_length), reversed(_G), dijkstra_dist(_G){ }
    1.86 +
    1.87 +    ///Runs Suurballe's algorithm
    1.88 +    
    1.89 +    ///Runs Suurballe's algorithm
    1.90 +    ///Returns true iff there are k edge-disjoint paths from s to t
    1.91 +    bool run(Node s, Node t, int k) {
    1.92 +
    1.93 +      LengthMap mod_length_c = length;
    1.94 +      ConstMap const1map;
    1.95 +      //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap> 
    1.96 +      TrivGraphType ize(G);
    1.97 +      ResGraphType res_graph(ize, reversed, const1map);
    1.98 +      //ModLengthMap modified_length(length, dijkstra_dist);
    1.99 +      //Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, modified_length);
   1.100 +      //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
   1.101 +      Dijkstra<ResGraphType, LengthMap> dijkstra(res_graph, mod_length_c);
   1.102 +      
   1.103 +      for (int i=0; i<k; ++i){
   1.104 +	dijkstra.run(s);
   1.105 +	if (!dijkstra.reached(t)){
   1.106 +	  //There is no k path from s to t
   1.107 +	  return false;
   1.108 +	};
   1.109 +	{
   1.110 +	  //We have to copy the potential
   1.111 +	  typename ResGraphType::EdgeIt e;
   1.112 +	  for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
   1.113 +	    //dijkstra_dist[e] = dijkstra.distMap()[e];
   1.114 +	    mod_length_c[Edge(e)] = mod_length_c[Edge(e)] - 
   1.115 +	      dijkstra.distMap()[res_graph.head(e)] +  
   1.116 +	      dijkstra.distMap()[res_graph.tail(e)];
   1.117 +	  }
   1.118 +	}
   1.119 +	
   1.120 +	//Reversing the sortest path
   1.121 +	Node n=t;
   1.122 +	Edge e;
   1.123 +	while (n!=s){
   1.124 +	  e = dijkstra.pred(n);
   1.125 +	  n = dijkstra.predNode(n);
   1.126 +	  reversed[e] = 1-reversed[e];
   1.127 +	}
   1.128 +
   1.129 +	  
   1.130 +      }
   1.131 +      return true;
   1.132 +    }
   1.133 +           
   1.134 +      
   1.135 +
   1.136 +
   1.137 +
   1.138 +  };//class Suurballe
   1.139 +
   1.140 +
   1.141 +
   1.142 +
   1.143 +} //namespace hugo
   1.144 +
   1.145 +#endif //HUGO_SUURBALLE_H