lemon/matching.h
changeset 1073 73c892335e74
parent 876 7f6e2bd76654
child 1092 dceba191c00d
equal deleted inserted replaced
6:9e3db382ffb6 7:b2e5c4b469c9
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
  1621       }
  1621       }
  1622       for (int i = 0; i < _blossom_num; ++i) {
  1622       for (int i = 0; i < _blossom_num; ++i) {
  1623         (*_delta2_index)[i] = _delta2->PRE_HEAP;
  1623         (*_delta2_index)[i] = _delta2->PRE_HEAP;
  1624         (*_delta4_index)[i] = _delta4->PRE_HEAP;
  1624         (*_delta4_index)[i] = _delta4->PRE_HEAP;
  1625       }
  1625       }
  1626       
  1626 
  1627       _unmatched = _node_num;
  1627       _unmatched = _node_num;
  1628 
  1628 
  1629       _delta1->clear();
  1629       _delta1->clear();
  1630       _delta2->clear();
  1630       _delta2->clear();
  1631       _delta3->clear();
  1631       _delta3->clear();
  1676     void fractionalInit() {
  1676     void fractionalInit() {
  1677       createStructures();
  1677       createStructures();
  1678 
  1678 
  1679       _blossom_node_list.clear();
  1679       _blossom_node_list.clear();
  1680       _blossom_potential.clear();
  1680       _blossom_potential.clear();
  1681       
  1681 
  1682       if (_fractional == 0) {
  1682       if (_fractional == 0) {
  1683         _fractional = new FractionalMatching(_graph, _weight, false);
  1683         _fractional = new FractionalMatching(_graph, _weight, false);
  1684       }
  1684       }
  1685       _fractional->run();
  1685       _fractional->run();
  1686 
  1686 
  1748           _delta1->push(n, _fractional->nodeValue(n));
  1748           _delta1->push(n, _fractional->nodeValue(n));
  1749           v = _graph.target(_fractional->matching(n));
  1749           v = _graph.target(_fractional->matching(n));
  1750           while (n != v) {
  1750           while (n != v) {
  1751             subblossoms[--num] = _blossom_set->find(v);
  1751             subblossoms[--num] = _blossom_set->find(v);
  1752             _delta1->push(v, _fractional->nodeValue(v));
  1752             _delta1->push(v, _fractional->nodeValue(v));
  1753             v = _graph.target(_fractional->matching(v));            
  1753             v = _graph.target(_fractional->matching(v));
  1754           }
  1754           }
  1755           
  1755 
  1756           int surface = 
  1756           int surface =
  1757             _blossom_set->join(subblossoms.begin(), subblossoms.end());
  1757             _blossom_set->join(subblossoms.begin(), subblossoms.end());
  1758           (*_blossom_data)[surface].status = EVEN;
  1758           (*_blossom_data)[surface].status = EVEN;
  1759           (*_blossom_data)[surface].pred = INVALID;
  1759           (*_blossom_data)[surface].pred = INVALID;
  1760           (*_blossom_data)[surface].next = INVALID;
  1760           (*_blossom_data)[surface].next = INVALID;
  1761           (*_blossom_data)[surface].pot = 0;
  1761           (*_blossom_data)[surface].pot = 0;
  1762           (*_blossom_data)[surface].offset = 0;
  1762           (*_blossom_data)[surface].offset = 0;
  1763           
  1763 
  1764           _tree_set->insert(surface);
  1764           _tree_set->insert(surface);
  1765           ++_unmatched;
  1765           ++_unmatched;
  1766         }
  1766         }
  1767       }
  1767       }
  1768 
  1768 
  1808               (*_node_data)[ni].heap.push(e, rw);
  1808               (*_node_data)[ni].heap.push(e, rw);
  1809               (*_node_data)[ni].heap_index.insert(std::make_pair(vt, e));
  1809               (*_node_data)[ni].heap_index.insert(std::make_pair(vt, e));
  1810             }
  1810             }
  1811           }
  1811           }
  1812         }
  1812         }
  1813             
  1813 
  1814         if (!(*_node_data)[ni].heap.empty()) {
  1814         if (!(*_node_data)[ni].heap.empty()) {
  1815           _blossom_set->decrease(n, (*_node_data)[ni].heap.prio());
  1815           _blossom_set->decrease(n, (*_node_data)[ni].heap.prio());
  1816           _delta2->push(nb, _blossom_set->classPrio(nb));
  1816           _delta2->push(nb, _blossom_set->classPrio(nb));
  1817         }
  1817         }
  1818       }
  1818       }
  2267     BinHeap<Value, IntIntMap> *_delta4;
  2267     BinHeap<Value, IntIntMap> *_delta4;
  2268 
  2268 
  2269     Value _delta_sum;
  2269     Value _delta_sum;
  2270     int _unmatched;
  2270     int _unmatched;
  2271 
  2271 
  2272     typedef MaxWeightedPerfectFractionalMatching<Graph, WeightMap> 
  2272     typedef MaxWeightedPerfectFractionalMatching<Graph, WeightMap>
  2273     FractionalMatching;
  2273     FractionalMatching;
  2274     FractionalMatching *_fractional;
  2274     FractionalMatching *_fractional;
  2275 
  2275 
  2276     void createStructures() {
  2276     void createStructures() {
  2277       _node_num = countNodes(_graph);
  2277       _node_num = countNodes(_graph);
  3093     void fractionalInit() {
  3093     void fractionalInit() {
  3094       createStructures();
  3094       createStructures();
  3095 
  3095 
  3096       _blossom_node_list.clear();
  3096       _blossom_node_list.clear();
  3097       _blossom_potential.clear();
  3097       _blossom_potential.clear();
  3098       
  3098 
  3099       if (_fractional == 0) {
  3099       if (_fractional == 0) {
  3100         _fractional = new FractionalMatching(_graph, _weight, false);
  3100         _fractional = new FractionalMatching(_graph, _weight, false);
  3101       }
  3101       }
  3102       if (!_fractional->run()) {
  3102       if (!_fractional->run()) {
  3103         _unmatched = -1;
  3103         _unmatched = -1;
  3159 
  3159 
  3160           subblossoms[--num] = _blossom_set->find(n);
  3160           subblossoms[--num] = _blossom_set->find(n);
  3161           v = _graph.target(_fractional->matching(n));
  3161           v = _graph.target(_fractional->matching(n));
  3162           while (n != v) {
  3162           while (n != v) {
  3163             subblossoms[--num] = _blossom_set->find(v);
  3163             subblossoms[--num] = _blossom_set->find(v);
  3164             v = _graph.target(_fractional->matching(v));            
  3164             v = _graph.target(_fractional->matching(v));
  3165           }
  3165           }
  3166           
  3166 
  3167           int surface = 
  3167           int surface =
  3168             _blossom_set->join(subblossoms.begin(), subblossoms.end());
  3168             _blossom_set->join(subblossoms.begin(), subblossoms.end());
  3169           (*_blossom_data)[surface].status = EVEN;
  3169           (*_blossom_data)[surface].status = EVEN;
  3170           (*_blossom_data)[surface].pred = INVALID;
  3170           (*_blossom_data)[surface].pred = INVALID;
  3171           (*_blossom_data)[surface].next = INVALID;
  3171           (*_blossom_data)[surface].next = INVALID;
  3172           (*_blossom_data)[surface].pot = 0;
  3172           (*_blossom_data)[surface].pot = 0;
  3173           (*_blossom_data)[surface].offset = 0;
  3173           (*_blossom_data)[surface].offset = 0;
  3174           
  3174 
  3175           _tree_set->insert(surface);
  3175           _tree_set->insert(surface);
  3176           ++_unmatched;
  3176           ++_unmatched;
  3177         }
  3177         }
  3178       }
  3178       }
  3179 
  3179 
  3219               (*_node_data)[ni].heap.push(e, rw);
  3219               (*_node_data)[ni].heap.push(e, rw);
  3220               (*_node_data)[ni].heap_index.insert(std::make_pair(vt, e));
  3220               (*_node_data)[ni].heap_index.insert(std::make_pair(vt, e));
  3221             }
  3221             }
  3222           }
  3222           }
  3223         }
  3223         }
  3224             
  3224 
  3225         if (!(*_node_data)[ni].heap.empty()) {
  3225         if (!(*_node_data)[ni].heap.empty()) {
  3226           _blossom_set->decrease(n, (*_node_data)[ni].heap.prio());
  3226           _blossom_set->decrease(n, (*_node_data)[ni].heap.prio());
  3227           _delta2->push(nb, _blossom_set->classPrio(nb));
  3227           _delta2->push(nb, _blossom_set->classPrio(nb));
  3228         }
  3228         }
  3229       }
  3229       }