# HG changeset patch
# User deba
# Date 1178527658 0
# Node ID 02c7076bf8942c39badd762e8dc49f693fc00c73
# Parent  0c941c524b47673de875b00c37680a7d0290ad52
Small improvements in MinMeanCycle class.

Patch from Peter Kovacs

diff -r 0c941c524b47 -r 02c7076bf894 lemon/min_mean_cycle.h
--- a/lemon/min_mean_cycle.h	Tue Apr 24 09:39:01 2007 +0000
+++ b/lemon/min_mean_cycle.h	Mon May 07 08:47:38 2007 +0000
@@ -21,7 +21,7 @@
 
 /// \ingroup min_cost_flow
 ///
-/// \file 
+/// \file
 /// \brief Karp algorithm for finding a minimum mean cycle.
 
 #include <lemon/graph_utils.h>
@@ -44,13 +44,8 @@
   ///
   /// \author Peter Kovacs
 
-#ifdef DOXYGEN
-  template <typename Graph, typename LengthMap>
-#else
   template <typename Graph,
     typename LengthMap = typename Graph::template EdgeMap<int> >
-#endif
-
   class MinMeanCycle
   {
     typedef typename Graph::Node Node;
@@ -65,7 +60,6 @@
     typedef typename Graph::template NodeMap<Edge> PredNodeMap;
     typedef Path<Graph> Path;
     typedef std::vector<Node> NodeVector;
-    typedef typename NodeVector::iterator NodeVectorIt;
 
   protected:
 
@@ -89,30 +83,30 @@
   protected:
 
     /// \brief Node map for storing path data.
-    /// 
+    ///
     /// Node map for storing path data of all nodes in the current
-    /// component. dmap[v][k] is the length of a shortest directed walk 
+    /// component. dmap[v][k] is the length of a shortest directed walk
     /// to node v from the starting node containing exactly k edges.
     PathDataNodeMap dmap;
-    
+
     /// \brief The directed graph the algorithm runs on.
-    const Graph& graph;
+    const Graph &graph;
     /// \brief The length of the edges.
-    const LengthMap& length;
-    
+    const LengthMap &length;
+
     /// \brief The total length of the found cycle.
     Length cycle_length;
     /// \brief The number of edges in the found cycle.
     int cycle_size;
-    /// \brief A node for obtaining a minimum mean cycle. 
+    /// \brief A node for obtaining a minimum mean cycle.
     Node cycle_node;
 
     /// \brief The found cycle.
     Path *cycle_path;
-    /// \brief The algorithm uses local \ref lemon::Path "Path" 
+    /// \brief The algorithm uses local \ref lemon::Path "Path"
     /// structure to store the found cycle.
     bool local_path;
-    
+
     /// \brief Node map for identifying strongly connected components.
     IntNodeMap comp;
     /// \brief The number of strongly connected components.
@@ -123,7 +117,7 @@
     NodeVector nodes;
     /// \brief The processed nodes in the last round.
     NodeVector process;
-    
+
   public :
 
     /// \brief The constructor of the class.
@@ -132,15 +126,15 @@
     ///
     /// \param _graph The directed graph the algorithm runs on.
     /// \param _length The length (cost) of the edges.
-    MinMeanCycle( const Graph& _graph,
-		  const LengthMap& _length ) :
+    MinMeanCycle( const Graph &_graph,
+		  const LengthMap &_length ) :
       graph(_graph), length(_length), dmap(_graph), comp(_graph),
       cycle_length(0), cycle_size(-1), cycle_node(INVALID),
       cycle_path(NULL), local_path(false)
     { }
 
     /// \brief The destructor of the class.
-    ~MinMeanCycle() { 
+    ~MinMeanCycle() {
       if (local_path) delete cycle_path;
     }
 
@@ -156,12 +150,12 @@
       }
       // Creating vectors for all nodes
       int n = nodes.size();
-      for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
-	dmap[*vi].resize(n + 1);
+      for (int i = 0; i < nodes.size(); ++i) {
+	dmap[nodes[i]].resize(n + 1);
       }
     }
-    
-    /// \brief Processes all rounds of computing required path data for 
+
+    /// \brief Processes all rounds of computing required path data for
     /// the current component.
     void processRounds() {
       dmap[nodes[0]][0] = PathData(true, 0);
@@ -173,30 +167,28 @@
 	dmap[v][1] = PathData(true, length[e], e);
 	process.push_back(v);
       }
-      // Processing other rounds 
+      // Processing other rounds
       int n = nodes.size(), k;
-      for (k = 2; k <= n && process.size() < n; ++k) {
+      for (k = 2; k <= n && process.size() < n; ++k)
 	processNextBuildRound(k);
-      }
-      for ( ; k <= n; ++k) {
+      for ( ; k <= n; ++k)
 	processNextFullRound(k);
-      }
     }
-    
+
     /// \brief Processes one round of computing required path data and
     /// rebuilds \ref process vector.
     void processNextBuildRound(int k) {
       NodeVector next;
-      for (NodeVectorIt ui = process.begin(); ui != process.end(); ++ui) {
-	for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
+      for (int i = 0; i < process.size(); ++i) {
+	for (OutEdgeIt e(graph, process[i]); e != INVALID; ++e) {
 	  Node v = graph.target(e);
 	  if (comp[v] != comp_cnt) continue;
 	  if (!dmap[v][k].found) {
 	    next.push_back(v);
-	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
+	    dmap[v][k] = PathData(true, dmap[process[i]][k-1].dist + length[e], e);
 	  }
-	  else if (dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist) {
-	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
+	  else if (dmap[process[i]][k-1].dist + length[e] < dmap[v][k].dist) {
+	    dmap[v][k] = PathData(true, dmap[process[i]][k-1].dist + length[e], e);
 	  }
 	}
       }
@@ -206,58 +198,58 @@
     /// \brief Processes one round of computing required path data
     /// using \ref nodes vector instead of \ref process vector.
     void processNextFullRound(int k) {
-      for (NodeVectorIt ui = nodes.begin(); ui != nodes.end(); ++ui) {
-	for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
+      for (int i = 0; i < nodes.size(); ++i) {
+	for (OutEdgeIt e(graph, nodes[i]); e != INVALID; ++e) {
 	  Node v = graph.target(e);
 	  if (comp[v] != comp_cnt) continue;
-	  if ( !dmap[v][k].found || 
-	       dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist ) {
-	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
+	  if ( !dmap[v][k].found ||
+	       dmap[nodes[i]][k-1].dist + length[e] < dmap[v][k].dist ) {
+	    dmap[v][k] = PathData(true, dmap[nodes[i]][k-1].dist + length[e], e);
 	  }
 	}
       }
     }
-    
-    /// \brief Finds the minimum cycle mean value in the current 
+
+    /// \brief Finds the minimum cycle mean value in the current
     /// component.
     bool findCurrentMin(Length &min_length, int &min_size, Node &min_node) {
       bool found_min = false;
-      for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
+      for (int i = 0; i < nodes.size(); ++i) {
 	int n = nodes.size();
-	if (!dmap[*vi][n].found) continue;
+	if (!dmap[nodes[i]][n].found) continue;
 	Length len;
 	int size;
 	bool found_one = false;
 	for (int k = 0; k < n; ++k) {
-	  if (!dmap[*vi][k].found) continue;
-	  Length _len = dmap[*vi][n].dist - dmap[*vi][k].dist;
-	  int _size = n - k; 
+	  if (!dmap[nodes[i]][k].found) continue;
+	  Length _len = dmap[nodes[i]][n].dist - dmap[nodes[i]][k].dist;
+	  int _size = n - k;
 	  if (!found_one || len * _size < _len * size) {
 	    found_one = true;
 	    len = _len;
 	    size = _size;
 	  }
 	}
-	if ( found_one && 
+	if ( found_one &&
 	     (!found_min || len * min_size < min_length * size) ) {
 	  found_min = true;
 	  min_length = len;
 	  min_size = size;
-	  min_node = *vi;
+	  min_node = nodes[i];
 	}
       }
       return found_min;
     }
-    
-  public:  
-    
+
+  public:
+
     /// \brief Runs the algorithm.
     ///
     /// Runs the algorithm.
     ///
     /// \return \c true if a cycle exists in the graph.
     ///
-    /// \note Apart from the return value, m.run() is just a shortcut 
+    /// \note Apart from the return value, m.run() is just a shortcut
     /// of the following code.
     /// \code
     ///   m.init();
@@ -269,7 +261,7 @@
       findMinMean();
       return findCycle();
     }
-    
+
     /// \brief Initializes the internal data structures.
     void init() {
       comp_num = stronglyConnectedComponents(graph, comp);
@@ -285,20 +277,20 @@
     /// mean value in the graph.
     ///
     /// \return \c true if a cycle exists in the graph.
-    /// 
+    ///
     /// \pre \ref init() must be called before using this function.
     bool findMinMean() {
       cycle_node = INVALID;
       for (comp_cnt = 0; comp_cnt < comp_num; ++comp_cnt) {
 	initCurrent();
 	processRounds();
-	
+
 	Length min_length;
 	int min_size;
 	Node min_node;
 	bool found_min = findCurrentMin(min_length, min_size, min_node);
-	
-	if ( found_min && (cycle_node == INVALID || 
+
+	if ( found_min && (cycle_node == INVALID ||
 	     min_length * cycle_size < cycle_length * min_size) ) {
 	  cycle_length = min_length;
 	  cycle_size = min_size;
@@ -307,15 +299,15 @@
       }
       return (cycle_node != INVALID);
     }
-    
+
     /// \brief Finds a critical (minimum mean) cycle.
     ///
     /// Finds a critical (minimum mean) cycle using the path data
     /// stored in \ref dmap.
     ///
     /// \return \c true if a cycle exists in the graph.
-    /// 
-    /// \pre \ref init() and \ref findMinMean() must be called before 
+    ///
+    /// \pre \ref init() and \ref findMinMean() must be called before
     /// using this function.
     bool findCycle() {
       if (cycle_node == INVALID) return false;
@@ -345,8 +337,8 @@
 
     /// \brief Resets the internal data structures.
     ///
-    /// Resets the internal data structures so that \ref findMinMean() 
-    /// and \ref findCycle() can be called again (e.g. when the 
+    /// Resets the internal data structures so that \ref findMinMean()
+    /// and \ref findCycle() can be called again (e.g. when the
     /// underlaying graph has been modified).
     void reset() {
       for (NodeIt u(graph); u != INVALID; ++u)
@@ -355,25 +347,25 @@
       if (cycle_path) cycle_path->clear();
       comp_num = stronglyConnectedComponents(graph, comp);
     }
-    
+
     /// \brief Returns the total length of the found cycle.
     ///
     /// Returns the total length of the found cycle.
     ///
     /// \pre \ref run() must be called before using this function.
-    Length cycleLength() const { 
+    Length cycleLength() const {
       return cycle_length;
     }
-    
+
     /// \brief Returns the number of edges in the found cycle.
     ///
     /// Returns the number of edges in the found cycle.
     ///
     /// \pre \ref run() must be called before using this function.
-    int cycleEdgeNum() const { 
+    int cycleEdgeNum() const {
       return cycle_size;
     }
-    
+
     /// \brief Returns the mean length of the found cycle.
     ///
     /// Returns the mean length of the found cycle.
@@ -386,7 +378,7 @@
     /// \code
     ///   return m.cycleEdgeNum() / double(m.cycleLength());
     /// \endcode
-    double minMean() const { 
+    double minMean() const {
       return cycle_length / (double)cycle_size;
     }
 
@@ -399,24 +391,24 @@
     /// \pre \ref run() must be called before using this function.
     ///
     /// \sa \ref cyclePath()
-    const Path &cycle() const {
+    const Path& cycle() const {
       return *cycle_path;
     }
-    
-    /// \brief Sets the \ref lemon::Path "Path" structure storing the 
+
+    /// \brief Sets the \ref lemon::Path "Path" structure storing the
     /// found cycle.
-    /// 
-    /// Sets the \ref lemon::Path "Path" structure storing the found 
-    /// cycle. If you don't use this function before calling 
-    /// \ref run(), it will allocate one. The destuctor deallocates 
+    ///
+    /// Sets the \ref lemon::Path "Path" structure storing the found
+    /// cycle. If you don't use this function before calling
+    /// \ref run(), it will allocate one. The destuctor deallocates
     /// this automatically allocated map, of course.
     ///
     /// \note The algorithm calls only the \ref lemon::Path::addFront()
-    /// "addFront()" method of the given \ref lemon::Path "Path" 
+    /// "addFront()" method of the given \ref lemon::Path "Path"
     /// structure.
-    /// 
+    ///
     /// \return \c (*this)
-    MinMeanCycle &cyclePath(Path& path) {
+    MinMeanCycle& cyclePath(Path &path) {
       if (local_path) {
 	delete cycle_path;
 	local_path = false;