# Changeset 2397:a501140ce878 in lemon-0.x

Ignore:
Timestamp:
03/07/07 12:56:53 (16 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3228
Message:

Some design correction

File:
1 edited

Unmodified
Added
Removed
• ## lemon/prim.h

 r2391 ///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(); ///\brief Sets the cost map. /// ///Sets the cost map. ///\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(), ///\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(), ///\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(), ///\brief Initializes the internal data structures. /// ///Initializes the internal data structures. /// ///\brief Adds a new source node. /// ///Adds a new source node to the priority heap. /// } ///\brief Processes the next node in the priority heap /// ///Processes the next node in the priority heap. /// ///\brief Next node to be processed. /// ///Next node to be processed. /// } ///\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 /// ///\brief Executes the algorithm. /// ///Executes the algorithm. /// ///\brief Executes the algorithm until a condition is met. /// ///Executes the algorithm until a condition is met. /// ///\brief Runs %Prim algorithm. /// ///This method runs the %Prim algorithm ///in order to compute the ///\brief Runs %Prim algorithm from node \c s. /// ///This method runs the %Prim algorithm from node \c s ///in order to ///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 ///\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;} ///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 ///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 ///\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 (*_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; } ///@} }; /// \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
Note: See TracChangeset for help on using the changeset viewer.