Diff [e05b2b48515aeb9bf7561ac758a5e5811326ae00:1b8db382910c830f5d548a8079260d2e49fde262] for / – LEMON

INSTALL

-                      r568
+                      r824
    Disable COIN-OR support.
+Makefile Variables
+==================
+Some Makefile variables are reserved by the GNU Coding Standards for
+the use of the "user" - the person building the package. For instance,
+CXX and CXXFLAGS are such variables, and have the same meaning as
+explained in the previous section. These variables can be set on the
+command line when invoking `make' like this:
+`make [VARIABLE=VALUE]...'
+WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us
+to hold several compiler flags related to warnings. Its default value
+can be overridden when invoking `make'. For example to disable all
+warning flags use `make WARNINGCXXFLAGS='.
+In order to turn off a single flag from the default set of warning
+flags, you can use the CXXFLAGS variable, since this is passed after
+WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is
+used by default when g++ is detected) you can use
+`make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.

demo/arg_parser_demo.cc

-                      r440
+                      r842
     .other("...");
+  // Throw an exception when problems occurs. The default behavior is to
+  // exit(1) on these cases, but this makes Valgrind falsely warn
+  // about memory leaks.
+  ap.throwOnProblems();
   // Perform the parsing process
   // (in case of any error it terminates the program)
+  ap.parse();
+  // The try {} construct is necessary only if the ap.trowOnProblems()
+  // setting is in use.
+  try {
+    ap.parse();
+  } catch (ArgParserException &) { return 1; }
   // Check each option if it has been given and print its value

doc/CMakeLists.txt

r744	r827
27	27	COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
28	28	COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
	29	COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
29	30	COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
30	31	COMMAND ${CMAKE_COMMAND} -E remove_directory html

doc/Makefile.am

r744	r827
29	29	edge_biconnected_components.eps \
30	30	node_biconnected_components.eps \
	31	planar.eps \
31	32	strongly_connected_components.eps
32	33

lemon/arg_parser.cc

-                      r440
+                      r842
 namespace lemon {
+  void ArgParser::_terminate(ArgParserException::Reason reason) const
+  {
+    if(_exit_on_problems)
+      exit(1);
+    else throw(ArgParserException(reason));
+  }
   void ArgParser::_showHelp(void *p)
+  {
     (static_cast<ArgParser*>(p))->showHelp();
     exit(1);
+    (static_cast<ArgParser*>(p))->_terminate(ArgParserException::HELP);
+  }
   ArgParser::ArgParser(int argc, const char * const *argv)
+    :_argc(argc), _argv(argv), _command_name(argv[0]) {
+    :_argc(argc), _argv(argv), _command_name(argv[0]),
+    _exit_on_problems(true) {
     funcOption("-help","Print a short help message",_showHelp,this);
     synonym("help","-help");
 …
         i!=_others_help.end();++i) showHelp(i);
     for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i);
     exit(1);
+    _terminate(ArgParserException::HELP);
+  }
 …
     std::cerr << "\nType '" << _command_name <<
       " --help' to obtain a short summary on the usage.\n\n";
     exit(1);
+    _terminate(ArgParserException::UNKNOWN_OPT);
+  }
 …
       std::cerr << "\nType '" << _command_name <<
         " --help' to obtain a short summary on the usage.\n\n";
       exit(1);
+      _terminate(ArgParserException::INVALID_OPT);
+    }
+  }

lemon/arg_parser.h

-                      r440
+                      r842
 namespace lemon {
+  ///Exception used by ArgParser
+  class ArgParserException : public Exception {
+  public:
+    enum Reason {
+      HELP,         /// <tt>--help</tt> option was given
+      UNKNOWN_OPT,  /// Unknown option was given
+      INVALID_OPT   /// Invalid combination of options
+    };
+  private:
+    Reason _reason;
+  public:
+    ///Constructor
+    ArgParserException(Reason r) throw() : _reason(r) {}
+    ///Virtual destructor
+    virtual ~ArgParserException() throw() {}
+    ///A short description of the exception
+    virtual const char* what() const throw() {
+      switch(_reason)
+        {
+        case HELP:
+          return "lemon::ArgParseException: ask for help";
+          break;
+        case UNKNOWN_OPT:
+          return "lemon::ArgParseException: unknown option";
+          break;
+        case INVALID_OPT:
+          return "lemon::ArgParseException: invalid combination of options";
+          break;
+        }
+      return "";
+    }
+    ///Return the reason for the failure
+    Reason reason() const {return _reason; }
+  };
   ///Command line arguments parser
 …
     std::string _command_name;
   private:
     //Bind a function to an option.
 …
                     const std::string &help,
                     void (*func)(void *),void *data);
+    bool _exit_on_problems;
+    void _terminate(ArgParserException::Reason reason) const;
   public:
 …
     const std::vector<std::string> &files() const { return _file_args; }
+    ///Throw instead of exit in case of problems
+    void throwOnProblems()
+    {
+      _exit_on_problems=false;
+    }
   };
+}

lemon/bellman_ford.h

-                      r804
+                      r844
 #include <lemon/error.h>
 #include <lemon/maps.h>
+#include <lemon/tolerance.h>
 #include <lemon/path.h>
 …
 namespace lemon {
   /// \brief Default OperationTraits for the BellmanFord algorithm class.
+  /// \brief Default operation traits for the BellmanFord algorithm class.
   ///
   /// This operation traits class defines all computational operations
 …
   /// If the numeric type does not have infinity value, then the maximum
   /// value is used as extremal infinity value.
+  ///
+  /// \see BellmanFordToleranceOperationTraits
   template <
     typename V,
     bool has_inf = std::numeric_limits<V>::has_infinity>
   struct BellmanFordDefaultOperationTraits {
     /// \e
+    /// \brief Value type for the algorithm.
     typedef V Value;
     /// \brief Gives back the zero value of the type.
 …
   };
+  /// \brief Operation traits for the BellmanFord algorithm class
+  /// using tolerance.
+  ///
+  /// This operation traits class defines all computational operations
+  /// and constants that are used in the Bellman-Ford algorithm.
+  /// The only difference between this implementation and
+  /// \ref BellmanFordDefaultOperationTraits is that this class uses
+  /// the \ref Tolerance "tolerance technique" in its \ref less()
+  /// function.
+  ///
+  /// \tparam V The value type.
+  /// \tparam eps The epsilon value for the \ref less() function.
+  /// By default, it is the epsilon value used by \ref Tolerance
+  /// "Tolerance<V>".
+  ///
+  /// \see BellmanFordDefaultOperationTraits
+#ifdef DOXYGEN
+  template <typename V, V eps>
+#else
+  template <
+    typename V,
+    V eps = Tolerance<V>::def_epsilon>
+#endif
+  struct BellmanFordToleranceOperationTraits {
+    /// \brief Value type for the algorithm.
+    typedef V Value;
+    /// \brief Gives back the zero value of the type.
+    static Value zero() {
+      return static_cast<Value>(0);
+    }
+    /// \brief Gives back the positive infinity value of the type.
+    static Value infinity() {
+      return std::numeric_limits<Value>::infinity();
+    }
+    /// \brief Gives back the sum of the given two elements.
+    static Value plus(const Value& left, const Value& right) {
+      return left + right;
+    }
+    /// \brief Gives back \c true only if the first value is less than
+    /// the second.
+    static bool less(const Value& left, const Value& right) {
+      return left + eps < right;
+    }
+  };
   /// \brief Default traits class of BellmanFord class.
   ///
 …
     /// It defines the used operations and the infinity value for the
     /// given \c Value type.
+    /// \see BellmanFordDefaultOperationTraits
+    /// \see BellmanFordDefaultOperationTraits,
+    /// BellmanFordToleranceOperationTraits
     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 …
   /// the lengths of the arcs. The default map type is
   /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref BellmanFordDefaultTraits
+  /// "BellmanFordDefaultTraits<GR, LEN>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR, typename LEN, typename TR>
 …
     /// It defines the used operations and the infinity value for the
     /// given \c Value type.
+    /// \see BellmanFordDefaultOperationTraits
+    /// \see BellmanFordDefaultOperationTraits,
+    /// BellmanFordToleranceOperationTraits
     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 …
   /// This class should only be used through the \ref bellmanFord()
   /// function, which makes it easier to use the algorithm.
+  ///
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm.
   template<class TR>
   class BellmanFordWizard : public TR {

lemon/bfs.h

-                      r788
+                      r825
   ///\tparam GR The type of the digraph the algorithm runs on.
   ///The default type is \ref ListDigraph.
+  ///\tparam TR The traits class that defines various types used by the
+  ///algorithm. By default, it is \ref BfsDefaultTraits
+  ///"BfsDefaultTraits<GR>".
+  ///In most cases, this parameter should not be set directly,
+  ///consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR,
 …
   /// This class should only be used through the \ref bfs() function,
   /// which makes it easier to use the algorithm.
+  ///
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm.
   template<class TR>
   class BfsWizard : public TR
 …
   /// does not observe the BFS events. If you want to observe the BFS
   /// events, you should implement your own visitor class.
   /// \tparam TR Traits class to set various data types used by the
   /// algorithm. The default traits class is
   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
   /// See \ref BfsVisitDefaultTraits for the documentation of
   /// a BFS visit traits class.
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref BfsVisitDefaultTraits
+  /// "BfsVisitDefaultTraits<GR>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR, typename VS, typename TR>

lemon/capacity_scaling.h

-                      r821
+                      r840
   /// \tparam GR The digraph type the algorithm runs on.
   /// \tparam V The number type used for flow amounts, capacity bounds
   /// and supply values in the algorithm. By default it is \c int.
+  /// and supply values in the algorithm. By default, it is \c int.
   /// \tparam C The number type used for costs and potentials in the
+  /// algorithm. By default it is the same as \c V.
+  /// algorithm. By default, it is the same as \c V.
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref CapacityScalingDefaultTraits
+  /// "CapacityScalingDefaultTraits<GR, V, C>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
   ///
   /// \warning Both number types must be signed and all input data must
 …
     typedef std::vector<int> IntVector;
-    typedef std::vector<char> BoolVector;
     typedef std::vector<Value> ValueVector;
     typedef std::vector<Cost> CostVector;
+    typedef std::vector<char> BoolVector;
+    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
   private:
 …
         "The cost type of CapacityScaling must be signed");
+      // Reset data structures
+      reset();
+    }
+    /// \name Parameters
+    /// The parameters of the algorithm can be specified using these
+    /// functions.
+    /// @{
+    /// \brief Set the lower bounds on the arcs.
+    ///
+    /// This function sets the lower bounds on the arcs.
+    /// If it is not used before calling \ref run(), the lower bounds
+    /// will be set to zero on all arcs.
+    ///
+    /// \param map An arc map storing the lower bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template <typename LowerMap>
+    CapacityScaling& lowerMap(const LowerMap& map) {
+      _have_lower = true;
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _lower[_arc_idf[a]] = map[a];
+        _lower[_arc_idb[a]] = map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the upper bounds (capacities) on the arcs.
+    ///
+    /// This function sets the upper bounds (capacities) on the arcs.
+    /// If it is not used before calling \ref run(), the upper bounds
+    /// will be set to \ref INF on all arcs (i.e. the flow value will be
+    /// unbounded from above).
+    ///
+    /// \param map An arc map storing the upper bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename UpperMap>
+    CapacityScaling& upperMap(const UpperMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _upper[_arc_idf[a]] = map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the costs of the arcs.
+    ///
+    /// This function sets the costs of the arcs.
+    /// If it is not used before calling \ref run(), the costs
+    /// will be set to \c 1 on all arcs.
+    ///
+    /// \param map An arc map storing the costs.
+    /// Its \c Value type must be convertible to the \c Cost type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename CostMap>
+    CapacityScaling& costMap(const CostMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _cost[_arc_idf[a]] =  map[a];
+        _cost[_arc_idb[a]] = -map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the supply values of the nodes.
+    ///
+    /// This function sets the supply values of the nodes.
+    /// If neither this function nor \ref stSupply() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// \param map A node map storing the supply values.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename SupplyMap>
+    CapacityScaling& supplyMap(const SupplyMap& map) {
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        _supply[_node_id[n]] = map[n];
+      }
+      return *this;
+    }
+    /// \brief Set single source and target nodes and a supply value.
+    ///
+    /// This function sets a single source node and a single target node
+    /// and the required flow value.
+    /// If neither this function nor \ref supplyMap() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// Using this function has the same effect as using \ref supplyMap()
+    /// with such a map in which \c k is assigned to \c s, \c -k is
+    /// assigned to \c t and all other nodes have zero supply value.
+    ///
+    /// \param s The source node.
+    /// \param t The target node.
+    /// \param k The required amount of flow from node \c s to node \c t
+    /// (i.e. the supply of \c s and the demand of \c t).
+    ///
+    /// \return <tt>(*this)</tt>
+    CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
+      for (int i = 0; i != _node_num; ++i) {
+        _supply[i] = 0;
+      }
+      _supply[_node_id[s]] =  k;
+      _supply[_node_id[t]] = -k;
+      return *this;
+    }
+    /// @}
+    /// \name Execution control
+    /// The algorithm can be executed using \ref run().
+    /// @{
+    /// \brief Run the algorithm.
+    ///
+    /// This function runs the algorithm.
+    /// The paramters can be specified using functions \ref lowerMap(),
+    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
+    /// For example,
+    /// \code
+    ///   CapacityScaling<ListDigraph> cs(graph);
+    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// This function can be called more than once. All the given parameters
+    /// are kept for the next call, unless \ref resetParams() or \ref reset()
+    /// is used, thus only the modified parameters have to be set again.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class (or the last \ref reset() call), then the \ref reset()
+    /// function must be called.
+    ///
+    /// \param factor The capacity scaling factor. It must be larger than
+    /// one to use scaling. If it is less or equal to one, then scaling
+    /// will be disabled.
+    ///
+    /// \return \c INFEASIBLE if no feasible flow exists,
+    /// \n \c OPTIMAL if the problem has optimal solution
+    /// (i.e. it is feasible and bounded), and the algorithm has found
+    /// optimal flow and node potentials (primal and dual solutions),
+    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
+    /// and infinite upper bound. It means that the objective function
+    /// is unbounded on that arc, however, note that it could actually be
+    /// bounded over the feasible flows, but this algroithm cannot handle
+    /// these cases.
+    ///
+    /// \see ProblemType
+    /// \see resetParams(), reset()
+    ProblemType run(int factor = 4) {
+      _factor = factor;
+      ProblemType pt = init();
+      if (pt != OPTIMAL) return pt;
+      return start();
+    }
+    /// \brief Reset all the parameters that have been given before.
+    ///
+    /// This function resets all the paramaters that have been given
+    /// before using functions \ref lowerMap(), \ref upperMap(),
+    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
+    ///
+    /// It is useful for multiple \ref run() calls. Basically, all the given
+    /// parameters are kept for the next \ref run() call, unless
+    /// \ref resetParams() or \ref reset() is used.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class or the last \ref reset() call, then the \ref reset()
+    /// function must be used, otherwise \ref resetParams() is sufficient.
+    ///
+    /// For example,
+    /// \code
+    ///   CapacityScaling<ListDigraph> cs(graph);
+    ///
+    ///   // First run
+    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    ///
+    ///   // Run again with modified cost map (resetParams() is not called,
+    ///   // so only the cost map have to be set again)
+    ///   cost[e] += 100;
+    ///   cs.costMap(cost).run();
+    ///
+    ///   // Run again from scratch using resetParams()
+    ///   // (the lower bounds will be set to zero on all arcs)
+    ///   cs.resetParams();
+    ///   cs.upperMap(capacity).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// \return <tt>(*this)</tt>
+    ///
+    /// \see reset(), run()
+    CapacityScaling& resetParams() {
+      for (int i = 0; i != _node_num; ++i) {
+        _supply[i] = 0;
+      }
+      for (int j = 0; j != _res_arc_num; ++j) {
+        _lower[j] = 0;
+        _upper[j] = INF;
+        _cost[j] = _forward[j] ? 1 : -1;
+      }
+      _have_lower = false;
+      return *this;
+    }
+    /// \brief Reset the internal data structures and all the parameters
+    /// that have been given before.
+    ///
+    /// This function resets the internal data structures and all the
+    /// paramaters that have been given before using functions \ref lowerMap(),
+    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
+    ///
+    /// It is useful for multiple \ref run() calls. Basically, all the given
+    /// parameters are kept for the next \ref run() call, unless
+    /// \ref resetParams() or \ref reset() is used.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class or the last \ref reset() call, then the \ref reset()
+    /// function must be used, otherwise \ref resetParams() is sufficient.
+    ///
+    /// See \ref resetParams() for examples.
+    ///
+    /// \return <tt>(*this)</tt>
+    ///
+    /// \see resetParams(), run()
+    CapacityScaling& reset() {
       // Resize vectors
       _node_num = countNodes(_graph);
 …
       // Reset parameters
+      reset();
+    }
+    /// \name Parameters
+    /// The parameters of the algorithm can be specified using these
+    /// functions.
+    /// @{
+    /// \brief Set the lower bounds on the arcs.
+    ///
+    /// This function sets the lower bounds on the arcs.
+    /// If it is not used before calling \ref run(), the lower bounds
+    /// will be set to zero on all arcs.
+    ///
+    /// \param map An arc map storing the lower bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template <typename LowerMap>
+    CapacityScaling& lowerMap(const LowerMap& map) {
+      _have_lower = true;
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _lower[_arc_idf[a]] = map[a];
+        _lower[_arc_idb[a]] = map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the upper bounds (capacities) on the arcs.
+    ///
+    /// This function sets the upper bounds (capacities) on the arcs.
+    /// If it is not used before calling \ref run(), the upper bounds
+    /// will be set to \ref INF on all arcs (i.e. the flow value will be
+    /// unbounded from above).
+    ///
+    /// \param map An arc map storing the upper bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename UpperMap>
+    CapacityScaling& upperMap(const UpperMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _upper[_arc_idf[a]] = map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the costs of the arcs.
+    ///
+    /// This function sets the costs of the arcs.
+    /// If it is not used before calling \ref run(), the costs
+    /// will be set to \c 1 on all arcs.
+    ///
+    /// \param map An arc map storing the costs.
+    /// Its \c Value type must be convertible to the \c Cost type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename CostMap>
+    CapacityScaling& costMap(const CostMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _cost[_arc_idf[a]] =  map[a];
+        _cost[_arc_idb[a]] = -map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the supply values of the nodes.
+    ///
+    /// This function sets the supply values of the nodes.
+    /// If neither this function nor \ref stSupply() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// \param map A node map storing the supply values.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename SupplyMap>
+    CapacityScaling& supplyMap(const SupplyMap& map) {
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        _supply[_node_id[n]] = map[n];
+      }
+      return *this;
+    }
+    /// \brief Set single source and target nodes and a supply value.
+    ///
+    /// This function sets a single source node and a single target node
+    /// and the required flow value.
+    /// If neither this function nor \ref supplyMap() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// Using this function has the same effect as using \ref supplyMap()
+    /// with such a map in which \c k is assigned to \c s, \c -k is
+    /// assigned to \c t and all other nodes have zero supply value.
+    ///
+    /// \param s The source node.
+    /// \param t The target node.
+    /// \param k The required amount of flow from node \c s to node \c t
+    /// (i.e. the supply of \c s and the demand of \c t).
+    ///
+    /// \return <tt>(*this)</tt>
+    CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
+      for (int i = 0; i != _node_num; ++i) {
+        _supply[i] = 0;
+      }
+      _supply[_node_id[s]] =  k;
+      _supply[_node_id[t]] = -k;
+      return *this;
+    }
+    /// @}
+    /// \name Execution control
+    /// The algorithm can be executed using \ref run().
+    /// @{
+    /// \brief Run the algorithm.
+    ///
+    /// This function runs the algorithm.
+    /// The paramters can be specified using functions \ref lowerMap(),
+    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
+    /// For example,
+    /// \code
+    ///   CapacityScaling<ListDigraph> cs(graph);
+    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// This function can be called more than once. All the parameters
+    /// that have been given are kept for the next call, unless
+    /// \ref reset() is called, thus only the modified parameters
+    /// have to be set again. See \ref reset() for examples.
+    /// However, the underlying digraph must not be modified after this
+    /// class have been constructed, since it copies and extends the graph.
+    ///
+    /// \param factor The capacity scaling factor. It must be larger than
+    /// one to use scaling. If it is less or equal to one, then scaling
+    /// will be disabled.
+    ///
+    /// \return \c INFEASIBLE if no feasible flow exists,
+    /// \n \c OPTIMAL if the problem has optimal solution
+    /// (i.e. it is feasible and bounded), and the algorithm has found
+    /// optimal flow and node potentials (primal and dual solutions),
+    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
+    /// and infinite upper bound. It means that the objective function
+    /// is unbounded on that arc, however, note that it could actually be
+    /// bounded over the feasible flows, but this algroithm cannot handle
+    /// these cases.
+    ///
+    /// \see ProblemType
+    ProblemType run(int factor = 4) {
+      _factor = factor;
+      ProblemType pt = init();
+      if (pt != OPTIMAL) return pt;
+      return start();
+    }
+    /// \brief Reset all the parameters that have been given before.
+    ///
+    /// This function resets all the paramaters that have been given
+    /// before using functions \ref lowerMap(), \ref upperMap(),
+    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
+    ///
+    /// It is useful for multiple run() calls. If this function is not
+    /// used, all the parameters given before are kept for the next
+    /// \ref run() call.
+    /// However, the underlying digraph must not be modified after this
+    /// class have been constructed, since it copies and extends the graph.
+    ///
+    /// For example,
+    /// \code
+    ///   CapacityScaling<ListDigraph> cs(graph);
+    ///
+    ///   // First run
+    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    ///
+    ///   // Run again with modified cost map (reset() is not called,
+    ///   // so only the cost map have to be set again)
+    ///   cost[e] += 100;
+    ///   cs.costMap(cost).run();
+    ///
+    ///   // Run again from scratch using reset()
+    ///   // (the lower bounds will be set to zero on all arcs)
+    ///   cs.reset();
+    ///   cs.upperMap(capacity).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// \return <tt>(*this)</tt>
+    CapacityScaling& reset() {
+      for (int i = 0; i != _node_num; ++i) {
+        _supply[i] = 0;
+      }
+      for (int j = 0; j != _res_arc_num; ++j) {
+        _lower[j] = 0;
+        _upper[j] = INF;
+        _cost[j] = _forward[j] ? 1 : -1;
+      }
+      _have_lower = false;
+      resetParams();
       return *this;
+    }
 …
       if (_factor > 1) {
         // With scaling
         Value max_sup = 0, max_dem = 0;
         for (int i = 0; i != _node_num; ++i) {
+        Value max_sup = 0, max_dem = 0, max_cap = 0;
+        for (int i = 0; i != _root; ++i) {
           Value ex = _excess[i];
           if ( ex > max_sup) max_sup =  ex;
           if (-ex > max_dem) max_dem = -ex;
+        }
         Value max_cap = 0;
         for (int j = 0; j != _res_arc_num; ++j) {
           if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
+          int last_out = _first_out[i+1] - 1;
+          for (int j = _first_out[i]; j != last_out; ++j) {
+            if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
+          }
+        }
         max_sup = std::min(std::min(max_sup, max_dem), max_cap);

lemon/circulation.h

-                      r786
+                      r825
      \tparam SM The type of the supply map. The default map type is
      \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
+     \tparam TR The traits class that defines various types used by the
+     algorithm. By default, it is \ref CirculationDefaultTraits
+     "CirculationDefaultTraits<GR, LM, UM, SM>".
+     In most cases, this parameter should not be set directly,
+     consider to use the named template parameters instead.
   */
 #ifdef DOXYGEN

lemon/cost_scaling.h

-                      r821
+                      r840
   /// \tparam GR The digraph type the algorithm runs on.
   /// \tparam V The number type used for flow amounts, capacity bounds
   /// and supply values in the algorithm. By default it is \c int.
+  /// and supply values in the algorithm. By default, it is \c int.
   /// \tparam C The number type used for costs and potentials in the
+  /// algorithm. By default it is the same as \c V.
+  /// algorithm. By default, it is the same as \c V.
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref CostScalingDefaultTraits
+  /// "CostScalingDefaultTraits<GR, V, C>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
   ///
   /// \warning Both number types must be signed and all input data must
 …
     ///
     /// The large cost type used for internal computations.
+    /// Using the \ref CostScalingDefaultTraits "default traits class",
+    /// it is \c long \c long if the \c Cost type is integer,
+    /// By default, it is \c long \c long if the \c Cost type is integer,
     /// otherwise it is \c double.
     typedef typename TR::LargeCost LargeCost;
 …
     typedef std::vector<int> IntVector;
-    typedef std::vector<char> BoolVector;
     typedef std::vector<Value> ValueVector;
     typedef std::vector<Cost> CostVector;
     typedef std::vector<LargeCost> LargeCostVector;
+    typedef std::vector<char> BoolVector;
+    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
   private:
 …
     bool _have_lower;
     Value _sum_supply;
+    int _sup_node_num;
     // Data structures for storing the digraph
 …
     int _alpha;
+    IntVector _buckets;
+    IntVector _bucket_next;
+    IntVector _bucket_prev;
+    IntVector _rank;
+    int _max_rank;
     // Data for a StaticDigraph structure
     typedef std::pair<int, int> IntPair;
 …
       LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
         "The cost type of CostScaling must be signed");
+      // Reset data structures
+      reset();
+    }
+    /// \name Parameters
+    /// The parameters of the algorithm can be specified using these
+    /// functions.
+    /// @{
+    /// \brief Set the lower bounds on the arcs.
+    ///
+    /// This function sets the lower bounds on the arcs.
+    /// If it is not used before calling \ref run(), the lower bounds
+    /// will be set to zero on all arcs.
+    ///
+    /// \param map An arc map storing the lower bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template <typename LowerMap>
+    CostScaling& lowerMap(const LowerMap& map) {
+      _have_lower = true;
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _lower[_arc_idf[a]] = map[a];
+        _lower[_arc_idb[a]] = map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the upper bounds (capacities) on the arcs.
+    ///
+    /// This function sets the upper bounds (capacities) on the arcs.
+    /// If it is not used before calling \ref run(), the upper bounds
+    /// will be set to \ref INF on all arcs (i.e. the flow value will be
+    /// unbounded from above).
+    ///
+    /// \param map An arc map storing the upper bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename UpperMap>
+    CostScaling& upperMap(const UpperMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _upper[_arc_idf[a]] = map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the costs of the arcs.
+    ///
+    /// This function sets the costs of the arcs.
+    /// If it is not used before calling \ref run(), the costs
+    /// will be set to \c 1 on all arcs.
+    ///
+    /// \param map An arc map storing the costs.
+    /// Its \c Value type must be convertible to the \c Cost type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename CostMap>
+    CostScaling& costMap(const CostMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _scost[_arc_idf[a]] =  map[a];
+        _scost[_arc_idb[a]] = -map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the supply values of the nodes.
+    ///
+    /// This function sets the supply values of the nodes.
+    /// If neither this function nor \ref stSupply() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// \param map A node map storing the supply values.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename SupplyMap>
+    CostScaling& supplyMap(const SupplyMap& map) {
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        _supply[_node_id[n]] = map[n];
+      }
+      return *this;
+    }
+    /// \brief Set single source and target nodes and a supply value.
+    ///
+    /// This function sets a single source node and a single target node
+    /// and the required flow value.
+    /// If neither this function nor \ref supplyMap() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// Using this function has the same effect as using \ref supplyMap()
+    /// with such a map in which \c k is assigned to \c s, \c -k is
+    /// assigned to \c t and all other nodes have zero supply value.
+    ///
+    /// \param s The source node.
+    /// \param t The target node.
+    /// \param k The required amount of flow from node \c s to node \c t
+    /// (i.e. the supply of \c s and the demand of \c t).
+    ///
+    /// \return <tt>(*this)</tt>
+    CostScaling& stSupply(const Node& s, const Node& t, Value k) {
+      for (int i = 0; i != _res_node_num; ++i) {
+        _supply[i] = 0;
+      }
+      _supply[_node_id[s]] =  k;
+      _supply[_node_id[t]] = -k;
+      return *this;
+    }
+    /// @}
+    /// \name Execution control
+    /// The algorithm can be executed using \ref run().
+    /// @{
+    /// \brief Run the algorithm.
+    ///
+    /// This function runs the algorithm.
+    /// The paramters can be specified using functions \ref lowerMap(),
+    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
+    /// For example,
+    /// \code
+    ///   CostScaling<ListDigraph> cs(graph);
+    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// This function can be called more than once. All the given parameters
+    /// are kept for the next call, unless \ref resetParams() or \ref reset()
+    /// is used, thus only the modified parameters have to be set again.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class (or the last \ref reset() call), then the \ref reset()
+    /// function must be called.
+    ///
+    /// \param method The internal method that will be used in the
+    /// algorithm. For more information, see \ref Method.
+    /// \param factor The cost scaling factor. It must be larger than one.
+    ///
+    /// \return \c INFEASIBLE if no feasible flow exists,
+    /// \n \c OPTIMAL if the problem has optimal solution
+    /// (i.e. it is feasible and bounded), and the algorithm has found
+    /// optimal flow and node potentials (primal and dual solutions),
+    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
+    /// and infinite upper bound. It means that the objective function
+    /// is unbounded on that arc, however, note that it could actually be
+    /// bounded over the feasible flows, but this algroithm cannot handle
+    /// these cases.
+    ///
+    /// \see ProblemType, Method
+    /// \see resetParams(), reset()
+    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
+      _alpha = factor;
+      ProblemType pt = init();
+      if (pt != OPTIMAL) return pt;
+      start(method);
+      return OPTIMAL;
+    }
+    /// \brief Reset all the parameters that have been given before.
+    ///
+    /// This function resets all the paramaters that have been given
+    /// before using functions \ref lowerMap(), \ref upperMap(),
+    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
+    ///
+    /// It is useful for multiple \ref run() calls. Basically, all the given
+    /// parameters are kept for the next \ref run() call, unless
+    /// \ref resetParams() or \ref reset() is used.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class or the last \ref reset() call, then the \ref reset()
+    /// function must be used, otherwise \ref resetParams() is sufficient.
+    ///
+    /// For example,
+    /// \code
+    ///   CostScaling<ListDigraph> cs(graph);
+    ///
+    ///   // First run
+    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    ///
+    ///   // Run again with modified cost map (resetParams() is not called,
+    ///   // so only the cost map have to be set again)
+    ///   cost[e] += 100;
+    ///   cs.costMap(cost).run();
+    ///
+    ///   // Run again from scratch using resetParams()
+    ///   // (the lower bounds will be set to zero on all arcs)
+    ///   cs.resetParams();
+    ///   cs.upperMap(capacity).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// \return <tt>(*this)</tt>
+    ///
+    /// \see reset(), run()
+    CostScaling& resetParams() {
+      for (int i = 0; i != _res_node_num; ++i) {
+        _supply[i] = 0;
+      }
+      int limit = _first_out[_root];
+      for (int j = 0; j != limit; ++j) {
+        _lower[j] = 0;
+        _upper[j] = INF;
+        _scost[j] = _forward[j] ? 1 : -1;
+      }
+      for (int j = limit; j != _res_arc_num; ++j) {
+        _lower[j] = 0;
+        _upper[j] = INF;
+        _scost[j] = 0;
+        _scost[_reverse[j]] = 0;
+      }
+      _have_lower = false;
+      return *this;
+    }
+    /// \brief Reset all the parameters that have been given before.
+    ///
+    /// This function resets all the paramaters that have been given
+    /// before using functions \ref lowerMap(), \ref upperMap(),
+    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
+    ///
+    /// It is useful for multiple run() calls. If this function is not
+    /// used, all the parameters given before are kept for the next
+    /// \ref run() call.
+    /// However, the underlying digraph must not be modified after this
+    /// class have been constructed, since it copies and extends the graph.
+    /// \return <tt>(*this)</tt>
+    CostScaling& reset() {
       // Resize vectors
       _node_num = countNodes(_graph);
 …
       // Reset parameters
+      reset();
+    }
+    /// \name Parameters
+    /// The parameters of the algorithm can be specified using these
+    /// functions.
+    /// @{
+    /// \brief Set the lower bounds on the arcs.
+    ///
+    /// This function sets the lower bounds on the arcs.
+    /// If it is not used before calling \ref run(), the lower bounds
+    /// will be set to zero on all arcs.
+    ///
+    /// \param map An arc map storing the lower bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template <typename LowerMap>
+    CostScaling& lowerMap(const LowerMap& map) {
+      _have_lower = true;
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _lower[_arc_idf[a]] = map[a];
+        _lower[_arc_idb[a]] = map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the upper bounds (capacities) on the arcs.
+    ///
+    /// This function sets the upper bounds (capacities) on the arcs.
+    /// If it is not used before calling \ref run(), the upper bounds
+    /// will be set to \ref INF on all arcs (i.e. the flow value will be
+    /// unbounded from above).
+    ///
+    /// \param map An arc map storing the upper bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename UpperMap>
+    CostScaling& upperMap(const UpperMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _upper[_arc_idf[a]] = map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the costs of the arcs.
+    ///
+    /// This function sets the costs of the arcs.
+    /// If it is not used before calling \ref run(), the costs
+    /// will be set to \c 1 on all arcs.
+    ///
+    /// \param map An arc map storing the costs.
+    /// Its \c Value type must be convertible to the \c Cost type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename CostMap>
+    CostScaling& costMap(const CostMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _scost[_arc_idf[a]] =  map[a];
+        _scost[_arc_idb[a]] = -map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the supply values of the nodes.
+    ///
+    /// This function sets the supply values of the nodes.
+    /// If neither this function nor \ref stSupply() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// \param map A node map storing the supply values.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename SupplyMap>
+    CostScaling& supplyMap(const SupplyMap& map) {
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        _supply[_node_id[n]] = map[n];
+      }
+      return *this;
+    }
+    /// \brief Set single source and target nodes and a supply value.
+    ///
+    /// This function sets a single source node and a single target node
+    /// and the required flow value.
+    /// If neither this function nor \ref supplyMap() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// Using this function has the same effect as using \ref supplyMap()
+    /// with such a map in which \c k is assigned to \c s, \c -k is
+    /// assigned to \c t and all other nodes have zero supply value.
+    ///
+    /// \param s The source node.
+    /// \param t The target node.
+    /// \param k The required amount of flow from node \c s to node \c t
+    /// (i.e. the supply of \c s and the demand of \c t).
+    ///
+    /// \return <tt>(*this)</tt>
+    CostScaling& stSupply(const Node& s, const Node& t, Value k) {
+      for (int i = 0; i != _res_node_num; ++i) {
+        _supply[i] = 0;
+      }
+      _supply[_node_id[s]] =  k;
+      _supply[_node_id[t]] = -k;
+      return *this;
+    }
+    /// @}
+    /// \name Execution control
+    /// The algorithm can be executed using \ref run().
+    /// @{
+    /// \brief Run the algorithm.
+    ///
+    /// This function runs the algorithm.
+    /// The paramters can be specified using functions \ref lowerMap(),
+    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
+    /// For example,
+    /// \code
+    ///   CostScaling<ListDigraph> cs(graph);
+    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// This function can be called more than once. All the parameters
+    /// that have been given are kept for the next call, unless
+    /// \ref reset() is called, thus only the modified parameters
+    /// have to be set again. See \ref reset() for examples.
+    /// However, the underlying digraph must not be modified after this
+    /// class have been constructed, since it copies and extends the graph.
+    ///
+    /// \param method The internal method that will be used in the
+    /// algorithm. For more information, see \ref Method.
+    /// \param factor The cost scaling factor. It must be larger than one.
+    ///
+    /// \return \c INFEASIBLE if no feasible flow exists,
+    /// \n \c OPTIMAL if the problem has optimal solution
+    /// (i.e. it is feasible and bounded), and the algorithm has found
+    /// optimal flow and node potentials (primal and dual solutions),
+    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
+    /// and infinite upper bound. It means that the objective function
+    /// is unbounded on that arc, however, note that it could actually be
+    /// bounded over the feasible flows, but this algroithm cannot handle
+    /// these cases.
+    ///
+    /// \see ProblemType, Method
+    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
+      _alpha = factor;
+      ProblemType pt = init();
+      if (pt != OPTIMAL) return pt;
+      start(method);
+      return OPTIMAL;
+    }
+    /// \brief Reset all the parameters that have been given before.
+    ///
+    /// This function resets all the paramaters that have been given
+    /// before using functions \ref lowerMap(), \ref upperMap(),
+    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
+    ///
+    /// It is useful for multiple run() calls. If this function is not
+    /// used, all the parameters given before are kept for the next
+    /// \ref run() call.
+    /// However, the underlying digraph must not be modified after this
+    /// class have been constructed, since it copies and extends the graph.
+    ///
+    /// For example,
+    /// \code
+    ///   CostScaling<ListDigraph> cs(graph);
+    ///
+    ///   // First run
+    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    ///
+    ///   // Run again with modified cost map (reset() is not called,
+    ///   // so only the cost map have to be set again)
+    ///   cost[e] += 100;
+    ///   cs.costMap(cost).run();
+    ///
+    ///   // Run again from scratch using reset()
+    ///   // (the lower bounds will be set to zero on all arcs)
+    ///   cs.reset();
+    ///   cs.upperMap(capacity).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// \return <tt>(*this)</tt>
+    CostScaling& reset() {
+      for (int i = 0; i != _res_node_num; ++i) {
+        _supply[i] = 0;
+      }
+      int limit = _first_out[_root];
+      for (int j = 0; j != limit; ++j) {
+        _lower[j] = 0;
+        _upper[j] = INF;
+        _scost[j] = _forward[j] ? 1 : -1;
+      }
+      for (int j = limit; j != _res_arc_num; ++j) {
+        _lower[j] = 0;
+        _upper[j] = INF;
+        _scost[j] = 0;
+        _scost[_reverse[j]] = 0;
+      }
+      _have_lower = false;
+      resetParams();
       return *this;
+    }
 …
+      }
+      _sup_node_num = 0;
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        if (sup[n] > 0) ++_sup_node_num;
+      }
       // Find a feasible flow using Circulation
       Circulation<Digraph, ConstMap<Arc, Value>, ValueArcMap, ValueNodeMap>
 …
         for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
           int ra = _reverse[a];
           _res_cap[a] = 1;
+          _res_cap[a] = 0;
           _res_cap[ra] = 0;
           _cost[a] = 0;
 …
       // Maximum path length for partial augment
       const int MAX_PATH_LENGTH = 4;
+      // Initialize data structures for buckets
+      _max_rank = _alpha * _res_node_num;
+      _buckets.resize(_max_rank);
+      _bucket_next.resize(_res_node_num + 1);
+      _bucket_prev.resize(_res_node_num + 1);
+      _rank.resize(_res_node_num + 1);
       // Execute the algorithm
       switch (method) {
 …
+      }
+    }
+    // Initialize a cost scaling phase
+    void initPhase() {
+      // Saturate arcs not satisfying the optimality condition
+      for (int u = 0; u != _res_node_num; ++u) {
+        int last_out = _first_out[u+1];
+        LargeCost pi_u = _pi[u];
+        for (int a = _first_out[u]; a != last_out; ++a) {
+          int v = _target[a];
+          if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) {
+            Value delta = _res_cap[a];
+            _excess[u] -= delta;
+            _excess[v] += delta;
+            _res_cap[a] = 0;
+            _res_cap[_reverse[a]] += delta;
+          }
+        }
+      }
+      // Find active nodes (i.e. nodes with positive excess)
+      for (int u = 0; u != _res_node_num; ++u) {
+        if (_excess[u] > 0) _active_nodes.push_back(u);
+      }
+      // Initialize the next arcs
+      for (int u = 0; u != _res_node_num; ++u) {
+        _next_out[u] = _first_out[u];
+      }
+    }
+    // Early termination heuristic
+    bool earlyTermination() {
+      const double EARLY_TERM_FACTOR = 3.0;
+      // Build a static residual graph
+      _arc_vec.clear();
+      _cost_vec.clear();
+      for (int j = 0; j != _res_arc_num; ++j) {
+        if (_res_cap[j] > 0) {
+          _arc_vec.push_back(IntPair(_source[j], _target[j]));
+          _cost_vec.push_back(_cost[j] + 1);
+        }
+      }
+      _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
+      // Run Bellman-Ford algorithm to check if the current flow is optimal
+      BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
+      bf.init(0);
+      bool done = false;
+      int K = int(EARLY_TERM_FACTOR * std::sqrt(double(_res_node_num)));
+      for (int i = 0; i < K && !done; ++i) {
+        done = bf.processNextWeakRound();
+      }
+      return done;
+    }
+    // Global potential update heuristic
+    void globalUpdate() {
+      int bucket_end = _root + 1;
+      // Initialize buckets
+      for (int r = 0; r != _max_rank; ++r) {
+        _buckets[r] = bucket_end;
+      }
+      Value total_excess = 0;
+      for (int i = 0; i != _res_node_num; ++i) {
+        if (_excess[i] < 0) {
+          _rank[i] = 0;
+          _bucket_next[i] = _buckets[0];
+          _bucket_prev[_buckets[0]] = i;
+          _buckets[0] = i;
+        } else {
+          total_excess += _excess[i];
+          _rank[i] = _max_rank;
+        }
+      }
+      if (total_excess == 0) return;
+      // Search the buckets
+      int r = 0;
+      for ( ; r != _max_rank; ++r) {
+        while (_buckets[r] != bucket_end) {
+          // Remove the first node from the current bucket
+          int u = _buckets[r];
+          _buckets[r] = _bucket_next[u];
+          // Search the incomming arcs of u
+          LargeCost pi_u = _pi[u];
+          int last_out = _first_out[u+1];
+          for (int a = _first_out[u]; a != last_out; ++a) {
+            int ra = _reverse[a];
+            if (_res_cap[ra] > 0) {
+              int v = _source[ra];
+              int old_rank_v = _rank[v];
+              if (r < old_rank_v) {
+                // Compute the new rank of v
+                LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
+                int new_rank_v = old_rank_v;
+                if (nrc < LargeCost(_max_rank))
+                  new_rank_v = r + 1 + int(nrc);
+                // Change the rank of v
+                if (new_rank_v < old_rank_v) {
+                  _rank[v] = new_rank_v;
+                  _next_out[v] = _first_out[v];
+                  // Remove v from its old bucket
+                  if (old_rank_v < _max_rank) {
+                    if (_buckets[old_rank_v] == v) {
+                      _buckets[old_rank_v] = _bucket_next[v];
+                    } else {
+                      _bucket_next[_bucket_prev[v]] = _bucket_next[v];
+                      _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
+                    }
+                  }
+                  // Insert v to its new bucket
+                  _bucket_next[v] = _buckets[new_rank_v];
+                  _bucket_prev[_buckets[new_rank_v]] = v;
+                  _buckets[new_rank_v] = v;
+                }
+              }
+            }
+          }
+          // Finish search if there are no more active nodes
+          if (_excess[u] > 0) {
+            total_excess -= _excess[u];
+            if (total_excess <= 0) break;
+          }
+        }
+        if (total_excess <= 0) break;
+      }
+      // Relabel nodes
+      for (int u = 0; u != _res_node_num; ++u) {
+        int k = std::min(_rank[u], r);
+        if (k > 0) {
+          _pi[u] -= _epsilon * k;
+          _next_out[u] = _first_out[u];
+        }
+      }
+    }
     /// Execute the algorithm performing augment and relabel operations
     void startAugment(int max_length = std::numeric_limits<int>::max()) {
       // Paramters for heuristics
+      const int BF_HEURISTIC_EPSILON_BOUND = 1000;
+      const int BF_HEURISTIC_BOUND_FACTOR  = 3;
+      const int EARLY_TERM_EPSILON_LIMIT = 1000;
+      const double GLOBAL_UPDATE_FACTOR = 3.0;
+      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
+        (_res_node_num + _sup_node_num * _sup_node_num));
+      int next_update_limit = global_update_freq;
+      int relabel_cnt = 0;
       // Perform cost scaling phases
+      IntVector pred_arc(_res_node_num);
+      std::vector<int> path_nodes;
+      std::vector<int> path;
       for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
 : _epsilon / _alpha )
+      {
+        // "Early Termination" heuristic: use Bellman-Ford algorithm
+        // to check if the current flow is optimal
+        if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) {
+          _arc_vec.clear();
+          _cost_vec.clear();
+          for (int j = 0; j != _res_arc_num; ++j) {
+            if (_res_cap[j] > 0) {
+              _arc_vec.push_back(IntPair(_source[j], _target[j]));
+              _cost_vec.push_back(_cost[j] + 1);
+            }
+          }
+          _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
+          BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
+          bf.init(0);
+          bool done = false;
+          int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num));
+          for (int i = 0; i < K && !done; ++i)
+            done = bf.processNextWeakRound();
+          if (done) break;
+        }
+        // Saturate arcs not satisfying the optimality condition
+        for (int a = 0; a != _res_arc_num; ++a) {
+          if (_res_cap[a] > 0 &&
+              _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
+            Value delta = _res_cap[a];
+            _excess[_source[a]] -= delta;
+            _excess[_target[a]] += delta;
+            _res_cap[a] = 0;
+            _res_cap[_reverse[a]] += delta;
+          }
+        // Early termination heuristic
+        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
+          if (earlyTermination()) break;
+        }
+        // Find active nodes (i.e. nodes with positive excess)
+        for (int u = 0; u != _res_node_num; ++u) {
+          if (_excess[u] > 0) _active_nodes.push_back(u);
+        }
+        // Initialize the next arcs
+        for (int u = 0; u != _res_node_num; ++u) {
+          _next_out[u] = _first_out[u];
+        }
+        // Initialize current phase
+        initPhase();
         // Perform partial augment and relabel operations
         while (true) {
 …
           if (_active_nodes.size() == 0) break;
           int start = _active_nodes.front();
-          path_nodes.clear();
-          path_nodes.push_back(start);
           // Find an augmenting path from the start node
+          path.clear();
           int tip = start;
+          while (_excess[tip] >= 0 &&
+                 int(path_nodes.size()) <= max_length) {
+          while (_excess[tip] >= 0 && int(path.size()) < max_length) {
             int u;
+            LargeCost min_red_cost, rc;
+            int last_out = _sum_supply < 0 ?
+              _first_out[tip+1] : _first_out[tip+1] - 1;
+            LargeCost min_red_cost, rc, pi_tip = _pi[tip];
+            int last_out = _first_out[tip+1];
             for (int a = _next_out[tip]; a != last_out; ++a) {
+              if (_res_cap[a] > 0 &&
+                  _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
+                u = _target[a];
+                pred_arc[u] = a;
+              u = _target[a];
+              if (_res_cap[a] > 0 && _cost[a] + pi_tip - _pi[u] < 0) {
+                path.push_back(a);
                 _next_out[tip] = a;
                 tip = u;
-                path_nodes.push_back(tip);
                 goto next_step;
+              }
 …
             // Relabel tip node
+            min_red_cost = std::numeric_limits<LargeCost>::max() / 2;
+            min_red_cost = std::numeric_limits<LargeCost>::max();
+            if (tip != start) {
+              int ra = _reverse[path.back()];
+              min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]];
+            }
             for (int a = _first_out[tip]; a != last_out; ++a) {
               rc = _cost[a] + _pi[_source[a]] - _pi[_target[a]];
+              rc = _cost[a] + pi_tip - _pi[_target[a]];
               if (_res_cap[a] > 0 && rc < min_red_cost) {
                 min_red_cost = rc;
 …
+            }
             _pi[tip] -= min_red_cost + _epsilon;
-            // Reset the next arc of tip
             _next_out[tip] = _first_out[tip];
+            ++relabel_cnt;
             // Step back
             if (tip != start) {
               path_nodes.pop_back();
               tip = path_nodes.back();
+              tip = _source[path.back()];
+              path.pop_back();
+            }
 …
           // Augment along the found path (as much flow as possible)
           Value delta;
+          int u, v = path_nodes.front(), pa;
+          for (int i = 1; i < int(path_nodes.size()); ++i) {
+          int pa, u, v = start;
+          for (int i = 0; i != int(path.size()); ++i) {
+            pa = path[i];
             u = v;
+            v = path_nodes[i];
+            pa = pred_arc[v];
+            v = _target[pa];
             delta = std::min(_res_cap[pa], _excess[u]);
             _res_cap[pa] -= delta;
 …
               _active_nodes.push_back(v);
+          }
+          // Global update heuristic
+          if (relabel_cnt >= next_update_limit) {
+            globalUpdate();
+            next_update_limit += global_update_freq;
+          }
+        }
+      }
 …
     void startPush() {
       // Paramters for heuristics
+      const int BF_HEURISTIC_EPSILON_BOUND = 1000;
+      const int BF_HEURISTIC_BOUND_FACTOR  = 3;
+      const int EARLY_TERM_EPSILON_LIMIT = 1000;
+      const double GLOBAL_UPDATE_FACTOR = 2.0;
+      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
+        (_res_node_num + _sup_node_num * _sup_node_num));
+      int next_update_limit = global_update_freq;
+      int relabel_cnt = 0;
       // Perform cost scaling phases
       BoolVector hyper(_res_node_num, false);
+      LargeCostVector hyper_cost(_res_node_num);
       for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
 : _epsilon / _alpha )
+      {
+        // "Early Termination" heuristic: use Bellman-Ford algorithm
+        // to check if the current flow is optimal
+        if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) {
+          _arc_vec.clear();
+          _cost_vec.clear();
+          for (int j = 0; j != _res_arc_num; ++j) {
+            if (_res_cap[j] > 0) {
+              _arc_vec.push_back(IntPair(_source[j], _target[j]));
+              _cost_vec.push_back(_cost[j] + 1);
+            }
+          }
+          _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
+          BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
+          bf.init(0);
+          bool done = false;
+          int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num));
+          for (int i = 0; i < K && !done; ++i)
+            done = bf.processNextWeakRound();
+          if (done) break;
+        }
+        // Saturate arcs not satisfying the optimality condition
+        for (int a = 0; a != _res_arc_num; ++a) {
+          if (_res_cap[a] > 0 &&
+              _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
+            Value delta = _res_cap[a];
+            _excess[_source[a]] -= delta;
+            _excess[_target[a]] += delta;
+            _res_cap[a] = 0;
+            _res_cap[_reverse[a]] += delta;
+          }
+        }
+        // Find active nodes (i.e. nodes with positive excess)
+        for (int u = 0; u != _res_node_num; ++u) {
+          if (_excess[u] > 0) _active_nodes.push_back(u);
+        }
+        // Initialize the next arcs
+        for (int u = 0; u != _res_node_num; ++u) {
+          _next_out[u] = _first_out[u];
+        }
+        // Early termination heuristic
+        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
+          if (earlyTermination()) break;
+        }
+        // Initialize current phase
+        initPhase();
         // Perform push and relabel operations
         while (_active_nodes.size() > 0) {
           LargeCost min_red_cost, rc;
+          LargeCost min_red_cost, rc, pi_n;
           Value delta;
           int n, t, a, last_out = _res_arc_num;
+        next_node:
           // Select an active node (FIFO selection)
-        next_node:
           n = _active_nodes.front();
           last_out = _sum_supply < 0 ?
             _first_out[n+1] : _first_out[n+1] - 1;
+          last_out = _first_out[n+1];
+          pi_n = _pi[n];
           // Perform push operations if there are admissible arcs
           if (_excess[n] > 0) {
             for (a = _next_out[n]; a != last_out; ++a) {
               if (_res_cap[a] > 0 &&
                   _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
+                  _cost[a] + pi_n - _pi[_target[a]] < 0) {
                 delta = std::min(_res_cap[a], _excess[n]);
                 t = _target[a];
 …
                 // Push-look-ahead heuristic
                 Value ahead = -_excess[t];
                 int last_out_t = _sum_supply < 0 ?
                   _first_out[t+1] : _first_out[t+1] - 1;
+                int last_out_t = _first_out[t+1];
+                LargeCost pi_t = _pi[t];
                 for (int ta = _next_out[t]; ta != last_out_t; ++ta) {
                   if (_res_cap[ta] > 0 &&
                       _cost[ta] + _pi[_source[ta]] - _pi[_target[ta]] < 0)
+                      _cost[ta] + pi_t - _pi[_target[ta]] < 0)
                     ahead += _res_cap[ta];
                   if (ahead >= delta) break;
 …
                 // Push flow along the arc
                 if (ahead < delta) {
+                if (ahead < delta && !hyper[t]) {
                   _res_cap[a] -= ahead;
                   _res_cap[_reverse[a]] += ahead;
 …
                   _active_nodes.push_front(t);
                   hyper[t] = true;
+                  hyper_cost[t] = _cost[a] + pi_n - pi_t;
                   _next_out[n] = a;
                   goto next_node;
 …
           // Relabel the node if it is still active (or hyper)
           if (_excess[n] > 0 || hyper[n]) {
+            min_red_cost = std::numeric_limits<LargeCost>::max() / 2;
+             min_red_cost = hyper[n] ? -hyper_cost[n] :
+               std::numeric_limits<LargeCost>::max();
             for (int a = _first_out[n]; a != last_out; ++a) {
               rc = _cost[a] + _pi[_source[a]] - _pi[_target[a]];
+              rc = _cost[a] + pi_n - _pi[_target[a]];
               if (_res_cap[a] > 0 && rc < min_red_cost) {
                 min_red_cost = rc;
 …
+            }
             _pi[n] -= min_red_cost + _epsilon;
+            _next_out[n] = _first_out[n];
             hyper[n] = false;
+            // Reset the next arc
+            _next_out[n] = _first_out[n];
+            ++relabel_cnt;
+          }
 …
             _active_nodes.pop_front();
+          }
+          // Global update heuristic
+          if (relabel_cnt >= next_update_limit) {
+            globalUpdate();
+            for (int u = 0; u != _res_node_num; ++u)
+              hyper[u] = false;
+            next_update_limit += global_update_freq;
+          }
+        }
+      }

lemon/cycle_canceling.h

-                      r820
+                      r840
     typedef std::vector<int> IntVector;
-    typedef std::vector<char> CharVector;
     typedef std::vector<double> DoubleVector;
     typedef std::vector<Value> ValueVector;
     typedef std::vector<Cost> CostVector;
+    typedef std::vector<char> BoolVector;
+    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
   private:
 …
     IntArcMap _arc_idb;
     IntVector _first_out;
     CharVector _forward;
+    BoolVector _forward;
     IntVector _source;
     IntVector _target;
 …
         "The cost type of CycleCanceling must be signed");
+      // Reset data structures
+      reset();
+    }
+    /// \name Parameters
+    /// The parameters of the algorithm can be specified using these
+    /// functions.
+    /// @{
+    /// \brief Set the lower bounds on the arcs.
+    ///
+    /// This function sets the lower bounds on the arcs.
+    /// If it is not used before calling \ref run(), the lower bounds
+    /// will be set to zero on all arcs.
+    ///
+    /// \param map An arc map storing the lower bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template <typename LowerMap>
+    CycleCanceling& lowerMap(const LowerMap& map) {
+      _have_lower = true;
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _lower[_arc_idf[a]] = map[a];
+        _lower[_arc_idb[a]] = map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the upper bounds (capacities) on the arcs.
+    ///
+    /// This function sets the upper bounds (capacities) on the arcs.
+    /// If it is not used before calling \ref run(), the upper bounds
+    /// will be set to \ref INF on all arcs (i.e. the flow value will be
+    /// unbounded from above).
+    ///
+    /// \param map An arc map storing the upper bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename UpperMap>
+    CycleCanceling& upperMap(const UpperMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _upper[_arc_idf[a]] = map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the costs of the arcs.
+    ///
+    /// This function sets the costs of the arcs.
+    /// If it is not used before calling \ref run(), the costs
+    /// will be set to \c 1 on all arcs.
+    ///
+    /// \param map An arc map storing the costs.
+    /// Its \c Value type must be convertible to the \c Cost type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename CostMap>
+    CycleCanceling& costMap(const CostMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _cost[_arc_idf[a]] =  map[a];
+        _cost[_arc_idb[a]] = -map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the supply values of the nodes.
+    ///
+    /// This function sets the supply values of the nodes.
+    /// If neither this function nor \ref stSupply() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// \param map A node map storing the supply values.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename SupplyMap>
+    CycleCanceling& supplyMap(const SupplyMap& map) {
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        _supply[_node_id[n]] = map[n];
+      }
+      return *this;
+    }
+    /// \brief Set single source and target nodes and a supply value.
+    ///
+    /// This function sets a single source node and a single target node
+    /// and the required flow value.
+    /// If neither this function nor \ref supplyMap() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// Using this function has the same effect as using \ref supplyMap()
+    /// with such a map in which \c k is assigned to \c s, \c -k is
+    /// assigned to \c t and all other nodes have zero supply value.
+    ///
+    /// \param s The source node.
+    /// \param t The target node.
+    /// \param k The required amount of flow from node \c s to node \c t
+    /// (i.e. the supply of \c s and the demand of \c t).
+    ///
+    /// \return <tt>(*this)</tt>
+    CycleCanceling& stSupply(const Node& s, const Node& t, Value k) {
+      for (int i = 0; i != _res_node_num; ++i) {
+        _supply[i] = 0;
+      }
+      _supply[_node_id[s]] =  k;
+      _supply[_node_id[t]] = -k;
+      return *this;
+    }
+    /// @}
+    /// \name Execution control
+    /// The algorithm can be executed using \ref run().
+    /// @{
+    /// \brief Run the algorithm.
+    ///
+    /// This function runs the algorithm.
+    /// The paramters can be specified using functions \ref lowerMap(),
+    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
+    /// For example,
+    /// \code
+    ///   CycleCanceling<ListDigraph> cc(graph);
+    ///   cc.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// This function can be called more than once. All the given parameters
+    /// are kept for the next call, unless \ref resetParams() or \ref reset()
+    /// is used, thus only the modified parameters have to be set again.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class (or the last \ref reset() call), then the \ref reset()
+    /// function must be called.
+    ///
+    /// \param method The cycle-canceling method that will be used.
+    /// For more information, see \ref Method.
+    ///
+    /// \return \c INFEASIBLE if no feasible flow exists,
+    /// \n \c OPTIMAL if the problem has optimal solution
+    /// (i.e. it is feasible and bounded), and the algorithm has found
+    /// optimal flow and node potentials (primal and dual solutions),
+    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
+    /// and infinite upper bound. It means that the objective function
+    /// is unbounded on that arc, however, note that it could actually be
+    /// bounded over the feasible flows, but this algroithm cannot handle
+    /// these cases.
+    ///
+    /// \see ProblemType, Method
+    /// \see resetParams(), reset()
+    ProblemType run(Method method = CANCEL_AND_TIGHTEN) {
+      ProblemType pt = init();
+      if (pt != OPTIMAL) return pt;
+      start(method);
+      return OPTIMAL;
+    }
+    /// \brief Reset all the parameters that have been given before.
+    ///
+    /// This function resets all the paramaters that have been given
+    /// before using functions \ref lowerMap(), \ref upperMap(),
+    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
+    ///
+    /// It is useful for multiple \ref run() calls. Basically, all the given
+    /// parameters are kept for the next \ref run() call, unless
+    /// \ref resetParams() or \ref reset() is used.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class or the last \ref reset() call, then the \ref reset()
+    /// function must be used, otherwise \ref resetParams() is sufficient.
+    ///
+    /// For example,
+    /// \code
+    ///   CycleCanceling<ListDigraph> cs(graph);
+    ///
+    ///   // First run
+    ///   cc.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    ///
+    ///   // Run again with modified cost map (resetParams() is not called,
+    ///   // so only the cost map have to be set again)
+    ///   cost[e] += 100;
+    ///   cc.costMap(cost).run();
+    ///
+    ///   // Run again from scratch using resetParams()
+    ///   // (the lower bounds will be set to zero on all arcs)
+    ///   cc.resetParams();
+    ///   cc.upperMap(capacity).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// \return <tt>(*this)</tt>
+    ///
+    /// \see reset(), run()
+    CycleCanceling& resetParams() {
+      for (int i = 0; i != _res_node_num; ++i) {
+        _supply[i] = 0;
+      }
+      int limit = _first_out[_root];
+      for (int j = 0; j != limit; ++j) {
+        _lower[j] = 0;
+        _upper[j] = INF;
+        _cost[j] = _forward[j] ? 1 : -1;
+      }
+      for (int j = limit; j != _res_arc_num; ++j) {
+        _lower[j] = 0;
+        _upper[j] = INF;
+        _cost[j] = 0;
+        _cost[_reverse[j]] = 0;
+      }
+      _have_lower = false;
+      return *this;
+    }
+    /// \brief Reset the internal data structures and all the parameters
+    /// that have been given before.
+    ///
+    /// This function resets the internal data structures and all the
+    /// paramaters that have been given before using functions \ref lowerMap(),
+    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
+    ///
+    /// It is useful for multiple \ref run() calls. Basically, all the given
+    /// parameters are kept for the next \ref run() call, unless
+    /// \ref resetParams() or \ref reset() is used.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class or the last \ref reset() call, then the \ref reset()
+    /// function must be used, otherwise \ref resetParams() is sufficient.
+    ///
+    /// See \ref resetParams() for examples.
+    ///
+    /// \return <tt>(*this)</tt>
+    ///
+    /// \see resetParams(), run()
+    CycleCanceling& reset() {
       // Resize vectors
       _node_num = countNodes(_graph);
 …
       // Reset parameters
+      reset();
+    }
+    /// \name Parameters
+    /// The parameters of the algorithm can be specified using these
+    /// functions.
+    /// @{
+    /// \brief Set the lower bounds on the arcs.
+    ///
+    /// This function sets the lower bounds on the arcs.
+    /// If it is not used before calling \ref run(), the lower bounds
+    /// will be set to zero on all arcs.
+    ///
+    /// \param map An arc map storing the lower bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template <typename LowerMap>
+    CycleCanceling& lowerMap(const LowerMap& map) {
+      _have_lower = true;
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _lower[_arc_idf[a]] = map[a];
+        _lower[_arc_idb[a]] = map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the upper bounds (capacities) on the arcs.
+    ///
+    /// This function sets the upper bounds (capacities) on the arcs.
+    /// If it is not used before calling \ref run(), the upper bounds
+    /// will be set to \ref INF on all arcs (i.e. the flow value will be
+    /// unbounded from above).
+    ///
+    /// \param map An arc map storing the upper bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename UpperMap>
+    CycleCanceling& upperMap(const UpperMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _upper[_arc_idf[a]] = map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the costs of the arcs.
+    ///
+    /// This function sets the costs of the arcs.
+    /// If it is not used before calling \ref run(), the costs
+    /// will be set to \c 1 on all arcs.
+    ///
+    /// \param map An arc map storing the costs.
+    /// Its \c Value type must be convertible to the \c Cost type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename CostMap>
+    CycleCanceling& costMap(const CostMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _cost[_arc_idf[a]] =  map[a];
+        _cost[_arc_idb[a]] = -map[a];
+      }
+      return *this;
+    }
+    /// \brief Set the supply values of the nodes.
+    ///
+    /// This function sets the supply values of the nodes.
+    /// If neither this function nor \ref stSupply() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// \param map A node map storing the supply values.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename SupplyMap>
+    CycleCanceling& supplyMap(const SupplyMap& map) {
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        _supply[_node_id[n]] = map[n];
+      }
+      return *this;
+    }
+    /// \brief Set single source and target nodes and a supply value.
+    ///
+    /// This function sets a single source node and a single target node
+    /// and the required flow value.
+    /// If neither this function nor \ref supplyMap() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// Using this function has the same effect as using \ref supplyMap()
+    /// with such a map in which \c k is assigned to \c s, \c -k is
+    /// assigned to \c t and all other nodes have zero supply value.
+    ///
+    /// \param s The source node.
+    /// \param t The target node.
+    /// \param k The required amount of flow from node \c s to node \c t
+    /// (i.e. the supply of \c s and the demand of \c t).
+    ///
+    /// \return <tt>(*this)</tt>
+    CycleCanceling& stSupply(const Node& s, const Node& t, Value k) {
+      for (int i = 0; i != _res_node_num; ++i) {
+        _supply[i] = 0;
+      }
+      _supply[_node_id[s]] =  k;
+      _supply[_node_id[t]] = -k;
+      return *this;
+    }
+    /// @}
+    /// \name Execution control
+    /// The algorithm can be executed using \ref run().
+    /// @{
+    /// \brief Run the algorithm.
+    ///
+    /// This function runs the algorithm.
+    /// The paramters can be specified using functions \ref lowerMap(),
+    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
+    /// For example,
+    /// \code
+    ///   CycleCanceling<ListDigraph> cc(graph);
+    ///   cc.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// This function can be called more than once. All the parameters
+    /// that have been given are kept for the next call, unless
+    /// \ref reset() is called, thus only the modified parameters
+    /// have to be set again. See \ref reset() for examples.
+    /// However, the underlying digraph must not be modified after this
+    /// class have been constructed, since it copies and extends the graph.
+    ///
+    /// \param method The cycle-canceling method that will be used.
+    /// For more information, see \ref Method.
+    ///
+    /// \return \c INFEASIBLE if no feasible flow exists,
+    /// \n \c OPTIMAL if the problem has optimal solution
+    /// (i.e. it is feasible and bounded), and the algorithm has found
+    /// optimal flow and node potentials (primal and dual solutions),
+    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
+    /// and infinite upper bound. It means that the objective function
+    /// is unbounded on that arc, however, note that it could actually be
+    /// bounded over the feasible flows, but this algroithm cannot handle
+    /// these cases.
+    ///
+    /// \see ProblemType, Method
+    ProblemType run(Method method = CANCEL_AND_TIGHTEN) {
+      ProblemType pt = init();
+      if (pt != OPTIMAL) return pt;
+      start(method);
+      return OPTIMAL;
+    }
+    /// \brief Reset all the parameters that have been given before.
+    ///
+    /// This function resets all the paramaters that have been given
+    /// before using functions \ref lowerMap(), \ref upperMap(),
+    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
+    ///
+    /// It is useful for multiple run() calls. If this function is not
+    /// used, all the parameters given before are kept for the next
+    /// \ref run() call.
+    /// However, the underlying digraph must not be modified after this
+    /// class have been constructed, since it copies and extends the graph.
+    ///
+    /// For example,
+    /// \code
+    ///   CycleCanceling<ListDigraph> cs(graph);
+    ///
+    ///   // First run
+    ///   cc.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    ///
+    ///   // Run again with modified cost map (reset() is not called,
+    ///   // so only the cost map have to be set again)
+    ///   cost[e] += 100;
+    ///   cc.costMap(cost).run();
+    ///
+    ///   // Run again from scratch using reset()
+    ///   // (the lower bounds will be set to zero on all arcs)
+    ///   cc.reset();
+    ///   cc.upperMap(capacity).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// \return <tt>(*this)</tt>
+    CycleCanceling& reset() {
+      for (int i = 0; i != _res_node_num; ++i) {
+        _supply[i] = 0;
+      }
+      int limit = _first_out[_root];
+      for (int j = 0; j != limit; ++j) {
+        _lower[j] = 0;
+        _upper[j] = INF;
+        _cost[j] = _forward[j] ? 1 : -1;
+      }
+      for (int j = limit; j != _res_arc_num; ++j) {
+        _lower[j] = 0;
+        _upper[j] = INF;
+        _cost[j] = 0;
+        _cost[_reverse[j]] = 0;
+      }
+      _have_lower = false;
+      resetParams();
       return *this;
+    }
 …
       DoubleVector pi(_res_node_num, 0.0);
       IntVector level(_res_node_num);
       CharVector reached(_res_node_num);
       CharVector processed(_res_node_num);
+      BoolVector reached(_res_node_num);
+      BoolVector processed(_res_node_num);
       IntVector pred_node(_res_node_num);
       IntVector pred_arc(_res_node_num);

lemon/dfs.h

-                      r788
+                      r825
   ///\tparam GR The type of the digraph the algorithm runs on.
   ///The default type is \ref ListDigraph.
+  ///\tparam TR The traits class that defines various types used by the
+  ///algorithm. By default, it is \ref DfsDefaultTraits
+  ///"DfsDefaultTraits<GR>".
+  ///In most cases, this parameter should not be set directly,
+  ///consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR,
 …
   /// This class should only be used through the \ref dfs() function,
   /// which makes it easier to use the algorithm.
+  ///
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm.
   template<class TR>
   class DfsWizard : public TR
 …
   /// does not observe the DFS events. If you want to observe the DFS
   /// events, you should implement your own visitor class.
   /// \tparam TR Traits class to set various data types used by the
   /// algorithm. The default traits class is
   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
   /// See \ref DfsVisitDefaultTraits for the documentation of
   /// a DFS visit traits class.
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref DfsVisitDefaultTraits
+  /// "DfsVisitDefaultTraits<GR>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR, typename VS, typename TR>

lemon/dijkstra.h

-                      r788
+                      r825
   ///it is necessary. The default map type is \ref
   ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
+  ///\tparam TR The traits class that defines various types used by the
+  ///algorithm. By default, it is \ref DijkstraDefaultTraits
+  ///"DijkstraDefaultTraits<GR, LEN>".
+  ///In most cases, this parameter should not be set directly,
+  ///consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR, typename LEN, typename TR>
 …
   /// This class should only be used through the \ref dijkstra() function,
   /// which makes it easier to use the algorithm.
+  ///
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm.
   template<class TR>
   class DijkstraWizard : public TR

lemon/glpk.h

-                      r746
+                      r833
 #include <lemon/lp_base.h>
-// forward declaration
-#if !defined _GLP_PROB && !defined GLP_PROB
-#define _GLP_PROB
-#define GLP_PROB
-typedef struct { double _opaque_prob; } glp_prob;
-/* LP/MIP problem object */
-#endif
 namespace lemon {
+  namespace _solver_bits {
+    class VoidPtr {
+    private:
+      void *_ptr;
+    public:
+      VoidPtr() : _ptr(0) {}
+      template <typename T>
+      VoidPtr(T* ptr) : _ptr(reinterpret_cast<void*>(ptr)) {}
+      template <typename T>
+      VoidPtr& operator=(T* ptr) {
+        _ptr = reinterpret_cast<void*>(ptr);
+        return *this;
+      }
+      template <typename T>
+      operator T*() const { return reinterpret_cast<T*>(_ptr); }
+    };
+  }
   /// \brief Base interface for the GLPK LP and MIP solver
 …
   protected:
+    typedef glp_prob LPX;
+    glp_prob* lp;
+    _solver_bits::VoidPtr lp;
     GlpkBase();
 …
     ///Pointer to the underlying GLPK data structure.
     LPX *lpx() {return lp;}
+    _solver_bits::VoidPtr lpx() {return lp;}
     ///Const pointer to the underlying GLPK data structure.
     const LPX *lpx() const {return lp;}
+    _solver_bits::VoidPtr lpx() const {return lp;}
     ///Returns the constraint identifier understood by GLPK.

lemon/graph_to_eps.h

-                      r786
+                      r838
 #else
       os << bits::getWinFormattedDate();
+      os << std::endl;
 #endif
+    }
-    os << std::endl;
     if (_autoArcWidthScale) {

lemon/hartmann_orlin.h

-                      r795
+                      r841
   /// \tparam LEN The type of the length map. The default
   /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref HartmannOrlinDefaultTraits
+  /// "HartmannOrlinDefaultTraits<GR, LEN>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR, typename LEN, typename TR>
 …
     ///
     /// The large value type used for internal computations.
+    /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
+    /// it is \c long \c long if the \c Value type is integer,
+    /// By default, it is \c long \c long if the \c Value type is integer,
     /// otherwise it is \c double.
     typedef typename TR::LargeValue LargeValue;
 …
     /// \pre \ref run() or \ref findMinMean() must be called before
     /// using this function.
     LargeValue cycleLength() const {
       return _best_length;
+    Value cycleLength() const {
+      return static_cast<Value>(_best_length);
+    }

lemon/howard.h

-                      r771
+                      r841
   /// \tparam LEN The type of the length map. The default
   /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref HowardDefaultTraits
+  /// "HowardDefaultTraits<GR, LEN>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR, typename LEN, typename TR>
 …
     ///
     /// The large value type used for internal computations.
+    /// Using the \ref HowardDefaultTraits "default traits class",
+    /// it is \c long \c long if the \c Value type is integer,
+    /// By default, it is \c long \c long if the \c Value type is integer,
     /// otherwise it is \c double.
     typedef typename TR::LargeValue LargeValue;
 …
     /// \pre \ref run() or \ref findMinMean() must be called before
     /// using this function.
     LargeValue cycleLength() const {
       return _best_length;
+    Value cycleLength() const {
+      return static_cast<Value>(_best_length);
+    }

lemon/karp.h

-                      r772
+                      r841
   /// \tparam LEN The type of the length map. The default
   /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref KarpDefaultTraits
+  /// "KarpDefaultTraits<GR, LEN>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR, typename LEN, typename TR>
 …
     ///
     /// The large value type used for internal computations.
+    /// Using the \ref KarpDefaultTraits "default traits class",
+    /// it is \c long \c long if the \c Value type is integer,
+    /// By default, it is \c long \c long if the \c Value type is integer,
     /// otherwise it is \c double.
     typedef typename TR::LargeValue LargeValue;
 …
     /// \pre \ref run() or \ref findMinMean() must be called before
     /// using this function.
     LargeValue cycleLength() const {
       return _cycle_length;
+    Value cycleLength() const {
+      return static_cast<Value>(_cycle_length);
+    }

lemon/lp_base.h

-                      r786
+                      r834
       Row r;
       c.expr().simplify();
       r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound():-INF,
+      r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF,
                                 ExprIterator(c.expr().comps.begin(), cols),
                                 ExprIterator(c.expr().comps.end(), cols),
                                 c.upperBounded()?c.upperBound():INF));
+                                c.upperBounded()?c.upperBound()-*c.expr():INF));
       return r;
+    }

lemon/min_cost_arborescence.h

-                      r713
+                      r825
   /// it is necessary. The default map type is \ref
   /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
+  /// \param TR Traits class to set various data types used
+  /// by the algorithm. The default traits class is
+  /// \ref MinCostArborescenceDefaultTraits
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref MinCostArborescenceDefaultTraits
   /// "MinCostArborescenceDefaultTraits<GR, CM>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
 #ifndef DOXYGEN
   template <typename GR,
 …
               MinCostArborescenceDefaultTraits<GR, CM> >
 #else
   template <typename GR, typename CM, typedef TR>
+  template <typename GR, typename CM, typename TR>
 #endif
   class MinCostArborescence {

lemon/network_simplex.h

-                      r812
+                      r840
     typedef std::vector<int> IntVector;
-    typedef std::vector<char> CharVector;
     typedef std::vector<Value> ValueVector;
     typedef std::vector<Cost> CostVector;
+    typedef std::vector<char> BoolVector;
+    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
     // State constants for arcs
 …
     IntVector _source;
     IntVector _target;
+    bool _arc_mixing;
     // Node and arc data
 …
     IntVector _last_succ;
     IntVector _dirty_revs;
     CharVector _forward;
     CharVector _state;
+    BoolVector _forward;
+    BoolVector _state;
     int _root;
 …
       const IntVector  &_target;
       const CostVector &_cost;
       const CharVector &_state;
+      const BoolVector &_state;
       const CostVector &_pi;
       int &_in_arc;
 …
       bool findEnteringArc() {
         Cost c;
         for (int e = _next_arc; e < _search_arc_num; ++e) {
+        for (int e = _next_arc; e != _search_arc_num; ++e) {
           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (c < 0) {
 …
+          }
+        }
         for (int e = 0; e < _next_arc; ++e) {
+        for (int e = 0; e != _next_arc; ++e) {
           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (c < 0) {
 …
       const IntVector  &_target;
       const CostVector &_cost;
       const CharVector &_state;
+      const BoolVector &_state;
       const CostVector &_pi;
       int &_in_arc;
 …
       bool findEnteringArc() {
         Cost c, min = 0;
         for (int e = 0; e < _search_arc_num; ++e) {
+        for (int e = 0; e != _search_arc_num; ++e) {
           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (c < min) {
 …
       const IntVector  &_target;
       const CostVector &_cost;
       const CharVector &_state;
+      const BoolVector &_state;
       const CostVector &_pi;
       int &_in_arc;
 …
+      {
         // The main parameters of the pivot rule
         const double BLOCK_SIZE_FACTOR = 0.5;
+        const double BLOCK_SIZE_FACTOR = 1.0;
         const int MIN_BLOCK_SIZE = 10;
 …
         int cnt = _block_size;
         int e;
         for (e = _next_arc; e < _search_arc_num; ++e) {
+        for (e = _next_arc; e != _search_arc_num; ++e) {
           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (c < min) {
 …
+          }
+        }
         for (e = 0; e < _next_arc; ++e) {
+        for (e = 0; e != _next_arc; ++e) {
           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (c < min) {
 …
       const IntVector  &_target;
       const CostVector &_cost;
       const CharVector &_state;
+      const BoolVector &_state;
       const CostVector &_pi;
       int &_in_arc;
 …
         min = 0;
         _curr_length = 0;
         for (e = _next_arc; e < _search_arc_num; ++e) {
+        for (e = _next_arc; e != _search_arc_num; ++e) {
           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (c < 0) {
 …
+          }
+        }
         for (e = 0; e < _next_arc; ++e) {
+        for (e = 0; e != _next_arc; ++e) {
           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (c < 0) {
 …
       const IntVector  &_target;
       const CostVector &_cost;
       const CharVector &_state;
+      const BoolVector &_state;
       const CostVector &_pi;
       int &_in_arc;
 …
         // Check the current candidate list
         int e;
         for (int i = 0; i < _curr_length; ++i) {
+        for (int i = 0; i != _curr_length; ++i) {
           e = _candidates[i];
           _cand_cost[e] = _state[e] *
 …
         int limit = _head_length;
         for (e = _next_arc; e < _search_arc_num; ++e) {
+        for (e = _next_arc; e != _search_arc_num; ++e) {
           _cand_cost[e] = _state[e] *
             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 …
+          }
+        }
         for (e = 0; e < _next_arc; ++e) {
+        for (e = 0; e != _next_arc; ++e) {
           _cand_cost[e] = _state[e] *
             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 …
     NetworkSimplex(const GR& graph, bool arc_mixing = false) :
       _graph(graph), _node_id(graph), _arc_id(graph),
+      _arc_mixing(arc_mixing),
       MAX(std::numeric_limits<Value>::max()),
       INF(std::numeric_limits<Value>::has_infinity ?
 …
         "The cost type of NetworkSimplex must be signed");
+      // Resize vectors
+      _node_num = countNodes(_graph);
+      _arc_num = countArcs(_graph);
+      int all_node_num = _node_num + 1;
+      int max_arc_num = _arc_num + 2 * _node_num;
+      _source.resize(max_arc_num);
+      _target.resize(max_arc_num);
+      _lower.resize(_arc_num);
+      _upper.resize(_arc_num);
+      _cap.resize(max_arc_num);
+      _cost.resize(max_arc_num);
+      _supply.resize(all_node_num);
+      _flow.resize(max_arc_num);
+      _pi.resize(all_node_num);
+      _parent.resize(all_node_num);
+      _pred.resize(all_node_num);
+      _forward.resize(all_node_num);
+      _thread.resize(all_node_num);
+      _rev_thread.resize(all_node_num);
+      _succ_num.resize(all_node_num);
+      _last_succ.resize(all_node_num);
+      _state.resize(max_arc_num);
+      // Copy the graph
+      int i = 0;
+      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
+        _node_id[n] = i;
+      }
+      if (arc_mixing) {
+        // Store the arcs in a mixed order
+        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
+        int i = 0, j = 0;
+        for (ArcIt a(_graph); a != INVALID; ++a) {
+          _arc_id[a] = i;
+          _source[i] = _node_id[_graph.source(a)];
+          _target[i] = _node_id[_graph.target(a)];
+          if ((i += k) >= _arc_num) i = ++j;
+        }
+      } else {
+        // Store the arcs in the original order
+        int i = 0;
+        for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
+          _arc_id[a] = i;
+          _source[i] = _node_id[_graph.source(a)];
+          _target[i] = _node_id[_graph.target(a)];
+        }
+      }
+      // Reset parameters
+      // Reset data structures
       reset();
+    }
 …
     /// \endcode
     ///
     /// This function can be called more than once. All the parameters
     /// that have been given are kept for the next call, unless
     /// \ref reset() is called, thus only the modified parameters
     /// have to be set again. See \ref reset() for examples.
     /// However, the underlying digraph must not be modified after this
     /// class have been constructed, since it copies and extends the graph.
+    /// This function can be called more than once. All the given parameters
+    /// are kept for the next call, unless \ref resetParams() or \ref reset()
+    /// is used, thus only the modified parameters have to be set again.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class (or the last \ref reset() call), then the \ref reset()
+    /// function must be called.
     ///
     /// \param pivot_rule The pivot rule that will be used during the
 …
     ///
     /// \see ProblemType, PivotRule
+    /// \see resetParams(), reset()
     ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
       if (!init()) return INFEASIBLE;
 …
     /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
     ///
+    /// It is useful for multiple run() calls. If this function is not
+    /// used, all the parameters given before are kept for the next
+    /// \ref run() call.
+    /// However, the underlying digraph must not be modified after this
+    /// class have been constructed, since it copies and extends the graph.
+    /// It is useful for multiple \ref run() calls. Basically, all the given
+    /// parameters are kept for the next \ref run() call, unless
+    /// \ref resetParams() or \ref reset() is used.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class or the last \ref reset() call, then the \ref reset()
+    /// function must be used, otherwise \ref resetParams() is sufficient.
     ///
     /// For example,
 …
     ///     .supplyMap(sup).run();
     ///
     ///   // Run again with modified cost map (reset() is not called,
+    ///   // Run again with modified cost map (resetParams() is not called,
     ///   // so only the cost map have to be set again)
     ///   cost[e] += 100;
     ///   ns.costMap(cost).run();
     ///
     ///   // Run again from scratch using reset()
+    ///   // Run again from scratch using resetParams()
     ///   // (the lower bounds will be set to zero on all arcs)
     ///   ns.reset();
+    ///   ns.resetParams();
     ///   ns.upperMap(capacity).costMap(cost)
     ///     .supplyMap(sup).run();
 …
     ///
     /// \return <tt>(*this)</tt>
+    NetworkSimplex& reset() {
+    ///
+    /// \see reset(), run()
+    NetworkSimplex& resetParams() {
       for (int i = 0; i != _node_num; ++i) {
         _supply[i] = 0;
 …
+    }
+    /// \brief Reset the internal data structures and all the parameters
+    /// that have been given before.
+    ///
+    /// This function resets the internal data structures and all the
+    /// paramaters that have been given before using functions \ref lowerMap(),
+    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
+    /// \ref supplyType().
+    ///
+    /// It is useful for multiple \ref run() calls. Basically, all the given
+    /// parameters are kept for the next \ref run() call, unless
+    /// \ref resetParams() or \ref reset() is used.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class or the last \ref reset() call, then the \ref reset()
+    /// function must be used, otherwise \ref resetParams() is sufficient.
+    ///
+    /// See \ref resetParams() for examples.
+    ///
+    /// \return <tt>(*this)</tt>
+    ///
+    /// \see resetParams(), run()
+    NetworkSimplex& reset() {
+      // Resize vectors
+      _node_num = countNodes(_graph);
+      _arc_num = countArcs(_graph);
+      int all_node_num = _node_num + 1;
+      int max_arc_num = _arc_num + 2 * _node_num;
+      _source.resize(max_arc_num);
+      _target.resize(max_arc_num);
+      _lower.resize(_arc_num);
+      _upper.resize(_arc_num);
+      _cap.resize(max_arc_num);
+      _cost.resize(max_arc_num);
+      _supply.resize(all_node_num);
+      _flow.resize(max_arc_num);
+      _pi.resize(all_node_num);
+      _parent.resize(all_node_num);
+      _pred.resize(all_node_num);
+      _forward.resize(all_node_num);
+      _thread.resize(all_node_num);
+      _rev_thread.resize(all_node_num);
+      _succ_num.resize(all_node_num);
+      _last_succ.resize(all_node_num);
+      _state.resize(max_arc_num);
+      // Copy the graph
+      int i = 0;
+      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
+        _node_id[n] = i;
+      }
+      if (_arc_mixing) {
+        // Store the arcs in a mixed order
+        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
+        int i = 0, j = 0;
+        for (ArcIt a(_graph); a != INVALID; ++a) {
+          _arc_id[a] = i;
+          _source[i] = _node_id[_graph.source(a)];
+          _target[i] = _node_id[_graph.target(a)];
+          if ((i += k) >= _arc_num) i = ++j;
+        }
+      } else {
+        // Store the arcs in the original order
+        int i = 0;
+        for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
+          _arc_id[a] = i;
+          _source[i] = _node_id[_graph.source(a)];
+          _target[i] = _node_id[_graph.target(a)];
+        }
+      }
+      // Reset parameters
+      resetParams();
+      return *this;
+    }
     /// @}
 …
       // Update _rev_thread using the new _thread values
       for (int i = 0; i < int(_dirty_revs.size()); ++i) {
+      for (int i = 0; i != int(_dirty_revs.size()); ++i) {
         u = _dirty_revs[i];
         _rev_thread[_thread[u]] = u;
 …
         _pi[u] += sigma;
+      }
+    }
+    // Heuristic initial pivots
+    bool initialPivots() {
+      Value curr, total = 0;
+      std::vector<Node> supply_nodes, demand_nodes;
+      for (NodeIt u(_graph); u != INVALID; ++u) {
+        curr = _supply[_node_id[u]];
+        if (curr > 0) {
+          total += curr;
+          supply_nodes.push_back(u);
+        }
+        else if (curr < 0) {
+          demand_nodes.push_back(u);
+        }
+      }
+      if (_sum_supply > 0) total -= _sum_supply;
+      if (total <= 0) return true;
+      IntVector arc_vector;
+      if (_sum_supply >= 0) {
+        if (supply_nodes.size() == 1 && demand_nodes.size() == 1) {
+          // Perform a reverse graph search from the sink to the source
+          typename GR::template NodeMap<bool> reached(_graph, false);
+          Node s = supply_nodes[0], t = demand_nodes[0];
+          std::vector<Node> stack;
+          reached[t] = true;
+          stack.push_back(t);
+          while (!stack.empty()) {
+            Node u, v = stack.back();
+            stack.pop_back();
+            if (v == s) break;
+            for (InArcIt a(_graph, v); a != INVALID; ++a) {
+              if (reached[u = _graph.source(a)]) continue;
+              int j = _arc_id[a];
+              if (_cap[j] >= total) {
+                arc_vector.push_back(j);
+                reached[u] = true;
+                stack.push_back(u);
+              }
+            }
+          }
+        } else {
+          // Find the min. cost incomming arc for each demand node
+          for (int i = 0; i != int(demand_nodes.size()); ++i) {
+            Node v = demand_nodes[i];
+            Cost c, min_cost = std::numeric_limits<Cost>::max();
+            Arc min_arc = INVALID;
+            for (InArcIt a(_graph, v); a != INVALID; ++a) {
+              c = _cost[_arc_id[a]];
+              if (c < min_cost) {
+                min_cost = c;
+                min_arc = a;
+              }
+            }
+            if (min_arc != INVALID) {
+              arc_vector.push_back(_arc_id[min_arc]);
+            }
+          }
+        }
+      } else {
+        // Find the min. cost outgoing arc for each supply node
+        for (int i = 0; i != int(supply_nodes.size()); ++i) {
+          Node u = supply_nodes[i];
+          Cost c, min_cost = std::numeric_limits<Cost>::max();
+          Arc min_arc = INVALID;
+          for (OutArcIt a(_graph, u); a != INVALID; ++a) {
+            c = _cost[_arc_id[a]];
+            if (c < min_cost) {
+              min_cost = c;
+              min_arc = a;
+            }
+          }
+          if (min_arc != INVALID) {
+            arc_vector.push_back(_arc_id[min_arc]);
+          }
+        }
+      }
+      // Perform heuristic initial pivots
+      for (int i = 0; i != int(arc_vector.size()); ++i) {
+        in_arc = arc_vector[i];
+        if (_state[in_arc] * (_cost[in_arc] + _pi[_source[in_arc]] -
+            _pi[_target[in_arc]]) >= 0) continue;
+        findJoinNode();
+        bool change = findLeavingArc();
+        if (delta >= MAX) return false;
+        changeFlow(change);
+        if (change) {
+          updateTreeStructure();
+          updatePotential();
+        }
+      }
+      return true;
+    }
 …
       PivotRuleImpl pivot(*this);
+      // Perform heuristic initial pivots
+      if (!initialPivots()) return UNBOUNDED;
       // Execute the Network Simplex algorithm
       while (pivot.findEnteringArc()) {

lemon/planarity.h

-                      r798
+                      r828
   ///
   /// This function implements the Boyer-Myrvold algorithm for
   /// planarity checking of an undirected graph. It is a simplified
+  /// planarity checking of an undirected simple graph. It is a simplified
   /// version of the PlanarEmbedding algorithm class because neither
   /// the embedding nor the kuratowski subdivisons are not computed.
+  /// the embedding nor the Kuratowski subdivisons are computed.
   template <typename GR>
   bool checkPlanarity(const GR& graph) {
 …
   ///
   /// This class implements the Boyer-Myrvold algorithm for planar
   /// embedding of an undirected graph. The planar embedding is an
+  /// embedding of an undirected simple graph. The planar embedding is an
   /// ordering of the outgoing edges of the nodes, which is a possible
   /// configuration to draw the graph in the plane. If there is not
   /// such ordering then the graph contains a \f$ K_5 \f$ (full graph
   /// with 5 nodes) or a \f$ K_{3,3} \f$ (complete bipartite graph on
   /// 3 ANode and 3 BNode) subdivision.
+  /// such ordering then the graph contains a K<sub>5</sub> (full graph
+  /// with 5 nodes) or a K<sub>3,3</sub> (complete bipartite graph on
+  /// 3 Red and 3 Blue nodes) subdivision.
   ///
   /// The current implementation calculates either an embedding or a
+  /// Kuratowski subdivision. The running time of the algorithm is
+  /// \f$ O(n) \f$.
+  /// Kuratowski subdivision. The running time of the algorithm is O(n).
+  ///
+  /// \see PlanarDrawing, checkPlanarity()
   template <typename Graph>
   class PlanarEmbedding {
 …
   public:
+    /// \brief The map for store of embedding
+    /// \brief The map type for storing the embedding
+    ///
+    /// The map type for storing the embedding.
+    /// \see embeddingMap()
     typedef typename Graph::template ArcMap<Arc> EmbeddingMap;
     /// \brief Constructor
     ///
+    /// \note The graph should be simple, i.e. parallel and loop arc
+    /// free.
+    /// Constructor.
+    /// \pre The graph must be simple, i.e. it should not
+    /// contain parallel or loop arcs.
     PlanarEmbedding(const Graph& graph)
       : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}
     /// \brief Runs the algorithm.
+    /// \brief Run the algorithm.
     ///
     /// Runs the algorithm.
     /// \param kuratowski If the parameter is false, then the
+    /// This function runs the algorithm.
+    /// \param kuratowski If this parameter is set to \c false, then the
     /// algorithm does not compute a Kuratowski subdivision.
     ///\return %True when the graph is planar.
+    /// \return \c true if the graph is planar.
     bool run(bool kuratowski = true) {
       typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
 …
+    }
     /// \brief Gives back the successor of an arc
+    /// \brief Give back the successor of an arc
     ///
     /// Gives back the successor of an arc. This function makes
+    /// This function gives back the successor of an arc. It makes
     /// possible to query the cyclic order of the outgoing arcs from
     /// a node.
 …
+    }
     /// \brief Gives back the calculated embedding map
+    /// \brief Give back the calculated embedding map
     ///
+    /// The returned map contains the successor of each arc in the
+    /// graph.
+    /// This function gives back the calculated embedding map, which
+    /// contains the successor of each arc in the cyclic order of the
+    /// outgoing arcs of its source node.
     const EmbeddingMap& embeddingMap() const {
       return _embedding;
+    }
     /// \brief Gives back true if the undirected arc is in the
     /// kuratowski subdivision
+    /// \brief Give back \c true if the given edge is in the Kuratowski
+    /// subdivision
     ///
+    /// Gives back true if the undirected arc is in the kuratowski
+    /// subdivision
+    /// \note The \c run() had to be called with true value.
+    bool kuratowski(const Edge& edge) {
+    /// This function gives back \c true if the given edge is in the found
+    /// Kuratowski subdivision.
+    /// \pre The \c run() function must be called with \c true parameter
+    /// before using this function.
+    bool kuratowski(const Edge& edge) const {
       return _kuratowski[edge];
+    }
 …
   ///
   /// The planar drawing algorithm calculates positions for the nodes
   /// in the plane which coordinates satisfy that if the arcs are
   /// represented with straight lines then they will not intersect
+  /// in the plane. These coordinates satisfy that if the edges are
+  /// represented with straight lines, then they will not intersect
   /// each other.
   ///
   /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid,
   /// i.e. each node will be located in the \c [0,n-2]x[0,n-2] square.
+  /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid,
+  /// i.e. each node will be located in the \c [0..n-2]x[0..n-2] square.
   /// The time complexity of the algorithm is O(n).
+  ///
+  /// \see PlanarEmbedding
   template <typename Graph>
   class PlanarDrawing {
 …
     TEMPLATE_GRAPH_TYPEDEFS(Graph);
     /// \brief The point type for store coordinates
+    /// \brief The point type for storing coordinates
     typedef dim2::Point<int> Point;
     /// \brief The map type for store coordinates
+    /// \brief The map type for storing the coordinates of the nodes
     typedef typename Graph::template NodeMap<Point> PointMap;
 …
     ///
     /// Constructor
+    /// \pre The graph should be simple, i.e. loop and parallel arc free.
+    /// \pre The graph must be simple, i.e. it should not
+    /// contain parallel or loop arcs.
     PlanarDrawing(const Graph& graph)
       : _graph(graph), _point_map(graph) {}
 …
   public:
     /// \brief Calculates the node positions
+    /// \brief Calculate the node positions
     ///
     /// This function calculates the node positions.
     /// \return %True if the graph is planar.
+    /// This function calculates the node positions on the plane.
+    /// \return \c true if the graph is planar.
     bool run() {
       PlanarEmbedding<Graph> pe(_graph);
 …
+    }
     /// \brief Calculates the node positions according to a
+    /// \brief Calculate the node positions according to a
     /// combinatorical embedding
     ///
+    /// This function calculates the node locations. The \c embedding
+    /// parameter should contain a valid combinatorical embedding, i.e.
+    /// a valid cyclic order of the arcs.
+    /// This function calculates the node positions on the plane.
+    /// The given \c embedding map should contain a valid combinatorical
+    /// embedding, i.e. a valid cyclic order of the arcs.
+    /// It can be computed using PlanarEmbedding.
     template <typename EmbeddingMap>
     void run(const EmbeddingMap& embedding) {
 …
     /// \brief The coordinate of the given node
     ///
     /// The coordinate of the given node.
+    /// This function returns the coordinate of the given node.
     Point operator[](const Node& node) const {
       return _point_map[node];
+    }
     /// \brief Returns the grid embedding in a \e NodeMap.
+    /// \brief Return the grid embedding in a node map
     ///
+    /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> .
+    /// This function returns the grid embedding in a node map of
+    /// \c dim2::Point<int> coordinates.
     const PointMap& coords() const {
       return _point_map;
 …
   ///
   /// The graph coloring problem is the coloring of the graph nodes
   /// that there are not adjacent nodes with the same color. The
   /// planar graphs can be always colored with four colors, it is
   /// proved by Appel and Haken and their proofs provide a quadratic
+  /// so that there are no adjacent nodes with the same color. The
+  /// planar graphs can always be colored with four colors, which is
+  /// proved by Appel and Haken. Their proofs provide a quadratic
   /// time algorithm for four coloring, but it could not be used to
   /// implement efficient algorithm. The five and six coloring can be
   /// made in linear time, but in this class the five coloring has
+  /// implement an efficient algorithm. The five and six coloring can be
+  /// made in linear time, but in this class, the five coloring has
   /// quadratic worst case time complexity. The two coloring (if
   /// possible) is solvable with a graph search algorithm and it is
   /// implemented in \ref bipartitePartitions() function in LEMON. To
+  /// decide whether the planar graph is three colorable is
+  /// NP-complete.
+  /// decide whether a planar graph is three colorable is NP-complete.
   ///
   /// This class contains member functions for calculate colorings
   /// with five and six colors. The six coloring algorithm is a simple
   /// greedy coloring on the backward minimum outgoing order of nodes.
   /// This order can be computed as in each phase the node with least
   /// outgoing arcs to unprocessed nodes is chosen. This order
+  /// This order can be computed by selecting the node with least
+  /// outgoing arcs to unprocessed nodes in each phase. This order
   /// guarantees that when a node is chosen for coloring it has at
   /// most five already colored adjacents. The five coloring algorithm
 …
     TEMPLATE_GRAPH_TYPEDEFS(Graph);
     /// \brief The map type for store color indexes
+    /// \brief The map type for storing color indices
     typedef typename Graph::template NodeMap<int> IndexMap;
+    /// \brief The map type for store colors
+    /// \brief The map type for storing colors
+    ///
+    /// The map type for storing colors.
+    /// \see Palette, Color
     typedef ComposeMap<Palette, IndexMap> ColorMap;
     /// \brief Constructor
     ///
+    /// Constructor
+    /// \pre The graph should be simple, i.e. loop and parallel arc free.
+    /// Constructor.
+    /// \pre The graph must be simple, i.e. it should not
+    /// contain parallel or loop arcs.
     PlanarColoring(const Graph& graph)
       : _graph(graph), _color_map(graph), _palette(0) {
 …
+    }
     /// \brief Returns the \e NodeMap of color indexes
+    /// \brief Return the node map of color indices
     ///
     /// Returns the \e NodeMap of color indexes. The values are in the
     /// range \c [0..4] or \c [0..5] according to the coloring method.
+    /// This function returns the node map of color indices. The values are
+    /// in the range \c [0..4] or \c [0..5] according to the coloring method.
     IndexMap colorIndexMap() const {
       return _color_map;
+    }
     /// \brief Returns the \e NodeMap of colors
+    /// \brief Return the node map of colors
     ///
     /// Returns the \e NodeMap of colors. The values are five or six
     /// distinct \ref lemon::Color "colors".
+    /// This function returns the node map of colors. The values are among
+    /// five or six distinct \ref lemon::Color "colors".
     ColorMap colorMap() const {
       return composeMap(_palette, _color_map);
+    }
     /// \brief Returns the color index of the node
+    /// \brief Return the color index of the node
     ///
     /// Returns the color index of the node. The values are in the
     /// range \c [0..4] or \c [0..5] according to the coloring method.
+    /// This function returns the color index of the given node. The value is
+    /// in the range \c [0..4] or \c [0..5] according to the coloring method.
     int colorIndex(const Node& node) const {
       return _color_map[node];
+    }
     /// \brief Returns the color of the node
+    /// \brief Return the color of the node
     ///
     /// Returns the color of the node. The values are five or six
     /// distinct \ref lemon::Color "colors".
+    /// This function returns the color of the given node. The value is among
+    /// five or six distinct \ref lemon::Color "colors".
     Color color(const Node& node) const {
       return _palette[_color_map[node]];
 …
     /// \brief Calculates a coloring with at most six colors
+    /// \brief Calculate a coloring with at most six colors
     ///
     /// This function calculates a coloring with at most six colors. The time
     /// complexity of this variant is linear in the size of the graph.
     /// \return %True when the algorithm could color the graph with six color.
     /// If the algorithm fails, then the graph could not be planar.
     /// \note This function can return true if the graph is not
     /// planar but it can be colored with 6 colors.
+    /// \return \c true if the algorithm could color the graph with six colors.
+    /// If the algorithm fails, then the graph is not planar.
+    /// \note This function can return \c true if the graph is not
+    /// planar, but it can be colored with at most six colors.
     bool runSixColoring() {
 …
   public:
     /// \brief Calculates a coloring with at most five colors
+    /// \brief Calculate a coloring with at most five colors
     ///
     /// This function calculates a coloring with at most five
     /// colors. The worst case time complexity of this variant is
     /// quadratic in the size of the graph.
+    /// \param embedding This map should contain a valid combinatorical
+    /// embedding, i.e. a valid cyclic order of the arcs.
+    /// It can be computed using PlanarEmbedding.
     template <typename EmbeddingMap>
     void runFiveColoring(const EmbeddingMap& embedding) {
 …
+    }
     /// \brief Calculates a coloring with at most five colors
+    /// \brief Calculate a coloring with at most five colors
     ///
     /// This function calculates a coloring with at most five
     /// colors. The worst case time complexity of this variant is
     /// quadratic in the size of the graph.
     /// \return %True when the graph is planar.
+    /// \return \c true if the graph is planar.
     bool runFiveColoring() {
       PlanarEmbedding<Graph> pe(_graph);

lemon/preflow.h

-                      r788
+                      r825
   /// second phase constructs a feasible maximum flow on each arc.
   ///
+  /// \warning This implementation cannot handle infinite or very large
+  /// capacities (e.g. the maximum value of \c CAP::Value).
+  ///
   /// \tparam GR The type of the digraph the algorithm runs on.
   /// \tparam CAP The type of the capacity map. The default map
   /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref PreflowDefaultTraits
+  /// "PreflowDefaultTraits<GR, CAP>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR, typename CAP, typename TR>

scripts/bib2dox.py

-                      r754
+                      r836
 #!/usr/bin/env /usr/local/Python/bin/python2.1
+#! /usr/bin/env python
 """
   BibTeX to Doxygen converter
   Usage: python bib2dox.py bibfile.bib > bibfile.dox
+  This file is a part of LEMON, a generic C++ optimization library.
+  **********************************************************************
   This code is the modification of the BibTeX to XML converter
+  by Vidar Bronken Gundersen et al. See the original copyright notices below.
+  by Vidar Bronken Gundersen et al.
+  See the original copyright notices below.
   **********************************************************************

test/bellman_ford_test.cc

r791	r844
105	105	::SetDistMap<concepts::ReadWriteMap<Node,Value> >
106	106	::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
	107	::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> >
107	108	::Create bf_test(gr,length);
108	109

test/min_cost_flow_test.cc

-                      r819
+                      r830
       const MCF& const_mcf = mcf;
       b = mcf.reset()
+      b = mcf.reset().resetParams()
              .lowerMap(me.lower)
              .upperMap(me.upper)
 …
   checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2,
            mcf1.OPTIMAL, true,     8010, test_str + "-4");
   mcf1.reset().supplyMap(s1);
+  mcf1.resetParams().supplyMap(s1);
   checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1,
            mcf1.OPTIMAL, true,       74, test_str + "-5");
 …
   // Tests for the GEQ form
   mcf1.reset().upperMap(u).costMap(c).supplyMap(s5);
+  mcf1.resetParams().upperMap(u).costMap(c).supplyMap(s5);
   checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5,
            mcf1.OPTIMAL, true,     3530, test_str + "-10", GEQ);
 …
   checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s,
            mcf2.OPTIMAL, true,   -40000, test_str + "-14");
   mcf2.reset().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
+  mcf2.resetParams().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
   checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s,
            mcf2.UNBOUNDED, false,     0, test_str + "-15");

tools/dimacs-solver.cc

-                      r644
+                      r846
+}
 template<class Value>
+template<class Value, class LargeValue>
 void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
                Value infty, DimacsDescriptor &desc)
 …
     std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
     std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n';
+    if (res) std::cerr << "Min flow cost: " << ns.totalCost() << '\n';
+    if (res) std::cerr << "Min flow cost: "
+                       << ns.template totalCost<LargeValue>() << '\n';
+  }
+}
 …
 template<class Value>
+template<class Value, class LargeValue>
 void solve(ArgParser &ap, std::istream &is, std::ostream &os,
            DimacsDescriptor &desc)
 …
+    {
     case DimacsDescriptor::MIN:
       solve_min<Value>(ap,is,os,infty,desc);
+      solve_min<Value, LargeValue>(ap,is,os,infty,desc);
       break;
     case DimacsDescriptor::MAX:
 …
   if(ap.given("double"))
     solve<double>(ap,is,os,desc);
+    solve<double, double>(ap,is,os,desc);
   else if(ap.given("ldouble"))
     solve<long double>(ap,is,os,desc);
+    solve<long double, long double>(ap,is,os,desc);
 #ifdef LEMON_HAVE_LONG_LONG
   else if(ap.given("long"))
+    solve<long long>(ap,is,os,desc);
+    solve<long long, long long>(ap,is,os,desc);
+  else solve<int, long long>(ap,is,os,desc);
+#else
+  else solve<int, long>(ap,is,os,desc);
 #endif
-  else solve<int>(ap,is,os,desc);
   return 0;

Context Navigation

Changes in / [848:e05b2b48515a:849:1b8db382910c] in lemon-main

Legend:

INSTALL

demo/arg_parser_demo.cc

doc/CMakeLists.txt

doc/Makefile.am

lemon/arg_parser.cc

lemon/arg_parser.h

lemon/bellman_ford.h

lemon/bfs.h

lemon/capacity_scaling.h

lemon/circulation.h

lemon/cost_scaling.h

lemon/cycle_canceling.h

lemon/dfs.h

lemon/dijkstra.h

lemon/glpk.h

lemon/graph_to_eps.h

lemon/hartmann_orlin.h

lemon/howard.h

lemon/karp.h

lemon/lp_base.h

lemon/min_cost_arborescence.h

lemon/network_simplex.h

lemon/planarity.h

lemon/preflow.h

scripts/bib2dox.py

test/bellman_ford_test.cc

test/min_cost_flow_test.cc

tools/dimacs-solver.cc

Download in other formats: