COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/fredman_tarjan.h @ 2029:e00114f165f5

Last change on this file since 2029:e00114f165f5 was 1993:2115143eceea, checked in by Balazs Dezso, 18 years ago

utility, invalid and traits moved to bits

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