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 4 line context
... ...
@@ -576,16 +576,23 @@
576 576
    }
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() {
591 598
      // Resize vectors
... ...
@@ -891,12 +898,4 @@
891 898
      }
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
902 901
      _max_rank = _alpha * _res_node_num;
... ...
@@ -906,5 +905,11 @@
906 905
      _rank.resize(_res_node_num + 1);
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) {
910 915
        case PUSH:
... ...
@@ -915,5 +920,5 @@
915 920
          break;
916 921
        case PARTIAL_AUGMENT:
917
          startAugment(MAX_PATH_LENGTH);
922
          startAugment(MAX_PARTIAL_PATH_LENGTH);
918 923
          break;
919 924
      }
... ...
@@ -952,7 +957,8 @@
952 957
        LargeCost pi_u = _pi[u];
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;
958 964
            _excess[v] += delta;
... ...
@@ -962,4 +968,5 @@
962 968
        }
963 969
      }
970
      }
964 971

	
965 972
      // Find active nodes (i.e. nodes with positive excess)
... ...
@@ -1002,5 +1009,5 @@
1002 1009
    // Global potential update heuristic
1003 1010
    void globalUpdate() {
1004
      int bucket_end = _root + 1;
1011
      const int bucket_end = _root + 1;
1005 1012

	
1006 1013
      // Initialize buckets
... ...
@@ -1009,10 +1016,11 @@
1009 1016
      }
1010 1017
      Value total_excess = 0;
1018
      int b0 = bucket_end;
1011 1019
      for (int i = 0; i != _res_node_num; ++i) {
1012 1020
        if (_excess[i] < 0) {
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 {
1018 1026
          total_excess += _excess[i];
... ...
@@ -1021,4 +1029,5 @@
1021 1029
      }
1022 1030
      if (total_excess == 0) return;
1031
      _buckets[0] = b0;
1023 1032

	
1024 1033
      // Search the buckets
... ...
@@ -1042,6 +1051,7 @@
1042 1051
                LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
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

	
1047 1057
                // Change the rank of v
... ...
@@ -1055,12 +1065,14 @@
1055 1065
                      _buckets[old_rank_v] = _bucket_next[v];
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
                    }
1060 1071
                  }
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;
1066 1078
                }
0 comments (0 inline)