COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/fredman_tarjan.h @ 2050:d9a221218ea4

Last change on this file since 2050:d9a221218ea4 was 2050:d9a221218ea4, checked in by Balazs Dezso, 18 years ago

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

File size: 16.2 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_FREDMAN_TARJAN_H
20#define LEMON_FREDMAN_TARJAN_H
21
22///\ingroup spantree
23///\file
24///\brief FredmanTarjan algorithm to compute minimum spanning forest.
25
26#include <limits>
27#include <vector>
28
29#include <lemon/list_graph.h>
30#include <lemon/smart_graph.h>
31#include <lemon/fib_heap.h>
32#include <lemon/radix_sort.h>
33#include <lemon/bits/invalid.h>
34#include <lemon/error.h>
35#include <lemon/maps.h>
36#include <lemon/bits/traits.h>
37#include <lemon/graph_utils.h>
38
39#include <lemon/concept/ugraph.h>
40
41namespace lemon {
42
43  ///Default traits class of FredmanTarjan class.
44
45  ///Default traits class of FredmanTarjan class.
46  ///\param GR Graph type.
47  ///\param CM Type of cost map.
48  template<class GR, class CM>
49  struct FredmanTarjanDefaultTraits{
50    ///The graph type the algorithm runs on.
51    typedef GR UGraph;
52    ///The type of the map that stores the edge costs.
53
54    ///The type of the map that stores the edge costs.
55    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
56    typedef CM CostMap;
57    //The type of the cost of the edges.
58    typedef typename CM::Value Value;
59    ///The type of the map that stores whether an edge is in the
60    ///spanning tree or not.
61
62    ///The type of the map that stores whether an edge is in the
63    ///spanning tree or not.
64    ///It must meet the \ref concept::ReadWriteMap "ReadWriteMap" concept.
65    ///By default it is a BoolEdgeMap.
66    typedef typename UGraph::template UEdgeMap<bool> TreeMap;
67    ///Instantiates a TreeMap.
68
69    ///This function instantiates a \ref TreeMap.
70    ///\param _graph is the graph, to which
71    ///we would like to define the \ref TreeMap
72    static TreeMap *createTreeMap(const GR &_graph){
73      return new TreeMap(_graph);
74    }
75  };
76 
77  ///%FredmanTarjan algorithm class to find a minimum spanning tree.
78 
79  /// \ingroup spantree
80  ///
81  ///This class provides an efficient implementation of %FredmanTarjan
82  ///algorithm whitch is sometimes a bit quicker than the Prim
83  ///algorithm on larger graphs.  Due to the structure of the
84  ///algorithm, it has less controll functions than Prim.
85  ///
86  /// The running time is \f$ O(e\beta(e,n)) \f$ where
87  /// \f$ \beta(e,n) = \min\{ i | \log^{i}(n) \le e/n\} \f$ and
88  /// \f$ \log^{i+1}(n)=\log(\log^{i}(n)) \f$
89  ///
90  ///The edge costs are passed to the algorithm using a \ref
91  ///concept::ReadMap "ReadMap", so it is easy to change it to any
92  ///kind of cost.
93  ///
94  ///The type of the cost is determined by the \ref
95  ///concept::ReadMap::Value "Value" of the cost map.
96  ///
97  ///\param GR The graph type the algorithm runs on. The default value
98  ///is \ref ListUGraph. The value of GR is not used directly by
99  ///FredmanTarjan, it is only passed to \ref
100  ///FredmanTarjanDefaultTraits.
101  ///
102  ///\param CM This read-only UEdgeMap determines the costs of the
103  ///edges. It is read once for each edge, so the map may involve in
104  ///relatively time consuming process to compute the edge cost if it
105  ///is necessary. The default map type is \ref
106  ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value of
107  ///CM is not used directly by FredmanTarjan, it is only passed to
108  ///\ref FredmanTarjanDefaultTraits.
109  ///
110  ///\param TR Traits class to set various data types used by the
111  ///algorithm.  The default traits class is \ref
112  ///FredmanTarjanDefaultTraits "FredmanTarjanDefaultTraits<GR,CM>".
113  ///See \ref FredmanTarjanDefaultTraits for the documentation of a
114  ///FredmanTarjan traits class.
115  ///
116  ///\author Balazs Attila Mihaly
117
118#ifdef DOXYGEN
119  template <typename GR,
120            typename CM,
121            typename TR>
122#else
123  template <typename GR=ListUGraph,
124            typename CM=typename GR::template UEdgeMap<int>,
125            typename TR=FredmanTarjanDefaultTraits<GR,CM> >
126#endif
127  class FredmanTarjan {
128  public:
129    ///\brief \ref Exception for uninitialized parameters.
130    ///
131    ///This error represents problems in the initialization
132    ///of the parameters of the algorithms.
133    class UninitializedParameter : public lemon::UninitializedParameter {
134    public:
135      virtual const char* exceptionName() const {
136        return "lemon::FredmanTarjan::UninitializedParameter";
137      }
138    };
139
140    typedef GR Graph;
141    typedef TR Traits;
142    ///The type of the underlying graph.
143    typedef typename TR::UGraph UGraph;
144    ///\e
145    typedef typename UGraph::Node Node;
146    ///\e
147    typedef typename UGraph::NodeIt NodeIt;
148    ///\e
149    typedef typename UGraph::UEdge UEdge;
150    ///\e
151    typedef typename UGraph::UEdgeIt UEdgeIt;
152    ///\e
153    typedef typename UGraph::IncEdgeIt IncEdgeIt;
154   
155    ///The type of the cost of the edges.
156    typedef typename TR::CostMap::Value Value;
157    ///The type of the map that stores the edge costs.
158    typedef typename TR::CostMap CostMap;
159    ///Edges of the spanning tree.
160    typedef typename TR::TreeMap TreeMap;
161  private:
162    ///Pointer to the underlying graph.
163    const UGraph *graph;
164    ///Pointer to the cost map
165    const CostMap *cost;
166    ///Pointer to the map of tree edges.
167    TreeMap *_tree;
168    ///Indicates if \ref _tree is locally allocated (\c true) or not.
169    bool local_tree;
170
171    ///Creates the maps if necessary.
172   
173    void create_maps(){
174      if(!_tree){
175        local_tree=true;
176        _tree=Traits::createTreeMap(*graph);
177      }
178    }
179   
180  public :
181
182    typedef FredmanTarjan Create;
183 
184    ///\name Named template parameters
185
186    ///@{
187
188    template <class TM>
189    struct DefTreeMapTraits : public Traits {
190      typedef TM TreeMap;
191      static TreeMap *createTreeMap(const UGraph &) {
192        throw UninitializedParameter();
193      }
194    };
195    ///\ref named-templ-param "Named parameter" for setting TreeMap
196
197    ///\ref named-templ-param "Named parameter" for setting TreeMap
198    ///
199    template <class TM>
200    struct DefTreeMap
201      : public FredmanTarjan< UGraph, CostMap, DefTreeMapTraits<TM> > {
202      typedef FredmanTarjan< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
203    };
204
205    ///@}
206
207
208  protected:
209
210    FredmanTarjan() {}
211
212  private:
213
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){
220      std::vector<typename SrcGraph::Node> tree_nodes;
221      int tree_index=tree_counter;
222      bool stop=false;
223      while(!heap.empty() && !stop){
224        typename SrcGraph::Node v=heap.top();
225        heap.pop();
226        if(processed[v]!=-1){
227          heap.state(v,Heap::PRE_HEAP);
228          tree_index=processed[v];
229          _tree->set(orig[pred[v]],true);
230          stop=true;
231          break;
232        }
233        tree_nodes.push_back(v);
234        for(typename SrcGraph::IncEdgeIt e(graph,v);e!=INVALID;++e){
235          typename SrcGraph::Node w=graph.oppositeNode(v,e);
236          switch(heap.state(w)){
237          case Heap::PRE_HEAP:
238            if(heap.size()>=limit){
239              stop=true;
240            }
241            else{
242              heap.push(w,(*cost)[orig[e]]);
243              pred.set(w,e);
244            }
245            break;
246          case Heap::IN_HEAP:
247            if ((*cost)[orig[e]]<heap[w]){
248              heap.decrease(w,(*cost)[orig[e]]);
249              pred.set(w,e);
250            }
251            break;
252          case Heap::POST_HEAP:
253            break;
254          }
255        }
256      }
257      for(int i=1;i<(int)tree_nodes.size();++i){
258        _tree->set(orig[pred[tree_nodes[i]]],true);
259        processed.set(tree_nodes[i],tree_index);
260        crossref[tree_nodes[i]] = Heap::PRE_HEAP;
261      }
262      processed.set(tree_nodes[0],tree_index);
263      crossref[tree_nodes[0]] = Heap::PRE_HEAP;
264      while (!heap.empty()) {
265        typename SrcGraph::Node v=heap.top();
266        heap.pop();
267        crossref[v] = Heap::PRE_HEAP;
268      }
269      heap.clear();
270      if(!stop)++tree_counter;
271    }
272
273    template<class SrcGraph,class OrigMap,class ProcessedMap>
274    void createTrees(const SrcGraph& graph, const OrigMap& orig,
275                     ProcessedMap& processed,
276                     int edgenum,int& tree_counter){
277      typedef typename SrcGraph::Node Node;
278      typedef typename SrcGraph::UEdge UEdge;
279      typedef typename SrcGraph::NodeIt NodeIt;
280      typedef typename SrcGraph::template NodeMap<int> HeapCrossRef;
281      typedef typename SrcGraph::template NodeMap<UEdge> PredMap;
282      HeapCrossRef crossref(graph,-1);
283      FibHeap<Node,Value,HeapCrossRef> heap(crossref);
284      PredMap pred(graph,INVALID);
285      int rate=2*edgenum/countNodes(graph);
286      int limit=(rate>std::numeric_limits<int>::digits)?
287      std::numeric_limits<int>::max() : (1<<rate);
288      for(NodeIt i(graph);i!=INVALID;++i){
289        if(processed[i]==-1){
290          heap.push(i, Value());
291          processNextTree(graph,orig,heap,crossref,
292                          processed,pred,tree_counter,limit);
293        }
294      }
295    }
296
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){
302      typedef typename SrcGraph::Node Node;
303      typedef typename DestGraph::Node DNode;
304      typedef typename SrcGraph::UEdge UEdge;
305      typedef typename DestGraph::UEdge DUEdge;
306      typedef typename SrcGraph::Edge Edge;
307      typedef typename SrcGraph::EdgeIt EdgeIt;
308      std::vector<Edge> edges;
309      std::vector<DNode> nodes(tree_counter, INVALID);
310      for(EdgeIt i(srcgraph);i!=INVALID;++i){
311        if(processed[srcgraph.source(i)]<processed[srcgraph.target(i)]){
312          edges.push_back(i);
313          if(nodes[processed[srcgraph.source(i)]]==INVALID) {
314            nodes[processed[srcgraph.source(i)]]=destgraph.addNode();
315          }
316          if(nodes[processed[srcgraph.target(i)]]==INVALID) {
317            nodes[processed[srcgraph.target(i)]]=destgraph.addNode();
318          }
319        }
320      }
321     
322      radixSort(edges.begin(),edges.end(),
323                mapFunctor(composeMap(processed,sourceMap(srcgraph))));
324      counterSort(edges.begin(),edges.end(),
325                  mapFunctor(composeMap(processed,targetMap(srcgraph))));
326      for(int i=0;i!=(int)edges.size();++i){
327        int srcproc=processed[srcgraph.source(edges[i])];
328        int trgproc=processed[srcgraph.target(edges[i])];
329        Value minval=(*cost)[srcorig[edges[i]]];
330        UEdge minpos=edges[i];
331        while (i+1!=(int)edges.size() &&
332               srcproc==processed[srcgraph.source(edges[i+1])] &&
333          trgproc==processed[srcgraph.target(edges[i+1])]) {
334          if (minval>(*cost)[srcorig[edges[i+1]]]) {
335            minval=(*cost)[srcorig[edges[i+1]]];
336            minpos=edges[i+1];
337          }
338          ++i;
339        }
340        destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=
341          srcorig[minpos];
342      }
343    }
344
345    template<class SrcGraph,class OrigMap>
346    void phase(const SrcGraph& graph,const OrigMap& orig,int edgenum){
347      int tree_counter = 0;
348      typename SrcGraph::template NodeMap<int> processed(graph,-1);
349      SmartUGraph destgraph;
350      SmartUGraph::UEdgeMap<typename OrigMap::Value> destorig(destgraph);
351      createTrees(graph,orig,processed,edgenum,tree_counter);
352      collect(graph,orig,destgraph,destorig,processed,tree_counter);
353      if (countNodes(destgraph)>1) {
354        phase(destgraph,destorig,edgenum);
355      }
356    }
357
358  public:     
359   
360    ///Constructor.
361   
362    ///\param _graph the graph the algorithm will run on.
363    ///\param _cost the cost map used by the algorithm.
364    FredmanTarjan(const UGraph& _graph, const CostMap& _cost) :
365      graph(&_graph), cost(&_cost),
366      _tree(0), local_tree(false)
367    {
368      checkConcept<concept::UGraph, UGraph>();
369    }
370   
371    ///Destructor.
372    ~FredmanTarjan(){
373      if(local_tree) delete _tree;
374    }
375
376    ///Sets the cost map.
377
378    ///Sets the cost map.
379    ///\return <tt> (*this) </tt>
380    FredmanTarjan &costMap(const CostMap &m){
381      cost = &m;
382      return *this;
383    }
384
385    ///Sets the map storing the tree edges.
386
387    ///Sets the map storing the tree edges.
388    ///If you don't use this function before calling \ref run(),
389    ///it will allocate one. The destuctor deallocates this
390    ///automatically allocated map, of course.
391    ///By default this is a BoolEdgeMap.
392    ///\return <tt> (*this) </tt>
393    FredmanTarjan &treeMap(TreeMap &m){
394      if(local_tree) {
395        delete _tree;
396        local_tree=false;
397      }
398      _tree = &m;
399      return *this;
400    }
401
402  public:
403    ///\name Execution control
404    ///The simplest way to execute the algorithm is to use
405    ///one of the member functions called \c run(...).
406
407    ///@{
408
409    ///Initializes the internal data structures.
410
411    ///Initializes the internal data structures.
412    ///
413    void init(){
414      create_maps();
415      for(typename Graph::UEdgeIt i(*graph);i!=INVALID;++i){
416        _tree->set(i,false);
417      }
418    }
419
420    ///Executes the algorithm.
421
422    ///Executes the algorithm.
423    ///
424    ///\pre init() must be called and at least one node should be added
425    ///with addSource() before using this function.
426    ///
427    ///This method runs the %FredmanTarjan algorithm from the node(s)
428    ///in order to compute the
429    ///minimum spanning tree.
430    void start(){
431        phase(*graph,identityMap<UEdge>(),countEdges(*graph));
432    }
433   
434    ///Runs %FredmanTarjan algorithm.
435   
436    ///This method runs the %FredmanTarjan algorithm
437    ///in order to compute the minimum spanning forest.
438    ///
439    ///\note ft.run() is just a shortcut of the following code.
440    ///\code
441    ///  ft.init();
442    ///  ft.start();
443    ///\endcode
444    void run() {
445      init();
446      start();
447    }
448
449    ///@}
450
451    ///\name Query Functions
452    ///The result of the %FredmanTarjan algorithm can be obtained using these
453    ///functions.\n
454    ///Before the use of these functions,
455    ///either run() or start() must be called.
456   
457    ///@{
458
459    ///Returns a reference to the tree edges map.
460
461    ///Returns a reference to the TreeEdgeMap of the edges of the
462    ///minimum spanning tree. The value of the map is \c true only if the
463    ///edge is in the minimum spanning tree.
464    ///
465    ///\pre \ref run() or \ref start() must be called before using this
466    ///function.
467    const TreeMap &treeMap() const { return *_tree;}
468 
469    ///Sets the tree edges map.
470
471    ///Sets the TreeMap of the edges of the minimum spanning tree.
472    ///The map values belonging to the edges of the minimum
473    ///spanning tree are set to \c tree_edge_value or \c true by default
474    ///while the edge values not belonging to the minimum spanning tree are
475    ///set to
476    ///\c tree_default_value or \c false by default.
477    ///
478    ///\pre \ref run() or \ref start() must be called before using this
479    ///function.
480
481    template<class TreeMap>
482    void treeEdges(
483        TreeMap& tree,
484        const typename TreeMap::Value& tree_edge_value=true,
485        const typename TreeMap::Value& tree_default_value=false) const {
486      for(typename UGraph::UEdgeIt i(*graph);i!=INVALID;++i){
487        (*_tree)[i]?tree.set(i,tree_edge_value):tree.set(i,tree_default_value);
488      }
489    }
490
491    ///\brief Checks if an edge is in the spanning tree or not.
492
493    ///Checks if an edge is in the spanning tree or not.
494    ///\param e is the edge that will be checked
495    ///\return \c true if e is in the spanning tree, \c false otherwise
496    bool tree(UEdge e){
497      return (*_tree)[e];
498    }
499    ///@}
500  };
501
502  /// \ingroup spantree
503  ///
504  /// \brief Function type interface for FredmanTarjan algorithm.
505  ///
506  /// Function type interface for FredmanTarjan algorithm.
507  /// \param graph the UGraph that the algorithm runs on
508  /// \param cost the CostMap of the edges
509  /// \retval tree the EdgeMap that contains whether an edge is in the
510  /// spanning tree or not
511  ///
512  /// \sa Prim
513  template<class Graph,class CostMap,class TreeMap>
514  void fredmanTarjan(const Graph& graph, const CostMap& cost,TreeMap& tree){
515    typename FredmanTarjan<Graph,CostMap>::template DefTreeMap<TreeMap>::
516      Create ft(graph,cost);
517    ft.treeMap(tree);
518    ft.run();
519  }
520
521} //END OF NAMESPACE LEMON
522
523#endif
Note: See TracBrowser for help on using the repository browser.