equal
deleted
inserted
replaced
24 /// \file |
24 /// \file |
25 /// \brief The network simplex algorithm for finding a minimum cost |
25 /// \brief The network simplex algorithm for finding a minimum cost |
26 /// flow. |
26 /// flow. |
27 |
27 |
28 #include <limits> |
28 #include <limits> |
|
29 #include <lemon/graph_adaptor.h> |
|
30 #include <lemon/graph_utils.h> |
29 #include <lemon/smart_graph.h> |
31 #include <lemon/smart_graph.h> |
30 #include <lemon/graph_utils.h> |
|
31 |
32 |
32 /// \brief The pivot rule used in the algorithm. |
33 /// \brief The pivot rule used in the algorithm. |
33 //#define FIRST_ELIGIBLE_PIVOT |
34 //#define FIRST_ELIGIBLE_PIVOT |
34 //#define BEST_ELIGIBLE_PIVOT |
35 //#define BEST_ELIGIBLE_PIVOT |
35 #define EDGE_BLOCK_PIVOT |
36 #define EDGE_BLOCK_PIVOT |
83 /// \param SupplyMap The type of the supply map. |
84 /// \param SupplyMap The type of the supply map. |
84 /// |
85 /// |
85 /// \warning |
86 /// \warning |
86 /// - Edge capacities and costs should be nonnegative integers. |
87 /// - Edge capacities and costs should be nonnegative integers. |
87 /// However \c CostMap::Value should be signed type. |
88 /// However \c CostMap::Value should be signed type. |
88 /// - Supply values should be integers. |
89 /// - Supply values should be signed integers. |
89 /// - \c LowerMap::Value must be convertible to |
90 /// - \c LowerMap::Value must be convertible to |
90 /// \c CapacityMap::Value and \c CapacityMap::Value must be |
91 /// \c CapacityMap::Value and \c CapacityMap::Value must be |
91 /// convertible to \c SupplyMap::Value. |
92 /// convertible to \c SupplyMap::Value. |
92 /// |
93 /// |
93 /// \author Peter Kovacs |
94 /// \author Peter Kovacs |
146 const SCostMap &cost_map; |
147 const SCostMap &cost_map; |
147 const SPotentialMap &pot_map; |
148 const SPotentialMap &pot_map; |
148 |
149 |
149 public: |
150 public: |
150 |
151 |
151 typedef typename MapBase<Edge, Cost>::Value Value; |
|
152 typedef typename MapBase<Edge, Cost>::Key Key; |
|
153 |
|
154 ReducedCostMap( const SGraph &_gr, |
152 ReducedCostMap( const SGraph &_gr, |
155 const SCostMap &_cm, |
153 const SCostMap &_cm, |
156 const SPotentialMap &_pm ) : |
154 const SPotentialMap &_pm ) : |
157 gr(_gr), cost_map(_cm), pot_map(_pm) {} |
155 gr(_gr), cost_map(_cm), pot_map(_pm) {} |
158 |
156 |
159 Value operator[](const Key &e) const { |
157 Cost operator[](const Edge &e) const { |
160 return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)]; |
158 return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)]; |
161 } |
159 } |
162 |
160 |
163 }; //class ReducedCostMap |
161 }; //class ReducedCostMap |
164 |
162 |