Changeset - r877:fe80a8145653
« 876:3b5349
878:4b1b37 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Small implementation improvements in MCF algorithms (#180) - Handle max() as infinite value (not only infinity()). - Better GEQ handling in CapacityScaling. - Skip the unnecessary saturating operations in the first phase in CapacityScaling. - Use vector<char> instead of vector<bool> and vector<int> if it is possible and it proved to be usually faster.
0 2 0
default
2 files changed with 61 insertions and 50 deletions:
lemon/capacity_scaling.h
44
35
lemon/network_simplex.h
17
15
↑ Collapse diff ↑
lemon/capacity_scaling.h
Show white space 2 line context
... ... 
@@ -135,3 +135,3 @@
135 135 
    typedef std::vector<int> IntVector;
136 
    typedef std::vector<bool> BoolVector;
136 
    typedef std::vector<char> BoolVector;
137 137 
    typedef std::vector<Value> ValueVector;
... ... 
@@ -198,2 +198,3 @@
198 198 
      int _node_num;
199 
      bool _geq;
199 200 
      const IntVector &_first_out;
... ... 
@@ -212,6 +213,6 @@
212 213 
      ResidualDijkstra(CapacityScaling& cs) :
213 
        _node_num(cs._node_num), _first_out(cs._first_out),
214 
        _target(cs._target), _cost(cs._cost), _res_cap(cs._res_cap),
215 
        _excess(cs._excess), _pi(cs._pi), _pred(cs._pred),
216 
        _dist(cs._node_num)
214 
        _node_num(cs._node_num), _geq(cs._sum_supply < 0),
215 
        _first_out(cs._first_out), _target(cs._target), _cost(cs._cost),
216 
        _res_cap(cs._res_cap), _excess(cs._excess), _pi(cs._pi),
217 
        _pred(cs._pred), _dist(cs._node_num)
217 218 
      {}
... ... 
@@ -234,3 +235,4 @@
234 235 
          // Traverse outgoing residual arcs
235 
          for (int a = _first_out[u]; a != _first_out[u+1]; ++a) {
236 
          int last_out = _geq ? _first_out[u+1] : _first_out[u+1] - 1;
237 
          for (int a = _first_out[u]; a != last_out; ++a) {
236 238 
            if (_res_cap[a] < delta) continue;
... ... 
@@ -689,3 +691,3 @@
689 691
690 
      // Initialize maps
692 
      // Initialize vectors
691 693 
      for (int i = 0; i != _root; ++i) {
... ... 
@@ -696,5 +698,8 @@
696 698 
      // Remove non-zero lower bounds
699 
      const Value MAX = std::numeric_limits<Value>::max();
700 
      int last_out;
697 701 
      if (_have_lower) {
698 702 
        for (int i = 0; i != _root; ++i) {
699 
          for (int j = _first_out[i]; j != _first_out[i+1]; ++j) {
703 
          last_out = _first_out[i+1];
704 
          for (int j = _first_out[i]; j != last_out; ++j) {
700 705 
            if (_forward[j]) {
... ... 
@@ -702,5 +707,5 @@
702 707 
              if (c >= 0) {
703 
                _res_cap[j] = _upper[j] < INF ? _upper[j] - c : INF;
708 
                _res_cap[j] = _upper[j] < MAX ? _upper[j] - c : INF;
704 709 
              } else {
705 
                _res_cap[j] = _upper[j] < INF + c ? _upper[j] - c : INF;
710 
                _res_cap[j] = _upper[j] < MAX + c ? _upper[j] - c : INF;
706 711 
              }
... ... 
@@ -720,11 +725,12 @@
720 725 
      // Handle negative costs
721 
      for (int u = 0; u != _root; ++u) {
722 
        for (int a = _first_out[u]; a != _first_out[u+1]; ++a) {
723 
          Value rc = _res_cap[a];
724 
          if (_cost[a] < 0 && rc > 0) {
725 
            if (rc == INF) return UNBOUNDED;
726 
            _excess[u] -= rc;
727 
            _excess[_target[a]] += rc;
728 
            _res_cap[a] = 0;
729 
            _res_cap[_reverse[a]] += rc;
726 
      for (int i = 0; i != _root; ++i) {
727 
        last_out = _first_out[i+1] - 1;
728 
        for (int j = _first_out[i]; j != last_out; ++j) {
729 
          Value rc = _res_cap[j];
730 
          if (_cost[j] < 0 && rc > 0) {
731 
            if (rc >= MAX) return UNBOUNDED;
732 
            _excess[i] -= rc;
733 
            _excess[_target[j]] += rc;
734 
            _res_cap[j] = 0;
735 
            _res_cap[_reverse[j]] += rc;
730 736 
          }
... ... 
@@ -738,11 +744,7 @@
738 744 
        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
739 
          int u = _target[a];
740 
          if (_excess[u] < 0) {
741 
            _res_cap[a] = -_excess[u] + 1;
742 
          } else {
743 
            _res_cap[a] = 1;
744 
          }
745 
          _res_cap[_reverse[a]] = 0;
745 
          int ra = _reverse[a];
746 
          _res_cap[a] = -_sum_supply + 1;
747 
          _res_cap[ra] = 0;
746 748 
          _cost[a] = 0;
747 
          _cost[_reverse[a]] = 0;
749 
          _cost[ra] = 0;
748 750 
        }
... ... 
@@ -752,6 +754,7 @@
752 754 
        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
755 
          int ra = _reverse[a];
753 756 
          _res_cap[a] = 1;
754 
          _res_cap[_reverse[a]] = 0;
757 
          _res_cap[ra] = 0;
755 758 
          _cost[a] = 0;
756 
          _cost[_reverse[a]] = 0;
759 
          _cost[ra] = 0;
757 760 
        }
... ... 
@@ -764,4 +767,5 @@
764 767 
        for (int i = 0; i != _node_num; ++i) {
765 
          if ( _excess[i] > max_sup) max_sup =  _excess[i];
766 
          if (-_excess[i] > max_dem) max_dem = -_excess[i];
768 
          Value ex = _excess[i];
769 
          if ( ex > max_sup) max_sup =  ex;
770 
          if (-ex > max_dem) max_dem = -ex;
767 771 
        }
... ... 
@@ -791,3 +795,4 @@
791 795 
      if (_have_lower) {
792 
        for (int j = 0; j != _res_arc_num - _node_num + 1; ++j) {
796 
        int limit = _first_out[_root];
797 
        for (int j = 0; j != limit; ++j) {
793 798 
          if (!_forward[j]) _res_cap[j] += _lower[j];
... ... 
@@ -814,4 +819,7 @@
814 819 
        // Saturate all arcs not satisfying the optimality condition
820 
        int last_out;
815 821 
        for (int u = 0; u != _node_num; ++u) {
816 
          for (int a = _first_out[u]; a != _first_out[u+1]; ++a) {
822 
          last_out = _sum_supply < 0 ?
823 
            _first_out[u+1] : _first_out[u+1] - 1;
824 
          for (int a = _first_out[u]; a != last_out; ++a) {
817 825 
            int v = _target[a];
... ... 
@@ -832,4 +840,5 @@
832 840 
        for (int u = 0; u != _node_num; ++u) {
833 
          if (_excess[u] >=  _delta) _excess_nodes.push_back(u);
834 
          if (_excess[u] <= -_delta) _deficit_nodes.push_back(u);
841 
          Value ex = _excess[u];
842 
          if (ex >=  _delta) _excess_nodes.push_back(u);
843 
          if (ex <= -_delta) _deficit_nodes.push_back(u);
835 844 
        }
lemon/network_simplex.h
Show white space 2 line context
... ... 
@@ -166,3 +166,3 @@
166 166 
    typedef std::vector<int> IntVector;
167 
    typedef std::vector<bool> BoolVector;
167 
    typedef std::vector<char> CharVector;
168 168 
    typedef std::vector<Value> ValueVector;
... ... 
@@ -214,4 +214,4 @@
214 214 
    IntVector _dirty_revs;
215 
    BoolVector _forward;
216 
    IntVector _state;
215 
    CharVector _forward;
216 
    CharVector _state;
217 217 
    int _root;
... ... 
@@ -224,2 +224,4 @@
224 224 

			




	
	225
	
		
    const Value MAX;


			




	
	226
	
		

			




	225
	227
	
		
  public:


			




	...
	...
	
		
@@ -244,3 +246,3 @@


			




	244
	246
	
		
      const CostVector &_cost;


			




	245
	
	
		
      const IntVector  &_state;


			




	
	247
	
		
      const CharVector &_state;


			




	246
	248
	
		
      const CostVector &_pi;


			




	...
	...
	
		
@@ -296,3 +298,3 @@


			




	296
	298
	
		
      const CostVector &_cost;


			




	297
	
	
		
      const IntVector  &_state;


			




	
	299
	
		
      const CharVector &_state;


			




	298
	300
	
		
      const CostVector &_pi;


			




	...
	...
	
		
@@ -335,3 +337,3 @@


			




	335
	337
	
		
      const CostVector &_cost;


			




	336
	
	
		
      const IntVector  &_state;


			




	
	338
	
		
      const CharVector &_state;


			




	337
	339
	
		
      const CostVector &_pi;


			




	...
	...
	
		
@@ -408,3 +410,3 @@


			




	408
	410
	
		
      const CostVector &_cost;


			




	409
	
	
		
      const IntVector  &_state;


			




	
	411
	
		
      const CharVector &_state;


			




	410
	412
	
		
      const CostVector &_pi;


			




	...
	...
	
		
@@ -511,3 +513,3 @@


			




	511
	513
	
		
      const CostVector &_cost;


			




	512
	
	
		
      const IntVector  &_state;


			




	
	514
	
		
      const CharVector &_state;


			




	513
	515
	
		
      const CostVector &_pi;


			




	...
	...
	
		
@@ -633,5 +635,5 @@


			




	633
	635
	
		
      _graph(graph), _node_id(graph), _arc_id(graph),


			




	
	636
	
		
      MAX(std::numeric_limits<Value>::max()),


			




	634
	637
	
		
      INF(std::numeric_limits<Value>::has_infinity ?


			




	635
	
	
		
          std::numeric_limits<Value>::infinity() :


			




	636
	
	
		
          std::numeric_limits<Value>::max())


			




	
	638
	
		
          std::numeric_limits<Value>::infinity() : MAX)


			




	637
	639
	
		
    {


			




	...
	...
	
		
@@ -1022,5 +1024,5 @@


			




	1022
	1024
	
		
          if (c >= 0) {


			




	1023
	
	
		
            _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;


			




	
	1025
	
		
            _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;


			




	1024
	1026
	
		
          } else {


			




	1025
	
	
		
            _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;


			




	
	1027
	
		
            _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;


			




	1026
	1028
	
		
          }


			




	...
	...
	
		
@@ -1216,3 +1218,3 @@


			




	1216
	1218
	
		
        d = _forward[u] ?


			




	1217
	
	
		
          _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);


			




	
	1219
	
		
          _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);


			




	1218
	1220
	
		
        if (d < delta) {


			




	...
	...
	
		
@@ -1227,3 +1229,3 @@


			




	1227
	1229
	
		
        d = _forward[u] ? 


			




	1228
	
	
		
          (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];


			




	
	1230
	
		
          (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];


			




	1229
	1231
	
		
        if (d <= delta) {


			




	...
	...
	
		
@@ -1426,3 +1428,3 @@


			




	1426
	1428
	
		
        bool change = findLeavingArc();


			




	1427
	
	
		
        if (delta >= INF) return UNBOUNDED;


			




	
	1429
	
		
        if (delta >= MAX) return UNBOUNDED;


			




	1428
	1430
	
		
        changeFlow(change);


			




        

    






    
    



    


    

     
    
0 comments (0 inline)