COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/prim.h @ 1922:1ee37068316b

Last change on this file since 1922:1ee37068316b was 1912:d9205a711324, checked in by Balazs Dezso, 18 years ago

Algorithms by szakall

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