Changeset 898:75c97c3786d6 in lemon for lemon/network_simplex.h
- Timestamp:
- 02/10/10 19:05:20 (14 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/network_simplex.h
r878 r898 195 195 IntVector _source; 196 196 IntVector _target; 197 bool _arc_mixing; 197 198 198 199 // Node and arc data … … 634 635 NetworkSimplex(const GR& graph, bool arc_mixing = false) : 635 636 _graph(graph), _node_id(graph), _arc_id(graph), 637 _arc_mixing(arc_mixing), 636 638 MAX(std::numeric_limits<Value>::max()), 637 639 INF(std::numeric_limits<Value>::has_infinity ? … … 644 646 "The cost type of NetworkSimplex must be signed"); 645 647 646 // Resize vectors 647 _node_num = countNodes(_graph); 648 _arc_num = countArcs(_graph); 649 int all_node_num = _node_num + 1; 650 int max_arc_num = _arc_num + 2 * _node_num; 651 652 _source.resize(max_arc_num); 653 _target.resize(max_arc_num); 654 655 _lower.resize(_arc_num); 656 _upper.resize(_arc_num); 657 _cap.resize(max_arc_num); 658 _cost.resize(max_arc_num); 659 _supply.resize(all_node_num); 660 _flow.resize(max_arc_num); 661 _pi.resize(all_node_num); 662 663 _parent.resize(all_node_num); 664 _pred.resize(all_node_num); 665 _forward.resize(all_node_num); 666 _thread.resize(all_node_num); 667 _rev_thread.resize(all_node_num); 668 _succ_num.resize(all_node_num); 669 _last_succ.resize(all_node_num); 670 _state.resize(max_arc_num); 671 672 // Copy the graph 673 int i = 0; 674 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 675 _node_id[n] = i; 676 } 677 if (arc_mixing) { 678 // Store the arcs in a mixed order 679 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 680 int i = 0, j = 0; 681 for (ArcIt a(_graph); a != INVALID; ++a) { 682 _arc_id[a] = i; 683 _source[i] = _node_id[_graph.source(a)]; 684 _target[i] = _node_id[_graph.target(a)]; 685 if ((i += k) >= _arc_num) i = ++j; 686 } 687 } else { 688 // Store the arcs in the original order 689 int i = 0; 690 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { 691 _arc_id[a] = i; 692 _source[i] = _node_id[_graph.source(a)]; 693 _target[i] = _node_id[_graph.target(a)]; 694 } 695 } 696 697 // Reset parameters 648 // Reset data structures 698 649 reset(); 699 650 } … … 843 794 /// \endcode 844 795 /// 845 /// This function can be called more than once. All the parameters846 /// that have been given are kept for the next call, unless847 /// \ref reset() is called, thus only the modified parameters848 /// have to be set again. See \ref reset() for examples.849 /// However, the underlying digraph must not be modified after this850 /// class have been constructed, since it copies and extends the graph.796 /// This function can be called more than once. All the given parameters 797 /// are kept for the next call, unless \ref resetParams() or \ref reset() 798 /// is used, thus only the modified parameters have to be set again. 799 /// If the underlying digraph was also modified after the construction 800 /// of the class (or the last \ref reset() call), then the \ref reset() 801 /// function must be called. 851 802 /// 852 803 /// \param pivot_rule The pivot rule that will be used during the … … 862 813 /// 863 814 /// \see ProblemType, PivotRule 815 /// \see resetParams(), reset() 864 816 ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) { 865 817 if (!init()) return INFEASIBLE; … … 873 825 /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType(). 874 826 /// 875 /// It is useful for multiple run() calls. If this function is not 876 /// used, all the parameters given before are kept for the next 877 /// \ref run() call. 878 /// However, the underlying digraph must not be modified after this 879 /// class have been constructed, since it copies and extends the graph. 827 /// It is useful for multiple \ref run() calls. Basically, all the given 828 /// parameters are kept for the next \ref run() call, unless 829 /// \ref resetParams() or \ref reset() is used. 830 /// If the underlying digraph was also modified after the construction 831 /// of the class or the last \ref reset() call, then the \ref reset() 832 /// function must be used, otherwise \ref resetParams() is sufficient. 880 833 /// 881 834 /// For example, … … 887 840 /// .supplyMap(sup).run(); 888 841 /// 889 /// // Run again with modified cost map (reset () is not called,842 /// // Run again with modified cost map (resetParams() is not called, 890 843 /// // so only the cost map have to be set again) 891 844 /// cost[e] += 100; 892 845 /// ns.costMap(cost).run(); 893 846 /// 894 /// // Run again from scratch using reset ()847 /// // Run again from scratch using resetParams() 895 848 /// // (the lower bounds will be set to zero on all arcs) 896 /// ns.reset ();849 /// ns.resetParams(); 897 850 /// ns.upperMap(capacity).costMap(cost) 898 851 /// .supplyMap(sup).run(); … … 900 853 /// 901 854 /// \return <tt>(*this)</tt> 902 NetworkSimplex& reset() { 855 /// 856 /// \see reset(), run() 857 NetworkSimplex& resetParams() { 903 858 for (int i = 0; i != _node_num; ++i) { 904 859 _supply[i] = 0; … … 914 869 } 915 870 871 /// \brief Reset the internal data structures and all the parameters 872 /// that have been given before. 873 /// 874 /// This function resets the internal data structures and all the 875 /// paramaters that have been given before using functions \ref lowerMap(), 876 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), 877 /// \ref supplyType(). 878 /// 879 /// It is useful for multiple \ref run() calls. Basically, all the given 880 /// parameters are kept for the next \ref run() call, unless 881 /// \ref resetParams() or \ref reset() is used. 882 /// If the underlying digraph was also modified after the construction 883 /// of the class or the last \ref reset() call, then the \ref reset() 884 /// function must be used, otherwise \ref resetParams() is sufficient. 885 /// 886 /// See \ref resetParams() for examples. 887 /// 888 /// \return <tt>(*this)</tt> 889 /// 890 /// \see resetParams(), run() 891 NetworkSimplex& reset() { 892 // Resize vectors 893 _node_num = countNodes(_graph); 894 _arc_num = countArcs(_graph); 895 int all_node_num = _node_num + 1; 896 int max_arc_num = _arc_num + 2 * _node_num; 897 898 _source.resize(max_arc_num); 899 _target.resize(max_arc_num); 900 901 _lower.resize(_arc_num); 902 _upper.resize(_arc_num); 903 _cap.resize(max_arc_num); 904 _cost.resize(max_arc_num); 905 _supply.resize(all_node_num); 906 _flow.resize(max_arc_num); 907 _pi.resize(all_node_num); 908 909 _parent.resize(all_node_num); 910 _pred.resize(all_node_num); 911 _forward.resize(all_node_num); 912 _thread.resize(all_node_num); 913 _rev_thread.resize(all_node_num); 914 _succ_num.resize(all_node_num); 915 _last_succ.resize(all_node_num); 916 _state.resize(max_arc_num); 917 918 // Copy the graph 919 int i = 0; 920 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 921 _node_id[n] = i; 922 } 923 if (_arc_mixing) { 924 // Store the arcs in a mixed order 925 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 926 int i = 0, j = 0; 927 for (ArcIt a(_graph); a != INVALID; ++a) { 928 _arc_id[a] = i; 929 _source[i] = _node_id[_graph.source(a)]; 930 _target[i] = _node_id[_graph.target(a)]; 931 if ((i += k) >= _arc_num) i = ++j; 932 } 933 } else { 934 // Store the arcs in the original order 935 int i = 0; 936 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { 937 _arc_id[a] = i; 938 _source[i] = _node_id[_graph.source(a)]; 939 _target[i] = _node_id[_graph.target(a)]; 940 } 941 } 942 943 // Reset parameters 944 resetParams(); 945 return *this; 946 } 947 916 948 /// @} 917 949
Note: See TracChangeset
for help on using the changeset viewer.