source: lemon-0.x/src/work/athos/minlengthpaths.h @ 302:2c52fc9781d4

// -*- c++ -*-
#ifndef HUGO_SUURBALLE_H
#define HUGO_SUURBALLE_H

///\file
///\brief Suurballe algorithm.

#include <iostream>
#include <dijkstra.h>
#include <graph_wrapper.h>
namespace hugo {


///\brief Implementation of Suurballe's algorithm
///
/// The class \ref hugo::Suurballe "Suurballe" implements
/// Suurballe's algorithm which seeks for k edge-disjoint paths
/// from a given source node to a given target node in an
/// edge-weighted directed graph having minimal total cost.
/// 
/// 

  template <typename Graph, typename T, 
    typename LengthMap=typename Graph::EdgeMap<T> >
  class Suurballe {


    //Writing maps 
    class ConstMap {
    public :
      typedef int ValueType;
      typedef typename Graph::Edge KeyType;

      int operator[](typename Graph::Edge e) const { 
        return 1;
      } 
    };
    /*
    //    template <typename Graph, typename T>
    class ModLengthMap {   
      typedef typename Graph::EdgeMap<T> EdgeMap;
      typedef typename Graph::NodeMap<T> NodeMap;

      const EdgeMap &ol;   
      const NodeMap &pot;     
    public :
      typedef typename EdgeMap::KeyType KeyType;
      typedef typename EdgeMap::ValueType ValueType;

      double operator[](typename Graph::EdgeIt e) const {     
        return 10;//ol.get(e)-pot.get(v)-pot.get(u);   
      }     

      ModLengthMap(const EdgeMap &o,
                   const NodeMap &p) : 
        ol(o), pot(p){}; 
    };
    */


    typedef typename Graph::Node Node;
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::Edge Edge;
    typedef typename Graph::OutEdgeIt OutEdgeIt;
    typedef TrivGraphWrapper<const Graph> TrivGraphType;
    typedef ResGraphWrapper<TrivGraphType,int,typename Graph::EdgeMap<int>,
      ConstMap> ResGraphType;

    const Graph& G;
    const LengthMap& length;


    //auxiliary variables
    
    typename Graph::EdgeMap<int> reversed; 
    typename Graph::NodeMap<T> dijkstra_dist; 
    
  public :
    

    Suurballe(Graph& _G, LengthMap& _length) : G(_G), 
      length(_length), reversed(_G), dijkstra_dist(_G){ }

    ///Runs Suurballe's algorithm
    
    ///Runs Suurballe's algorithm
    ///Returns true iff there are k edge-disjoint paths from s to t
    bool run(Node s, Node t, int k) {

      LengthMap mod_length_c = length;
      ConstMap const1map;
      //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap> 
      TrivGraphType ize(G);
      ResGraphType res_graph(ize, reversed, const1map);
      //ModLengthMap modified_length(length, dijkstra_dist);
      //Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, modified_length);
      //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
      Dijkstra<ResGraphType, LengthMap> dijkstra(res_graph, mod_length_c);
      
      for (int i=0; i<k; ++i){
        dijkstra.run(s);
        if (!dijkstra.reached(t)){
          //There is no k path from s to t
          return false;
        };
        {
          //We have to copy the potential
          typename ResGraphType::EdgeIt e;
          for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
            //dijkstra_dist[e] = dijkstra.distMap()[e];
            mod_length_c[Edge(e)] = mod_length_c[Edge(e)] - 
              dijkstra.distMap()[res_graph.head(e)] +  
              dijkstra.distMap()[res_graph.tail(e)];
          }
        }
        
        //Reversing the sortest path
        Node n=t;
        Edge e;
        while (n!=s){
          e = dijkstra.pred(n);
          n = dijkstra.predNode(n);
          reversed[e] = 1-reversed[e];
        }

          
      }
      return true;
    }
           
      



  };//class Suurballe




} //namespace hugo

#endif //HUGO_SUURBALLE_H