Fix warning when compiling with -Wall.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
24 ///\brief Prim algorithm to compute minimum spanning tree.
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>
33 #include <lemon/concepts/ugraph.h>
37 ///Default traits class of Prim class.
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.
46 ///The type of the map that stores the edge costs.
48 ///The type of the map that stores the edge costs.
49 ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
51 //The type of the cost of the edges.
52 typedef typename CM::Value Value;
53 /// The cross reference type used by heap.
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.
60 ///This function instantiates a \ref HeapCrossRef.
61 /// \param _graph is the graph, to which we would like to define the
63 static HeapCrossRef *createHeapCrossRef(const GR &_graph){
64 return new HeapCrossRef(_graph);
67 ///The heap type used by Prim algorithm.
69 ///The heap type used by Prim algorithm.
73 typedef BinHeap<typename CM::Value,
74 HeapCrossRef, std::less<Value> > Heap;
76 static Heap *createHeap(HeapCrossRef& _ref){
77 return new Heap(_ref);
80 ///\brief The type of the map that stores the last
81 ///edges of the minimum spanning tree.
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.
87 typedef typename UGraph::template NodeMap<typename GR::UEdge> PredMap;
88 ///Instantiates a PredMap.
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);
96 ///The type of the map that stores whether an edge is in the
97 ///spanning tree or not.
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.
105 ///This function instantiates a \ref TreeMap.
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();
113 ///The type of the map that stores whether a nodes is processed.
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.
121 ///This function instantiates a \ref ProcessedMap.
122 ///\param _graph is the graph, to which
123 ///we would like to define the \ref ProcessedMap
125 static ProcessedMap *createProcessedMap(const GR &_graph)
127 static ProcessedMap *createProcessedMap(const GR &)
130 return new ProcessedMap();
134 ///%Prim algorithm class to find a minimum spanning tree.
136 /// \ingroup spantree
137 ///This class provides an efficient implementation of %Prim algorithm.
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.
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.
146 ///The type of the cost is determined by the
147 ///\ref concepts::ReadMap::Value "Value" of the cost map.
149 ///It is also possible to change the underlying priority heap.
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.
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.
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
170 ///\author Balazs Attila Mihaly
173 template <typename GR,
177 template <typename GR=ListUGraph,
178 typename CM=typename GR::template UEdgeMap<int>,
179 typename TR=PrimDefaultTraits<GR,CM> >
184 /// \brief \ref Exception for uninitialized parameters.
186 /// This error represents problems in the initialization
187 /// of the parameters of the algorithms.
188 class UninitializedParameter : public lemon::UninitializedParameter {
190 virtual const char* what() const throw() {
191 return "lemon::Prim::UninitializedParameter";
196 ///The type of the underlying graph.
197 typedef typename TR::UGraph UGraph;
199 typedef typename UGraph::Node Node;
201 typedef typename UGraph::NodeIt NodeIt;
203 typedef typename UGraph::UEdge UEdge;
205 typedef typename UGraph::IncEdgeIt IncEdgeIt;
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;
223 /// Pointer to the underlying graph.
225 /// Pointer to the cost map
227 ///Pointer to the map of predecessors edges.
229 ///Indicates if \ref _pred is locally allocated (\c true) or not.
231 ///Pointer to the map of tree edges.
233 ///Indicates if \ref _tree is locally allocated (\c true) or not.
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.
245 ///Indicates if \ref _heap is locally allocated (\c true) or not.
248 ///Creates the maps if necessary.
252 _pred = Traits::createPredMap(*graph);
256 _tree = Traits::createTreeMap(*graph);
259 local_processed = true;
260 _processed = Traits::createProcessedMap(*graph);
262 if (!_heap_cross_ref) {
263 local_heap_cross_ref = true;
264 _heap_cross_ref = Traits::createHeapCrossRef(*graph);
268 _heap = Traits::createHeap(*_heap_cross_ref);
276 ///\name Named template parameters
281 struct DefPredMapTraits : public Traits {
283 static PredMap *createPredMap(const UGraph &_graph){
284 throw UninitializedParameter();
287 ///\brief \ref named-templ-param "Named parameter" for setting PredMap type
289 ///\ref named-templ-param "Named parameter" for setting PredMap type
293 : public Prim< UGraph, CostMap, DefPredMapTraits<T> > {
294 typedef Prim< UGraph, CostMap, DefPredMapTraits<T> > Create;
298 struct DefProcessedMapTraits : public Traits {
299 typedef T ProcessedMap;
300 static ProcessedMap *createProcessedMap(const UGraph &_graph){
301 throw UninitializedParameter();
304 ///\brief \ref named-templ-param "Named parameter" for setting
307 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
310 struct DefProcessedMap
311 : public Prim< UGraph, CostMap, DefProcessedMapTraits<T> > {
312 typedef Prim< UGraph, CostMap, DefProcessedMapTraits<T> > Create;
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);
323 template <class H, class CR>
324 struct DefHeapTraits : public Traits {
325 typedef CR HeapCrossRef;
327 static HeapCrossRef *createHeapCrossRef(const UGraph &) {
328 throw UninitializedParameter();
330 static Heap *createHeap(HeapCrossRef &){
331 return UninitializedParameter();
334 ///\brief \ref named-templ-param "Named parameter" for setting
335 ///heap and cross reference type
337 ///\ref named-templ-param "Named parameter" for setting heap and cross
340 template <class H, class CR = typename UGraph::template NodeMap<int> >
342 : public Prim< UGraph, CostMap, DefHeapTraits<H, CR> > {
343 typedef Prim< UGraph, CostMap, DefHeapTraits<H, CR> > Create;
346 template <class H, class CR>
347 struct DefStandardHeapTraits : public Traits {
348 typedef CR HeapCrossRef;
350 static HeapCrossRef *createHeapCrossRef(const UGraph &_graph) {
351 return new HeapCrossRef(_graph);
353 static Heap *createHeap(HeapCrossRef &ref){
354 return new Heap(ref);
357 ///\brief \ref named-templ-param "Named parameter" for setting
358 ///heap and cross reference type with automatic allocation
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> >
372 struct DefTreeMapTraits : public Traits {
374 static TreeMap *createTreeMap(const UGraph &) {
375 throw UninitializedParameter();
378 ///\brief \ref named-templ-param "Named parameter" for setting
381 ///\ref named-templ-param "Named parameter" for setting TreeMap
385 : public Prim< UGraph, CostMap, DefTreeMapTraits<TM> > {
386 typedef Prim< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
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);
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)
417 checkConcept<concepts::UGraph, UGraph>();
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;
429 ///\brief Sets the cost map.
431 ///Sets the cost map.
432 ///\return <tt> (*this) </tt>
433 Prim &costMap(const CostMap &m){
438 ///\brief Sets the map storing the predecessor edges.
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){
454 ///\brief Sets the map storing the tree edges.
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){
471 ///\brief Sets the heap and the cross reference used by algorithm.
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;
483 _heap_cross_ref = &crossRef;
493 ///\name Execution control
494 ///The simplest way to execute the algorithm is to use
495 ///one of the member functions called \c run(...).
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
505 ///\brief Initializes the internal data structures.
507 ///Initializes the internal data structures.
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);
519 ///\brief Adds a new source node.
521 ///Adds a new source node to the priority heap.
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());
530 ///\brief Processes the next node in the priority heap
532 ///Processes the next node in the priority heap.
534 ///\return The processed node.
536 ///\warning The priority heap must not be empty!
537 Node processNextNode(){
540 _processed->set(v,true);
542 for(IncEdgeIt e(*graph,v); e!=INVALID; ++e) {
543 Node w=graph->oppositeNode(v,e);
544 switch(_heap->state(w)) {
546 _heap->push(w,(*cost)[e]);
550 if ( (*cost)[e] < (*_heap)[w] ) {
551 _heap->decrease(w,(*cost)[e]);
555 case Heap::POST_HEAP:
559 if ((*_pred)[v]!=INVALID)_tree->set((*_pred)[v],true);
563 ///\brief Next node to be processed.
565 ///Next node to be processed.
567 ///\return The next node to be processed or INVALID if the priority heap
570 return _heap->empty()?_heap->top():INVALID;
573 ///\brief Returns \c false if there are nodes to be processed in
576 ///Returns \c false if there are nodes
577 ///to be processed in the priority heap
578 bool emptyQueue() { return _heap->empty(); }
580 ///\brief Returns the number of the nodes to be processed in the
583 ///Returns the number of the nodes to be processed in the priority heap
585 int queueSize() { return _heap->size(); }
587 ///\brief Executes the algorithm.
589 ///Executes the algorithm.
591 ///\pre init() must be called and at least one node should be added
592 ///with addSource() before using this function.
594 ///This method runs the %Prim algorithm from the node(s)
595 ///in order to compute the
596 ///minimum spanning tree.
599 while ( !_heap->empty() ) processNextNode();
602 ///\brief Executes the algorithm until a condition is met.
604 ///Executes the algorithm until a condition is met.
606 ///\pre init() must be called and at least one node should be added
607 ///with addSource() before using this function.
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);
617 ///\brief Runs %Prim algorithm.
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.
626 for(NodeIt it(*graph);it!=INVALID;++it){
634 ///\brief Runs %Prim algorithm from node \c s.
636 ///This method runs the %Prim algorithm from node \c s
639 ///minimun spanning tree
641 ///\note p.run(s) is just a shortcut of the following code.
647 ///\note If the graph has more than one components, the method
648 ///will compute the minimun spanning tree for only one component.
650 ///See \ref run() if you want to compute the minimal spanning forest.
659 ///\name Query Functions
660 ///The result of the %Prim algorithm can be obtained using these
662 ///Before the use of these functions,
663 ///either run() or start() must be called.
667 ///\brief Returns the 'previous edge' of the minimum spanning tree.
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
676 UEdge predEdge(Node v) const { return (*_pred)[v]; }
678 ///\brief Returns the 'previous node' of the minimum spanning
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
688 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
689 graph->source((*_pred)[v]); }
691 ///\brief Returns a reference to the NodeMap of the edges of the
692 ///minimum spanning tree.
694 ///Returns a reference to the NodeMap of the edges of the minimum
696 ///\pre \ref run() or \ref start() must be called before using
698 const PredMap &predMap() const { return *_pred;}
700 ///\brief Returns a reference to the tree edges map.
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.
706 ///\warning By default, the TreeEdgeMap is a NullMap.
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
714 const TreeMap &treeMap() const { return *_tree;}
716 ///\brief Sets the tree edges map.
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.
723 ///\pre \ref run() or \ref start() must be called before using
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);
733 ///\brief Sets the tree edges map.
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.
741 ///\pre \ref run() or \ref start() must be called before using
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) {
749 for(NodeIt i(*graph); i != INVALID; ++i){
750 if((*_pred)[i] != INVALID) tree.set((*_pred)[i],true);
754 ///\brief Checks if a node is reachable from the starting node.
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
761 bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
763 ///\brief Checks if a node is processed.
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; }
771 ///\brief Checks if an edge is in the spanning tree or not.
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
777 return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e;
780 ///\brief Returns the value of the total cost of the spanning tree.
782 /// Returns the value of the total cost of the spanning tree.
783 Value treeValue() const {
785 for(NodeIt i(*graph); i!= INVALID; ++i){
786 if ((*_pred)[i] != INVALID) value += (*cost)[(*_pred)[i]];
794 /// \ingroup spantree
796 /// \brief Function type interface for Prim algorithm.
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
806 template<class Graph,class CostMap,class TreeMap>
807 typename CostMap::Value prim(const Graph& graph,
810 typename Prim<Graph,CostMap>::
811 template DefTreeMap<TreeMap>::
812 Create prm(graph,cost);
815 return prm.treeValue();
818 /// \ingroup spantree
820 /// \brief Function type interface for Prim algorithm.
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
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);
835 return prm.treeValue();
838 } //END OF NAMESPACE LEMON