COIN-OR::LEMON - Graph Library

Changeset 581:aa1804409f29 in lemon-1.2 for lemon/max_matching.h


Ignore:
Timestamp:
04/14/09 10:35:38 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Exploit that the standard maps are reference maps (#190)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/max_matching.h

    r559 r581  
    283283
    284284        while (base != nca) {
    285           _ear->set(node, arc);
     285          (*_ear)[node] = arc;
    286286
    287287          Node n = node;
     
    290290            Arc a = (*_ear)[n];
    291291            n = _graph.target(a);
    292             _ear->set(n, _graph.oppositeArc(a));
     292            (*_ear)[n] = _graph.oppositeArc(a);
    293293          }
    294294          node = _graph.target((*_matching)[base]);
     
    296296          _tree_set->erase(node);
    297297          _blossom_set->insert(node, _blossom_set->find(base));
    298           _status->set(node, EVEN);
     298          (*_status)[node] = EVEN;
    299299          _node_queue[_last++] = node;
    300300          arc = _graph.oppositeArc((*_ear)[node]);
     
    305305      }
    306306
    307       _blossom_rep->set(_blossom_set->find(nca), nca);
     307      (*_blossom_rep)[_blossom_set->find(nca)] = nca;
    308308
    309309      {
     
    314314
    315315        while (base != nca) {
    316           _ear->set(node, arc);
     316          (*_ear)[node] = arc;
    317317
    318318          Node n = node;
     
    321321            Arc a = (*_ear)[n];
    322322            n = _graph.target(a);
    323             _ear->set(n, _graph.oppositeArc(a));
     323            (*_ear)[n] = _graph.oppositeArc(a);
    324324          }
    325325          node = _graph.target((*_matching)[base]);
     
    327327          _tree_set->erase(node);
    328328          _blossom_set->insert(node, _blossom_set->find(base));
    329           _status->set(node, EVEN);
     329          (*_status)[node] = EVEN;
    330330          _node_queue[_last++] = node;
    331331          arc = _graph.oppositeArc((*_ear)[node]);
     
    336336      }
    337337
    338       _blossom_rep->set(_blossom_set->find(nca), nca);
     338      (*_blossom_rep)[_blossom_set->find(nca)] = nca;
    339339    }
    340340
     
    345345      Node odd = _graph.target(a);
    346346
    347       _ear->set(odd, _graph.oppositeArc(a));
     347      (*_ear)[odd] = _graph.oppositeArc(a);
    348348      Node even = _graph.target((*_matching)[odd]);
    349       _blossom_rep->set(_blossom_set->insert(even), even);
    350       _status->set(odd, ODD);
    351       _status->set(even, EVEN);
     349      (*_blossom_rep)[_blossom_set->insert(even)] = even;
     350      (*_status)[odd] = ODD;
     351      (*_status)[even] = EVEN;
    352352      int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(base)]);
    353353      _tree_set->insert(odd, tree);
     
    363363      int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(even)]);
    364364
    365       _matching->set(odd, _graph.oppositeArc(a));
    366       _status->set(odd, MATCHED);
     365      (*_matching)[odd] = _graph.oppositeArc(a);
     366      (*_status)[odd] = MATCHED;
    367367
    368368      Arc arc = (*_matching)[even];
    369       _matching->set(even, a);
     369      (*_matching)[even] = a;
    370370
    371371      while (arc != INVALID) {
     
    373373        arc = (*_ear)[odd];
    374374        even = _graph.target(arc);
    375         _matching->set(odd, arc);
     375        (*_matching)[odd] = arc;
    376376        arc = (*_matching)[even];
    377         _matching->set(even, _graph.oppositeArc((*_matching)[odd]));
     377        (*_matching)[even] = _graph.oppositeArc((*_matching)[odd]);
    378378      }
    379379
     
    381381           it != INVALID; ++it) {
    382382        if ((*_status)[it] == ODD) {
    383           _status->set(it, MATCHED);
     383          (*_status)[it] = MATCHED;
    384384        } else {
    385385          int blossom = _blossom_set->find(it);
    386386          for (typename BlossomSet::ItemIt jt(*_blossom_set, blossom);
    387387               jt != INVALID; ++jt) {
    388             _status->set(jt, MATCHED);
     388            (*_status)[jt] = MATCHED;
    389389          }
    390390          _blossom_set->eraseClass(blossom);
     
    428428      createStructures();
    429429      for(NodeIt n(_graph); n != INVALID; ++n) {
    430         _matching->set(n, INVALID);
    431         _status->set(n, UNMATCHED);
     430        (*_matching)[n] = INVALID;
     431        (*_status)[n] = UNMATCHED;
    432432      }
    433433    }
     
    439439      createStructures();
    440440      for (NodeIt n(_graph); n != INVALID; ++n) {
    441         _matching->set(n, INVALID);
    442         _status->set(n, UNMATCHED);
     441        (*_matching)[n] = INVALID;
     442        (*_status)[n] = UNMATCHED;
    443443      }
    444444      for (NodeIt n(_graph); n != INVALID; ++n) {
     
    447447            Node v = _graph.target(a);
    448448            if ((*_matching)[v] == INVALID && v != n) {
    449               _matching->set(n, a);
    450               _status->set(n, MATCHED);
    451               _matching->set(v, _graph.oppositeArc(a));
    452               _status->set(v, MATCHED);
     449              (*_matching)[n] = a;
     450              (*_status)[n] = MATCHED;
     451              (*_matching)[v] = _graph.oppositeArc(a);
     452              (*_status)[v] = MATCHED;
    453453              break;
    454454            }
     
    470470
    471471      for (NodeIt n(_graph); n != INVALID; ++n) {
    472         _matching->set(n, INVALID);
    473         _status->set(n, UNMATCHED);
     472        (*_matching)[n] = INVALID;
     473        (*_status)[n] = UNMATCHED;
    474474      }
    475475      for(EdgeIt e(_graph); e!=INVALID; ++e) {
     
    478478          Node u = _graph.u(e);
    479479          if ((*_matching)[u] != INVALID) return false;
    480           _matching->set(u, _graph.direct(e, true));
    481           _status->set(u, MATCHED);
     480          (*_matching)[u] = _graph.direct(e, true);
     481          (*_status)[u] = MATCHED;
    482482
    483483          Node v = _graph.v(e);
    484484          if ((*_matching)[v] != INVALID) return false;
    485           _matching->set(v, _graph.direct(e, false));
    486           _status->set(v, MATCHED);
     485          (*_matching)[v] = _graph.direct(e, false);
     486          (*_status)[v] = MATCHED;
    487487        }
    488488      }
     
    498498          (*_blossom_rep)[_blossom_set->insert(n)] = n;
    499499          _tree_set->insert(n);
    500           _status->set(n, EVEN);
     500          (*_status)[n] = EVEN;
    501501          processSparse(n);
    502502        }
     
    513513          (*_blossom_rep)[_blossom_set->insert(n)] = n;
    514514          _tree_set->insert(n);
    515           _status->set(n, EVEN);
     515          (*_status)[n] = EVEN;
    516516          processDense(n);
    517517        }
     
    15491549        Value pot = (*_node_data)[bi].pot;
    15501550
    1551         _matching->set(base, matching);
     1551        (*_matching)[base] = matching;
    15521552        _blossom_node_list.push_back(base);
    1553         _node_potential->set(base, pot);
     1553        (*_node_potential)[base] = pot;
    15541554      } else {
    15551555
     
    16451645
    16461646      for (ArcIt e(_graph); e != INVALID; ++e) {
    1647         _node_heap_index->set(e, BinHeap<Value, IntArcMap>::PRE_HEAP);
     1647        (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
    16481648      }
    16491649      for (NodeIt n(_graph); n != INVALID; ++n) {
    1650         _delta1_index->set(n, _delta1->PRE_HEAP);
     1650        (*_delta1_index)[n] = _delta1->PRE_HEAP;
    16511651      }
    16521652      for (EdgeIt e(_graph); e != INVALID; ++e) {
    1653         _delta3_index->set(e, _delta3->PRE_HEAP);
     1653        (*_delta3_index)[e] = _delta3->PRE_HEAP;
    16541654      }
    16551655      for (int i = 0; i < _blossom_num; ++i) {
    1656         _delta2_index->set(i, _delta2->PRE_HEAP);
    1657         _delta4_index->set(i, _delta4->PRE_HEAP);
     1656        (*_delta2_index)[i] = _delta2->PRE_HEAP;
     1657        (*_delta4_index)[i] = _delta4->PRE_HEAP;
    16581658      }
    16591659
     
    16671667          }
    16681668        }
    1669         _node_index->set(n, index);
     1669        (*_node_index)[n] = index;
    16701670        (*_node_data)[index].pot = max;
    16711671        _delta1->push(n, max);
     
    27422742        Value pot = (*_node_data)[bi].pot;
    27432743
    2744         _matching->set(base, matching);
     2744        (*_matching)[base] = matching;
    27452745        _blossom_node_list.push_back(base);
    2746         _node_potential->set(base, pot);
     2746        (*_node_potential)[base] = pot;
    27472747      } else {
    27482748
     
    28322832
    28332833      for (ArcIt e(_graph); e != INVALID; ++e) {
    2834         _node_heap_index->set(e, BinHeap<Value, IntArcMap>::PRE_HEAP);
     2834        (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
    28352835      }
    28362836      for (EdgeIt e(_graph); e != INVALID; ++e) {
    2837         _delta3_index->set(e, _delta3->PRE_HEAP);
     2837        (*_delta3_index)[e] = _delta3->PRE_HEAP;
    28382838      }
    28392839      for (int i = 0; i < _blossom_num; ++i) {
    2840         _delta2_index->set(i, _delta2->PRE_HEAP);
    2841         _delta4_index->set(i, _delta4->PRE_HEAP);
     2840        (*_delta2_index)[i] = _delta2->PRE_HEAP;
     2841        (*_delta4_index)[i] = _delta4->PRE_HEAP;
    28422842      }
    28432843
     
    28512851          }
    28522852        }
    2853         _node_index->set(n, index);
     2853        (*_node_index)[n] = index;
    28542854        (*_node_data)[index].pot = max;
    28552855        int blossom =
Note: See TracChangeset for help on using the changeset viewer.