RhodeCode

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_SUURBALLE_H

#define LEMON_SUURBALLE_H

///\ingroup shortest_path

///\file

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

/// nodes having minimum total length.

#include <vector>

#include <limits>

#include <lemon/bin_heap.h>

#include <lemon/path.h>

#include <lemon/list_graph.h>

#include <lemon/maps.h>

namespace lemon {

  /// \addtogroup shortest_path

  /// @{

  /// \brief Algorithm for finding arc-disjoint paths between two nodes

  /// 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.

  ///

  /// Note that this problem is a special case of the \ref min_cost_flow

  /// "minimum cost flow problem". This implementation is actually an

  /// efficient specialized version of the \ref CapacityScaling

  /// "successive shortest path" algorithm directly for this problem.

  /// Therefore this class provides query functions for flow values and

  /// node potentials (the dual solution) just like the minimum cost flow

  /// algorithms.

  ///

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

  /// \tparam LEN The type of the length map.

    /// 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;

#ifdef DOXYGEN

    /// The type of the flow map.

    typedef GR::ArcMap<int> FlowMap;

    /// The type of the potential map.

    typedef GR::NodeMap<Length> PotentialMap;

#else

    /// 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;

#endif

    /// The type of the path structures.

    typedef SimplePath<GR> Path;

  private:

    // ResidualDijkstra is a special implementation of the

    // Dijkstra algorithm for finding shortest paths in the

    // residual network with respect to the reduced arc lengths

    // and modifying the node potentials according to the

    // distance of the nodes.

    class ResidualDijkstra

    {

    private:

      const Digraph &_graph;

      const LengthMap &_length;

      const FlowMap &_flow;

      PotentialMap &_pi;

      PredMap &_pred;

      Node _s;

      Node _t;

      PotentialMap _dist;

      std::vector<Node> _proc_nodes;

    public:

      // Constructor

      ResidualDijkstra(Suurballe &srb) :

        _graph(srb._graph), _length(srb._length),

        _flow(*srb._flow), _pi(*srb._potential), _pred(srb._pred), 

        _s(srb._s), _t(srb._t), _dist(_graph) {}

      // Run the algorithm and return true if a path is found

      // from the source node to the target node.

      bool run(int cnt) {

    // The digraph the algorithm runs on

    const Digraph &_graph;

    // The length map

    const LengthMap &_length;

    // Arc map of the current flow

    FlowMap *_flow;

    bool _local_flow;

    // Node map of the current potentials

    PotentialMap *_potential;

    bool _local_potential;

    // The source node

    Node _s;

    // The target node

    Node _t;

    // Container to store the found paths

    std::vector<Path> _paths;

    int _path_num;

    // The pred arc map

    PredMap _pred;

  public:

    /// \brief Constructor.

    ///

    /// Constructor.

    ///

    /// \param graph The digraph the algorithm runs on.

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

    Suurballe( const Digraph &graph,

               const LengthMap &length ) :

      _graph(graph), _length(length), _flow(0), _local_flow(false),

    {}

    /// Destructor.

    ~Suurballe() {

      if (_local_flow) delete _flow;

      if (_local_potential) delete _potential;

    }

    /// \brief Set the flow map.

    ///

    /// This function sets the flow map.

    /// If it is not used before calling \ref run() or \ref init(),

    /// an instance will be allocated automatically. The destructor

    /// deallocates this automatically allocated map, of course.

    ///

    /// The found flow contains only 0 and 1 values, since it is the

    /// union of the found arc-disjoint paths.

    ///

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

    Suurballe& flowMap(FlowMap &map) {

      if (_local_flow) {

        delete _flow;

        _local_flow = false;

      }

      _flow = ↦

      return *this;

    }

    /// \brief Set the potential map.

    ///

    /// This function sets the potential map.

    /// If it is not used before calling \ref run() or \ref init(),

    /// an instance will be allocated automatically. The destructor

    /// deallocates this automatically allocated map, of course.

    ///

    /// The node potentials provide the dual solution of the underlying

    /// \ref min_cost_flow "minimum cost flow problem".

    ///

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

    Suurballe& potentialMap(PotentialMap &map) {

      if (_local_potential) {

        delete _potential;

        _local_potential = false;

      }

      _potential = ↦

      return *this;

    }

    /// \name Execution Control

    /// The simplest way to execute the algorithm is to call the run()

    /// If you only need the flow that is the union of the found

    /// @{

    /// \brief Run the algorithm.

    ///

    /// This function runs the algorithm.

    ///

    /// \param s The source node.

    /// \param t The target node.

    /// \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.

    ///

    /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is

    /// just a shortcut of the following code.

    /// \code

    ///   s.init(s);

    /// \endcode

    int run(const Node& s, const Node& t, int k = 2) {

      init(s);

      return _path_num;

    }

    /// \brief Initialize the algorithm.

    ///

    ///

    /// \param s The source node.

    void init(const Node& s) {

      _s = s;

      // Initialize maps

      if (!_flow) {

        _flow = new FlowMap(_graph);

        _local_flow = true;

      }

      if (!_potential) {

        _potential = new PotentialMap(_graph);

        _local_potential = true;

      }

    }

    /// \brief Execute the algorithm to find an optimal flow.

    ///

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

    /// find a minimum cost flow, which is the union of \c k (or less)

    /// arc-disjoint paths.

    ///

    /// \param t The target node.

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

    ///

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

    /// the source node to the given node \c t in the digraph.

    /// Otherwise it returns the number of arc-disjoint paths found.

    ///

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

    int findFlow(const Node& t, int k = 2) {

      _t = t;

      ResidualDijkstra dijkstra(*this);

      // Find shortest paths

      while (_path_num < k) {

        // Run Dijkstra

        if (!dijkstra.run(_path_num)) break;

        ++_path_num;

        // Set the flow along the found shortest path

        Node u = _t;

        Arc e;

        while ((e = _pred[u]) != INVALID) {

          if (u == _graph.target(e)) {

            (*_flow)[e] = 1;

            u = _graph.source(e);

          } else {

            (*_flow)[e] = 0;

            u = _graph.target(e);

          }

        }

      }

      return _path_num;

    }

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

    ///

    /// This function computes arc-disjoint paths from the found minimum

  typedef Digraph::Node Node;

  typedef Digraph::Arc Arc;

  typedef concepts::ReadMap<Arc, VType> LengthMap;

  typedef Suurballe<Digraph, LengthMap> SuurballeType;

  Digraph g;

  Node n;

  Arc e;

  LengthMap len;

  SuurballeType::FlowMap flow(g);

  SuurballeType::PotentialMap pi(g);

  SuurballeType suurb_test(g, len);

  const SuurballeType& const_suurb_test = suurb_test;

  suurb_test

    .flowMap(flow)

    .potentialMap(pi);

  int k;

  k = suurb_test.run(n, n);

  k = suurb_test.run(n, n, k);

  suurb_test.init(n);

  k = suurb_test.findFlow(n);

  k = suurb_test.findFlow(n, k);

  suurb_test.findPaths();

  int f;

  VType c;

  c = const_suurb_test.totalLength();

  f = const_suurb_test.flow(e);

  const SuurballeType::FlowMap& fm =

    const_suurb_test.flowMap();

  c = const_suurb_test.potential(n);

  const SuurballeType::PotentialMap& pm =

    const_suurb_test.potentialMap();

  k = const_suurb_test.pathNum();

  Path<Digraph> p = const_suurb_test.path(k);

  ignore_unused_variable_warning(fm);

  ignore_unused_variable_warning(pm);

}

// 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,