Change the compilation flag at release make distcheck.
(This setting is probably indifferent, though.)
2 * lemon/prim.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
22 ///\brief Prim algorithm to compute minimum spanning tree.
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>
31 #include <lemon/concept/ugraph.h>
35 ///Default traits class of Prim class.
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.
44 ///The type of the map that stores the edge costs.
46 ///The type of the map that stores the edge costs.
47 ///It must meet the \ref concept::ReadMap "ReadMap" concept.
49 //The type of the cost of the edges.
50 typedef typename LM::Value Value;
51 /// The cross reference type used by heap.
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.
58 ///This function instantiates a \ref HeapCrossRef.
59 /// \param _graph is the graph, to which we would like to define the
61 static HeapCrossRef *createHeapCrossRef(const GR &_graph){
62 return new HeapCrossRef(_graph);
65 ///The heap type used by Prim algorithm.
67 ///The heap type used by Prim algorithm.
71 typedef BinHeap<typename UGraph::Node, typename LM::Value,
72 HeapCrossRef, std::less<Value> > Heap;
74 static Heap *createHeap(HeapCrossRef& _ref){
75 return new Heap(_ref);
78 ///\brief The type of the map that stores the last
79 ///edges of the minimum spanning tree.
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.
85 typedef typename UGraph::template NodeMap<typename GR::UEdge> PredMap;
86 ///Instantiates a PredMap.
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);
94 ///The type of the map that stores whether an edge is in the
95 ///spanning tree or not.
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.
103 ///This function instantiates a \ref TreeMap.
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();
111 ///The type of the map that stores whether a nodes is processed.
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.
119 ///This function instantiates a \ref ProcessedMap.
120 ///\param _graph is the graph, to which
121 ///we would like to define the \ref ProcessedMap
123 static ProcessedMap *createProcessedMap(const GR &_graph)
125 static ProcessedMap *createProcessedMap(const GR &)
128 return new ProcessedMap();
132 ///%Prim algorithm class to find a minimum spanning tree.
134 /// \ingroup spantree
135 ///This class provides an efficient implementation of %Prim algorithm.
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.
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.
144 ///The type of the cost is determined by the
145 ///\ref concept::ReadMap::Value "Value" of the cost map.
147 ///It is also possible to change the underlying priority heap.
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.
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.
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
168 ///\author Balazs Attila Mihaly
171 template <typename GR,
175 template <typename GR=ListUGraph,
176 typename LM=typename GR::template UEdgeMap<int>,
177 typename TR=PrimDefaultTraits<GR,LM> >
182 * \brief \ref Exception for uninitialized parameters.
184 * This error represents problems in the initialization
185 * of the parameters of the algorithms.
187 class UninitializedParameter : public lemon::UninitializedParameter {
189 virtual const char* exceptionName() const {
190 return "lemon::Prim::UninitializedParameter";
195 ///The type of the underlying graph.
196 typedef typename TR::UGraph UGraph;
198 typedef typename UGraph::Node Node;
200 typedef typename UGraph::NodeIt NodeIt;
202 typedef typename UGraph::UEdge UEdge;
204 typedef typename UGraph::IncEdgeIt IncEdgeIt;
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;
222 /// Pointer to the underlying graph.
224 /// Pointer to the cost map
226 ///Pointer to the map of predecessors edges.
228 ///Indicates if \ref _pred is locally allocated (\c true) or not.
230 ///Pointer to the map of tree edges.
232 ///Indicates if \ref _tree is locally allocated (\c true) or not.
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.
244 ///Indicates if \ref _heap is locally allocated (\c true) or not.
247 ///Creates the maps if necessary.
251 _pred = Traits::createPredMap(*graph);
255 _tree = Traits::createTreeMap(*graph);
258 local_processed = true;
259 _processed = Traits::createProcessedMap(*graph);
261 if (!_heap_cross_ref) {
262 local_heap_cross_ref = true;
263 _heap_cross_ref = Traits::createHeapCrossRef(*graph);
267 _heap = Traits::createHeap(*_heap_cross_ref);
275 ///\name Named template parameters
280 struct DefPredMapTraits : public Traits {
282 static PredMap *createPredMap(const UGraph &_graph){
283 throw UninitializedParameter();
286 ///\ref named-templ-param "Named parameter" for setting PredMap type
288 ///\ref named-templ-param "Named parameter" for setting PredMap type
292 : public Prim< UGraph, CostMap, DefPredMapTraits<T> > {
293 typedef Prim< UGraph, CostMap, DefPredMapTraits<T> > Create;
297 struct DefProcessedMapTraits : public Traits {
298 typedef T ProcessedMap;
299 static ProcessedMap *createProcessedMap(const UGraph &_graph){
300 throw UninitializedParameter();
303 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
305 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
308 struct DefProcessedMap
309 : public Prim< UGraph, CostMap, DefProcessedMapTraits<T> > {
310 typedef Prim< UGraph, CostMap, DefProcessedMapTraits<T> > Create;
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);
321 template <class H, class CR>
322 struct DefHeapTraits : public Traits {
323 typedef CR HeapCrossRef;
325 static HeapCrossRef *createHeapCrossRef(const UGraph &) {
326 throw UninitializedParameter();
328 static Heap *createHeap(HeapCrossRef &){
329 return UninitializedParameter();
332 ///\ref named-templ-param "Named parameter" for setting heap and cross
335 ///\ref named-templ-param "Named parameter" for setting heap and cross
338 template <class H, class CR = typename UGraph::template NodeMap<int> >
340 : public Prim< UGraph, CostMap, DefHeapTraits<H, CR> > {
341 typedef Prim< UGraph, CostMap, DefHeapTraits<H, CR> > Create;
344 template <class H, class CR>
345 struct DefStandardHeapTraits : public Traits {
346 typedef CR HeapCrossRef;
348 static HeapCrossRef *createHeapCrossRef(const UGraph &_graph) {
349 return new HeapCrossRef(_graph);
351 static Heap *createHeap(HeapCrossRef &ref){
352 return new Heap(ref);
355 ///\ref named-templ-param "Named parameter" for setting heap and cross
356 ///reference type with automatic allocation
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> >
370 struct DefTreeMapTraits : public Traits {
372 static TreeMap *createTreeMap(const UGraph &) {
373 throw UninitializedParameter();
376 ///\ref named-templ-param "Named parameter" for setting TreeMap
378 ///\ref named-templ-param "Named parameter" for setting TreeMap
382 : public Prim< UGraph, CostMap, DefTreeMapTraits<TM> > {
383 typedef Prim< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
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);
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)
414 checkConcept<concept::UGraph, UGraph>();
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;
426 ///\brief Sets the cost map.
428 ///Sets the cost map.
429 ///\return <tt> (*this) </tt>
430 Prim &costMap(const CostMap &m){
435 ///\brief Sets the map storing the predecessor edges.
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){
451 ///\brief Sets the map storing the tree edges.
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){
468 ///\brief Sets the heap and the cross reference used by algorithm.
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;
480 _heap_cross_ref = &crossRef;
490 ///\name Execution control
491 ///The simplest way to execute the algorithm is to use
492 ///one of the member functions called \c run(...).
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
502 ///\brief Initializes the internal data structures.
504 ///Initializes the internal data structures.
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);
516 ///\brief Adds a new source node.
518 ///Adds a new source node to the priority heap.
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());
527 ///\brief Processes the next node in the priority heap
529 ///Processes the next node in the priority heap.
531 ///\return The processed node.
533 ///\warning The priority heap must not be empty!
534 Node processNextNode(){
537 _processed->set(v,true);
539 for(IncEdgeIt e(*graph,v); e!=INVALID; ++e) {
540 Node w=graph->oppositeNode(v,e);
541 switch(_heap->state(w)) {
543 _heap->push(w,(*cost)[e]);
547 if ( (*cost)[e] < (*_heap)[w] ) {
548 _heap->decrease(w,(*cost)[e]);
552 case Heap::POST_HEAP:
556 if ((*_pred)[v]!=INVALID)_tree->set((*_pred)[v],true);
560 ///\brief Next node to be processed.
562 ///Next node to be processed.
564 ///\return The next node to be processed or INVALID if the priority heap
567 return _heap->empty()?_heap->top():INVALID;
570 ///\brief Returns \c false if there are nodes to be processed in the priority heap
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
577 ///Returns the number of the nodes to be processed in the priority heap
579 int queueSize() { return _heap->size(); }
581 ///\brief Executes the algorithm.
583 ///Executes the algorithm.
585 ///\pre init() must be called and at least one node should be added
586 ///with addSource() before using this function.
588 ///This method runs the %Prim algorithm from the node(s)
589 ///in order to compute the
590 ///minimum spanning tree.
593 while ( !_heap->empty() ) processNextNode();
596 ///\brief Executes the algorithm until a condition is met.
598 ///Executes the algorithm until a condition is met.
600 ///\pre init() must be called and at least one node should be added
601 ///with addSource() before using this function.
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);
611 ///\brief Runs %Prim algorithm.
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.
620 for(NodeIt it(*graph);it!=INVALID;++it){
628 ///\brief Runs %Prim algorithm from node \c s.
630 ///This method runs the %Prim algorithm from node \c s
633 ///minimun spanning tree
635 ///\note d.run(s) is just a shortcut of the following code.
641 ///\note If the graph has more than one components, the method
642 ///will compute the minimun spanning tree for only one component.
644 ///See \ref run() if you want to compute the minimal spanning forest.
653 ///\name Query Functions
654 ///The result of the %Prim algorithm can be obtained using these
656 ///Before the use of these functions,
657 ///either run() or start() must be called.
661 ///\brief Returns the 'previous edge' of the minimum spanning tree.
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]; }
671 ///\brief Returns the 'previous node' of the minimum spanning tree.
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]); }
682 ///\brief Returns a reference to the NodeMap of the edges of the minimum spanning tree.
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;}
689 ///\brief Returns a reference to the tree edges map.
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.
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;}
703 ///\brief Sets the tree edges map.
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.
710 ///\pre \ref run() or \ref start() must be called before using this function.
712 template<class TreeMap>
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);
721 ///\brief Sets the tree edges map.
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.
729 ///\pre \ref run() or \ref start() must be called before using this function.
731 template<class TreeMap>
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);
743 ///\brief Checks if a node is reachable from the starting node.
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.
749 bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
751 ///\brief Checks if a node is processed.
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.
757 bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
760 ///\brief Checks if an edge is in the spanning tree or not.
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
766 return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e;
772 /// \ingroup spantree
774 /// \brief Function type interface for Prim algorithm.
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
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);
791 } //END OF NAMESPACE LEMON