1.1 --- a/lemon/bin_heap.h Fri Apr 14 15:05:51 2006 +0000
1.2 +++ b/lemon/bin_heap.h Fri Apr 14 18:05:02 2006 +0000
1.3 @@ -112,11 +112,11 @@
1.4
1.5 /// \brief Make empty this heap.
1.6 ///
1.7 - /// Make empty this heap.
1.8 + /// Make empty this heap. It does not change the cross reference map.
1.9 + /// If you want to reuse what is not surely empty you should first clear
1.10 + /// the heap and after that you should set the cross reference map for
1.11 + /// each item to \c PRE_HEAP.
1.12 void clear() {
1.13 - for (int i = 0; i < (int)data.size(); ++i) {
1.14 - iim.set(data[i].first, POST_HEAP);
1.15 - }
1.16 data.clear();
1.17 }
1.18
2.1 --- a/lemon/bucket_heap.h Fri Apr 14 15:05:51 2006 +0000
2.2 +++ b/lemon/bucket_heap.h Fri Apr 14 18:05:02 2006 +0000
2.3 @@ -90,11 +90,11 @@
2.4
2.5 /// \brief Make empty this heap.
2.6 ///
2.7 - /// Make empty this heap.
2.8 + /// Make empty this heap. It does not change the cross reference
2.9 + /// map. If you want to reuse a heap what is not surely empty you
2.10 + /// should first clear the heap and after that you should set the
2.11 + /// cross reference map for each item to \c PRE_HEAP.
2.12 void clear() {
2.13 - for (int i = 0; i < (int)data.size(); ++i) {
2.14 - index[data[i].item] = -2;
2.15 - }
2.16 data.clear(); first.clear(); minimal = 0;
2.17 }
2.18
2.19 @@ -349,9 +349,6 @@
2.20 bool empty() const { return data.empty(); }
2.21
2.22 void clear() {
2.23 - for (int i = 0; i < (int)data.size(); ++i) {
2.24 - index[data[i].item] = -2;
2.25 - }
2.26 data.clear(); first.clear(); maximal = -1;
2.27 }
2.28
3.1 --- a/lemon/fib_heap.h Fri Apr 14 15:05:51 2006 +0000
3.2 +++ b/lemon/fib_heap.h Fri Apr 14 18:05:02 2006 +0000
3.3 @@ -116,13 +116,11 @@
3.4
3.5 /// \brief Make empty this heap.
3.6 ///
3.7 - /// Make empty this heap.
3.8 + /// Make empty this heap. It does not change the cross reference
3.9 + /// map. If you want to reuse a heap what is not surely empty you
3.10 + /// should first clear the heap and after that you should set the
3.11 + /// cross reference map for each item to \c PRE_HEAP.
3.12 void clear() {
3.13 - if (num_items != 0) {
3.14 - for (int i = 0; i < (int)container.size(); ++i) {
3.15 - iimap[container[i].name] = -2;
3.16 - }
3.17 - }
3.18 container.clear(); minimum = 0; num_items = 0;
3.19 }
3.20
4.1 --- a/lemon/fredman_tarjan.h Fri Apr 14 15:05:51 2006 +0000
4.2 +++ b/lemon/fredman_tarjan.h Fri Apr 14 18:05:02 2006 +0000
4.3 @@ -211,9 +211,12 @@
4.4
4.5 private:
4.6
4.7 - template<class SrcGraph,class OrigMap,class Heap,class ProcessedMap,class PredMap>
4.8 - void processNextTree(const SrcGraph& graph,const OrigMap& orig,Heap &heap,
4.9 - ProcessedMap& processed,PredMap& pred,int& tree_counter,const int limit){
4.10 + template<class SrcGraph,class OrigMap,class Heap,class HeapCrossRef,
4.11 + class ProcessedMap,class PredMap>
4.12 + void processNextTree(const SrcGraph& graph,const OrigMap& orig,
4.13 + Heap &heap, HeapCrossRef& crossref,
4.14 + ProcessedMap& processed,PredMap& pred,
4.15 + int& tree_counter,const int limit){
4.16 std::vector<typename SrcGraph::Node> tree_nodes;
4.17 int tree_index=tree_counter;
4.18 bool stop=false;
4.19 @@ -254,21 +257,23 @@
4.20 for(int i=1;i<(int)tree_nodes.size();++i){
4.21 _tree->set(orig[pred[tree_nodes[i]]],true);
4.22 processed.set(tree_nodes[i],tree_index);
4.23 - heap.state(tree_nodes[i], Heap::PRE_HEAP);
4.24 + crossref[tree_nodes[i]] = Heap::PRE_HEAP;
4.25 }
4.26 processed.set(tree_nodes[0],tree_index);
4.27 - heap.state(tree_nodes[0],Heap::PRE_HEAP);
4.28 + crossref[tree_nodes[0]] = Heap::PRE_HEAP;
4.29 while (!heap.empty()) {
4.30 typename SrcGraph::Node v=heap.top();
4.31 heap.pop();
4.32 - heap.state(v,Heap::PRE_HEAP);
4.33 + crossref[v] = Heap::PRE_HEAP;
4.34 }
4.35 + heap.clear();
4.36 if(!stop)++tree_counter;
4.37 }
4.38
4.39 template<class SrcGraph,class OrigMap,class ProcessedMap>
4.40 - void createTrees(const SrcGraph& graph,const OrigMap& orig, ProcessedMap& processed,
4.41 - int edgenum,int& tree_counter){
4.42 + void createTrees(const SrcGraph& graph, const OrigMap& orig,
4.43 + ProcessedMap& processed,
4.44 + int edgenum,int& tree_counter){
4.45 typedef typename SrcGraph::Node Node;
4.46 typedef typename SrcGraph::UEdge UEdge;
4.47 typedef typename SrcGraph::NodeIt NodeIt;
4.48 @@ -278,18 +283,22 @@
4.49 FibHeap<Node,Value,HeapCrossRef> heap(crossref);
4.50 PredMap pred(graph,INVALID);
4.51 int rate=2*edgenum/countNodes(graph);
4.52 - int limit=(rate>std::numeric_limits<int>::digits)?std::numeric_limits<int>::max():(1<<rate);
4.53 + int limit=(rate>std::numeric_limits<int>::digits)?
4.54 + std::numeric_limits<int>::max() : (1<<rate);
4.55 for(NodeIt i(graph);i!=INVALID;++i){
4.56 if(processed[i]==-1){
4.57 heap.push(i, Value());
4.58 - processNextTree(graph,orig,heap,processed,pred,tree_counter,limit);
4.59 + processNextTree(graph,orig,heap,crossref,
4.60 + processed,pred,tree_counter,limit);
4.61 }
4.62 }
4.63 }
4.64
4.65 - template<class SrcGraph,class DestGraph,class SrcOrigMap,class DestOrigMap,class ProcessedMap>
4.66 - void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,DestGraph& destgraph,
4.67 - DestOrigMap& destorig,const ProcessedMap& processed,const int tree_counter){
4.68 + template<class SrcGraph,class DestGraph,class SrcOrigMap,
4.69 + class DestOrigMap,class ProcessedMap>
4.70 + void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,
4.71 + DestGraph& destgraph,DestOrigMap& destorig,
4.72 + const ProcessedMap& processed,const int tree_counter){
4.73 typedef typename SrcGraph::Node Node;
4.74 typedef typename DestGraph::Node DNode;
4.75 typedef typename SrcGraph::UEdge UEdge;
4.76 @@ -310,14 +319,17 @@
4.77 }
4.78 }
4.79
4.80 - radixSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,sourceMap(srcgraph))));
4.81 - counterSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,targetMap(srcgraph))));
4.82 + radixSort(edges.begin(),edges.end(),
4.83 + mapFunctor(composeMap(processed,sourceMap(srcgraph))));
4.84 + counterSort(edges.begin(),edges.end(),
4.85 + mapFunctor(composeMap(processed,targetMap(srcgraph))));
4.86 for(int i=0;i!=(int)edges.size();++i){
4.87 int srcproc=processed[srcgraph.source(edges[i])];
4.88 int trgproc=processed[srcgraph.target(edges[i])];
4.89 Value minval=(*cost)[srcorig[edges[i]]];
4.90 UEdge minpos=edges[i];
4.91 - while (i+1!=(int)edges.size() && srcproc==processed[srcgraph.source(edges[i+1])] &&
4.92 + while (i+1!=(int)edges.size() &&
4.93 + srcproc==processed[srcgraph.source(edges[i+1])] &&
4.94 trgproc==processed[srcgraph.target(edges[i+1])]) {
4.95 if (minval>(*cost)[srcorig[edges[i+1]]]) {
4.96 minval=(*cost)[srcorig[edges[i+1]]];
4.97 @@ -325,7 +337,8 @@
4.98 }
4.99 ++i;
4.100 }
4.101 - destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=srcorig[minpos];
4.102 + destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=
4.103 + srcorig[minpos];
4.104 }
4.105 }
4.106
5.1 --- a/lemon/radix_heap.h Fri Apr 14 15:05:51 2006 +0000
5.2 +++ b/lemon/radix_heap.h Fri Apr 14 18:05:02 2006 +0000
5.3 @@ -136,11 +136,11 @@
5.4
5.5 /// \brief Make empty this heap.
5.6 ///
5.7 - /// Make empty this heap.
5.8 + /// Make empty this heap. It does not change the cross reference
5.9 + /// map. If you want to reuse a heap what is not surely empty you
5.10 + /// should first clear the heap and after that you should set the
5.11 + /// cross reference map for each item to \c PRE_HEAP.
5.12 void clear(int minimal = 0, int capacity = 0) {
5.13 - for (int i = 0; i < (int)data.size(); ++i) {
5.14 - iim[data[i].item] = -2;
5.15 - }
5.16 data.clear(); boxes.clear();
5.17 boxes.push_back(RadixBox(minimal, 1));
5.18 boxes.push_back(RadixBox(minimal + 1, 1));