COIN-OR::LEMON - Graph Library

Changeset 2624:dc4dd5fc0e25 in lemon-0.x


Ignore:
Timestamp:
10/08/08 11:17:01 (15 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3509
Message:

Bug fixes is HaoOrlin? and MinCostArborescence?

MinCostArborescence?

  • proper deallocation

HaoOrlin?

  • the target needn't to be the last in its bucket
  • proper size of container (if each node starts in different buckets initially)
Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/hao_orlin.h

    r2553 r2624  
    2222#include <vector>
    2323#include <list>
    24 #include <ext/hash_set>
    2524#include <limits>
    2625
    2726#include <lemon/maps.h>
    2827#include <lemon/graph_utils.h>
    29 #include <lemon/graph_adaptor.h>
    30 #include <lemon/iterable_maps.h>
     28#include <lemon/tolerance.h>
    3129
    3230/// \file
     
    294292            _excess->set(u, (*_excess)[u] + (*_capacity)[e]);
    295293            if (!(*_active)[u] && u != _source) {
    296               activate(u);
    297             }
    298           }
    299         }
     294              activate(u);           
     295            }
     296          }
     297        }
     298
    300299        if ((*_active)[target]) {
    301300          deactivate(target);
     
    308307        }
    309308      }
    310 
    311309
    312310      while (true) {
     
    463461        {
    464462          Node new_target;
    465           if ((*_prev)[target] != INVALID) {
    466             _last[(*_bucket)[target]] = (*_prev)[target];
    467             _next->set((*_prev)[target], INVALID);
    468             new_target = (*_prev)[target];
     463          if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) {
     464            if ((*_next)[target] == INVALID) {
     465              _last[(*_bucket)[target]] = (*_prev)[target];
     466              new_target = (*_prev)[target];
     467            } else {
     468              _prev->set((*_next)[target], (*_prev)[target]);
     469              new_target = (*_next)[target];
     470            }
     471            if ((*_prev)[target] == INVALID) {
     472              _first[(*_bucket)[target]] = (*_next)[target];
     473            } else {
     474              _next->set((*_prev)[target], (*_next)[target]);
     475            }
    469476          } else {
    470477            _sets.back().pop_back();
     
    762769        {
    763770          Node new_target;
    764           if ((*_prev)[target] != INVALID) {
    765             _last[(*_bucket)[target]] = (*_prev)[target];
    766             _next->set((*_prev)[target], INVALID);
    767             new_target = (*_prev)[target];
     771          if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) {
     772            if ((*_next)[target] == INVALID) {
     773              _last[(*_bucket)[target]] = (*_prev)[target];
     774              new_target = (*_prev)[target];
     775            } else {
     776              _prev->set((*_next)[target], (*_prev)[target]);
     777              new_target = (*_next)[target];
     778            }
     779            if ((*_prev)[target] == INVALID) {
     780              _first[(*_bucket)[target]] = (*_next)[target];
     781            } else {
     782              _next->set((*_prev)[target], (*_next)[target]);
     783            }
    768784          } else {
    769785            _sets.back().pop_back();
     
    851867      _node_num = countNodes(_graph);
    852868     
    853       _first.resize(_node_num);
    854       _last.resize(_node_num);
    855 
    856       _dormant.resize(_node_num);
     869      _first.resize(_node_num + 1);
     870      _last.resize(_node_num + 1);
     871
     872      _dormant.resize(_node_num + 1);
    857873
    858874      if (!_flow) {
  • lemon/min_cost_arborescence.h

    r2553 r2624  
    644644        delete _pred;
    645645      }
    646       if (!_edge_order) {
     646      if (_edge_order) {
    647647        delete _edge_order;
    648648      }
     
    650650        delete _node_order;
    651651      }
    652       if (!_cost_edges) {
     652      if (_cost_edges) {
    653653        delete _cost_edges;
    654654      }
    655       if (!_heap) {
     655      if (_heap) {
    656656        delete _heap;
    657657      }
    658       if (!_heap_cross_ref) {
     658      if (_heap_cross_ref) {
    659659        delete _heap_cross_ref;
    660660      }
Note: See TracChangeset for help on using the changeset viewer.