lemon/capacity_scaling.h
changeset 808 9c428bb2b105
parent 806 fa6f37d7a25b
child 810 3b53491bf643
equal deleted inserted replaced
1:51ac6f5addeb 2:5979e08ce50b
    28 #include <limits>
    28 #include <limits>
    29 #include <lemon/core.h>
    29 #include <lemon/core.h>
    30 #include <lemon/bin_heap.h>
    30 #include <lemon/bin_heap.h>
    31 
    31 
    32 namespace lemon {
    32 namespace lemon {
       
    33 
       
    34   /// \brief Default traits class of CapacityScaling algorithm.
       
    35   ///
       
    36   /// Default traits class of CapacityScaling algorithm.
       
    37   /// \tparam GR Digraph type.
       
    38   /// \tparam V The value type used for flow amounts, capacity bounds
       
    39   /// and supply values. By default it is \c int.
       
    40   /// \tparam C The value type used for costs and potentials.
       
    41   /// By default it is the same as \c V.
       
    42   template <typename GR, typename V = int, typename C = V>
       
    43   struct CapacityScalingDefaultTraits
       
    44   {
       
    45     /// The type of the digraph
       
    46     typedef GR Digraph;
       
    47     /// The type of the flow amounts, capacity bounds and supply values
       
    48     typedef V Value;
       
    49     /// The type of the arc costs
       
    50     typedef C Cost;
       
    51 
       
    52     /// \brief The type of the heap used for internal Dijkstra computations.
       
    53     ///
       
    54     /// The type of the heap used for internal Dijkstra computations.
       
    55     /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
       
    56     /// its priority type must be \c Cost and its cross reference type
       
    57     /// must be \ref RangeMap "RangeMap<int>".
       
    58     typedef BinHeap<Cost, RangeMap<int> > Heap;
       
    59   };
    33 
    60 
    34   /// \addtogroup min_cost_flow_algs
    61   /// \addtogroup min_cost_flow_algs
    35   /// @{
    62   /// @{
    36 
    63 
    37   /// \brief Implementation of the Capacity Scaling algorithm for
    64   /// \brief Implementation of the Capacity Scaling algorithm for
    55   ///
    82   ///
    56   /// \warning Both value types must be signed and all input data must
    83   /// \warning Both value types must be signed and all input data must
    57   /// be integer.
    84   /// be integer.
    58   /// \warning This algorithm does not support negative costs for such
    85   /// \warning This algorithm does not support negative costs for such
    59   /// arcs that have infinite upper bound.
    86   /// arcs that have infinite upper bound.
    60   template <typename GR, typename V = int, typename C = V>
    87 #ifdef DOXYGEN
       
    88   template <typename GR, typename V, typename C, typename TR>
       
    89 #else
       
    90   template < typename GR, typename V = int, typename C = V,
       
    91              typename TR = CapacityScalingDefaultTraits<GR, V, C> >
       
    92 #endif
    61   class CapacityScaling
    93   class CapacityScaling
    62   {
    94   {
    63   public:
    95   public:
    64 
    96 
       
    97     /// The type of the digraph
       
    98     typedef typename TR::Digraph Digraph;
    65     /// The type of the flow amounts, capacity bounds and supply values
    99     /// The type of the flow amounts, capacity bounds and supply values
    66     typedef V Value;
   100     typedef typename TR::Value Value;
    67     /// The type of the arc costs
   101     /// The type of the arc costs
    68     typedef C Cost;
   102     typedef typename TR::Cost Cost;
       
   103 
       
   104     /// The type of the heap used for internal Dijkstra computations
       
   105     typedef typename TR::Heap Heap;
       
   106 
       
   107     /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
       
   108     typedef TR Traits;
    69 
   109 
    70   public:
   110   public:
    71 
   111 
    72     /// \brief Problem type constants for the \c run() function.
   112     /// \brief Problem type constants for the \c run() function.
    73     ///
   113     ///
    90   
   130   
    91   private:
   131   private:
    92 
   132 
    93     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
   133     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    94 
   134 
    95     typedef std::vector<Arc> ArcVector;
       
    96     typedef std::vector<Node> NodeVector;
       
    97     typedef std::vector<int> IntVector;
   135     typedef std::vector<int> IntVector;
    98     typedef std::vector<bool> BoolVector;
   136     typedef std::vector<bool> BoolVector;
    99     typedef std::vector<Value> ValueVector;
   137     typedef std::vector<Value> ValueVector;
   100     typedef std::vector<Cost> CostVector;
   138     typedef std::vector<Cost> CostVector;
   101 
   139 
   153     // shortest paths in the residual network of the digraph with
   191     // shortest paths in the residual network of the digraph with
   154     // respect to the reduced arc costs and modifying the node
   192     // respect to the reduced arc costs and modifying the node
   155     // potentials according to the found distance labels.
   193     // potentials according to the found distance labels.
   156     class ResidualDijkstra
   194     class ResidualDijkstra
   157     {
   195     {
   158       typedef RangeMap<int> HeapCrossRef;
       
   159       typedef BinHeap<Cost, HeapCrossRef> Heap;
       
   160 
       
   161     private:
   196     private:
   162 
   197 
   163       int _node_num;
   198       int _node_num;
   164       const IntVector &_first_out;
   199       const IntVector &_first_out;
   165       const IntVector &_target;
   200       const IntVector &_target;
   180         _excess(cs._excess), _pi(cs._pi), _pred(cs._pred),
   215         _excess(cs._excess), _pi(cs._pi), _pred(cs._pred),
   181         _dist(cs._node_num)
   216         _dist(cs._node_num)
   182       {}
   217       {}
   183 
   218 
   184       int run(int s, Value delta = 1) {
   219       int run(int s, Value delta = 1) {
   185         HeapCrossRef heap_cross_ref(_node_num, Heap::PRE_HEAP);
   220         RangeMap<int> heap_cross_ref(_node_num, Heap::PRE_HEAP);
   186         Heap heap(heap_cross_ref);
   221         Heap heap(heap_cross_ref);
   187         heap.push(s, 0);
   222         heap.push(s, 0);
   188         _pred[s] = -1;
   223         _pred[s] = -1;
   189         _proc_nodes.clear();
   224         _proc_nodes.clear();
   190 
   225 
   231 
   266 
   232     }; //class ResidualDijkstra
   267     }; //class ResidualDijkstra
   233 
   268 
   234   public:
   269   public:
   235 
   270 
       
   271     /// \name Named Template Parameters
       
   272     /// @{
       
   273 
       
   274     template <typename T>
       
   275     struct SetHeapTraits : public Traits {
       
   276       typedef T Heap;
       
   277     };
       
   278 
       
   279     /// \brief \ref named-templ-param "Named parameter" for setting
       
   280     /// \c Heap type.
       
   281     ///
       
   282     /// \ref named-templ-param "Named parameter" for setting \c Heap
       
   283     /// type, which is used for internal Dijkstra computations.
       
   284     /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
       
   285     /// its priority type must be \c Cost and its cross reference type
       
   286     /// must be \ref RangeMap "RangeMap<int>".
       
   287     template <typename T>
       
   288     struct SetHeap
       
   289       : public CapacityScaling<GR, V, C, SetHeapTraits<T> > {
       
   290       typedef  CapacityScaling<GR, V, C, SetHeapTraits<T> > Create;
       
   291     };
       
   292 
       
   293     /// @}
       
   294 
       
   295   public:
       
   296 
   236     /// \brief Constructor.
   297     /// \brief Constructor.
   237     ///
   298     ///
   238     /// The constructor of the class.
   299     /// The constructor of the class.
   239     ///
   300     ///
   240     /// \param graph The digraph the algorithm runs on.
   301     /// \param graph The digraph the algorithm runs on.
   429     }
   490     }
   430     
   491     
   431     /// @}
   492     /// @}
   432 
   493 
   433     /// \name Execution control
   494     /// \name Execution control
       
   495     /// The algorithm can be executed using \ref run().
   434 
   496 
   435     /// @{
   497     /// @{
   436 
   498 
   437     /// \brief Run the algorithm.
   499     /// \brief Run the algorithm.
   438     ///
   500     ///
   745       return pt;
   807       return pt;
   746     }
   808     }
   747 
   809 
   748     // Execute the capacity scaling algorithm
   810     // Execute the capacity scaling algorithm
   749     ProblemType startWithScaling() {
   811     ProblemType startWithScaling() {
   750       // Process capacity scaling phases
   812       // Perform capacity scaling phases
   751       int s, t;
   813       int s, t;
   752       int phase_cnt = 0;
   814       int phase_cnt = 0;
   753       int factor = 4;
   815       int factor = 4;
   754       ResidualDijkstra _dijkstra(*this);
   816       ResidualDijkstra _dijkstra(*this);
   755       while (true) {
   817       while (true) {