RhodeCode

///\ingroup shortest_path

///\file

///\brief An algorithm for finding arc-disjoint paths between two

/// nodes having minimum total length.

#include <vector>

#include <lemon/bin_heap.h>

#include <lemon/path.h>

#include <lemon/list_graph.h>

#include <lemon/maps.h>

namespace lemon {

  /// having minimum total length.

  ///

  /// \ref lemon::Suurballe "Suurballe" implements an algorithm for

  /// finding arc-disjoint paths having minimum total length (cost)

  /// from a given source node to a given target node in a digraph.

  ///

  ///

  /// \tparam GR The digraph type the algorithm runs on.

  ///

  /// \warning Length values should be \e non-negative \e integers.

  ///

  /// \note For finding node-disjoint paths this algorithm can be used

#ifdef DOXYGEN

  template <typename GR, typename LEN>

#else

             typename LEN = typename GR::template ArcMap<int> >

#endif

  class Suurballe

  {

    TEMPLATE_DIGRAPH_TYPEDEFS(GR);

    /// The type of the digraph the algorithm runs on.

    typedef GR Digraph;

    /// The type of the length map.

    typedef LEN LengthMap;

    /// The type of the lengths.

    typedef typename LengthMap::Value Length;

    /// The type of the flow map.

    typedef typename Digraph::template ArcMap<int> FlowMap;

    /// The type of the potential map.

    typedef typename Digraph::template NodeMap<Length> PotentialMap;

    /// The type of the path structures.

  private:

    class ResidualDijkstra

    {

      typedef typename Digraph::template NodeMap<int> HeapCrossRef;

      typedef BinHeap<Length, HeapCrossRef> Heap;

    private:

      Node _s;

      Node _t;

    public:

      /// Constructor.

                        const FlowMap &flow,

                        const LengthMap &length,

                        PotentialMap &potential,

                        PredMap &pred,

                        Node s, Node t ) :

      /// \brief Run the algorithm. It returns \c true if a path is found

      /// from the source node to the target node.

      bool run() {

        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);

        Heap heap(heap_cross_ref);

  public:

    /// \brief Constructor.

    ///

    /// Constructor.

    ///

    /// \param length The length (cost) values of the arcs.

    /// Destructor.

    ~Suurballe() {

      if (_local_flow) delete _flow;

      if (_local_potential) delete _potential;

      delete _dijkstra;

    }

    /// \brief Set the flow map.

    ///

    /// This function sets the flow map.

    ///

    ///

    /// \return <tt>(*this)</tt>

    Suurballe& flowMap(FlowMap &map) {

      if (_local_flow) {

        delete _flow;

        _local_flow = false;

      return *this;

    }

    /// \brief Set the potential map.

    ///

    /// This function sets the potential map.

    ///

    ///

    /// \return <tt>(*this)</tt>

    Suurballe& potentialMap(PotentialMap &map) {

      if (_local_potential) {

        delete _potential;

        _local_potential = false;

    /// @{

    /// \brief Run the algorithm.

    ///

    /// This function runs the algorithm.

    ///

    /// \param k The number of paths to be found.

    ///

    /// \return \c k if there are at least \c k arc-disjoint paths from

    /// \c s to \c t in the digraph. Otherwise it returns the number of

    /// arc-disjoint paths found.

    ///

    /// \code

    ///   s.findPaths();

    /// \endcode

      findPaths();

      return _path_num;

    }

    /// \brief Initialize the algorithm.

    ///

    /// This function initializes the algorithm.

      // Initialize maps

      if (!_flow) {

        _flow = new FlowMap(_graph);

        _local_flow = true;

      }

      if (!_potential) {

        _potential = new PotentialMap(_graph);

        _local_potential = true;

      }

      for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;

      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;

    }

    ///

    /// This function executes the successive shortest path algorithm to

    /// arc-disjoint paths.

    ///

    /// \return \c k if there are at least \c k arc-disjoint paths from

    ///

    /// \pre \ref init() must be called before using this function.

      // Find shortest paths

      _path_num = 0;

      while (_path_num < k) {

        // Run Dijkstra

        if (!_dijkstra->run()) break;

        ++_path_num;

      }

      return _path_num;

    }

    /// \brief Compute the paths from the flow.

    ///

    ///

    /// \pre \ref init() and \ref findFlow() must be called before using

    /// this function.

    void findPaths() {

      FlowMap res_flow(_graph);

      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];

      paths.clear();

      paths.resize(_path_num);

      for (int i = 0; i < _path_num; ++i) {

    /// The results of the algorithm can be obtained using these

    /// functions.

    /// \n The algorithm should be executed before using them.

    /// @{

    /// found flow.

    ///

    /// the flow that is the union of the found arc-disjoint paths.

    ///

    /// \pre \ref run() or \ref findFlow() must be called before using

    /// this function.

    const FlowMap& flowMap() const {

      return *_flow;

    }

    /// \brief Return the potential of the given node.

    ///

    /// This function returns the potential of the given node.

    ///

    /// \pre \ref run() or \ref findFlow() must be called before using

    /// this function.

    Length potential(const Node& node) const {

      return (*_potential)[node];

    }

    ///

    ///

    /// \pre \ref run() or \ref findFlow() must be called before using

    /// this function.

    }

    /// \brief Return the number of the found paths.

    ///

    /// This function returns the number of the found paths.

    ///

    }

    /// \brief Return a const reference to the specified path.

    ///

    /// This function returns a const reference to the specified path.

    ///

    /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.

    ///

    /// \pre \ref run() or \ref findPaths() must be called before using

    /// this function.

    Path path(int i) const {

      return paths[i];

#include <iostream>

#include <lemon/list_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/path.h>

#include <lemon/suurballe.h>

#include "test_tools.h"

using namespace lemon;

char test_lgf[] =

  "@nodes\n"

  "@arcs\n"

  "@attributes\n"

  "source  1\n"

  "target 12\n"

  "@end\n";

// Check the feasibility of the flow

template <typename Digraph, typename FlowMap>

bool checkFlow( const Digraph& gr, const FlowMap& flow,

                typename Digraph::Node s, typename Digraph::Node t,

                int value )

{

// Check a path

template <typename Digraph, typename Path>

bool checkPath( const Digraph& gr, const Path& path,

                typename Digraph::Node s, typename Digraph::Node t)

{

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  Node n = s;

  for (int i = 0; i < path.length(); ++i) {

    if (gr.source(path.nth(i)) != n) return false;

    n = gr.target(path.nth(i));

  }

{

  DIGRAPH_TYPEDEFS(ListDigraph);

  // Read the test digraph

  ListDigraph digraph;

  ListDigraph::ArcMap<int> length(digraph);

  std::istringstream input(test_lgf);

  DigraphReader<ListDigraph>(digraph, input).

    run();

  // Find 2 paths

  {

          "The flow is not feasible");

    check(suurballe.totalLength() == 510, "The flow is not optimal");

    check(checkOptimality(digraph, length, suurballe.flowMap(),

                          suurballe.potentialMap()),

          "Wrong potentials");

    for (int i = 0; i < suurballe.pathNum(); ++i)

  }

  // Find 3 paths

  {

          "The flow is not feasible");

    check(suurballe.totalLength() == 1040, "The flow is not optimal");

    check(checkOptimality(digraph, length, suurballe.flowMap(),

                          suurballe.potentialMap()),

          "Wrong potentials");

    for (int i = 0; i < suurballe.pathNum(); ++i)

  }

  // Find 5 paths (only 3 can be found)

  {

          "The flow is not feasible");

    check(suurballe.totalLength() == 1040, "The flow is not optimal");

    check(checkOptimality(digraph, length, suurballe.flowMap(),

                          suurballe.potentialMap()),

          "Wrong potentials");

    for (int i = 0; i < suurballe.pathNum(); ++i)

  }

  return 0;

}

      ei!=arcs.rend();++ei)

    {

      Node a=g.u(*ei);

      Node b=g.v(*ei);

      g.erase(*ei);

      ConstMap<Arc,int> cegy(1);

      if(k<2 || sur.totalLength()>d)

        g.addEdge(a,b);

      else cnt++;

//       else std::cout << "Remove arc " << g.id(a) << "-" << g.id(b) << '\n';

    }

}

      Line li(pi->a,pi->b);

      EdgeIt e(g);

      for(;e!=INVALID && !cross(e,li);++e) ;

      Edge ne;

      if(e==INVALID) {

        ConstMap<Arc,int> cegy(1);

        if(k<2 || sur.totalLength()>d)

          {

            ne=g.addEdge(pi->a,pi->b);

            arcs.push_back(ne);

            cnt++;

          }