Changes in / [903:207ba6c0f2e4:904:b9b2e8abe70b] in lemon

Files:

• INSTALL (modified) (1 diff)
• doc/CMakeLists.txt (modified) (1 diff)
• doc/Makefile.am (modified) (1 diff)
• doc/groups.dox (modified) (1 diff)
• doc/images/planar.eps (added)
• lemon/Makefile.am (modified) (2 diffs)
• lemon/bellman_ford.h (modified) (4 diffs)
• lemon/bfs.h (modified) (3 diffs)
• lemon/bits/map_extender.h (modified) (6 diffs)
• lemon/capacity_scaling.h (added)
• lemon/circulation.h (modified) (1 diff)
• lemon/concepts/heap.h (modified) (12 diffs)
• lemon/cost_scaling.h (added)
• lemon/cycle_canceling.h (added)
• lemon/dfs.h (modified) (3 diffs)
• lemon/dijkstra.h (modified) (2 diffs)
• lemon/glpk.h (modified) (3 diffs)
• lemon/hartmann_orlin.h (modified) (2 diffs)
• lemon/howard.h (modified) (2 diffs)
• lemon/karp.h (modified) (2 diffs)
• lemon/min_cost_arborescence.h (modified) (2 diffs)
• lemon/network_simplex.h (modified) (25 diffs)
• lemon/planarity.h (modified) (17 diffs)
• lemon/preflow.h (modified) (1 diff)
• lemon/unionfind.h (modified) (1 diff)
• test/min_cost_flow_test.cc (modified) (7 diffs)

INSTALL

@@ -174 +174 @@
 
    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"'.

doc/CMakeLists.txt

@@ -27 +27 @@
     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     COMMAND ${CMAKE_COMMAND} -E remove_directory html

doc/Makefile.am

@@ -29 +29 @@
         edge_biconnected_components.eps \
         node_biconnected_components.eps \
+        planar.eps \
         strongly_connected_components.eps
 

doc/groups.dox

@@ -407 +407 @@
  - \ref NetworkSimplex Primal Network Simplex algorithm with various
    pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
- - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
-   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
+ - \ref CostScaling Cost Scaling algorithm based on push/augment and
+   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
    \ref bunnagel98efficient.
- - \ref CapacityScaling Successive Shortest %Path algorithm with optional
-   capacity scaling \ref edmondskarp72theoretical.
- - \ref CancelAndTighten The Cancel and Tighten algorithm
-   \ref goldberg89cyclecanceling.
- - \ref CycleCanceling Cycle-Canceling algorithms
-   \ref klein67primal, \ref goldberg89cyclecanceling.
+ - \ref CapacityScaling Capacity Scaling algorithm based on the successive
+   shortest path method \ref edmondskarp72theoretical.
+ - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
+   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
 
 In general NetworkSimplex is the most efficient implementation,

lemon/Makefile.am

@@ -63 +63 @@
         lemon/binom_heap.h \
         lemon/bucket_heap.h \
+        lemon/capacity_scaling.h \
         lemon/cbc.h \
         lemon/circulation.h \
@@ -69 +70 @@
         lemon/concept_check.h \
         lemon/connectivity.h \
+        lemon/core.h \
+        lemon/cost_scaling.h \
         lemon/counter.h \
-        lemon/core.h \
         lemon/cplex.h \
+        lemon/cycle_canceling.h \
         lemon/dfs.h \
         lemon/dijkstra.h \

lemon/bellman_ford.h

@@ -172 +172 @@
   /// 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>
@@ -238 +243 @@
         _dist = Traits::createDistMap(*_gr);
       }
-      _mask = new MaskMap(*_gr, false);
+      if(!_mask) {
+        _mask = new MaskMap(*_gr);
+      }
     }
     
@@ -404 +411 @@
           _process.push_back(it);
           _mask->set(it, true);
+        }
+      } else {
+        for (NodeIt it(*_gr); it != INVALID; ++it) {
+          _mask->set(it, false);
         }
       }
@@ -928 +939 @@
   /// 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

@@ -122 +122 @@
   ///\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,
@@ -958 +963 @@
   /// 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
@@ -1296 +1304 @@
   /// 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/bits/map_extender.h

@@ -85 +85 @@
       typedef typename Map::Value Value;
 
-      MapIt() {}
-
-      MapIt(Invalid i) : Parent(i) { }
-
-      explicit MapIt(Map& _map) : map(_map) {
-        map.notifier()->first(*this);
+      MapIt() : map(NULL) {}
+
+      MapIt(Invalid i) : Parent(i), map(NULL) {}
+
+      explicit MapIt(Map& _map) : map(&_map) {
+        map->notifier()->first(*this);
       }
 
       MapIt(const Map& _map, const Item& item)
+        : Parent(item), map(&_map) {}
+
+      MapIt& operator++() {
+        map->notifier()->next(*this);
+        return *this;
+      }
+
+      typename MapTraits<Map>::ConstReturnValue operator*() const {
+        return (*map)[*this];
+      }
+
+      typename MapTraits<Map>::ReturnValue operator*() {
+        return (*map)[*this];
+      }
+
+      void set(const Value& value) {
+        map->set(*this, value);
+      }
+
+    protected:
+      Map* map;
+
+    };
+
+    class ConstMapIt : public Item {
+      typedef Item Parent;
+
+    public:
+
+      typedef typename Map::Value Value;
+
+      ConstMapIt() : map(NULL) {}
+
+      ConstMapIt(Invalid i) : Parent(i), map(NULL) {}
+
+      explicit ConstMapIt(Map& _map) : map(&_map) {
+        map->notifier()->first(*this);
+      }
+
+      ConstMapIt(const Map& _map, const Item& item)
         : Parent(item), map(_map) {}
 
-      MapIt& operator++() {
-        map.notifier()->next(*this);
+      ConstMapIt& operator++() {
+        map->notifier()->next(*this);
         return *this;
       }
@@ -105 +145 @@
       }
 
-      typename MapTraits<Map>::ReturnValue operator*() {
-        return map[*this];
-      }
-
-      void set(const Value& value) {
-        map.set(*this, value);
-      }
-
-    protected:
-      Map& map;
-
-    };
-
-    class ConstMapIt : public Item {
-      typedef Item Parent;
-
-    public:
-
-      typedef typename Map::Value Value;
-
-      ConstMapIt() {}
-
-      ConstMapIt(Invalid i) : Parent(i) { }
-
-      explicit ConstMapIt(Map& _map) : map(_map) {
-        map.notifier()->first(*this);
-      }
-
-      ConstMapIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
-
-      ConstMapIt& operator++() {
-        map.notifier()->next(*this);
-        return *this;
-      }
-
-      typename MapTraits<Map>::ConstReturnValue operator*() const {
-        return map[*this];
-      }
-
-    protected:
-      const Map& map;
+    protected:
+      const Map* map;
     };
 
@@ -153 +153 @@
 
     public:
-
-      ItemIt() {}
-
-      ItemIt(Invalid i) : Parent(i) { }
-
-      explicit ItemIt(Map& _map) : map(_map) {
-        map.notifier()->first(*this);
+      ItemIt() : map(NULL) {}
+
+
+      ItemIt(Invalid i) : Parent(i), map(NULL) {}
+
+      explicit ItemIt(Map& _map) : map(&_map) {
+        map->notifier()->first(*this);
       }
 
       ItemIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
+        : Parent(item), map(&_map) {}
 
       ItemIt& operator++() {
-        map.notifier()->next(*this);
-        return *this;
-      }
-
-    protected:
-      const Map& map;
+        map->notifier()->next(*this);
+        return *this;
+      }
+
+    protected:
+      const Map* map;
 
     };
@@ -232 +232 @@
       typedef typename Map::Value Value;
 
-      MapIt() {}
-
-      MapIt(Invalid i) : Parent(i) { }
-
-      explicit MapIt(Map& _map) : map(_map) {
-        map.graph.first(*this);
+      MapIt() : map(NULL) {}
+
+      MapIt(Invalid i) : Parent(i), map(NULL) { }
+
+      explicit MapIt(Map& _map) : map(&_map) {
+        map->graph.first(*this);
       }
 
       MapIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
+        : Parent(item), map(&_map) {}
 
       MapIt& operator++() {
-        map.graph.next(*this);
+        map->graph.next(*this);
         return *this;
       }
 
       typename MapTraits<Map>::ConstReturnValue operator*() const {
-        return map[*this];
+        return (*map)[*this];
       }
 
       typename MapTraits<Map>::ReturnValue operator*() {
-        return map[*this];
+        return (*map)[*this];
       }
 
       void set(const Value& value) {
-        map.set(*this, value);
-      }
-
-    protected:
-      Map& map;
+        map->set(*this, value);
+      }
+
+    protected:
+      Map* map;
 
     };
@@ -272 +272 @@
       typedef typename Map::Value Value;
 
-      ConstMapIt() {}
-
-      ConstMapIt(Invalid i) : Parent(i) { }
-
-      explicit ConstMapIt(Map& _map) : map(_map) {
-        map.graph.first(*this);
+      ConstMapIt() : map(NULL) {}
+
+      ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
+
+      explicit ConstMapIt(Map& _map) : map(&_map) {
+        map->graph.first(*this);
       }
 
       ConstMapIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
+        : Parent(item), map(&_map) {}
 
       ConstMapIt& operator++() {
-        map.graph.next(*this);
+        map->graph.next(*this);
         return *this;
       }
 
       typename MapTraits<Map>::ConstReturnValue operator*() const {
-        return map[*this];
-      }
-
-    protected:
-      const Map& map;
+        return (*map)[*this];
+      }
+
+    protected:
+      const Map* map;
     };
 
@@ -300 +300 @@
 
     public:
-
-      ItemIt() {}
-
-      ItemIt(Invalid i) : Parent(i) { }
-
-      explicit ItemIt(Map& _map) : map(_map) {
-        map.graph.first(*this);
+      ItemIt() : map(NULL) {}
+
+
+      ItemIt(Invalid i) : Parent(i), map(NULL) { }
+
+      explicit ItemIt(Map& _map) : map(&_map) {
+        map->graph.first(*this);
       }
 
       ItemIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
+        : Parent(item), map(&_map) {}
 
       ItemIt& operator++() {
-        map.graph.next(*this);
-        return *this;
-      }
-
-    protected:
-      const Map& map;
+        map->graph.next(*this);
+        return *this;
+      }
+
+    protected:
+      const Map* map;
 
     };

lemon/circulation.h

@@ -174 +174 @@
      \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/concepts/heap.h

@@ -89 +89 @@
       /// handle the cross references. The assigned value must be
       /// \c PRE_HEAP (<tt>-1</tt>) for each item.
+#ifdef DOXYGEN
       explicit Heap(ItemIntMap &map) {}
+#else
+      explicit Heap(ItemIntMap&) {}
+#endif      
 
       /// \brief Constructor.
@@ -99 +103 @@
       /// \c PRE_HEAP (<tt>-1</tt>) for each item.
       /// \param comp The function object used for comparing the priorities.
+#ifdef DOXYGEN
       explicit Heap(ItemIntMap &map, const CMP &comp) {}
+#else
+      explicit Heap(ItemIntMap&, const CMP&) {}
+#endif      
 
       /// \brief The number of items stored in the heap.
@@ -127 +135 @@
       /// \param p The priority of the item.
       /// \pre \e i must not be stored in the heap.
+#ifdef DOXYGEN
       void push(const Item &i, const Prio &p) {}
+#else
+      void push(const Item&, const Prio&) {}
+#endif      
 
       /// \brief Return the item having minimum priority.
@@ -133 +145 @@
       /// This function returns the item having minimum priority.
       /// \pre The heap must be non-empty.
-      Item top() const {}
+      Item top() const { return Item(); }
 
       /// \brief The minimum priority.
@@ -139 +151 @@
       /// This function returns the minimum priority.
       /// \pre The heap must be non-empty.
-      Prio prio() const {}
+      Prio prio() const { return Prio(); }
 
       /// \brief Remove the item having minimum priority.
@@ -153 +165 @@
       /// \param i The item to delete.
       /// \pre \e i must be in the heap.
+#ifdef DOXYGEN
       void erase(const Item &i) {}
+#else
+      void erase(const Item&) {}
+#endif      
 
       /// \brief The priority of the given item.
@@ -160 +176 @@
       /// \param i The item.
       /// \pre \e i must be in the heap.
+#ifdef DOXYGEN
       Prio operator[](const Item &i) const {}
+#else
+      Prio operator[](const Item&) const { return Prio(); }
+#endif      
 
       /// \brief Set the priority of an item or insert it, if it is
@@ -171 +191 @@
       /// \param i The item.
       /// \param p The priority.
+#ifdef DOXYGEN
       void set(const Item &i, const Prio &p) {}
+#else
+      void set(const Item&, const Prio&) {}
+#endif      
 
       /// \brief Decrease the priority of an item to the given value.
@@ -179 +203 @@
       /// \param p The priority.
       /// \pre \e i must be stored in the heap with priority at least \e p.
+#ifdef DOXYGEN
       void decrease(const Item &i, const Prio &p) {}
+#else
+      void decrease(const Item&, const Prio&) {}
+#endif      
 
       /// \brief Increase the priority of an item to the given value.
@@ -187 +215 @@
       /// \param p The priority.
       /// \pre \e i must be stored in the heap with priority at most \e p.
+#ifdef DOXYGEN
       void increase(const Item &i, const Prio &p) {}
+#else
+      void increase(const Item&, const Prio&) {}
+#endif      
 
       /// \brief Return the state of an item.
@@ -197 +229 @@
       /// to the heap again.
       /// \param i The item.
+#ifdef DOXYGEN
       State state(const Item &i) const {}
+#else
+      State state(const Item&) const { return PRE_HEAP; }
+#endif      
 
       /// \brief Set the state of an item in the heap.
@@ -206 +242 @@
       /// \param i The item.
       /// \param st The state. It should not be \c IN_HEAP.
+#ifdef DOXYGEN
       void state(const Item& i, State st) {}
+#else
+      void state(const Item&, State) {}
+#endif      
 
 

lemon/dfs.h

@@ -122 +122 @@
   ///\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,
@@ -888 +893 @@
   /// 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
@@ -1238 +1246 @@
   /// 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

@@ -193 +193 @@
   ///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>
@@ -1093 +1098 @@
   /// 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

@@ -26 +26 @@
 #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
@@ -44 +56 @@
   protected:
 
-    typedef glp_prob LPX;
-    glp_prob* lp;
+    _solver_bits::VoidPtr lp;
 
     GlpkBase();
@@ -124 +135 @@
 
     ///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/hartmann_orlin.h

@@ -107 +107 @@
   /// \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>
@@ -128 +133 @@
     ///
     /// 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;

lemon/howard.h

@@ -107 +107 @@
   /// \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>
@@ -128 +133 @@
     ///
     /// 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;

lemon/karp.h

@@ -105 +105 @@
   /// \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>
@@ -126 +131 @@
     ///
     /// 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;

lemon/min_cost_arborescence.h

@@ -113 +113 @@
   /// 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,
@@ -123 +124 @@
               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

@@ -44 +44 @@
   /// \ref amo93networkflows, \ref dantzig63linearprog,
   /// \ref kellyoneill91netsimplex.
-  /// This algorithm is a specialized version of the linear programming
-  /// simplex method directly for the minimum cost flow problem.
-  /// It is one of the most efficient solution methods.
+  /// This algorithm is a highly efficient specialized version of the
+  /// linear programming simplex method directly for the minimum cost
+  /// flow problem.
   ///
-  /// In general this class is the fastest implementation available
-  /// in LEMON for the minimum cost flow problem.
-  /// Moreover it supports both directions of the supply/demand inequality
+  /// In general, %NetworkSimplex is the fastest implementation available
+  /// in LEMON for this problem.
+  /// Moreover, it supports both directions of the supply/demand inequality
   /// constraints. For more information, see \ref SupplyType.
   ///
@@ -59 +59 @@
   ///
   /// \tparam GR The digraph type the algorithm runs on.
-  /// \tparam V The value type used for flow amounts, capacity bounds
+  /// \tparam V The number type used for flow amounts, capacity bounds
   /// and supply values in the algorithm. By default, it is \c int.
-  /// \tparam C The value type used for costs and potentials in the
+  /// \tparam C The number type used for costs and potentials in the
   /// algorithm. By default, it is the same as \c V.
   ///
-  /// \warning Both value types must be signed and all input data must
+  /// \warning Both number types must be signed and all input data must
   /// be integer.
   ///
@@ -127 +127 @@
     /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
     /// proved to be the most efficient and the most robust on various
-    /// test inputs according to our benchmark tests.
+    /// test inputs.
     /// However, another pivot rule can be selected using the \ref run()
     /// function with the proper parameter.
@@ -165 +165 @@
 
     typedef std::vector<int> IntVector;
-    typedef std::vector<bool> BoolVector;
+    typedef std::vector<char> CharVector;
     typedef std::vector<Value> ValueVector;
     typedef std::vector<Cost> CostVector;
@@ -195 +195 @@
     IntVector _source;
     IntVector _target;
+    bool _arc_mixing;
 
     // Node and arc data
@@ -213 +214 @@
     IntVector _last_succ;
     IntVector _dirty_revs;
-    BoolVector _forward;
-    IntVector _state;
+    CharVector _forward;
+    CharVector _state;
     int _root;
 
@@ -222 +223 @@
     int stem, par_stem, new_stem;
     Value delta;
+    
+    const Value MAX;
 
   public:
@@ -243 +246 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const IntVector  &_state;
+      const CharVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -295 +298 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const IntVector  &_state;
+      const CharVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -334 +337 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const IntVector  &_state;
+      const CharVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -407 +410 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const IntVector  &_state;
+      const CharVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -510 +513 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const IntVector  &_state;
+      const CharVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -632 +635 @@
     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 ?
-          std::numeric_limits<Value>::infinity() :
-          std::numeric_limits<Value>::max())
+          std::numeric_limits<Value>::infinity() : MAX)
     {
-      // Check the value types
+      // Check the number types
       LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
         "The flow type of NetworkSimplex must be signed");
@@ -642 +646 @@
         "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();
     }
@@ -728 +681 @@
     /// 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 on each arc).
+    /// unbounded from above).
     ///
     /// \param map An arc map storing the upper bounds.
@@ -841 +794 @@
     /// \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
@@ -860 +813 @@
     ///
     /// \see ProblemType, PivotRule
+    /// \see resetParams(), reset()
     ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
       if (!init()) return INFEASIBLE;
@@ -871 +825 @@
     /// \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,
@@ -885 +840 @@
     ///     .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();
@@ -898 +853 @@
     ///
     /// \return <tt>(*this)</tt>
-    NetworkSimplex& reset() {
+    ///
+    /// \see reset(), run()
+    NetworkSimplex& resetParams() {
       for (int i = 0; i != _node_num; ++i) {
         _supply[i] = 0;
@@ -912 +869 @@
     }
 
+    /// \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;
+    }
+    
     /// @}
 
@@ -1021 +1055 @@
           Value c = _lower[i];
           if (c >= 0) {
-            _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
+            _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;
           } else {
-            _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
+            _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;
           }
           _supply[_source[i]] -= c;
@@ -1215 +1249 @@
         e = _pred[u];
         d = _forward[u] ?
-          _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);
+          _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
         if (d < delta) {
           delta = d;
@@ -1226 +1260 @@
         e = _pred[u];
         d = _forward[u] ? 
-          (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
+          (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
         if (d <= delta) {
           delta = d;
@@ -1425 +1459 @@
         findJoinNode();
         bool change = findLeavingArc();
-        if (delta >= INF) return UNBOUNDED;
+        if (delta >= MAX) return UNBOUNDED;
         changeFlow(change);
         if (change) {

lemon/planarity.h

@@ -519 +519 @@
   ///
   /// 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) {
@@ -533 +533 @@
   ///
   /// 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 {
@@ -592 +593 @@
   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;
@@ -700 +705 @@
     }
 
-    /// \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.
@@ -709 +714 @@
     }
 
-    /// \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];
     }
@@ -2060 +2067 @@
   ///
   /// 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 {
@@ -2073 +2082 @@
     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;
 
@@ -2082 +2091 @@
     ///
     /// 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) {}
@@ -2367 +2377 @@
   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);
@@ -2379 +2389 @@
     }
 
-    /// \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) {
@@ -2424 +2435 @@
     /// \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;
@@ -2471 +2483 @@
   ///
   /// 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
@@ -2500 +2511 @@
     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) {
@@ -2519 +2534 @@
     }
 
-    /// \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]];
@@ -2552 +2567 @@
 
 
-    /// \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() {
 
@@ -2661 +2676 @@
   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) {
@@ -2712 +2730 @@
     }
 
-    /// \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

@@ -114 +114 @@
   /// 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>

lemon/unionfind.h

@@ -740 +740 @@
     void clear() {
       items.clear();
-      classes.clear;
+      classes.clear();
       firstClass = firstFreeClass = firstFreeItem = -1;
     }

test/min_cost_flow_test.cc

@@ -25 +25 @@
 
 #include <lemon/network_simplex.h>
+#include <lemon/capacity_scaling.h>
+#include <lemon/cost_scaling.h>
+#include <lemon/cycle_canceling.h>
 
 #include <lemon/concepts/digraph.h>
+#include <lemon/concepts/heap.h>
 #include <lemon/concept_check.h>
 
@@ -33 +37 @@
 using namespace lemon;
 
+// Test networks
 char test_lgf[] =
   "@nodes\n"
@@ -77 +82 @@
   "target 12\n";
 
+char test_neg1_lgf[] =
+  "@nodes\n"
+  "label   sup\n"
+  "    1   100\n"
+  "    2     0\n"
+  "    3     0\n"
+  "    4  -100\n"
+  "    5     0\n"
+  "    6     0\n"
+  "    7     0\n"
+  "@arcs\n"
+  "      cost   low1   low2\n"
+  "1 2    100      0      0\n"
+  "1 3     30      0      0\n"
+  "2 4     20      0      0\n"
+  "3 4     80      0      0\n"
+  "3 2     50      0      0\n"
+  "5 3     10      0      0\n"
+  "5 6     80      0   1000\n"
+  "6 7     30      0  -1000\n"
+  "7 5   -120      0      0\n";
+  
+char test_neg2_lgf[] =
+  "@nodes\n"
+  "label   sup\n"
+  "    1   100\n"
+  "    2  -300\n"
+  "@arcs\n"
+  "      cost\n"
+  "1 2     -1\n";
+
+
+// Test data
+typedef ListDigraph Digraph;
+DIGRAPH_TYPEDEFS(ListDigraph);
+
+Digraph gr;
+Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
+Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
+ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
+Node v, w;
+
+Digraph neg1_gr;
+Digraph::ArcMap<int> neg1_c(neg1_gr), neg1_l1(neg1_gr), neg1_l2(neg1_gr);
+ConstMap<Arc, int> neg1_u1(std::numeric_limits<int>::max()), neg1_u2(5000);
+Digraph::NodeMap<int> neg1_s(neg1_gr);
+
+Digraph neg2_gr;
+Digraph::ArcMap<int> neg2_c(neg2_gr);
+ConstMap<Arc, int> neg2_l(0), neg2_u(1000);
+Digraph::NodeMap<int> neg2_s(neg2_gr);
+
 
 enum SupplyType {
@@ -83 +140 @@
   LEQ
 };
+
 
 // Check the interface of an MCF algorithm
@@ -100 +158 @@
       const MCF& const_mcf = mcf;
 
-      b = mcf.reset()
+      b = mcf.reset().resetParams()
              .lowerMap(me.lower)
              .upperMap(me.upper)
@@ -269 +327 @@
 }
 
+template < typename MCF, typename Param >
+void runMcfGeqTests( Param param,
+                     const std::string &test_str = "",
+                     bool full_neg_cost_support = false )
+{
+  MCF mcf1(gr), mcf2(neg1_gr), mcf3(neg2_gr);
+  
+  // Basic tests
+  mcf1.upperMap(u).costMap(c).supplyMap(s1);
+  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s1,
+           mcf1.OPTIMAL, true,     5240, test_str + "-1");
+  mcf1.stSupply(v, w, 27);
+  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s2,
+           mcf1.OPTIMAL, true,     7620, test_str + "-2");
+  mcf1.lowerMap(l2).supplyMap(s1);
+  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s1,
+           mcf1.OPTIMAL, true,     5970, test_str + "-3");
+  mcf1.stSupply(v, w, 27);
+  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2,
+           mcf1.OPTIMAL, true,     8010, test_str + "-4");
+  mcf1.resetParams().supplyMap(s1);
+  checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1,
+           mcf1.OPTIMAL, true,       74, test_str + "-5");
+  mcf1.lowerMap(l2).stSupply(v, w, 27);
+  checkMcf(mcf1, mcf1.run(param), gr, l2, cu, cc, s2,
+           mcf1.OPTIMAL, true,       94, test_str + "-6");
+  mcf1.reset();
+  checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s3,
+           mcf1.OPTIMAL, true,        0, test_str + "-7");
+  mcf1.lowerMap(l2).upperMap(u);
+  checkMcf(mcf1, mcf1.run(param), gr, l2, u, cc, s3,
+           mcf1.INFEASIBLE, false,    0, test_str + "-8");
+  mcf1.lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
+  checkMcf(mcf1, mcf1.run(param), gr, l3, u, c, s4,
+           mcf1.OPTIMAL, true,     6360, test_str + "-9");
+
+  // Tests for the GEQ form
+  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);
+  mcf1.lowerMap(l2);
+  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5,
+           mcf1.OPTIMAL, true,     4540, test_str + "-11", GEQ);
+  mcf1.supplyMap(s6);
+  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6,
+           mcf1.INFEASIBLE, false,    0, test_str + "-12", GEQ);
+
+  // Tests with negative costs
+  mcf2.lowerMap(neg1_l1).costMap(neg1_c).supplyMap(neg1_s);
+  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u1, neg1_c, neg1_s,
+           mcf2.UNBOUNDED, false,     0, test_str + "-13");
+  mcf2.upperMap(neg1_u2);
+  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s,
+           mcf2.OPTIMAL, true,   -40000, test_str + "-14");
+  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");
+
+  mcf3.costMap(neg2_c).supplyMap(neg2_s);
+  if (full_neg_cost_support) {
+    checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
+             mcf3.OPTIMAL, true,   -300, test_str + "-16", GEQ);
+  } else {
+    checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
+             mcf3.UNBOUNDED, false,   0, test_str + "-17", GEQ);
+  }
+  mcf3.upperMap(neg2_u);
+  checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
+           mcf3.OPTIMAL, true,     -300, test_str + "-18", GEQ);
+}
+
+template < typename MCF, typename Param >
+void runMcfLeqTests( Param param,
+                     const std::string &test_str = "" )
+{
+  // Tests for the LEQ form
+  MCF mcf1(gr);
+  mcf1.supplyType(mcf1.LEQ);
+  mcf1.upperMap(u).costMap(c).supplyMap(s6);
+  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s6,
+           mcf1.OPTIMAL, true,   5080, test_str + "-19", LEQ);
+  mcf1.lowerMap(l2);
+  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6,
+           mcf1.OPTIMAL, true,   5930, test_str + "-20", LEQ);
+  mcf1.supplyMap(s5);
+  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5,
+           mcf1.INFEASIBLE, false,  0, test_str + "-21", LEQ);
+}
+
+
 int main()
 {
-  // Check the interfaces
-  {
-    typedef concepts::Digraph GR;
-    checkConcept< McfClassConcept<GR, int, int>,
-                  NetworkSimplex<GR> >();
-    checkConcept< McfClassConcept<GR, double, double>,
-                  NetworkSimplex<GR, double> >();
-    checkConcept< McfClassConcept<GR, int, double>,
-                  NetworkSimplex<GR, int, double> >();
-  }
-
-  // Run various MCF tests
-  typedef ListDigraph Digraph;
-  DIGRAPH_TYPEDEFS(ListDigraph);
-
-  // Read the test digraph
-  Digraph gr;
-  Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
-  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
-  ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
-  Node v, w;
-
+  // Read the test networks
   std::istringstream input(test_lgf);
   DigraphReader<Digraph>(gr, input)
@@ -310 +437 @@
     .run();
   
-  // Build test digraphs with negative costs
-  Digraph neg_gr;
-  Node n1 = neg_gr.addNode();
-  Node n2 = neg_gr.addNode();
-  Node n3 = neg_gr.addNode();
-  Node n4 = neg_gr.addNode();
-  Node n5 = neg_gr.addNode();
-  Node n6 = neg_gr.addNode();
-  Node n7 = neg_gr.addNode();
-  
-  Arc a1 = neg_gr.addArc(n1, n2);
-  Arc a2 = neg_gr.addArc(n1, n3);
-  Arc a3 = neg_gr.addArc(n2, n4);
-  Arc a4 = neg_gr.addArc(n3, n4);
-  Arc a5 = neg_gr.addArc(n3, n2);
-  Arc a6 = neg_gr.addArc(n5, n3);
-  Arc a7 = neg_gr.addArc(n5, n6);
-  Arc a8 = neg_gr.addArc(n6, n7);
-  Arc a9 = neg_gr.addArc(n7, n5);
-  
-  Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0);
-  ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000);
-  Digraph::NodeMap<int> neg_s(neg_gr, 0);
-  
-  neg_l2[a7] =  1000;
-  neg_l2[a8] = -1000;
-  
-  neg_s[n1] =  100;
-  neg_s[n4] = -100;
-  
-  neg_c[a1] =  100;
-  neg_c[a2] =   30;
-  neg_c[a3] =   20;
-  neg_c[a4] =   80;
-  neg_c[a5] =   50;
-  neg_c[a6] =   10;
-  neg_c[a7] =   80;
-  neg_c[a8] =   30;
-  neg_c[a9] = -120;
-
-  Digraph negs_gr;
-  Digraph::NodeMap<int> negs_s(negs_gr);
-  Digraph::ArcMap<int> negs_c(negs_gr);
-  ConstMap<Arc, int> negs_l(0), negs_u(1000);
-  n1 = negs_gr.addNode();
-  n2 = negs_gr.addNode();
-  negs_s[n1] = 100;
-  negs_s[n2] = -300;
-  negs_c[negs_gr.addArc(n1, n2)] = -1;
-
-
-  // A. Test NetworkSimplex with the default pivot rule
-  {
-    NetworkSimplex<Digraph> mcf(gr);
-
-    // Check the equality form
-    mcf.upperMap(u).costMap(c);
-    checkMcf(mcf, mcf.supplyMap(s1).run(),
-             gr, l1, u, c, s1, mcf.OPTIMAL, true,   5240, "#A1");
-    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
-             gr, l1, u, c, s2, mcf.OPTIMAL, true,   7620, "#A2");
-    mcf.lowerMap(l2);
-    checkMcf(mcf, mcf.supplyMap(s1).run(),
-             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#A3");
-    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
-             gr, l2, u, c, s2, mcf.OPTIMAL, true,   8010, "#A4");
-    mcf.reset();
-    checkMcf(mcf, mcf.supplyMap(s1).run(),
-             gr, l1, cu, cc, s1, mcf.OPTIMAL, true,   74, "#A5");
-    checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
-             gr, l2, cu, cc, s2, mcf.OPTIMAL, true,   94, "#A6");
-    mcf.reset();
-    checkMcf(mcf, mcf.run(),
-             gr, l1, cu, cc, s3, mcf.OPTIMAL, true,    0, "#A7");
-    checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(),
-             gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8");
-    mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
-    checkMcf(mcf, mcf.run(),
-             gr, l3, u, c, s4, mcf.OPTIMAL, true,   6360, "#A9");
-
-    // Check the GEQ form
-    mcf.reset().upperMap(u).costMap(c).supplyMap(s5);
-    checkMcf(mcf, mcf.run(),
-             gr, l1, u, c, s5, mcf.OPTIMAL, true,   3530, "#A10", GEQ);
-    mcf.supplyType(mcf.GEQ);
-    checkMcf(mcf, mcf.lowerMap(l2).run(),
-             gr, l2, u, c, s5, mcf.OPTIMAL, true,   4540, "#A11", GEQ);
-    mcf.supplyMap(s6);
-    checkMcf(mcf, mcf.run(),
-             gr, l2, u, c, s6, mcf.INFEASIBLE, false,  0, "#A12", GEQ);
-
-    // Check the LEQ form
-    mcf.reset().supplyType(mcf.LEQ);
-    mcf.upperMap(u).costMap(c).supplyMap(s6);
-    checkMcf(mcf, mcf.run(),
-             gr, l1, u, c, s6, mcf.OPTIMAL, true,   5080, "#A13", LEQ);
-    checkMcf(mcf, mcf.lowerMap(l2).run(),
-             gr, l2, u, c, s6, mcf.OPTIMAL, true,   5930, "#A14", LEQ);
-    mcf.supplyMap(s5);
-    checkMcf(mcf, mcf.run(),
-             gr, l2, u, c, s5, mcf.INFEASIBLE, false,  0, "#A15", LEQ);
-
-    // Check negative costs
-    NetworkSimplex<Digraph> neg_mcf(neg_gr);
-    neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s);
-    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1,
-      neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A16");
-    neg_mcf.upperMap(neg_u2);
-    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2,
-      neg_c, neg_s, neg_mcf.OPTIMAL, true,  -40000, "#A17");
-    neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s);
-    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1,
-      neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A18");
-      
-    NetworkSimplex<Digraph> negs_mcf(negs_gr);
-    negs_mcf.costMap(negs_c).supplyMap(negs_s);
-    checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u,
-      negs_c, negs_s, negs_mcf.OPTIMAL, true, -300, "#A19", GEQ);
-  }
-
-  // B. Test NetworkSimplex with each pivot rule
-  {
-    NetworkSimplex<Digraph> mcf(gr);
-    mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2);
-
-    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
-             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B1");
-    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
-             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B2");
-    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
-             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B3");
-    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
-             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B4");
-    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
-             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B5");
+  std::istringstream neg_inp1(test_neg1_lgf);
+  DigraphReader<Digraph>(neg1_gr, neg_inp1)
+    .arcMap("cost", neg1_c)
+    .arcMap("low1", neg1_l1)
+    .arcMap("low2", neg1_l2)
+    .nodeMap("sup", neg1_s)
+    .run();
+  
+  std::istringstream neg_inp2(test_neg2_lgf);
+  DigraphReader<Digraph>(neg2_gr, neg_inp2)
+    .arcMap("cost", neg2_c)
+    .nodeMap("sup", neg2_s)
+    .run();
+  
+  // Check the interface of NetworkSimplex
+  {
+    typedef concepts::Digraph GR;
+    checkConcept< McfClassConcept<GR, int, int>,
+                  NetworkSimplex<GR> >();
+    checkConcept< McfClassConcept<GR, double, double>,
+                  NetworkSimplex<GR, double> >();
+    checkConcept< McfClassConcept<GR, int, double>,
+                  NetworkSimplex<GR, int, double> >();
+  }
+
+  // Check the interface of CapacityScaling
+  {
+    typedef concepts::Digraph GR;
+    checkConcept< McfClassConcept<GR, int, int>,
+                  CapacityScaling<GR> >();
+    checkConcept< McfClassConcept<GR, double, double>,
+                  CapacityScaling<GR, double> >();
+    checkConcept< McfClassConcept<GR, int, double>,
+                  CapacityScaling<GR, int, double> >();
+    typedef CapacityScaling<GR>::
+      SetHeap<concepts::Heap<int, RangeMap<int> > >::Create CAS;
+    checkConcept< McfClassConcept<GR, int, int>, CAS >();
+  }
+
+  // Check the interface of CostScaling
+  {
+    typedef concepts::Digraph GR;
+    checkConcept< McfClassConcept<GR, int, int>,
+                  CostScaling<GR> >();
+    checkConcept< McfClassConcept<GR, double, double>,
+                  CostScaling<GR, double> >();
+    checkConcept< McfClassConcept<GR, int, double>,
+                  CostScaling<GR, int, double> >();
+    typedef CostScaling<GR>::
+      SetLargeCost<double>::Create COS;
+    checkConcept< McfClassConcept<GR, int, int>, COS >();
+  }
+
+  // Check the interface of CycleCanceling
+  {
+    typedef concepts::Digraph GR;
+    checkConcept< McfClassConcept<GR, int, int>,
+                  CycleCanceling<GR> >();
+    checkConcept< McfClassConcept<GR, double, double>,
+                  CycleCanceling<GR, double> >();
+    checkConcept< McfClassConcept<GR, int, double>,
+                  CycleCanceling<GR, int, double> >();
+  }
+
+  // Test NetworkSimplex
+  { 
+    typedef NetworkSimplex<Digraph> MCF;
+    runMcfGeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE", true);
+    runMcfLeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE");
+    runMcfGeqTests<MCF>(MCF::BEST_ELIGIBLE,  "NS-BE", true);
+    runMcfLeqTests<MCF>(MCF::BEST_ELIGIBLE,  "NS-BE");
+    runMcfGeqTests<MCF>(MCF::BLOCK_SEARCH,   "NS-BS", true);
+    runMcfLeqTests<MCF>(MCF::BLOCK_SEARCH,   "NS-BS");
+    runMcfGeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL", true);
+    runMcfLeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL");
+    runMcfGeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL", true);
+    runMcfLeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL");
+  }
+  
+  // Test CapacityScaling
+  {
+    typedef CapacityScaling<Digraph> MCF;
+    runMcfGeqTests<MCF>(0, "SSP");
+    runMcfGeqTests<MCF>(2, "CAS");
+  }
+
+  // Test CostScaling
+  {
+    typedef CostScaling<Digraph> MCF;
+    runMcfGeqTests<MCF>(MCF::PUSH, "COS-PR");
+    runMcfGeqTests<MCF>(MCF::AUGMENT, "COS-AR");
+    runMcfGeqTests<MCF>(MCF::PARTIAL_AUGMENT, "COS-PAR");
+  }
+
+  // Test CycleCanceling
+  {
+    typedef CycleCanceling<Digraph> MCF;
+    runMcfGeqTests<MCF>(MCF::SIMPLE_CYCLE_CANCELING, "SCC");
+    runMcfGeqTests<MCF>(MCF::MINIMUM_MEAN_CYCLE_CANCELING, "MMCC");
+    runMcfGeqTests<MCF>(MCF::CANCEL_AND_TIGHTEN, "CAT");
   }