Changeset 688:756a5ec551c8 in lemon for lemon/network_simplex.h
 Timestamp:
 04/29/09 14:25:51 (10 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/network_simplex.h
r687 r688 57 57 /// 58 58 /// \tparam GR The digraph type the algorithm runs on. 59 /// \tparam FThe value type used for flow amounts, capacity bounds59 /// \tparam V The value type used for flow amounts, capacity bounds 60 60 /// and supply values in the algorithm. By default it is \c int. 61 61 /// \tparam C The value type used for costs and potentials in the 62 /// algorithm. By default it is the same as \c F.62 /// algorithm. By default it is the same as \c V. 63 63 /// 64 64 /// \warning Both value types must be signed and all input data must … … 68 68 /// implementations, from which the most efficient one is used 69 69 /// by default. For more information see \ref PivotRule. 70 template <typename GR, typename F = int, typename C = F>70 template <typename GR, typename V = int, typename C = V> 71 71 class NetworkSimplex 72 72 { … … 74 74 75 75 /// The flow type of the algorithm 76 typedef F Flow;76 typedef V Value; 77 77 /// The cost type of the algorithm 78 78 typedef C Cost; 79 79 #ifdef DOXYGEN 80 80 /// The type of the flow map 81 typedef GR::ArcMap< Flow> FlowMap;81 typedef GR::ArcMap<Value> FlowMap; 82 82 /// The type of the potential map 83 83 typedef GR::NodeMap<Cost> PotentialMap; 84 84 #else 85 85 /// The type of the flow map 86 typedef typename GR::template ArcMap< Flow> FlowMap;86 typedef typename GR::template ArcMap<Value> FlowMap; 87 87 /// The type of the potential map 88 88 typedef typename GR::template NodeMap<Cost> PotentialMap; … … 207 207 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 208 208 209 typedef typename GR::template ArcMap< Flow> FlowArcMap;209 typedef typename GR::template ArcMap<Value> ValueArcMap; 210 210 typedef typename GR::template ArcMap<Cost> CostArcMap; 211 typedef typename GR::template NodeMap< Flow> FlowNodeMap;211 typedef typename GR::template NodeMap<Value> ValueNodeMap; 212 212 213 213 typedef std::vector<Arc> ArcVector; … … 215 215 typedef std::vector<int> IntVector; 216 216 typedef std::vector<bool> BoolVector; 217 typedef std::vector< Flow> FlowVector;217 typedef std::vector<Value> FlowVector; 218 218 typedef std::vector<Cost> CostVector; 219 219 … … 233 233 234 234 // Parameters of the problem 235 FlowArcMap *_plower;236 FlowArcMap *_pupper;235 ValueArcMap *_plower; 236 ValueArcMap *_pupper; 237 237 CostArcMap *_pcost; 238 FlowNodeMap *_psupply;238 ValueNodeMap *_psupply; 239 239 bool _pstsup; 240 240 Node _psource, _ptarget; 241 Flow_pstflow;241 Value _pstflow; 242 242 SupplyType _stype; 243 243 244 Flow_sum_supply;244 Value _sum_supply; 245 245 246 246 // Result maps … … 279 279 int first, second, right, last; 280 280 int stem, par_stem, new_stem; 281 Flowdelta;281 Value delta; 282 282 283 283 public: … … 286 286 /// 287 287 /// Constant for infinite upper bounds (capacities). 288 /// It is \c std::numeric_limits< Flow>::infinity() if available,289 /// \c std::numeric_limits< Flow>::max() otherwise.290 const FlowINF;288 /// It is \c std::numeric_limits<Value>::infinity() if available, 289 /// \c std::numeric_limits<Value>::max() otherwise. 290 const Value INF; 291 291 292 292 private: … … 696 696 _local_flow(false), _local_potential(false), 697 697 _node_id(graph), 698 INF(std::numeric_limits< Flow>::has_infinity ?699 std::numeric_limits< Flow>::infinity() :700 std::numeric_limits< Flow>::max())698 INF(std::numeric_limits<Value>::has_infinity ? 699 std::numeric_limits<Value>::infinity() : 700 std::numeric_limits<Value>::max()) 701 701 { 702 702 // Check the value types 703 LEMON_ASSERT(std::numeric_limits< Flow>::is_signed,703 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, 704 704 "The flow type of NetworkSimplex must be signed"); 705 705 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, … … 726 726 /// 727 727 /// \param map An arc map storing the lower bounds. 728 /// Its \c Value type must be convertible to the \c Flowtype728 /// Its \c Value type must be convertible to the \c Value type 729 729 /// of the algorithm. 730 730 /// … … 733 733 NetworkSimplex& lowerMap(const LowerMap& map) { 734 734 delete _plower; 735 _plower = new FlowArcMap(_graph);735 _plower = new ValueArcMap(_graph); 736 736 for (ArcIt a(_graph); a != INVALID; ++a) { 737 737 (*_plower)[a] = map[a]; … … 748 748 /// 749 749 /// \param map An arc map storing the upper bounds. 750 /// Its \c Value type must be convertible to the \c Flowtype750 /// Its \c Value type must be convertible to the \c Value type 751 751 /// of the algorithm. 752 752 /// … … 755 755 NetworkSimplex& upperMap(const UpperMap& map) { 756 756 delete _pupper; 757 _pupper = new FlowArcMap(_graph);757 _pupper = new ValueArcMap(_graph); 758 758 for (ArcIt a(_graph); a != INVALID; ++a) { 759 759 (*_pupper)[a] = map[a]; … … 791 791 /// 792 792 /// \param map A node map storing the supply values. 793 /// Its \c Value type must be convertible to the \c Flowtype793 /// Its \c Value type must be convertible to the \c Value type 794 794 /// of the algorithm. 795 795 /// … … 799 799 delete _psupply; 800 800 _pstsup = false; 801 _psupply = new FlowNodeMap(_graph);801 _psupply = new ValueNodeMap(_graph); 802 802 for (NodeIt n(_graph); n != INVALID; ++n) { 803 803 (*_psupply)[n] = map[n]; … … 824 824 /// 825 825 /// \return <tt>(*this)</tt> 826 NetworkSimplex& stSupply(const Node& s, const Node& t, Flowk) {826 NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) { 827 827 delete _psupply; 828 828 _psupply = NULL; … … 1026 1026 /// 1027 1027 /// \pre \ref run() must be called before using this function. 1028 Flowflow(const Arc& a) const {1028 Value flow(const Arc& a) const { 1029 1029 return (*_flow_map)[a]; 1030 1030 } … … 1205 1205 if (_plower) { 1206 1206 for (int i = 0; i != _arc_num; ++i) { 1207 Flowc = (*_plower)[_arc_ref[i]];1207 Value c = (*_plower)[_arc_ref[i]]; 1208 1208 if (c > 0) { 1209 1209 if (_cap[i] < INF) _cap[i] = c; … … 1276 1276 delta = _cap[in_arc]; 1277 1277 int result = 0; 1278 Flowd;1278 Value d; 1279 1279 int e; 1280 1280 … … 1316 1316 // Augment along the cycle 1317 1317 if (delta > 0) { 1318 Flowval = _state[in_arc] * delta;1318 Value val = _state[in_arc] * delta; 1319 1319 _flow[in_arc] += val; 1320 1320 for (int u = _source[in_arc]; u != join; u = _parent[u]) {
Note: See TracChangeset
for help on using the changeset viewer.