RhodeCode

#include <limits>

  /// 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 LEN The type of the length map.

  /// The default value is <tt>GR::ArcMap<int></tt>.

  /// along with the \ref SplitNodes adaptor.

  template < typename GR,

#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

#endif

    typedef SimplePath<GR> Path;

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

      ResidualDijkstra( const Digraph &graph,

        _graph(graph), _flow(flow), _length(length), _potential(potential),

        _dist(graph), _pred(pred), _s(s), _t(t) {}

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

    Suurballe( const Digraph &graph,

               const LengthMap &length ) :

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

      _potential(0), _local_potential(false), _pred(graph)

    {

      LEMON_ASSERT(std::numeric_limits<Length>::is_integer,

        "The length type of Suurballe must be integer");

    }

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

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

    /// \param s The source node.

    /// \param t The target node.

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

    /// just a shortcut of the following code.

    ///   s.init(s);

    ///   s.findFlow(t, k);

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

      init(s);

      findFlow(t, k);

    ///

    /// \param s The source node.

    void init(const Node& s) {

      _source = s;

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

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

    /// \param t The target node.

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

    ///

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

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

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

      _target = t;

      _dijkstra =

        new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred,

                              _source, _target );

    /// This function computes the paths from the found minimum cost flow,

    /// which is the union of some arc-disjoint paths.

    /// \brief Return the total length of the found paths.

    ///

    /// This function returns the total length of the found paths, i.e.

    /// the total cost of the found flow.

    /// The complexity of the function is O(e).

    ///

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

    /// this function.

    Length totalLength() const {

      Length c = 0;

      for (ArcIt e(_graph); e != INVALID; ++e)

        c += (*_flow)[e] * _length[e];

      return c;

    }

    /// \brief Return the flow value on the given arc.

    ///

    /// This function returns the flow value on the given arc.

    /// It is \c 1 if the arc is involved in one of the found arc-disjoint

    /// paths, otherwise it is \c 0.

    ///

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

    /// this function.

    int flow(const Arc& arc) const {

      return (*_flow)[arc];

    }

    /// \brief Return a const reference to an arc map storing the

    /// This function returns a const reference to an arc map storing

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

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

    /// \brief Return a const reference to a node map storing the

    /// found potentials (the dual solution).

    /// This function returns a const reference to a node map storing

    /// the found potentials that provide the dual solution of the

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

    const PotentialMap& potentialMap() const {

      return *_potential;

    /// \param i The function returns the <tt>i</tt>-th path.

#include <lemon/concepts/digraph.h>

  "label\n"

  "1\n"

  "2\n"

  "3\n"

  "4\n"

  "5\n"

  "6\n"

  "7\n"

  "8\n"

  "9\n"

  "10\n"

  "11\n"

  "12\n"

  "      length\n"

  " 1  2  70\n"

  " 1  3 150\n"

  " 1  4  80\n"

  " 2  8  80\n"

  " 3  5 140\n"

  " 4  6  60\n"

  " 4  7  80\n"

  " 4  8 110\n"

  " 5  7  60\n"

  " 5 11 120\n"

  " 6  3   0\n"

  " 6  9 140\n"

  " 6 10  90\n"

  " 7  1  30\n"

  " 8 12  60\n"

  " 9 12  50\n"

  "10 12  70\n"

  "10  2 100\n"

  "10  7  60\n"

  "11 10  20\n"

  "12 11  30\n"

// Check the interface of Suurballe

void checkSuurballeCompile()

{

  typedef int VType;

  typedef concepts::Digraph Digraph;

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

}

  Node s, t;

    arcMap("length", length).

    node("source", s).

    node("target", t).

    Suurballe<ListDigraph> suurballe(digraph, length);

    check(suurballe.run(s, t) == 2, "Wrong number of paths");

    check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),

      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");

    Suurballe<ListDigraph> suurballe(digraph, length);

    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");

    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),

      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");

    Suurballe<ListDigraph> suurballe(digraph, length);

    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");

    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),

      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");

      Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);

      int k=sur.run(a,b,2);

        Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);

        int k=sur.run(pi->a,pi->b,2);