COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/fredman_tarjan.h @ 2042:bdc953f2a449

Last change on this file since 2042:bdc953f2a449 was 2042:bdc953f2a449, checked in by Balazs Dezso, 14 years ago

New Algorithm group for matchings

LaTeX formulas
Bug fix => /\f$ will cause parsing error in doxygen

File size: 15.9 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 ProcessedMap,class PredMap>
215    void processNextTree(const SrcGraph& graph,const OrigMap& orig,Heap &heap,
216        ProcessedMap& processed,PredMap& pred,int& tree_counter,const int limit){
217      std::vector<typename SrcGraph::Node> tree_nodes;
218      int tree_index=tree_counter;
219      bool stop=false;
220      while(!heap.empty() && !stop){
221        typename SrcGraph::Node v=heap.top();
222        heap.pop();
223        if(processed[v]!=-1){
224          heap.state(v,Heap::PRE_HEAP);
225          tree_index=processed[v];
226          _tree->set(orig[pred[v]],true);
227          stop=true;
228          break;
229        }
230        tree_nodes.push_back(v);
231        for(typename SrcGraph::IncEdgeIt e(graph,v);e!=INVALID;++e){
232          typename SrcGraph::Node w=graph.oppositeNode(v,e);
233          switch(heap.state(w)){
234          case Heap::PRE_HEAP:
235            if(heap.size()>=limit){
236              stop=true;
237            }
238            else{
239              heap.push(w,(*cost)[orig[e]]);
240              pred.set(w,e);
241            }
242            break;
243          case Heap::IN_HEAP:
244            if ((*cost)[orig[e]]<heap[w]){
245              heap.decrease(w,(*cost)[orig[e]]);
246              pred.set(w,e);
247            }
248            break;
249          case Heap::POST_HEAP:
250            break;
251          }
252        }
253      }
254      for(int i=1;i<(int)tree_nodes.size();++i){
255        _tree->set(orig[pred[tree_nodes[i]]],true);
256        processed.set(tree_nodes[i],tree_index);
257        heap.state(tree_nodes[i], Heap::PRE_HEAP);
258      }
259      processed.set(tree_nodes[0],tree_index);
260      heap.state(tree_nodes[0],Heap::PRE_HEAP);
261      while (!heap.empty()) {
262        typename SrcGraph::Node v=heap.top();
263        heap.pop();
264        heap.state(v,Heap::PRE_HEAP);
265      }
266      if(!stop)++tree_counter;
267    }
268
269    template<class SrcGraph,class OrigMap,class ProcessedMap>
270    void createTrees(const SrcGraph& graph,const OrigMap& orig, ProcessedMap& processed,
271        int edgenum,int& tree_counter){
272      typedef typename SrcGraph::Node Node;
273      typedef typename SrcGraph::UEdge UEdge;
274      typedef typename SrcGraph::NodeIt NodeIt;
275      typedef typename SrcGraph::template NodeMap<int> HeapCrossRef;
276      typedef typename SrcGraph::template NodeMap<UEdge> PredMap;
277      HeapCrossRef crossref(graph,-1);
278      FibHeap<Node,Value,HeapCrossRef> heap(crossref);
279      PredMap pred(graph,INVALID);
280      int rate=2*edgenum/countNodes(graph);
281      int limit=(rate>std::numeric_limits<int>::digits)?std::numeric_limits<int>::max():(1<<rate);
282      for(NodeIt i(graph);i!=INVALID;++i){
283        if(processed[i]==-1){
284          heap.push(i, Value());
285          processNextTree(graph,orig,heap,processed,pred,tree_counter,limit);
286        }
287      }
288    }
289
290    template<class SrcGraph,class DestGraph,class SrcOrigMap,class DestOrigMap,class ProcessedMap>
291    void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,DestGraph& destgraph,
292        DestOrigMap& destorig,const ProcessedMap& processed,const int tree_counter){
293      typedef typename SrcGraph::Node Node;
294      typedef typename DestGraph::Node DNode;
295      typedef typename SrcGraph::UEdge UEdge;
296      typedef typename DestGraph::UEdge DUEdge;
297      typedef typename SrcGraph::Edge Edge;
298      typedef typename SrcGraph::EdgeIt EdgeIt;
299      std::vector<Edge> edges;
300      std::vector<DNode> nodes(tree_counter, INVALID);
301      for(EdgeIt i(srcgraph);i!=INVALID;++i){
302        if(processed[srcgraph.source(i)]<processed[srcgraph.target(i)]){
303          edges.push_back(i);
304          if(nodes[processed[srcgraph.source(i)]]==INVALID) {
305            nodes[processed[srcgraph.source(i)]]=destgraph.addNode();
306          }
307          if(nodes[processed[srcgraph.target(i)]]==INVALID) {
308            nodes[processed[srcgraph.target(i)]]=destgraph.addNode();
309          }
310        }
311      }
312     
313      radixSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,sourceMap(srcgraph))));
314      counterSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,targetMap(srcgraph))));
315      for(int i=0;i!=(int)edges.size();++i){
316        int srcproc=processed[srcgraph.source(edges[i])];
317        int trgproc=processed[srcgraph.target(edges[i])];
318        Value minval=(*cost)[srcorig[edges[i]]];
319        UEdge minpos=edges[i];
320        while (i+1!=(int)edges.size() && srcproc==processed[srcgraph.source(edges[i+1])] &&
321          trgproc==processed[srcgraph.target(edges[i+1])]) {
322          if (minval>(*cost)[srcorig[edges[i+1]]]) {
323            minval=(*cost)[srcorig[edges[i+1]]];
324            minpos=edges[i+1];
325          }
326          ++i;
327        }
328        destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=srcorig[minpos];
329      }
330    }
331
332    template<class SrcGraph,class OrigMap>
333    void phase(const SrcGraph& graph,const OrigMap& orig,int edgenum){
334      int tree_counter = 0;
335      typename SrcGraph::template NodeMap<int> processed(graph,-1);
336      SmartUGraph destgraph;
337      SmartUGraph::UEdgeMap<typename OrigMap::Value> destorig(destgraph);
338      createTrees(graph,orig,processed,edgenum,tree_counter);
339      collect(graph,orig,destgraph,destorig,processed,tree_counter);
340      if (countNodes(destgraph)>1) {
341        phase(destgraph,destorig,edgenum);
342      }
343    }
344
345  public:     
346   
347    ///Constructor.
348   
349    ///\param _graph the graph the algorithm will run on.
350    ///\param _cost the cost map used by the algorithm.
351    FredmanTarjan(const UGraph& _graph, const CostMap& _cost) :
352      graph(&_graph), cost(&_cost),
353      _tree(0), local_tree(false)
354    {
355      checkConcept<concept::UGraph, UGraph>();
356    }
357   
358    ///Destructor.
359    ~FredmanTarjan(){
360      if(local_tree) delete _tree;
361    }
362
363    ///Sets the cost map.
364
365    ///Sets the cost map.
366    ///\return <tt> (*this) </tt>
367    FredmanTarjan &costMap(const CostMap &m){
368      cost = &m;
369      return *this;
370    }
371
372    ///Sets the map storing the tree edges.
373
374    ///Sets the map storing the tree edges.
375    ///If you don't use this function before calling \ref run(),
376    ///it will allocate one. The destuctor deallocates this
377    ///automatically allocated map, of course.
378    ///By default this is a BoolEdgeMap.
379    ///\return <tt> (*this) </tt>
380    FredmanTarjan &treeMap(TreeMap &m){
381      if(local_tree) {
382        delete _tree;
383        local_tree=false;
384      }
385      _tree = &m;
386      return *this;
387    }
388
389  public:
390    ///\name Execution control
391    ///The simplest way to execute the algorithm is to use
392    ///one of the member functions called \c run(...).
393
394    ///@{
395
396    ///Initializes the internal data structures.
397
398    ///Initializes the internal data structures.
399    ///
400    void init(){
401      create_maps();
402      for(typename Graph::UEdgeIt i(*graph);i!=INVALID;++i){
403        _tree->set(i,false);
404      }
405    }
406
407    ///Executes the algorithm.
408
409    ///Executes the algorithm.
410    ///
411    ///\pre init() must be called and at least one node should be added
412    ///with addSource() before using this function.
413    ///
414    ///This method runs the %FredmanTarjan algorithm from the node(s)
415    ///in order to compute the
416    ///minimum spanning tree.
417    void start(){
418        phase(*graph,identityMap<UEdge>(),countEdges(*graph));
419    }
420   
421    ///Runs %FredmanTarjan algorithm.
422   
423    ///This method runs the %FredmanTarjan algorithm
424    ///in order to compute the minimum spanning forest.
425    ///
426    ///\note ft.run() is just a shortcut of the following code.
427    ///\code
428    ///  ft.init();
429    ///  ft.start();
430    ///\endcode
431    void run() {
432      init();
433      start();
434    }
435
436    ///@}
437
438    ///\name Query Functions
439    ///The result of the %FredmanTarjan algorithm can be obtained using these
440    ///functions.\n
441    ///Before the use of these functions,
442    ///either run() or start() must be called.
443   
444    ///@{
445
446    ///Returns a reference to the tree edges map.
447
448    ///Returns a reference to the TreeEdgeMap of the edges of the
449    ///minimum spanning tree. The value of the map is \c true only if the
450    ///edge is in the minimum spanning tree.
451    ///
452    ///\pre \ref run() or \ref start() must be called before using this
453    ///function.
454    const TreeMap &treeMap() const { return *_tree;}
455 
456    ///Sets the tree edges map.
457
458    ///Sets the TreeMap of the edges of the minimum spanning tree.
459    ///The map values belonging to the edges of the minimum
460    ///spanning tree are set to \c tree_edge_value or \c true by default
461    ///while the edge values not belonging to the minimum spanning tree are
462    ///set to
463    ///\c tree_default_value or \c false by default.
464    ///
465    ///\pre \ref run() or \ref start() must be called before using this
466    ///function.
467
468    template<class TreeMap>
469    void treeEdges(
470        TreeMap& tree,
471        const typename TreeMap::Value& tree_edge_value=true,
472        const typename TreeMap::Value& tree_default_value=false) const {
473      for(typename UGraph::UEdgeIt i(*graph);i!=INVALID;++i){
474        (*_tree)[i]?tree.set(i,tree_edge_value):tree.set(i,tree_default_value);
475      }
476    }
477
478    ///\brief Checks if an edge is in the spanning tree or not.
479
480    ///Checks if an edge is in the spanning tree or not.
481    ///\param e is the edge that will be checked
482    ///\return \c true if e is in the spanning tree, \c false otherwise
483    bool tree(UEdge e){
484      return (*_tree)[e];
485    }
486    ///@}
487  };
488
489  /// \ingroup spantree
490  ///
491  /// \brief Function type interface for FredmanTarjan algorithm.
492  ///
493  /// Function type interface for FredmanTarjan algorithm.
494  /// \param graph the UGraph that the algorithm runs on
495  /// \param cost the CostMap of the edges
496  /// \retval tree the EdgeMap that contains whether an edge is in the
497  /// spanning tree or not
498  ///
499  /// \sa Prim
500  template<class Graph,class CostMap,class TreeMap>
501  void fredmanTarjan(const Graph& graph, const CostMap& cost,TreeMap& tree){
502    typename FredmanTarjan<Graph,CostMap>::template DefTreeMap<TreeMap>::
503      Create ft(graph,cost);
504    ft.treeMap(tree);
505    ft.run();
506  }
507
508} //END OF NAMESPACE LEMON
509
510#endif
Note: See TracBrowser for help on using the repository browser.