1.1 --- a/lemon/fredman_tarjan.h	Fri Apr 14 15:05:51 2006 +0000
     1.2 +++ b/lemon/fredman_tarjan.h	Fri Apr 14 18:05:02 2006 +0000
     1.3 @@ -211,9 +211,12 @@
     1.4  
     1.5    private:
     1.6  
     1.7 -    template<class SrcGraph,class OrigMap,class Heap,class ProcessedMap,class PredMap>
     1.8 -    void processNextTree(const SrcGraph& graph,const OrigMap& orig,Heap &heap,
     1.9 -	ProcessedMap& processed,PredMap& pred,int& tree_counter,const int limit){
    1.10 +    template<class SrcGraph,class OrigMap,class Heap,class HeapCrossRef,
    1.11 +             class ProcessedMap,class PredMap>
    1.12 +    void processNextTree(const SrcGraph& graph,const OrigMap& orig,
    1.13 +                         Heap &heap, HeapCrossRef& crossref,
    1.14 +                         ProcessedMap& processed,PredMap& pred,
    1.15 +                         int& tree_counter,const int limit){
    1.16        std::vector<typename SrcGraph::Node> tree_nodes;
    1.17        int tree_index=tree_counter;
    1.18        bool stop=false;
    1.19 @@ -254,21 +257,23 @@
    1.20        for(int i=1;i<(int)tree_nodes.size();++i){
    1.21  	_tree->set(orig[pred[tree_nodes[i]]],true);
    1.22          processed.set(tree_nodes[i],tree_index);
    1.23 -        heap.state(tree_nodes[i], Heap::PRE_HEAP);
    1.24 +        crossref[tree_nodes[i]] = Heap::PRE_HEAP;
    1.25        }
    1.26        processed.set(tree_nodes[0],tree_index);
    1.27 -      heap.state(tree_nodes[0],Heap::PRE_HEAP);
    1.28 +      crossref[tree_nodes[0]] = Heap::PRE_HEAP;
    1.29        while (!heap.empty()) {
    1.30          typename SrcGraph::Node v=heap.top();
    1.31  	heap.pop();
    1.32 -        heap.state(v,Heap::PRE_HEAP);
    1.33 +        crossref[v] = Heap::PRE_HEAP;
    1.34        }
    1.35 +      heap.clear();
    1.36        if(!stop)++tree_counter;
    1.37      }
    1.38  
    1.39      template<class SrcGraph,class OrigMap,class ProcessedMap>
    1.40 -    void createTrees(const SrcGraph& graph,const OrigMap& orig, ProcessedMap& processed,
    1.41 -	int edgenum,int& tree_counter){
    1.42 +    void createTrees(const SrcGraph& graph, const OrigMap& orig, 
    1.43 +                     ProcessedMap& processed,
    1.44 +                     int edgenum,int& tree_counter){
    1.45        typedef typename SrcGraph::Node Node;
    1.46        typedef typename SrcGraph::UEdge UEdge;
    1.47        typedef typename SrcGraph::NodeIt NodeIt;
    1.48 @@ -278,18 +283,22 @@
    1.49        FibHeap<Node,Value,HeapCrossRef> heap(crossref);
    1.50        PredMap pred(graph,INVALID);
    1.51        int rate=2*edgenum/countNodes(graph);
    1.52 -      int limit=(rate>std::numeric_limits<int>::digits)?std::numeric_limits<int>::max():(1<<rate);
    1.53 +      int limit=(rate>std::numeric_limits<int>::digits)?
    1.54 +      std::numeric_limits<int>::max() : (1<<rate);
    1.55        for(NodeIt i(graph);i!=INVALID;++i){
    1.56  	if(processed[i]==-1){
    1.57  	  heap.push(i, Value());
    1.58 -	  processNextTree(graph,orig,heap,processed,pred,tree_counter,limit);
    1.59 +	  processNextTree(graph,orig,heap,crossref,
    1.60 +                          processed,pred,tree_counter,limit);
    1.61  	}
    1.62        }
    1.63      }
    1.64  
    1.65 -    template<class SrcGraph,class DestGraph,class SrcOrigMap,class DestOrigMap,class ProcessedMap>
    1.66 -    void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,DestGraph& destgraph,
    1.67 -	DestOrigMap& destorig,const ProcessedMap& processed,const int tree_counter){
    1.68 +    template<class SrcGraph,class DestGraph,class SrcOrigMap,
    1.69 +             class DestOrigMap,class ProcessedMap>
    1.70 +    void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,
    1.71 +                 DestGraph& destgraph,DestOrigMap& destorig,
    1.72 +                 const ProcessedMap& processed,const int tree_counter){
    1.73        typedef typename SrcGraph::Node Node;
    1.74        typedef typename DestGraph::Node DNode;
    1.75        typedef typename SrcGraph::UEdge UEdge;
    1.76 @@ -310,14 +319,17 @@
    1.77  	}
    1.78        }
    1.79        
    1.80 -      radixSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,sourceMap(srcgraph))));
    1.81 -      counterSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,targetMap(srcgraph))));
    1.82 +      radixSort(edges.begin(),edges.end(),
    1.83 +                mapFunctor(composeMap(processed,sourceMap(srcgraph))));
    1.84 +      counterSort(edges.begin(),edges.end(),
    1.85 +                  mapFunctor(composeMap(processed,targetMap(srcgraph))));
    1.86        for(int i=0;i!=(int)edges.size();++i){
    1.87  	int srcproc=processed[srcgraph.source(edges[i])];
    1.88  	int trgproc=processed[srcgraph.target(edges[i])];
    1.89          Value minval=(*cost)[srcorig[edges[i]]];
    1.90          UEdge minpos=edges[i];
    1.91 -	while (i+1!=(int)edges.size() && srcproc==processed[srcgraph.source(edges[i+1])] &&
    1.92 +	while (i+1!=(int)edges.size() && 
    1.93 +               srcproc==processed[srcgraph.source(edges[i+1])] &&
    1.94  	  trgproc==processed[srcgraph.target(edges[i+1])]) {
    1.95  	  if (minval>(*cost)[srcorig[edges[i+1]]]) {
    1.96              minval=(*cost)[srcorig[edges[i+1]]];
    1.97 @@ -325,7 +337,8 @@
    1.98  	  }
    1.99            ++i;
   1.100  	} 
   1.101 -	destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=srcorig[minpos];
   1.102 +	destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=
   1.103 +          srcorig[minpos];
   1.104        }
   1.105      }
   1.106