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 <lemon/list_graph.h>
deba@1912: #include <lemon/bin_heap.h>
deba@1993: #include <lemon/bits/invalid.h>
deba@1912: #include <lemon/error.h>
deba@1912: #include <lemon/maps.h>
deba@1993: #include <lemon/bits/traits.h>
deba@1912: 
alpar@2260: #include <lemon/concepts/ugraph.h>
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<class GR, class CM>
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<int>.
deba@1912:     typedef typename UGraph::template NodeMap<int> 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<typename CM::Value,
deba@1912: 		    HeapCrossRef, std::less<Value> > 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<typename GR::UEdge> 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<typename UGraph::UEdge,bool> 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<bool>.
deba@1912:     typedef NullMap<typename UGraph::Node,bool> 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<int>".  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<GR,CM>".  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 <typename GR,
deba@2030: 	    typename CM,
deba@1912: 	    typename TR>
deba@1912: #else
deba@1912:   template <typename GR=ListUGraph,
deba@2030: 	    typename CM=typename GR::template UEdgeMap<int>,
deba@2030: 	    typename TR=PrimDefaultTraits<GR,CM> >
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 <class T>
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 <class T>
deba@1912:     struct DefPredMap 
deba@1912:       : public Prim< UGraph, CostMap, DefPredMapTraits<T> > {
deba@1912:       typedef Prim< UGraph, CostMap, DefPredMapTraits<T> > Create;
deba@1912:     };
deba@1912:     
deba@1912:     template <class T>
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 <class T>
deba@1912:     struct DefProcessedMap 
deba@1912:       : public Prim< UGraph, CostMap, DefProcessedMapTraits<T> > { 
deba@1912:       typedef Prim< UGraph, CostMap, DefProcessedMapTraits<T> > Create;
deba@1912:     };
deba@1912:     
deba@1912:     struct DefGraphProcessedMapTraits : public Traits {
deba@1912:       typedef typename UGraph::template NodeMap<bool> 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 <class H, class CR>
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 <class H, class CR = typename UGraph::template NodeMap<int> >
deba@1912:     struct DefHeap
deba@1912:       : public Prim< UGraph, CostMap, DefHeapTraits<H, CR> > {
deba@1912:       typedef Prim< UGraph, CostMap, DefHeapTraits<H, CR> > Create;
deba@1912:     };
deba@1912: 
deba@1912:     template <class H, class CR>
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 <class H, class CR = typename UGraph::template NodeMap<int> >
deba@1912:     struct DefStandardHeap
deba@1912:       : public Prim< UGraph, CostMap, DefStandardHeapTraits<H, CR> > { 
deba@1912:       typedef Prim< UGraph, CostMap, DefStandardHeapTraits<H, CR> > 
deba@1912:       Create;
deba@1912:     };
deba@1912: 
deba@1912:     template <class TM>
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 <class TM>
deba@1912:     struct DefTreeMap
deba@1912:       : public Prim< UGraph, CostMap, DefTreeMapTraits<TM> > {
deba@1912:       typedef Prim< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
deba@1912:     };    
deba@1912: 
deba@1912:     struct DefGraphTreeMapTraits : public Traits {
deba@1912:       typedef typename UGraph::template NodeMap<bool> 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<concepts::UGraph, UGraph>();
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 <tt> (*this) </tt>
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 <tt> (*this) </tt>
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 <tt> (*this) </tt>
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 <tt> (*this) </tt>
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 <tt>nm[v]==true</tt>.
deba@1912:     template<class NodeBoolMap>
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<class TreeMap>
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 <class TreeMap>
deba@2397:     void treeEdges(TreeMap& tree) const {
deba@2397:       typedef typename ItemSetTraits<UGraph,UEdge>::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<class Graph,class CostMap,class TreeMap>
deba@2397:   typename CostMap::Value prim(const Graph& graph, 
deba@2397:                                const CostMap& cost,
deba@2397:                                TreeMap& tree){
deba@2397:     typename Prim<Graph,CostMap>::
deba@2397:       template DefTreeMap<TreeMap>::
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<class Graph,class CostMap,class TreeMap>
deba@2397:   typename CostMap::Value prim(const Graph& graph, 
deba@2397:                                const CostMap& cost){
deba@2397:     typename Prim<Graph,CostMap>::
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