COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/prim.h @ 1953:d4f411003580

Last change on this file since 1953:d4f411003580 was 1953:d4f411003580, checked in by Alpar Juttner, 14 years ago

Polish the doc.

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