RhodeCode

#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)

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

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

  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 =