Changeset 873:78071e00de00 in lemon
- Timestamp:
- 11/12/09 23:27:21 (15 years ago)
- Branch:
- default
- Phase:
- public
- Rebase:
- 33336539313938363364303661336366373764356634303962303164663663353665313137343963
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r872 r873 31 31 32 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 61 /// \addtogroup min_cost_flow_algs … … 58 85 /// \warning This algorithm does not support negative costs for such 59 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 93 class CapacityScaling 62 94 { 63 95 public: 64 96 97 /// The type of the digraph 98 typedef typename TR::Digraph Digraph; 65 99 /// The type of the flow amounts, capacity bounds and supply values 66 typedef VValue;100 typedef typename TR::Value Value; 67 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 110 public: … … 93 133 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 94 134 95 typedef std::vector<Arc> ArcVector;96 typedef std::vector<Node> NodeVector;97 135 typedef std::vector<int> IntVector; 98 136 typedef std::vector<bool> BoolVector; … … 156 194 class ResidualDijkstra 157 195 { 158 typedef RangeMap<int> HeapCrossRef;159 typedef BinHeap<Cost, HeapCrossRef> Heap;160 161 196 private: 162 197 … … 183 218 184 219 int run(int s, Value delta = 1) { 185 HeapCrossRefheap_cross_ref(_node_num, Heap::PRE_HEAP);220 RangeMap<int> heap_cross_ref(_node_num, Heap::PRE_HEAP); 186 221 Heap heap(heap_cross_ref); 187 222 heap.push(s, 0); … … 234 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 297 /// \brief Constructor. 237 298 /// … … 432 493 433 494 /// \name Execution control 495 /// The algorithm can be executed using \ref run(). 434 496 435 497 /// @{ … … 748 810 // Execute the capacity scaling algorithm 749 811 ProblemType startWithScaling() { 750 // P rocesscapacity scaling phases812 // Perform capacity scaling phases 751 813 int s, t; 752 814 int phase_cnt = 0;
Note: See TracChangeset
for help on using the changeset viewer.