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