lemon/max_matching.h
changeset 599 f63e87b9748e
parent 559 c5fd2d996909
child 590 b61354458b59
     1.1 --- a/lemon/max_matching.h	Sat Apr 18 21:54:30 2009 +0200
     1.2 +++ b/lemon/max_matching.h	Tue Apr 21 10:34:49 2009 +0100
     1.3 @@ -282,20 +282,20 @@
     1.4          Node base = (*_blossom_rep)[_blossom_set->find(node)];
     1.5  
     1.6          while (base != nca) {
     1.7 -          _ear->set(node, arc);
     1.8 +          (*_ear)[node] = arc;
     1.9  
    1.10            Node n = node;
    1.11            while (n != base) {
    1.12              n = _graph.target((*_matching)[n]);
    1.13              Arc a = (*_ear)[n];
    1.14              n = _graph.target(a);
    1.15 -            _ear->set(n, _graph.oppositeArc(a));
    1.16 +            (*_ear)[n] = _graph.oppositeArc(a);
    1.17            }
    1.18            node = _graph.target((*_matching)[base]);
    1.19            _tree_set->erase(base);
    1.20            _tree_set->erase(node);
    1.21            _blossom_set->insert(node, _blossom_set->find(base));
    1.22 -          _status->set(node, EVEN);
    1.23 +          (*_status)[node] = EVEN;
    1.24            _node_queue[_last++] = node;
    1.25            arc = _graph.oppositeArc((*_ear)[node]);
    1.26            node = _graph.target((*_ear)[node]);
    1.27 @@ -304,7 +304,7 @@
    1.28          }
    1.29        }
    1.30  
    1.31 -      _blossom_rep->set(_blossom_set->find(nca), nca);
    1.32 +      (*_blossom_rep)[_blossom_set->find(nca)] = nca;
    1.33  
    1.34        {
    1.35  
    1.36 @@ -313,20 +313,20 @@
    1.37          Node base = (*_blossom_rep)[_blossom_set->find(node)];
    1.38  
    1.39          while (base != nca) {
    1.40 -          _ear->set(node, arc);
    1.41 +          (*_ear)[node] = arc;
    1.42  
    1.43            Node n = node;
    1.44            while (n != base) {
    1.45              n = _graph.target((*_matching)[n]);
    1.46              Arc a = (*_ear)[n];
    1.47              n = _graph.target(a);
    1.48 -            _ear->set(n, _graph.oppositeArc(a));
    1.49 +            (*_ear)[n] = _graph.oppositeArc(a);
    1.50            }
    1.51            node = _graph.target((*_matching)[base]);
    1.52            _tree_set->erase(base);
    1.53            _tree_set->erase(node);
    1.54            _blossom_set->insert(node, _blossom_set->find(base));
    1.55 -          _status->set(node, EVEN);
    1.56 +          (*_status)[node] = EVEN;
    1.57            _node_queue[_last++] = node;
    1.58            arc = _graph.oppositeArc((*_ear)[node]);
    1.59            node = _graph.target((*_ear)[node]);
    1.60 @@ -335,7 +335,7 @@
    1.61          }
    1.62        }
    1.63  
    1.64 -      _blossom_rep->set(_blossom_set->find(nca), nca);
    1.65 +      (*_blossom_rep)[_blossom_set->find(nca)] = nca;
    1.66      }
    1.67  
    1.68  
    1.69 @@ -344,11 +344,11 @@
    1.70        Node base = _graph.source(a);
    1.71        Node odd = _graph.target(a);
    1.72  
    1.73 -      _ear->set(odd, _graph.oppositeArc(a));
    1.74 +      (*_ear)[odd] = _graph.oppositeArc(a);
    1.75        Node even = _graph.target((*_matching)[odd]);
    1.76 -      _blossom_rep->set(_blossom_set->insert(even), even);
    1.77 -      _status->set(odd, ODD);
    1.78 -      _status->set(even, EVEN);
    1.79 +      (*_blossom_rep)[_blossom_set->insert(even)] = even;
    1.80 +      (*_status)[odd] = ODD;
    1.81 +      (*_status)[even] = EVEN;
    1.82        int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(base)]);
    1.83        _tree_set->insert(odd, tree);
    1.84        _tree_set->insert(even, tree);
    1.85 @@ -362,30 +362,30 @@
    1.86  
    1.87        int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(even)]);
    1.88  
    1.89 -      _matching->set(odd, _graph.oppositeArc(a));
    1.90 -      _status->set(odd, MATCHED);
    1.91 +      (*_matching)[odd] = _graph.oppositeArc(a);
    1.92 +      (*_status)[odd] = MATCHED;
    1.93  
    1.94        Arc arc = (*_matching)[even];
    1.95 -      _matching->set(even, a);
    1.96 +      (*_matching)[even] = a;
    1.97  
    1.98        while (arc != INVALID) {
    1.99          odd = _graph.target(arc);
   1.100          arc = (*_ear)[odd];
   1.101          even = _graph.target(arc);
   1.102 -        _matching->set(odd, arc);
   1.103 +        (*_matching)[odd] = arc;
   1.104          arc = (*_matching)[even];
   1.105 -        _matching->set(even, _graph.oppositeArc((*_matching)[odd]));
   1.106 +        (*_matching)[even] = _graph.oppositeArc((*_matching)[odd]);
   1.107        }
   1.108  
   1.109        for (typename TreeSet::ItemIt it(*_tree_set, tree);
   1.110             it != INVALID; ++it) {
   1.111          if ((*_status)[it] == ODD) {
   1.112 -          _status->set(it, MATCHED);
   1.113 +          (*_status)[it] = MATCHED;
   1.114          } else {
   1.115            int blossom = _blossom_set->find(it);
   1.116            for (typename BlossomSet::ItemIt jt(*_blossom_set, blossom);
   1.117                 jt != INVALID; ++jt) {
   1.118 -            _status->set(jt, MATCHED);
   1.119 +            (*_status)[jt] = MATCHED;
   1.120            }
   1.121            _blossom_set->eraseClass(blossom);
   1.122          }
   1.123 @@ -427,8 +427,8 @@
   1.124      void init() {
   1.125        createStructures();
   1.126        for(NodeIt n(_graph); n != INVALID; ++n) {
   1.127 -        _matching->set(n, INVALID);
   1.128 -        _status->set(n, UNMATCHED);
   1.129 +        (*_matching)[n] = INVALID;
   1.130 +        (*_status)[n] = UNMATCHED;
   1.131        }
   1.132      }
   1.133  
   1.134 @@ -438,18 +438,18 @@
   1.135      void greedyInit() {
   1.136        createStructures();
   1.137        for (NodeIt n(_graph); n != INVALID; ++n) {
   1.138 -        _matching->set(n, INVALID);
   1.139 -        _status->set(n, UNMATCHED);
   1.140 +        (*_matching)[n] = INVALID;
   1.141 +        (*_status)[n] = UNMATCHED;
   1.142        }
   1.143        for (NodeIt n(_graph); n != INVALID; ++n) {
   1.144          if ((*_matching)[n] == INVALID) {
   1.145            for (OutArcIt a(_graph, n); a != INVALID ; ++a) {
   1.146              Node v = _graph.target(a);
   1.147              if ((*_matching)[v] == INVALID && v != n) {
   1.148 -              _matching->set(n, a);
   1.149 -              _status->set(n, MATCHED);
   1.150 -              _matching->set(v, _graph.oppositeArc(a));
   1.151 -              _status->set(v, MATCHED);
   1.152 +              (*_matching)[n] = a;
   1.153 +              (*_status)[n] = MATCHED;
   1.154 +              (*_matching)[v] = _graph.oppositeArc(a);
   1.155 +              (*_status)[v] = MATCHED;
   1.156                break;
   1.157              }
   1.158            }
   1.159 @@ -469,21 +469,21 @@
   1.160        createStructures();
   1.161  
   1.162        for (NodeIt n(_graph); n != INVALID; ++n) {
   1.163 -        _matching->set(n, INVALID);
   1.164 -        _status->set(n, UNMATCHED);
   1.165 +        (*_matching)[n] = INVALID;
   1.166 +        (*_status)[n] = UNMATCHED;
   1.167        }
   1.168        for(EdgeIt e(_graph); e!=INVALID; ++e) {
   1.169          if (matching[e]) {
   1.170  
   1.171            Node u = _graph.u(e);
   1.172            if ((*_matching)[u] != INVALID) return false;
   1.173 -          _matching->set(u, _graph.direct(e, true));
   1.174 -          _status->set(u, MATCHED);
   1.175 +          (*_matching)[u] = _graph.direct(e, true);
   1.176 +          (*_status)[u] = MATCHED;
   1.177  
   1.178            Node v = _graph.v(e);
   1.179            if ((*_matching)[v] != INVALID) return false;
   1.180 -          _matching->set(v, _graph.direct(e, false));
   1.181 -          _status->set(v, MATCHED);
   1.182 +          (*_matching)[v] = _graph.direct(e, false);
   1.183 +          (*_status)[v] = MATCHED;
   1.184          }
   1.185        }
   1.186        return true;
   1.187 @@ -497,7 +497,7 @@
   1.188          if ((*_status)[n] == UNMATCHED) {
   1.189            (*_blossom_rep)[_blossom_set->insert(n)] = n;
   1.190            _tree_set->insert(n);
   1.191 -          _status->set(n, EVEN);
   1.192 +          (*_status)[n] = EVEN;
   1.193            processSparse(n);
   1.194          }
   1.195        }
   1.196 @@ -512,7 +512,7 @@
   1.197          if ((*_status)[n] == UNMATCHED) {
   1.198            (*_blossom_rep)[_blossom_set->insert(n)] = n;
   1.199            _tree_set->insert(n);
   1.200 -          _status->set(n, EVEN);
   1.201 +          (*_status)[n] = EVEN;
   1.202            processDense(n);
   1.203          }
   1.204        }
   1.205 @@ -1548,9 +1548,9 @@
   1.206          int bi = (*_node_index)[base];
   1.207          Value pot = (*_node_data)[bi].pot;
   1.208  
   1.209 -        _matching->set(base, matching);
   1.210 +        (*_matching)[base] = matching;
   1.211          _blossom_node_list.push_back(base);
   1.212 -        _node_potential->set(base, pot);
   1.213 +        (*_node_potential)[base] = pot;
   1.214        } else {
   1.215  
   1.216          Value pot = (*_blossom_data)[blossom].pot;
   1.217 @@ -1644,17 +1644,17 @@
   1.218        createStructures();
   1.219  
   1.220        for (ArcIt e(_graph); e != INVALID; ++e) {
   1.221 -        _node_heap_index->set(e, BinHeap<Value, IntArcMap>::PRE_HEAP);
   1.222 +        (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
   1.223        }
   1.224        for (NodeIt n(_graph); n != INVALID; ++n) {
   1.225 -        _delta1_index->set(n, _delta1->PRE_HEAP);
   1.226 +        (*_delta1_index)[n] = _delta1->PRE_HEAP;
   1.227        }
   1.228        for (EdgeIt e(_graph); e != INVALID; ++e) {
   1.229 -        _delta3_index->set(e, _delta3->PRE_HEAP);
   1.230 +        (*_delta3_index)[e] = _delta3->PRE_HEAP;
   1.231        }
   1.232        for (int i = 0; i < _blossom_num; ++i) {
   1.233 -        _delta2_index->set(i, _delta2->PRE_HEAP);
   1.234 -        _delta4_index->set(i, _delta4->PRE_HEAP);
   1.235 +        (*_delta2_index)[i] = _delta2->PRE_HEAP;
   1.236 +        (*_delta4_index)[i] = _delta4->PRE_HEAP;
   1.237        }
   1.238  
   1.239        int index = 0;
   1.240 @@ -1666,7 +1666,7 @@
   1.241              max = (dualScale * _weight[e]) / 2;
   1.242            }
   1.243          }
   1.244 -        _node_index->set(n, index);
   1.245 +        (*_node_index)[n] = index;
   1.246          (*_node_data)[index].pot = max;
   1.247          _delta1->push(n, max);
   1.248          int blossom =
   1.249 @@ -2741,9 +2741,9 @@
   1.250          int bi = (*_node_index)[base];
   1.251          Value pot = (*_node_data)[bi].pot;
   1.252  
   1.253 -        _matching->set(base, matching);
   1.254 +        (*_matching)[base] = matching;
   1.255          _blossom_node_list.push_back(base);
   1.256 -        _node_potential->set(base, pot);
   1.257 +        (*_node_potential)[base] = pot;
   1.258        } else {
   1.259  
   1.260          Value pot = (*_blossom_data)[blossom].pot;
   1.261 @@ -2831,14 +2831,14 @@
   1.262        createStructures();
   1.263  
   1.264        for (ArcIt e(_graph); e != INVALID; ++e) {
   1.265 -        _node_heap_index->set(e, BinHeap<Value, IntArcMap>::PRE_HEAP);
   1.266 +        (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
   1.267        }
   1.268        for (EdgeIt e(_graph); e != INVALID; ++e) {
   1.269 -        _delta3_index->set(e, _delta3->PRE_HEAP);
   1.270 +        (*_delta3_index)[e] = _delta3->PRE_HEAP;
   1.271        }
   1.272        for (int i = 0; i < _blossom_num; ++i) {
   1.273 -        _delta2_index->set(i, _delta2->PRE_HEAP);
   1.274 -        _delta4_index->set(i, _delta4->PRE_HEAP);
   1.275 +        (*_delta2_index)[i] = _delta2->PRE_HEAP;
   1.276 +        (*_delta4_index)[i] = _delta4->PRE_HEAP;
   1.277        }
   1.278  
   1.279        int index = 0;
   1.280 @@ -2850,7 +2850,7 @@
   1.281              max = (dualScale * _weight[e]) / 2;
   1.282            }
   1.283          }
   1.284 -        _node_index->set(n, index);
   1.285 +        (*_node_index)[n] = index;
   1.286          (*_node_data)[index].pot = max;
   1.287          int blossom =
   1.288            _blossom_set->insert(n, std::numeric_limits<Value>::max());