COIN-OR::LEMON - Graph Library

Changeset 754:3887d6f994d7 in lemon


Ignore:
Timestamp:
07/24/09 01:07:45 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
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.