vmap.h: Enables one to create maps with a virtual base class.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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/invalid.h>
29 #include <lemon/error.h>
30 #include <lemon/maps.h>
31 #include <lemon/traits.h>
33 #include <lemon/concept/ugraph.h>
37 ///Default traits class of Prim class.
39 ///Default traits class of Prim class.
40 ///\param GR Graph type.
41 ///\param LM Type of cost map.
42 template<class GR, class LM>
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 concept::ReadMap "ReadMap" concept.
51 //The type of the cost of the edges.
52 typedef typename LM::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 UGraph::Node, typename LM::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 concept::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 concept::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 O(e*log n) 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 concept::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 concept::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 LM 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 ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value
160 ///of LM 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,LM>". 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 LM=typename GR::template UEdgeMap<int>,
179 typename TR=PrimDefaultTraits<GR,LM> >
184 * \brief \ref Exception for uninitialized parameters.
186 * This error represents problems in the initialization
187 * of the parameters of the algorithms.
189 class UninitializedParameter : public lemon::UninitializedParameter {
191 virtual const char* exceptionName() const {
192 return "lemon::Prim::UninitializedParameter";
197 ///The type of the underlying graph.
198 typedef typename TR::UGraph UGraph;
200 typedef typename UGraph::Node Node;
202 typedef typename UGraph::NodeIt NodeIt;
204 typedef typename UGraph::UEdge UEdge;
206 typedef typename UGraph::IncEdgeIt IncEdgeIt;
208 ///The type of the cost of the edges.
209 typedef typename TR::CostMap::Value Value;
210 ///The type of the map that stores the edge costs.
211 typedef typename TR::CostMap CostMap;
212 ///\brief The type of the map that stores the last
213 ///predecessor edges of the spanning tree.
214 typedef typename TR::PredMap PredMap;
215 ///Edges of the spanning tree.
216 typedef typename TR::TreeMap TreeMap;
217 ///The type of the map indicating if a node is processed.
218 typedef typename TR::ProcessedMap ProcessedMap;
219 ///The cross reference type used for the current heap.
220 typedef typename TR::HeapCrossRef HeapCrossRef;
221 ///The heap type used by the prim algorithm.
222 typedef typename TR::Heap Heap;
224 /// Pointer to the underlying graph.
226 /// Pointer to the cost map
228 ///Pointer to the map of predecessors edges.
230 ///Indicates if \ref _pred is locally allocated (\c true) or not.
232 ///Pointer to the map of tree edges.
234 ///Indicates if \ref _tree is locally allocated (\c true) or not.
236 ///Pointer to the map of processed status of the nodes.
237 ProcessedMap *_processed;
238 ///Indicates if \ref _processed is locally allocated (\c true) or not.
239 bool local_processed;
240 ///Pointer to the heap cross references.
241 HeapCrossRef *_heap_cross_ref;
242 ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
243 bool local_heap_cross_ref;
244 ///Pointer to the heap.
246 ///Indicates if \ref _heap is locally allocated (\c true) or not.
249 ///Creates the maps if necessary.
253 _pred = Traits::createPredMap(*graph);
257 _tree = Traits::createTreeMap(*graph);
260 local_processed = true;
261 _processed = Traits::createProcessedMap(*graph);
263 if (!_heap_cross_ref) {
264 local_heap_cross_ref = true;
265 _heap_cross_ref = Traits::createHeapCrossRef(*graph);
269 _heap = Traits::createHeap(*_heap_cross_ref);
277 ///\name Named template parameters
282 struct DefPredMapTraits : public Traits {
284 static PredMap *createPredMap(const UGraph &_graph){
285 throw UninitializedParameter();
288 ///\ref named-templ-param "Named parameter" for setting PredMap type
290 ///\ref named-templ-param "Named parameter" for setting PredMap type
294 : public Prim< UGraph, CostMap, DefPredMapTraits<T> > {
295 typedef Prim< UGraph, CostMap, DefPredMapTraits<T> > Create;
299 struct DefProcessedMapTraits : public Traits {
300 typedef T ProcessedMap;
301 static ProcessedMap *createProcessedMap(const UGraph &_graph){
302 throw UninitializedParameter();
305 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
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 ///\ref named-templ-param "Named parameter" for setting heap and cross
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 ///\ref named-templ-param "Named parameter" for setting heap and cross
358 ///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 ///\ref named-templ-param "Named parameter" for setting TreeMap
380 ///\ref named-templ-param "Named parameter" for setting TreeMap
384 : public Prim< UGraph, CostMap, DefTreeMapTraits<TM> > {
385 typedef Prim< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
388 struct DefGraphTreeMapTraits : public Traits {
389 typedef typename UGraph::template NodeMap<bool> TreeMap;
390 static TreeMap *createTreeMap(const UGraph &_graph){
391 return new TreeMap(_graph);
406 ///\param _graph the graph the algorithm will run on.
407 ///\param _cost the cost map used by the algorithm.
408 Prim(const UGraph& _graph, const CostMap& _cost) :
409 graph(&_graph), cost(&_cost),
410 _pred(NULL), local_pred(false),
411 _tree(NULL), local_tree(false),
412 _processed(NULL), local_processed(false),
413 _heap_cross_ref(NULL), local_heap_cross_ref(false),
414 _heap(NULL), local_heap(false)
416 checkConcept<concept::UGraph, UGraph>();
421 if(local_pred) delete _pred;
422 if(local_tree) delete _tree;
423 if(local_processed) delete _processed;
424 if(local_heap_cross_ref) delete _heap_cross_ref;
425 if(local_heap) delete _heap;
428 ///\brief Sets the cost map.
430 ///Sets the cost map.
431 ///\return <tt> (*this) </tt>
432 Prim &costMap(const CostMap &m){
437 ///\brief Sets the map storing the predecessor edges.
439 ///Sets the map storing the predecessor edges.
440 ///If you don't use this function before calling \ref run(),
441 ///it will allocate one. The destuctor deallocates this
442 ///automatically allocated map, of course.
443 ///\return <tt> (*this) </tt>
444 Prim &predMap(PredMap &m){
453 ///\brief Sets the map storing the tree edges.
455 ///Sets the map storing the tree edges.
456 ///If you don't use this function before calling \ref run(),
457 ///it will allocate one. The destuctor deallocates this
458 ///automatically allocated map, of course.
459 ///By default this is a NullMap.
460 ///\return <tt> (*this) </tt>
461 Prim &treeMap(TreeMap &m){
470 ///\brief Sets the heap and the cross reference used by algorithm.
472 ///Sets the heap and the cross reference used by algorithm.
473 ///If you don't use this function before calling \ref run(),
474 ///it will allocate one. The destuctor deallocates this
475 ///automatically allocated map, of course.
476 ///\return <tt> (*this) </tt>
477 Prim &heap(Heap& heap, HeapCrossRef &crossRef){
478 if(local_heap_cross_ref) {
479 delete _heap_cross_ref;
480 local_heap_cross_ref=false;
482 _heap_cross_ref = &crossRef;
492 ///\name Execution control
493 ///The simplest way to execute the algorithm is to use
494 ///one of the member functions called \c run(...).
496 ///If you need more control on the execution,
497 ///first you must call \ref init(), then you can add several source nodes
498 ///with \ref addSource().
499 ///Finally \ref start() will perform the actual path
504 ///\brief Initializes the internal data structures.
506 ///Initializes the internal data structures.
511 for ( NodeIt u(*graph) ; u!=INVALID ; ++u ) {
512 _pred->set(u,INVALID);
513 _processed->set(u,false);
514 _heap_cross_ref->set(u,Heap::PRE_HEAP);
518 ///\brief Adds a new source node.
520 ///Adds a new source node to the priority heap.
522 ///It checks if the node has already been added to the heap and
523 ///it is pushed to the heap only if it was not in the heap.
524 void addSource(Node s){
525 if(_heap->state(s) != Heap::IN_HEAP) {
526 _heap->push(s,Value());
529 ///\brief Processes the next node in the priority heap
531 ///Processes the next node in the priority heap.
533 ///\return The processed node.
535 ///\warning The priority heap must not be empty!
536 Node processNextNode(){
539 _processed->set(v,true);
541 for(IncEdgeIt e(*graph,v); e!=INVALID; ++e) {
542 Node w=graph->oppositeNode(v,e);
543 switch(_heap->state(w)) {
545 _heap->push(w,(*cost)[e]);
549 if ( (*cost)[e] < (*_heap)[w] ) {
550 _heap->decrease(w,(*cost)[e]);
554 case Heap::POST_HEAP:
558 if ((*_pred)[v]!=INVALID)_tree->set((*_pred)[v],true);
562 ///\brief Next node to be processed.
564 ///Next node to be processed.
566 ///\return The next node to be processed or INVALID if the priority heap
569 return _heap->empty()?_heap->top():INVALID;
572 ///\brief Returns \c false if there are nodes to be processed in the priority heap
574 ///Returns \c false if there are nodes
575 ///to be processed in the priority heap
576 bool emptyQueue() { return _heap->empty(); }
577 ///\brief Returns the number of the nodes to be processed in the priority heap
579 ///Returns the number of the nodes to be processed in the priority heap
581 int queueSize() { return _heap->size(); }
583 ///\brief Executes the algorithm.
585 ///Executes the algorithm.
587 ///\pre init() must be called and at least one node should be added
588 ///with addSource() before using this function.
590 ///This method runs the %Prim algorithm from the node(s)
591 ///in order to compute the
592 ///minimum spanning tree.
595 while ( !_heap->empty() ) processNextNode();
598 ///\brief Executes the algorithm until a condition is met.
600 ///Executes the algorithm until a condition is met.
602 ///\pre init() must be called and at least one node should be added
603 ///with addSource() before using this function.
605 ///\param nm must be a bool (or convertible) node map. The algorithm
606 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
607 template<class NodeBoolMap>
608 void start(const NodeBoolMap &nm){
609 while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
610 if ( !_heap->empty() ) _processed->set(_heap->top(),true);
613 ///\brief Runs %Prim algorithm.
615 ///This method runs the %Prim algorithm
616 ///in order to compute the
617 ///minimum spanning tree (or minimum spanning forest).
618 ///The method also works on graphs that has more than one components.
619 ///In this case it computes the minimum spanning forest.
622 for(NodeIt it(*graph);it!=INVALID;++it){
630 ///\brief Runs %Prim algorithm from node \c s.
632 ///This method runs the %Prim algorithm from node \c s
635 ///minimun spanning tree
637 ///\note d.run(s) is just a shortcut of the following code.
643 ///\note If the graph has more than one components, the method
644 ///will compute the minimun spanning tree for only one component.
646 ///See \ref run() if you want to compute the minimal spanning forest.
655 ///\name Query Functions
656 ///The result of the %Prim algorithm can be obtained using these
658 ///Before the use of these functions,
659 ///either run() or start() must be called.
663 ///\brief Returns the 'previous edge' of the minimum spanning tree.
665 ///For a node \c v it returns the 'previous edge' of the minimum spanning tree,
666 ///i.e. it returns the edge from where \c v was reached. For a source node
667 ///or an unreachable node it is \ref INVALID.
668 ///The minimum spanning tree used here is equal to the minimum spanning tree used
669 ///in \ref predNode(). \pre \ref run() or \ref start() must be called before
670 ///using this function.
671 UEdge predEdge(Node v) const { return (*_pred)[v]; }
673 ///\brief Returns the 'previous node' of the minimum spanning tree.
675 ///For a node \c v it returns the 'previous node' of the minimum spanning tree,
676 ///i.e. it returns the node from where \c v was reached. For a source node
677 ///or an unreachable node it is \ref INVALID.
678 //The minimum spanning tree used here is equal to the minimum spanning
679 ///tree used in \ref predEdge(). \pre \ref run() or \ref start() must be called
680 ///before using this function.
681 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
682 graph->source((*_pred)[v]); }
684 ///\brief Returns a reference to the NodeMap of the edges of the minimum spanning tree.
686 ///Returns a reference to the NodeMap of the edges of the
687 ///minimum spanning tree.
688 ///\pre \ref run() or \ref start() must be called before using this function.
689 const PredMap &predMap() const { return *_pred;}
691 ///\brief Returns a reference to the tree edges map.
693 ///Returns a reference to the TreeEdgeMap of the edges of the
694 ///minimum spanning tree. The value of the map is \c true only if the edge is in
695 ///the minimum spanning tree.
696 ///\warning By default, the TreeEdgeMap is a NullMap.
698 ///If it is not set before the execution of the algorithm, use the \ref
699 ///treeMap(TreeMap&) function (after the execution) to set an UEdgeMap with the
700 ///edges of the minimum spanning tree in O(n) time where n is the number of
701 ///nodes in the graph.
702 ///\pre \ref run() or \ref start() must be called before using this function.
703 const TreeMap &treeMap() const { return *_tree;}
705 ///\brief Sets the tree edges map.
707 ///Sets the TreeMap of the edges of the minimum spanning tree.
708 ///The map values belonging to the edges of the minimum
709 ///spanning tree are set to \c tree_edge_value or \c true by default,
710 ///the other map values remain untouched.
712 ///\pre \ref run() or \ref start() must be called before using this function.
714 template<class TreeMap>
717 const typename TreeMap::Value& tree_edge_value=true) const {
718 for(NodeIt i(*graph);i!=INVALID;++i){
719 if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
723 ///\brief Sets the tree edges map.
725 ///Sets the TreeMap of the edges of the minimum spanning tree.
726 ///The map values belonging to the edges of the minimum
727 ///spanning tree are set to \c tree_edge_value or \c true by default while
728 ///the edge values not belonging to the minimum spanning tree are set to
729 ///\c tree_default_value or \c false by default.
731 ///\pre \ref run() or \ref start() must be called before using this function.
733 template<class TreeMap>
736 const typename TreeMap::Value& tree_edge_value=true,
737 const typename TreeMap::Value& tree_default_value=false) const {
738 for(typename ItemSetTraits<UGraph,UEdge>::ItemIt i(*graph);i!=INVALID;++i)
739 tree.set(i,tree_default_value);
740 for(NodeIt i(*graph);i!=INVALID;++i){
741 if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
745 ///\brief Checks if a node is reachable from the starting node.
747 ///Returns \c true if \c v is reachable from the starting node.
748 ///\warning The source nodes are inditated as unreached.
749 ///\pre \ref run() or \ref start() must be called before using this function.
751 bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
753 ///\brief Checks if a node is processed.
755 ///Returns \c true if \c v is processed, i.e. \c v is already connencted to the
756 ///minimum spanning tree.
757 ///\pre \ref run() or \ref start() must be called before using this function.
759 bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
762 ///\brief Checks if an edge is in the spanning tree or not.
764 ///Checks if an edge is in the spanning tree or not.
765 ///\param e is the edge that will be checked
766 ///\return \c true if e is in the spanning tree, \c false otherwise
768 return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e;
774 /// \ingroup spantree
776 /// \brief Function type interface for Prim algorithm.
778 /// Function type interface for Prim algorithm.
779 /// \param graph the UGraph that the algorithm runs on
780 /// \param cost the CostMap of the edges
781 /// \retval tree the EdgeMap that contains whether an edge is in
782 /// the spanning tree or not
785 template<class Graph,class CostMap,class TreeMap>
786 void prim(const Graph& graph, const CostMap& cost,TreeMap& tree){
787 typename Prim<Graph,CostMap>::template DefTreeMap<TreeMap>::
788 Create prm(graph,cost);
793 } //END OF NAMESPACE LEMON