COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/fredman_tarjan.h @ 2524:44675961f645

Last change on this file since 2524:44675961f645 was 2490:31a93dd6f714, checked in by Balazs Dezso, 16 years ago

Minor bug fixes in documentation

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-2007
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/concepts/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 concepts::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 concepts::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  ///concepts::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  ///concepts::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  ///concepts::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* what() const throw() {
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    ///\brief \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<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<concepts::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.