/* -*- mode: C++; indent-tabs-mode: nil; -*-

 /* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  *

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  *

  * Permission to use, modify and distribute this software is granted

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * provided that this copyright notice appears in all copies. For

       }

       }

       for (int i = 0; i < _blossom_num; ++i) {

       for (int i = 0; i < _blossom_num; ++i) {

         (*_delta2_index)[i] = _delta2->PRE_HEAP;

         (*_delta2_index)[i] = _delta2->PRE_HEAP;

         (*_delta4_index)[i] = _delta4->PRE_HEAP;

         (*_delta4_index)[i] = _delta4->PRE_HEAP;

       }

       }

       _unmatched = _node_num;

       _unmatched = _node_num;

       _delta1->clear();

       _delta1->clear();

       _delta2->clear();

       _delta2->clear();

       _delta3->clear();

       _delta3->clear();

     void fractionalInit() {

     void fractionalInit() {

       createStructures();

       createStructures();

       _blossom_node_list.clear();

       _blossom_node_list.clear();

       _blossom_potential.clear();

       _blossom_potential.clear();

       if (_fractional == 0) {

       if (_fractional == 0) {

         _fractional = new FractionalMatching(_graph, _weight, false);

         _fractional = new FractionalMatching(_graph, _weight, false);

       }

       }

       _fractional->run();

       _fractional->run();

           _delta1->push(n, _fractional->nodeValue(n));

           _delta1->push(n, _fractional->nodeValue(n));

           v = _graph.target(_fractional->matching(n));

           v = _graph.target(_fractional->matching(n));

           while (n != v) {

           while (n != v) {

             subblossoms[--num] = _blossom_set->find(v);

             subblossoms[--num] = _blossom_set->find(v);

             _delta1->push(v, _fractional->nodeValue(v));

             _delta1->push(v, _fractional->nodeValue(v));

           }

           }

             _blossom_set->join(subblossoms.begin(), subblossoms.end());

             _blossom_set->join(subblossoms.begin(), subblossoms.end());

           (*_blossom_data)[surface].status = EVEN;

           (*_blossom_data)[surface].status = EVEN;

           (*_blossom_data)[surface].pred = INVALID;

           (*_blossom_data)[surface].pred = INVALID;

           (*_blossom_data)[surface].next = INVALID;

           (*_blossom_data)[surface].next = INVALID;

           (*_blossom_data)[surface].pot = 0;

           (*_blossom_data)[surface].pot = 0;

           (*_blossom_data)[surface].offset = 0;

           (*_blossom_data)[surface].offset = 0;

           _tree_set->insert(surface);

           _tree_set->insert(surface);

           ++_unmatched;

           ++_unmatched;

         }

         }

       }

       }

               (*_node_data)[ni].heap.push(e, rw);

               (*_node_data)[ni].heap.push(e, rw);

               (*_node_data)[ni].heap_index.insert(std::make_pair(vt, e));

               (*_node_data)[ni].heap_index.insert(std::make_pair(vt, e));

             }

             }

           }

           }

         }

         }

         if (!(*_node_data)[ni].heap.empty()) {

         if (!(*_node_data)[ni].heap.empty()) {

           _blossom_set->decrease(n, (*_node_data)[ni].heap.prio());

           _blossom_set->decrease(n, (*_node_data)[ni].heap.prio());

           _delta2->push(nb, _blossom_set->classPrio(nb));

           _delta2->push(nb, _blossom_set->classPrio(nb));

         }

         }

       }

       }

     BinHeap<Value, IntIntMap> *_delta4;

     BinHeap<Value, IntIntMap> *_delta4;

     Value _delta_sum;

     Value _delta_sum;

     int _unmatched;

     int _unmatched;

     FractionalMatching;

     FractionalMatching;

     FractionalMatching *_fractional;

     FractionalMatching *_fractional;

     void createStructures() {

     void createStructures() {

       _node_num = countNodes(_graph);

       _node_num = countNodes(_graph);

     void fractionalInit() {

     void fractionalInit() {

       createStructures();

       createStructures();

       _blossom_node_list.clear();

       _blossom_node_list.clear();

       _blossom_potential.clear();

       _blossom_potential.clear();

       if (_fractional == 0) {

       if (_fractional == 0) {

         _fractional = new FractionalMatching(_graph, _weight, false);

         _fractional = new FractionalMatching(_graph, _weight, false);

       }

       }

       if (!_fractional->run()) {

       if (!_fractional->run()) {

         _unmatched = -1;

         _unmatched = -1;

           subblossoms[--num] = _blossom_set->find(n);

           subblossoms[--num] = _blossom_set->find(n);

           v = _graph.target(_fractional->matching(n));

           v = _graph.target(_fractional->matching(n));

           while (n != v) {

           while (n != v) {

             subblossoms[--num] = _blossom_set->find(v);

             subblossoms[--num] = _blossom_set->find(v);

           }

           }

             _blossom_set->join(subblossoms.begin(), subblossoms.end());

             _blossom_set->join(subblossoms.begin(), subblossoms.end());

           (*_blossom_data)[surface].status = EVEN;

           (*_blossom_data)[surface].status = EVEN;

           (*_blossom_data)[surface].pred = INVALID;

           (*_blossom_data)[surface].pred = INVALID;

           (*_blossom_data)[surface].next = INVALID;

           (*_blossom_data)[surface].next = INVALID;

           (*_blossom_data)[surface].pot = 0;

           (*_blossom_data)[surface].pot = 0;

           (*_blossom_data)[surface].offset = 0;

           (*_blossom_data)[surface].offset = 0;

           _tree_set->insert(surface);

           _tree_set->insert(surface);

           ++_unmatched;

           ++_unmatched;

         }

         }

       }

       }

               (*_node_data)[ni].heap.push(e, rw);

               (*_node_data)[ni].heap.push(e, rw);

               (*_node_data)[ni].heap_index.insert(std::make_pair(vt, e));

               (*_node_data)[ni].heap_index.insert(std::make_pair(vt, e));

             }

             }

           }

           }

         }

         }

         if (!(*_node_data)[ni].heap.empty()) {

         if (!(*_node_data)[ni].heap.empty()) {

           _blossom_set->decrease(n, (*_node_data)[ni].heap.prio());

           _blossom_set->decrease(n, (*_node_data)[ni].heap.prio());

           _delta2->push(nb, _blossom_set->classPrio(nb));

           _delta2->push(nb, _blossom_set->classPrio(nb));

         }

         }

       }

       }