Changeset 2397:a501140ce878 in lemon-0.x

Timestamp:

03/07/07 12:56:53 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3228

Message:

Some design correction

File:

• lemon/prim.h (modified) (21 diffs)

lemon/prim.h

@@ -402 +402 @@
     
     ///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<concepts::UGraph, UGraph>();
@@ -426 +426 @@
 
     ///\brief Sets the cost map.
-
+    ///
     ///Sets the cost map.
     ///\return <tt> (*this) </tt>
@@ -435 +435 @@
 
     ///\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(),
@@ -451 +451 @@
 
     ///\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(),
@@ -468 +468 @@
 
     ///\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(),
@@ -502 +502 @@
 
     ///\brief Initializes the internal data structures.
-
+    ///
     ///Initializes the internal data structures.
     ///
@@ -516 +516 @@
     
     ///\brief Adds a new source node.
-
+    ///
     ///Adds a new source node to the priority heap.
     ///
@@ -527 +527 @@
     }
     ///\brief Processes the next node in the priority heap
-
+    ///
     ///Processes the next node in the priority heap.
     ///
@@ -560 +560 @@
 
     ///\brief Next node to be processed.
-    
+    ///
     ///Next node to be processed.
     ///
@@ -569 +569 @@
     }
  
-    ///\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
     ///
@@ -581 +584 @@
     
     ///\brief Executes the algorithm.
-
+    ///
     ///Executes the algorithm.
     ///
@@ -596 +599 @@
     
     ///\brief Executes the algorithm until a condition is met.
-
+    ///
     ///Executes the algorithm until a condition is met.
     ///
@@ -611 +614 @@
     
     ///\brief Runs %Prim algorithm.
-    
+    ///
     ///This method runs the %Prim algorithm
     ///in order to compute the
@@ -628 +631 @@
 
     ///\brief Runs %Prim algorithm from node \c s.
-    
+    ///
     ///This method runs the %Prim algorithm from node \c s
     ///in order to
@@ -634 +637 @@
     ///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
@@ -662 +665 @@
     ///\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;}
  
@@ -691 +699 @@
 
     ///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
@@ -709 +719 @@
     ///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(
-        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
@@ -728 +737 @@
     ///\c tree_default_value or \c false by default.
     ///
-    ///\pre \ref run() or \ref start() must be called before using this function.
-
-    template<class TreeMap>
-    void treeEdges(
-        TreeMap& tree,
-        const typename TreeMap::Value& tree_edge_value=true,
-        const typename TreeMap::Value& tree_default_value=false) const {
-      for(typename ItemSetTraits<UGraph,UEdge>::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 <class TreeMap>
+    void treeEdges(TreeMap& tree) const {
+      typedef typename ItemSetTraits<UGraph,UEdge>::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
@@ -767 +775 @@
       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;
+    }
     ///@}
   };
@@ -780 +799 @@
   /// \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 Prim<Graph,CostMap>::template DefTreeMap<TreeMap>::
+  typename CostMap::Value prim(const Graph& graph, 
+                               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