COIN-OR::LEMON - Graph Library

Changeset 2050:d9a221218ea4 in lemon-0.x


Ignore:
Timestamp:
04/14/06 20:05:02 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2693
Message:

Changing the mining of the clear in heaps
It does not touch the heap cross ref. It is
sometimes more clean useable and more efficient

Location:
lemon
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • lemon/bin_heap.h

    r1956 r2050  
    113113    /// \brief Make empty this heap.
    114114    ///
    115     /// Make empty this heap.
     115    /// Make empty this heap. It does not change the cross reference map.
     116    /// If you want to reuse what is not surely empty you should first clear
     117    /// the heap and after that you should set the cross reference map for
     118    /// each item to \c PRE_HEAP.
    116119    void clear() {
    117       for (int i = 0; i < (int)data.size(); ++i) {
    118         iim.set(data[i].first, POST_HEAP);
    119       }
    120120      data.clear();
    121121    }
  • lemon/bucket_heap.h

    r2042 r2050  
    9191    /// \brief Make empty this heap.
    9292    ///
    93     /// Make empty this heap.
     93    /// Make empty this heap. It does not change the cross reference
     94    /// map.  If you want to reuse a heap what is not surely empty you
     95    /// should first clear the heap and after that you should set the
     96    /// cross reference map for each item to \c PRE_HEAP.
    9497    void clear() {
    95       for (int i = 0; i < (int)data.size(); ++i) {
    96         index[data[i].item] = -2;
    97       }
    9898      data.clear(); first.clear(); minimal = 0;
    9999    }
     
    350350
    351351    void clear() {
    352       for (int i = 0; i < (int)data.size(); ++i) {
    353         index[data[i].item] = -2;
    354       }
    355352      data.clear(); first.clear(); maximal = -1;
    356353    }
  • lemon/fib_heap.h

    r1956 r2050  
    117117    /// \brief Make empty this heap.
    118118    ///
    119     /// Make empty this heap.
     119    /// Make empty this heap. It does not change the cross reference
     120    /// map.  If you want to reuse a heap what is not surely empty you
     121    /// should first clear the heap and after that you should set the
     122    /// cross reference map for each item to \c PRE_HEAP.
    120123    void clear() {
    121       if (num_items != 0) {
    122         for (int i = 0; i < (int)container.size(); ++i) {
    123           iimap[container[i].name] = -2;
    124         }
    125       }
    126124      container.clear(); minimum = 0; num_items = 0;
    127125    }
  • lemon/fredman_tarjan.h

    r2042 r2050  
    212212  private:
    213213
    214     template<class SrcGraph,class OrigMap,class Heap,class ProcessedMap,class PredMap>
    215     void processNextTree(const SrcGraph& graph,const OrigMap& orig,Heap &heap,
    216         ProcessedMap& processed,PredMap& pred,int& tree_counter,const int limit){
     214    template<class SrcGraph,class OrigMap,class Heap,class HeapCrossRef,
     215             class ProcessedMap,class PredMap>
     216    void processNextTree(const SrcGraph& graph,const OrigMap& orig,
     217                         Heap &heap, HeapCrossRef& crossref,
     218                         ProcessedMap& processed,PredMap& pred,
     219                         int& tree_counter,const int limit){
    217220      std::vector<typename SrcGraph::Node> tree_nodes;
    218221      int tree_index=tree_counter;
     
    255258        _tree->set(orig[pred[tree_nodes[i]]],true);
    256259        processed.set(tree_nodes[i],tree_index);
    257         heap.state(tree_nodes[i], Heap::PRE_HEAP);
     260        crossref[tree_nodes[i]] = Heap::PRE_HEAP;
    258261      }
    259262      processed.set(tree_nodes[0],tree_index);
    260       heap.state(tree_nodes[0],Heap::PRE_HEAP);
     263      crossref[tree_nodes[0]] = Heap::PRE_HEAP;
    261264      while (!heap.empty()) {
    262265        typename SrcGraph::Node v=heap.top();
    263266        heap.pop();
    264         heap.state(v,Heap::PRE_HEAP);
    265       }
     267        crossref[v] = Heap::PRE_HEAP;
     268      }
     269      heap.clear();
    266270      if(!stop)++tree_counter;
    267271    }
    268272
    269273    template<class SrcGraph,class OrigMap,class ProcessedMap>
    270     void createTrees(const SrcGraph& graph,const OrigMap& orig, ProcessedMap& processed,
    271         int edgenum,int& tree_counter){
     274    void createTrees(const SrcGraph& graph, const OrigMap& orig,
     275                     ProcessedMap& processed,
     276                     int edgenum,int& tree_counter){
    272277      typedef typename SrcGraph::Node Node;
    273278      typedef typename SrcGraph::UEdge UEdge;
     
    279284      PredMap pred(graph,INVALID);
    280285      int rate=2*edgenum/countNodes(graph);
    281       int limit=(rate>std::numeric_limits<int>::digits)?std::numeric_limits<int>::max():(1<<rate);
     286      int limit=(rate>std::numeric_limits<int>::digits)?
     287      std::numeric_limits<int>::max() : (1<<rate);
    282288      for(NodeIt i(graph);i!=INVALID;++i){
    283289        if(processed[i]==-1){
    284290          heap.push(i, Value());
    285           processNextTree(graph,orig,heap,processed,pred,tree_counter,limit);
     291          processNextTree(graph,orig,heap,crossref,
     292                          processed,pred,tree_counter,limit);
    286293        }
    287294      }
    288295    }
    289296
    290     template<class SrcGraph,class DestGraph,class SrcOrigMap,class DestOrigMap,class ProcessedMap>
    291     void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,DestGraph& destgraph,
    292         DestOrigMap& destorig,const ProcessedMap& processed,const int tree_counter){
     297    template<class SrcGraph,class DestGraph,class SrcOrigMap,
     298             class DestOrigMap,class ProcessedMap>
     299    void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,
     300                 DestGraph& destgraph,DestOrigMap& destorig,
     301                 const ProcessedMap& processed,const int tree_counter){
    293302      typedef typename SrcGraph::Node Node;
    294303      typedef typename DestGraph::Node DNode;
     
    311320      }
    312321     
    313       radixSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,sourceMap(srcgraph))));
    314       counterSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,targetMap(srcgraph))));
     322      radixSort(edges.begin(),edges.end(),
     323                mapFunctor(composeMap(processed,sourceMap(srcgraph))));
     324      counterSort(edges.begin(),edges.end(),
     325                  mapFunctor(composeMap(processed,targetMap(srcgraph))));
    315326      for(int i=0;i!=(int)edges.size();++i){
    316327        int srcproc=processed[srcgraph.source(edges[i])];
     
    318329        Value minval=(*cost)[srcorig[edges[i]]];
    319330        UEdge minpos=edges[i];
    320         while (i+1!=(int)edges.size() && srcproc==processed[srcgraph.source(edges[i+1])] &&
     331        while (i+1!=(int)edges.size() &&
     332               srcproc==processed[srcgraph.source(edges[i+1])] &&
    321333          trgproc==processed[srcgraph.target(edges[i+1])]) {
    322334          if (minval>(*cost)[srcorig[edges[i+1]]]) {
     
    326338          ++i;
    327339        }
    328         destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=srcorig[minpos];
     340        destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=
     341          srcorig[minpos];
    329342      }
    330343    }
  • lemon/radix_heap.h

    r1956 r2050  
    137137    /// \brief Make empty this heap.
    138138    ///
    139     /// Make empty this heap.
     139    /// Make empty this heap. It does not change the cross reference
     140    /// map.  If you want to reuse a heap what is not surely empty you
     141    /// should first clear the heap and after that you should set the
     142    /// cross reference map for each item to \c PRE_HEAP.
    140143    void clear(int minimal = 0, int capacity = 0) {
    141       for (int i = 0; i < (int)data.size(); ++i) {
    142         iim[data[i].item] = -2;
    143       }
    144144      data.clear(); boxes.clear();
    145145      boxes.push_back(RadixBox(minimal, 1));
Note: See TracChangeset for help on using the changeset viewer.