# HG changeset patch # User deba # Date 1173268613 0 # Node ID a501140ce878a0bad269d33848238ae8c6a9acea # Parent 658c04d74729f1ebdb4a9ca126555eb8a4c6be33 Some design correction diff -r 658c04d74729 -r a501140ce878 lemon/prim.h --- a/lemon/prim.h Wed Mar 07 11:56:14 2007 +0000 +++ b/lemon/prim.h Wed Mar 07 11:56:53 2007 +0000 @@ -401,16 +401,16 @@ 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), - _tree(NULL), local_tree(false), - _processed(NULL), local_processed(false), - _heap_cross_ref(NULL), local_heap_cross_ref(false), - _heap(NULL), local_heap(false) + _pred(0), local_pred(false), + _tree(0), local_tree(false), + _processed(0), local_processed(false), + _heap_cross_ref(0), local_heap_cross_ref(false), + _heap(0), local_heap(false) { checkConcept(); } @@ -425,7 +425,7 @@ } ///\brief Sets the cost map. - + /// ///Sets the cost map. ///\return (*this) Prim &costMap(const CostMap &m){ @@ -434,7 +434,7 @@ } ///\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 @@ -450,7 +450,7 @@ } ///\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 @@ -467,7 +467,7 @@ } ///\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 @@ -501,7 +501,7 @@ ///@{ ///\brief Initializes the internal data structures. - + /// ///Initializes the internal data structures. /// void init(){ @@ -515,7 +515,7 @@ } ///\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 @@ -526,7 +526,7 @@ } } ///\brief Processes the next node in the priority heap - + /// ///Processes the next node in the priority heap. /// ///\return The processed node. @@ -559,7 +559,7 @@ } ///\brief Next node to be processed. - + /// ///Next node to be processed. /// ///\return The next node to be processed or INVALID if the priority heap @@ -568,19 +568,22 @@ 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 @@ -595,7 +598,7 @@ } ///\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 @@ -610,7 +613,7 @@ } ///\brief Runs %Prim algorithm. - + /// ///This method runs the %Prim algorithm ///in order to compute the ///minimum spanning tree (or minimum spanning forest). @@ -627,17 +630,17 @@ } ///\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(); - /// d.addSource(s); - /// d.start(); + /// p.init(); + /// p.addSource(s); + /// p.start(); ///\endcode ///\note If the graph has more than one components, the method ///will compute the minimun spanning tree for only one component. @@ -661,111 +664,127 @@ ///\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, - ///i.e. it returns the edge from where \c v was reached. For a source node - ///or an unreachable node it is \ref INVALID. - ///The minimum spanning tree used here is equal to the minimum spanning tree used - ///in \ref predNode(). \pre \ref run() or \ref start() must be called before - ///using this function. + ///For a node \c v it returns the 'previous edge' of the minimum + ///spanning tree, i.e. it returns the edge from where \c v was + ///reached. For a source node or an unreachable node it is \ref + ///INVALID. The minimum spanning tree used here is equal to the + ///minimum spanning tree used in \ref predNode(). + ///\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. - - ///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 - ///or an unreachable node it is \ref INVALID. - //The minimum spanning tree used here is equal to the minimum spanning - ///tree used in \ref predEdge(). \pre \ref run() or \ref start() must be called - ///before using this function. + ///\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 or an unreachable node it is \ref + ///INVALID. //The minimum spanning tree used here is equal to the + ///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. - - ///Returns a reference to the NodeMap of the edges of the + ///\brief 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 - ///the minimum spanning tree. + ///minimum spanning tree. The value of the map is \c true only if + ///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 - ///treeMap(TreeMap&) function (after the execution) to set an UEdgeMap with the - ///edges of the minimum spanning tree in O(n) time where n is the number of - ///nodes in the graph. - ///\pre \ref run() or \ref start() must be called before using this function. + ///If it is not set before the execution of the algorithm, use the + ///\ref treeMap(TreeMap&) function (after the execution) to set an + ///UEdgeMap with the edges of the minimum spanning tree in O(n) + ///time where n is the number of nodes in the graph. + ///\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 - void quickTreeEdges( - TreeMap& tree, - const typename TreeMap::Value& tree_edge_value=true) const { + void quickTreeEdges(TreeMap& tree) 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. - - template - void treeEdges( - TreeMap& tree, - const typename TreeMap::Value& tree_edge_value=true, - const typename TreeMap::Value& tree_default_value=false) const { - for(typename ItemSetTraits::ItemIt i(*graph);i!=INVALID;++i) - tree.set(i,tree_default_value); - for(NodeIt i(*graph);i!=INVALID;++i){ - if((*_pred)[i]!=INVALID) tree.set((*_pred)[i],tree_edge_value); + ///\pre \ref run() or \ref start() must be called before using + ///this function. + template + void treeEdges(TreeMap& tree) const { + typedef typename ItemSetTraits::ItemIt TreeMapIt; + for(TreeMapIt i(*graph); i != INVALID; ++i) { + tree.set(i,false); + } + for(NodeIt i(*graph); i != INVALID; ++i){ + if((*_pred)[i] != INVALID) tree.set((*_pred)[i],true); } } ///\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 - ///minimum spanning tree. - ///\pre \ref run() or \ref start() must be called before using this function. /// + ///Returns \c true if \c v is processed, i.e. \c v is already + ///connencted to the minimum spanning tree. \pre \ref run() or + ///\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; + } ///@} }; @@ -779,14 +798,39 @@ /// \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 - void prim(const Graph& graph, const CostMap& cost,TreeMap& tree){ - typename Prim::template DefTreeMap:: + typename CostMap::Value prim(const Graph& graph, + const CostMap& cost, + TreeMap& tree){ + typename Prim:: + template DefTreeMap:: 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 + typename CostMap::Value prim(const Graph& graph, + const CostMap& cost){ + typename Prim:: + Create prm(graph,cost); + prm.run(); + return prm.treeValue(); } } //END OF NAMESPACE LEMON