Index: demo/dim_to_dot.cc
===================================================================
--- demo/dim_to_dot.cc	(revision 2391)
+++ demo/dim_to_dot.cc	(revision 2413)
@@ -18,15 +18,13 @@
 
 ///\file
-///\brief Dim (Dimacs) to Dot (Graphviz) converter
+///\brief Dim (DIMACS) to Dot (Graphviz) converter
 ///
-/// This program can convert the dimacs format to graphviz dot format.
+/// This program can convert the DIMACS format to Graphviz format.
 ///
-/// Use a DIMACS max flow file as stdin.
+/// <tt>dim_to_dot dimacs_max_flow_file > dot_output_file</tt>
 ///
-/// <tt>dim_to_dot < dimacs_max_flow_file > dot_output_file</tt>
-///
-/// This program makes a dot file from a dimacs max flow file. 
-/// This program can be an aid in making up to date visualized documantation 
-/// of demo programs.
+/// This program makes a dot file from a DIMACS max flow file. 
+/// This program can be an aid in making up to date visualized 
+/// documantation of demo programs.
 ///
 /// \include dim_to_dot.cc
@@ -47,9 +45,8 @@
   if(argc<2)
   {
-      std::cerr << "USAGE: sub_graph_adaptor_demo input_file.dim" << std::endl;
+      std::cerr << "USAGE: dim_to_dot input_file.dim" << std::endl;
       std::cerr << "The file 'input_file.dim' has to contain a max flow instance in DIMACS format (e.g. sub_graph_adaptor_demo.dim is such a file)." << std::endl;
       return 0;
   }
-
 
   //input stream to read the graph from
Index: lemon/dimacs.h
===================================================================
--- lemon/dimacs.h	(revision 2391)
+++ lemon/dimacs.h	(revision 2413)
@@ -28,9 +28,8 @@
 /// \ingroup dimacs_group
 /// \file
-/// \brief Dimacs file format reader.
+/// \brief DIMACS file format reader.
 
 namespace lemon {
 
-  ///
   ///@defgroup dimacs_group DIMACS format
   ///\brief Read and write files in DIMACS format
@@ -42,79 +41,68 @@
   /// \addtogroup dimacs_group
   /// @{
-
-  /// Dimacs min cost flow reader function.
-
-  /// This function reads a min cost flow instance from dimacs format,
-  /// i.e. from dimacs files having a line starting with
-  ///\code
-  /// p "min"
-  ///\endcode
-  /// At the beginning \c g is cleared by \c g.clear(). The edge
-  /// capacities are written to \c capacity, \c s and \c t are set to
-  /// the source and the target nodes resp. and the cost of the edges
-  /// are written to \c cost.
-  ///
-  /// \author Marton Makai
-  template<typename Graph, typename CapacityMap, typename CostMap>
-  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
-		  typename Graph::Node &s, typename Graph::Node &t, 
-		  CostMap& cost) {
+  
+  /// DIMACS min cost flow reader function.
+  ///
+  /// This function reads a min cost flow instance from DIMACS format,
+  /// i.e. from DIMACS files having a line starting with
+  /// \code
+  ///   p min
+  /// \endcode
+  /// At the beginning \c g is cleared by \c g.clear(). The supply 
+  /// amount of the nodes are written to \c supply (signed). The 
+  /// lower bounds, capacities and costs of the edges are written to 
+  /// \c lower, \c capacity and \c cost.
+  ///
+  /// \author Marton Makai and Peter Kovacs
+  template <typename Graph, typename SupplyMap, 
+    typename CapacityMap, typename CostMap>
+  void readDimacs( std::istream& is,
+		   Graph &g,
+		   SupplyMap& supply, 
+		   CapacityMap& lower, 
+		   CapacityMap& capacity, 
+		   CostMap& cost )
+  {
     g.clear();
-    typename CapacityMap::Value _cap;
-    typename CostMap::Value _cost;
-    char d;
-    std::string problem;
+    std::vector<typename Graph::Node> nodes;
+    typename Graph::Edge e;
+    std::string problem, str;
     char c;
+    int n, m; 
     int i, j;
-    std::string str;
-    int n, m; 
-    typename Graph::Edge e;
-    std::vector<typename Graph::Node> nodes;
-    while (is>>c) {
+    typename SupplyMap::Value sup;
+    typename CapacityMap::Value low;
+    typename CapacityMap::Value cap;
+    typename CostMap::Value co;
+    while (is >> c) {
       switch (c) {
-      case 'c': //comment
-	getline(is, str);
-	break;
-      case 'p': //problem definition
+      case 'c': // comment line
+	getline(is, str);
+	break;
+      case 'p': // problem definition line
 	is >> problem >> n >> m;
 	getline(is, str);
-	nodes.resize(n+1);
-	for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
-	break;
-      case 'n': //node definition
-	if (problem=="sp") { //shortest path problem
-	  is >> i;
-	  getline(is, str);
-	  s=nodes[i];
-	}
-	if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
-	  is >> i >> d;
-	  getline(is, str);
-	  if (d=='s') s=nodes[i];
-	  if (d=='t') t=nodes[i];
-	}
-	break;
-      case 'a':
-	if ( problem == "max" || problem == "sp") {
-	  is >> i >> j >> _cap;
-	  getline(is, str);
-	  e=g.addEdge(nodes[i], nodes[j]);
-	  //capacity.update();
-	  capacity.set(e, _cap);
-	} else {
-	  if ( problem == "min" ) {
-	    is >> i >> j >> _cap >> _cost;
-	    getline(is, str);
-	    e=g.addEdge(nodes[i], nodes[j]);
-	    //capacity.update();
-	    capacity.set(e, _cap);
-	    //cost.update();
-	    cost.set(e, _cost);
-	  } else {
-	    is >> i >> j;
-	    getline(is, str);
-	    g.addEdge(nodes[i], nodes[j]);
-	  }
-	}
+	if (problem != "min") return;
+	nodes.resize(n + 1);
+	for (int k = 1; k <= n; ++k) {
+	  nodes[k] = g.addNode();
+	  supply[nodes[k]] = 0;
+	}
+	break;
+      case 'n': // node definition line
+	is >> i >> sup;
+	getline(is, str);
+	supply.set(nodes[i], sup);
+	break;
+      case 'a': // edge (arc) definition line
+	is >> i >> j >> low >> cap >> co;
+	getline(is, str);
+	e = g.addEdge(nodes[i], nodes[j]);
+	lower.set(e, low);
+	if (cap >= 0)
+	  capacity.set(e, cap);
+	else
+	  capacity.set(e, -1);
+	cost.set(e, co);
 	break;
       }
@@ -122,14 +110,13 @@
   }
 
-
-  /// Dimacs max flow reader function.
-
-  /// This function reads a max flow instance from dimacs format,
-  /// i.e. from dimacs files having a line starting with
-  ///\code
-  /// p "max"
-  ///\endcode
-  ///At the beginning \c g is cleared by \c g.clear(). The
-  /// edge capacities are written to \c capacity and \c s and \c t are
+  /// DIMACS max flow reader function.
+  ///
+  /// This function reads a max flow instance from DIMACS format,
+  /// i.e. from DIMACS files having a line starting with
+  /// \code
+  ///   p max
+  /// \endcode
+  /// At the beginning \c g is cleared by \c g.clear(). The edge 
+  /// capacities are written to \c capacity and \c s and \c t are
   /// set to the source and the target nodes.
   ///
@@ -138,16 +125,61 @@
   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
 		  typename Graph::Node &s, typename Graph::Node &t) {
-    NullMap<typename Graph::Edge, int> n;
-    readDimacs(is, g, capacity, s, t, n);
-  }
-
-
-  /// Dimacs shortest path reader function.
-
-  /// This function reads a shortest path instance from dimacs format,
-  /// i.e. from dimacs files having a line starting with
-  ///\code
-  /// p "sp"
-  ///\endcode
+    g.clear();
+    std::vector<typename Graph::Node> nodes;
+    typename Graph::Edge e;
+    std::string problem;
+    char c, d;
+    int n, m; 
+    int i, j;
+    typename CapacityMap::Value _cap;
+    std::string str;
+    while (is >> c) {
+      switch (c) {
+      case 'c': // comment line
+	getline(is, str);
+	break;
+      case 'p': // problem definition line
+	is >> problem >> n >> m;
+	getline(is, str);
+	nodes.resize(n + 1);
+	for (int k = 1; k <= n; ++k)
+	  nodes[k] = g.addNode();
+	break;
+      case 'n': // node definition line
+	if (problem == "sp") { // shortest path problem
+	  is >> i;
+	  getline(is, str);
+	  s = nodes[i];
+	}
+	if (problem == "max") { // max flow problem
+	  is >> i >> d;
+	  getline(is, str);
+	  if (d == 's') s = nodes[i];
+	  if (d == 't') t = nodes[i];
+	}
+	break;
+      case 'a': // edge (arc) definition line
+	if (problem == "max" || problem == "sp") {
+	  is >> i >> j >> _cap;
+	  getline(is, str);
+	  e = g.addEdge(nodes[i], nodes[j]);
+	  capacity.set(e, _cap);
+	} else {
+	  is >> i >> j;
+	  getline(is, str);
+	  g.addEdge(nodes[i], nodes[j]);
+	}
+	break;
+      }
+    }
+  }
+
+  /// DIMACS shortest path reader function.
+  ///
+  /// This function reads a shortest path instance from DIMACS format,
+  /// i.e. from DIMACS files having a line starting with
+  /// \code
+  ///   p sp
+  /// \endcode
   /// At the beginning \c g is cleared by \c g.clear(). The edge
   /// capacities are written to \c capacity and \c s is set to the
@@ -158,13 +190,11 @@
   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
 		  typename Graph::Node &s) {
-    NullMap<typename Graph::Edge, int> n;
-    readDimacs(is, g, capacity, s, s, n);
-  }
-
-
-  /// Dimacs capacitated graph reader function.
-
+    readDimacs(is, g, capacity, s, s);
+  }
+
+  /// DIMACS capacitated graph reader function.
+  ///
   /// This function reads an edge capacitated graph instance from
-  /// dimacs format.  At the beginning \c g is cleared by \c g.clear()
+  /// DIMACS format. At the beginning \c g is cleared by \c g.clear()
   /// and the edge capacities are written to \c capacity.
   ///
@@ -173,19 +203,16 @@
   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
     typename Graph::Node u;
-    NullMap<typename Graph::Edge, int> n;
-    readDimacs(is, g, capacity, u, u, n);
-  }
-
-
-  /// Dimacs plain graph reader function.
-
+    readDimacs(is, g, capacity, u, u);
+  }
+
+  /// DIMACS plain graph reader function.
+  ///
   /// This function reads a graph without any designated nodes and
-  /// maps from dimacs format, i.e. from dimacs files having a line
+  /// maps from DIMACS format, i.e. from DIMACS files having a line
   /// starting with
-  ///\code
-  /// p "mat"
-  ///\endcode
-  /// At the beginning \c g is cleared
-  /// by \c g.clear().
+  /// \code
+  ///   p mat
+  /// \endcode
+  /// At the beginning \c g is cleared by \c g.clear().
   ///
   /// \author Marton Makai
@@ -194,11 +221,17 @@
     typename Graph::Node u;
     NullMap<typename Graph::Edge, int> n;
-    readDimacs(is, g, n, u, u, n);
+    readDimacs(is, g, n, u, u);
   }
   
-
-
-  
-  /// write matching problem
+  /// DIMACS plain graph writer function.
+  ///
+  /// This function writes a graph without any designated nodes and
+  /// maps into DIMACS format, i.e. into DIMACS file having a line 
+  /// starting with
+  /// \code
+  ///   p mat
+  /// \endcode
+  ///
+  /// \author Marton Makai
   template<typename Graph>
   void writeDimacs(std::ostream& os, const Graph &g) {
@@ -206,20 +239,16 @@
     typedef typename Graph::EdgeIt EdgeIt;  
     
+    os << "c matching problem" << std::endl;
+    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
+
     typename Graph::template NodeMap<int> nodes(g);
-
-    os << "c matching problem" << std::endl;
-
-    int i=1;
-    for(NodeIt v(g); v!=INVALID; ++v) {
+    int i = 1;
+    for(NodeIt v(g); v != INVALID; ++v) {
       nodes.set(v, i);
       ++i;
     }    
-    
-    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
-
-    for(EdgeIt e(g); e!=INVALID; ++e) {
+    for(EdgeIt e(g); e != INVALID; ++e) {
       os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl; 
     }
-
   }
 
Index: lemon/min_mean_cycle.h
===================================================================
--- lemon/min_mean_cycle.h	(revision 2409)
+++ lemon/min_mean_cycle.h	(revision 2413)
@@ -34,9 +34,9 @@
   /// @{
 
-  /// \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.
@@ -58,9 +58,8 @@
     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;
@@ -70,20 +69,22 @@
 
   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:
 
@@ -93,5 +94,5 @@
     /// 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.
@@ -104,7 +105,11 @@
     /// \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;
     
@@ -113,5 +118,5 @@
     /// \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.
@@ -130,6 +135,6 @@
     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)
     { }
@@ -141,13 +146,4 @@
 
   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
@@ -159,5 +155,4 @@
 	if (comp[v] == comp_cnt) nodes.push_back(v);
       }
-
       // Creating vectors for all nodes
       int n = nodes.size();
@@ -167,14 +162,17 @@
     }
     
-    /// \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) {
@@ -191,10 +189,13 @@
       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);
 	  }
 	}
@@ -207,9 +208,10 @@
     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);
 	  }
 	}
@@ -217,26 +219,19 @@
     }
     
-    /// \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;
@@ -244,5 +239,6 @@
 	  }
 	}
-	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;
@@ -254,26 +250,6 @@
     }
     
-    /// \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.
     ///
@@ -281,11 +257,38 @@
     ///
     /// \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();
@@ -294,8 +297,8 @@
 	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;
@@ -303,11 +306,58 @@
 	}
       }
-      if (found_cycle) findCycle(cycle_node);
-      return found_cycle;
-    }
-    
-    /// \brief Returns the total length of the found critical cycle.
-    ///
-    /// Returns the total length of the found critical cycle.
+      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 
+    /// 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.
@@ -316,8 +366,7 @@
     }
     
-    /// \brief Returns the number of edges in the found critical 
-    /// cycle.
-    ///
-    /// 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 cycle.
     ///
     /// \pre \ref run() must be called before using this function.
@@ -326,20 +375,25 @@
     }
     
-    /// \brief Returns the mean length of the found critical cycle.
-    ///
-    /// 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 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.
Index: lemon/tolerance.h
===================================================================
--- lemon/tolerance.h	(revision 2391)
+++ lemon/tolerance.h	(revision 2413)
@@ -306,4 +306,71 @@
     static Value zero() {return 0;}
   };
+  
+
+  ///Long integer specialization of \ref Tolerance.
+
+  ///Long integer specialization of \ref Tolerance.
+  ///\sa Tolerance
+  template<>
+  class Tolerance<long int>
+  {
+  public:
+    ///\e
+    typedef long int Value;
+
+    ///\name Comparisons
+    ///See \ref Tolerance for more details.
+
+    ///@{
+
+    ///Returns \c true if \c a is \e surely strictly less than \c b
+    static bool less(Value a,Value b) { return a<b;}
+    ///Returns \c true if \c a is \e surely different from \c b
+    static bool different(Value a,Value b) { return a!=b; }
+    ///Returns \c true if \c a is \e surely positive
+    static bool positive(Value a) { return 0<a; }
+    ///Returns \c true if \c a is \e surely negative
+    static bool negative(Value a) { return 0>a; }
+    ///Returns \c true if \c a is \e surely non-zero
+    static bool nonZero(Value a) { return a!=0;};
+
+    ///@}
+
+    ///Returns zero
+    static Value zero() {return 0;}
+  };
+
+  ///Unsigned long integer specialization of \ref Tolerance.
+
+  ///Unsigned long integer specialization of \ref Tolerance.
+  ///\sa Tolerance
+  template<>
+  class Tolerance<unsigned long int>
+  {
+  public:
+    ///\e
+    typedef unsigned long int Value;
+
+    ///\name Comparisons
+    ///See \ref Tolerance for more details.
+
+    ///@{
+
+    ///Returns \c true if \c a is \e surely strictly less than \c b
+    static bool less(Value a,Value b) { return a<b;}
+    ///Returns \c true if \c a is \e surely different from \c b
+    static bool different(Value a,Value b) { return a!=b; }
+    ///Returns \c true if \c a is \e surely positive
+    static bool positive(Value a) { return 0<a; }
+    ///Returns \c true if \c a is \e surely negative
+    static bool negative(Value) { return false; }
+    ///Returns \c true if \c a is \e surely non-zero
+    static bool nonZero(Value a) { return a!=0;};
+
+    ///@}
+
+    ///Returns zero
+    static Value zero() {return 0;}
+  };
 
 #if defined __GNUC__ && !defined __STRICT_ANSI__
Index: tools/dim_to_lgf.cc
===================================================================
--- tools/dim_to_lgf.cc	(revision 2410)
+++ tools/dim_to_lgf.cc	(revision 2413)
@@ -47,5 +47,6 @@
   typedef Graph::EdgeIt EdgeIt;
   typedef Graph::NodeIt NodeIt;
-  typedef Graph::EdgeMap<double> DoubleMap;
+  typedef Graph::EdgeMap<double> DoubleEdgeMap;
+  typedef Graph::NodeMap<double> DoubleNodeMap;
 
   std::string inputName;
@@ -116,11 +117,11 @@
   if (mincostflow) {
     Graph graph;
-    Node s, t;
-    DoubleMap cost(graph), capacity(graph);
-    readDimacs(is, graph, capacity, s, t, cost);
+    DoubleNodeMap supply(graph);
+    DoubleEdgeMap lower(graph), capacity(graph), cost(graph);
+    readDimacs(is, graph, supply, lower, capacity, cost);
     GraphWriter<Graph>(os, graph).
+      writeNodeMap("supply", supply).
+      writeEdgeMap("lower", lower).
       writeEdgeMap("capacity", capacity).
-      writeNode("source", s).
-      writeNode("target", t).
       writeEdgeMap("cost", cost).
       run();
@@ -128,5 +129,5 @@
     Graph graph;
     Node s, t;
-    DoubleMap capacity(graph);
+    DoubleEdgeMap capacity(graph);
     readDimacs(is, graph, capacity, s, t);
     GraphWriter<Graph>(os, graph).
@@ -138,5 +139,5 @@
     Graph graph;
     Node s;
-    DoubleMap capacity(graph);
+    DoubleEdgeMap capacity(graph);
     readDimacs(is, graph, capacity, s);
     GraphWriter<Graph>(os, graph).
@@ -146,5 +147,5 @@
   } else if (capacitated) {
     Graph graph;
-    DoubleMap capacity(graph);
+    DoubleEdgeMap capacity(graph);
     readDimacs(is, graph, capacity);
     GraphWriter<Graph>(os, graph).
