COIN-OR::LEMON - Graph Library

Changeset 754:3887d6f994d7 in lemon


Ignore:
Timestamp:
07/24/09 01:07:45 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Much faster implementation for BinomHeap? (#301)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/binom_heap.h

    r750 r754  
    8080
    8181  private:
    82     class store;
    83 
    84     std::vector<store> _data;
     82    class Store;
     83
     84    std::vector<Store> _data;
    8585    int _min, _head;
    8686    ItemIntMap &_iim;
     
    157157        int s=_data.size();
    158158        _iim.set( item,s );
    159         store st;
     159        Store st;
    160160        st.name=item;
     161        st.prio=value;
    161162        _data.push_back(st);
    162163        i=s;
     
    166167        _data[i].degree=0;
    167168        _data[i].in=true;
    168       }
    169       _data[i].prio=value;
    170 
    171       if( 0==_num_items ) { _head=i; _min=i; }
    172       else { merge(i); }
    173 
    174       _min = findMin();
    175 
     169        _data[i].prio=value;
     170      }
     171
     172      if( 0==_num_items ) {
     173        _head=i;
     174        _min=i;
     175      } else {
     176        merge(i);
     177        if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
     178      }
    176179      ++_num_items;
    177180    }
     
    209212        int child=_data[_min].child;
    210213        int neighb;
    211         int prev=-1;
    212214        while( child!=-1 ) {
    213215          neighb=_data[child].right_neighbor;
    214216          _data[child].parent=-1;
    215           _data[child].right_neighbor=prev;
     217          _data[child].right_neighbor=head_child;
    216218          head_child=child;
    217           prev=child;
    218219          child=neighb;
    219220        }
    220221      }
    221222
    222       // The first case is that there are only one root.
    223       if ( -1==_data[_head].right_neighbor ) {
     223      if ( _data[_head].right_neighbor==-1 ) {
     224        // there was only one root
    224225        _head=head_child;
    225226      }
    226       // The case where there are more roots.
    227227      else {
     228        // there were more roots
    228229        if( _head!=_min )  { unlace(_min); }
    229230        else { _head=_data[_head].right_neighbor; }
    230 
    231231        merge(head_child);
    232232      }
     
    257257    void decrease (Item item, const Prio& value) {
    258258      int i=_iim[item];
    259 
    260       if( _comp( value,_data[i].prio ) ) {
    261         _data[i].prio=value;
    262 
    263         int p_loc=_data[i].parent, loc=i;
    264         int parent, child, neighb;
    265 
    266         while( -1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) {
    267 
    268           // parent set for other loc_child
    269           child=_data[loc].child;
    270           while( -1!=child ) {
    271             _data[child].parent=p_loc;
    272             child=_data[child].right_neighbor;
    273           }
    274 
    275           // parent set for other p_loc_child
    276           child=_data[p_loc].child;
    277           while( -1!=child ) {
    278             _data[child].parent=loc;
    279             child=_data[child].right_neighbor;
    280           }
    281 
    282           child=_data[p_loc].child;
    283           _data[p_loc].child=_data[loc].child;
    284           if( child==loc )
    285             child=p_loc;
    286           _data[loc].child=child;
    287 
    288           // left_neighb set for p_loc
    289           if( _data[loc].child!=p_loc ) {
    290             while( _data[child].right_neighbor!=loc )
    291               child=_data[child].right_neighbor;
    292             _data[child].right_neighbor=p_loc;
    293           }
    294 
    295           // left_neighb set for loc
    296           parent=_data[p_loc].parent;
    297           if( -1!=parent ) child=_data[parent].child;
    298           else child=_head;
    299 
    300           if( child!=p_loc ) {
    301             while( _data[child].right_neighbor!=p_loc )
    302               child=_data[child].right_neighbor;
    303             _data[child].right_neighbor=loc;
    304           }
    305 
    306           neighb=_data[p_loc].right_neighbor;
    307           _data[p_loc].right_neighbor=_data[loc].right_neighbor;
    308           _data[loc].right_neighbor=neighb;
    309 
    310           _data[p_loc].parent=loc;
    311           _data[loc].parent=parent;
    312 
    313           if( -1!=parent && _data[parent].child==p_loc )
    314             _data[parent].child=loc;
    315 
    316           /*if new parent will be the first root*/
    317           if( _head==p_loc )
    318             _head=loc;
    319 
    320           p_loc=_data[loc].parent;
    321         }
    322       }
    323       if( _comp(value,_data[_min].prio) ) {
    324         _min=i;
    325       }
     259      int p=_data[i].parent;
     260      _data[i].prio=value;
     261     
     262      while( p!=-1 && _comp(value, _data[p].prio) ) {
     263        _data[i].name=_data[p].name;
     264        _data[i].prio=_data[p].prio;
     265        _data[p].name=item;
     266        _data[p].prio=value;
     267        _iim[_data[i].name]=i;
     268        i=p;
     269        p=_data[p].parent;
     270      }
     271      _iim[item]=i;
     272      if ( _comp(value, _data[_min].prio) ) _min=i;
    326273    }
    327274
     
    376323
    377324  private:
     325   
     326    // Find the minimum of the roots
    378327    int findMin() {
    379       int min_loc=-1, min_val;
    380       int x=_head;
    381       if( x!=-1 ) {
    382         min_val=_data[x].prio;
    383         min_loc=x;
    384         x=_data[x].right_neighbor;
    385 
    386         while( x!=-1 ) {
     328      if( _head!=-1 ) {
     329        int min_loc=_head, min_val=_data[_head].prio;
     330        for( int x=_data[_head].right_neighbor; x!=-1;
     331             x=_data[x].right_neighbor ) {
    387332          if( _comp( _data[x].prio,min_val ) ) {
    388333            min_val=_data[x].prio;
    389334            min_loc=x;
    390335          }
    391           x=_data[x].right_neighbor;
    392         }
    393       }
    394       return min_loc;
    395     }
    396 
     336        }
     337        return min_loc;
     338      }
     339      else return -1;
     340    }
     341
     342    // Merge the heap with another heap starting at the given position
    397343    void merge(int a) {
    398       interleave(a);
    399 
     344      if( _head==-1 || a==-1 ) return;
     345      if( _data[a].right_neighbor==-1 &&
     346          _data[a].degree<=_data[_head].degree ) {
     347        _data[a].right_neighbor=_head;
     348        _head=a;
     349      } else {
     350        interleave(a);
     351      }
     352      if( _data[_head].right_neighbor==-1 ) return;
     353     
    400354      int x=_head;
    401       if( -1!=x ) {
    402         int x_prev=-1, x_next=_data[x].right_neighbor;
    403         while( -1!=x_next ) {
    404           if( _data[x].degree!=_data[x_next].degree || ( -1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
    405             x_prev=x;
     355      int x_prev=-1, x_next=_data[x].right_neighbor;
     356      while( x_next!=-1 ) {
     357        if( _data[x].degree!=_data[x_next].degree ||
     358            ( _data[x_next].right_neighbor!=-1 &&
     359              _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
     360          x_prev=x;
     361          x=x_next;
     362        }
     363        else {
     364          if( _comp(_data[x_next].prio,_data[x].prio) ) {
     365            if( x_prev==-1 ) {
     366              _head=x_next;
     367            } else {
     368              _data[x_prev].right_neighbor=x_next;
     369            }
     370            fuse(x,x_next);
    406371            x=x_next;
    407372          }
    408373          else {
    409             if( _comp(_data[x].prio,_data[x_next].prio) ) {
    410               _data[x].right_neighbor=_data[x_next].right_neighbor;
    411               fuse(x_next,x);
    412             }
    413             else {
    414               if( -1==x_prev ) { _head=x_next; }
    415               else {
    416                 _data[x_prev].right_neighbor=x_next;
    417               }
    418               fuse(x,x_next);
    419               x=x_next;
    420             }
     374            _data[x].right_neighbor=_data[x_next].right_neighbor;
     375            fuse(x_next,x);
    421376          }
    422           x_next=_data[x].right_neighbor;
    423         }
    424       }
    425     }
    426 
     377        }
     378        x_next=_data[x].right_neighbor;
     379      }
     380    }
     381
     382    // Interleave the elements of the given list into the list of the roots
    427383    void interleave(int a) {
    428       int other=-1, head_other=-1;
    429 
    430       while( -1!=a || -1!=_head ) {
    431         if( -1==a ) {
    432           if( -1==head_other ) {
    433             head_other=_head;
    434           }
    435           else {
    436             _data[other].right_neighbor=_head;
    437           }
    438           _head=-1;
    439         }
    440         else if( -1==_head ) {
    441           if( -1==head_other ) {
    442             head_other=a;
    443           }
    444           else {
    445             _data[other].right_neighbor=a;
    446           }
    447           a=-1;
     384      int p=_head, q=a;
     385      int curr=_data.size();
     386      _data.push_back(Store());
     387     
     388      while( p!=-1 || q!=-1 ) {
     389        if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
     390          _data[curr].right_neighbor=p;
     391          curr=p;
     392          p=_data[p].right_neighbor;
    448393        }
    449394        else {
    450           if( _data[a].degree<_data[_head].degree ) {
    451             if( -1==head_other ) {
    452               head_other=a;
    453             }
    454             else {
    455               _data[other].right_neighbor=a;
    456             }
    457             other=a;
    458             a=_data[a].right_neighbor;
    459           }
    460           else {
    461             if( -1==head_other ) {
    462               head_other=_head;
    463             }
    464             else {
    465               _data[other].right_neighbor=_head;
    466             }
    467             other=_head;
    468             _head=_data[_head].right_neighbor;
    469           }
    470         }
    471       }
    472       _head=head_other;
    473     }
    474 
    475     // Lacing a under b
     395          _data[curr].right_neighbor=q;
     396          curr=q;
     397          q=_data[q].right_neighbor;
     398        }
     399      }
     400     
     401      _head=_data.back().right_neighbor;
     402      _data.pop_back();
     403    }
     404
     405    // Lace node a under node b
    476406    void fuse(int a, int b) {
    477407      _data[a].parent=b;
     
    482412    }
    483413
    484     // It is invoked only if a has siblings.
     414    // Unlace node a (if it has siblings)
    485415    void unlace(int a) {
    486416      int neighb=_data[a].right_neighbor;
     
    494424  private:
    495425
    496     class store {
     426    class Store {
    497427      friend class BinomHeap;
    498428
     
    505435      Prio prio;
    506436
    507       store() : parent(-1), right_neighbor(-1), child(-1), degree(0), in(true) {}
     437      Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
     438        in(true) {}
    508439    };
    509440  };
Note: See TracChangeset for help on using the changeset viewer.