deba@1912: /* -*- C++ -*- deba@1912: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2553: * Copyright (C) 2003-2008 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@1912: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@1912: * deba@1912: * Permission to use, modify and distribute this software is granted deba@1912: * provided that this copyright notice appears in all copies. For deba@1912: * precise terms see the accompanying LICENSE file. deba@1912: * deba@1912: * This software is provided "AS IS" with no warranty of any kind, deba@1912: * express or implied, and with no claim as to its suitability for any deba@1912: * purpose. deba@1912: * deba@1912: */ deba@1912: deba@1912: #ifndef LEMON_PRIM_H deba@1912: #define LEMON_PRIM_H deba@1912: deba@1912: ///\ingroup spantree deba@1912: ///\file deba@1912: ///\brief Prim algorithm to compute minimum spanning tree. deba@1912: deba@1912: #include deba@1912: #include deba@1993: #include deba@1912: #include deba@1912: #include deba@1993: #include deba@1912: alpar@2260: #include deba@1912: deba@1912: namespace lemon { deba@1912: deba@1912: ///Default traits class of Prim class. deba@1912: deba@1912: ///Default traits class of Prim class. deba@1912: ///\param GR Graph type. deba@2030: ///\param CM Type of cost map. deba@2030: template deba@1912: struct PrimDefaultTraits{ deba@1912: ///The graph type the algorithm runs on. deba@1912: typedef GR UGraph; deba@1912: ///The type of the map that stores the edge costs. deba@1912: deba@1912: ///The type of the map that stores the edge costs. alpar@2260: ///It must meet the \ref concepts::ReadMap "ReadMap" concept. deba@2030: typedef CM CostMap; deba@1912: //The type of the cost of the edges. deba@2030: typedef typename CM::Value Value; deba@1912: /// The cross reference type used by heap. deba@1912: deba@1912: /// The cross reference type used by heap. deba@1912: /// Usually it is \c UGraph::NodeMap. deba@1912: typedef typename UGraph::template NodeMap HeapCrossRef; deba@1912: ///Instantiates a HeapCrossRef. deba@1912: deba@1912: ///This function instantiates a \ref HeapCrossRef. alpar@1953: /// \param _graph is the graph, to which we would like to define the deba@1912: /// HeapCrossRef. deba@1912: static HeapCrossRef *createHeapCrossRef(const GR &_graph){ deba@1912: return new HeapCrossRef(_graph); deba@1912: } deba@1912: deba@1912: ///The heap type used by Prim algorithm. deba@1912: deba@1912: ///The heap type used by Prim algorithm. deba@1912: /// deba@1912: ///\sa BinHeap deba@1912: ///\sa Prim mqrelly@2263: typedef BinHeap > Heap; deba@1912: deba@1912: static Heap *createHeap(HeapCrossRef& _ref){ deba@1912: return new Heap(_ref); deba@1912: } deba@1912: deba@1912: ///\brief The type of the map that stores the last deba@1912: ///edges of the minimum spanning tree. deba@1912: /// deba@1912: ///The type of the map that stores the last deba@1912: ///edges of the minimum spanning tree. alpar@2260: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. deba@1912: /// deba@1912: typedef typename UGraph::template NodeMap PredMap; deba@1912: ///Instantiates a PredMap. deba@1912: deba@1912: ///This function instantiates a \ref PredMap. alpar@1953: ///\param _graph is the graph, to which we would like to define the PredMap. deba@1912: static PredMap *createPredMap(const GR &_graph){ deba@1912: return new PredMap(_graph); deba@1912: } deba@1912: deba@1912: ///The type of the map that stores whether an edge is in the deba@1912: ///spanning tree or not. deba@1912: deba@1912: ///The type of the map that stores whether an edge is in the deba@1912: ///spanning tree or not. deba@1912: ///By default it is a NullMap. deba@1912: typedef NullMap TreeMap; deba@1912: ///Instantiates a TreeMap. deba@1912: deba@1912: ///This function instantiates a \ref TreeMap. alpar@1953: /// alpar@1953: ///The first parameter is the graph, to which deba@1912: ///we would like to define the \ref TreeMap deba@1912: static TreeMap *createTreeMap(const GR &){ deba@1912: return new TreeMap(); deba@1912: } deba@1912: deba@1912: ///The type of the map that stores whether a nodes is processed. deba@1912: deba@1912: ///The type of the map that stores whether a nodes is processed. alpar@2260: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. deba@1912: ///By default it is a NodeMap. deba@1912: typedef NullMap ProcessedMap; deba@1912: ///Instantiates a ProcessedMap. deba@1912: deba@1912: ///This function instantiates a \ref ProcessedMap. alpar@1953: ///\param _graph is the graph, to which deba@1912: ///we would like to define the \ref ProcessedMap deba@1912: #ifdef DOXYGEN deba@1912: static ProcessedMap *createProcessedMap(const GR &_graph) deba@1912: #else deba@1912: static ProcessedMap *createProcessedMap(const GR &) deba@1912: #endif deba@1912: { deba@1912: return new ProcessedMap(); deba@1912: } deba@1912: }; deba@1912: deba@1912: ///%Prim algorithm class to find a minimum spanning tree. deba@1912: deba@1912: /// \ingroup spantree deba@1912: ///This class provides an efficient implementation of %Prim algorithm. deba@1912: /// deba@2042: ///The running time is \f$ O(e\log(n)) \f$ where e is the number of edges and deba@1912: ///n is the number of nodes in the graph. deba@1912: /// deba@1912: ///The edge costs are passed to the algorithm using a alpar@2260: ///\ref concepts::ReadMap "ReadMap", deba@1912: ///so it is easy to change it to any kind of cost. deba@1912: /// deba@1912: ///The type of the cost is determined by the alpar@2260: ///\ref concepts::ReadMap::Value "Value" of the cost map. deba@1912: /// deba@1912: ///It is also possible to change the underlying priority heap. deba@1912: /// deba@1912: ///\param GR The graph type the algorithm runs on. The default value deba@1912: ///is \ref ListUGraph. The value of GR is not used directly by deba@1912: ///Prim, it is only passed to \ref PrimDefaultTraits. deba@1912: /// deba@2030: ///\param CM This read-only UEdgeMap determines the costs of the deba@1912: ///edges. It is read once for each edge, so the map may involve in deba@1912: ///relatively time consuming process to compute the edge cost if deba@1912: ///it is necessary. The default map type is \ref alpar@2260: ///concepts::UGraph::UEdgeMap "UGraph::UEdgeMap". The value deba@2030: ///of CM is not used directly by Prim, it is only passed to \ref deba@1912: ///PrimDefaultTraits. deba@1912: /// deba@1912: ///\param TR Traits class to set deba@1912: ///various data types used by the algorithm. The default traits deba@1912: ///class is \ref PrimDefaultTraits deba@2030: ///"PrimDefaultTraits". See \ref deba@1912: ///PrimDefaultTraits for the documentation of a Prim traits deba@1912: ///class. deba@1912: /// deba@1912: ///\author Balazs Attila Mihaly deba@1912: deba@1912: #ifdef DOXYGEN deba@1912: template deba@1912: #else deba@1912: template , deba@2030: typename TR=PrimDefaultTraits > deba@1912: #endif deba@1912: class Prim { deba@1912: public: deba@2030: deba@2030: /// \brief \ref Exception for uninitialized parameters. deba@2030: /// deba@2030: /// This error represents problems in the initialization deba@2030: /// of the parameters of the algorithms. deba@1912: class UninitializedParameter : public lemon::UninitializedParameter { deba@1912: public: alpar@2151: virtual const char* what() const throw() { deba@1912: return "lemon::Prim::UninitializedParameter"; deba@1912: } deba@1912: }; deba@1912: deba@1912: typedef TR Traits; deba@1912: ///The type of the underlying graph. deba@1912: typedef typename TR::UGraph UGraph; deba@1912: ///\e deba@1912: typedef typename UGraph::Node Node; deba@1912: ///\e deba@1912: typedef typename UGraph::NodeIt NodeIt; deba@1912: ///\e deba@1912: typedef typename UGraph::UEdge UEdge; deba@1912: ///\e deba@1912: typedef typename UGraph::IncEdgeIt IncEdgeIt; deba@1912: deba@1912: ///The type of the cost of the edges. deba@1912: typedef typename TR::CostMap::Value Value; deba@1912: ///The type of the map that stores the edge costs. deba@1912: typedef typename TR::CostMap CostMap; deba@1912: ///\brief The type of the map that stores the last deba@1912: ///predecessor edges of the spanning tree. deba@1912: typedef typename TR::PredMap PredMap; deba@1912: ///Edges of the spanning tree. deba@1912: typedef typename TR::TreeMap TreeMap; deba@1912: ///The type of the map indicating if a node is processed. deba@1912: typedef typename TR::ProcessedMap ProcessedMap; deba@1912: ///The cross reference type used for the current heap. deba@1912: typedef typename TR::HeapCrossRef HeapCrossRef; deba@1912: ///The heap type used by the prim algorithm. deba@1912: typedef typename TR::Heap Heap; deba@1912: private: deba@1912: /// Pointer to the underlying graph. deba@1912: const UGraph *graph; deba@1912: /// Pointer to the cost map deba@1912: const CostMap *cost; deba@1912: ///Pointer to the map of predecessors edges. deba@1912: PredMap *_pred; deba@1912: ///Indicates if \ref _pred is locally allocated (\c true) or not. deba@1912: bool local_pred; deba@1912: ///Pointer to the map of tree edges. deba@1912: TreeMap *_tree; deba@1912: ///Indicates if \ref _tree is locally allocated (\c true) or not. deba@1912: bool local_tree; deba@1912: ///Pointer to the map of processed status of the nodes. deba@1912: ProcessedMap *_processed; deba@1912: ///Indicates if \ref _processed is locally allocated (\c true) or not. deba@1912: bool local_processed; deba@1912: ///Pointer to the heap cross references. deba@1912: HeapCrossRef *_heap_cross_ref; deba@1912: ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not. deba@1912: bool local_heap_cross_ref; deba@1912: ///Pointer to the heap. deba@1912: Heap *_heap; deba@1912: ///Indicates if \ref _heap is locally allocated (\c true) or not. deba@1912: bool local_heap; deba@1912: deba@1912: ///Creates the maps if necessary. deba@1912: void create_maps(){ deba@1912: if(!_pred) { deba@1912: local_pred = true; deba@1912: _pred = Traits::createPredMap(*graph); deba@1912: } deba@1912: if(!_tree) { deba@1912: local_tree = true; deba@1912: _tree = Traits::createTreeMap(*graph); deba@1912: } deba@1912: if(!_processed) { deba@1912: local_processed = true; deba@1912: _processed = Traits::createProcessedMap(*graph); deba@1912: } deba@1912: if (!_heap_cross_ref) { deba@1912: local_heap_cross_ref = true; deba@1912: _heap_cross_ref = Traits::createHeapCrossRef(*graph); deba@1912: } deba@1912: if (!_heap) { deba@1912: local_heap = true; deba@1912: _heap = Traits::createHeap(*_heap_cross_ref); deba@1912: } deba@1912: } deba@1912: deba@1912: public : deba@1912: deba@1912: typedef Prim Create; deba@1912: deba@1912: ///\name Named template parameters deba@1912: deba@1912: ///@{ deba@1912: deba@1912: template deba@1912: struct DefPredMapTraits : public Traits { deba@1912: typedef T PredMap; deba@1912: static PredMap *createPredMap(const UGraph &_graph){ deba@1912: throw UninitializedParameter(); deba@1912: } deba@1912: }; deba@2490: ///\brief \ref named-templ-param "Named parameter" for setting PredMap type deba@2490: /// deba@1912: ///\ref named-templ-param "Named parameter" for setting PredMap type deba@1912: /// deba@1912: template deba@1912: struct DefPredMap deba@1912: : public Prim< UGraph, CostMap, DefPredMapTraits > { deba@1912: typedef Prim< UGraph, CostMap, DefPredMapTraits > Create; deba@1912: }; deba@1912: deba@1912: template deba@1912: struct DefProcessedMapTraits : public Traits { deba@1912: typedef T ProcessedMap; deba@1912: static ProcessedMap *createProcessedMap(const UGraph &_graph){ deba@1912: throw UninitializedParameter(); deba@1912: } deba@1912: }; deba@2490: ///\brief \ref named-templ-param "Named parameter" for setting deba@2490: ///ProcessedMap type deba@2490: /// deba@1912: ///\ref named-templ-param "Named parameter" for setting ProcessedMap type deba@1912: /// deba@1912: template deba@1912: struct DefProcessedMap deba@1912: : public Prim< UGraph, CostMap, DefProcessedMapTraits > { deba@1912: typedef Prim< UGraph, CostMap, DefProcessedMapTraits > Create; deba@1912: }; deba@1912: deba@1912: struct DefGraphProcessedMapTraits : public Traits { deba@1912: typedef typename UGraph::template NodeMap ProcessedMap; deba@1912: static ProcessedMap *createProcessedMap(const UGraph &_graph){ deba@1912: return new ProcessedMap(_graph); deba@1912: } deba@1912: }; deba@1912: deba@1912: deba@1912: template deba@1912: struct DefHeapTraits : public Traits { deba@1912: typedef CR HeapCrossRef; deba@1912: typedef H Heap; deba@1912: static HeapCrossRef *createHeapCrossRef(const UGraph &) { deba@1912: throw UninitializedParameter(); deba@1912: } deba@1912: static Heap *createHeap(HeapCrossRef &){ deba@1912: return UninitializedParameter(); deba@1912: } deba@1912: }; deba@2230: ///\brief \ref named-templ-param "Named parameter" for setting deba@2230: ///heap and cross reference type deba@2230: /// deba@1912: ///\ref named-templ-param "Named parameter" for setting heap and cross deba@1912: ///reference type deba@1912: /// deba@1912: template > deba@1912: struct DefHeap deba@1912: : public Prim< UGraph, CostMap, DefHeapTraits > { deba@1912: typedef Prim< UGraph, CostMap, DefHeapTraits > Create; deba@1912: }; deba@1912: deba@1912: template deba@1912: struct DefStandardHeapTraits : public Traits { deba@1912: typedef CR HeapCrossRef; deba@1912: typedef H Heap; deba@1912: static HeapCrossRef *createHeapCrossRef(const UGraph &_graph) { deba@1912: return new HeapCrossRef(_graph); deba@1912: } deba@1912: static Heap *createHeap(HeapCrossRef &ref){ deba@1912: return new Heap(ref); deba@1912: } deba@1912: }; deba@2230: ///\brief \ref named-templ-param "Named parameter" for setting deba@2230: ///heap and cross reference type with automatic allocation deba@2230: /// deba@1912: ///\ref named-templ-param "Named parameter" for setting heap and cross deba@1912: ///reference type. It can allocate the heap and the cross reference deba@1912: ///object if the cross reference's constructor waits for the graph as deba@1912: ///parameter and the heap's constructor waits for the cross reference. deba@1912: template > deba@1912: struct DefStandardHeap deba@1912: : public Prim< UGraph, CostMap, DefStandardHeapTraits > { deba@1912: typedef Prim< UGraph, CostMap, DefStandardHeapTraits > deba@1912: Create; deba@1912: }; deba@1912: deba@1912: template deba@1912: struct DefTreeMapTraits : public Traits { deba@1912: typedef TM TreeMap; deba@1912: static TreeMap *createTreeMap(const UGraph &) { deba@1912: throw UninitializedParameter(); deba@1912: } deba@1912: }; deba@2490: ///\brief \ref named-templ-param "Named parameter" for setting deba@2490: ///TreeMap deba@2490: /// deba@1912: ///\ref named-templ-param "Named parameter" for setting TreeMap deba@1912: /// deba@1912: template deba@1912: struct DefTreeMap deba@1912: : public Prim< UGraph, CostMap, DefTreeMapTraits > { deba@1912: typedef Prim< UGraph, CostMap, DefTreeMapTraits > Create; deba@1912: }; deba@1912: deba@1912: struct DefGraphTreeMapTraits : public Traits { deba@1912: typedef typename UGraph::template NodeMap TreeMap; deba@1912: static TreeMap *createTreeMap(const UGraph &_graph){ deba@1912: return new TreeMap(_graph); deba@1912: } deba@1912: }; deba@1912: deba@1912: ///@} deba@1912: deba@1912: deba@1912: protected: deba@1912: deba@1912: Prim() {} deba@1912: deba@1912: public: deba@1912: deba@1912: ///Constructor. deba@2397: /// deba@1912: ///\param _graph the graph the algorithm will run on. deba@1912: ///\param _cost the cost map used by the algorithm. deba@1912: Prim(const UGraph& _graph, const CostMap& _cost) : deba@1912: graph(&_graph), cost(&_cost), deba@2397: _pred(0), local_pred(false), deba@2397: _tree(0), local_tree(false), deba@2397: _processed(0), local_processed(false), deba@2397: _heap_cross_ref(0), local_heap_cross_ref(false), deba@2397: _heap(0), local_heap(false) deba@1912: { alpar@2260: checkConcept(); deba@1912: } deba@1912: deba@1912: ///Destructor. deba@1912: ~Prim(){ deba@1912: if(local_pred) delete _pred; deba@1912: if(local_tree) delete _tree; deba@1912: if(local_processed) delete _processed; deba@1912: if(local_heap_cross_ref) delete _heap_cross_ref; deba@1912: if(local_heap) delete _heap; deba@1912: } deba@1912: deba@1912: ///\brief Sets the cost map. deba@2397: /// deba@1912: ///Sets the cost map. deba@1912: ///\return (*this) deba@1912: Prim &costMap(const CostMap &m){ deba@1912: cost = &m; deba@1912: return *this; deba@1912: } deba@1912: deba@1912: ///\brief Sets the map storing the predecessor edges. deba@2397: /// deba@1912: ///Sets the map storing the predecessor edges. deba@1912: ///If you don't use this function before calling \ref run(), deba@1912: ///it will allocate one. The destuctor deallocates this deba@1912: ///automatically allocated map, of course. deba@1912: ///\return (*this) deba@1912: Prim &predMap(PredMap &m){ deba@1912: if(local_pred) { deba@1912: delete _pred; deba@1912: local_pred=false; deba@1912: } deba@1912: _pred = &m; deba@1912: return *this; deba@1912: } deba@1912: deba@1912: ///\brief Sets the map storing the tree edges. deba@2397: /// deba@1912: ///Sets the map storing the tree edges. deba@1912: ///If you don't use this function before calling \ref run(), deba@1912: ///it will allocate one. The destuctor deallocates this deba@1912: ///automatically allocated map, of course. deba@1912: ///By default this is a NullMap. deba@1912: ///\return (*this) deba@1912: Prim &treeMap(TreeMap &m){ deba@1912: if(local_tree) { deba@1912: delete _tree; deba@1912: local_tree=false; deba@1912: } deba@1912: _tree = &m; deba@1912: return *this; deba@1912: } deba@1912: deba@1912: ///\brief Sets the heap and the cross reference used by algorithm. deba@2397: /// deba@1912: ///Sets the heap and the cross reference used by algorithm. deba@1912: ///If you don't use this function before calling \ref run(), deba@1912: ///it will allocate one. The destuctor deallocates this deba@1912: ///automatically allocated map, of course. deba@1912: ///\return (*this) deba@1912: Prim &heap(Heap& heap, HeapCrossRef &crossRef){ deba@1912: if(local_heap_cross_ref) { deba@1912: delete _heap_cross_ref; deba@1912: local_heap_cross_ref=false; deba@1912: } deba@1912: _heap_cross_ref = &crossRef; deba@1912: if(local_heap) { deba@1912: delete _heap; deba@1912: local_heap=false; deba@1912: } deba@1912: _heap = &heap; deba@1912: return *this; deba@1912: } deba@1912: deba@1912: public: deba@1912: ///\name Execution control deba@1912: ///The simplest way to execute the algorithm is to use deba@1912: ///one of the member functions called \c run(...). deba@1912: ///\n deba@1912: ///If you need more control on the execution, deba@1912: ///first you must call \ref init(), then you can add several source nodes deba@1912: ///with \ref addSource(). deba@1912: ///Finally \ref start() will perform the actual path deba@1912: ///computation. deba@1912: deba@1912: ///@{ deba@1912: deba@1912: ///\brief Initializes the internal data structures. deba@2397: /// deba@1912: ///Initializes the internal data structures. deba@1912: /// deba@1912: void init(){ deba@1912: create_maps(); deba@1912: _heap->clear(); deba@1912: for ( NodeIt u(*graph) ; u!=INVALID ; ++u ) { deba@1912: _pred->set(u,INVALID); deba@1912: _processed->set(u,false); deba@1912: _heap_cross_ref->set(u,Heap::PRE_HEAP); deba@1912: } deba@1912: } deba@1912: deba@1912: ///\brief Adds a new source node. deba@2397: /// deba@1912: ///Adds a new source node to the priority heap. deba@1912: /// deba@1912: ///It checks if the node has already been added to the heap and deba@1912: ///it is pushed to the heap only if it was not in the heap. deba@1912: void addSource(Node s){ deba@1912: if(_heap->state(s) != Heap::IN_HEAP) { deba@1912: _heap->push(s,Value()); deba@1912: } deba@1912: } deba@1912: ///\brief Processes the next node in the priority heap deba@2397: /// deba@1912: ///Processes the next node in the priority heap. deba@1912: /// deba@1912: ///\return The processed node. deba@1912: /// deba@1912: ///\warning The priority heap must not be empty! deba@1912: Node processNextNode(){ deba@1912: Node v=_heap->top(); deba@1912: _heap->pop(); deba@1912: _processed->set(v,true); deba@1912: deba@1912: for(IncEdgeIt e(*graph,v); e!=INVALID; ++e) { deba@1912: Node w=graph->oppositeNode(v,e); deba@1912: switch(_heap->state(w)) { deba@1912: case Heap::PRE_HEAP: deba@1912: _heap->push(w,(*cost)[e]); deba@1912: _pred->set(w,e); deba@1912: break; deba@1912: case Heap::IN_HEAP: deba@1912: if ( (*cost)[e] < (*_heap)[w] ) { deba@1912: _heap->decrease(w,(*cost)[e]); deba@1912: _pred->set(w,e); deba@1912: } deba@1912: break; deba@1912: case Heap::POST_HEAP: deba@1912: break; deba@1912: } deba@1912: } deba@1912: if ((*_pred)[v]!=INVALID)_tree->set((*_pred)[v],true); deba@1912: return v; deba@1912: } deba@1912: deba@1912: ///\brief Next node to be processed. deba@2397: /// deba@1912: ///Next node to be processed. deba@1912: /// deba@1912: ///\return The next node to be processed or INVALID if the priority heap deba@1912: /// is empty. deba@1912: Node nextNode(){ deba@1912: return _heap->empty()?_heap->top():INVALID; deba@1912: } deba@1912: deba@2397: ///\brief Returns \c false if there are nodes to be processed in deba@2397: ///the priority heap deba@1912: /// deba@1912: ///Returns \c false if there are nodes deba@1912: ///to be processed in the priority heap deba@1912: bool emptyQueue() { return _heap->empty(); } deba@1912: deba@2397: ///\brief Returns the number of the nodes to be processed in the deba@2397: ///priority heap deba@2397: /// deba@1912: ///Returns the number of the nodes to be processed in the priority heap deba@1912: /// deba@1912: int queueSize() { return _heap->size(); } deba@1912: deba@1912: ///\brief Executes the algorithm. deba@2397: /// deba@1912: ///Executes the algorithm. deba@1912: /// deba@1912: ///\pre init() must be called and at least one node should be added deba@1912: ///with addSource() before using this function. deba@1912: /// deba@1912: ///This method runs the %Prim algorithm from the node(s) deba@1912: ///in order to compute the deba@1912: ///minimum spanning tree. deba@1912: /// deba@1912: void start(){ deba@1912: while ( !_heap->empty() ) processNextNode(); deba@1912: } deba@1912: deba@1912: ///\brief Executes the algorithm until a condition is met. deba@2397: /// deba@1912: ///Executes the algorithm until a condition is met. deba@1912: /// deba@1912: ///\pre init() must be called and at least one node should be added deba@1912: ///with addSource() before using this function. deba@1912: /// deba@1912: ///\param nm must be a bool (or convertible) node map. The algorithm deba@1912: ///will stop when it reaches a node \c v with nm[v]==true. deba@1912: template deba@1912: void start(const NodeBoolMap &nm){ deba@1912: while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode(); deba@1912: if ( !_heap->empty() ) _processed->set(_heap->top(),true); deba@1912: } deba@1912: deba@1912: ///\brief Runs %Prim algorithm. deba@2397: /// deba@1912: ///This method runs the %Prim algorithm deba@1912: ///in order to compute the deba@1912: ///minimum spanning tree (or minimum spanning forest). deba@1912: ///The method also works on graphs that has more than one components. deba@1912: ///In this case it computes the minimum spanning forest. deba@1912: void run() { deba@1912: init(); deba@1912: for(NodeIt it(*graph);it!=INVALID;++it){ deba@1912: if(!processed(it)){ deba@1912: addSource(it); deba@1912: start(); deba@1912: } deba@1912: } deba@1912: } deba@1912: deba@1912: ///\brief Runs %Prim algorithm from node \c s. deba@2397: /// deba@1912: ///This method runs the %Prim algorithm from node \c s deba@1912: ///in order to deba@1912: ///compute the deba@1912: ///minimun spanning tree deba@1912: /// deba@2397: ///\note p.run(s) is just a shortcut of the following code. deba@1912: ///\code deba@2397: /// p.init(); deba@2397: /// p.addSource(s); deba@2397: /// p.start(); deba@1912: ///\endcode deba@1912: ///\note If the graph has more than one components, the method deba@1912: ///will compute the minimun spanning tree for only one component. deba@1912: /// deba@1912: ///See \ref run() if you want to compute the minimal spanning forest. deba@1912: void run(Node s){ deba@1912: init(); deba@1912: addSource(s); deba@1912: start(); deba@1912: } deba@1912: deba@1912: ///@} deba@1912: deba@1912: ///\name Query Functions deba@1912: ///The result of the %Prim algorithm can be obtained using these deba@1912: ///functions.\n deba@1912: ///Before the use of these functions, deba@1912: ///either run() or start() must be called. deba@1912: deba@1912: ///@{ deba@1912: deba@1912: ///\brief Returns the 'previous edge' of the minimum spanning tree. deba@1912: deba@2397: ///For a node \c v it returns the 'previous edge' of the minimum deba@2397: ///spanning tree, i.e. it returns the edge from where \c v was deba@2397: ///reached. For a source node or an unreachable node it is \ref deba@2397: ///INVALID. The minimum spanning tree used here is equal to the deba@2397: ///minimum spanning tree used in \ref predNode(). deba@2397: ///\pre \ref run() or \ref start() must be called before using deba@2397: ///this function. deba@1912: UEdge predEdge(Node v) const { return (*_pred)[v]; } deba@1912: deba@2397: ///\brief Returns the 'previous node' of the minimum spanning deba@2397: ///tree. deba@2397: /// deba@2397: ///For a node \c v it returns the 'previous node' of the minimum deba@2397: ///spanning tree, i.e. it returns the node from where \c v was deba@2397: ///reached. For a source node or an unreachable node it is \ref deba@2397: ///INVALID. //The minimum spanning tree used here is equal to the deba@2397: ///minimum spanning tree used in \ref predEdge(). deba@2397: ///\pre \ref run() or \ref start() must be called before using deba@2397: ///this function. deba@1912: Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: deba@1912: graph->source((*_pred)[v]); } deba@1912: deba@2397: ///\brief Returns a reference to the NodeMap of the edges of the deba@1912: ///minimum spanning tree. deba@2397: /// deba@2397: ///Returns a reference to the NodeMap of the edges of the minimum deba@2397: ///spanning tree. deba@2397: ///\pre \ref run() or \ref start() must be called before using deba@2397: ///this function. deba@1912: const PredMap &predMap() const { return *_pred;} deba@1912: deba@1912: ///\brief Returns a reference to the tree edges map. deba@1912: deba@1912: ///Returns a reference to the TreeEdgeMap of the edges of the deba@2397: ///minimum spanning tree. The value of the map is \c true only if deba@2397: ///the edge is in the minimum spanning tree. deba@2397: /// deba@1912: ///\warning By default, the TreeEdgeMap is a NullMap. deba@1912: /// deba@2397: ///If it is not set before the execution of the algorithm, use the deba@2397: ///\ref treeMap(TreeMap&) function (after the execution) to set an deba@2397: ///UEdgeMap with the edges of the minimum spanning tree in O(n) deba@2397: ///time where n is the number of nodes in the graph. deba@2397: ///\pre \ref run() or \ref start() must be called before using deba@2397: ///this function. deba@1912: const TreeMap &treeMap() const { return *_tree;} deba@1912: deba@1912: ///\brief Sets the tree edges map. deba@2397: /// deba@1912: ///Sets the TreeMap of the edges of the minimum spanning tree. deba@1912: ///The map values belonging to the edges of the minimum alpar@1953: ///spanning tree are set to \c tree_edge_value or \c true by default, deba@1912: ///the other map values remain untouched. deba@1912: /// deba@2397: ///\pre \ref run() or \ref start() must be called before using deba@2397: ///this function. deba@1912: deba@1912: template deba@2397: void quickTreeEdges(TreeMap& tree) const { deba@1912: for(NodeIt i(*graph);i!=INVALID;++i){ deba@2397: if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],true); deba@1912: } deba@1912: } deba@1912: deba@1912: ///\brief Sets the tree edges map. deba@2397: /// deba@1912: ///Sets the TreeMap of the edges of the minimum spanning tree. deba@1912: ///The map values belonging to the edges of the minimum alpar@1953: ///spanning tree are set to \c tree_edge_value or \c true by default while deba@1912: ///the edge values not belonging to the minimum spanning tree are set to alpar@1953: ///\c tree_default_value or \c false by default. deba@1912: /// deba@2397: ///\pre \ref run() or \ref start() must be called before using deba@2397: ///this function. deba@2397: template deba@2397: void treeEdges(TreeMap& tree) const { deba@2397: typedef typename ItemSetTraits::ItemIt TreeMapIt; deba@2397: for(TreeMapIt i(*graph); i != INVALID; ++i) { deba@2397: tree.set(i,false); deba@2397: } deba@2397: for(NodeIt i(*graph); i != INVALID; ++i){ deba@2397: if((*_pred)[i] != INVALID) tree.set((*_pred)[i],true); deba@1912: } deba@1912: } deba@1912: deba@1912: ///\brief Checks if a node is reachable from the starting node. deba@2397: /// deba@1912: ///Returns \c true if \c v is reachable from the starting node. deba@1912: ///\warning The source nodes are inditated as unreached. deba@2397: ///\pre \ref run() or \ref start() must be called before using deba@2397: ///this function. deba@1912: /// deba@1912: bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; } deba@1912: deba@1912: ///\brief Checks if a node is processed. deba@1912: /// deba@2397: ///Returns \c true if \c v is processed, i.e. \c v is already deba@2397: ///connencted to the minimum spanning tree. \pre \ref run() or deba@2397: ///\ref start() must be called before using this function. deba@1912: bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } deba@1912: deba@1912: deba@1912: ///\brief Checks if an edge is in the spanning tree or not. deba@2397: /// deba@1912: ///Checks if an edge is in the spanning tree or not. deba@1912: ///\param e is the edge that will be checked deba@1912: ///\return \c true if e is in the spanning tree, \c false otherwise deba@1912: bool tree(UEdge e){ deba@1912: return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e; deba@1912: } deba@2397: deba@2397: ///\brief Returns the value of the total cost of the spanning tree. deba@2397: /// deba@2397: /// Returns the value of the total cost of the spanning tree. deba@2397: Value treeValue() const { deba@2397: Value value = 0; deba@2397: for(NodeIt i(*graph); i!= INVALID; ++i){ deba@2397: if ((*_pred)[i] != INVALID) value += (*cost)[(*_pred)[i]]; deba@2397: } deba@2397: return value; deba@2397: } deba@1912: ///@} deba@1912: }; deba@1912: deba@1912: deba@1912: /// \ingroup spantree deba@1912: /// deba@1912: /// \brief Function type interface for Prim algorithm. deba@1912: /// deba@1912: /// Function type interface for Prim algorithm. deba@1912: /// \param graph the UGraph that the algorithm runs on deba@1912: /// \param cost the CostMap of the edges deba@1912: /// \retval tree the EdgeMap that contains whether an edge is in deba@1912: /// the spanning tree or not deba@2397: /// \return The total cost of the spanning tree deba@1912: /// deba@1912: ///\sa Prim deba@1912: template deba@2397: typename CostMap::Value prim(const Graph& graph, deba@2397: const CostMap& cost, deba@2397: TreeMap& tree){ deba@2397: typename Prim:: deba@2397: template DefTreeMap:: deba@1912: Create prm(graph,cost); deba@1912: prm.treeMap(tree); deba@1912: prm.run(); deba@2397: return prm.treeValue(); deba@2397: } deba@2397: deba@2397: /// \ingroup spantree deba@2397: /// deba@2397: /// \brief Function type interface for Prim algorithm. deba@2397: /// deba@2397: /// Function type interface for Prim algorithm. deba@2397: /// \param graph the UGraph that the algorithm runs on deba@2397: /// \param cost the CostMap of the edges deba@2397: /// the spanning tree or not deba@2397: /// \return The total cost of the spanning tree deba@2397: /// deba@2397: ///\sa Prim deba@2397: template deba@2397: typename CostMap::Value prim(const Graph& graph, deba@2397: const CostMap& cost){ deba@2397: typename Prim:: deba@2397: Create prm(graph,cost); deba@2397: prm.run(); deba@2397: return prm.treeValue(); deba@1979: } deba@1912: deba@1912: } //END OF NAMESPACE LEMON deba@1912: deba@1912: #endif