COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/prim.h

Last change on this file was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 26.5 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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/concepts/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 concepts::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 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 concepts::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 concepts::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 concepts::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 concepts::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  ///concepts::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* what() const throw() {
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    ///\brief \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    ///\brief \ref named-templ-param "Named parameter" for setting
305    ///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    ///\brief \ref named-templ-param "Named parameter" for setting
335    ///heap and cross 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    ///\brief \ref named-templ-param "Named parameter" for setting
358    ///heap and cross 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    ///\brief \ref named-templ-param "Named parameter" for setting
379    ///TreeMap
380    ///
381    ///\ref named-templ-param "Named parameter" for setting TreeMap
382    ///
383    template <class TM>
384    struct DefTreeMap
385      : public Prim< UGraph, CostMap, DefTreeMapTraits<TM> > {
386      typedef Prim< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
387    };   
388
389    struct DefGraphTreeMapTraits : public Traits {
390      typedef typename UGraph::template NodeMap<bool> TreeMap;
391      static TreeMap *createTreeMap(const UGraph &_graph){
392        return new TreeMap(_graph);
393      }
394    };
395
396    ///@}
397
398
399  protected:
400
401    Prim() {}
402
403  public:     
404   
405    ///Constructor.
406    ///
407    ///\param _graph the graph the algorithm will run on.
408    ///\param _cost the cost map used by the algorithm.
409    Prim(const UGraph& _graph, const CostMap& _cost) :
410      graph(&_graph), cost(&_cost),
411      _pred(0), local_pred(false),
412      _tree(0), local_tree(false),
413      _processed(0), local_processed(false),
414      _heap_cross_ref(0), local_heap_cross_ref(false),
415      _heap(0), local_heap(false)
416    {
417      checkConcept<concepts::UGraph, UGraph>();
418    }
419   
420    ///Destructor.
421    ~Prim(){
422      if(local_pred) delete _pred;
423      if(local_tree) delete _tree;
424      if(local_processed) delete _processed;
425      if(local_heap_cross_ref) delete _heap_cross_ref;
426      if(local_heap) delete _heap;
427    }
428
429    ///\brief Sets the cost map.
430    ///
431    ///Sets the cost map.
432    ///\return <tt> (*this) </tt>
433    Prim &costMap(const CostMap &m){
434      cost = &m;
435      return *this;
436    }
437
438    ///\brief Sets the map storing the predecessor edges.
439    ///
440    ///Sets the map storing the predecessor edges.
441    ///If you don't use this function before calling \ref run(),
442    ///it will allocate one. The destuctor deallocates this
443    ///automatically allocated map, of course.
444    ///\return <tt> (*this) </tt>
445    Prim &predMap(PredMap &m){
446      if(local_pred) {
447        delete _pred;
448        local_pred=false;
449      }
450      _pred = &m;
451      return *this;
452    }
453
454    ///\brief Sets the map storing the tree edges.
455    ///
456    ///Sets the map storing the tree edges.
457    ///If you don't use this function before calling \ref run(),
458    ///it will allocate one. The destuctor deallocates this
459    ///automatically allocated map, of course.
460    ///By default this is a NullMap.
461    ///\return <tt> (*this) </tt>
462    Prim &treeMap(TreeMap &m){
463      if(local_tree) {
464        delete _tree;
465        local_tree=false;
466      }
467      _tree = &m;
468      return *this;
469    }
470
471    ///\brief Sets the heap and the cross reference used by algorithm.
472    ///
473    ///Sets the heap and the cross reference used by algorithm.
474    ///If you don't use this function before calling \ref run(),
475    ///it will allocate one. The destuctor deallocates this
476    ///automatically allocated map, of course.
477    ///\return <tt> (*this) </tt>
478    Prim &heap(Heap& heap, HeapCrossRef &crossRef){
479      if(local_heap_cross_ref) {
480        delete _heap_cross_ref;
481        local_heap_cross_ref=false;
482      }
483      _heap_cross_ref = &crossRef;
484      if(local_heap) {
485        delete _heap;
486        local_heap=false;
487      }
488      _heap = &heap;
489      return *this;
490    }
491
492  public:
493    ///\name Execution control
494    ///The simplest way to execute the algorithm is to use
495    ///one of the member functions called \c run(...).
496    ///\n
497    ///If you need more control on the execution,
498    ///first you must call \ref init(), then you can add several source nodes
499    ///with \ref addSource().
500    ///Finally \ref start() will perform the actual path
501    ///computation.
502
503    ///@{
504
505    ///\brief Initializes the internal data structures.
506    ///
507    ///Initializes the internal data structures.
508    ///
509    void init(){
510      create_maps();
511      _heap->clear();
512      for ( NodeIt u(*graph) ; u!=INVALID ; ++u ) {
513        _pred->set(u,INVALID);
514        _processed->set(u,false);
515        _heap_cross_ref->set(u,Heap::PRE_HEAP);
516      }
517    }
518   
519    ///\brief Adds a new source node.
520    ///
521    ///Adds a new source node to the priority heap.
522    ///
523    ///It checks if the node has already been added to the heap and
524    ///it is pushed to the heap only if it was not in the heap.
525    void addSource(Node s){
526      if(_heap->state(s) != Heap::IN_HEAP) {
527        _heap->push(s,Value());
528      }
529    }
530    ///\brief Processes the next node in the priority heap
531    ///
532    ///Processes the next node in the priority heap.
533    ///
534    ///\return The processed node.
535    ///
536    ///\warning The priority heap must not be empty!
537    Node processNextNode(){
538      Node v=_heap->top();
539      _heap->pop();
540      _processed->set(v,true);
541     
542      for(IncEdgeIt e(*graph,v); e!=INVALID; ++e) {
543        Node w=graph->oppositeNode(v,e);
544        switch(_heap->state(w)) {
545        case Heap::PRE_HEAP:
546          _heap->push(w,(*cost)[e]);
547          _pred->set(w,e);
548          break;
549        case Heap::IN_HEAP:
550          if ( (*cost)[e] < (*_heap)[w] ) {
551            _heap->decrease(w,(*cost)[e]);
552            _pred->set(w,e);
553          }
554          break;
555        case Heap::POST_HEAP:
556          break;
557        }
558      }
559      if ((*_pred)[v]!=INVALID)_tree->set((*_pred)[v],true);
560      return v;
561    }
562
563    ///\brief Next node to be processed.
564    ///
565    ///Next node to be processed.
566    ///
567    ///\return The next node to be processed or INVALID if the priority heap
568    /// is empty.
569    Node nextNode(){
570      return _heap->empty()?_heap->top():INVALID;
571    }
572 
573    ///\brief Returns \c false if there are nodes to be processed in
574    ///the priority heap
575    ///
576    ///Returns \c false if there are nodes
577    ///to be processed in the priority heap
578    bool emptyQueue() { return _heap->empty(); }
579
580    ///\brief Returns the number of the nodes to be processed in the
581    ///priority heap
582    ///
583    ///Returns the number of the nodes to be processed in the priority heap
584    ///
585    int queueSize() { return _heap->size(); }
586   
587    ///\brief Executes the algorithm.
588    ///
589    ///Executes the algorithm.
590    ///
591    ///\pre init() must be called and at least one node should be added
592    ///with addSource() before using this function.
593    ///
594    ///This method runs the %Prim algorithm from the node(s)
595    ///in order to compute the
596    ///minimum spanning tree.
597    ///
598    void start(){
599      while ( !_heap->empty() ) processNextNode();
600    }
601   
602    ///\brief Executes the algorithm until a condition is met.
603    ///
604    ///Executes the algorithm until a condition is met.
605    ///
606    ///\pre init() must be called and at least one node should be added
607    ///with addSource() before using this function.
608    ///
609    ///\param nm must be a bool (or convertible) node map. The algorithm
610    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
611    template<class NodeBoolMap>
612    void start(const NodeBoolMap &nm){
613      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
614      if ( !_heap->empty() ) _processed->set(_heap->top(),true);
615    }
616   
617    ///\brief Runs %Prim algorithm.
618    ///
619    ///This method runs the %Prim algorithm
620    ///in order to compute the
621    ///minimum spanning tree (or minimum spanning forest).
622    ///The method also works on graphs that has more than one components.
623    ///In this case it computes the minimum spanning forest.
624    void run() {
625      init();
626      for(NodeIt it(*graph);it!=INVALID;++it){
627        if(!processed(it)){
628          addSource(it);
629          start();
630        }
631      }
632    }
633
634    ///\brief Runs %Prim algorithm from node \c s.
635    ///
636    ///This method runs the %Prim algorithm from node \c s
637    ///in order to
638    ///compute the
639    ///minimun spanning tree
640    ///
641    ///\note p.run(s) is just a shortcut of the following code.
642    ///\code
643    ///  p.init();
644    ///  p.addSource(s);
645    ///  p.start();
646    ///\endcode
647    ///\note If the graph has more than one components, the method
648    ///will compute the minimun spanning tree for only one component.
649    ///
650    ///See \ref run() if you want to compute the minimal spanning forest.
651    void run(Node s){
652      init();
653      addSource(s);
654      start();
655    }
656   
657    ///@}
658
659    ///\name Query Functions
660    ///The result of the %Prim algorithm can be obtained using these
661    ///functions.\n
662    ///Before the use of these functions,
663    ///either run() or start() must be called.
664   
665    ///@{
666
667    ///\brief Returns the 'previous edge' of the minimum spanning tree.
668
669    ///For a node \c v it returns the 'previous edge' of the minimum
670    ///spanning tree, i.e. it returns the edge from where \c v was
671    ///reached. For a source node or an unreachable node it is \ref
672    ///INVALID.  The minimum spanning tree used here is equal to the
673    ///minimum spanning tree used in \ref predNode(). 
674    ///\pre \ref run() or \ref start() must be called before using
675    ///this function.
676    UEdge predEdge(Node v) const { return (*_pred)[v]; }
677
678    ///\brief Returns the 'previous node' of the minimum spanning
679    ///tree.
680    ///
681    ///For a node \c v it returns the 'previous node' of the minimum
682    ///spanning tree, i.e. it returns the node from where \c v was
683    ///reached. For a source node or an unreachable node it is \ref
684    ///INVALID.  //The minimum spanning tree used here is equal to the
685    ///minimum spanning tree used in \ref predEdge(). 
686    ///\pre \ref run() or \ref start() must be called before using
687    ///this function.
688    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
689                                  graph->source((*_pred)[v]); }
690   
691    ///\brief Returns a reference to the NodeMap of the edges of the
692    ///minimum spanning tree.
693    ///
694    ///Returns a reference to the NodeMap of the edges of the minimum
695    ///spanning tree.
696    ///\pre \ref run() or \ref start() must be called before using
697    ///this function.
698    const PredMap &predMap() const { return *_pred;}
699 
700    ///\brief Returns a reference to the tree edges map.
701
702    ///Returns a reference to the TreeEdgeMap of the edges of the
703    ///minimum spanning tree. The value of the map is \c true only if
704    ///the edge is in the minimum spanning tree.
705    ///
706    ///\warning By default, the TreeEdgeMap is a NullMap.
707    ///
708    ///If it is not set before the execution of the algorithm, use the
709    ///\ref treeMap(TreeMap&) function (after the execution) to set an
710    ///UEdgeMap with the edges of the minimum spanning tree in O(n)
711    ///time where n is the number of nodes in the graph.
712    ///\pre \ref run() or \ref start() must be called before using
713    ///this function.
714    const TreeMap &treeMap() const { return *_tree;}
715 
716    ///\brief Sets the tree edges map.
717    ///
718    ///Sets the TreeMap of the edges of the minimum spanning tree.
719    ///The map values belonging to the edges of the minimum
720    ///spanning tree are set to \c tree_edge_value or \c true by default,
721    ///the other map values remain untouched.
722    ///
723    ///\pre \ref run() or \ref start() must be called before using
724    ///this function.
725
726    template<class TreeMap>
727    void quickTreeEdges(TreeMap& tree) const {
728      for(NodeIt i(*graph);i!=INVALID;++i){
729        if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],true);
730      }
731    }
732
733    ///\brief Sets the tree edges map.
734    ///
735    ///Sets the TreeMap of the edges of the minimum spanning tree.
736    ///The map values belonging to the edges of the minimum
737    ///spanning tree are set to \c tree_edge_value or \c true by default while
738    ///the edge values not belonging to the minimum spanning tree are set to
739    ///\c tree_default_value or \c false by default.
740    ///
741    ///\pre \ref run() or \ref start() must be called before using
742    ///this function.
743    template <class TreeMap>
744    void treeEdges(TreeMap& tree) const {
745      typedef typename ItemSetTraits<UGraph,UEdge>::ItemIt TreeMapIt;
746      for(TreeMapIt i(*graph); i != INVALID; ++i) {
747        tree.set(i,false);
748      }
749      for(NodeIt i(*graph); i != INVALID; ++i){
750        if((*_pred)[i] != INVALID) tree.set((*_pred)[i],true);
751      }
752    }
753
754    ///\brief Checks if a node is reachable from the starting node.
755    ///
756    ///Returns \c true if \c v is reachable from the starting node.
757    ///\warning The source nodes are inditated as unreached.
758    ///\pre \ref run() or \ref start() must be called before using
759    ///this function.
760    ///
761    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
762
763    ///\brief Checks if a node is processed.
764    ///
765    ///Returns \c true if \c v is processed, i.e. \c v is already
766    ///connencted to the minimum spanning tree.  \pre \ref run() or
767    ///\ref start() must be called before using this function.
768    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
769   
770
771    ///\brief Checks if an edge is in the spanning tree or not.
772    ///
773    ///Checks if an edge is in the spanning tree or not.
774    ///\param e is the edge that will be checked
775    ///\return \c true if e is in the spanning tree, \c false otherwise
776    bool tree(UEdge e){
777      return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e;
778    }
779
780    ///\brief Returns the value of the total cost of the spanning tree.
781    ///
782    /// Returns the value of the total cost of the spanning tree.
783    Value treeValue() const {
784      Value value = 0;
785      for(NodeIt i(*graph); i!= INVALID; ++i){
786        if ((*_pred)[i] != INVALID) value += (*cost)[(*_pred)[i]];
787      }
788      return value;
789    }
790    ///@}
791  };
792
793
794  /// \ingroup spantree
795  ///
796  /// \brief Function type interface for Prim algorithm.
797  ///
798  /// Function type interface for Prim algorithm.
799  /// \param graph the UGraph that the algorithm runs on
800  /// \param cost the CostMap of the edges
801  /// \retval tree the EdgeMap that contains whether an edge is in
802  /// the spanning tree or not
803  /// \return The total cost of the spanning tree
804  ///
805  ///\sa Prim
806  template<class Graph,class CostMap,class TreeMap>
807  typename CostMap::Value prim(const Graph& graph,
808                               const CostMap& cost,
809                               TreeMap& tree){
810    typename Prim<Graph,CostMap>::
811      template DefTreeMap<TreeMap>::
812      Create prm(graph,cost);
813    prm.treeMap(tree);
814    prm.run();
815    return prm.treeValue();
816  }
817
818  /// \ingroup spantree
819  ///
820  /// \brief Function type interface for Prim algorithm.
821  ///
822  /// Function type interface for Prim algorithm.
823  /// \param graph the UGraph that the algorithm runs on
824  /// \param cost the CostMap of the edges
825  /// the spanning tree or not
826  /// \return The total cost of the spanning tree
827  ///
828  ///\sa Prim
829  template<class Graph,class CostMap,class TreeMap>
830  typename CostMap::Value prim(const Graph& graph,
831                               const CostMap& cost){
832    typename Prim<Graph,CostMap>::
833      Create prm(graph,cost);
834    prm.run();
835    return prm.treeValue();
836  }
837
838} //END OF NAMESPACE LEMON
839
840#endif
Note: See TracBrowser for help on using the repository browser.