lemon/network_simplex.h
changeset 864 d3ea191c3412
parent 840 2914b6f0fde0
child 877 141f9c0db4a3
equal deleted inserted replaced
27:b74e7ff13cc7 28:e2acf237e0e0
   168     typedef std::vector<Cost> CostVector;
   168     typedef std::vector<Cost> CostVector;
   169     typedef std::vector<char> BoolVector;
   169     typedef std::vector<char> BoolVector;
   170     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
   170     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
   171 
   171 
   172     // State constants for arcs
   172     // State constants for arcs
   173     enum ArcStateEnum {
   173     enum ArcState {
   174       STATE_UPPER = -1,
   174       STATE_UPPER = -1,
   175       STATE_TREE  =  0,
   175       STATE_TREE  =  0,
   176       STATE_LOWER =  1
   176       STATE_LOWER =  1
   177     };
   177     };
       
   178 
       
   179     typedef std::vector<signed char> StateVector;
       
   180     // Note: vector<signed char> is used instead of vector<ArcState> for
       
   181     // efficiency reasons
   178 
   182 
   179   private:
   183   private:
   180 
   184 
   181     // Data related to the underlying digraph
   185     // Data related to the underlying digraph
   182     const GR &_graph;
   186     const GR &_graph;
   213     IntVector _rev_thread;
   217     IntVector _rev_thread;
   214     IntVector _succ_num;
   218     IntVector _succ_num;
   215     IntVector _last_succ;
   219     IntVector _last_succ;
   216     IntVector _dirty_revs;
   220     IntVector _dirty_revs;
   217     BoolVector _forward;
   221     BoolVector _forward;
   218     BoolVector _state;
   222     StateVector _state;
   219     int _root;
   223     int _root;
   220 
   224 
   221     // Temporary data used in the current pivot iteration
   225     // Temporary data used in the current pivot iteration
   222     int in_arc, join, u_in, v_in, u_out, v_out;
   226     int in_arc, join, u_in, v_in, u_out, v_out;
   223     int first, second, right, last;
   227     int first, second, right, last;
   244 
   248 
   245       // References to the NetworkSimplex class
   249       // References to the NetworkSimplex class
   246       const IntVector  &_source;
   250       const IntVector  &_source;
   247       const IntVector  &_target;
   251       const IntVector  &_target;
   248       const CostVector &_cost;
   252       const CostVector &_cost;
   249       const BoolVector &_state;
   253       const StateVector &_state;
   250       const CostVector &_pi;
   254       const CostVector &_pi;
   251       int &_in_arc;
   255       int &_in_arc;
   252       int _search_arc_num;
   256       int _search_arc_num;
   253 
   257 
   254       // Pivot rule data
   258       // Pivot rule data
   296 
   300 
   297       // References to the NetworkSimplex class
   301       // References to the NetworkSimplex class
   298       const IntVector  &_source;
   302       const IntVector  &_source;
   299       const IntVector  &_target;
   303       const IntVector  &_target;
   300       const CostVector &_cost;
   304       const CostVector &_cost;
   301       const BoolVector &_state;
   305       const StateVector &_state;
   302       const CostVector &_pi;
   306       const CostVector &_pi;
   303       int &_in_arc;
   307       int &_in_arc;
   304       int _search_arc_num;
   308       int _search_arc_num;
   305 
   309 
   306     public:
   310     public:
   335 
   339 
   336       // References to the NetworkSimplex class
   340       // References to the NetworkSimplex class
   337       const IntVector  &_source;
   341       const IntVector  &_source;
   338       const IntVector  &_target;
   342       const IntVector  &_target;
   339       const CostVector &_cost;
   343       const CostVector &_cost;
   340       const BoolVector &_state;
   344       const StateVector &_state;
   341       const CostVector &_pi;
   345       const CostVector &_pi;
   342       int &_in_arc;
   346       int &_in_arc;
   343       int _search_arc_num;
   347       int _search_arc_num;
   344 
   348 
   345       // Pivot rule data
   349       // Pivot rule data
   408 
   412 
   409       // References to the NetworkSimplex class
   413       // References to the NetworkSimplex class
   410       const IntVector  &_source;
   414       const IntVector  &_source;
   411       const IntVector  &_target;
   415       const IntVector  &_target;
   412       const CostVector &_cost;
   416       const CostVector &_cost;
   413       const BoolVector &_state;
   417       const StateVector &_state;
   414       const CostVector &_pi;
   418       const CostVector &_pi;
   415       int &_in_arc;
   419       int &_in_arc;
   416       int _search_arc_num;
   420       int _search_arc_num;
   417 
   421 
   418       // Pivot rule data
   422       // Pivot rule data
   511 
   515 
   512       // References to the NetworkSimplex class
   516       // References to the NetworkSimplex class
   513       const IntVector  &_source;
   517       const IntVector  &_source;
   514       const IntVector  &_target;
   518       const IntVector  &_target;
   515       const CostVector &_cost;
   519       const CostVector &_cost;
   516       const BoolVector &_state;
   520       const StateVector &_state;
   517       const CostVector &_pi;
   521       const CostVector &_pi;
   518       int &_in_arc;
   522       int &_in_arc;
   519       int _search_arc_num;
   523       int _search_arc_num;
   520 
   524 
   521       // Pivot rule data
   525       // Pivot rule data