COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/prim.h @ 1979:c2992fd74dad

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

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

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