athos@276: // -*- c++ -*-
athos@276: #ifndef HUGO_SUURBALLE_H
athos@276: #define HUGO_SUURBALLE_H
athos@276: 
athos@276: #include <iostream>
athos@276: #include <dijkstra.h>
athos@276: #include <graph_wrapper.h>
athos@276: namespace hugo {
athos@276: 
athos@276: 
athos@276: ///\brief Implementation of Suurballe's algorithm
athos@276: ///
athos@276: /// The class \ref hugo::Suurballe "Suurballe" implements
athos@276: /// Suurballe's algorithm which seeks for k edge-disjoint paths
athos@276: /// from a given source node to a given target node in an
athos@276: /// edge-weighted directed graph having minimal total cost.
athos@276: /// 
athos@276: /// 
athos@276: 
athos@276: 
athos@276:   template <typename Graph, typename T, 
athos@276:     typename LengthMap=typename Graph::EdgeMap<T> >
athos@276:   class Suurballe {
athos@276: 
athos@276: 
athos@276:     //Writing maps 
athos@276:     class ConstMap {
athos@276:     public :
athos@276:       typedef int ValueType;
athos@276:       int operator[](typename Graph::Edge e) const { 
athos@276: 	return 1;
athos@276:       } 
athos@276:     };
athos@276:     /*
athos@276:     //    template <typename Graph, typename T>
athos@276:     class ModLengthMap {   
athos@276:       typedef typename Graph::EdgeMap<T> EdgeMap;
athos@276:       typedef typename Graph::NodeMap<T> NodeMap;
athos@276: 
athos@276:       const EdgeMap &ol;   
athos@276:       const NodeMap &pot;     
athos@276:     public :
athos@276:       typedef typename EdgeMap::KeyType KeyType;
athos@276:       typedef typename EdgeMap::ValueType ValueType;
athos@276: 
athos@276:       double operator[](typename Graph::EdgeIt e) const {     
athos@276: 	return 10;//ol.get(e)-pot.get(v)-pot.get(u);   
athos@276:       }     
athos@276: 
athos@276:       ModLengthMap(const EdgeMap &o,
athos@276: 		   const NodeMap &p) : 
athos@276: 	ol(o), pot(p){}; 
athos@276:     };
athos@276:     */
athos@276: 
athos@276: 
athos@276:     typedef typename Graph::Node Node;
athos@276:     typedef typename Graph::NodeIt NodeIt;
athos@276:     typedef typename Graph::Edge Edge;
athos@276:     typedef typename Graph::OutEdgeIt OutEdgeIt;
athos@276:     typedef ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap > ResGraphType;
athos@276: 
athos@276:     const Graph& G;
athos@276:     const LengthMap& length;
athos@276: 
athos@276: 
athos@276:     //auxiliary variables
athos@276:     
athos@276:     typename Graph::EdgeMap<int> reversed; 
athos@276:     typename Graph::NodeMap<T> dijkstra_dist; 
athos@276:     
athos@276:   public :
athos@276:     
athos@276: 
athos@276:     Suurballe(Graph& _G, LengthMap& _length) : G(_G), 
athos@276:       length(_length), reversed(_G), dijkstra_dist(_G){ }
athos@276: 
athos@276:     ///Runs Suurballe's algorithm
athos@276:     ///Returns true iff there are k edge-disjoint paths from s to t
athos@276:     bool run(Node s, Node t, int k) {
athos@276: 
athos@276:       LengthMap mod_length_c = length;
athos@276:       ConstMap const1map;
athos@276:       //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap> 
athos@276:       ResGraphType res_graph(G, reversed, const1map);
athos@276:       //ModLengthMap modified_length(length, dijkstra_dist);
athos@276:       //Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, modified_length);
athos@276:       //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
athos@276:       Dijkstra<ResGraphType, LengthMap> dijkstra(res_graph, mod_length_c);
athos@276:       
athos@276:       for (int i=0; i<k; ++i){
athos@276: 	dijkstra.run(s);
athos@276: 	if (!dijkstra.reached(t)){
athos@276: 	  //There is no k path from s to t
athos@276: 	  return false;
athos@276: 	};
athos@276: 	{
athos@276: 	  //We have to copy the potential
athos@276: 	  typename ResGraphType::EdgeIt e;
athos@276: 	  for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
athos@276: 	    //dijkstra_dist[e] = dijkstra.distMap()[e];
athos@276: 	    mod_length_c[Edge(e)] = mod_length_c[Edge(e)] - 
athos@276: 	      dijkstra.distMap()[res_graph.head(e)] +  
athos@276: 	      dijkstra.distMap()[res_graph.tail(e)];
athos@276: 	  }
athos@276: 	}
athos@276: 	
athos@276: 	//Reversing the sortest path
athos@276: 	Node n=t;
athos@276: 	Edge e;
athos@276: 	while (n!=s){
athos@276: 	  e=dijkstra.pred(n);
athos@276: 	  n=dijkstra.predNode(n);
athos@276: 	  reversed[e] = 1-reversed[e];
athos@276: 	}
athos@276: 
athos@276: 	  
athos@276:       }
athos@276:       return true;
athos@276:     }
athos@276:            
athos@276:       
athos@276: 
athos@276: 
athos@276: 
athos@276:   };//class Suurballe
athos@276: 
athos@276: 
athos@276: 
athos@276: 
athos@276: } //namespace hugo
athos@276: 
athos@276: #endif //HUGO_SUURBALLE_H