RhodeCode

  /// By default it is the same as \c V.

  template <typename GR, typename V = int, typename C = V>

  struct CapacityScalingDefaultTraits

  {

    /// The type of the digraph

    typedef GR Digraph;

    /// The type of the flow amounts, capacity bounds and supply values

    typedef V Value;

    /// The type of the arc costs

    typedef C Cost;

    /// \brief The type of the heap used for internal Dijkstra computations.

    ///

    /// The type of the heap used for internal Dijkstra computations.

    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,

    /// its priority type must be \c Cost and its cross reference type

    /// must be \ref RangeMap "RangeMap<int>".

    typedef BinHeap<Cost, RangeMap<int> > Heap;

  };

  /// \addtogroup min_cost_flow_algs

  /// @{

  /// \brief Implementation of the Capacity Scaling algorithm for

  /// finding a \ref min_cost_flow "minimum cost flow".

  ///

  /// \ref CapacityScaling implements the capacity scaling version

  /// of the successive shortest path algorithm for finding a

  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,

  /// \ref edmondskarp72theoretical. It is an efficient dual

  /// solution method.

  ///

  /// Most of the parameters of the problem (except for the digraph)

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

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

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// and supply values in the algorithm. By default, it is \c int.

  /// \tparam C The number type used for costs and potentials in the

  /// algorithm. By default, it is the same as \c V.

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref CapacityScalingDefaultTraits

  /// "CapacityScalingDefaultTraits<GR, V, C>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

  ///

  /// be integer.

  /// \warning This algorithm does not support negative costs for such

  /// arcs that have infinite upper bound.

#ifdef DOXYGEN

  template <typename GR, typename V, typename C, typename TR>

#else

  template < typename GR, typename V = int, typename C = V,

             typename TR = CapacityScalingDefaultTraits<GR, V, C> >

#endif

  class CapacityScaling

  {

  public:

    /// The type of the digraph

    typedef typename TR::Digraph Digraph;

    /// The type of the flow amounts, capacity bounds and supply values

    typedef typename TR::Value Value;

    /// The type of the arc costs

    typedef typename TR::Cost Cost;

    /// The type of the heap used for internal Dijkstra computations

    typedef typename TR::Heap Heap;

    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

  public:

    /// \brief Problem type constants for the \c run() function.

    ///

    /// Enum type containing the problem type constants that can be

    /// returned by the \ref run() function of the algorithm.

    enum ProblemType {

      /// The problem has no feasible solution (flow).

      INFEASIBLE,

      /// The problem has optimal solution (i.e. it is feasible and

      /// bounded), and the algorithm has found optimal flow and node

      /// potentials (primal and dual solutions).

      OPTIMAL,

      /// The digraph contains an arc of negative cost and infinite

      /// upper bound. It means that the objective function is unbounded

      /// on that arc, however, note that it could actually be bounded

      /// over the feasible flows, but this algroithm cannot handle

      /// these cases.

      UNBOUNDED

    };

  private:

    typedef double LargeCost;

  };

  // Default traits class for integer cost types

  template <typename GR, typename V, typename C>

  struct CostScalingDefaultTraits<GR, V, C, true>

  {

    typedef GR Digraph;

    typedef V Value;

    typedef C Cost;

#ifdef LEMON_HAVE_LONG_LONG

    typedef long long LargeCost;

#else

    typedef long LargeCost;

#endif

  };

  /// \addtogroup min_cost_flow_algs

  /// @{

  /// \brief Implementation of the Cost Scaling algorithm for

  /// finding a \ref min_cost_flow "minimum cost flow".

  ///

  /// \ref CostScaling implements a cost scaling algorithm that performs

  /// push/augment and relabel operations for finding a \ref min_cost_flow

  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,

  /// \ref goldberg97efficient, \ref bunnagel98efficient.

  /// It is a highly efficient primal-dual solution method, which

  /// can be viewed as the generalization of the \ref Preflow

  /// "preflow push-relabel" algorithm for the maximum flow problem.

  ///

  /// Most of the parameters of the problem (except for the digraph)

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

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

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// and supply values in the algorithm. By default, it is \c int.

  /// \tparam C The number type used for costs and potentials in the

  /// algorithm. By default, it is the same as \c V.

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref CostScalingDefaultTraits

  /// "CostScalingDefaultTraits<GR, V, C>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

  ///

  /// be integer.

  /// \warning This algorithm does not support negative costs for such

  /// arcs that have infinite upper bound.

  ///

  /// \note %CostScaling provides three different internal methods,

  /// from which the most efficient one is used by default.

  /// For more information, see \ref Method.

#ifdef DOXYGEN

  template <typename GR, typename V, typename C, typename TR>

#else

  template < typename GR, typename V = int, typename C = V,

             typename TR = CostScalingDefaultTraits<GR, V, C> >

#endif

  class CostScaling

  {

  public:

    /// The type of the digraph

    typedef typename TR::Digraph Digraph;

    /// The type of the flow amounts, capacity bounds and supply values

    typedef typename TR::Value Value;

    /// The type of the arc costs

    typedef typename TR::Cost Cost;

    /// \brief The large cost type

    ///

    /// The large cost type used for internal computations.

    /// By default, it is \c long \c long if the \c Cost type is integer,

    /// otherwise it is \c double.

    typedef typename TR::LargeCost LargeCost;

    /// The \ref CostScalingDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

  public:

    /// \brief Problem type constants for the \c run() function.

    ///

    /// Enum type containing the problem type constants that can be

    /// returned by the \ref run() function of the algorithm.

    enum ProblemType {

      /// The problem has no feasible solution (flow).

      INFEASIBLE,

      /// The problem has optimal solution (i.e. it is feasible and

      /// bounded), and the algorithm has found optimal flow and node

      /// potentials (primal and dual solutions).

      OPTIMAL,

      /// The digraph contains an arc of negative cost and infinite

#define LEMON_CYCLE_CANCELING_H

/// \ingroup min_cost_flow_algs

/// \file

/// \brief Cycle-canceling algorithms for finding a minimum cost flow.

#include <vector>

#include <limits>

#include <lemon/core.h>

#include <lemon/maps.h>

#include <lemon/path.h>

#include <lemon/math.h>

#include <lemon/static_graph.h>

#include <lemon/adaptors.h>

#include <lemon/circulation.h>

#include <lemon/bellman_ford.h>

#include <lemon/howard_mmc.h>

namespace lemon {

  /// \addtogroup min_cost_flow_algs

  /// @{

  /// \brief Implementation of cycle-canceling algorithms for

  /// finding a \ref min_cost_flow "minimum cost flow".

  ///

  /// \ref CycleCanceling implements three different cycle-canceling

  /// algorithms for finding a \ref min_cost_flow "minimum cost flow"

  /// \ref amo93networkflows, \ref klein67primal,

  /// \ref goldberg89cyclecanceling.

  /// The most efficent one (both theoretically and practically)

  /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm,

  /// thus it is the default method.

  /// It is strongly polynomial, but in practice, it is typically much

  /// slower than the scaling algorithms and NetworkSimplex.

  ///

  /// Most of the parameters of the problem (except for the digraph)

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

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

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// and supply values in the algorithm. By default, it is \c int.

  /// \tparam C The number type used for costs and potentials in the

  /// algorithm. By default, it is the same as \c V.

  ///

  /// be integer.

  /// \warning This algorithm does not support negative costs for such

  /// arcs that have infinite upper bound.

  ///

  /// \note For more information about the three available methods,

  /// see \ref Method.

#ifdef DOXYGEN

  template <typename GR, typename V, typename C>

#else

  template <typename GR, typename V = int, typename C = V>

#endif

  class CycleCanceling

  {

  public:

    /// The type of the digraph

    typedef GR Digraph;

    /// The type of the flow amounts, capacity bounds and supply values

    typedef V Value;

    /// The type of the arc costs

    typedef C Cost;

  public:

    /// \brief Problem type constants for the \c run() function.

    ///

    /// Enum type containing the problem type constants that can be

    /// returned by the \ref run() function of the algorithm.

    enum ProblemType {

      /// The problem has no feasible solution (flow).

      INFEASIBLE,

      /// The problem has optimal solution (i.e. it is feasible and

      /// bounded), and the algorithm has found optimal flow and node

      /// potentials (primal and dual solutions).

      OPTIMAL,

      /// The digraph contains an arc of negative cost and infinite

      /// upper bound. It means that the objective function is unbounded

      /// on that arc, however, note that it could actually be bounded

      /// over the feasible flows, but this algroithm cannot handle

      /// these cases.

      UNBOUNDED

    };

    /// \brief Constants for selecting the used method.

    ///

    /// Enum type containing constants for selecting the used method

    /// for the \ref run() function.

    ///

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * 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_KRUSKAL_H

#define LEMON_KRUSKAL_H

#include <algorithm>

#include <vector>

#include <lemon/unionfind.h>

#include <lemon/maps.h>

#include <lemon/core.h>

#include <lemon/bits/traits.h>

///\ingroup spantree

///\file

///\brief Kruskal's algorithm to compute a minimum cost spanning tree

namespace lemon {

  namespace _kruskal_bits {

    // Kruskal for directed graphs.

    template <typename Digraph, typename In, typename Out>

    typename disable_if<lemon::UndirectedTagIndicator<Digraph>,

                       typename In::value_type::second_type >::type

    kruskal(const Digraph& digraph, const In& in, Out& out,dummy<0> = 0) {

      typedef typename In::value_type::second_type Value;

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

      typedef typename Digraph::Node Node;

      IndexMap index(digraph);

      UnionFind<IndexMap> uf(index);

      for (typename Digraph::NodeIt it(digraph); it != INVALID; ++it) {

        uf.insert(it);

      }

      Value tree_value = 0;

      for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {

        if (uf.join(digraph.target(it->first),digraph.source(it->first))) {

          out.set(it->first, true);

          tree_value += it->second;

        }

        else {

          out.set(it->first, false);

        }

      }

      return tree_value;

    }

    // Kruskal for undirected graphs.

    template <typename Graph, typename In, typename Out>

    typename enable_if<lemon::UndirectedTagIndicator<Graph>,

                       typename In::value_type::second_type >::type

    kruskal(const Graph& graph, const In& in, Out& out,dummy<1> = 1) {

      typedef typename In::value_type::second_type Value;

      typedef typename Graph::template NodeMap<int> IndexMap;

      typedef typename Graph::Node Node;

      IndexMap index(graph);

      UnionFind<IndexMap> uf(index);

      for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {

        uf.insert(it);

#ifndef LEMON_NETWORK_SIMPLEX_H

#define LEMON_NETWORK_SIMPLEX_H

/// \ingroup min_cost_flow_algs

///

/// \file

/// \brief Network Simplex algorithm for finding a minimum cost flow.

#include <vector>

#include <limits>

#include <algorithm>

#include <lemon/core.h>

#include <lemon/math.h>

namespace lemon {

  /// \addtogroup min_cost_flow_algs

  /// @{

  /// \brief Implementation of the primal Network Simplex algorithm

  /// for finding a \ref min_cost_flow "minimum cost flow".

  ///

  /// \ref NetworkSimplex implements the primal Network Simplex algorithm

  /// for finding a \ref min_cost_flow "minimum cost flow"

  /// \ref amo93networkflows, \ref dantzig63linearprog,

  /// \ref kellyoneill91netsimplex.

  /// This algorithm is a highly efficient specialized version of the

  /// linear programming simplex method directly for the minimum cost

  /// flow problem.

  ///

  /// In general, %NetworkSimplex is the fastest implementation available

  /// in LEMON for this problem.

  /// Moreover, it supports both directions of the supply/demand inequality

  /// constraints. For more information, see \ref SupplyType.

  ///

  /// Most of the parameters of the problem (except for the digraph)

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

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

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// and supply values in the algorithm. By default, it is \c int.

  /// \tparam C The number type used for costs and potentials in the

  /// algorithm. By default, it is the same as \c V.

  ///

  /// be integer.

  ///

  /// \note %NetworkSimplex provides five different pivot rule

  /// implementations, from which the most efficient one is used

  /// by default. For more information, see \ref PivotRule.

  template <typename GR, typename V = int, typename C = V>

  class NetworkSimplex

  {

  public:

    /// The type of the flow amounts, capacity bounds and supply values

    typedef V Value;

    /// The type of the arc costs

    typedef C Cost;

  public:

    /// \brief Problem type constants for the \c run() function.

    ///

    /// Enum type containing the problem type constants that can be

    /// returned by the \ref run() function of the algorithm.

    enum ProblemType {

      /// The problem has no feasible solution (flow).

      INFEASIBLE,

      /// The problem has optimal solution (i.e. it is feasible and

      /// bounded), and the algorithm has found optimal flow and node

      /// potentials (primal and dual solutions).

      OPTIMAL,

      /// The objective function of the problem is unbounded, i.e.

      /// there is a directed cycle having negative total cost and

      /// infinite upper bound.

      UNBOUNDED

    };

    /// \brief Constants for selecting the type of the supply constraints.

    ///

    /// Enum type containing constants for selecting the supply type,

    /// i.e. the direction of the inequalities in the supply/demand

    /// constraints of the \ref min_cost_flow "minimum cost flow problem".

    ///

    /// The default supply type is \c GEQ, the \c LEQ type can be

    /// selected using \ref supplyType().

    /// The equality form is a special case of both supply types.

    enum SupplyType {

      /// This option means that there are <em>"greater or equal"</em>

      /// supply/demand constraints in the definition of the problem.

      GEQ,

      /// This option means that there are <em>"less or equal"</em>