Changeset 603:425cc8328c0e in lemon1.2 for lemon/network_simplex.h
 Timestamp:
 03/23/09 23:54:42 (12 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/network_simplex.h
r601 r603 29 29 #include <algorithm> 30 30 31 #include <lemon/core.h> 31 32 #include <lemon/math.h> 32 33 … … 121 122 122 123 // References for the original data 123 const Digraph &_ orig_graph;124 const Digraph &_graph; 124 125 const LowerMap *_orig_lower; 125 126 const CapacityMap &_orig_cap; … … 131 132 132 133 // Result maps 133 FlowMap *_flow_ result;134 PotentialMap *_potential_ result;134 FlowMap *_flow_map; 135 PotentialMap *_potential_map; 135 136 bool _local_flow; 136 137 bool _local_potential; 137 138 // Data structures for storing the graph139 ArcVector _arc;140 NodeVector _node;141 IntNodeMap _node_id;142 IntVector _source;143 IntVector _target;144 138 145 139 // The number of nodes and arcs in the original graph 146 140 int _node_num; 147 141 int _arc_num; 142 143 // Data structures for storing the graph 144 IntNodeMap _node_id; 145 ArcVector _arc_ref; 146 IntVector _source; 147 IntVector _target; 148 148 149 149 // Node and arc maps … … 154 154 CostVector _pi; 155 155 156 // Node and arc maps forthe spanning tree structure156 // Data for storing the spanning tree structure 157 157 IntVector _depth; 158 158 IntVector _parent; … … 161 161 BoolVector _forward; 162 162 IntVector _state; 163 164 // The root node165 163 int _root; 166 164 167 // The entering arc in the current pivot iteration168 int _in_arc;169 170 165 // Temporary data used in the current pivot iteration 171 int join, u_in, v_in, u_out, v_out;172 int right, first, second, last;166 int in_arc, join, u_in, v_in, u_out, v_out; 167 int first, second, right, last; 173 168 int stem, par_stem, new_stem; 174 169 Capacity delta; … … 188 183 189 184 // References to the NetworkSimplex class 190 const ArcVector &_arc;191 185 const IntVector &_source; 192 186 const IntVector &_target; … … 204 198 /// Constructor 205 199 FirstEligiblePivotRule(NetworkSimplex &ns) : 206 _ arc(ns._arc), _source(ns._source), _target(ns._target),200 _source(ns._source), _target(ns._target), 207 201 _cost(ns._cost), _state(ns._state), _pi(ns._pi), 208 _in_arc(ns. _in_arc), _arc_num(ns._arc_num), _next_arc(0)202 _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0) 209 203 {} 210 204 … … 246 240 247 241 // References to the NetworkSimplex class 248 const ArcVector &_arc;249 242 const IntVector &_source; 250 243 const IntVector &_target; … … 259 252 /// Constructor 260 253 BestEligiblePivotRule(NetworkSimplex &ns) : 261 _ arc(ns._arc), _source(ns._source), _target(ns._target),254 _source(ns._source), _target(ns._target), 262 255 _cost(ns._cost), _state(ns._state), _pi(ns._pi), 263 _in_arc(ns. _in_arc), _arc_num(ns._arc_num)256 _in_arc(ns.in_arc), _arc_num(ns._arc_num) 264 257 {} 265 258 … … 292 285 293 286 // References to the NetworkSimplex class 294 const ArcVector &_arc;295 287 const IntVector &_source; 296 288 const IntVector &_target; … … 309 301 /// Constructor 310 302 BlockSearchPivotRule(NetworkSimplex &ns) : 311 _ arc(ns._arc), _source(ns._source), _target(ns._target),303 _source(ns._source), _target(ns._target), 312 304 _cost(ns._cost), _state(ns._state), _pi(ns._pi), 313 _in_arc(ns. _in_arc), _arc_num(ns._arc_num), _next_arc(0)305 _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0) 314 306 { 315 307 // The main parameters of the pivot rule … … 371 363 372 364 // References to the NetworkSimplex class 373 const ArcVector &_arc;374 365 const IntVector &_source; 375 366 const IntVector &_target; … … 390 381 /// Constructor 391 382 CandidateListPivotRule(NetworkSimplex &ns) : 392 _ arc(ns._arc), _source(ns._source), _target(ns._target),383 _source(ns._source), _target(ns._target), 393 384 _cost(ns._cost), _state(ns._state), _pi(ns._pi), 394 _in_arc(ns. _in_arc), _arc_num(ns._arc_num), _next_arc(0)385 _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0) 395 386 { 396 387 // The main parameters of the pivot rule … … 483 474 484 475 // References to the NetworkSimplex class 485 const ArcVector &_arc;486 476 const IntVector &_source; 487 477 const IntVector &_target; … … 516 506 /// Constructor 517 507 AlteringListPivotRule(NetworkSimplex &ns) : 518 _ arc(ns._arc), _source(ns._source), _target(ns._target),508 _source(ns._source), _target(ns._target), 519 509 _cost(ns._cost), _state(ns._state), _pi(ns._pi), 520 _in_arc(ns. _in_arc), _arc_num(ns._arc_num),510 _in_arc(ns.in_arc), _arc_num(ns._arc_num), 521 511 _next_arc(0), _cand_cost(ns._arc_num), _sort_func(_cand_cost) 522 512 { … … 550 540 // Extend the list 551 541 int cnt = _block_size; 552 int last_ edge= 0;542 int last_arc = 0; 553 543 int limit = _head_length; 554 544 … … 558 548 if (_cand_cost[e] < 0) { 559 549 _candidates[_curr_length++] = e; 560 last_ edge= e;550 last_arc = e; 561 551 } 562 552 if (cnt == 0) { … … 572 562 if (_cand_cost[e] < 0) { 573 563 _candidates[_curr_length++] = e; 574 last_ edge= e;564 last_arc = e; 575 565 } 576 566 if (cnt == 0) { … … 582 572 } 583 573 if (_curr_length == 0) return false; 584 _next_arc = last_ edge+ 1;574 _next_arc = last_arc + 1; 585 575 586 576 // Make heap of the candidate list (approximating a partial sort) … … 604 594 /// General constructor (with lower bounds). 605 595 /// 606 /// \param digraph The digraph the algorithm runs on.596 /// \param graph The digraph the algorithm runs on. 607 597 /// \param lower The lower bounds of the arcs. 608 598 /// \param capacity The capacities (upper bounds) of the arcs. 609 599 /// \param cost The cost (length) values of the arcs. 610 600 /// \param supply The supply values of the nodes (signed). 611 NetworkSimplex( const Digraph & digraph,601 NetworkSimplex( const Digraph &graph, 612 602 const LowerMap &lower, 613 603 const CapacityMap &capacity, 614 604 const CostMap &cost, 615 605 const SupplyMap &supply ) : 616 _ orig_graph(digraph), _orig_lower(&lower), _orig_cap(capacity),606 _graph(graph), _orig_lower(&lower), _orig_cap(capacity), 617 607 _orig_cost(cost), _orig_supply(&supply), 618 _flow_ result(NULL), _potential_result(NULL),608 _flow_map(NULL), _potential_map(NULL), 619 609 _local_flow(false), _local_potential(false), 620 _node_id( digraph)610 _node_id(graph) 621 611 {} 622 612 … … 625 615 /// General constructor (without lower bounds). 626 616 /// 627 /// \param digraph The digraph the algorithm runs on.617 /// \param graph The digraph the algorithm runs on. 628 618 /// \param capacity The capacities (upper bounds) of the arcs. 629 619 /// \param cost The cost (length) values of the arcs. 630 620 /// \param supply The supply values of the nodes (signed). 631 NetworkSimplex( const Digraph & digraph,621 NetworkSimplex( const Digraph &graph, 632 622 const CapacityMap &capacity, 633 623 const CostMap &cost, 634 624 const SupplyMap &supply ) : 635 _ orig_graph(digraph), _orig_lower(NULL), _orig_cap(capacity),625 _graph(graph), _orig_lower(NULL), _orig_cap(capacity), 636 626 _orig_cost(cost), _orig_supply(&supply), 637 _flow_ result(NULL), _potential_result(NULL),627 _flow_map(NULL), _potential_map(NULL), 638 628 _local_flow(false), _local_potential(false), 639 _node_id( digraph)629 _node_id(graph) 640 630 {} 641 631 … … 644 634 /// Simple constructor (with lower bounds). 645 635 /// 646 /// \param digraph The digraph the algorithm runs on.636 /// \param graph The digraph the algorithm runs on. 647 637 /// \param lower The lower bounds of the arcs. 648 638 /// \param capacity The capacities (upper bounds) of the arcs. … … 652 642 /// \param flow_value The required amount of flow from node \c s 653 643 /// to node \c t (i.e. the supply of \c s and the demand of \c t). 654 NetworkSimplex( const Digraph & digraph,644 NetworkSimplex( const Digraph &graph, 655 645 const LowerMap &lower, 656 646 const CapacityMap &capacity, … … 658 648 Node s, Node t, 659 649 Capacity flow_value ) : 660 _ orig_graph(digraph), _orig_lower(&lower), _orig_cap(capacity),650 _graph(graph), _orig_lower(&lower), _orig_cap(capacity), 661 651 _orig_cost(cost), _orig_supply(NULL), 662 652 _orig_source(s), _orig_target(t), _orig_flow_value(flow_value), 663 _flow_ result(NULL), _potential_result(NULL),653 _flow_map(NULL), _potential_map(NULL), 664 654 _local_flow(false), _local_potential(false), 665 _node_id( digraph)655 _node_id(graph) 666 656 {} 667 657 … … 670 660 /// Simple constructor (without lower bounds). 671 661 /// 672 /// \param digraph The digraph the algorithm runs on.662 /// \param graph The digraph the algorithm runs on. 673 663 /// \param capacity The capacities (upper bounds) of the arcs. 674 664 /// \param cost The cost (length) values of the arcs. … … 677 667 /// \param flow_value The required amount of flow from node \c s 678 668 /// to node \c t (i.e. the supply of \c s and the demand of \c t). 679 NetworkSimplex( const Digraph & digraph,669 NetworkSimplex( const Digraph &graph, 680 670 const CapacityMap &capacity, 681 671 const CostMap &cost, 682 672 Node s, Node t, 683 673 Capacity flow_value ) : 684 _ orig_graph(digraph), _orig_lower(NULL), _orig_cap(capacity),674 _graph(graph), _orig_lower(NULL), _orig_cap(capacity), 685 675 _orig_cost(cost), _orig_supply(NULL), 686 676 _orig_source(s), _orig_target(t), _orig_flow_value(flow_value), 687 _flow_ result(NULL), _potential_result(NULL),677 _flow_map(NULL), _potential_map(NULL), 688 678 _local_flow(false), _local_potential(false), 689 _node_id( digraph)679 _node_id(graph) 690 680 {} 691 681 692 682 /// Destructor. 693 683 ~NetworkSimplex() { 694 if (_local_flow) delete _flow_ result;695 if (_local_potential) delete _potential_ result;684 if (_local_flow) delete _flow_map; 685 if (_local_potential) delete _potential_map; 696 686 } 697 687 … … 703 693 NetworkSimplex& flowMap(FlowMap &map) { 704 694 if (_local_flow) { 705 delete _flow_ result;695 delete _flow_map; 706 696 _local_flow = false; 707 697 } 708 _flow_ result= ↦698 _flow_map = ↦ 709 699 return *this; 710 700 } … … 717 707 NetworkSimplex& potentialMap(PotentialMap &map) { 718 708 if (_local_potential) { 719 delete _potential_ result;709 delete _potential_map; 720 710 _local_potential = false; 721 711 } 722 _potential_ result= ↦712 _potential_map = ↦ 723 713 return *this; 724 714 } … … 784 774 /// \pre \ref run() must be called before using this function. 785 775 const FlowMap& flowMap() const { 786 return *_flow_ result;776 return *_flow_map; 787 777 } 788 778 … … 795 785 /// \pre \ref run() must be called before using this function. 796 786 const PotentialMap& potentialMap() const { 797 return *_potential_ result;787 return *_potential_map; 798 788 } 799 789 … … 804 794 /// \pre \ref run() must be called before using this function. 805 795 Capacity flow(const Arc& arc) const { 806 return (*_flow_ result)[arc];796 return (*_flow_map)[arc]; 807 797 } 808 798 … … 813 803 /// \pre \ref run() must be called before using this function. 814 804 Cost potential(const Node& node) const { 815 return (*_potential_ result)[node];805 return (*_potential_map)[node]; 816 806 } 817 807 … … 824 814 Cost totalCost() const { 825 815 Cost c = 0; 826 for (ArcIt e(_ orig_graph); e != INVALID; ++e)827 c += (*_flow_ result)[e] * _orig_cost[e];816 for (ArcIt e(_graph); e != INVALID; ++e) 817 c += (*_flow_map)[e] * _orig_cost[e]; 828 818 return c; 829 819 } … … 836 826 bool init() { 837 827 // Initialize result maps 838 if (!_flow_ result) {839 _flow_ result = new FlowMap(_orig_graph);828 if (!_flow_map) { 829 _flow_map = new FlowMap(_graph); 840 830 _local_flow = true; 841 831 } 842 if (!_potential_ result) {843 _potential_ result = new PotentialMap(_orig_graph);832 if (!_potential_map) { 833 _potential_map = new PotentialMap(_graph); 844 834 _local_potential = true; 845 835 } 846 836 847 837 // Initialize vectors 848 _node_num = countNodes(_ orig_graph);849 _arc_num = countArcs(_ orig_graph);838 _node_num = countNodes(_graph); 839 _arc_num = countArcs(_graph); 850 840 int all_node_num = _node_num + 1; 851 int all_edge_num = _arc_num + _node_num; 852 853 _arc.resize(_arc_num); 854 _node.reserve(_node_num); 855 _source.resize(all_edge_num); 856 _target.resize(all_edge_num); 857 858 _cap.resize(all_edge_num); 859 _cost.resize(all_edge_num); 841 int all_arc_num = _arc_num + _node_num; 842 843 _arc_ref.resize(_arc_num); 844 _source.resize(all_arc_num); 845 _target.resize(all_arc_num); 846 847 _cap.resize(all_arc_num); 848 _cost.resize(all_arc_num); 860 849 _supply.resize(all_node_num); 861 _flow.resize(all_ edge_num, 0);850 _flow.resize(all_arc_num, 0); 862 851 _pi.resize(all_node_num, 0); 863 852 … … 865 854 _parent.resize(all_node_num); 866 855 _pred.resize(all_node_num); 856 _forward.resize(all_node_num); 867 857 _thread.resize(all_node_num); 868 _forward.resize(all_node_num); 869 _state.resize(all_edge_num, STATE_LOWER); 858 _state.resize(all_arc_num, STATE_LOWER); 870 859 871 860 // Initialize node related data … … 874 863 Supply sum = 0; 875 864 int i = 0; 876 for (NodeIt n(_orig_graph); n != INVALID; ++n, ++i) { 877 _node.push_back(n); 865 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 878 866 _node_id[n] = i; 879 867 _supply[i] = (*_orig_supply)[n]; … … 883 871 } else { 884 872 int i = 0; 885 for (NodeIt n(_orig_graph); n != INVALID; ++n, ++i) { 886 _node.push_back(n); 873 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 887 874 _node_id[n] = i; 888 875 _supply[i] = 0; … … 905 892 int k = std::max(int(sqrt(_arc_num)), 10); 906 893 int i = 0; 907 for (ArcIt e(_ orig_graph); e != INVALID; ++e) {908 _arc [i] = e;894 for (ArcIt e(_graph); e != INVALID; ++e) { 895 _arc_ref[i] = e; 909 896 if ((i += k) >= _arc_num) i = (i % k) + 1; 910 897 } … … 912 899 // Initialize arc maps 913 900 for (int i = 0; i != _arc_num; ++i) { 914 Arc e = _arc [i];915 _source[i] = _node_id[_ orig_graph.source(e)];916 _target[i] = _node_id[_ orig_graph.target(e)];901 Arc e = _arc_ref[i]; 902 _source[i] = _node_id[_graph.source(e)]; 903 _target[i] = _node_id[_graph.target(e)]; 917 904 _cost[i] = _orig_cost[e]; 918 905 _cap[i] = _orig_cap[e]; … … 922 909 if (_orig_lower) { 923 910 for (int i = 0; i != _arc_num; ++i) { 924 Capacity c = (*_orig_lower)[_arc [i]];911 Capacity c = (*_orig_lower)[_arc_ref[i]]; 925 912 if (c != 0) { 926 913 _cap[i] = c; … … 958 945 // Find the join node 959 946 void findJoinNode() { 960 int u = _source[ _in_arc];961 int v = _target[ _in_arc];947 int u = _source[in_arc]; 948 int v = _target[in_arc]; 962 949 while (_depth[u] > _depth[v]) u = _parent[u]; 963 950 while (_depth[v] > _depth[u]) v = _parent[v]; … … 974 961 // Initialize first and second nodes according to the direction 975 962 // of the cycle 976 if (_state[ _in_arc] == STATE_LOWER) {977 first = _source[ _in_arc];978 second = _target[ _in_arc];963 if (_state[in_arc] == STATE_LOWER) { 964 first = _source[in_arc]; 965 second = _target[in_arc]; 979 966 } else { 980 first = _target[ _in_arc];981 second = _source[ _in_arc];982 } 983 delta = _cap[ _in_arc];967 first = _target[in_arc]; 968 second = _source[in_arc]; 969 } 970 delta = _cap[in_arc]; 984 971 int result = 0; 985 972 Capacity d; … … 1021 1008 // Augment along the cycle 1022 1009 if (delta > 0) { 1023 Capacity val = _state[ _in_arc] * delta;1024 _flow[ _in_arc] += val;1025 for (int u = _source[ _in_arc]; u != join; u = _parent[u]) {1010 Capacity val = _state[in_arc] * delta; 1011 _flow[in_arc] += val; 1012 for (int u = _source[in_arc]; u != join; u = _parent[u]) { 1026 1013 _flow[_pred[u]] += _forward[u] ? val : val; 1027 1014 } 1028 for (int u = _target[ _in_arc]; u != join; u = _parent[u]) {1015 for (int u = _target[in_arc]; u != join; u = _parent[u]) { 1029 1016 _flow[_pred[u]] += _forward[u] ? val : val; 1030 1017 } … … 1032 1019 // Update the state of the entering and leaving arcs 1033 1020 if (change) { 1034 _state[ _in_arc] = STATE_TREE;1021 _state[in_arc] = STATE_TREE; 1035 1022 _state[_pred[u_out]] = 1036 1023 (_flow[_pred[u_out]] == 0) ? STATE_LOWER : STATE_UPPER; 1037 1024 } else { 1038 _state[ _in_arc] = _state[_in_arc];1025 _state[in_arc] = _state[in_arc]; 1039 1026 } 1040 1027 } … … 1107 1094 u = v; 1108 1095 } 1109 _pred[u_in] = _in_arc;1110 _forward[u_in] = (u_in == _source[ _in_arc]);1096 _pred[u_in] = in_arc; 1097 _forward[u_in] = (u_in == _source[in_arc]); 1111 1098 } 1112 1099 … … 1164 1151 } 1165 1152 1166 // Copy flow values to _flow_ result1153 // Copy flow values to _flow_map 1167 1154 if (_orig_lower) { 1168 1155 for (int i = 0; i != _arc_num; ++i) { 1169 Arc e = _arc [i];1170 (*_flow_result)[e] = (*_orig_lower)[e] + _flow[i];1156 Arc e = _arc_ref[i]; 1157 _flow_map>set(e, (*_orig_lower)[e] + _flow[i]); 1171 1158 } 1172 1159 } else { 1173 1160 for (int i = 0; i != _arc_num; ++i) { 1174 (*_flow_result)[_arc[i]] = _flow[i];1175 } 1176 } 1177 // Copy potential values to _potential_ result1178 for ( int i = 0; i != _node_num; ++i) {1179 (*_potential_result)[_node[i]] = _pi[i];1161 _flow_map>set(_arc_ref[i], _flow[i]); 1162 } 1163 } 1164 // Copy potential values to _potential_map 1165 for (NodeIt n(_graph); n != INVALID; ++n) { 1166 _potential_map>set(n, _pi[_node_id[n]]); 1180 1167 } 1181 1168
Note: See TracChangeset
for help on using the changeset viewer.