209 |
209 |
210 FredmanTarjan() {} |
210 FredmanTarjan() {} |
211 |
211 |
212 private: |
212 private: |
213 |
213 |
214 template<class SrcGraph,class OrigMap,class Heap,class ProcessedMap,class PredMap> |
214 template<class SrcGraph,class OrigMap,class Heap,class HeapCrossRef, |
215 void processNextTree(const SrcGraph& graph,const OrigMap& orig,Heap &heap, |
215 class ProcessedMap,class PredMap> |
216 ProcessedMap& processed,PredMap& pred,int& tree_counter,const int limit){ |
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){ |
217 std::vector<typename SrcGraph::Node> tree_nodes; |
220 std::vector<typename SrcGraph::Node> tree_nodes; |
218 int tree_index=tree_counter; |
221 int tree_index=tree_counter; |
219 bool stop=false; |
222 bool stop=false; |
220 while(!heap.empty() && !stop){ |
223 while(!heap.empty() && !stop){ |
221 typename SrcGraph::Node v=heap.top(); |
224 typename SrcGraph::Node v=heap.top(); |
252 } |
255 } |
253 } |
256 } |
254 for(int i=1;i<(int)tree_nodes.size();++i){ |
257 for(int i=1;i<(int)tree_nodes.size();++i){ |
255 _tree->set(orig[pred[tree_nodes[i]]],true); |
258 _tree->set(orig[pred[tree_nodes[i]]],true); |
256 processed.set(tree_nodes[i],tree_index); |
259 processed.set(tree_nodes[i],tree_index); |
257 heap.state(tree_nodes[i], Heap::PRE_HEAP); |
260 crossref[tree_nodes[i]] = Heap::PRE_HEAP; |
258 } |
261 } |
259 processed.set(tree_nodes[0],tree_index); |
262 processed.set(tree_nodes[0],tree_index); |
260 heap.state(tree_nodes[0],Heap::PRE_HEAP); |
263 crossref[tree_nodes[0]] = Heap::PRE_HEAP; |
261 while (!heap.empty()) { |
264 while (!heap.empty()) { |
262 typename SrcGraph::Node v=heap.top(); |
265 typename SrcGraph::Node v=heap.top(); |
263 heap.pop(); |
266 heap.pop(); |
264 heap.state(v,Heap::PRE_HEAP); |
267 crossref[v] = Heap::PRE_HEAP; |
265 } |
268 } |
|
269 heap.clear(); |
266 if(!stop)++tree_counter; |
270 if(!stop)++tree_counter; |
267 } |
271 } |
268 |
272 |
269 template<class SrcGraph,class OrigMap,class ProcessedMap> |
273 template<class SrcGraph,class OrigMap,class ProcessedMap> |
270 void createTrees(const SrcGraph& graph,const OrigMap& orig, ProcessedMap& processed, |
274 void createTrees(const SrcGraph& graph, const OrigMap& orig, |
271 int edgenum,int& tree_counter){ |
275 ProcessedMap& processed, |
|
276 int edgenum,int& tree_counter){ |
272 typedef typename SrcGraph::Node Node; |
277 typedef typename SrcGraph::Node Node; |
273 typedef typename SrcGraph::UEdge UEdge; |
278 typedef typename SrcGraph::UEdge UEdge; |
274 typedef typename SrcGraph::NodeIt NodeIt; |
279 typedef typename SrcGraph::NodeIt NodeIt; |
275 typedef typename SrcGraph::template NodeMap<int> HeapCrossRef; |
280 typedef typename SrcGraph::template NodeMap<int> HeapCrossRef; |
276 typedef typename SrcGraph::template NodeMap<UEdge> PredMap; |
281 typedef typename SrcGraph::template NodeMap<UEdge> PredMap; |
277 HeapCrossRef crossref(graph,-1); |
282 HeapCrossRef crossref(graph,-1); |
278 FibHeap<Node,Value,HeapCrossRef> heap(crossref); |
283 FibHeap<Node,Value,HeapCrossRef> heap(crossref); |
279 PredMap pred(graph,INVALID); |
284 PredMap pred(graph,INVALID); |
280 int rate=2*edgenum/countNodes(graph); |
285 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); |
282 for(NodeIt i(graph);i!=INVALID;++i){ |
288 for(NodeIt i(graph);i!=INVALID;++i){ |
283 if(processed[i]==-1){ |
289 if(processed[i]==-1){ |
284 heap.push(i, Value()); |
290 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); |
286 } |
293 } |
287 } |
294 } |
288 } |
295 } |
289 |
296 |
290 template<class SrcGraph,class DestGraph,class SrcOrigMap,class DestOrigMap,class ProcessedMap> |
297 template<class SrcGraph,class DestGraph,class SrcOrigMap, |
291 void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,DestGraph& destgraph, |
298 class DestOrigMap,class ProcessedMap> |
292 DestOrigMap& destorig,const ProcessedMap& processed,const int tree_counter){ |
299 void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig, |
|
300 DestGraph& destgraph,DestOrigMap& destorig, |
|
301 const ProcessedMap& processed,const int tree_counter){ |
293 typedef typename SrcGraph::Node Node; |
302 typedef typename SrcGraph::Node Node; |
294 typedef typename DestGraph::Node DNode; |
303 typedef typename DestGraph::Node DNode; |
295 typedef typename SrcGraph::UEdge UEdge; |
304 typedef typename SrcGraph::UEdge UEdge; |
296 typedef typename DestGraph::UEdge DUEdge; |
305 typedef typename DestGraph::UEdge DUEdge; |
297 typedef typename SrcGraph::Edge Edge; |
306 typedef typename SrcGraph::Edge Edge; |
308 nodes[processed[srcgraph.target(i)]]=destgraph.addNode(); |
317 nodes[processed[srcgraph.target(i)]]=destgraph.addNode(); |
309 } |
318 } |
310 } |
319 } |
311 } |
320 } |
312 |
321 |
313 radixSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,sourceMap(srcgraph)))); |
322 radixSort(edges.begin(),edges.end(), |
314 counterSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,targetMap(srcgraph)))); |
323 mapFunctor(composeMap(processed,sourceMap(srcgraph)))); |
|
324 counterSort(edges.begin(),edges.end(), |
|
325 mapFunctor(composeMap(processed,targetMap(srcgraph)))); |
315 for(int i=0;i!=(int)edges.size();++i){ |
326 for(int i=0;i!=(int)edges.size();++i){ |
316 int srcproc=processed[srcgraph.source(edges[i])]; |
327 int srcproc=processed[srcgraph.source(edges[i])]; |
317 int trgproc=processed[srcgraph.target(edges[i])]; |
328 int trgproc=processed[srcgraph.target(edges[i])]; |
318 Value minval=(*cost)[srcorig[edges[i]]]; |
329 Value minval=(*cost)[srcorig[edges[i]]]; |
319 UEdge minpos=edges[i]; |
330 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])] && |
321 trgproc==processed[srcgraph.target(edges[i+1])]) { |
333 trgproc==processed[srcgraph.target(edges[i+1])]) { |
322 if (minval>(*cost)[srcorig[edges[i+1]]]) { |
334 if (minval>(*cost)[srcorig[edges[i+1]]]) { |
323 minval=(*cost)[srcorig[edges[i+1]]]; |
335 minval=(*cost)[srcorig[edges[i+1]]]; |
324 minpos=edges[i+1]; |
336 minpos=edges[i+1]; |
325 } |
337 } |
326 ++i; |
338 ++i; |
327 } |
339 } |
328 destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=srcorig[minpos]; |
340 destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]= |
|
341 srcorig[minpos]; |
329 } |
342 } |
330 } |
343 } |
331 |
344 |
332 template<class SrcGraph,class OrigMap> |
345 template<class SrcGraph,class OrigMap> |
333 void phase(const SrcGraph& graph,const OrigMap& orig,int edgenum){ |
346 void phase(const SrcGraph& graph,const OrigMap& orig,int edgenum){ |