diff -r 086fc76d591d -r 21eb3ccdc3df lemon/min_mean_cycle.h
--- a/lemon/min_mean_cycle.h	Thu Mar 22 06:36:50 2007 +0000
+++ b/lemon/min_mean_cycle.h	Thu Mar 22 15:40:50 2007 +0000
@@ -33,11 +33,11 @@
   /// \addtogroup min_cost_flow
   /// @{
 
-  /// \brief Implementation of Karp's algorithm for finding a 
-  /// minimum mean cycle.
+  /// \brief Implementation of Karp's algorithm for finding a
+  /// minimum mean (directed) cycle.
   ///
-  /// The \ref lemon::MinMeanCycle "MinMeanCycle" implements Karp's 
-  /// algorithm for finding a minimum mean cycle.
+  /// The \ref lemon::MinMeanCycle "MinMeanCycle" implements Karp's
+  /// algorithm for finding a minimum mean (directed) cycle.
   ///
   /// \param Graph The directed graph type the algorithm runs on.
   /// \param LengthMap The type of the length (cost) map.
@@ -57,11 +57,10 @@
     typedef typename Graph::NodeIt NodeIt;
     typedef typename Graph::Edge Edge;
     typedef typename Graph::EdgeIt EdgeIt;
-    typedef typename Graph::InEdgeIt InEdgeIt;
     typedef typename Graph::OutEdgeIt OutEdgeIt;
 
     typedef typename LengthMap::Value Length;
-    
+
     typedef typename Graph::template NodeMap<int> IntNodeMap;
     typedef typename Graph::template NodeMap<Edge> PredNodeMap;
     typedef Path<Graph> Path;
@@ -69,22 +68,24 @@
     typedef typename NodeVector::iterator NodeVectorIt;
 
   protected:
-  
+
     /// \brief Data sturcture for path data.
-    struct PathData {
+    struct PathData
+    {
       bool found;
       Length dist;
       Edge pred;
-      PathData(bool _found = false, Length _dist = 0) : 
+      PathData(bool _found = false, Length _dist = 0) :
 	found(_found), dist(_dist), pred(INVALID) {}
-      PathData(bool _found, Length _dist, Edge _pred) : 
+      PathData(bool _found, Length _dist, Edge _pred) :
 	found(_found), dist(_dist), pred(_pred) {}
     };
-    
+
   private:
-  
-    typedef typename Graph::template NodeMap<std::vector<PathData> > PathVectorNodeMap;
-  
+
+    typedef typename Graph::template NodeMap<std::vector<PathData> >
+      PathDataNodeMap;
+
   protected:
 
     /// \brief Node map for storing path data.
@@ -92,7 +93,7 @@
     /// Node map for storing path data of all nodes in the current
     /// component. dmap[v][k] is the length of a shortest directed walk 
     /// to node v from the starting node containing exactly k edges.
-    PathVectorNodeMap dmap;
+    PathDataNodeMap dmap;
     
     /// \brief The directed graph the algorithm runs on.
     const Graph& graph;
@@ -103,16 +104,20 @@
     Length cycle_length;
     /// \brief The number of edges in the found cycle.
     int cycle_size;
+    /// \brief A node for obtaining a minimum mean cycle. 
+    Node cycle_node;
+
     /// \brief The found cycle.
     Path *cycle_path;
-    /// \brief The found cycle.
+    /// \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.
     int comp_num;
-    /// \brief %Counter for identifying the current component.
+    /// \brief Counter for identifying the current component.
     int comp_cnt;
     /// \brief Nodes of the current component.
     NodeVector nodes;
@@ -129,8 +134,8 @@
     /// \param _length The length (cost) of the edges.
     MinMeanCycle( const Graph& _graph,
 		  const LengthMap& _length ) :
-      graph(_graph), length(_length), dmap(_graph), 
-      cycle_length(0), cycle_size(-1), comp(_graph),
+      graph(_graph), length(_length), dmap(_graph), comp(_graph),
+      cycle_length(0), cycle_size(-1), cycle_node(INVALID),
       cycle_path(NULL), local_path(false)
     { }
 
@@ -140,15 +145,6 @@
     }
 
   protected:
-    
-    /// \brief Initializes the internal data structures.
-    void init() {
-      comp_num = stronglyConnectedComponents(graph, comp);
-      if (!cycle_path) {
-	local_path = true;
-	cycle_path = new Path;
-      }
-    }
 
     /// \brief Initializes the internal data structures for the current
     /// component.
@@ -158,7 +154,6 @@
       for (NodeIt v(graph); v != INVALID; ++v) {
 	if (comp[v] == comp_cnt) nodes.push_back(v);
       }
-
       // Creating vectors for all nodes
       int n = nodes.size();
       for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
@@ -166,16 +161,19 @@
       }
     }
     
-    /// \brief Processes all rounds of computing required path data.
+    /// \brief Processes all rounds of computing required path data for 
+    /// the current component.
     void processRounds() {
       dmap[nodes[0]][0] = PathData(true, 0);
       process.clear();
-      for (OutEdgeIt oe(graph, nodes[0]); oe != INVALID; ++oe) {
-	Node v = graph.target(oe);
+      // Processing the first round
+      for (OutEdgeIt e(graph, nodes[0]); e != INVALID; ++e) {
+	Node v = graph.target(e);
 	if (comp[v] != comp_cnt || v == nodes[0]) continue;
-	dmap[v][1] = PathData(true, length[oe], oe);
+	dmap[v][1] = PathData(true, length[e], e);
 	process.push_back(v);
       }
+      // Processing other rounds 
       int n = nodes.size(), k;
       for (k = 2; k <= n && process.size() < n; ++k) {
 	processNextBuildRound(k);
@@ -190,12 +188,15 @@
     void processNextBuildRound(int k) {
       NodeVector next;
       for (NodeVectorIt ui = process.begin(); ui != process.end(); ++ui) {
-	for (OutEdgeIt oe(graph, *ui); oe != INVALID; ++oe) {
-	  Node v = graph.target(oe);
+	for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
+	  Node v = graph.target(e);
 	  if (comp[v] != comp_cnt) continue;
-	  if ( !dmap[v][k].found || (dmap[v][k].dist > dmap[*ui][k-1].dist + length[oe]) ) {
-	    if (!dmap[v][k].found) next.push_back(v); 
-	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[oe], oe);
+	  if (!dmap[v][k].found) {
+	    next.push_back(v);
+	    dmap[v][k] = PathData(true, dmap[*ui][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);
 	  }
 	}
       }
@@ -206,44 +207,39 @@
     /// using \ref nodes vector instead of \ref process vector.
     void processNextFullRound(int k) {
       for (NodeVectorIt ui = nodes.begin(); ui != nodes.end(); ++ui) {
-	for (OutEdgeIt oe(graph, *ui); oe != INVALID; ++oe) {
-	  Node v = graph.target(oe);
+	for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
+	  Node v = graph.target(e);
 	  if (comp[v] != comp_cnt) continue;
-	  if ( !dmap[v][k].found || (dmap[v][k].dist > dmap[*ui][k-1].dist + length[oe]) ) {
-	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[oe], oe);
+	  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);
 	  }
 	}
       }
     }
     
-    /// \brief Finds the minimum cycle mean value according to the path
-    /// data stored in \ref dmap.
-    ///
-    /// Finds the minimum cycle mean value according to the path data
-    /// stored in \ref dmap.
-    ///
-    /// \retval min_length The total length of the found cycle.
-    /// \retval min_size The number of edges in the found cycle.
-    /// \retval min_node A node for obtaining a critical cycle.
-    ///
-    /// \return \c true if a cycle exists in the graph.
-    bool findMinCycleMean(Length &min_length, int &min_size, Node &min_node) {
+    /// \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) {
+	int n = nodes.size();
+	if (!dmap[*vi][n].found) continue;
 	Length len;
 	int size;
 	bool found_one = false;
-	int n = nodes.size();
 	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[*vi][n].found && dmap[*vi][k].found && (!found_one || len * _size < _len * size) ) {
+	  if (!found_one || len * _size < _len * size) {
 	    found_one = true;
 	    len = _len;
 	    size = _size;
 	  }
 	}
-	if (found_one && (!found_min || len * min_size < min_length * size)) {
+	if ( found_one && 
+	     (!found_min || len * min_size < min_length * size) ) {
 	  found_min = true;
 	  min_length = len;
 	  min_size = size;
@@ -253,94 +249,152 @@
       return found_min;
     }
     
-    /// \brief Finds a critical (minimum mean) cycle according to the
-    /// path data stored in \ref dmap.
-    void findCycle(const Node &min_n) {
-      IntNodeMap reached(graph, -1);
-      int r = reached[min_n] = dmap[min_n].size() - 1;
-      Node u = graph.source(dmap[min_n][r].pred);
-      while (reached[u] < 0) {
-	reached[u] = --r;
-	u = graph.source(dmap[u][r].pred);
-      }
-      r = reached[u];
-      Edge ce = dmap[u][r].pred;
-      cycle_path->addFront(ce);
-      Node v;
-      while ((v = graph.source(ce)) != u) {
-	ce = dmap[v][--r].pred;
-	cycle_path->addFront(ce);
-      }
-    }
+  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 
+    /// of the following code.
+    /// \code
+    ///   m.init();
+    ///   m.findMinMean();
+    ///   m.findCycle();
+    /// \endcode
     bool run() {
       init();
-      // Searching for the minimum mean cycle in all components
-      bool found_cycle = false;
-      Node cycle_node;
+      findMinMean();
+      return findCycle();
+    }
+    
+    /// \brief Initializes the internal data structures.
+    void init() {
+      comp_num = stronglyConnectedComponents(graph, comp);
+      if (!cycle_path) {
+	local_path = true;
+	cycle_path = new Path;
+      }
+    }
+
+    /// \brief Finds the minimum cycle mean value in the graph.
+    ///
+    /// Computes all the required path data and finds the minimum cycle
+    /// 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 = findMinCycleMean(min_length, min_size, min_node);
+	bool found_min = findCurrentMin(min_length, min_size, min_node);
 	
-	if ( found_min && (!found_cycle || min_length * cycle_size  < cycle_length * min_size) ) {
-	  found_cycle = true;
+	if ( found_min && (cycle_node == INVALID || 
+	     min_length * cycle_size < cycle_length * min_size) ) {
 	  cycle_length = min_length;
 	  cycle_size = min_size;
 	  cycle_node = min_node;
 	}
       }
-      if (found_cycle) findCycle(cycle_node);
-      return found_cycle;
+      return (cycle_node != INVALID);
     }
     
-    /// \brief Returns the total length of the found critical cycle.
+    /// \brief Finds a critical (minimum mean) cycle.
     ///
-    /// Returns the total length of the found critical 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 
+    /// using this function.
+    bool findCycle() {
+      if (cycle_node == INVALID) return false;
+      cycle_length = 0;
+      cycle_size = 0;
+      IntNodeMap reached(graph, -1);
+      int r = reached[cycle_node] = dmap[cycle_node].size() - 1;
+      Node u = graph.source(dmap[cycle_node][r].pred);
+      while (reached[u] < 0) {
+	reached[u] = --r;
+	u = graph.source(dmap[u][r].pred);
+      }
+      r = reached[u];
+      Edge e = dmap[u][r].pred;
+      cycle_path->addFront(e);
+      cycle_length = cycle_length + length[e];
+      ++cycle_size;
+      Node v;
+      while ((v = graph.source(e)) != u) {
+	e = dmap[v][--r].pred;
+	cycle_path->addFront(e);
+	cycle_length = cycle_length + length[e];
+	++cycle_size;
+      }
+      return true;
+    }
+
+    /// \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 
+    /// underlaying graph has been modified).
+    void reset() {
+      for (NodeIt u(graph); u != INVALID; ++u)
+	dmap[u].clear();
+      cycle_node = INVALID;
+      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 { 
       return cycle_length;
     }
     
-    /// \brief Returns the number of edges in the found critical 
-    /// cycle.
+    /// \brief Returns the number of edges in the found cycle.
     ///
-    /// Returns the number of edges in the found critical cycle.
+    /// Returns the number of edges in the found cycle.
     ///
     /// \pre \ref run() must be called before using this function.
     int cycleEdgeNum() const { 
       return cycle_size;
     }
     
-    /// \brief Returns the mean length of the found critical cycle.
+    /// \brief Returns the mean length of the found cycle.
     ///
-    /// Returns the mean length of the found critical cycle.
+    /// Returns the mean length of the found cycle.
     ///
     /// \pre \ref run() must be called before using this function.
     ///
     /// \warning LengthMap::Value must be convertible to double.
+    ///
+    /// \note m.minMean() is just a shortcut of the following code.
+    /// \code
+    ///   return m.cycleEdgeNum() / double(m.cycleLength());
+    /// \endcode
     double minMean() const { 
-      return (double)cycle_length / (double)cycle_size;
+      return cycle_length / (double)cycle_size;
     }
 
     /// \brief Returns a const reference to the \ref lemon::Path "Path"
-    /// structure of the found flow.
+    /// structure of the found cycle.
     ///
     /// Returns a const reference to the \ref lemon::Path "Path"
-    /// structure of the found flow.
+    /// structure of the found cycle.
     ///
     /// \pre \ref run() must be called before using this function.
     ///