lemon/circulation.h
changeset 536 97674155c135
parent 440 88ed40ad0d4f
child 559 c5fd2d996909
child 610 dacc2cee2b4c
equal deleted inserted replaced
4:7c6a93e1090b 5:89a6d2e45da2
    29 namespace lemon {
    29 namespace lemon {
    30 
    30 
    31   /// \brief Default traits class of Circulation class.
    31   /// \brief Default traits class of Circulation class.
    32   ///
    32   ///
    33   /// Default traits class of Circulation class.
    33   /// Default traits class of Circulation class.
    34   /// \tparam _Diraph Digraph type.
    34   /// \tparam GR Digraph type.
    35   /// \tparam _LCapMap Lower bound capacity map type.
    35   /// \tparam LM Lower bound capacity map type.
    36   /// \tparam _UCapMap Upper bound capacity map type.
    36   /// \tparam UM Upper bound capacity map type.
    37   /// \tparam _DeltaMap Delta map type.
    37   /// \tparam DM Delta map type.
    38   template <typename _Diraph, typename _LCapMap,
    38   template <typename GR, typename LM,
    39             typename _UCapMap, typename _DeltaMap>
    39             typename UM, typename DM>
    40   struct CirculationDefaultTraits {
    40   struct CirculationDefaultTraits {
    41 
    41 
    42     /// \brief The type of the digraph the algorithm runs on.
    42     /// \brief The type of the digraph the algorithm runs on.
    43     typedef _Diraph Digraph;
    43     typedef GR Digraph;
    44 
    44 
    45     /// \brief The type of the map that stores the circulation lower
    45     /// \brief The type of the map that stores the circulation lower
    46     /// bound.
    46     /// bound.
    47     ///
    47     ///
    48     /// The type of the map that stores the circulation lower bound.
    48     /// The type of the map that stores the circulation lower bound.
    49     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    49     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    50     typedef _LCapMap LCapMap;
    50     typedef LM LCapMap;
    51 
    51 
    52     /// \brief The type of the map that stores the circulation upper
    52     /// \brief The type of the map that stores the circulation upper
    53     /// bound.
    53     /// bound.
    54     ///
    54     ///
    55     /// The type of the map that stores the circulation upper bound.
    55     /// The type of the map that stores the circulation upper bound.
    56     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    56     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    57     typedef _UCapMap UCapMap;
    57     typedef UM UCapMap;
    58 
    58 
    59     /// \brief The type of the map that stores the lower bound for
    59     /// \brief The type of the map that stores the lower bound for
    60     /// the supply of the nodes.
    60     /// the supply of the nodes.
    61     ///
    61     ///
    62     /// The type of the map that stores the lower bound for the supply
    62     /// The type of the map that stores the lower bound for the supply
    63     /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
    63     /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
    64     /// concept.
    64     /// concept.
    65     typedef _DeltaMap DeltaMap;
    65     typedef DM DeltaMap;
    66 
    66 
    67     /// \brief The type of the flow values.
    67     /// \brief The type of the flow values.
    68     typedef typename DeltaMap::Value Value;
    68     typedef typename DeltaMap::Value Value;
    69 
    69 
    70     /// \brief The type of the map that stores the flow values.
    70     /// \brief The type of the map that stores the flow values.
   135      will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
   135      will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
   136      Thus a feasible solution for the
   136      Thus a feasible solution for the
   137      \ref min_cost_flow "minimum cost flow" problem can be calculated
   137      \ref min_cost_flow "minimum cost flow" problem can be calculated
   138      in this way.
   138      in this way.
   139 
   139 
   140      \tparam _Digraph The type of the digraph the algorithm runs on.
   140      \tparam GR The type of the digraph the algorithm runs on.
   141      \tparam _LCapMap The type of the lower bound capacity map. The default
   141      \tparam LM The type of the lower bound capacity map. The default
   142      map type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
   142      map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   143      \tparam _UCapMap The type of the upper bound capacity map. The default
   143      \tparam UM The type of the upper bound capacity map. The default
   144      map type is \c _LCapMap.
   144      map type is \c LM.
   145      \tparam _DeltaMap The type of the map that stores the lower bound
   145      \tparam DM The type of the map that stores the lower bound
   146      for the supply of the nodes. The default map type is
   146      for the supply of the nodes. The default map type is
   147      \c _Digraph::ArcMap<_UCapMap::Value>.
   147      \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
   148   */
   148   */
   149 #ifdef DOXYGEN
   149 #ifdef DOXYGEN
   150 template< typename _Digraph,
   150 template< typename GR,
   151           typename _LCapMap,
   151           typename LM,
   152           typename _UCapMap,
   152           typename UM,
   153           typename _DeltaMap,
   153           typename DM,
   154           typename _Traits >
   154           typename TR >
   155 #else
   155 #else
   156 template< typename _Digraph,
   156 template< typename GR,
   157           typename _LCapMap = typename _Digraph::template ArcMap<int>,
   157           typename LM = typename GR::template ArcMap<int>,
   158           typename _UCapMap = _LCapMap,
   158           typename UM = LM,
   159           typename _DeltaMap = typename _Digraph::
   159           typename DM = typename GR::template NodeMap<typename UM::Value>,
   160                                template NodeMap<typename _UCapMap::Value>,
   160           typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
   161           typename _Traits=CirculationDefaultTraits<_Digraph, _LCapMap,
       
   162                                                     _UCapMap, _DeltaMap> >
       
   163 #endif
   161 #endif
   164   class Circulation {
   162   class Circulation {
   165   public:
   163   public:
   166 
   164 
   167     ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
   165     ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
   168     typedef _Traits Traits;
   166     typedef TR Traits;
   169     ///The type of the digraph the algorithm runs on.
   167     ///The type of the digraph the algorithm runs on.
   170     typedef typename Traits::Digraph Digraph;
   168     typedef typename Traits::Digraph Digraph;
   171     ///The type of the flow values.
   169     ///The type of the flow values.
   172     typedef typename Traits::Value Value;
   170     typedef typename Traits::Value Value;
   173 
   171