COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/fredman_tarjan.h @ 1933:a876a3d6a4c7

Last change on this file since 1933:a876a3d6a4c7 was 1912:d9205a711324, checked in by Balazs Dezso, 14 years ago

Algorithms by szakall

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