lemon-0.x: comparison lemon/prim.h

equal deleted inserted replaced

-:07336b4933ea
+:d93dd4011ef5
 Prim() {}
 public:
 ///Constructor.
+///
 ///\param _graph the graph the algorithm will run on.
 ///\param _cost the cost map used by the algorithm.
 Prim(const UGraph& _graph, const CostMap& _cost) :
 graph(&_graph), cost(&_cost),
-_pred(NULL), local_pred(false),
+_pred(0), local_pred(false),
-_tree(NULL), local_tree(false),
+_tree(0), local_tree(false),
-_processed(NULL), local_processed(false),
+_processed(0), local_processed(false),
-_heap_cross_ref(NULL), local_heap_cross_ref(false),
+_heap_cross_ref(0), local_heap_cross_ref(false),
-_heap(NULL), local_heap(false)
+_heap(0), local_heap(false)
 {
 checkConcept<concepts::UGraph, UGraph>();
 }
 ///Destructor.
 if(local_heap_cross_ref) delete _heap_cross_ref;
 if(local_heap) delete _heap;
 }
 ///\brief Sets the cost map.
+///
 ///Sets the cost map.
 ///\return <tt> (*this) </tt>
 Prim &costMap(const CostMap &m){
 cost = &m;
 return *this;
 }
 ///\brief Sets the map storing the predecessor edges.
+///
 ///Sets the map storing the predecessor edges.
 ///If you don't use this function before calling \ref run(),
 ///it will allocate one. The destuctor deallocates this
 ///automatically allocated map, of course.
 ///\return <tt> (*this) </tt>
 _pred = &m;
 return *this;
 }
 ///\brief Sets the map storing the tree edges.
+///
 ///Sets the map storing the tree edges.
 ///If you don't use this function before calling \ref run(),
 ///it will allocate one. The destuctor deallocates this
 ///automatically allocated map, of course.
 ///By default this is a NullMap.
 _tree = &m;
 return *this;
 }
 ///\brief Sets the heap and the cross reference used by algorithm.
+///
 ///Sets the heap and the cross reference used by algorithm.
 ///If you don't use this function before calling \ref run(),
 ///it will allocate one. The destuctor deallocates this
 ///automatically allocated map, of course.
 ///\return <tt> (*this) </tt>
 ///computation.
 ///@{
 ///\brief Initializes the internal data structures.
+///
 ///Initializes the internal data structures.
 ///
 void init(){
 create_maps();
 _heap->clear();
 	_heap_cross_ref->set(u,Heap::PRE_HEAP);
 }
 }
 ///\brief Adds a new source node.
+///
 ///Adds a new source node to the priority heap.
 ///
 ///It checks if the node has already been added to the heap and
 ///it is pushed to the heap only if it was not in the heap.
 void addSource(Node s){
 if(_heap->state(s) != Heap::IN_HEAP) {
 	_heap->push(s,Value());
 }
 }
 ///\brief Processes the next node in the priority heap
+///
 ///Processes the next node in the priority heap.
 ///
 ///\return The processed node.
 ///
 ///\warning The priority heap must not be empty!
 if ((*_pred)[v]!=INVALID)_tree->set((*_pred)[v],true);
 return v;
 }
 ///\brief Next node to be processed.
+///
 ///Next node to be processed.
 ///
 ///\return The next node to be processed or INVALID if the priority heap
 /// is empty.
 Node nextNode(){
 return _heap->empty()?_heap->top():INVALID;
 }
-///\brief Returns \c false if there are nodes to be processed in the priority heap
+///\brief Returns \c false if there are nodes to be processed in
+///the priority heap
 ///
 ///Returns \c false if there are nodes
 ///to be processed in the priority heap
 bool emptyQueue() { return _heap->empty(); }
-///\brief Returns the number of the nodes to be processed in the priority heap
+///\brief Returns the number of the nodes to be processed in the
+///priority heap
+///
 ///Returns the number of the nodes to be processed in the priority heap
 ///
 int queueSize() { return _heap->size(); }
 ///\brief Executes the algorithm.
+///
 ///Executes the algorithm.
 ///
 ///\pre init() must be called and at least one node should be added
 ///with addSource() before using this function.
 ///
 void start(){
 while ( !_heap->empty() ) processNextNode();
 }
 ///\brief Executes the algorithm until a condition is met.
+///
 ///Executes the algorithm until a condition is met.
 ///
 ///\pre init() must be called and at least one node should be added
 ///with addSource() before using this function.
 ///
 while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
 if ( !_heap->empty() ) _processed->set(_heap->top(),true);
 }
 ///\brief Runs %Prim algorithm.
+///
 ///This method runs the %Prim algorithm
 ///in order to compute the
 ///minimum spanning tree (or minimum spanning forest).
 ///The method also works on graphs that has more than one components.
 ///In this case it computes the minimum spanning forest.
 	}
 }
 }
 ///\brief Runs %Prim algorithm from node \c s.
+///
 ///This method runs the %Prim algorithm from node \c s
 ///in order to
 ///compute the
 ///minimun spanning tree
 ///
-///\note d.run(s) is just a shortcut of the following code.
+///\note p.run(s) is just a shortcut of the following code.
 ///\code
-///  d.init();
+///  p.init();
-///  d.addSource(s);
+///  p.addSource(s);
-///  d.start();
+///  p.start();
 ///\endcode
 ///\note If the graph has more than one components, the method
 ///will compute the minimun spanning tree for only one component.
 ///
 ///See \ref run() if you want to compute the minimal spanning forest.
 ///@{
 ///\brief Returns the 'previous edge' of the minimum spanning tree.
-///For a node \c v it returns the 'previous edge' of the minimum spanning tree,
+///For a node \c v it returns the 'previous edge' of the minimum
-///i.e. it returns the edge from where \c v was reached. For a source node
+///spanning tree, i.e. it returns the edge from where \c v was
-///or an unreachable node it is \ref INVALID.
+///reached. For a source node or an unreachable node it is \ref
-///The minimum spanning tree used here is equal to the minimum spanning tree used
+///INVALID.  The minimum spanning tree used here is equal to the
-///in \ref predNode().  \pre \ref run() or \ref start() must be called before
+///minimum spanning tree used in \ref predNode().
-///using this function.
+///\pre \ref run() or \ref start() must be called before using
+///this function.
 UEdge predEdge(Node v) const { return (*_pred)[v]; }
-///\brief Returns the 'previous node' of the minimum spanning tree.
+///\brief Returns the 'previous node' of the minimum spanning
+///tree.
-///For a node \c v it returns the 'previous node' of the minimum spanning tree,
+///
-///i.e. it returns the node from where \c v was reached. For a source node
+///For a node \c v it returns the 'previous node' of the minimum
-///or an unreachable node it is \ref INVALID.
+///spanning tree, i.e. it returns the node from where \c v was
-//The minimum spanning tree used here is equal to the minimum spanning
+///reached. For a source node or an unreachable node it is \ref
-///tree used in \ref predEdge().  \pre \ref run() or \ref start() must be called
+///INVALID.  //The minimum spanning tree used here is equal to the
-///before using this function.
+///minimum spanning tree used in \ref predEdge().
+///\pre \ref run() or \ref start() must be called before using
+///this function.
 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 				  graph->source((*_pred)[v]); }
-///\brief Returns a reference to the NodeMap of the edges of the minimum spanning tree.
+///\brief Returns a reference to the NodeMap of the edges of the
-///Returns a reference to the NodeMap of the edges of the
 ///minimum spanning tree.
-///\pre \ref run() or \ref start() must be called before using this function.
+///
+///Returns a reference to the NodeMap of the edges of the minimum
+///spanning tree.
+///\pre \ref run() or \ref start() must be called before using
+///this function.
 const PredMap &predMap() const { return *_pred;}
 ///\brief Returns a reference to the tree edges map.
 ///Returns a reference to the TreeEdgeMap of the edges of the
-///minimum spanning tree. The value of the map is \c true only if the edge is in
+///minimum spanning tree. The value of the map is \c true only if
-///the minimum spanning tree.
+///the edge is in the minimum spanning tree.
+///
 ///\warning By default, the TreeEdgeMap is a NullMap.
 ///
-///If it is not set before the execution of the algorithm, use the \ref
+///If it is not set before the execution of the algorithm, use the
-///treeMap(TreeMap&) function (after the execution) to set an UEdgeMap with the
+///\ref treeMap(TreeMap&) function (after the execution) to set an
-///edges of the minimum spanning tree in O(n) time where n is the number of
+///UEdgeMap with the edges of the minimum spanning tree in O(n)
-///nodes in the graph.
+///time where n is the number of nodes in the graph.
-///\pre \ref run() or \ref start() must be called before using this function.
+///\pre \ref run() or \ref start() must be called before using
+///this function.
 const TreeMap &treeMap() const { return *_tree;}
 ///\brief Sets the tree edges map.
+///
 ///Sets the TreeMap of the edges of the minimum spanning tree.
 ///The map values belonging to the edges of the minimum
 ///spanning tree are set to \c tree_edge_value or \c true by default,
 ///the other map values remain untouched.
 ///
-///\pre \ref run() or \ref start() must be called before using this function.
+///\pre \ref run() or \ref start() must be called before using
+///this function.
 template<class TreeMap>
-void quickTreeEdges(
+void quickTreeEdges(TreeMap& tree) const {
-TreeMap& tree,
-const typename TreeMap::Value& tree_edge_value=true) const {
 for(NodeIt i(*graph);i!=INVALID;++i){
-if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
+if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],true);
 }
 }
 ///\brief Sets the tree edges map.
+///
 ///Sets the TreeMap of the edges of the minimum spanning tree.
 ///The map values belonging to the edges of the minimum
 ///spanning tree are set to \c tree_edge_value or \c true by default while
 ///the edge values not belonging to the minimum spanning tree are set to
 ///\c tree_default_value or \c false by default.
 ///
-///\pre \ref run() or \ref start() must be called before using this function.
+///\pre \ref run() or \ref start() must be called before using
+///this function.
-template<class TreeMap>
+template <class TreeMap>
-void treeEdges(
+void treeEdges(TreeMap& tree) const {
-TreeMap& tree,
+typedef typename ItemSetTraits<UGraph,UEdge>::ItemIt TreeMapIt;
-const typename TreeMap::Value& tree_edge_value=true,
+for(TreeMapIt i(*graph); i != INVALID; ++i) {
-const typename TreeMap::Value& tree_default_value=false) const {
+	tree.set(i,false);
-for(typename ItemSetTraits<UGraph,UEdge>::ItemIt i(*graph);i!=INVALID;++i)
+}
-	tree.set(i,tree_default_value);
+for(NodeIt i(*graph); i != INVALID; ++i){
-for(NodeIt i(*graph);i!=INVALID;++i){
+if((*_pred)[i] != INVALID) tree.set((*_pred)[i],true);
-if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value);
 }
 }
 ///\brief Checks if a node is reachable from the starting node.
+///
 ///Returns \c true if \c v is reachable from the starting node.
 ///\warning The source nodes are inditated as unreached.
-///\pre \ref run() or \ref start() must be called before using this function.
+///\pre \ref run() or \ref start() must be called before using
+///this function.
 ///
 bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
 ///\brief Checks if a node is processed.
+///
-///Returns \c true if \c v is processed, i.e. \c v is already connencted to the
+///Returns \c true if \c v is processed, i.e. \c v is already
-///minimum spanning tree.
+///connencted to the minimum spanning tree.  \pre \ref run() or
-///\pre \ref run() or \ref start() must be called before using this function.
+///\ref start() must be called before using this function.
-///
 bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
 ///\brief Checks if an edge is in the spanning tree or not.
+///
 ///Checks if an edge is in the spanning tree or not.
 ///\param e is the edge that will be checked
 ///\return \c true if e is in the spanning tree, \c false otherwise
 bool tree(UEdge e){
 return (*_pred)[*graph.source(e)]==e || (*_pred)[*graph.target(e)]==e;
 }
+///\brief Returns the value of the total cost of the spanning tree.
+///
+/// Returns the value of the total cost of the spanning tree.
+Value treeValue() const {
+Value value = 0;
+for(NodeIt i(*graph); i!= INVALID; ++i){
+if ((*_pred)[i] != INVALID) value += (*cost)[(*_pred)[i]];
+}
+return value;
+}
 ///@}
 };
 /// \ingroup spantree
 /// Function type interface for Prim algorithm.
 /// \param graph the UGraph that the algorithm runs on
 /// \param cost the CostMap of the edges
 /// \retval tree the EdgeMap that contains whether an edge is in
 /// the spanning tree or not
+/// \return The total cost of the spanning tree
 ///
 ///\sa Prim
 template<class Graph,class CostMap,class TreeMap>
-void prim(const Graph& graph, const CostMap& cost,TreeMap& tree){
+typename CostMap::Value prim(const Graph& graph,
-typename Prim<Graph,CostMap>::template DefTreeMap<TreeMap>::
+const CostMap& cost,
+TreeMap& tree){
+typename Prim<Graph,CostMap>::
+template DefTreeMap<TreeMap>::
 Create prm(graph,cost);
 prm.treeMap(tree);
 prm.run();
+return prm.treeValue();
 }
+/// \ingroup spantree
+///
+/// \brief Function type interface for Prim algorithm.
+///
+/// Function type interface for Prim algorithm.
+/// \param graph the UGraph that the algorithm runs on
+/// \param cost the CostMap of the edges
+/// the spanning tree or not
+/// \return The total cost of the spanning tree
+///
+///\sa Prim
+template<class Graph,class CostMap,class TreeMap>
+typename CostMap::Value prim(const Graph& graph,
+const CostMap& cost){
+typename Prim<Graph,CostMap>::
+Create prm(graph,cost);
+prm.run();
+return prm.treeValue();
+}
 } //END OF NAMESPACE LEMON
 #endif

changeset 2409	fe0a8fe16271
parent 2391	14a343be7a5a
child 2490	31a93dd6f714