Changes in / [1041:f112c18bc304:1043:4e36fdf856b7] in lemon

Files:

• .hgtags (added)
• CMakeLists.txt (modified) (6 diffs)
• LICENSE (modified) (1 diff)
• NEWS (modified) (3 diffs)
• configure.ac (modified) (2 diffs)
• doc/CMakeLists.txt (modified) (2 diffs)
• doc/Doxyfile.in (modified) (14 diffs)
• doc/DoxygenLayout.xml (modified) (1 diff)
• doc/groups.dox (modified) (9 diffs)
• doc/mainpage.dox (deleted)
• doc/mainpage.dox.in (added)
• lemon/CMakeLists.txt (modified) (2 diffs)
• lemon/arg_parser.h (modified) (1 diff)
• lemon/bellman_ford.h (modified) (6 diffs)
• lemon/bits/edge_set_extender.h (modified) (1 diff)
• lemon/bits/graph_adaptor_extender.h (modified) (1 diff)
• lemon/bits/path_dump.h (modified) (2 diffs)
• lemon/core.h (modified) (2 diffs)
• lemon/dfs.h (modified) (2 diffs)
• lemon/hartmann_orlin_mmc.h (modified) (2 diffs)
• lemon/lemon.pc.cmake (added)
• lemon/network_simplex.h (modified) (2 diffs)
• lemon/preflow.h (modified) (5 diffs)
• test/CMakeLists.txt (modified) (3 diffs)
• test/bellman_ford_test.cc (modified) (1 diff)
• test/dfs_test.cc (modified) (4 diffs)
• test/graph_copy_test.cc (modified) (8 diffs)
• test/preflow_test.cc (modified) (2 diffs)

CMakeLists.txt

@@ -3 +3 @@
 SET(PROJECT_NAME "LEMON")
 PROJECT(${PROJECT_NAME})
+
+INCLUDE(FindPythonInterp)
+INCLUDE(FindWget)
 
 IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
@@ -10 +13 @@
 ELSE()
   EXECUTE_PROCESS(
+    COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
+    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
+    OUTPUT_VARIABLE HG_REVISION_PATH
+    ERROR_QUIET
+    OUTPUT_STRIP_TRAILING_WHITESPACE
+  )
+  EXECUTE_PROCESS(
     COMMAND hg id -i
     WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
@@ -17 +27 @@
   )
   IF(HG_REVISION STREQUAL "")
-    SET(HG_REVISION "hg-tip")
+    SET(HG_REVISION_ID "hg-tip")
+  ELSE()
+    IF(HG_REVISION_PATH STREQUAL "")
+      SET(HG_REVISION_ID ${HG_REVISION})
+    ELSE()
+      SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
+    ENDIF()
   ENDIF()
-  SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
+  SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
 ENDIF()
 
@@ -32 +48 @@
 FIND_PACKAGE(COIN)
 
+IF(DEFINED ENV{LEMON_CXX_WARNING})
+  SET(CXX_WARNING $ENV{LEMON_CXX_WARNING})
+ELSE()
+  IF(CMAKE_COMPILER_IS_GNUCXX)
+    SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
+    SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
+    SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
+  ELSEIF(MSVC)
+    # This part is unnecessary 'casue the same is set by the lemon/core.h.
+    # Still keep it as an example.
+    SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")
+    # Suppressed warnings:
+    # C4250: 'class1' : inherits 'class2::member' via dominance
+    # C4355: 'this' : used in base member initializer list
+    # C4503: 'function' : decorated name length exceeded, name was truncated
+    # C4800: 'type' : forcing value to bool 'true' or 'false'
+    #        (performance warning)
+    # C4996: 'function': was declared deprecated
+  ELSE()
+    SET(CXX_WARNING "-Wall -W")
+  ENDIF()
+ENDIF()
+SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.")
+
+SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
+
+SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb" CACHE STRING
+    "Flags used by the C++ compiler during maintainer builds."
+    FORCE )
+SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING
+    "Flags used by the C compiler during maintainer builds."
+    FORCE )
+SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
+    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
+    "Flags used for linking binaries during maintainer builds."
+    FORCE )
+SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
+    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
+    "Flags used by the shared libraries linker during maintainer builds."
+    FORCE )
+MARK_AS_ADVANCED(
+    CMAKE_CXX_FLAGS_MAINTAINER
+    CMAKE_C_FLAGS_MAINTAINER
+    CMAKE_EXE_LINKER_FLAGS_MAINTAINER
+    CMAKE_SHARED_LINKER_FLAGS_MAINTAINER )
+
+IF(CMAKE_CONFIGURATION_TYPES)
+  LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer)
+  LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES)
+  SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING
+      "Add the configurations that we need"
+      FORCE)
+ endif()
+
+IF(NOT CMAKE_BUILD_TYPE)
+  SET(CMAKE_BUILD_TYPE "Release")
+ENDIF()
+
+SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING
+    "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer."
+    FORCE )
+
+
 INCLUDE(CheckTypeSize)
 CHECK_TYPE_SIZE("long long" LONG_LONG)
@@ -39 +118 @@
 
 ENABLE_TESTING()
+
+IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
+  ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
+ELSE()
+  ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})
+ENDIF()
 
 ADD_SUBDIRECTORY(lemon)
@@ -65 +150 @@
 ENDIF()
 
-IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
+IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
   SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
   SET(CPACK_PACKAGE_VENDOR "EGRES")

LICENSE

@@ -2 +2 @@
 copyright/license.
 
-Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi
+Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi
 Kutatocsoport (Egervary Combinatorial Optimization Research Group,
 EGRES).

NEWS

@@ +1 @@
+2010-10-21 Version 1.2.1 released
+
+        Bugfix release.
+
+        #366: Fix Pred[Matrix]MapPath::empty()
+        #371: Bug fix in (di)graphCopy()
+              The target graph is cleared before adding nodes and arcs/edges.
+
+        #364: Add missing UndirectedTags
+        #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
+        #372: Fix a critical bug in preflow
+
+2010-03-19 Version 1.2 released
+
+        This is major feature release
+
+        * New algorithms
+          * Bellman-Ford algorithm (#51)
+          * Minimum mean cycle algorithms (#179)
+            * Karp, Hartman-Orlin and Howard algorithms
+          * New minimum cost flow algorithms (#180)
+            * Cost Scaling algorithms
+            * Capacity Scaling algorithm
+            * Cycle-Canceling algorithms
+          * Planarity related algorithms (#62)
+            * Planarity checking algorithm
+            * Planar embedding algorithm
+            * Schnyder's planar drawing algorithm
+            * Coloring planar graphs with five or six colors
+          * Fractional matching algorithms (#314)
+        * New data structures
+          * StaticDigraph structure (#68)
+          * Several new priority queue structures (#50, #301)
+            * Fibonacci, Radix, Bucket, Pairing, Binomial
+              D-ary and fourary heaps (#301)
+          * Iterable map structures (#73)
+        * Other new tools and functionality
+          * Map utility functions (#320)
+          * Reserve functions are added to ListGraph and SmartGraph (#311)
+          * A resize() function is added to HypercubeGraph (#311)
+          * A count() function is added to CrossRefMap (#302)
+          * Support for multiple targets in Suurballe using fullInit() (#181)
+          * Traits class and named parameters for Suurballe (#323)
+          * Separate reset() and resetParams() functions in NetworkSimplex
+            to handle graph changes (#327)
+          * tolerance() functions are added to HaoOrlin (#306)
+        * Implementation improvements
+          * Improvements in weighted matching algorithms (#314)
+            * Jumpstart initialization
+          * ArcIt iteration is based on out-arc lists instead of in-arc lists
+            in ListDigraph (#311)
+          * Faster add row operation in CbcMip (#203)
+          * Better implementation for split() in ListDigraph (#311)
+          * ArgParser can also throw exception instead of exit(1) (#332)
+        * Miscellaneous
+          * A simple interactive bootstrap script
+          * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,
+                #316,#319)
+            * BibTeX references in the doc (#184)
+          * Optionally use valgrind when running tests
+          * Also check ReferenceMapTag in concept checks (#312)
+          * dimacs-solver uses long long type by default.
+        * Several bugfixes (compared to release 1.1):
+          #295: Suppress MSVC warnings using pragmas
+          ----: Various CMAKE related improvements
+                * Remove duplications from doc/CMakeLists.txt
+                * Rename documentation install folder from 'docs' to 'html'
+                * Add tools/CMakeLists.txt to the tarball
+                * Generate and install LEMONConfig.cmake
+                * Change the label of the html project in Visual Studio
+                * Fix the check for the 'long long' type
+                * Put the version string into config.h
+                * Minor CMake improvements
+                * Set the version to 'hg-tip' if everything fails
+          #311: Add missing 'explicit' keywords
+          #302: Fix the implementation and doc of CrossRefMap
+          #308: Remove duplicate list_graph.h entry from source list
+          #307: Bugfix in Preflow and Circulation
+          #305: Bugfix and extension in the rename script
+          #312: Also check ReferenceMapTag in concept checks
+          #250: Bugfix in pathSource() and pathTarget()
+          #321: Use pathCopy(from,to) instead of copyPath(to,from)
+          #322: Distribure LEMONConfig.cmake.in
+          #330: Bug fix in map_extender.h
+          #336: Fix the date field comment of graphToEps() output
+          #323: Bug fix in Suurballe
+          #335: Fix clear() function in ExtendFindEnum
+          #337: Use void* as the LPX object pointer
+          #317: Fix (and improve) error message in mip_test.cc
+                Remove unnecessary OsiCbc dependency
+          #356: Allow multiple executions of weighted matching algorithms (#356)
+
 2009-05-13 Version 1.1 released
 
@@ -73 +165 @@
           ----: Add missing unistd.h include to time_measure.h
           #204: Compilation bug fixed in graph_to_eps.h with VS2005
-          #214,#215: windows.h should never be included by lemon headers
+          #214,#215: windows.h should never be included by LEMON headers
           #230: Build systems check the availability of 'long long' type
           #229: Default implementation of Tolerance<> is used for integer types
@@ -95 +187 @@
 2008-10-13 Version 1.0 released
 
-        This is the first stable release of LEMON. Compared to the 0.x
-        release series, it features a considerably smaller but more
-        matured set of tools. The API has also completely revised and
-        changed in several places.
-
-        * The major name changes compared to the 0.x series (see the
+        This is the first stable release of LEMON. Compared to the 0.x
+        release series, it features a considerably smaller but more
+        matured set of tools. The API has also completely revised and
+        changed in several places.
+
+        * The major name changes compared to the 0.x series (see the
           Migration Guide in the doc for more details)
           * Graph -> Digraph, UGraph -> Graph
           * Edge -> Arc, UEdge -> Edge
-          * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
-        * Other improvements
-          * Better documentation
-          * Reviewed and cleaned up codebase
-          * CMake based build system (along with the autotools based one)
-        * Contents of the library (ported from 0.x)
-          * Algorithms
-            * breadth-first search (bfs.h)
-            * depth-first search (dfs.h)
-            * Dijkstra's algorithm (dijkstra.h)
-            * Kruskal's algorithm (kruskal.h)
-          * Data structures
-            * graph data structures (list_graph.h, smart_graph.h)
-            * path data structures (path.h)
-            * binary heap data structure (bin_heap.h)
-            * union-find data structures (unionfind.h)
-            * miscellaneous property maps (maps.h)
-            * two dimensional vector and bounding box (dim2.h)
+          * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
+        * Other improvements
+          * Better documentation
+          * Reviewed and cleaned up codebase
+          * CMake based build system (along with the autotools based one)
+        * Contents of the library (ported from 0.x)
+          * Algorithms
+            * breadth-first search (bfs.h)
+            * depth-first search (dfs.h)
+            * Dijkstra's algorithm (dijkstra.h)
+            * Kruskal's algorithm (kruskal.h)
+          * Data structures
+            * graph data structures (list_graph.h, smart_graph.h)
+            * path data structures (path.h)
+            * binary heap data structure (bin_heap.h)
+            * union-find data structures (unionfind.h)
+            * miscellaneous property maps (maps.h)
+            * two dimensional vector and bounding box (dim2.h)
           * Concepts
-            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
+            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
               concepts/graph_components.h)
-            * concepts for other structures (concepts/heap.h, concepts/maps.h,
-              concepts/path.h)
-          * Tools
-            * Mersenne twister random number generator (random.h)
-            * tools for measuring cpu and wall clock time (time_measure.h)
-            * tools for counting steps and events (counter.h)
-            * tool for parsing command line arguments (arg_parser.h)
-            * tool for visualizing graphs (graph_to_eps.h)
-            * tools for reading and writing data in LEMON Graph Format
+            * concepts for other structures (concepts/heap.h, concepts/maps.h,
+              concepts/path.h)
+          * Tools
+            * Mersenne twister random number generator (random.h)
+            * tools for measuring cpu and wall clock time (time_measure.h)
+            * tools for counting steps and events (counter.h)
+            * tool for parsing command line arguments (arg_parser.h)
+            * tool for visualizing graphs (graph_to_eps.h)
+            * tools for reading and writing data in LEMON Graph Format
               (lgf_reader.h, lgf_writer.h)
             * tools to handle the anomalies of calculations with
-              floating point numbers (tolerance.h)
+              floating point numbers (tolerance.h)
             * tools to manage RGB colors (color.h)
-          * Infrastructure
-            * extended assertion handling (assert.h)
-            * exception classes and error handling (error.h)
-            * concept checking (concept_check.h)
-            * commonly used mathematical constants (math.h)
+          * Infrastructure
+            * extended assertion handling (assert.h)
+            * exception classes and error handling (error.h)
+            * concept checking (concept_check.h)
+            * commonly used mathematical constants (math.h)

configure.ac

@@ -115 +115 @@
 dnl Add dependencies on files generated by configure.
 AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
-  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
+  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/doc/mainpage.dox.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
 
 AC_CONFIG_FILES([
@@ -122 +122 @@
 cmake/version.cmake
 doc/Doxyfile
+doc/mainpage.dox
 lemon/lemon.pc
 ])

doc/CMakeLists.txt

@@ -4 +4 @@
 SET(abs_top_builddir ${PROJECT_BINARY_DIR})
 
+SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
+
 CONFIGURE_FILE(
   ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
   ${PROJECT_BINARY_DIR}/doc/Doxyfile
+  @ONLY
+)
+
+CONFIGURE_FILE(
+  ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in
+  ${PROJECT_BINARY_DIR}/doc/mainpage.dox
   @ONLY
 )
@@ -53 +61 @@
 
 ENDIF()
+
+IF(WGET_FOUND)
+ADD_CUSTOM_TARGET(update-external-tags
+  COMMAND ${CMAKE_COMMAND} -E make_directory dl
+  # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl
+  COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
+  COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag
+  COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag
+  COMMAND ${CMAKE_COMMAND} -E remove_directory dl
+  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
+  )
+ENDIF()

doc/Doxyfile.in

@@ -1 @@
-# Doxyfile 1.5.9
+# Doxyfile 1.7.3
 
 #---------------------------------------------------------------------------
@@ -5 +5 @@
 #---------------------------------------------------------------------------
 DOXYFILE_ENCODING      = UTF-8
-PROJECT_NAME           = @PACKAGE_NAME@
-PROJECT_NUMBER         = @PACKAGE_VERSION@
+PROJECT_NAME           = 
+PROJECT_NUMBER         = 
+PROJECT_BRIEF          =
+PROJECT_LOGO           =
 OUTPUT_DIRECTORY       = 
 CREATE_SUBDIRS         = NO
@@ -30 +32 @@
 OPTIMIZE_FOR_FORTRAN   = NO
 OPTIMIZE_OUTPUT_VHDL   = NO
+EXTENSION_MAPPING      =
 BUILTIN_STL_SUPPORT    = YES
 CPP_CLI_SUPPORT        = NO
@@ -55 +58 @@
 HIDE_SCOPE_NAMES       = YES
 SHOW_INCLUDE_FILES     = YES
+FORCE_LOCAL_INCLUDES   = NO
 INLINE_INFO            = YES
 SORT_MEMBER_DOCS       = NO
 SORT_BRIEF_DOCS        = NO
+SORT_MEMBERS_CTORS_1ST = NO
 SORT_GROUP_NAMES       = NO
 SORT_BY_SCOPE_NAME     = NO
+STRICT_PROTO_MATCHING  = NO
 GENERATE_TODOLIST      = YES
 GENERATE_TESTLIST      = YES
@@ -71 +77 @@
 SHOW_NAMESPACES        = YES
 FILE_VERSION_FILTER    = 
-LAYOUT_FILE            = DoxygenLayout.xml
+LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
 #---------------------------------------------------------------------------
 # configuration options related to warning and progress messages
@@ -92 +98 @@
                          "@abs_top_srcdir@/tools" \
                          "@abs_top_srcdir@/test/test_tools.h" \
+                         "@abs_top_builddir@/doc/mainpage.dox" \
                          "@abs_top_builddir@/doc/references.dox"
 INPUT_ENCODING         = UTF-8
@@ -112 +119 @@
 FILTER_PATTERNS        = 
 FILTER_SOURCE_FILES    = NO
+FILTER_SOURCE_PATTERNS =
 #---------------------------------------------------------------------------
 # configuration options related to source browsing
 #---------------------------------------------------------------------------
-SOURCE_BROWSER         = NO
+SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
 INLINE_SOURCES         = NO
 STRIP_CODE_COMMENTS    = YES
@@ -138 +146 @@
 HTML_FOOTER            = 
 HTML_STYLESHEET        = 
+HTML_COLORSTYLE_HUE    = 220
+HTML_COLORSTYLE_SAT    = 100
+HTML_COLORSTYLE_GAMMA  = 80
+HTML_TIMESTAMP         = YES
 HTML_ALIGN_MEMBERS     = YES
-HTML_DYNAMIC_SECTIONS  = NO
+HTML_DYNAMIC_SECTIONS  = YES
 GENERATE_DOCSET        = NO
 DOCSET_FEEDNAME        = "Doxygen generated docs"
 DOCSET_BUNDLE_ID       = org.doxygen.Project
+DOCSET_PUBLISHER_ID    = org.doxygen.Publisher
+DOCSET_PUBLISHER_NAME  = Publisher
 GENERATE_HTMLHELP      = NO
 CHM_FILE               = 
@@ -154 +168 @@
 QHP_NAMESPACE          = org.doxygen.Project
 QHP_VIRTUAL_FOLDER     = doc
+QHP_CUST_FILTER_NAME   =
+QHP_CUST_FILTER_ATTRS  =
+QHP_SECT_FILTER_ATTRS  =
 QHG_LOCATION           = 
+GENERATE_ECLIPSEHELP   = NO
+ECLIPSE_DOC_ID         = org.doxygen.Project
 DISABLE_INDEX          = NO
 ENUM_VALUES_PER_LINE   = 4
 GENERATE_TREEVIEW      = NO
+USE_INLINE_TREES       = NO
 TREEVIEW_WIDTH         = 250
+EXT_LINKS_IN_WINDOW    = NO
 FORMULA_FONTSIZE       = 10
+FORMULA_TRANSPARENT    = YES
+USE_MATHJAX            = NO
+MATHJAX_RELPATH        = http://www.mathjax.org/mathjax
+SEARCHENGINE           = YES
+SERVER_BASED_SEARCH    = NO
 #---------------------------------------------------------------------------
 # configuration options related to the LaTeX output
@@ -176 +202 @@
 LATEX_BATCHMODE        = NO
 LATEX_HIDE_INDICES     = NO
+LATEX_SOURCE_CODE      = NO
 #---------------------------------------------------------------------------
 # configuration options related to the RTF output
@@ -224 +251 @@
 SKIP_FUNCTION_MACROS   = YES
 #---------------------------------------------------------------------------
-# Options related to the search engine   
-#---------------------------------------------------------------------------
-TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
+# Configuration::additions related to external references
+#---------------------------------------------------------------------------
+TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
 GENERATE_TAGFILE       = html/lemon.tag
 ALLEXTERNALS           = NO
@@ -238 +265 @@
 HIDE_UNDOC_RELATIONS   = YES
 HAVE_DOT               = YES
+DOT_NUM_THREADS        = 0
 DOT_FONTNAME           = FreeSans
 DOT_FONTSIZE           = 10
@@ -255 +283 @@
 DOT_PATH               = 
 DOTFILE_DIRS           = 
+MSCFILE_DIRS           =
 DOT_GRAPH_MAX_NODES    = 50
 MAX_DOT_GRAPH_DEPTH    = 0
@@ -261 +290 @@
 GENERATE_LEGEND        = YES
 DOT_CLEANUP            = YES
-#---------------------------------------------------------------------------
-# Configuration::additions related to the search engine   
-#---------------------------------------------------------------------------
-SEARCHENGINE           = NO

doc/DoxygenLayout.xml

@@ -3 +3 @@
   <navindex>
     <tab type="mainpage" visible="yes" title=""/>
-    <tab type="modules" visible="yes" title=""/>
+    <tab type="modules" visible="yes" title="" intro=""/>
     <tab type="classes" visible="yes" title="">
-      <tab type="classes" visible="yes" title=""/>
-      <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/> 
-      <tab type="hierarchy" visible="yes" title=""/>
-      <tab type="classmembers" visible="yes" title=""/>
+      <tab type="classes" visible="yes" title="" intro=""/>
+      <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/>
+      <tab type="hierarchy" visible="yes" title="" intro=""/>
+      <tab type="classmembers" visible="yes" title="" intro=""/>
     </tab>
     <tab type="namespaces" visible="yes" title="">
-      <tab type="namespaces" visible="yes" title=""/>
-      <tab type="namespacemembers" visible="yes" title=""/>
+      <tab type="namespaces" visible="yes" title="" intro=""/>
+      <tab type="namespacemembers" visible="yes" title="" intro=""/>
     </tab>
     <tab type="files" visible="yes" title="">
-      <tab type="files" visible="yes" title=""/>
-      <tab type="globals" visible="yes" title=""/>
+      <tab type="files" visible="yes" title="" intro=""/>
+      <tab type="globals" visible="yes" title="" intro=""/>
     </tab>
-    <tab type="dirs" visible="yes" title=""/>
-    <tab type="examples" visible="yes" title=""/>  
-    <tab type="pages" visible="yes" title=""/>
+    <tab type="dirs" visible="yes" title="" intro=""/>
+    <tab type="examples" visible="yes" title="" intro=""/>
+    <tab type="pages" visible="yes" title="" intro=""/>
   </navindex>
 

doc/groups.dox

@@ -264 +264 @@
 
 /**
-@defgroup matrices Matrices
-@ingroup datas
-\brief Two dimensional data storages implemented in LEMON.
-
-This group contains two dimensional data storages implemented in LEMON.
-*/
-
-/**
 @defgroup auxdat Auxiliary Data Structures
 @ingroup datas
@@ -292 +284 @@
    rectangular bounding box of a set of \ref lemon::dim2::Point
    "dim2::Point"'s.
-*/
-
-/**
-@defgroup matrices Matrices
-@ingroup auxdat
-\brief Two dimensional data storages implemented in LEMON.
-
-This group contains two dimensional data storages implemented in LEMON.
 */
 
@@ -335 +319 @@
    but the digraph should not contain directed cycles with negative total
    length.
- - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
-   for solving the \e all-pairs \e shortest \e paths \e problem when arc
-   lenghts can be either positive or negative, but the digraph should
-   not contain directed cycles with negative total length.
  - \ref Suurballe A successive shortest path algorithm for finding
    arc-disjoint paths between two nodes having minimum total length.
@@ -372 +352 @@
 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
 
-LEMON contains several algorithms for solving maximum flow problems:
-- \ref EdmondsKarp Edmonds-Karp algorithm
-  \ref edmondskarp72theoretical.
-- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
-  \ref goldberg88newapproach.
-- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
-  \ref dinic70algorithm, \ref sleator83dynamic.
-- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
-  \ref goldberg88newapproach, \ref sleator83dynamic.
-
-In most cases the \ref Preflow algorithm provides the
-fastest method for computing a maximum flow. All implementations
-also provide functions to query the minimum cut, which is the dual
-problem of maximum flow.
+\ref Preflow is an efficient implementation of Goldberg-Tarjan's
+preflow push-relabel algorithm \ref goldberg88newapproach for finding
+maximum flows. It also provides functions to query the minimum cut,
+which is the dual problem of maximum flow.
 
 \ref Circulation is a preflow push-relabel algorithm implemented directly
@@ -442 +412 @@
 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
   in directed graphs.
-- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
-  calculating minimum cut in undirected graphs.
 - \ref GomoryHu "Gomory-Hu tree computation" for calculating
   all-pairs minimum cut in undirected graphs.
@@ -473 +441 @@
 
 LEMON contains three algorithms for solving the minimum mean cycle problem:
-- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
+- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
   \ref dasdan98minmeancycle.
-- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
+- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
   version of Karp's algorithm \ref dasdan98minmeancycle.
-- \ref Howard "Howard"'s policy iteration algorithm
+- \ref HowardMmc Howard's policy iteration algorithm
   \ref dasdan98minmeancycle.
 
-In practice, the Howard algorithm proved to be by far the most efficient
-one, though the best known theoretical bound on its running time is
-exponential.
-Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
-O(n<sup>2</sup>+e), but the latter one is typically faster due to the
-applied early termination scheme.
+In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
+most efficient one, though the best known theoretical bound on its running
+time is exponential.
+Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
+run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
+typically faster due to the applied early termination scheme.
 */
 
@@ -506 +474 @@
 
 The matching algorithms implemented in LEMON:
-- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
-  for calculating maximum cardinality matching in bipartite graphs.
-- \ref PrBipartiteMatching Push-relabel algorithm
-  for calculating maximum cardinality matching in bipartite graphs.
-- \ref MaxWeightedBipartiteMatching
-  Successive shortest path algorithm for calculating maximum weighted
-  matching and maximum weighted bipartite matching in bipartite graphs.
-- \ref MinCostMaxBipartiteMatching
-  Successive shortest path algorithm for calculating minimum cost maximum
-  matching in bipartite graphs.
 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
   maximum cardinality matching in general graphs.
@@ -560 +518 @@
 
 /**
-@defgroup approx Approximation Algorithms
-@ingroup algs
-\brief Approximation algorithms.
-
-This group contains the approximation and heuristic algorithms
-implemented in LEMON.
-*/
-
-/**
 @defgroup auxalg Auxiliary Algorithms
 @ingroup algs
@@ -597 +546 @@
 The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
 \ref cplex, \ref soplex.
-*/
-
-/**
-@defgroup lp_utils Tools for Lp and Mip Solvers
-@ingroup lp_group
-\brief Helper tools to the Lp and Mip solvers.
-
-This group adds some helper tools to general optimization framework
-implemented in LEMON.
-*/
-
-/**
-@defgroup metah Metaheuristics
-@ingroup gen_opt_group
-\brief Metaheuristics for LEMON library.
-
-This group contains some metaheuristic optimization tools.
 */
 

lemon/CMakeLists.txt

@@ -7 +7 @@
   ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
   ${CMAKE_CURRENT_BINARY_DIR}/config.h
+)
+
+CONFIGURE_FILE(
+  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
+  ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
+  @ONLY
 )
 
@@ -67 +73 @@
   COMPONENT headers
 )
+
+INSTALL(
+  FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
+  DESTINATION lib/pkgconfig
+)
+

lemon/arg_parser.h

@@ -36 +36 @@
 
   ///Exception used by ArgParser
+
+  ///Exception used by ArgParser.
+  ///
   class ArgParserException : public Exception {
   public:
+    /// Reasons for failure
+
+    /// Reasons for failure.
+    ///
     enum Reason {
-      HELP,         /// <tt>--help</tt> option was given
-      UNKNOWN_OPT,  /// Unknown option was given
-      INVALID_OPT   /// Invalid combination of options
+      HELP,         ///< <tt>--help</tt> option was given.
+      UNKNOWN_OPT,  ///< Unknown option was given.
+      INVALID_OPT   ///< Invalid combination of options.
     };
 

lemon/bellman_ford.h

@@ -29 +29 @@
 #include <lemon/error.h>
 #include <lemon/maps.h>
-#include <lemon/tolerance.h>
 #include <lemon/path.h>
 
@@ -36 +35 @@
 namespace lemon {
 
-  /// \brief Default operation traits for the BellmanFord algorithm class.
+  /// \brief Default OperationTraits for the BellmanFord algorithm class.
   ///
   /// This operation traits class defines all computational operations
@@ -43 +42 @@
   /// 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 {
-    /// \brief Value type for the algorithm.
+    /// \e
     typedef V Value;
     /// \brief Gives back the zero value of the type.
@@ -85 +82 @@
     static bool less(const Value& left, const Value& right) {
       return left < right;
-    }
-  };
-
-  /// \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;
     }
   };
@@ -156 +108 @@
     /// It defines the used operations and the infinity value for the
     /// given \c Value type.
-    /// \see BellmanFordDefaultOperationTraits,
-    /// BellmanFordToleranceOperationTraits
+    /// \see BellmanFordDefaultOperationTraits
     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 
@@ -887 +838 @@
     /// It defines the used operations and the infinity value for the
     /// given \c Value type.
-    /// \see BellmanFordDefaultOperationTraits,
-    /// BellmanFordToleranceOperationTraits
+    /// \see BellmanFordDefaultOperationTraits
     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 

lemon/bits/edge_set_extender.h

@@ -281 +281 @@
     typedef EdgeSetExtender Graph;
 
+    typedef True UndirectedTag;
+
     typedef typename Parent::Node Node;
     typedef typename Parent::Arc Arc;

lemon/bits/graph_adaptor_extender.h

@@ -182 +182 @@
     typedef GraphAdaptorExtender Adaptor;
 
+    typedef True UndirectedTag;
+
     typedef typename Parent::Node Node;
     typedef typename Parent::Arc Arc;

lemon/bits/path_dump.h

@@ -50 +50 @@
 
     bool empty() const {
-      return predMap[target] != INVALID;
+      return predMap[target] == INVALID;
     }
 
@@ -124 +124 @@
 
     bool empty() const {
-      return source != target;
+      return predMatrixMap(source, target) == INVALID;
     }
 

lemon/core.h

@@ -395 +395 @@
       static void copy(const From& from, Digraph &to,
                        NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
+        to.clear();
         for (typename From::NodeIt it(from); it != INVALID; ++it) {
           nodeRefMap[it] = to.addNode();
@@ -422 +423 @@
       static void copy(const From& from, Graph &to,
                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
+        to.clear();
         for (typename From::NodeIt it(from); it != INVALID; ++it) {
           nodeRefMap[it] = to.addNode();

lemon/dfs.h

@@ -566 +566 @@
     void start(Node t)
     {
-      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
+      while ( !emptyQueue() && !(*_reached)[t] )
         processNextArc();
     }
@@ -1513 +1513 @@
     /// with addSource() before using this function.
     void start(Node t) {
-      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
+      while ( !emptyQueue() && !(*_reached)[t] )
         processNextArc();
     }

lemon/hartmann_orlin_mmc.h

@@ -39 +39 @@
   /// \tparam GR The type of the digraph.
   /// \tparam CM The type of the cost map.
-  /// It must conform to the \ref concepts::Rea_data "Rea_data" concept.
+  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 #ifdef DOXYGEN
   template <typename GR, typename CM>
@@ -100 +100 @@
   /// a directed cycle of minimum mean cost in a digraph
   /// \ref amo93networkflows, \ref dasdan98minmeancycle.
-  /// It is an improved version of \ref Karp "Karp"'s original algorithm,
+  /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
   /// it applies an efficient early termination scheme.
   /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).

lemon/network_simplex.h

@@ -1078 +1078 @@
         ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;
       } else {
-        ART_COST = std::numeric_limits<Cost>::min();
+        ART_COST = 0;
         for (int i = 0; i != _arc_num; ++i) {
           if (_cost[i] > ART_COST) ART_COST = _cost[i];
@@ -1590 +1590 @@
       if (_sum_supply == 0) {
         if (_stype == GEQ) {
-          Cost max_pot = std::numeric_limits<Cost>::min();
+          Cost max_pot = -std::numeric_limits<Cost>::max();
           for (int i = 0; i != _node_num; ++i) {
             if (_pi[i] > max_pot) max_pot = _pi[i];

lemon/preflow.h

@@ -544 +544 @@
           _flow->set(e, (*_capacity)[e]);
           (*_excess)[u] += rem;
-          if (u != _target && !_level->active(u)) {
-            _level->activate(u);
-          }
         }
       }
@@ -556 +553 @@
           _flow->set(e, 0);
           (*_excess)[v] += rem;
-          if (v != _target && !_level->active(v)) {
-            _level->activate(v);
-          }
-        }
-      }
+        }
+      }
+      for (NodeIt n(_graph); n != INVALID; ++n) 
+        if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))
+          _level->activate(n);
+          
       return true;
     }
@@ -577 +575 @@
       _phase = true;
 
-      Node n = _level->highestActive();
-      int level = _level->highestActiveLevel();
-      while (n != INVALID) {
+      while (true) {
         int num = _node_num;
 
-        while (num > 0 && n != INVALID) {
+        Node n = INVALID;
+        int level = -1;
+
+        while (num > 0) {
+          n = _level->highestActive();
+          if (n == INVALID) goto first_phase_done;
+          level = _level->highestActiveLevel();
+          --num;
+          
           Value excess = (*_excess)[n];
           int new_level = _level->maxLevel();
@@ -648 +652 @@
             _level->deactivate(n);
           }
-
-          n = _level->highestActive();
-          level = _level->highestActiveLevel();
+        }
+
+        num = _node_num * 20;
+        while (num > 0) {
+          while (level >= 0 && _level->activeFree(level)) {
+            --level;
+          }
+          if (level == -1) {
+            n = _level->highestActive();
+            level = _level->highestActiveLevel();
+            if (n == INVALID) goto first_phase_done;
+          } else {
+            n = _level->activeOn(level);
+          }
           --num;
-        }
-
-        num = _node_num * 20;
-        while (num > 0 && n != INVALID) {
+
           Value excess = (*_excess)[n];
           int new_level = _level->maxLevel();
@@ -721 +733 @@
             _level->deactivate(n);
           }
-
-          while (level >= 0 && _level->activeFree(level)) {
-            --level;
-          }
-          if (level == -1) {
-            n = _level->highestActive();
-            level = _level->highestActiveLevel();
-          } else {
-            n = _level->activeOn(level);
-          }
-          --num;
-        }
-      }
+        }
+      }
+    first_phase_done:;
     }
 

test/CMakeLists.txt

@@ -46 +46 @@
 
 IF(LEMON_HAVE_LP)
-  ADD_EXECUTABLE(lp_test lp_test.cc)
+  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
+    ADD_EXECUTABLE(lp_test lp_test.cc)
+  ELSE()
+    ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc)
+  ENDIF()
+
   SET(LP_TEST_LIBS lemon)
 
@@ -82 +87 @@
 
 IF(LEMON_HAVE_MIP)
-  ADD_EXECUTABLE(mip_test mip_test.cc)
+  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
+    ADD_EXECUTABLE(mip_test mip_test.cc)
+  ELSE()
+    ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc)
+  ENDIF()
+
   SET(MIP_TEST_LIBS lemon)
 
@@ -118 +128 @@
 
 FOREACH(TEST_NAME ${TESTS})
-  ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
+  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
+    ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
+  ELSE()
+    ADD_EXECUTABLE(${TEST_NAME} EXCLUDE_FROM_ALL ${TEST_NAME}.cc)
+  ENDIF()
   TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
   ADD_TEST(${TEST_NAME} ${TEST_NAME})
+  ADD_DEPENDENCIES(check ${TEST_NAME})
 ENDFOREACH()

test/bellman_ford_test.cc

@@ -105 +105 @@
       ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
       ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
-      ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> >
       ::Create bf_test(gr,length);
 

test/dfs_test.cc

@@ -51 +51 @@
   "@attributes\n"
   "source 0\n"
-  "target 5\n";
+  "target 5\n"
+  "source1 6\n"
+  "target1 3\n";
+
 
 void checkDfsCompile()
@@ -180 +183 @@
   Digraph G;
   Node s, t;
+  Node s1, t1;
 
   std::istringstream input(test_lgf);
@@ -185 +189 @@
     node("source", s).
     node("target", t).
+    node("source1", s1).
+    node("target1", t1).
     run();
 
@@ -211 +217 @@
 
   {
+  Dfs<Digraph> dfs(G);
+  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
+  }
+  
+  {
     NullMap<Node,Arc> myPredMap;
     dfs(G).predMap(myPredMap).run(s);

test/graph_copy_test.cc

@@ -30 +30 @@
   const int nn = 10;
 
+  // Build a digraph
   SmartDigraph from;
   SmartDigraph::NodeMap<int> fnm(from);
@@ -52 +53 @@
   }
 
+  // Test digraph copy
   ListDigraph to;
   ListDigraph::NodeMap<int> tnm(to);
@@ -69 +71 @@
     nodeCrossRef(ncr).arcCrossRef(ecr).
     node(fn, tn).arc(fa, ta).run();
+  
+  check(countNodes(from) == countNodes(to), "Wrong copy.");
+  check(countArcs(from) == countArcs(to), "Wrong copy.");
 
   for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
@@ -91 +96 @@
   check(tn == nr[fn], "Wrong copy.");
   check(ta == er[fa], "Wrong copy.");
+
+  // Test repeated copy
+  digraphCopy(from, to).run();
+  
+  check(countNodes(from) == countNodes(to), "Wrong copy.");
+  check(countArcs(from) == countArcs(to), "Wrong copy.");
 }
 
@@ -96 +107 @@
   const int nn = 10;
 
+  // Build a graph
   SmartGraph from;
   SmartGraph::NodeMap<int> fnm(from);
@@ -123 +135 @@
   }
 
+  // Test graph copy
   ListGraph to;
   ListGraph::NodeMap<int> tnm(to);
@@ -144 +157 @@
     nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
     node(fn, tn).arc(fa, ta).edge(fe, te).run();
+
+  check(countNodes(from) == countNodes(to), "Wrong copy.");
+  check(countEdges(from) == countEdges(to), "Wrong copy.");
+  check(countArcs(from) == countArcs(to), "Wrong copy.");
 
   for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
@@ -181 +198 @@
   check(ta == ar[fa], "Wrong copy.");
   check(te == er[fe], "Wrong copy.");
+
+  // Test repeated copy
+  graphCopy(from, to).run();
+  
+  check(countNodes(from) == countNodes(to), "Wrong copy.");
+  check(countEdges(from) == countEdges(to), "Wrong copy.");
+  check(countArcs(from) == countArcs(to), "Wrong copy.");
 }
 

test/preflow_test.cc

@@ -157 +157 @@
 }
 
+void initFlowTest()
+{
+  DIGRAPH_TYPEDEFS(SmartDigraph);
+  
+  SmartDigraph g;
+  SmartDigraph::ArcMap<int> cap(g),iflow(g);
+  Node s=g.addNode(); Node t=g.addNode();
+  Node n1=g.addNode(); Node n2=g.addNode();
+  Arc a;
+  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
+  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
+  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
+
+  Preflow<SmartDigraph> pre(g,cap,s,t);
+  pre.init(iflow);
+  pre.startFirstPhase();
+  check(pre.flowValue() == 10, "The incorrect max flow value.");
+  check(pre.minCut(s), "Wrong min cut (Node s).");
+  check(pre.minCut(n1), "Wrong min cut (Node n1).");
+  check(!pre.minCut(n2), "Wrong min cut (Node n2).");
+  check(!pre.minCut(t), "Wrong min cut (Node t).");
+}
+
+
 int main() {
 
@@ -247 +271 @@
         "The max flow value or the three min cut values are incorrect.");
 
+  initFlowTest();
+  
   return 0;
 }