gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Minor improvements in CostScaling (#417)
0 1 0
default
1 file changed with 44 insertions and 32 deletions:
↑ Collapse diff ↑
Show white space 2 line context
... ...
@@ -577,14 +577,21 @@
577 577

	
578
    /// \brief Reset all the parameters that have been given before.
578
    /// \brief Reset the internal data structures and all the parameters
579
    /// that have been given before.
579 580
    ///
580
    /// This function resets all the paramaters that have been given
581
    /// before using functions \ref lowerMap(), \ref upperMap(),
582
    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
581
    /// This function resets the internal data structures and all the
582
    /// paramaters that have been given before using functions \ref lowerMap(),
583
    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
583 584
    ///
584
    /// It is useful for multiple run() calls. If this function is not
585
    /// used, all the parameters given before are kept for the next
586
    /// \ref run() call.
587
    /// However, the underlying digraph must not be modified after this
588
    /// class have been constructed, since it copies and extends the graph.
585
    /// It is useful for multiple \ref run() calls. By default, all the given
586
    /// parameters are kept for the next \ref run() call, unless
587
    /// \ref resetParams() or \ref reset() is used.
588
    /// If the underlying digraph was also modified after the construction
589
    /// of the class or the last \ref reset() call, then the \ref reset()
590
    /// function must be used, otherwise \ref resetParams() is sufficient.
591
    ///
592
    /// See \ref resetParams() for examples.
593
    ///
589 594
    /// \return <tt>(*this)</tt>
595
    ///
596
    /// \see resetParams(), run()
590 597
    CostScaling& reset() {
... ...
@@ -892,10 +899,2 @@
892 899

	
893
      return OPTIMAL;
894
    }
895

	
896
    // Execute the algorithm and transform the results
897
    void start(Method method) {
898
      // Maximum path length for partial augment
899
      const int MAX_PATH_LENGTH = 4;
900

	
901 900
      // Initialize data structures for buckets
... ...
@@ -907,3 +906,9 @@
907 906

	
908
      // Execute the algorithm
907
      return OPTIMAL;
908
    }
909

	
910
    // Execute the algorithm and transform the results
911
    void start(Method method) {
912
      const int MAX_PARTIAL_PATH_LENGTH = 4;
913

	
909 914
      switch (method) {
... ...
@@ -916,3 +921,3 @@
916 921
        case PARTIAL_AUGMENT:
917
          startAugment(MAX_PATH_LENGTH);
922
          startAugment(MAX_PARTIAL_PATH_LENGTH);
918 923
          break;
... ...
@@ -953,5 +958,6 @@
953 958
        for (int a = _first_out[u]; a != last_out; ++a) {
959
          Value delta = _res_cap[a];
960
          if (delta > 0) {
954 961
          int v = _target[a];
955
          if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) {
956
            Value delta = _res_cap[a];
962
            if (_cost[a] + pi_u - _pi[v] < 0) {
957 963
            _excess[u] -= delta;
... ...
@@ -963,2 +969,3 @@
963 969
      }
970
      }
964 971

	
... ...
@@ -1003,3 +1010,3 @@
1003 1010
    void globalUpdate() {
1004
      int bucket_end = _root + 1;
1011
      const int bucket_end = _root + 1;
1005 1012

	
... ...
@@ -1010,2 +1017,3 @@
1010 1017
      Value total_excess = 0;
1018
      int b0 = bucket_end;
1011 1019
      for (int i = 0; i != _res_node_num; ++i) {
... ...
@@ -1013,5 +1021,5 @@
1013 1021
          _rank[i] = 0;
1014
          _bucket_next[i] = _buckets[0];
1015
          _bucket_prev[_buckets[0]] = i;
1016
          _buckets[0] = i;
1022
          _bucket_next[i] = b0;
1023
          _bucket_prev[b0] = i;
1024
          b0 = i;
1017 1025
        } else {
... ...
@@ -1022,2 +1030,3 @@
1022 1030
      if (total_excess == 0) return;
1031
      _buckets[0] = b0;
1023 1032

	
... ...
@@ -1043,4 +1052,5 @@
1043 1052
                int new_rank_v = old_rank_v;
1044
                if (nrc < LargeCost(_max_rank))
1045
                  new_rank_v = r + 1 + int(nrc);
1053
                if (nrc < LargeCost(_max_rank)) {
1054
                  new_rank_v = r + 1 + static_cast<int>(nrc);
1055
                }
1046 1056

	
... ...
@@ -1056,4 +1066,5 @@
1056 1066
                    } else {
1057
                      _bucket_next[_bucket_prev[v]] = _bucket_next[v];
1058
                      _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
1067
                      int pv = _bucket_prev[v], nv = _bucket_next[v];
1068
                      _bucket_next[pv] = nv;
1069
                      _bucket_prev[nv] = pv;
1059 1070
                    }
... ...
@@ -1061,5 +1072,6 @@
1061 1072

	
1062
                  // Insert v to its new bucket
1063
                  _bucket_next[v] = _buckets[new_rank_v];
1064
                  _bucket_prev[_buckets[new_rank_v]] = v;
1073
                  // Insert v into its new bucket
1074
                  int nv = _buckets[new_rank_v];
1075
                  _bucket_next[v] = nv;
1076
                  _bucket_prev[nv] = v;
1065 1077
                  _buckets[new_rank_v] = v;
0 comments (0 inline)