COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/prim.h @ 2091:c8ccc1f8fd51

Last change on this file since 2091:c8ccc1f8fd51 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: 25.4 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_PRIM_H
20#define LEMON_PRIM_H
21
22///\ingroup spantree
23///\file
24///\brief Prim algorithm to compute minimum spanning tree.
25
26#include <lemon/list_graph.h>
27#include <lemon/bin_heap.h>
28#include <lemon/bits/invalid.h>
29#include <lemon/error.h>
30#include <lemon/maps.h>
31#include <lemon/bits/traits.h>
32
33#include <lemon/concept/ugraph.h>
34
35namespace lemon {
36
37  ///Default traits class of Prim class.
38
39  ///Default traits class of Prim class.
40  ///\param GR Graph type.
41  ///\param CM Type of cost map.
42  template<class GR, class CM>
43  struct PrimDefaultTraits{
44    ///The graph type the algorithm runs on.
45    typedef GR UGraph;
46    ///The type of the map that stores the edge costs.
47
48    ///The type of the map that stores the edge costs.
49    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
50    typedef CM CostMap;
51    //The type of the cost of the edges.
52    typedef typename CM::Value Value;
53    /// The cross reference type used by heap.
54
55    /// The cross reference type used by heap.
56    /// Usually it is \c UGraph::NodeMap<int>.
57    typedef typename UGraph::template NodeMap<int> HeapCrossRef;
58    ///Instantiates a HeapCrossRef.
59
60    ///This function instantiates a \ref HeapCrossRef.
61    /// \param _graph is the graph, to which we would like to define the
62    /// HeapCrossRef.
63    static HeapCrossRef *createHeapCrossRef(const GR &_graph){
64      return new HeapCrossRef(_graph);
65    }
66   
67    ///The heap type used by Prim algorithm.
68
69    ///The heap type used by Prim algorithm.
70    ///
71    ///\sa BinHeap
72    ///\sa Prim
73    typedef BinHeap<typename UGraph::Node, typename CM::Value,
74                    HeapCrossRef, std::less<Value> > Heap;
75
76    static Heap *createHeap(HeapCrossRef& _ref){
77      return new Heap(_ref);
78    }
79
80    ///\brief The type of the map that stores the last
81    ///edges of the minimum spanning tree.
82    ///
83    ///The type of the map that stores the last
84    ///edges of the minimum spanning tree.
85    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
86    ///
87    typedef typename UGraph::template NodeMap<typename GR::UEdge> PredMap;
88    ///Instantiates a PredMap.
89 
90    ///This function instantiates a \ref PredMap.
91    ///\param _graph is the graph, to which we would like to define the PredMap.
92    static PredMap *createPredMap(const GR &_graph){
93      return new PredMap(_graph);
94    }
95
96    ///The type of the map that stores whether an edge is in the
97    ///spanning tree or not.
98
99    ///The type of the map that stores whether an edge is in the
100    ///spanning tree or not.
101    ///By default it is a NullMap.
102    typedef NullMap<typename UGraph::UEdge,bool> TreeMap;
103    ///Instantiates a TreeMap.
104
105    ///This function instantiates a \ref TreeMap.
106    ///
107    ///The first parameter is the graph, to which
108    ///we would like to define the \ref TreeMap
109    static TreeMap *createTreeMap(const GR &){
110      return new TreeMap();
111    }
112
113    ///The type of the map that stores whether a nodes is processed.
114 
115    ///The type of the map that stores whether a nodes is processed.
116    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
117    ///By default it is a NodeMap<bool>.
118    typedef NullMap<typename UGraph::Node,bool> ProcessedMap;
119    ///Instantiates a ProcessedMap.
120 
121    ///This function instantiates a \ref ProcessedMap.
122    ///\param _graph is the graph, to which
123    ///we would like to define the \ref ProcessedMap
124#ifdef DOXYGEN
125    static ProcessedMap *createProcessedMap(const GR &_graph)
126#else
127    static ProcessedMap *createProcessedMap(const GR &)
128#endif
129    {
130      return new ProcessedMap();
131    }
132  };
133 
134  ///%Prim algorithm class to find a minimum spanning tree.
135 
136  /// \ingroup spantree
137  ///This class provides an efficient implementation of %Prim algorithm.
138  ///
139  ///The running time is \f$ O(e\log(n)) \f$ where e is the number of edges and
140  ///n is the number of nodes in the graph.
141  ///
142  ///The edge costs are passed to the algorithm using a
143  ///\ref concept::ReadMap "ReadMap",
144  ///so it is easy to change it to any kind of cost.
145  ///
146  ///The type of the cost is determined by the
147  ///\ref concept::ReadMap::Value "Value" of the cost map.
148  ///
149  ///It is also possible to change the underlying priority heap.
150  ///
151  ///\param GR The graph type the algorithm runs on. The default value
152  ///is \ref ListUGraph. The value of GR is not used directly by
153  ///Prim, it is only passed to \ref PrimDefaultTraits.
154  ///
155  ///\param CM This read-only UEdgeMap determines the costs of the
156  ///edges. It is read once for each edge, so the map may involve in
157  ///relatively time consuming process to compute the edge cost if
158  ///it is necessary. The default map type is \ref
159  ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>".  The value
160  ///of CM is not used directly by Prim, it is only passed to \ref
161  ///PrimDefaultTraits.
162  ///
163  ///\param TR Traits class to set
164  ///various data types used by the algorithm.  The default traits
165  ///class is \ref PrimDefaultTraits
166  ///"PrimDefaultTraits<GR,CM>".  See \ref
167  ///PrimDefaultTraits for the documentation of a Prim traits
168  ///class.
169  ///
170  ///\author Balazs Attila Mihaly
171
172#ifdef DOXYGEN
173  template <typename GR,
174            typename CM,
175            typename TR>
176#else
177  template <typename GR=ListUGraph,
178            typename CM=typename GR::template UEdgeMap<int>,
179            typename TR=PrimDefaultTraits<GR,CM> >
180#endif
181  class Prim {
182  public:
183   
184    /// \brief \ref Exception for uninitialized parameters.
185    ///
186    /// This error represents problems in the initialization
187    /// of the parameters of the algorithms.
188    class UninitializedParameter : public lemon::UninitializedParameter {
189    public:
190      virtual const char* exceptionName() const {
191        return "lemon::Prim::UninitializedParameter";
192      }
193    };
194
195    typedef TR Traits;
196    ///The type of the underlying graph.
197    typedef typename TR::UGraph UGraph;
198    ///\e
199    typedef typename UGraph::Node Node;
200    ///\e
201    typedef typename UGraph::NodeIt NodeIt;
202    ///\e
203    typedef typename UGraph::UEdge UEdge;
204    ///\e
205    typedef typename UGraph::IncEdgeIt IncEdgeIt;
206   
207    ///The type of the cost of the edges.
208    typedef typename TR::CostMap::Value Value;
209    ///The type of the map that stores the edge costs.
210    typedef typename TR::CostMap CostMap;
211    ///\brief The type of the map that stores the last
212    ///predecessor edges of the spanning tree.
213    typedef typename TR::PredMap PredMap;
214    ///Edges of the spanning tree.
215    typedef typename TR::TreeMap TreeMap;
216    ///The type of the map indicating if a node is processed.
217    typedef typename TR::ProcessedMap ProcessedMap;
218    ///The cross reference type used for the current heap.
219    typedef typename TR::HeapCrossRef HeapCrossRef;
220    ///The heap type used by the prim algorithm.
221    typedef typename TR::Heap Heap;
222  private:
223    /// Pointer to the underlying graph.
224    const UGraph *graph;
225    /// Pointer to the cost map
226    const CostMap *cost;
227    ///Pointer to the map of predecessors edges.
228    PredMap *_pred;
229    ///Indicates if \ref _pred is locally allocated (\c true) or not.
230    bool local_pred;
231    ///Pointer to the map of tree edges.
232    TreeMap *_tree;
233    ///Indicates if \ref _tree is locally allocated (\c true) or not.
234    bool local_tree;
235    ///Pointer to the map of processed status of the nodes.
236    ProcessedMap *_processed;
237    ///Indicates if \ref _processed is locally allocated (\c true) or not.
238    bool local_processed;
239    ///Pointer to the heap cross references.
240    HeapCrossRef *_heap_cross_ref;
241    ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
242    bool local_heap_cross_ref;
243    ///Pointer to the heap.
244    Heap *_heap;
245    ///Indicates if \ref _heap is locally allocated (\c true) or not.
246    bool local_heap;
247
248    ///Creates the maps if necessary.
249    void create_maps(){
250      if(!_pred) {
251        local_pred = true;
252        _pred = Traits::createPredMap(*graph);
253      }
254      if(!_tree) {
255        local_tree = true;
256        _tree = Traits::createTreeMap(*graph);
257      }
258      if(!_processed) {
259        local_processed = true;
260        _processed = Traits::createProcessedMap(*graph);
261      }
262      if (!_heap_cross_ref) {
263        local_heap_cross_ref = true;
264        _heap_cross_ref = Traits::createHeapCrossRef(*graph);
265      }
266      if (!_heap) {
267        local_heap = true;
268        _heap = Traits::createHeap(*_heap_cross_ref);
269      }
270    }
271   
272  public :
273
274    typedef Prim Create;
275 
276    ///\name Named template parameters
277
278    ///@{
279
280    template <class T>
281    struct DefPredMapTraits : public Traits {
282      typedef T PredMap;
283      static PredMap *createPredMap(const UGraph &_graph){
284        throw UninitializedParameter();
285      }
286    };
287    ///\ref named-templ-param "Named parameter" for setting PredMap type
288
289    ///\ref named-templ-param "Named parameter" for setting PredMap type
290    ///
291    template <class T>
292    struct DefPredMap
293      : public Prim< UGraph, CostMap, DefPredMapTraits<T> > {
294      typedef Prim< UGraph, CostMap, DefPredMapTraits<T> > Create;
295    };
296   
297    template <class T>
298    struct DefProcessedMapTraits : public Traits {
299      typedef T ProcessedMap;
300      static ProcessedMap *createProcessedMap(const UGraph &_graph){
301        throw UninitializedParameter();
302      }
303    };
304    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
305
306    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
307    ///
308    template <class T>
309    struct DefProcessedMap
310      : public Prim< UGraph, CostMap, DefProcessedMapTraits<T> > {
311      typedef Prim< UGraph, CostMap, DefProcessedMapTraits<T> > Create;
312    };
313   
314    struct DefGraphProcessedMapTraits : public Traits {
315      typedef typename UGraph::template NodeMap<bool> ProcessedMap;
316      static ProcessedMap *createProcessedMap(const UGraph &_graph){
317        return new ProcessedMap(_graph);
318      }
319    };
320
321
322    template <class H, class CR>
323    struct DefHeapTraits : public Traits {
324      typedef CR HeapCrossRef;
325      typedef H Heap;
326      static HeapCrossRef *createHeapCrossRef(const UGraph &) {
327        throw UninitializedParameter();
328      }
329      static Heap *createHeap(HeapCrossRef &){
330        return UninitializedParameter();
331      }
332    };
333    ///\ref named-templ-param "Named parameter" for setting heap and cross
334    ///reference type
335
336    ///\ref named-templ-param "Named parameter" for setting heap and cross
337    ///reference type
338    ///
339    template <class H, class CR = typename UGraph::template NodeMap<int> >
340    struct DefHeap
341      : public Prim< UGraph, CostMap, DefHeapTraits<H, CR> > {
342      typedef Prim< UGraph, CostMap, DefHeapTraits<H, CR> > Create;
343    };
344
345    template <class H, class CR>
346    struct DefStandardHeapTraits : public Traits {
347      typedef CR HeapCrossRef;
348      typedef H Heap;
349      static HeapCrossRef *createHeapCrossRef(const UGraph &_graph) {
350        return new HeapCrossRef(_graph);
351      }
352      static Heap *createHeap(HeapCrossRef &ref){
353        return new Heap(ref);
354      }
355    };
356    ///\ref named-templ-param "Named parameter" for setting heap and cross
357    ///reference type with automatic allocation
358
359    ///\ref named-templ-param "Named parameter" for setting heap and cross
360    ///reference type. It can allocate the heap and the cross reference
361    ///object if the cross reference's constructor waits for the graph as
362    ///parameter and the heap's constructor waits for the cross reference.
363    template <class H, class CR = typename UGraph::template NodeMap<int> >
364    struct DefStandardHeap
365      : public Prim< UGraph, CostMap, DefStandardHeapTraits<H, CR> > {
366      typedef Prim< UGraph, CostMap, DefStandardHeapTraits<H, CR> >
367      Create;
368    };
369
370    template <class TM>
371    struct DefTreeMapTraits : public Traits {
372      typedef TM TreeMap;
373      static TreeMap *createTreeMap(const UGraph &) {
374        throw UninitializedParameter();
375      }
376    };
377    ///\ref named-templ-param "Named parameter" for setting TreeMap
378
379    ///\ref named-templ-param "Named parameter" for setting TreeMap
380    ///
381    template <class TM>
382    struct DefTreeMap
383      : public Prim< UGraph, CostMap, DefTreeMapTraits<TM> > {
384      typedef Prim< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
385    };   
386
387    struct DefGraphTreeMapTraits : public Traits {
388      typedef typename UGraph::template NodeMap<bool> TreeMap;
389      static TreeMap *createTreeMap(const UGraph &_graph){
390        return new TreeMap(_graph);
391      }
392    };
393
394    ///@}
395
396
397  protected:
398
399    Prim() {}
400
401  public:     
402   
403    ///Constructor.
404   
405    ///\param _graph the graph the algorithm will run on.
406    ///\param _cost the cost map used by the algorithm.
407    Prim(const UGraph& _graph, const CostMap& _cost) :
408      graph(&_graph), cost(&_cost),
409      _pred(NULL), local_pred(false),
410      _tree(NULL), local_tree(false),
411      _processed(NULL), local_processed(false),
412      _heap_cross_ref(NULL), local_heap_cross_ref(false),
413      _heap(NULL), local_heap(false)
414    {
415      checkConcept<concept::UGraph, UGraph>();
416    }
417   
418    ///Destructor.
419    ~Prim(){
420      if(local_pred) delete _pred;
421      if(local_tree) delete _tree;
422      if(local_processed) delete _processed;
423      if(local_heap_cross_ref) delete _heap_cross_ref;
424      if(local_heap) delete _heap;
425    }
426
427    ///\brief Sets the cost map.
428
429    ///Sets the cost map.
430    ///\return <tt> (*this) </tt>
431    Prim &costMap(const CostMap &m){
432      cost = &m;
433      return *this;
434    }
435
436    ///\brief Sets the map storing the predecessor edges.
437
438    ///Sets the map storing the predecessor edges.
439    ///If you don't use this function before calling \ref run(),
440    ///it will allocate one. The destuctor deallocates this
441    ///automatically allocated map, of course.
442    ///\return <tt> (*this) </tt>
443    Prim &predMap(PredMap &m){
444      if(local_pred) {
445        delete _pred;
446        local_pred=false;
447      }
448      _pred = &m;
449      return *this;
450    }
451
452    ///\brief Sets the map storing the tree edges.
453
454    ///Sets the map storing the tree edges.
455    ///If you don't use this function before calling \ref run(),
456    ///it will allocate one. The destuctor deallocates this
457    ///automatically allocated map, of course.
458    ///By default this is a NullMap.
459    ///\return <tt> (*this) </tt>
460    Prim &treeMap(TreeMap &m){
461      if(local_tree) {
462        delete _tree;
463        local_tree=false;
464      }
465      _tree = &m;
466      return *this;
467    }
468
469    ///\brief Sets the heap and the cross reference used by algorithm.
470
471    ///Sets the heap and the cross reference used by algorithm.
472    ///If you don't use this function before calling \ref run(),
473    ///it will allocate one. The destuctor deallocates this
474    ///automatically allocated map, of course.
475    ///\return <tt> (*this) </tt>
476    Prim &heap(Heap& heap, HeapCrossRef &crossRef){
477      if(local_heap_cross_ref) {
478        delete _heap_cross_ref;
479        local_heap_cross_ref=false;
480      }
481      _heap_cross_ref = &crossRef;
482      if(local_heap) {
483        delete _heap;
484        local_heap=false;
485      }
486      _heap = &heap;
487      return *this;
488    }
489
490  public:
491    ///\name Execution control
492    ///The simplest way to execute the algorithm is to use
493    ///one of the member functions called \c run(...).
494    ///\n
495    ///If you need more control on the execution,
496    ///first you must call \ref init(), then you can add several source nodes
497    ///with \ref addSource().
498    ///Finally \ref start() will perform the actual path
499    ///computation.
500
501    ///@{
502
503    ///\brief Initializes the internal data structures.
504
505    ///Initializes the internal data structures.
506    ///
507    void init(){
508      create_maps();
509      _heap->clear();
510      for ( NodeIt u(*graph) ; u!=INVALID ; ++u ) {
511        _pred->set(u,INVALID);
512        _processed->set(u,false);
513        _heap_cross_ref->set(u,Heap::PRE_HEAP);
514      }
515    }
516   
517    ///\brief Adds a new source node.
518
519    ///Adds a new source node to the priority heap.
520    ///
521    ///It checks if the node has already been added to the heap and
522    ///it is pushed to the heap only if it was not in the heap.
523    void addSource(Node s){
524      if(_heap->state(s) != Heap::IN_HEAP) {
525        _heap->push(s,Value());
526      }
527    }
528    ///\brief Processes the next node in the priority heap
529
530    ///Processes the next node in the priority heap.
531    ///
532    ///\return The processed node.
533    ///
534    ///\warning The priority heap must not be empty!
535    Node processNextNode(){
536      Node v=_heap->top();
537      _heap->pop();
538      _processed->set(v,true);
539     
540      for(IncEdgeIt e(*graph,v); e!=INVALID; ++e) {
541        Node w=graph->oppositeNode(v,e);
542        switch(_heap->state(w)) {
543        case Heap::PRE_HEAP:
544          _heap->push(w,(*cost)[e]);
545          _pred->set(w,e);
546          break;
547        case Heap::IN_HEAP:
548          if ( (*cost)[e] < (*_heap)[w] ) {
549            _heap->decrease(w,(*cost)[e]);
550            _pred->set(w,e);
551          }
552          break;
553        case Heap::POST_HEAP:
554          break;
555        }
556      }
557      if ((*_pred)[v]!=INVALID)_tree->set((*_pred)[v],true);
558      return v;
559    }
560
561    ///\brief Next node to be processed.
562   
563    ///Next node to be processed.
564    ///
565    ///\return The next node to be processed or INVALID if the priority heap
566    /// is empty.
567    Node nextNode(){
568      return _heap->empty()?_heap->top():INVALID;
569    }
570 
571    ///\brief Returns \c false if there are nodes to be processed in the priority heap
572    ///
573    ///Returns \c false if there are nodes
574    ///to be processed in the priority heap
575    bool emptyQueue() { return _heap->empty(); }
576    ///\brief Returns the number of the nodes to be processed in the priority heap
577
578    ///Returns the number of the nodes to be processed in the priority heap
579    ///
580    int queueSize() { return _heap->size(); }
581   
582    ///\brief Executes the algorithm.
583
584    ///Executes the algorithm.
585    ///
586    ///\pre init() must be called and at least one node should be added
587    ///with addSource() before using this function.
588    ///
589    ///This method runs the %Prim algorithm from the node(s)
590    ///in order to compute the
591    ///minimum spanning tree.
592    ///
593    void start(){
594      while ( !_heap->empty() ) processNextNode();
595    }
596   
597    ///\brief Executes the algorithm until a condition is met.
598
599    ///Executes the algorithm until a condition is met.
600    ///
601    ///\pre init() must be called and at least one node should be added
602    ///with addSource() before using this function.
603    ///
604    ///\param nm must be a bool (or convertible) node map. The algorithm
605    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
606    template<class NodeBoolMap>
607    void start(const NodeBoolMap &nm){
608      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
609      if ( !_heap->empty() ) _processed->set(_heap->top(),true);
610    }
611   
612    ///\brief Runs %Prim algorithm.
613   
614    ///This method runs the %Prim algorithm
615    ///in order to compute the
616    ///minimum spanning tree (or minimum spanning forest).
617    ///The method also works on graphs that has more than one components.
618    ///In this case it computes the minimum spanning forest.
619    void run() {
620      init();
621      for(NodeIt it(*graph);it!=INVALID;++it){
622        if(!processed(it)){
623          addSource(it);
624          start();
625        }
626      }
627    }
628
629    ///\brief Runs %Prim algorithm from node \c s.
630   
631    ///This method runs the %Prim algorithm from node \c s
632    ///in order to
633    ///compute the
634    ///minimun spanning tree
635    ///
636    ///\note d.run(s) is just a shortcut of the following code.
637    ///\code
638    ///  d.init();
639    ///  d.addSource(s);
640    ///  d.start();
641    ///\endcode
642    ///\note If the graph has more than one components, the method
643    ///will compute the minimun spanning tree for only one component.
644    ///
645    ///See \ref run() if you want to compute the minimal spanning forest.
646    void run(Node s){
647      init();
648      addSource(s);
649      start();
650    }
651   
652    ///@}
653
654    ///\name Query Functions
655    ///The result of the %Prim algorithm can be obtained using these
656    ///functions.\n
657    ///Before the use of these functions,
658    ///either run() or start() must be called.
659   
660    ///@{
661
662    ///\brief Returns the 'previous edge' of the minimum spanning tree.
663
664    ///For a node \c v it returns the 'previous edge' of the minimum spanning tree,
665    ///i.e. it returns the edge from where \c v was reached. For a source node
666    ///or an unreachable node it is \ref INVALID.
667    ///The minimum spanning tree used here is equal to the minimum spanning tree used
668    ///in \ref predNode().  \pre \ref run() or \ref start() must be called before
669    ///using this function.
670    UEdge predEdge(Node v) const { return (*_pred)[v]; }
671
672    ///\brief Returns the 'previous node' of the minimum spanning tree.
673
674    ///For a node \c v it returns the 'previous node' of the minimum spanning tree,
675    ///i.e. it returns the node from where \c v was reached. For a source node
676    ///or an unreachable node it is \ref INVALID.
677    //The minimum spanning tree used here is equal to the minimum spanning
678    ///tree used in \ref predEdge().  \pre \ref run() or \ref start() must be called
679    ///before using this function.
680    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
681                                  graph->source((*_pred)[v]); }
682   
683    ///\brief Returns a reference to the NodeMap of the edges of the minimum spanning tree.
684
685    ///Returns a reference to the NodeMap of the edges of the
686    ///minimum spanning tree.
687    ///\pre \ref run() or \ref start() must be called before using this function.
688    const PredMap &predMap() const { return *_pred;}
689 
690    ///\brief Returns a reference to the tree edges map.
691
692    ///Returns a reference to the TreeEdgeMap of the edges of the
693    ///minimum spanning tree. The value of the map is \c true only if the edge is in
694    ///the minimum spanning tree.
695    ///\warning By default, the TreeEdgeMap is a NullMap.
696    ///
697    ///If it is not set before the execution of the algorithm, use the \ref
698    ///treeMap(TreeMap&) function (after the execution) to set an UEdgeMap with the
699    ///edges of the minimum spanning tree in O(n) time where n is the number of
700    ///nodes in the graph.
701    ///\pre \ref run() or \ref start() must be called before using this function.
702    const TreeMap &treeMap() const { return *_tree;}
703 
704    ///\brief Sets the tree edges map.
705
706    ///Sets the TreeMap of the edges of the minimum spanning tree.
707    ///The map values belonging to the edges of the minimum
708    ///spanning tree are set to \c tree_edge_value or \c true by default,
709    ///the other map values remain untouched.
710    ///
711    ///\pre \ref run() or \ref start() must be called before using this function.
712
713    template<class TreeMap>
714    void quickTreeEdges(
715        TreeMap& tree,
716        const typename TreeMap::Value& tree_edge_value=true) const {
717      for(NodeIt i(*graph);i!=INVALID;++i){
718        if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
719      }
720    }
721
722    ///\brief Sets the tree edges map.
723
724    ///Sets the TreeMap of the edges of the minimum spanning tree.
725    ///The map values belonging to the edges of the minimum
726    ///spanning tree are set to \c tree_edge_value or \c true by default while
727    ///the edge values not belonging to the minimum spanning tree are set to
728    ///\c tree_default_value or \c false by default.
729    ///
730    ///\pre \ref run() or \ref start() must be called before using this function.
731
732    template<class TreeMap>
733    void treeEdges(
734        TreeMap& tree,
735        const typename TreeMap::Value& tree_edge_value=true,
736        const typename TreeMap::Value& tree_default_value=false) const {
737      for(typename ItemSetTraits<UGraph,UEdge>::ItemIt i(*graph);i!=INVALID;++i)
738        tree.set(i,tree_default_value);
739      for(NodeIt i(*graph);i!=INVALID;++i){
740        if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
741      }
742    }
743
744    ///\brief Checks if a node is reachable from the starting node.
745
746    ///Returns \c true if \c v is reachable from the starting node.
747    ///\warning The source nodes are inditated as unreached.
748    ///\pre \ref run() or \ref start() must be called before using this function.
749    ///
750    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
751
752    ///\brief Checks if a node is processed.
753
754    ///Returns \c true if \c v is processed, i.e. \c v is already connencted to the
755    ///minimum spanning tree.
756    ///\pre \ref run() or \ref start() must be called before using this function.
757    ///
758    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
759   
760
761    ///\brief Checks if an edge is in the spanning tree or not.
762
763    ///Checks if an edge is in the spanning tree or not.
764    ///\param e is the edge that will be checked
765    ///\return \c true if e is in the spanning tree, \c false otherwise
766    bool tree(UEdge e){
767      return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e;
768    }
769    ///@}
770  };
771
772
773  /// \ingroup spantree
774  ///
775  /// \brief Function type interface for Prim algorithm.
776  ///
777  /// Function type interface for Prim algorithm.
778  /// \param graph the UGraph that the algorithm runs on
779  /// \param cost the CostMap of the edges
780  /// \retval tree the EdgeMap that contains whether an edge is in
781  /// the spanning tree or not
782  ///
783  ///\sa Prim
784  template<class Graph,class CostMap,class TreeMap>
785  void prim(const Graph& graph, const CostMap& cost,TreeMap& tree){
786    typename Prim<Graph,CostMap>::template DefTreeMap<TreeMap>::
787      Create prm(graph,cost);
788    prm.treeMap(tree);
789    prm.run();
790  }
791
792} //END OF NAMESPACE LEMON
793
794#endif
Note: See TracBrowser for help on using the repository browser.