# HG changeset patch
# User deba
# Date 1174578050 0
# Node ID 21eb3ccdc3dfa28b28a27d7a3a256743874d2d18
# Parent  086fc76d591d1a6638e97a6c835fe949c41bb326
Right dimacs format for min cost flows
Bug fixes in tolerance and min_mean_cycle

diff -r 086fc76d591d -r 21eb3ccdc3df demo/dim_to_dot.cc
--- a/demo/dim_to_dot.cc	Thu Mar 22 06:36:50 2007 +0000
+++ b/demo/dim_to_dot.cc	Thu Mar 22 15:40:50 2007 +0000
@@ -17,17 +17,15 @@
  */
 
 ///\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
 
@@ -46,12 +44,11 @@
 {
   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
   std::ifstream is(argv[1]);
 
diff -r 086fc76d591d -r 21eb3ccdc3df lemon/dimacs.h
--- a/lemon/dimacs.h	Thu Mar 22 06:36:50 2007 +0000
+++ b/lemon/dimacs.h	Thu Mar 22 15:40:50 2007 +0000
@@ -27,11 +27,10 @@
 
 /// \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
   ///
@@ -41,114 +40,147 @@
 
   /// \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 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();
+    std::vector<typename Graph::Node> nodes;
+    typename Graph::Edge e;
+    std::string problem, str;
+    char c;
+    int n, m; 
+    int i, j;
+    typename SupplyMap::Value sup;
+    typename CapacityMap::Value low;
+    typename CapacityMap::Value cap;
+    typename CostMap::Value co;
+    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);
+	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;
+      }
+    }
+  }
 
-  /// 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.
+  /// 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.
   ///
   /// \author Marton Makai
-  template<typename Graph, typename CapacityMap, typename CostMap>
+  template<typename Graph, typename CapacityMap>
   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
-		  typename Graph::Node &s, typename Graph::Node &t, 
-		  CostMap& cost) {
+		  typename Graph::Node &s, typename Graph::Node &t) {
     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;
-    typename CostMap::Value _cost;
-    char d;
-    std::string problem;
-    char c;
-    int i, j;
     std::string str;
-    int n, m; 
-    typename Graph::Edge e;
-    std::vector<typename Graph::Node> nodes;
-    while (is>>c) {
+    while (is >> c) {
       switch (c) {
-      case 'c': //comment
+      case 'c': // comment line
 	getline(is, str);
 	break;
-      case 'p': //problem definition
+      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();
+	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
+      case 'n': // node definition line
+	if (problem == "sp") { // shortest path problem
 	  is >> i;
 	  getline(is, str);
-	  s=nodes[i];
+	  s = nodes[i];
 	}
-	if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
+	if (problem == "max") { // max flow problem
 	  is >> i >> d;
 	  getline(is, str);
-	  if (d=='s') s=nodes[i];
-	  if (d=='t') t=nodes[i];
+	  if (d == 's') s = nodes[i];
+	  if (d == 't') t = nodes[i];
 	}
 	break;
-      case 'a':
-	if ( problem == "max" || problem == "sp") {
+      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.update();
+	  e = g.addEdge(nodes[i], nodes[j]);
 	  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]);
-	  }
+	  is >> i >> j;
+	  getline(is, str);
+	  g.addEdge(nodes[i], nodes[j]);
 	}
 	break;
       }
     }
   }
 
-
-  /// 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.
+  /// DIMACS shortest path reader function.
   ///
-  /// \author Marton Makai
-  template<typename Graph, typename CapacityMap>
-  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
+  /// 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
   /// source node.
@@ -157,70 +189,67 @@
   template<typename Graph, typename CapacityMap>
   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);
+    readDimacs(is, g, capacity, s, s);
   }
 
-
-  /// Dimacs capacitated graph reader function.
-
+  /// 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.
   ///
   /// \author Marton Makai
   template<typename Graph, typename CapacityMap>
   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);
+    readDimacs(is, g, capacity, u, u);
   }
 
-
-  /// Dimacs plain graph reader function.
-
+  /// 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
   template<typename Graph>
   void readDimacs(std::istream& is, Graph &g) {
     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) {
     typedef typename Graph::NodeIt NodeIt;
     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; 
     }
-
   }
 
   /// @}
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.
     ///
diff -r 086fc76d591d -r 21eb3ccdc3df lemon/tolerance.h
--- a/lemon/tolerance.h	Thu Mar 22 06:36:50 2007 +0000
+++ b/lemon/tolerance.h	Thu Mar 22 15:40:50 2007 +0000
@@ -305,6 +305,73 @@
     ///Returns zero
     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__
 
diff -r 086fc76d591d -r 21eb3ccdc3df tools/dim_to_lgf.cc
--- a/tools/dim_to_lgf.cc	Thu Mar 22 06:36:50 2007 +0000
+++ b/tools/dim_to_lgf.cc	Thu Mar 22 15:40:50 2007 +0000
@@ -46,7 +46,8 @@
   typedef Graph::Node Node;
   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;
   std::string outputName;
@@ -115,19 +116,19 @@
 
   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();
   } else if (maxflow) {
     Graph graph;
     Node s, t;
-    DoubleMap capacity(graph);
+    DoubleEdgeMap capacity(graph);
     readDimacs(is, graph, capacity, s, t);
     GraphWriter<Graph>(os, graph).
       writeEdgeMap("capacity", capacity).
@@ -137,7 +138,7 @@
   } else if (shortestpath) {
     Graph graph;
     Node s;
-    DoubleMap capacity(graph);
+    DoubleEdgeMap capacity(graph);
     readDimacs(is, graph, capacity, s);
     GraphWriter<Graph>(os, graph).
       writeEdgeMap("capacity", capacity).
@@ -145,7 +146,7 @@
       run();
   } else if (capacitated) {
     Graph graph;
-    DoubleMap capacity(graph);
+    DoubleEdgeMap capacity(graph);
     readDimacs(is, graph, capacity);
     GraphWriter<Graph>(os, graph).
       writeEdgeMap("capacity", capacity).