RhodeCode

  /// \brief Default traits class of CapacityScaling algorithm.

  ///

  /// Default traits class of CapacityScaling algorithm.

  /// \tparam GR Digraph type.

  /// and supply values. By default it is \c int.

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

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

  struct CapacityScalingDefaultTraits

  {

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

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

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

#ifdef DOXYGEN

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

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

      /// these cases.

      UNBOUNDED

    };

      INF(std::numeric_limits<Value>::has_infinity ?

          std::numeric_limits<Value>::infinity() :

          std::numeric_limits<Value>::max())

    {

      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,

        "The flow type of CapacityScaling must be signed");

      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,

        "The cost type of CapacityScaling must be signed");

    ///

    /// This function sets the upper bounds (capacities) on the arcs.

    /// If it is not used before calling \ref run(), the upper bounds

    /// will be set to \ref INF on all arcs (i.e. the flow value will be

    ///

    /// \param map An arc map storing the upper bounds.

    /// Its \c Value type must be convertible to the \c Value type

    /// of the algorithm.

    /// This function can be called more than once. All the parameters

    /// that have been given are kept for the next call, unless

    /// \ref reset() is called, thus only the modified parameters

    /// have to be set again. See \ref reset() for examples.

    /// class have been constructed, since it copies and extends the graph.

    ///

    /// \param factor The capacity scaling factor. It must be larger than

    /// one to use scaling. If it is less or equal to one, then scaling

    /// (i.e. it is feasible and bounded), and the algorithm has found

    /// optimal flow and node potentials (primal and dual solutions),

    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost

    /// and infinite upper bound. It means that the objective function

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

    /// these cases.

    ///

    /// \see ProblemType

  /// \brief Default traits class of CostScaling algorithm.

  ///

  /// Default traits class of CostScaling algorithm.

  /// \tparam GR Digraph type.

  /// and supply values. By default it is \c int.

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

#ifdef DOXYGEN

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

#else

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

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

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

  ///

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

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

      /// these cases.

      UNBOUNDED

    };

      INF(std::numeric_limits<Value>::has_infinity ?

          std::numeric_limits<Value>::infinity() :

          std::numeric_limits<Value>::max())

    {

      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,

        "The flow type of CostScaling must be signed");

      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,

        "The cost type of CostScaling must be signed");

    ///

    /// This function sets the upper bounds (capacities) on the arcs.

    /// If it is not used before calling \ref run(), the upper bounds

    /// will be set to \ref INF on all arcs (i.e. the flow value will be

    ///

    /// \param map An arc map storing the upper bounds.

    /// Its \c Value type must be convertible to the \c Value type

    /// of the algorithm.

    /// (i.e. it is feasible and bounded), and the algorithm has found

    /// optimal flow and node potentials (primal and dual solutions),

    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost

    /// and infinite upper bound. It means that the objective function

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

    /// these cases.

    ///

    /// \see ProblemType, Method

    ///

    /// It is useful for multiple run() calls. If this function is not

    /// used, all the parameters given before are kept for the next

    /// \ref run() call.

    /// class have been constructed, since it copies and extends the graph.

    ///

    /// For example,

    /// \code

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

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

  /// \ref amo93networkflows, \ref dantzig63linearprog,

  /// \ref kellyoneill91netsimplex.

  ///

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

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

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

    /// implementations that significantly affect the running time

    /// of the algorithm.

    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which

    /// proved to be the most efficient and the most robust on various

    /// However, another pivot rule can be selected using the \ref run()

    /// function with the proper parameter.

    enum PivotRule {

      MAX(std::numeric_limits<Value>::max()),

      INF(std::numeric_limits<Value>::has_infinity ?

          std::numeric_limits<Value>::infinity() : MAX)

    {

      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,

        "The flow type of NetworkSimplex must be signed");

      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,

        "The cost type of NetworkSimplex must be signed");

    ///

    /// This function sets the upper bounds (capacities) on the arcs.

    /// If it is not used before calling \ref run(), the upper bounds

    /// will be set to \ref INF on all arcs (i.e. the flow value will be

    ///

    /// \param map An arc map storing the upper bounds.

    /// Its \c Value type must be convertible to the \c Value type

    /// of the algorithm.