Better handling of inexact computation.
We do not use tolerance for excess, just for edges
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/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 ///\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 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
306 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
309 struct DefProcessedMap
310 : public Prim< UGraph, CostMap, DefProcessedMapTraits<T> > {
311 typedef Prim< UGraph, CostMap, DefProcessedMapTraits<T> > Create;
314 struct DefGraphProcessedMapTraits : public Traits {
315 typedef typename UGraph::template NodeMap<bool> ProcessedMap;
316 static ProcessedMap *createProcessedMap(const UGraph &_graph){
317 return new ProcessedMap(_graph);
322 template <class H, class CR>
323 struct DefHeapTraits : public Traits {
324 typedef CR HeapCrossRef;
326 static HeapCrossRef *createHeapCrossRef(const UGraph &) {
327 throw UninitializedParameter();
329 static Heap *createHeap(HeapCrossRef &){
330 return UninitializedParameter();
333 ///\brief \ref named-templ-param "Named parameter" for setting
334 ///heap and cross reference type
336 ///\ref named-templ-param "Named parameter" for setting heap and cross
339 template <class H, class CR = typename UGraph::template NodeMap<int> >
341 : public Prim< UGraph, CostMap, DefHeapTraits<H, CR> > {
342 typedef Prim< UGraph, CostMap, DefHeapTraits<H, CR> > Create;
345 template <class H, class CR>
346 struct DefStandardHeapTraits : public Traits {
347 typedef CR HeapCrossRef;
349 static HeapCrossRef *createHeapCrossRef(const UGraph &_graph) {
350 return new HeapCrossRef(_graph);
352 static Heap *createHeap(HeapCrossRef &ref){
353 return new Heap(ref);
356 ///\brief \ref named-templ-param "Named parameter" for setting
357 ///heap and cross reference type with automatic allocation
359 ///\ref named-templ-param "Named parameter" for setting heap and cross
360 ///reference type. It can allocate the heap and the cross reference
361 ///object if the cross reference's constructor waits for the graph as
362 ///parameter and the heap's constructor waits for the cross reference.
363 template <class H, class CR = typename UGraph::template NodeMap<int> >
364 struct DefStandardHeap
365 : public Prim< UGraph, CostMap, DefStandardHeapTraits<H, CR> > {
366 typedef Prim< UGraph, CostMap, DefStandardHeapTraits<H, CR> >
371 struct DefTreeMapTraits : public Traits {
373 static TreeMap *createTreeMap(const UGraph &) {
374 throw UninitializedParameter();
377 ///\ref named-templ-param "Named parameter" for setting TreeMap
379 ///\ref named-templ-param "Named parameter" for setting TreeMap
383 : public Prim< UGraph, CostMap, DefTreeMapTraits<TM> > {
384 typedef Prim< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
387 struct DefGraphTreeMapTraits : public Traits {
388 typedef typename UGraph::template NodeMap<bool> TreeMap;
389 static TreeMap *createTreeMap(const UGraph &_graph){
390 return new TreeMap(_graph);
405 ///\param _graph the graph the algorithm will run on.
406 ///\param _cost the cost map used by the algorithm.
407 Prim(const UGraph& _graph, const CostMap& _cost) :
408 graph(&_graph), cost(&_cost),
409 _pred(NULL), local_pred(false),
410 _tree(NULL), local_tree(false),
411 _processed(NULL), local_processed(false),
412 _heap_cross_ref(NULL), local_heap_cross_ref(false),
413 _heap(NULL), local_heap(false)
415 checkConcept<concepts::UGraph, UGraph>();
420 if(local_pred) delete _pred;
421 if(local_tree) delete _tree;
422 if(local_processed) delete _processed;
423 if(local_heap_cross_ref) delete _heap_cross_ref;
424 if(local_heap) delete _heap;
427 ///\brief Sets the cost map.
429 ///Sets the cost map.
430 ///\return <tt> (*this) </tt>
431 Prim &costMap(const CostMap &m){
436 ///\brief Sets the map storing the predecessor edges.
438 ///Sets the map storing the predecessor edges.
439 ///If you don't use this function before calling \ref run(),
440 ///it will allocate one. The destuctor deallocates this
441 ///automatically allocated map, of course.
442 ///\return <tt> (*this) </tt>
443 Prim &predMap(PredMap &m){
452 ///\brief Sets the map storing the tree edges.
454 ///Sets the map storing the tree edges.
455 ///If you don't use this function before calling \ref run(),
456 ///it will allocate one. The destuctor deallocates this
457 ///automatically allocated map, of course.
458 ///By default this is a NullMap.
459 ///\return <tt> (*this) </tt>
460 Prim &treeMap(TreeMap &m){
469 ///\brief Sets the heap and the cross reference used by algorithm.
471 ///Sets the heap and the cross reference used by algorithm.
472 ///If you don't use this function before calling \ref run(),
473 ///it will allocate one. The destuctor deallocates this
474 ///automatically allocated map, of course.
475 ///\return <tt> (*this) </tt>
476 Prim &heap(Heap& heap, HeapCrossRef &crossRef){
477 if(local_heap_cross_ref) {
478 delete _heap_cross_ref;
479 local_heap_cross_ref=false;
481 _heap_cross_ref = &crossRef;
491 ///\name Execution control
492 ///The simplest way to execute the algorithm is to use
493 ///one of the member functions called \c run(...).
495 ///If you need more control on the execution,
496 ///first you must call \ref init(), then you can add several source nodes
497 ///with \ref addSource().
498 ///Finally \ref start() will perform the actual path
503 ///\brief Initializes the internal data structures.
505 ///Initializes the internal data structures.
510 for ( NodeIt u(*graph) ; u!=INVALID ; ++u ) {
511 _pred->set(u,INVALID);
512 _processed->set(u,false);
513 _heap_cross_ref->set(u,Heap::PRE_HEAP);
517 ///\brief Adds a new source node.
519 ///Adds a new source node to the priority heap.
521 ///It checks if the node has already been added to the heap and
522 ///it is pushed to the heap only if it was not in the heap.
523 void addSource(Node s){
524 if(_heap->state(s) != Heap::IN_HEAP) {
525 _heap->push(s,Value());
528 ///\brief Processes the next node in the priority heap
530 ///Processes the next node in the priority heap.
532 ///\return The processed node.
534 ///\warning The priority heap must not be empty!
535 Node processNextNode(){
538 _processed->set(v,true);
540 for(IncEdgeIt e(*graph,v); e!=INVALID; ++e) {
541 Node w=graph->oppositeNode(v,e);
542 switch(_heap->state(w)) {
544 _heap->push(w,(*cost)[e]);
548 if ( (*cost)[e] < (*_heap)[w] ) {
549 _heap->decrease(w,(*cost)[e]);
553 case Heap::POST_HEAP:
557 if ((*_pred)[v]!=INVALID)_tree->set((*_pred)[v],true);
561 ///\brief Next node to be processed.
563 ///Next node to be processed.
565 ///\return The next node to be processed or INVALID if the priority heap
568 return _heap->empty()?_heap->top():INVALID;
571 ///\brief Returns \c false if there are nodes to be processed in the priority heap
573 ///Returns \c false if there are nodes
574 ///to be processed in the priority heap
575 bool emptyQueue() { return _heap->empty(); }
576 ///\brief Returns the number of the nodes to be processed in the priority heap
578 ///Returns the number of the nodes to be processed in the priority heap
580 int queueSize() { return _heap->size(); }
582 ///\brief Executes the algorithm.
584 ///Executes the algorithm.
586 ///\pre init() must be called and at least one node should be added
587 ///with addSource() before using this function.
589 ///This method runs the %Prim algorithm from the node(s)
590 ///in order to compute the
591 ///minimum spanning tree.
594 while ( !_heap->empty() ) processNextNode();
597 ///\brief Executes the algorithm until a condition is met.
599 ///Executes the algorithm until a condition is met.
601 ///\pre init() must be called and at least one node should be added
602 ///with addSource() before using this function.
604 ///\param nm must be a bool (or convertible) node map. The algorithm
605 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
606 template<class NodeBoolMap>
607 void start(const NodeBoolMap &nm){
608 while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
609 if ( !_heap->empty() ) _processed->set(_heap->top(),true);
612 ///\brief Runs %Prim algorithm.
614 ///This method runs the %Prim algorithm
615 ///in order to compute the
616 ///minimum spanning tree (or minimum spanning forest).
617 ///The method also works on graphs that has more than one components.
618 ///In this case it computes the minimum spanning forest.
621 for(NodeIt it(*graph);it!=INVALID;++it){
629 ///\brief Runs %Prim algorithm from node \c s.
631 ///This method runs the %Prim algorithm from node \c s
634 ///minimun spanning tree
636 ///\note d.run(s) is just a shortcut of the following code.
642 ///\note If the graph has more than one components, the method
643 ///will compute the minimun spanning tree for only one component.
645 ///See \ref run() if you want to compute the minimal spanning forest.
654 ///\name Query Functions
655 ///The result of the %Prim algorithm can be obtained using these
657 ///Before the use of these functions,
658 ///either run() or start() must be called.
662 ///\brief Returns the 'previous edge' of the minimum spanning tree.
664 ///For a node \c v it returns the 'previous edge' of the minimum spanning tree,
665 ///i.e. it returns the edge from where \c v was reached. For a source node
666 ///or an unreachable node it is \ref INVALID.
667 ///The minimum spanning tree used here is equal to the minimum spanning tree used
668 ///in \ref predNode(). \pre \ref run() or \ref start() must be called before
669 ///using this function.
670 UEdge predEdge(Node v) const { return (*_pred)[v]; }
672 ///\brief Returns the 'previous node' of the minimum spanning tree.
674 ///For a node \c v it returns the 'previous node' of the minimum spanning tree,
675 ///i.e. it returns the node from where \c v was reached. For a source node
676 ///or an unreachable node it is \ref INVALID.
677 //The minimum spanning tree used here is equal to the minimum spanning
678 ///tree used in \ref predEdge(). \pre \ref run() or \ref start() must be called
679 ///before using this function.
680 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
681 graph->source((*_pred)[v]); }
683 ///\brief Returns a reference to the NodeMap of the edges of the minimum spanning tree.
685 ///Returns a reference to the NodeMap of the edges of the
686 ///minimum spanning tree.
687 ///\pre \ref run() or \ref start() must be called before using this function.
688 const PredMap &predMap() const { return *_pred;}
690 ///\brief Returns a reference to the tree edges map.
692 ///Returns a reference to the TreeEdgeMap of the edges of the
693 ///minimum spanning tree. The value of the map is \c true only if the edge is in
694 ///the minimum spanning tree.
695 ///\warning By default, the TreeEdgeMap is a NullMap.
697 ///If it is not set before the execution of the algorithm, use the \ref
698 ///treeMap(TreeMap&) function (after the execution) to set an UEdgeMap with the
699 ///edges of the minimum spanning tree in O(n) time where n is the number of
700 ///nodes in the graph.
701 ///\pre \ref run() or \ref start() must be called before using this function.
702 const TreeMap &treeMap() const { return *_tree;}
704 ///\brief Sets the tree edges map.
706 ///Sets the TreeMap of the edges of the minimum spanning tree.
707 ///The map values belonging to the edges of the minimum
708 ///spanning tree are set to \c tree_edge_value or \c true by default,
709 ///the other map values remain untouched.
711 ///\pre \ref run() or \ref start() must be called before using this function.
713 template<class TreeMap>
716 const typename TreeMap::Value& tree_edge_value=true) const {
717 for(NodeIt i(*graph);i!=INVALID;++i){
718 if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
722 ///\brief Sets the tree edges map.
724 ///Sets the TreeMap of the edges of the minimum spanning tree.
725 ///The map values belonging to the edges of the minimum
726 ///spanning tree are set to \c tree_edge_value or \c true by default while
727 ///the edge values not belonging to the minimum spanning tree are set to
728 ///\c tree_default_value or \c false by default.
730 ///\pre \ref run() or \ref start() must be called before using this function.
732 template<class TreeMap>
735 const typename TreeMap::Value& tree_edge_value=true,
736 const typename TreeMap::Value& tree_default_value=false) const {
737 for(typename ItemSetTraits<UGraph,UEdge>::ItemIt i(*graph);i!=INVALID;++i)
738 tree.set(i,tree_default_value);
739 for(NodeIt i(*graph);i!=INVALID;++i){
740 if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
744 ///\brief Checks if a node is reachable from the starting node.
746 ///Returns \c true if \c v is reachable from the starting node.
747 ///\warning The source nodes are inditated as unreached.
748 ///\pre \ref run() or \ref start() must be called before using this function.
750 bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
752 ///\brief Checks if a node is processed.
754 ///Returns \c true if \c v is processed, i.e. \c v is already connencted to the
755 ///minimum spanning tree.
756 ///\pre \ref run() or \ref start() must be called before using this function.
758 bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
761 ///\brief Checks if an edge is in the spanning tree or not.
763 ///Checks if an edge is in the spanning tree or not.
764 ///\param e is the edge that will be checked
765 ///\return \c true if e is in the spanning tree, \c false otherwise
767 return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e;
773 /// \ingroup spantree
775 /// \brief Function type interface for Prim algorithm.
777 /// Function type interface for Prim algorithm.
778 /// \param graph the UGraph that the algorithm runs on
779 /// \param cost the CostMap of the edges
780 /// \retval tree the EdgeMap that contains whether an edge is in
781 /// the spanning tree or not
784 template<class Graph,class CostMap,class TreeMap>
785 void prim(const Graph& graph, const CostMap& cost,TreeMap& tree){
786 typename Prim<Graph,CostMap>::template DefTreeMap<TreeMap>::
787 Create prm(graph,cost);
792 } //END OF NAMESPACE LEMON