COIN-OR::LEMON - Graph Library

Ignore:
Files:
9 added
1 deleted
37 edited

Legend:

Unmodified
Added
Removed
  • CMakeLists.txt

    r791 r1056  
    33SET(PROJECT_NAME "LEMON")
    44PROJECT(${PROJECT_NAME})
     5
     6INCLUDE(FindPythonInterp)
     7INCLUDE(FindWget)
    58
    69IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
     
    1013ELSE()
    1114  EXECUTE_PROCESS(
     15    COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
     16    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     17    OUTPUT_VARIABLE HG_REVISION_PATH
     18    ERROR_QUIET
     19    OUTPUT_STRIP_TRAILING_WHITESPACE
     20  )
     21  EXECUTE_PROCESS(
    1222    COMMAND hg id -i
    1323    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     
    1727  )
    1828  IF(HG_REVISION STREQUAL "")
    19     SET(HG_REVISION "hg-tip")
     29    SET(HG_REVISION_ID "hg-tip")
     30  ELSE()
     31    IF(HG_REVISION_PATH STREQUAL "")
     32      SET(HG_REVISION_ID ${HG_REVISION})
     33    ELSE()
     34      SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
     35    ENDIF()
    2036  ENDIF()
    21   SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
     37  SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
    2238ENDIF()
    2339
     
    3248FIND_PACKAGE(COIN)
    3349
     50IF(DEFINED ENV{LEMON_CXX_WARNING})
     51  SET(CXX_WARNING $ENV{LEMON_CXX_WARNING})
     52ELSE()
     53  IF(CMAKE_COMPILER_IS_GNUCXX)
     54    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 -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
     55    SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
     56    SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
     57  ELSEIF(MSVC)
     58    # This part is unnecessary 'casue the same is set by the lemon/core.h.
     59    # Still keep it as an example.
     60    SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")
     61    # Suppressed warnings:
     62    # C4250: 'class1' : inherits 'class2::member' via dominance
     63    # C4355: 'this' : used in base member initializer list
     64    # C4503: 'function' : decorated name length exceeded, name was truncated
     65    # C4800: 'type' : forcing value to bool 'true' or 'false'
     66    #        (performance warning)
     67    # C4996: 'function': was declared deprecated
     68  ELSE()
     69    SET(CXX_WARNING "-Wall -W")
     70  ENDIF()
     71ENDIF()
     72SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.")
     73
     74SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
     75
     76SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb" CACHE STRING
     77    "Flags used by the C++ compiler during maintainer builds."
     78    FORCE )
     79SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING
     80    "Flags used by the C compiler during maintainer builds."
     81    FORCE )
     82SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     83    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
     84    "Flags used for linking binaries during maintainer builds."
     85    FORCE )
     86SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     87    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
     88    "Flags used by the shared libraries linker during maintainer builds."
     89    FORCE )
     90MARK_AS_ADVANCED(
     91    CMAKE_CXX_FLAGS_MAINTAINER
     92    CMAKE_C_FLAGS_MAINTAINER
     93    CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     94    CMAKE_SHARED_LINKER_FLAGS_MAINTAINER )
     95
     96IF(CMAKE_CONFIGURATION_TYPES)
     97  LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer)
     98  LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES)
     99  SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING
     100      "Add the configurations that we need"
     101      FORCE)
     102 endif()
     103
     104IF(NOT CMAKE_BUILD_TYPE)
     105  SET(CMAKE_BUILD_TYPE "Release")
     106ENDIF()
     107
     108SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING
     109    "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer."
     110    FORCE )
     111
     112
    34113INCLUDE(CheckTypeSize)
    35114CHECK_TYPE_SIZE("long long" LONG_LONG)
    36115SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
    37116
    38 INCLUDE(FindPythonInterp)
    39 
    40117ENABLE_TESTING()
     118
     119IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     120  ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
     121ELSE()
     122  ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})
     123ENDIF()
    41124
    42125ADD_SUBDIRECTORY(lemon)
    43126IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     127  ADD_SUBDIRECTORY(contrib)
    44128  ADD_SUBDIRECTORY(demo)
    45129  ADD_SUBDIRECTORY(tools)
     
    65149ENDIF()
    66150
    67 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
     151IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    68152  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    69153  SET(CPACK_PACKAGE_VENDOR "EGRES")
  • LICENSE

    r600 r959  
    22copyright/license.
    33
    4 Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi
     4Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi
    55Kutatocsoport (Egervary Combinatorial Optimization Research Group,
    66EGRES).
  • NEWS

    r712 r962  
     12010-03-19 Version 1.2 released
     2
     3        This is major feature release
     4
     5        * New algorithms
     6          * Bellman-Ford algorithm (#51)
     7          * Minimum mean cycle algorithms (#179)
     8            * Karp, Hartman-Orlin and Howard algorithms
     9          * New minimum cost flow algorithms (#180)
     10            * Cost Scaling algorithms
     11            * Capacity Scaling algorithm
     12            * Cycle-Canceling algorithms
     13          * Planarity related algorithms (#62)
     14            * Planarity checking algorithm
     15            * Planar embedding algorithm
     16            * Schnyder's planar drawing algorithm
     17            * Coloring planar graphs with five or six colors
     18          * Fractional matching algorithms (#314)
     19        * New data structures
     20          * StaticDigraph structure (#68)
     21          * Several new priority queue structures (#50, #301)
     22            * Fibonacci, Radix, Bucket, Pairing, Binomial
     23              D-ary and fourary heaps (#301)
     24          * Iterable map structures (#73)
     25        * Other new tools and functionality
     26          * Map utility functions (#320)
     27          * Reserve functions are added to ListGraph and SmartGraph (#311)
     28          * A resize() function is added to HypercubeGraph (#311)
     29          * A count() function is added to CrossRefMap (#302)
     30          * Support for multiple targets in Suurballe using fullInit() (#181)
     31          * Traits class and named parameters for Suurballe (#323)
     32          * Separate reset() and resetParams() functions in NetworkSimplex
     33            to handle graph changes (#327)
     34          * tolerance() functions are added to HaoOrlin (#306)
     35        * Implementation improvements
     36          * Improvements in weighted matching algorithms (#314)
     37            * Jumpstart initialization
     38          * ArcIt iteration is based on out-arc lists instead of in-arc lists
     39            in ListDigraph (#311)
     40          * Faster add row operation in CbcMip (#203)
     41          * Better implementation for split() in ListDigraph (#311)
     42          * ArgParser can also throw exception instead of exit(1) (#332)
     43        * Miscellaneous
     44          * A simple interactive bootstrap script
     45          * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,
     46                #316,#319)
     47            * BibTeX references in the doc (#184)
     48          * Optionally use valgrind when running tests
     49          * Also check ReferenceMapTag in concept checks (#312)
     50          * dimacs-solver uses long long type by default.
     51        * Several bugfixes (compared to release 1.1):
     52          #295: Suppress MSVC warnings using pragmas
     53          ----: Various CMAKE related improvements
     54                * Remove duplications from doc/CMakeLists.txt
     55                * Rename documentation install folder from 'docs' to 'html'
     56                * Add tools/CMakeLists.txt to the tarball
     57                * Generate and install LEMONConfig.cmake
     58                * Change the label of the html project in Visual Studio
     59                * Fix the check for the 'long long' type
     60                * Put the version string into config.h
     61                * Minor CMake improvements
     62                * Set the version to 'hg-tip' if everything fails
     63          #311: Add missing 'explicit' keywords
     64          #302: Fix the implementation and doc of CrossRefMap
     65          #308: Remove duplicate list_graph.h entry from source list
     66          #307: Bugfix in Preflow and Circulation
     67          #305: Bugfix and extension in the rename script
     68          #312: Also check ReferenceMapTag in concept checks
     69          #250: Bugfix in pathSource() and pathTarget()
     70          #321: Use pathCopy(from,to) instead of copyPath(to,from)
     71          #322: Distribure LEMONConfig.cmake.in
     72          #330: Bug fix in map_extender.h
     73          #336: Fix the date field comment of graphToEps() output
     74          #323: Bug fix in Suurballe
     75          #335: Fix clear() function in ExtendFindEnum
     76          #337: Use void* as the LPX object pointer
     77          #317: Fix (and improve) error message in mip_test.cc
     78                Remove unnecessary OsiCbc dependency
     79          #356: Allow multiple executions of weighted matching algorithms (#356)
     80
    1812009-05-13 Version 1.1 released
    282
     
    73153          ----: Add missing unistd.h include to time_measure.h
    74154          #204: Compilation bug fixed in graph_to_eps.h with VS2005
    75           #214,#215: windows.h should never be included by lemon headers
     155          #214,#215: windows.h should never be included by LEMON headers
    76156          #230: Build systems check the availability of 'long long' type
    77157          #229: Default implementation of Tolerance<> is used for integer types
     
    951752008-10-13 Version 1.0 released
    96176
    97         This is the first stable release of LEMON. Compared to the 0.x
    98         release series, it features a considerably smaller but more
    99         matured set of tools. The API has also completely revised and
    100         changed in several places.
    101 
    102         * The major name changes compared to the 0.x series (see the
     177        This is the first stable release of LEMON. Compared to the 0.x
     178        release series, it features a considerably smaller but more
     179        matured set of tools. The API has also completely revised and
     180        changed in several places.
     181
     182        * The major name changes compared to the 0.x series (see the
    103183          Migration Guide in the doc for more details)
    104184          * Graph -> Digraph, UGraph -> Graph
    105185          * Edge -> Arc, UEdge -> Edge
    106           * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
    107         * Other improvements
    108           * Better documentation
    109           * Reviewed and cleaned up codebase
    110           * CMake based build system (along with the autotools based one)
    111         * Contents of the library (ported from 0.x)
    112           * Algorithms
    113             * breadth-first search (bfs.h)
    114             * depth-first search (dfs.h)
    115             * Dijkstra's algorithm (dijkstra.h)
    116             * Kruskal's algorithm (kruskal.h)
    117           * Data structures
    118             * graph data structures (list_graph.h, smart_graph.h)
    119             * path data structures (path.h)
    120             * binary heap data structure (bin_heap.h)
    121             * union-find data structures (unionfind.h)
    122             * miscellaneous property maps (maps.h)
    123             * two dimensional vector and bounding box (dim2.h)
     186          * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
     187        * Other improvements
     188          * Better documentation
     189          * Reviewed and cleaned up codebase
     190          * CMake based build system (along with the autotools based one)
     191        * Contents of the library (ported from 0.x)
     192          * Algorithms
     193            * breadth-first search (bfs.h)
     194            * depth-first search (dfs.h)
     195            * Dijkstra's algorithm (dijkstra.h)
     196            * Kruskal's algorithm (kruskal.h)
     197          * Data structures
     198            * graph data structures (list_graph.h, smart_graph.h)
     199            * path data structures (path.h)
     200            * binary heap data structure (bin_heap.h)
     201            * union-find data structures (unionfind.h)
     202            * miscellaneous property maps (maps.h)
     203            * two dimensional vector and bounding box (dim2.h)
    124204          * Concepts
    125             * graph structure concepts (concepts/digraph.h, concepts/graph.h,
     205            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
    126206              concepts/graph_components.h)
    127             * concepts for other structures (concepts/heap.h, concepts/maps.h,
    128               concepts/path.h)
    129           * Tools
    130             * Mersenne twister random number generator (random.h)
    131             * tools for measuring cpu and wall clock time (time_measure.h)
    132             * tools for counting steps and events (counter.h)
    133             * tool for parsing command line arguments (arg_parser.h)
    134             * tool for visualizing graphs (graph_to_eps.h)
    135             * tools for reading and writing data in LEMON Graph Format
     207            * concepts for other structures (concepts/heap.h, concepts/maps.h,
     208              concepts/path.h)
     209          * Tools
     210            * Mersenne twister random number generator (random.h)
     211            * tools for measuring cpu and wall clock time (time_measure.h)
     212            * tools for counting steps and events (counter.h)
     213            * tool for parsing command line arguments (arg_parser.h)
     214            * tool for visualizing graphs (graph_to_eps.h)
     215            * tools for reading and writing data in LEMON Graph Format
    136216              (lgf_reader.h, lgf_writer.h)
    137217            * tools to handle the anomalies of calculations with
    138               floating point numbers (tolerance.h)
     218              floating point numbers (tolerance.h)
    139219            * tools to manage RGB colors (color.h)
    140           * Infrastructure
    141             * extended assertion handling (assert.h)
    142             * exception classes and error handling (error.h)
    143             * concept checking (concept_check.h)
    144             * commonly used mathematical constants (math.h)
     220          * Infrastructure
     221            * extended assertion handling (assert.h)
     222            * exception classes and error handling (error.h)
     223            * concept checking (concept_check.h)
     224            * commonly used mathematical constants (math.h)
  • configure.ac

    r840 r1039  
    115115dnl Add dependencies on files generated by configure.
    116116AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
    117   ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
     117  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/doc/mainpage.dox.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
    118118
    119119AC_CONFIG_FILES([
     
    122122cmake/version.cmake
    123123doc/Doxyfile
     124doc/mainpage.dox
    124125lemon/lemon.pc
    125126])
  • doc/CMakeLists.txt

    r943 r1040  
    44SET(abs_top_builddir ${PROJECT_BINARY_DIR})
    55
     6SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
     7
    68CONFIGURE_FILE(
    79  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
    810  ${PROJECT_BINARY_DIR}/doc/Doxyfile
     11  @ONLY
     12)
     13
     14CONFIGURE_FILE(
     15  ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in
     16  ${PROJECT_BINARY_DIR}/doc/mainpage.dox
    917  @ONLY
    1018)
     
    5361
    5462ENDIF()
     63
     64IF(WGET_FOUND)
     65ADD_CUSTOM_TARGET(update-external-tags
     66  COMMAND ${CMAKE_COMMAND} -E make_directory dl
     67  # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl
     68  COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
     69  COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag
     70  COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag
     71  COMMAND ${CMAKE_COMMAND} -E remove_directory dl
     72  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     73  )
     74ENDIF()
  • doc/Doxyfile.in

    r803 r1040  
    1 # Doxyfile 1.5.9
     1# Doxyfile 1.7.3
    22
    33#---------------------------------------------------------------------------
     
    55#---------------------------------------------------------------------------
    66DOXYFILE_ENCODING      = UTF-8
    7 PROJECT_NAME           = @PACKAGE_NAME@
    8 PROJECT_NUMBER         = @PACKAGE_VERSION@
     7PROJECT_NAME           =
     8PROJECT_NUMBER         =
     9PROJECT_BRIEF          =
     10PROJECT_LOGO           =
    911OUTPUT_DIRECTORY       =
    1012CREATE_SUBDIRS         = NO
     
    3032OPTIMIZE_FOR_FORTRAN   = NO
    3133OPTIMIZE_OUTPUT_VHDL   = NO
     34EXTENSION_MAPPING      =
    3235BUILTIN_STL_SUPPORT    = YES
    3336CPP_CLI_SUPPORT        = NO
     
    5558HIDE_SCOPE_NAMES       = YES
    5659SHOW_INCLUDE_FILES     = YES
     60FORCE_LOCAL_INCLUDES   = NO
    5761INLINE_INFO            = YES
    5862SORT_MEMBER_DOCS       = NO
    5963SORT_BRIEF_DOCS        = NO
     64SORT_MEMBERS_CTORS_1ST = NO
    6065SORT_GROUP_NAMES       = NO
    6166SORT_BY_SCOPE_NAME     = NO
     67STRICT_PROTO_MATCHING  = NO
    6268GENERATE_TODOLIST      = YES
    6369GENERATE_TESTLIST      = YES
     
    7177SHOW_NAMESPACES        = YES
    7278FILE_VERSION_FILTER    =
    73 LAYOUT_FILE            = DoxygenLayout.xml
     79LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
    7480#---------------------------------------------------------------------------
    7581# configuration options related to warning and progress messages
     
    9096                         "@abs_top_srcdir@/lemon/concepts" \
    9197                         "@abs_top_srcdir@/demo" \
     98                         "@abs_top_srcdir@/contrib" \
    9299                         "@abs_top_srcdir@/tools" \
    93100                         "@abs_top_srcdir@/test/test_tools.h" \
     101                         "@abs_top_builddir@/doc/mainpage.dox" \
    94102                         "@abs_top_builddir@/doc/references.dox"
    95103INPUT_ENCODING         = UTF-8
     
    112120FILTER_PATTERNS        =
    113121FILTER_SOURCE_FILES    = NO
     122FILTER_SOURCE_PATTERNS =
    114123#---------------------------------------------------------------------------
    115124# configuration options related to source browsing
    116125#---------------------------------------------------------------------------
    117 SOURCE_BROWSER         = NO
     126SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
    118127INLINE_SOURCES         = NO
    119128STRIP_CODE_COMMENTS    = YES
     
    138147HTML_FOOTER            =
    139148HTML_STYLESHEET        =
     149HTML_COLORSTYLE_HUE    = 220
     150HTML_COLORSTYLE_SAT    = 100
     151HTML_COLORSTYLE_GAMMA  = 80
     152HTML_TIMESTAMP         = YES
    140153HTML_ALIGN_MEMBERS     = YES
    141 HTML_DYNAMIC_SECTIONS  = NO
     154HTML_DYNAMIC_SECTIONS  = YES
    142155GENERATE_DOCSET        = NO
    143156DOCSET_FEEDNAME        = "Doxygen generated docs"
    144157DOCSET_BUNDLE_ID       = org.doxygen.Project
     158DOCSET_PUBLISHER_ID    = org.doxygen.Publisher
     159DOCSET_PUBLISHER_NAME  = Publisher
    145160GENERATE_HTMLHELP      = NO
    146161CHM_FILE               =
     
    154169QHP_NAMESPACE          = org.doxygen.Project
    155170QHP_VIRTUAL_FOLDER     = doc
     171QHP_CUST_FILTER_NAME   =
     172QHP_CUST_FILTER_ATTRS  =
     173QHP_SECT_FILTER_ATTRS  =
    156174QHG_LOCATION           =
     175GENERATE_ECLIPSEHELP   = NO
     176ECLIPSE_DOC_ID         = org.doxygen.Project
    157177DISABLE_INDEX          = NO
    158178ENUM_VALUES_PER_LINE   = 4
    159179GENERATE_TREEVIEW      = NO
     180USE_INLINE_TREES       = NO
    160181TREEVIEW_WIDTH         = 250
     182EXT_LINKS_IN_WINDOW    = NO
    161183FORMULA_FONTSIZE       = 10
     184FORMULA_TRANSPARENT    = YES
     185USE_MATHJAX            = NO
     186MATHJAX_RELPATH        = http://www.mathjax.org/mathjax
     187SEARCHENGINE           = YES
     188SERVER_BASED_SEARCH    = NO
    162189#---------------------------------------------------------------------------
    163190# configuration options related to the LaTeX output
     
    176203LATEX_BATCHMODE        = NO
    177204LATEX_HIDE_INDICES     = NO
     205LATEX_SOURCE_CODE      = NO
    178206#---------------------------------------------------------------------------
    179207# configuration options related to the RTF output
     
    224252SKIP_FUNCTION_MACROS   = YES
    225253#---------------------------------------------------------------------------
    226 # Options related to the search engine   
    227 #---------------------------------------------------------------------------
    228 TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
     254# Configuration::additions related to external references
     255#---------------------------------------------------------------------------
     256TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
    229257GENERATE_TAGFILE       = html/lemon.tag
    230258ALLEXTERNALS           = NO
     
    238266HIDE_UNDOC_RELATIONS   = YES
    239267HAVE_DOT               = YES
     268DOT_NUM_THREADS        = 0
    240269DOT_FONTNAME           = FreeSans
    241270DOT_FONTSIZE           = 10
     
    255284DOT_PATH               =
    256285DOTFILE_DIRS           =
     286MSCFILE_DIRS           =
    257287DOT_GRAPH_MAX_NODES    = 50
    258288MAX_DOT_GRAPH_DEPTH    = 0
     
    261291GENERATE_LEGEND        = YES
    262292DOT_CLEANUP            = YES
    263 #---------------------------------------------------------------------------
    264 # Configuration::additions related to the search engine   
    265 #---------------------------------------------------------------------------
    266 SEARCHENGINE           = NO
  • doc/DoxygenLayout.xml

    r316 r1036  
    33  <navindex>
    44    <tab type="mainpage" visible="yes" title=""/>
    5     <tab type="modules" visible="yes" title=""/>
     5    <tab type="modules" visible="yes" title="" intro=""/>
    66    <tab type="classes" visible="yes" title="">
    7       <tab type="classes" visible="yes" title=""/>
    8       <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/> 
    9       <tab type="hierarchy" visible="yes" title=""/>
    10       <tab type="classmembers" visible="yes" title=""/>
     7      <tab type="classes" visible="yes" title="" intro=""/>
     8      <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/>
     9      <tab type="hierarchy" visible="yes" title="" intro=""/>
     10      <tab type="classmembers" visible="yes" title="" intro=""/>
    1111    </tab>
    1212    <tab type="namespaces" visible="yes" title="">
    13       <tab type="namespaces" visible="yes" title=""/>
    14       <tab type="namespacemembers" visible="yes" title=""/>
     13      <tab type="namespaces" visible="yes" title="" intro=""/>
     14      <tab type="namespacemembers" visible="yes" title="" intro=""/>
    1515    </tab>
    1616    <tab type="files" visible="yes" title="">
    17       <tab type="files" visible="yes" title=""/>
    18       <tab type="globals" visible="yes" title=""/>
     17      <tab type="files" visible="yes" title="" intro=""/>
     18      <tab type="globals" visible="yes" title="" intro=""/>
    1919    </tab>
    20     <tab type="dirs" visible="yes" title=""/>
    21     <tab type="examples" visible="yes" title=""/> 
    22     <tab type="pages" visible="yes" title=""/>
     20    <tab type="dirs" visible="yes" title="" intro=""/>
     21    <tab type="examples" visible="yes" title="" intro=""/>
     22    <tab type="pages" visible="yes" title="" intro=""/>
    2323  </navindex>
    2424
  • doc/coding_style.dox

    r463 r1023  
    9999\subsection pri-loc-var Private member variables
    100100
    101 Private member variables should start with underscore
     101Private member variables should start with underscore.
    102102
    103103\code
    104 _start_with_underscores
     104_start_with_underscore
    105105\endcode
    106106
  • doc/dirs.dox

    r463 r1031  
    3232documentation.
    3333*/
     34
     35/**
     36\dir contrib
     37\brief Directory for user contributed source codes.
     38
     39You can place your own C++ code using LEMON into this directory, which
     40will compile to an executable along with LEMON when you build the
     41library. This is probably the easiest way of compiling short to medium
     42codes, for this does require neither a LEMON installed system-wide nor
     43adding several paths to the compiler.
     44
     45Please have a look at <tt>contrib/CMakeLists.txt</tt> for
     46instruction on how to add your own files into the build process.  */
    3447
    3548/**
  • doc/groups.dox

    r956 r1023  
    264264
    265265/**
    266 @defgroup matrices Matrices
    267 @ingroup datas
    268 \brief Two dimensional data storages implemented in LEMON.
    269 
    270 This group contains two dimensional data storages implemented in LEMON.
    271 */
    272 
    273 /**
    274266@defgroup auxdat Auxiliary Data Structures
    275267@ingroup datas
     
    415407   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
    416408
    417 In general NetworkSimplex is the most efficient implementation,
    418 but in special cases other algorithms could be faster.
     409In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
     410implementations, but the other two algorithms could be faster in special cases.
    419411For example, if the total supply and/or capacities are rather small,
    420 CapacityScaling is usually the fastest algorithm (without effective scaling).
     412\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
    421413*/
    422414
     
    473465
    474466LEMON contains three algorithms for solving the minimum mean cycle problem:
    475 - \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
     467- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
    476468  \ref dasdan98minmeancycle.
    477 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
     469- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    478470  version of Karp's algorithm \ref dasdan98minmeancycle.
    479 - \ref Howard "Howard"'s policy iteration algorithm
     471- \ref HowardMmc Howard's policy iteration algorithm
    480472  \ref dasdan98minmeancycle.
    481473
    482 In practice, the Howard algorithm proved to be by far the most efficient
    483 one, though the best known theoretical bound on its running time is
    484 exponential.
    485 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
    486 O(n<sup>2</sup>+e), but the latter one is typically faster due to the
    487 applied early termination scheme.
     474In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
     475most efficient one, though the best known theoretical bound on its running
     476time is exponential.
     477Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
     478run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
     479typically faster due to the applied early termination scheme.
    488480*/
    489481
     
    548540
    549541/**
    550 @defgroup planar Planarity Embedding and Drawing
     542@defgroup planar Planar Embedding and Drawing
    551543@ingroup algs
    552544\brief Algorithms for planarity checking, embedding and drawing
     
    560552
    561553/**
    562 @defgroup approx Approximation Algorithms
     554@defgroup approx_algs Approximation Algorithms
    563555@ingroup algs
    564556\brief Approximation algorithms.
     
    566558This group contains the approximation and heuristic algorithms
    567559implemented in LEMON.
     560
     561<b>Maximum Clique Problem</b>
     562  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
     563    Grosso, Locatelli, and Pullan.
    568564*/
    569565
  • doc/references.bib

    r802 r999  
    298298  address =      {Dublin, Ireland},
    299299  year =         1991,
    300   month =        sep,
    301 }
     300  month =        sep
     301}
     302
     303%%%%% Other algorithms %%%%%
     304
     305@article{grosso08maxclique,
     306  author =       {Andrea Grosso and Marco Locatelli and Wayne Pullan},
     307  title =        {Simple ingredients leading to very efficient
     308                  heuristics for the maximum clique problem},
     309  journal =      {Journal of Heuristics},
     310  year =         2008,
     311  volume =       14,
     312  number =       6,
     313  pages =        {587--612}
     314}
  • lemon/CMakeLists.txt

    r726 r1012  
    77  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
    88  ${CMAKE_CURRENT_BINARY_DIR}/config.h
     9)
     10
     11CONFIGURE_FILE(
     12  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
     13  ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
     14  @ONLY
    915)
    1016
     
    6773  COMPONENT headers
    6874)
     75
     76INSTALL(
     77  FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
     78  DESTINATION lib/pkgconfig
     79)
     80
  • lemon/Makefile.am

    r953 r1021  
    9191        lemon/graph_to_eps.h \
    9292        lemon/grid_graph.h \
     93        lemon/grosso_locatelli_pullan_mc.h \
    9394        lemon/hartmann_orlin_mmc.h \
    9495        lemon/howard_mmc.h \
     
    107108        lemon/math.h \
    108109        lemon/min_cost_arborescence.h \
     110        lemon/max_cardinality_search.h \
     111        lemon/nagamochi_ibaraki.h \
    109112        lemon/nauty_reader.h \
    110113        lemon/network_simplex.h \
  • lemon/arg_parser.h

    r956 r959  
    3636
    3737  ///Exception used by ArgParser
     38
     39  ///Exception used by ArgParser.
     40  ///
    3841  class ArgParserException : public Exception {
    3942  public:
     43    /// Reasons for failure
     44
     45    /// Reasons for failure.
     46    ///
    4047    enum Reason {
    41       HELP,         /// <tt>--help</tt> option was given
    42       UNKNOWN_OPT,  /// Unknown option was given
    43       INVALID_OPT   /// Invalid combination of options
     48      HELP,         ///< <tt>--help</tt> option was given.
     49      UNKNOWN_OPT,  ///< Unknown option was given.
     50      INVALID_OPT   ///< Invalid combination of options.
    4451    };
    4552
  • lemon/bellman_ford.h

    r956 r960  
    2929#include <lemon/error.h>
    3030#include <lemon/maps.h>
    31 #include <lemon/tolerance.h>
    3231#include <lemon/path.h>
    3332
     
    3635namespace lemon {
    3736
    38   /// \brief Default operation traits for the BellmanFord algorithm class.
     37  /// \brief Default OperationTraits for the BellmanFord algorithm class.
    3938  ///
    4039  /// This operation traits class defines all computational operations
     
    4342  /// If the numeric type does not have infinity value, then the maximum
    4443  /// value is used as extremal infinity value.
    45   ///
    46   /// \see BellmanFordToleranceOperationTraits
    4744  template <
    4845    typename V,
    4946    bool has_inf = std::numeric_limits<V>::has_infinity>
    5047  struct BellmanFordDefaultOperationTraits {
    51     /// \brief Value type for the algorithm.
     48    /// \e
    5249    typedef V Value;
    5350    /// \brief Gives back the zero value of the type.
     
    8582    static bool less(const Value& left, const Value& right) {
    8683      return left < right;
    87     }
    88   };
    89 
    90   /// \brief Operation traits for the BellmanFord algorithm class
    91   /// using tolerance.
    92   ///
    93   /// This operation traits class defines all computational operations
    94   /// and constants that are used in the Bellman-Ford algorithm.
    95   /// The only difference between this implementation and
    96   /// \ref BellmanFordDefaultOperationTraits is that this class uses
    97   /// the \ref Tolerance "tolerance technique" in its \ref less()
    98   /// function.
    99   ///
    100   /// \tparam V The value type.
    101   /// \tparam eps The epsilon value for the \ref less() function.
    102   /// By default, it is the epsilon value used by \ref Tolerance
    103   /// "Tolerance<V>".
    104   ///
    105   /// \see BellmanFordDefaultOperationTraits
    106 #ifdef DOXYGEN
    107   template <typename V, V eps>
    108 #else
    109   template <
    110     typename V,
    111     V eps = Tolerance<V>::def_epsilon>
    112 #endif
    113   struct BellmanFordToleranceOperationTraits {
    114     /// \brief Value type for the algorithm.
    115     typedef V Value;
    116     /// \brief Gives back the zero value of the type.
    117     static Value zero() {
    118       return static_cast<Value>(0);
    119     }
    120     /// \brief Gives back the positive infinity value of the type.
    121     static Value infinity() {
    122       return std::numeric_limits<Value>::infinity();
    123     }
    124     /// \brief Gives back the sum of the given two elements.
    125     static Value plus(const Value& left, const Value& right) {
    126       return left + right;
    127     }
    128     /// \brief Gives back \c true only if the first value is less than
    129     /// the second.
    130     static bool less(const Value& left, const Value& right) {
    131       return left + eps < right;
    13284    }
    13385  };
     
    156108    /// It defines the used operations and the infinity value for the
    157109    /// given \c Value type.
    158     /// \see BellmanFordDefaultOperationTraits,
    159     /// BellmanFordToleranceOperationTraits
     110    /// \see BellmanFordDefaultOperationTraits
    160111    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
    161112
     
    887838    /// It defines the used operations and the infinity value for the
    888839    /// given \c Value type.
    889     /// \see BellmanFordDefaultOperationTraits,
    890     /// BellmanFordToleranceOperationTraits
     840    /// \see BellmanFordDefaultOperationTraits
    891841    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
    892842
  • lemon/bits/edge_set_extender.h

    r956 r968  
    281281    typedef EdgeSetExtender Graph;
    282282
     283    typedef True UndirectedTag;
     284
    283285    typedef typename Parent::Node Node;
    284286    typedef typename Parent::Arc Arc;
  • lemon/bits/graph_adaptor_extender.h

    r664 r965  
    182182    typedef GraphAdaptorExtender Adaptor;
    183183
     184    typedef True UndirectedTag;
     185
    184186    typedef typename Parent::Node Node;
    185187    typedef typename Parent::Arc Arc;
  • lemon/bits/path_dump.h

    r576 r973  
    5050
    5151    bool empty() const {
    52       return predMap[target] != INVALID;
     52      return predMap[target] == INVALID;
    5353    }
    5454
     
    124124
    125125    bool empty() const {
    126       return source != target;
     126      return predMatrixMap(source, target) == INVALID;
    127127    }
    128128
  • lemon/bits/windows.cc

    r956 r1055  
    4141#include <unistd.h>
    4242#include <ctime>
     43#ifndef WIN32
    4344#include <sys/times.h>
     45#endif
    4446#include <sys/time.h>
    4547#endif
  • lemon/capacity_scaling.h

    r956 r1026  
    8787  /// consider to use the named template parameters instead.
    8888  ///
    89   /// \warning Both number types must be signed and all input data must
     89  /// \warning Both \c V and \c C must be signed number types.
     90  /// \warning All input data (capacities, supply values, and costs) must
    9091  /// be integer.
    91   /// \warning This algorithm does not support negative costs for such
    92   /// arcs that have infinite upper bound.
     92  /// \warning This algorithm does not support negative costs for
     93  /// arcs having infinite upper bound.
    9394#ifdef DOXYGEN
    9495  template <typename GR, typename V, typename C, typename TR>
     
    423424    ///
    424425    /// Using this function has the same effect as using \ref supplyMap()
    425     /// with such a map in which \c k is assigned to \c s, \c -k is
     426    /// with a map in which \c k is assigned to \c s, \c -k is
    426427    /// assigned to \c t and all other nodes have zero supply value.
    427428    ///
  • lemon/core.h

    r956 r1023  
    395395      static void copy(const From& from, Digraph &to,
    396396                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
     397        to.clear();
    397398        for (typename From::NodeIt it(from); it != INVALID; ++it) {
    398399          nodeRefMap[it] = to.addNode();
     
    422423      static void copy(const From& from, Graph &to,
    423424                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
     425        to.clear();
    424426        for (typename From::NodeIt it(from); it != INVALID; ++it) {
    425427          nodeRefMap[it] = to.addNode();
     
    445447
    446448  }
     449
     450  /// \brief Check whether a graph is undirected.
     451  ///
     452  /// This function returns \c true if the given graph is undirected.
     453#ifdef DOXYGEN
     454  template <typename GR>
     455  bool undirected(const GR& g) { return false; }
     456#else
     457  template <typename GR>
     458  typename enable_if<UndirectedTagIndicator<GR>, bool>::type
     459  undirected(const GR&) {
     460    return true;
     461  }
     462  template <typename GR>
     463  typename disable_if<UndirectedTagIndicator<GR>, bool>::type
     464  undirected(const GR&) {
     465    return false;
     466  }
     467#endif
    447468
    448469  /// \brief Class to copy a digraph.
  • lemon/cost_scaling.h

    r1041 r1049  
    9898  /// "preflow push-relabel" algorithm for the maximum flow problem.
    9999  ///
     100  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
     101  /// implementations available in LEMON for this problem.
     102  ///
    100103  /// Most of the parameters of the problem (except for the digraph)
    101104  /// can be given using separate functions, and the algorithm can be
     
    114117  /// consider to use the named template parameters instead.
    115118  ///
    116   /// \warning Both number types must be signed and all input data must
     119  /// \warning Both \c V and \c C must be signed number types.
     120  /// \warning All input data (capacities, supply values, and costs) must
    117121  /// be integer.
    118   /// \warning This algorithm does not support negative costs for such
    119   /// arcs that have infinite upper bound.
     122  /// \warning This algorithm does not support negative costs for
     123  /// arcs having infinite upper bound.
    120124  ///
    121125  /// \note %CostScaling provides three different internal methods,
     
    179183    /// relabel operation.
    180184    /// By default, the so called \ref PARTIAL_AUGMENT
    181     /// "Partial Augment-Relabel" method is used, which proved to be
     185    /// "Partial Augment-Relabel" method is used, which turned out to be
    182186    /// the most efficient and the most robust on various test inputs.
    183187    /// However, the other methods can be selected using the \ref run()
     
    234238    };
    235239
    236     typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;
    237240    typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap;
    238241
     
    285288    int _max_rank;
    286289
    287     // Data for a StaticDigraph structure
    288     typedef std::pair<int, int> IntPair;
    289     StaticDigraph _sgr;
    290     std::vector<IntPair> _arc_vec;
    291     std::vector<LargeCost> _cost_vec;
    292     LargeCostArcMap _cost_map;
    293     LargeCostNodeMap _pi_map;
    294 
    295290  public:
    296291
     
    339334    CostScaling(const GR& graph) :
    340335      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
    341       _cost_map(_cost_vec), _pi_map(_pi),
    342336      INF(std::numeric_limits<Value>::has_infinity ?
    343337          std::numeric_limits<Value>::infinity() :
     
    448442    ///
    449443    /// Using this function has the same effect as using \ref supplyMap()
    450     /// with such a map in which \c k is assigned to \c s, \c -k is
     444    /// with a map in which \c k is assigned to \c s, \c -k is
    451445    /// assigned to \c t and all other nodes have zero supply value.
    452446    ///
     
    494488    /// \param method The internal method that will be used in the
    495489    /// algorithm. For more information, see \ref Method.
    496     /// \param factor The cost scaling factor. It must be larger than one.
     490    /// \param factor The cost scaling factor. It must be at least two.
    497491    ///
    498492    /// \return \c INFEASIBLE if no feasible flow exists,
     
    508502    /// \see ProblemType, Method
    509503    /// \see resetParams(), reset()
    510     ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
     504    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 16) {
     505      LEMON_ASSERT(factor >= 2, "The scaling factor must be at least 2");
    511506      _alpha = factor;
    512507      ProblemType pt = init();
     
    572567    }
    573568
    574     /// \brief Reset all the parameters that have been given before.
    575     ///
    576     /// This function resets all the paramaters that have been given
    577     /// before using functions \ref lowerMap(), \ref upperMap(),
    578     /// \ref costMap(), \ref supplyMap(), \ref stSupply().
    579     ///
    580     /// It is useful for multiple run() calls. If this function is not
    581     /// used, all the parameters given before are kept for the next
    582     /// \ref run() call.
    583     /// However, the underlying digraph must not be modified after this
    584     /// class have been constructed, since it copies and extends the graph.
     569    /// \brief Reset the internal data structures and all the parameters
     570    /// that have been given before.
     571    ///
     572    /// This function resets the internal data structures and all the
     573    /// paramaters that have been given before using functions \ref lowerMap(),
     574    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     575    ///
     576    /// It is useful for multiple \ref run() calls. By default, all the given
     577    /// parameters are kept for the next \ref run() call, unless
     578    /// \ref resetParams() or \ref reset() is used.
     579    /// If the underlying digraph was also modified after the construction
     580    /// of the class or the last \ref reset() call, then the \ref reset()
     581    /// function must be used, otherwise \ref resetParams() is sufficient.
     582    ///
     583    /// See \ref resetParams() for examples.
     584    ///
    585585    /// \return <tt>(*this)</tt>
     586    ///
     587    /// \see resetParams(), run()
    586588    CostScaling& reset() {
    587589      // Resize vectors
     
    608610      _excess.resize(_res_node_num);
    609611      _next_out.resize(_res_node_num);
    610 
    611       _arc_vec.reserve(_res_arc_num);
    612       _cost_vec.reserve(_res_arc_num);
    613612
    614613      // Copy the graph
     
    887886      }
    888887
    889       return OPTIMAL;
    890     }
    891 
    892     // Execute the algorithm and transform the results
    893     void start(Method method) {
    894       // Maximum path length for partial augment
    895       const int MAX_PATH_LENGTH = 4;
    896 
    897888      // Initialize data structures for buckets
    898889      _max_rank = _alpha * _res_node_num;
     
    902893      _rank.resize(_res_node_num + 1);
    903894
    904       // Execute the algorithm
     895      return OPTIMAL;
     896    }
     897
     898    // Execute the algorithm and transform the results
     899    void start(Method method) {
     900      const int MAX_PARTIAL_PATH_LENGTH = 4;
     901
    905902      switch (method) {
    906903        case PUSH:
     
    911908          break;
    912909        case PARTIAL_AUGMENT:
    913           startAugment(MAX_PATH_LENGTH);
     910          startAugment(MAX_PARTIAL_PATH_LENGTH);
    914911          break;
    915912      }
    916913
    917       // Compute node potentials for the original costs
    918       _arc_vec.clear();
    919       _cost_vec.clear();
    920       for (int j = 0; j != _res_arc_num; ++j) {
    921         if (_res_cap[j] > 0) {
    922           _arc_vec.push_back(IntPair(_source[j], _target[j]));
    923           _cost_vec.push_back(_scost[j]);
    924         }
    925       }
    926       _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
    927 
    928       typename BellmanFord<StaticDigraph, LargeCostArcMap>
    929         ::template SetDistMap<LargeCostNodeMap>::Create bf(_sgr, _cost_map);
    930       bf.distMap(_pi_map);
    931       bf.init(0);
    932       bf.start();
     914      // Compute node potentials (dual solution)
     915      for (int i = 0; i != _res_node_num; ++i) {
     916        _pi[i] = static_cast<Cost>(_pi[i] / (_res_node_num * _alpha));
     917      }
     918      bool optimal = true;
     919      for (int i = 0; optimal && i != _res_node_num; ++i) {
     920        LargeCost pi_i = _pi[i];
     921        int last_out = _first_out[i+1];
     922        for (int j = _first_out[i]; j != last_out; ++j) {
     923          if (_res_cap[j] > 0 && _scost[j] + pi_i - _pi[_target[j]] < 0) {
     924            optimal = false;
     925            break;
     926          }
     927        }
     928      }
     929
     930      if (!optimal) {
     931        // Compute node potentials for the original costs with BellmanFord
     932        // (if it is necessary)
     933        typedef std::pair<int, int> IntPair;
     934        StaticDigraph sgr;
     935        std::vector<IntPair> arc_vec;
     936        std::vector<LargeCost> cost_vec;
     937        LargeCostArcMap cost_map(cost_vec);
     938
     939        arc_vec.clear();
     940        cost_vec.clear();
     941        for (int j = 0; j != _res_arc_num; ++j) {
     942          if (_res_cap[j] > 0) {
     943            int u = _source[j], v = _target[j];
     944            arc_vec.push_back(IntPair(u, v));
     945            cost_vec.push_back(_scost[j] + _pi[u] - _pi[v]);
     946          }
     947        }
     948        sgr.build(_res_node_num, arc_vec.begin(), arc_vec.end());
     949
     950        typename BellmanFord<StaticDigraph, LargeCostArcMap>::Create
     951          bf(sgr, cost_map);
     952        bf.init(0);
     953        bf.start();
     954
     955        for (int i = 0; i != _res_node_num; ++i) {
     956          _pi[i] += bf.dist(sgr.node(i));
     957        }
     958      }
     959
     960      // Shift potentials to meet the requirements of the GEQ type
     961      // optimality conditions
     962      LargeCost max_pot = _pi[_root];
     963      for (int i = 0; i != _res_node_num; ++i) {
     964        if (_pi[i] > max_pot) max_pot = _pi[i];
     965      }
     966      if (max_pot != 0) {
     967        for (int i = 0; i != _res_node_num; ++i) {
     968          _pi[i] -= max_pot;
     969        }
     970      }
    933971
    934972      // Handle non-zero lower bounds
     
    948986        LargeCost pi_u = _pi[u];
    949987        for (int a = _first_out[u]; a != last_out; ++a) {
    950           int v = _target[a];
    951           if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) {
    952             Value delta = _res_cap[a];
    953             _excess[u] -= delta;
    954             _excess[v] += delta;
    955             _res_cap[a] = 0;
    956             _res_cap[_reverse[a]] += delta;
     988          Value delta = _res_cap[a];
     989          if (delta > 0) {
     990            int v = _target[a];
     991            if (_cost[a] + pi_u - _pi[v] < 0) {
     992              _excess[u] -= delta;
     993              _excess[v] += delta;
     994              _res_cap[a] = 0;
     995              _res_cap[_reverse[a]] += delta;
     996            }
    957997          }
    958998        }
     
    9701010    }
    9711011
    972     // Early termination heuristic
    973     bool earlyTermination() {
    974       const double EARLY_TERM_FACTOR = 3.0;
    975 
    976       // Build a static residual graph
    977       _arc_vec.clear();
    978       _cost_vec.clear();
    979       for (int j = 0; j != _res_arc_num; ++j) {
    980         if (_res_cap[j] > 0) {
    981           _arc_vec.push_back(IntPair(_source[j], _target[j]));
    982           _cost_vec.push_back(_cost[j] + 1);
    983         }
    984       }
    985       _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
    986 
    987       // Run Bellman-Ford algorithm to check if the current flow is optimal
    988       BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
    989       bf.init(0);
    990       bool done = false;
    991       int K = int(EARLY_TERM_FACTOR * std::sqrt(double(_res_node_num)));
    992       for (int i = 0; i < K && !done; ++i) {
    993         done = bf.processNextWeakRound();
    994       }
    995       return done;
     1012    // Price (potential) refinement heuristic
     1013    bool priceRefinement() {
     1014
     1015      // Stack for stroing the topological order
     1016      IntVector stack(_res_node_num);
     1017      int stack_top;
     1018
     1019      // Perform phases
     1020      while (topologicalSort(stack, stack_top)) {
     1021
     1022        // Compute node ranks in the acyclic admissible network and
     1023        // store the nodes in buckets
     1024        for (int i = 0; i != _res_node_num; ++i) {
     1025          _rank[i] = 0;
     1026        }
     1027        const int bucket_end = _root + 1;
     1028        for (int r = 0; r != _max_rank; ++r) {
     1029          _buckets[r] = bucket_end;
     1030        }
     1031        int top_rank = 0;
     1032        for ( ; stack_top >= 0; --stack_top) {
     1033          int u = stack[stack_top], v;
     1034          int rank_u = _rank[u];
     1035
     1036          LargeCost rc, pi_u = _pi[u];
     1037          int last_out = _first_out[u+1];
     1038          for (int a = _first_out[u]; a != last_out; ++a) {
     1039            if (_res_cap[a] > 0) {
     1040              v = _target[a];
     1041              rc = _cost[a] + pi_u - _pi[v];
     1042              if (rc < 0) {
     1043                LargeCost nrc = static_cast<LargeCost>((-rc - 0.5) / _epsilon);
     1044                if (nrc < LargeCost(_max_rank)) {
     1045                  int new_rank_v = rank_u + static_cast<int>(nrc);
     1046                  if (new_rank_v > _rank[v]) {
     1047                    _rank[v] = new_rank_v;
     1048                  }
     1049                }
     1050              }
     1051            }
     1052          }
     1053
     1054          if (rank_u > 0) {
     1055            top_rank = std::max(top_rank, rank_u);
     1056            int bfirst = _buckets[rank_u];
     1057            _bucket_next[u] = bfirst;
     1058            _bucket_prev[bfirst] = u;
     1059            _buckets[rank_u] = u;
     1060          }
     1061        }
     1062
     1063        // Check if the current flow is epsilon-optimal
     1064        if (top_rank == 0) {
     1065          return true;
     1066        }
     1067
     1068        // Process buckets in top-down order
     1069        for (int rank = top_rank; rank > 0; --rank) {
     1070          while (_buckets[rank] != bucket_end) {
     1071            // Remove the first node from the current bucket
     1072            int u = _buckets[rank];
     1073            _buckets[rank] = _bucket_next[u];
     1074
     1075            // Search the outgoing arcs of u
     1076            LargeCost rc, pi_u = _pi[u];
     1077            int last_out = _first_out[u+1];
     1078            int v, old_rank_v, new_rank_v;
     1079            for (int a = _first_out[u]; a != last_out; ++a) {
     1080              if (_res_cap[a] > 0) {
     1081                v = _target[a];
     1082                old_rank_v = _rank[v];
     1083
     1084                if (old_rank_v < rank) {
     1085
     1086                  // Compute the new rank of node v
     1087                  rc = _cost[a] + pi_u - _pi[v];
     1088                  if (rc < 0) {
     1089                    new_rank_v = rank;
     1090                  } else {
     1091                    LargeCost nrc = rc / _epsilon;
     1092                    new_rank_v = 0;
     1093                    if (nrc < LargeCost(_max_rank)) {
     1094                      new_rank_v = rank - 1 - static_cast<int>(nrc);
     1095                    }
     1096                  }
     1097
     1098                  // Change the rank of node v
     1099                  if (new_rank_v > old_rank_v) {
     1100                    _rank[v] = new_rank_v;
     1101
     1102                    // Remove v from its old bucket
     1103                    if (old_rank_v > 0) {
     1104                      if (_buckets[old_rank_v] == v) {
     1105                        _buckets[old_rank_v] = _bucket_next[v];
     1106                      } else {
     1107                        int pv = _bucket_prev[v], nv = _bucket_next[v];
     1108                        _bucket_next[pv] = nv;
     1109                        _bucket_prev[nv] = pv;
     1110                      }
     1111                    }
     1112
     1113                    // Insert v into its new bucket
     1114                    int nv = _buckets[new_rank_v];
     1115                    _bucket_next[v] = nv;
     1116                    _bucket_prev[nv] = v;
     1117                    _buckets[new_rank_v] = v;
     1118                  }
     1119                }
     1120              }
     1121            }
     1122
     1123            // Refine potential of node u
     1124            _pi[u] -= rank * _epsilon;
     1125          }
     1126        }
     1127
     1128      }
     1129
     1130      return false;
     1131    }
     1132
     1133    // Find and cancel cycles in the admissible network and
     1134    // determine topological order using DFS
     1135    bool topologicalSort(IntVector &stack, int &stack_top) {
     1136      const int MAX_CYCLE_CANCEL = 1;
     1137
     1138      BoolVector reached(_res_node_num, false);
     1139      BoolVector processed(_res_node_num, false);
     1140      IntVector pred(_res_node_num);
     1141      for (int i = 0; i != _res_node_num; ++i) {
     1142        _next_out[i] = _first_out[i];
     1143      }
     1144      stack_top = -1;
     1145
     1146      int cycle_cnt = 0;
     1147      for (int start = 0; start != _res_node_num; ++start) {
     1148        if (reached[start]) continue;
     1149
     1150        // Start DFS search from this start node
     1151        pred[start] = -1;
     1152        int tip = start, v;
     1153        while (true) {
     1154          // Check the outgoing arcs of the current tip node
     1155          reached[tip] = true;
     1156          LargeCost pi_tip = _pi[tip];
     1157          int a, last_out = _first_out[tip+1];
     1158          for (a = _next_out[tip]; a != last_out; ++a) {
     1159            if (_res_cap[a] > 0) {
     1160              v = _target[a];
     1161              if (_cost[a] + pi_tip - _pi[v] < 0) {
     1162                if (!reached[v]) {
     1163                  // A new node is reached
     1164                  reached[v] = true;
     1165                  pred[v] = tip;
     1166                  _next_out[tip] = a;
     1167                  tip = v;
     1168                  a = _next_out[tip];
     1169                  last_out = _first_out[tip+1];
     1170                  break;
     1171                }
     1172                else if (!processed[v]) {
     1173                  // A cycle is found
     1174                  ++cycle_cnt;
     1175                  _next_out[tip] = a;
     1176
     1177                  // Find the minimum residual capacity along the cycle
     1178                  Value d, delta = _res_cap[a];
     1179                  int u, delta_node = tip;
     1180                  for (u = tip; u != v; ) {
     1181                    u = pred[u];
     1182                    d = _res_cap[_next_out[u]];
     1183                    if (d <= delta) {
     1184                      delta = d;
     1185                      delta_node = u;
     1186                    }
     1187                  }
     1188
     1189                  // Augment along the cycle
     1190                  _res_cap[a] -= delta;
     1191                  _res_cap[_reverse[a]] += delta;
     1192                  for (u = tip; u != v; ) {
     1193                    u = pred[u];
     1194                    int ca = _next_out[u];
     1195                    _res_cap[ca] -= delta;
     1196                    _res_cap[_reverse[ca]] += delta;
     1197                  }
     1198
     1199                  // Check the maximum number of cycle canceling
     1200                  if (cycle_cnt >= MAX_CYCLE_CANCEL) {
     1201                    return false;
     1202                  }
     1203
     1204                  // Roll back search to delta_node
     1205                  if (delta_node != tip) {
     1206                    for (u = tip; u != delta_node; u = pred[u]) {
     1207                      reached[u] = false;
     1208                    }
     1209                    tip = delta_node;
     1210                    a = _next_out[tip] + 1;
     1211                    last_out = _first_out[tip+1];
     1212                    break;
     1213                  }
     1214                }
     1215              }
     1216            }
     1217          }
     1218
     1219          // Step back to the previous node
     1220          if (a == last_out) {
     1221            processed[tip] = true;
     1222            stack[++stack_top] = tip;
     1223            tip = pred[tip];
     1224            if (tip < 0) {
     1225              // Finish DFS from the current start node
     1226              break;
     1227            }
     1228            ++_next_out[tip];
     1229          }
     1230        }
     1231
     1232      }
     1233
     1234      return (cycle_cnt == 0);
    9961235    }
    9971236
    9981237    // Global potential update heuristic
    9991238    void globalUpdate() {
    1000       int bucket_end = _root + 1;
     1239      const int bucket_end = _root + 1;
    10011240
    10021241      // Initialize buckets
     
    10051244      }
    10061245      Value total_excess = 0;
     1246      int b0 = bucket_end;
    10071247      for (int i = 0; i != _res_node_num; ++i) {
    10081248        if (_excess[i] < 0) {
    10091249          _rank[i] = 0;
    1010           _bucket_next[i] = _buckets[0];
    1011           _bucket_prev[_buckets[0]] = i;
    1012           _buckets[0] = i;
     1250          _bucket_next[i] = b0;
     1251          _bucket_prev[b0] = i;
     1252          b0 = i;
    10131253        } else {
    10141254          total_excess += _excess[i];
     
    10171257      }
    10181258      if (total_excess == 0) return;
     1259      _buckets[0] = b0;
    10191260
    10201261      // Search the buckets
     
    10381279                LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
    10391280                int new_rank_v = old_rank_v;
    1040                 if (nrc < LargeCost(_max_rank))
    1041                   new_rank_v = r + 1 + int(nrc);
     1281                if (nrc < LargeCost(_max_rank)) {
     1282                  new_rank_v = r + 1 + static_cast<int>(nrc);
     1283                }
    10421284
    10431285                // Change the rank of v
     
    10511293                      _buckets[old_rank_v] = _bucket_next[v];
    10521294                    } else {
    1053                       _bucket_next[_bucket_prev[v]] = _bucket_next[v];
    1054                       _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
     1295                      int pv = _bucket_prev[v], nv = _bucket_next[v];
     1296                      _bucket_next[pv] = nv;
     1297                      _bucket_prev[nv] = pv;
    10551298                    }
    10561299                  }
    10571300
    1058                   // Insert v to its new bucket
    1059                   _bucket_next[v] = _buckets[new_rank_v];
    1060                   _bucket_prev[_buckets[new_rank_v]] = v;
     1301                  // Insert v into its new bucket
     1302                  int nv = _buckets[new_rank_v];
     1303                  _bucket_next[v] = nv;
     1304                  _bucket_prev[nv] = v;
    10611305                  _buckets[new_rank_v] = v;
    10621306                }
     
    10871331    void startAugment(int max_length) {
    10881332      // Paramters for heuristics
    1089       const int EARLY_TERM_EPSILON_LIMIT = 1000;
    1090       const double GLOBAL_UPDATE_FACTOR = 3.0;
    1091 
    1092       const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
     1333      const int PRICE_REFINEMENT_LIMIT = 2;
     1334      const double GLOBAL_UPDATE_FACTOR = 1.0;
     1335      const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR *
    10931336        (_res_node_num + _sup_node_num * _sup_node_num));
    1094       int next_update_limit = global_update_freq;
    1095 
     1337      int next_global_update_limit = global_update_skip;
     1338
     1339      // Perform cost scaling phases
     1340      IntVector path;
     1341      BoolVector path_arc(_res_arc_num, false);
    10961342      int relabel_cnt = 0;
    1097 
    1098       // Perform cost scaling phases
    1099       std::vector<int> path;
     1343      int eps_phase_cnt = 0;
    11001344      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
    11011345                                        1 : _epsilon / _alpha )
    11021346      {
    1103         // Early termination heuristic
    1104         if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
    1105           if (earlyTermination()) break;
     1347        ++eps_phase_cnt;
     1348
     1349        // Price refinement heuristic
     1350        if (eps_phase_cnt >= PRICE_REFINEMENT_LIMIT) {
     1351          if (priceRefinement()) continue;
    11061352        }
    11071353
     
    11201366
    11211367          // Find an augmenting path from the start node
    1122           path.clear();
    11231368          int tip = start;
    1124           while (_excess[tip] >= 0 && int(path.size()) < max_length) {
     1369          while (int(path.size()) < max_length && _excess[tip] >= 0) {
    11251370            int u;
    1126             LargeCost min_red_cost, rc, pi_tip = _pi[tip];
     1371            LargeCost rc, min_red_cost = std::numeric_limits<LargeCost>::max();
     1372            LargeCost pi_tip = _pi[tip];
    11271373            int last_out = _first_out[tip+1];
    11281374            for (int a = _next_out[tip]; a != last_out; ++a) {
    1129               u = _target[a];
    1130               if (_res_cap[a] > 0 && _cost[a] + pi_tip - _pi[u] < 0) {
    1131                 path.push_back(a);
    1132                 _next_out[tip] = a;
    1133                 tip = u;
    1134                 goto next_step;
     1375              if (_res_cap[a] > 0) {
     1376                u = _target[a];
     1377                rc = _cost[a] + pi_tip - _pi[u];
     1378                if (rc < 0) {
     1379                  path.push_back(a);
     1380                  _next_out[tip] = a;
     1381                  if (path_arc[a]) {
     1382                    goto augment;   // a cycle is found, stop path search
     1383                  }
     1384                  tip = u;
     1385                  path_arc[a] = true;
     1386                  goto next_step;
     1387                }
     1388                else if (rc < min_red_cost) {
     1389                  min_red_cost = rc;
     1390                }
    11351391              }
    11361392            }
    11371393
    11381394            // Relabel tip node
    1139             min_red_cost = std::numeric_limits<LargeCost>::max();
    11401395            if (tip != start) {
    11411396              int ra = _reverse[path.back()];
    1142               min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]];
     1397              min_red_cost =
     1398                std::min(min_red_cost, _cost[ra] + pi_tip - _pi[_target[ra]]);
    11431399            }
     1400            last_out = _next_out[tip];
    11441401            for (int a = _first_out[tip]; a != last_out; ++a) {
    1145               rc = _cost[a] + pi_tip - _pi[_target[a]];
    1146               if (_res_cap[a] > 0 && rc < min_red_cost) {
    1147                 min_red_cost = rc;
     1402              if (_res_cap[a] > 0) {
     1403                rc = _cost[a] + pi_tip - _pi[_target[a]];
     1404                if (rc < min_red_cost) {
     1405                  min_red_cost = rc;
     1406                }
    11481407              }
    11491408            }
     
    11541413            // Step back
    11551414            if (tip != start) {
    1156               tip = _source[path.back()];
     1415              int pa = path.back();
     1416              path_arc[pa] = false;
     1417              tip = _source[pa];
    11571418              path.pop_back();
    11581419            }
     
    11621423
    11631424          // Augment along the found path (as much flow as possible)
     1425        augment:
    11641426          Value delta;
    11651427          int pa, u, v = start;
     
    11681430            u = v;
    11691431            v = _target[pa];
     1432            path_arc[pa] = false;
    11701433            delta = std::min(_res_cap[pa], _excess[u]);
    11711434            _res_cap[pa] -= delta;
     
    11731436            _excess[u] -= delta;
    11741437            _excess[v] += delta;
    1175             if (_excess[v] > 0 && _excess[v] <= delta)
     1438            if (_excess[v] > 0 && _excess[v] <= delta) {
    11761439              _active_nodes.push_back(v);
    1177           }
     1440            }
     1441          }
     1442          path.clear();
    11781443
    11791444          // Global update heuristic
    1180           if (relabel_cnt >= next_update_limit) {
     1445          if (relabel_cnt >= next_global_update_limit) {
    11811446            globalUpdate();
    1182             next_update_limit += global_update_freq;
    1183           }
    1184         }
    1185       }
     1447            next_global_update_limit += global_update_skip;
     1448          }
     1449        }
     1450
     1451      }
     1452
    11861453    }
    11871454
     
    11891456    void startPush() {
    11901457      // Paramters for heuristics
    1191       const int EARLY_TERM_EPSILON_LIMIT = 1000;
     1458      const int PRICE_REFINEMENT_LIMIT = 2;
    11921459      const double GLOBAL_UPDATE_FACTOR = 2.0;
    11931460
    1194       const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
     1461      const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR *
    11951462        (_res_node_num + _sup_node_num * _sup_node_num));
    1196       int next_update_limit = global_update_freq;
    1197 
    1198       int relabel_cnt = 0;
     1463      int next_global_update_limit = global_update_skip;
    11991464
    12001465      // Perform cost scaling phases
    12011466      BoolVector hyper(_res_node_num, false);
    12021467      LargeCostVector hyper_cost(_res_node_num);
     1468      int relabel_cnt = 0;
     1469      int eps_phase_cnt = 0;
    12031470      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
    12041471                                        1 : _epsilon / _alpha )
    12051472      {
    1206         // Early termination heuristic
    1207         if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
    1208           if (earlyTermination()) break;
     1473        ++eps_phase_cnt;
     1474
     1475        // Price refinement heuristic
     1476        if (eps_phase_cnt >= PRICE_REFINEMENT_LIMIT) {
     1477          if (priceRefinement()) continue;
    12091478        }
    12101479
     
    12781547               std::numeric_limits<LargeCost>::max();
    12791548            for (int a = _first_out[n]; a != last_out; ++a) {
    1280               rc = _cost[a] + pi_n - _pi[_target[a]];
    1281               if (_res_cap[a] > 0 && rc < min_red_cost) {
    1282                 min_red_cost = rc;
     1549              if (_res_cap[a] > 0) {
     1550                rc = _cost[a] + pi_n - _pi[_target[a]];
     1551                if (rc < min_red_cost) {
     1552                  min_red_cost = rc;
     1553                }
    12831554              }
    12841555            }
     
    12981569
    12991570          // Global update heuristic
    1300           if (relabel_cnt >= next_update_limit) {
     1571          if (relabel_cnt >= next_global_update_limit) {
    13011572            globalUpdate();
    13021573            for (int u = 0; u != _res_node_num; ++u)
    13031574              hyper[u] = false;
    1304             next_update_limit += global_update_freq;
     1575            next_global_update_limit += global_update_skip;
    13051576          }
    13061577        }
  • lemon/cycle_canceling.h

    r956 r1026  
    6666  /// algorithm. By default, it is the same as \c V.
    6767  ///
    68   /// \warning Both number types must be signed and all input data must
     68  /// \warning Both \c V and \c C must be signed number types.
     69  /// \warning All input data (capacities, supply values, and costs) must
    6970  /// be integer.
    70   /// \warning This algorithm does not support negative costs for such
    71   /// arcs that have infinite upper bound.
     71  /// \warning This algorithm does not support negative costs for
     72  /// arcs having infinite upper bound.
    7273  ///
    7374  /// \note For more information about the three available methods,
     
    117118    /// \ref CycleCanceling provides three different cycle-canceling
    118119    /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
    119     /// is used, which proved to be the most efficient and the most robust
    120     /// on various test inputs.
     120    /// is used, which is by far the most efficient and the most robust.
    121121    /// However, the other methods can be selected using the \ref run()
    122122    /// function with the proper parameter.
     
    350350    ///
    351351    /// Using this function has the same effect as using \ref supplyMap()
    352     /// with such a map in which \c k is assigned to \c s, \c -k is
     352    /// with a map in which \c k is assigned to \c s, \c -k is
    353353    /// assigned to \c t and all other nodes have zero supply value.
    354354    ///
  • lemon/dfs.h

    r956 r1010  
    566566    void start(Node t)
    567567    {
    568       while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
     568      while ( !emptyQueue() && !(*_reached)[t] )
    569569        processNextArc();
    570570    }
     
    15131513    /// with addSource() before using this function.
    15141514    void start(Node t) {
    1515       while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
     1515      while ( !emptyQueue() && !(*_reached)[t] )
    15161516        processNextArc();
    15171517    }
  • lemon/euler.h

    r956 r1023  
    3737  ///Euler tour iterator for digraphs.
    3838
    39   /// \ingroup graph_prop
     39  /// \ingroup graph_properties
    4040  ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
    4141  ///graph (if there exists) and it converts to the \c Arc type of the digraph.
  • lemon/hao_orlin.h

    r956 r1019  
    5454  /// preflow push-relabel algorithm. Our implementation calculates
    5555  /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
    56   /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
    57   /// purpose of such algorithm is e.g. testing network reliability.
     56  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. A notable
     57  /// use of this algorithm is testing network reliability.
    5858  ///
    5959  /// For an undirected graph you can run just the first phase of the
     
    913913    /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
    914914    /// \f$ source \in X \f$ and minimal outgoing capacity).
     915    /// It updates the stored cut if (and only if) the newly found one
     916    /// is better.
    915917    ///
    916918    /// \pre \ref init() must be called before using this function.
     
    925927    /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with
    926928    /// \f$ source \notin X \f$ and minimal outgoing capacity).
     929    /// It updates the stored cut if (and only if) the newly found one
     930    /// is better.
    927931    ///
    928932    /// \pre \ref init() must be called before using this function.
     
    934938    /// \brief Run the algorithm.
    935939    ///
    936     /// This function runs the algorithm. It finds nodes \c source and
    937     /// \c target arbitrarily and then calls \ref init(), \ref calculateOut()
     940    /// This function runs the algorithm. It chooses source node,
     941    /// then calls \ref init(), \ref calculateOut()
    938942    /// and \ref calculateIn().
    939943    void run() {
     
    945949    /// \brief Run the algorithm.
    946950    ///
    947     /// This function runs the algorithm. It uses the given \c source node,
    948     /// finds a proper \c target node and then calls the \ref init(),
    949     /// \ref calculateOut() and \ref calculateIn().
     951    /// This function runs the algorithm. It calls \ref init(),
     952    /// \ref calculateOut() and \ref calculateIn() with the given
     953    /// source node.
    950954    void run(const Node& s) {
    951955      init(s);
     
    966970    /// \brief Return the value of the minimum cut.
    967971    ///
    968     /// This function returns the value of the minimum cut.
     972    /// This function returns the value of the best cut found by the
     973    /// previously called \ref run(), \ref calculateOut() or \ref
     974    /// calculateIn().
    969975    ///
    970976    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
     
    977983    /// \brief Return a minimum cut.
    978984    ///
    979     /// This function sets \c cutMap to the characteristic vector of a
    980     /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$
    981     /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly
     985    /// This function gives the best cut found by the
     986    /// previously called \ref run(), \ref calculateOut() or \ref
     987    /// calculateIn().
     988    ///
     989    /// It sets \c cutMap to the characteristic vector of the found
     990    /// minimum value cut - a non-empty set \f$ X\subsetneq V \f$
     991    /// of minimum outgoing capacity (i.e. \c cutMap will be \c true exactly
    982992    /// for the nodes of \f$ X \f$).
    983993    ///
  • lemon/hartmann_orlin_mmc.h

    r956 r959  
    3939  /// \tparam GR The type of the digraph.
    4040  /// \tparam CM The type of the cost map.
    41   /// It must conform to the \ref concepts::Rea_data "Rea_data" concept.
     41  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    4242#ifdef DOXYGEN
    4343  template <typename GR, typename CM>
     
    100100  /// a directed cycle of minimum mean cost in a digraph
    101101  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
    102   /// It is an improved version of \ref Karp "Karp"'s original algorithm,
     102  /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
    103103  /// it applies an efficient early termination scheme.
    104104  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
  • lemon/kruskal.h

    r631 r1025  
    3131///\file
    3232///\brief Kruskal's algorithm to compute a minimum cost spanning tree
    33 ///
    34 ///Kruskal's algorithm to compute a minimum cost spanning tree.
    35 ///
    3633
    3734namespace lemon {
  • lemon/network_simplex.h

    r956 r1026  
    4848  /// flow problem.
    4949  ///
    50   /// In general, %NetworkSimplex is the fastest implementation available
    51   /// in LEMON for this problem.
    52   /// Moreover, it supports both directions of the supply/demand inequality
    53   /// constraints. For more information, see \ref SupplyType.
     50  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
     51  /// implementations available in LEMON for this problem.
     52  /// Furthermore, this class supports both directions of the supply/demand
     53  /// inequality constraints. For more information, see \ref SupplyType.
    5454  ///
    5555  /// Most of the parameters of the problem (except for the digraph)
     
    6464  /// algorithm. By default, it is the same as \c V.
    6565  ///
    66   /// \warning Both number types must be signed and all input data must
     66  /// \warning Both \c V and \c C must be signed number types.
     67  /// \warning All input data (capacities, supply values, and costs) must
    6768  /// be integer.
    6869  ///
     
    126127    /// of the algorithm.
    127128    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
    128     /// proved to be the most efficient and the most robust on various
     129    /// turend out to be the most efficient and the most robust on various
    129130    /// test inputs.
    130131    /// However, another pivot rule can be selected using the \ref run()
     
    167168    typedef std::vector<Value> ValueVector;
    168169    typedef std::vector<Cost> CostVector;
    169     typedef std::vector<char> BoolVector;
    170     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
     170    typedef std::vector<signed char> CharVector;
     171    // Note: vector<signed char> is used instead of vector<ArcState> and
     172    // vector<ArcDirection> for efficiency reasons
    171173
    172174    // State constants for arcs
     
    177179    };
    178180
    179     typedef std::vector<signed char> StateVector;
    180     // Note: vector<signed char> is used instead of vector<ArcState> for
    181     // efficiency reasons
     181    // Direction constants for tree arcs
     182    enum ArcDirection {
     183      DIR_DOWN = -1,
     184      DIR_UP   =  1
     185    };
    182186
    183187  private:
     
    218222    IntVector _succ_num;
    219223    IntVector _last_succ;
     224    CharVector _pred_dir;
     225    CharVector _state;
    220226    IntVector _dirty_revs;
    221     BoolVector _forward;
    222     StateVector _state;
    223227    int _root;
    224228
    225229    // Temporary data used in the current pivot iteration
    226230    int in_arc, join, u_in, v_in, u_out, v_out;
    227     int first, second, right, last;
    228     int stem, par_stem, new_stem;
    229231    Value delta;
    230232
     
    251253      const IntVector  &_target;
    252254      const CostVector &_cost;
    253       const StateVector &_state;
     255      const CharVector &_state;
    254256      const CostVector &_pi;
    255257      int &_in_arc;
     
    303305      const IntVector  &_target;
    304306      const CostVector &_cost;
    305       const StateVector &_state;
     307      const CharVector &_state;
    306308      const CostVector &_pi;
    307309      int &_in_arc;
     
    342344      const IntVector  &_target;
    343345      const CostVector &_cost;
    344       const StateVector &_state;
     346      const CharVector &_state;
    345347      const CostVector &_pi;
    346348      int &_in_arc;
     
    415417      const IntVector  &_target;
    416418      const CostVector &_cost;
    417       const StateVector &_state;
     419      const CharVector &_state;
    418420      const CostVector &_pi;
    419421      int &_in_arc;
     
    518520      const IntVector  &_target;
    519521      const CostVector &_cost;
    520       const StateVector &_state;
     522      const CharVector &_state;
    521523      const CostVector &_pi;
    522524      int &_in_arc;
     
    571573        // Check the current candidate list
    572574        int e;
     575        Cost c;
    573576        for (int i = 0; i != _curr_length; ++i) {
    574577          e = _candidates[i];
    575           _cand_cost[e] = _state[e] *
    576             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    577           if (_cand_cost[e] >= 0) {
     578          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     579          if (c < 0) {
     580            _cand_cost[e] = c;
     581          } else {
    578582            _candidates[i--] = _candidates[--_curr_length];
    579583          }
     
    585589
    586590        for (e = _next_arc; e != _search_arc_num; ++e) {
    587           _cand_cost[e] = _state[e] *
    588             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    589           if (_cand_cost[e] < 0) {
     591          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     592          if (c < 0) {
     593            _cand_cost[e] = c;
    590594            _candidates[_curr_length++] = e;
    591595          }
     
    634638    ///
    635639    /// \param graph The digraph the algorithm runs on.
    636     /// \param arc_mixing Indicate if the arcs have to be stored in a
     640    /// \param arc_mixing Indicate if the arcs will be stored in a
    637641    /// mixed order in the internal data structure.
    638     /// In special cases, it could lead to better overall performance,
    639     /// but it is usually slower. Therefore it is disabled by default.
    640     NetworkSimplex(const GR& graph, bool arc_mixing = false) :
     642    /// In general, it leads to similar performance as using the original
     643    /// arc order, but it makes the algorithm more robust and in special
     644    /// cases, even significantly faster. Therefore, it is enabled by default.
     645    NetworkSimplex(const GR& graph, bool arc_mixing = true) :
    641646      _graph(graph), _node_id(graph), _arc_id(graph),
    642647      _arc_mixing(arc_mixing),
     
    731736    ///
    732737    /// \return <tt>(*this)</tt>
     738    ///
     739    /// \sa supplyType()
    733740    template<typename SupplyMap>
    734741    NetworkSimplex& supplyMap(const SupplyMap& map) {
     
    747754    ///
    748755    /// Using this function has the same effect as using \ref supplyMap()
    749     /// with such a map in which \c k is assigned to \c s, \c -k is
     756    /// with a map in which \c k is assigned to \c s, \c -k is
    750757    /// assigned to \c t and all other nodes have zero supply value.
    751758    ///
     
    914921      _parent.resize(all_node_num);
    915922      _pred.resize(all_node_num);
    916       _forward.resize(all_node_num);
     923      _pred_dir.resize(all_node_num);
    917924      _thread.resize(all_node_num);
    918925      _rev_thread.resize(all_node_num);
     
    928935      if (_arc_mixing) {
    929936        // Store the arcs in a mixed order
    930         int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     937        const int skip = std::max(_arc_num / _node_num, 3);
    931938        int i = 0, j = 0;
    932939        for (ArcIt a(_graph); a != INVALID; ++a) {
     
    934941          _source[i] = _node_id[_graph.source(a)];
    935942          _target[i] = _node_id[_graph.target(a)];
    936           if ((i += k) >= _arc_num) i = ++j;
     943          if ((i += skip) >= _arc_num) i = ++j;
    937944        }
    938945      } else {
     
    10781085        ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;
    10791086      } else {
    1080         ART_COST = std::numeric_limits<Cost>::min();
     1087        ART_COST = 0;
    10811088        for (int i = 0; i != _arc_num; ++i) {
    10821089          if (_cost[i] > ART_COST) ART_COST = _cost[i];
     
    11171124          _state[e] = STATE_TREE;
    11181125          if (_supply[u] >= 0) {
    1119             _forward[u] = true;
     1126            _pred_dir[u] = DIR_UP;
    11201127            _pi[u] = 0;
    11211128            _source[e] = u;
     
    11241131            _cost[e] = 0;
    11251132          } else {
    1126             _forward[u] = false;
     1133            _pred_dir[u] = DIR_DOWN;
    11271134            _pi[u] = ART_COST;
    11281135            _source[e] = _root;
     
    11441151          _last_succ[u] = u;
    11451152          if (_supply[u] >= 0) {
    1146             _forward[u] = true;
     1153            _pred_dir[u] = DIR_UP;
    11471154            _pi[u] = 0;
    11481155            _pred[u] = e;
     
    11541161            _state[e] = STATE_TREE;
    11551162          } else {
    1156             _forward[u] = false;
     1163            _pred_dir[u] = DIR_DOWN;
    11571164            _pi[u] = ART_COST;
    11581165            _pred[u] = f;
     
    11851192          _last_succ[u] = u;
    11861193          if (_supply[u] <= 0) {
    1187             _forward[u] = false;
     1194            _pred_dir[u] = DIR_DOWN;
    11881195            _pi[u] = 0;
    11891196            _pred[u] = e;
     
    11951202            _state[e] = STATE_TREE;
    11961203          } else {
    1197             _forward[u] = true;
     1204            _pred_dir[u] = DIR_UP;
    11981205            _pi[u] = -ART_COST;
    11991206            _pred[u] = f;
     
    12381245      // Initialize first and second nodes according to the direction
    12391246      // of the cycle
     1247      int first, second;
    12401248      if (_state[in_arc] == STATE_LOWER) {
    12411249        first  = _source[in_arc];
     
    12471255      delta = _cap[in_arc];
    12481256      int result = 0;
    1249       Value d;
     1257      Value c, d;
    12501258      int e;
    12511259
    1252       // Search the cycle along the path form the first node to the root
     1260      // Search the cycle form the first node to the join node
    12531261      for (int u = first; u != join; u = _parent[u]) {
    12541262        e = _pred[u];
    1255         d = _forward[u] ?
    1256           _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
     1263        d = _flow[e];
     1264        if (_pred_dir[u] == DIR_DOWN) {
     1265          c = _cap[e];
     1266          d = c >= MAX ? INF : c - d;
     1267        }
    12571268        if (d < delta) {
    12581269          delta = d;
     
    12611272        }
    12621273      }
    1263       // Search the cycle along the path form the second node to the root
     1274
     1275      // Search the cycle form the second node to the join node
    12641276      for (int u = second; u != join; u = _parent[u]) {
    12651277        e = _pred[u];
    1266         d = _forward[u] ?
    1267           (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
     1278        d = _flow[e];
     1279        if (_pred_dir[u] == DIR_UP) {
     1280          c = _cap[e];
     1281          d = c >= MAX ? INF : c - d;
     1282        }
    12681283        if (d <= delta) {
    12691284          delta = d;
     
    12901305        _flow[in_arc] += val;
    12911306        for (int u = _source[in_arc]; u != join; u = _parent[u]) {
    1292           _flow[_pred[u]] += _forward[u] ? -val : val;
     1307          _flow[_pred[u]] -= _pred_dir[u] * val;
    12931308        }
    12941309        for (int u = _target[in_arc]; u != join; u = _parent[u]) {
    1295           _flow[_pred[u]] += _forward[u] ? val : -val;
     1310          _flow[_pred[u]] += _pred_dir[u] * val;
    12961311        }
    12971312      }
     
    13081323    // Update the tree structure
    13091324    void updateTreeStructure() {
    1310       int u, w;
    13111325      int old_rev_thread = _rev_thread[u_out];
    13121326      int old_succ_num = _succ_num[u_out];
     
    13141328      v_out = _parent[u_out];
    13151329
    1316       u = _last_succ[u_in];  // the last successor of u_in
    1317       right = _thread[u];    // the node after it
    1318 
    1319       // Handle the case when old_rev_thread equals to v_in
    1320       // (it also means that join and v_out coincide)
    1321       if (old_rev_thread == v_in) {
    1322         last = _thread[_last_succ[u_out]];
     1330      // Check if u_in and u_out coincide
     1331      if (u_in == u_out) {
     1332        // Update _parent, _pred, _pred_dir
     1333        _parent[u_in] = v_in;
     1334        _pred[u_in] = in_arc;
     1335        _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
     1336
     1337        // Update _thread and _rev_thread
     1338        if (_thread[v_in] != u_out) {
     1339          int after = _thread[old_last_succ];
     1340          _thread[old_rev_thread] = after;
     1341          _rev_thread[after] = old_rev_thread;
     1342          after = _thread[v_in];
     1343          _thread[v_in] = u_out;
     1344          _rev_thread[u_out] = v_in;
     1345          _thread[old_last_succ] = after;
     1346          _rev_thread[after] = old_last_succ;
     1347        }
    13231348      } else {
    1324         last = _thread[v_in];
    1325       }
    1326 
    1327       // Update _thread and _parent along the stem nodes (i.e. the nodes
    1328       // between u_in and u_out, whose parent have to be changed)
    1329       _thread[v_in] = stem = u_in;
    1330       _dirty_revs.clear();
    1331       _dirty_revs.push_back(v_in);
    1332       par_stem = v_in;
    1333       while (stem != u_out) {
    1334         // Insert the next stem node into the thread list
    1335         new_stem = _parent[stem];
    1336         _thread[u] = new_stem;
    1337         _dirty_revs.push_back(u);
    1338 
    1339         // Remove the subtree of stem from the thread list
    1340         w = _rev_thread[stem];
    1341         _thread[w] = right;
    1342         _rev_thread[right] = w;
    1343 
    1344         // Change the parent node and shift stem nodes
    1345         _parent[stem] = par_stem;
    1346         par_stem = stem;
    1347         stem = new_stem;
    1348 
    1349         // Update u and right
    1350         u = _last_succ[stem] == _last_succ[par_stem] ?
    1351           _rev_thread[par_stem] : _last_succ[stem];
    1352         right = _thread[u];
    1353       }
    1354       _parent[u_out] = par_stem;
    1355       _thread[u] = last;
    1356       _rev_thread[last] = u;
    1357       _last_succ[u_out] = u;
    1358 
    1359       // Remove the subtree of u_out from the thread list except for
    1360       // the case when old_rev_thread equals to v_in
    1361       // (it also means that join and v_out coincide)
    1362       if (old_rev_thread != v_in) {
    1363         _thread[old_rev_thread] = right;
    1364         _rev_thread[right] = old_rev_thread;
    1365       }
    1366 
    1367       // Update _rev_thread using the new _thread values
    1368       for (int i = 0; i != int(_dirty_revs.size()); ++i) {
    1369         u = _dirty_revs[i];
    1370         _rev_thread[_thread[u]] = u;
    1371       }
    1372 
    1373       // Update _pred, _forward, _last_succ and _succ_num for the
    1374       // stem nodes from u_out to u_in
    1375       int tmp_sc = 0, tmp_ls = _last_succ[u_out];
    1376       u = u_out;
    1377       while (u != u_in) {
    1378         w = _parent[u];
    1379         _pred[u] = _pred[w];
    1380         _forward[u] = !_forward[w];
    1381         tmp_sc += _succ_num[u] - _succ_num[w];
    1382         _succ_num[u] = tmp_sc;
    1383         _last_succ[w] = tmp_ls;
    1384         u = w;
    1385       }
    1386       _pred[u_in] = in_arc;
    1387       _forward[u_in] = (u_in == _source[in_arc]);
    1388       _succ_num[u_in] = old_succ_num;
    1389 
    1390       // Set limits for updating _last_succ form v_in and v_out
    1391       // towards the root
    1392       int up_limit_in = -1;
    1393       int up_limit_out = -1;
    1394       if (_last_succ[join] == v_in) {
    1395         up_limit_out = join;
    1396       } else {
    1397         up_limit_in = join;
     1349        // Handle the case when old_rev_thread equals to v_in
     1350        // (it also means that join and v_out coincide)
     1351        int thread_continue = old_rev_thread == v_in ?
     1352          _thread[old_last_succ] : _thread[v_in];
     1353
     1354        // Update _thread and _parent along the stem nodes (i.e. the nodes
     1355        // between u_in and u_out, whose parent have to be changed)
     1356        int stem = u_in;              // the current stem node
     1357        int par_stem = v_in;          // the new parent of stem
     1358        int next_stem;                // the next stem node
     1359        int last = _last_succ[u_in];  // the last successor of stem
     1360        int before, after = _thread[last];
     1361        _thread[v_in] = u_in;
     1362        _dirty_revs.clear();
     1363        _dirty_revs.push_back(v_in);
     1364        while (stem != u_out) {
     1365          // Insert the next stem node into the thread list
     1366          next_stem = _parent[stem];
     1367          _thread[last] = next_stem;
     1368          _dirty_revs.push_back(last);
     1369
     1370          // Remove the subtree of stem from the thread list
     1371          before = _rev_thread[stem];
     1372          _thread[before] = after;
     1373          _rev_thread[after] = before;
     1374
     1375          // Change the parent node and shift stem nodes
     1376          _parent[stem] = par_stem;
     1377          par_stem = stem;
     1378          stem = next_stem;
     1379
     1380          // Update last and after
     1381          last = _last_succ[stem] == _last_succ[par_stem] ?
     1382            _rev_thread[par_stem] : _last_succ[stem];
     1383          after = _thread[last];
     1384        }
     1385        _parent[u_out] = par_stem;
     1386        _thread[last] = thread_continue;
     1387        _rev_thread[thread_continue] = last;
     1388        _last_succ[u_out] = last;
     1389
     1390        // Remove the subtree of u_out from the thread list except for
     1391        // the case when old_rev_thread equals to v_in
     1392        if (old_rev_thread != v_in) {
     1393          _thread[old_rev_thread] = after;
     1394          _rev_thread[after] = old_rev_thread;
     1395        }
     1396
     1397        // Update _rev_thread using the new _thread values
     1398        for (int i = 0; i != int(_dirty_revs.size()); ++i) {
     1399          int u = _dirty_revs[i];
     1400          _rev_thread[_thread[u]] = u;
     1401        }
     1402
     1403        // Update _pred, _pred_dir, _last_succ and _succ_num for the
     1404        // stem nodes from u_out to u_in
     1405        int tmp_sc = 0, tmp_ls = _last_succ[u_out];
     1406        for (int u = u_out, p = _parent[u]; u != u_in; u = p, p = _parent[u]) {
     1407          _pred[u] = _pred[p];
     1408          _pred_dir[u] = -_pred_dir[p];
     1409          tmp_sc += _succ_num[u] - _succ_num[p];
     1410          _succ_num[u] = tmp_sc;
     1411          _last_succ[p] = tmp_ls;
     1412        }
     1413        _pred[u_in] = in_arc;
     1414        _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
     1415        _succ_num[u_in] = old_succ_num;
    13981416      }
    13991417
    14001418      // Update _last_succ from v_in towards the root
    1401       for (u = v_in; u != up_limit_in && _last_succ[u] == v_in;
    1402            u = _parent[u]) {
    1403         _last_succ[u] = _last_succ[u_out];
    1404       }
     1419      int up_limit_out = _last_succ[join] == v_in ? join : -1;
     1420      int last_succ_out = _last_succ[u_out];
     1421      for (int u = v_in; u != -1 && _last_succ[u] == v_in; u = _parent[u]) {
     1422        _last_succ[u] = last_succ_out;
     1423      }
     1424
    14051425      // Update _last_succ from v_out towards the root
    14061426      if (join != old_rev_thread && v_in != old_rev_thread) {
    1407         for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
     1427        for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
    14081428             u = _parent[u]) {
    14091429          _last_succ[u] = old_rev_thread;
    14101430        }
    1411       } else {
    1412         for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
     1431      }
     1432      else if (last_succ_out != old_last_succ) {
     1433        for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
    14131434             u = _parent[u]) {
    1414           _last_succ[u] = _last_succ[u_out];
     1435          _last_succ[u] = last_succ_out;
    14151436        }
    14161437      }
    14171438
    14181439      // Update _succ_num from v_in to join
    1419       for (u = v_in; u != join; u = _parent[u]) {
     1440      for (int u = v_in; u != join; u = _parent[u]) {
    14201441        _succ_num[u] += old_succ_num;
    14211442      }
    14221443      // Update _succ_num from v_out to join
    1423       for (u = v_out; u != join; u = _parent[u]) {
     1444      for (int u = v_out; u != join; u = _parent[u]) {
    14241445        _succ_num[u] -= old_succ_num;
    14251446      }
    14261447    }
    14271448
    1428     // Update potentials
     1449    // Update potentials in the subtree that has been moved
    14291450    void updatePotential() {
    1430       Cost sigma = _forward[u_in] ?
    1431         _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
    1432         _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];
    1433       // Update potentials in the subtree, which has been moved
     1451      Cost sigma = _pi[v_in] - _pi[u_in] -
     1452                   _pred_dir[u_in] * _cost[in_arc];
    14341453      int end = _thread[_last_succ[u_in]];
    14351454      for (int u = u_in; u != end; u = _thread[u]) {
     
    15901609      if (_sum_supply == 0) {
    15911610        if (_stype == GEQ) {
    1592           Cost max_pot = std::numeric_limits<Cost>::min();
     1611          Cost max_pot = -std::numeric_limits<Cost>::max();
    15931612          for (int i = 0; i != _node_num; ++i) {
    15941613            if (_pi[i] > max_pot) max_pot = _pi[i];
  • lemon/path.h

    r956 r1024  
    4444  ///
    4545  /// In a sense, the path can be treated as a list of arcs. The
    46   /// lemon path type stores just this list. As a consequence, it
     46  /// LEMON path type stores just this list. As a consequence, it
    4747  /// cannot enumerate the nodes of the path and the source node of
    4848  /// a zero length path is undefined.
     
    136136    void clear() { head.clear(); tail.clear(); }
    137137
    138     /// \brief The nth arc.
     138    /// \brief The n-th arc.
    139139    ///
    140140    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
     
    144144    }
    145145
    146     /// \brief Initialize arc iterator to point to the nth arc
     146    /// \brief Initialize arc iterator to point to the n-th arc
    147147    ///
    148148    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
     
    232232  ///
    233233  /// In a sense, the path can be treated as a list of arcs. The
    234   /// lemon path type stores just this list. As a consequence it
     234  /// LEMON path type stores just this list. As a consequence it
    235235  /// cannot enumerate the nodes in the path and the zero length paths
    236236  /// cannot store the source.
     
    328328    void clear() { data.clear(); }
    329329
    330     /// \brief The nth arc.
     330    /// \brief The n-th arc.
    331331    ///
    332332    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
     
    335335    }
    336336
    337     /// \brief  Initializes arc iterator to point to the nth arc.
     337    /// \brief  Initializes arc iterator to point to the n-th arc.
    338338    ArcIt nthIt(int n) const {
    339339      return ArcIt(*this, n);
     
    396396  ///
    397397  /// In a sense, the path can be treated as a list of arcs. The
    398   /// lemon path type stores just this list. As a consequence it
     398  /// LEMON path type stores just this list. As a consequence it
    399399  /// cannot enumerate the nodes in the path and the zero length paths
    400400  /// cannot store the source.
     
    505505    };
    506506
    507     /// \brief The nth arc.
    508     ///
    509     /// This function looks for the nth arc in O(n) time.
     507    /// \brief The n-th arc.
     508    ///
     509    /// This function looks for the n-th arc in O(n) time.
    510510    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    511511    const Arc& nth(int n) const {
     
    517517    }
    518518
    519     /// \brief Initializes arc iterator to point to the nth arc.
     519    /// \brief Initializes arc iterator to point to the n-th arc.
    520520    ArcIt nthIt(int n) const {
    521521      Node *node = first;
     
    736736  ///
    737737  /// In a sense, the path can be treated as a list of arcs. The
    738   /// lemon path type stores just this list. As a consequence it
     738  /// LEMON path type stores just this list. As a consequence it
    739739  /// cannot enumerate the nodes in the path and the source node of
    740740  /// a zero length path is undefined.
     
    832832    };
    833833
    834     /// \brief The nth arc.
     834    /// \brief The n-th arc.
    835835    ///
    836836    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
     
    839839    }
    840840
    841     /// \brief The arc iterator pointing to the nth arc.
     841    /// \brief The arc iterator pointing to the n-th arc.
    842842    ArcIt nthIt(int n) const {
    843843      return ArcIt(*this, n);
     
    10431043  ///
    10441044  /// In a sense, the path can be treated as a list of arcs. The
    1045   /// lemon path type stores only this list. As a consequence, it
     1045  /// LEMON path type stores only this list. As a consequence, it
    10461046  /// cannot enumerate the nodes in the path and the zero length paths
    10471047  /// cannot have a source node.
  • lemon/preflow.h

    r956 r1029  
    544544          _flow->set(e, (*_capacity)[e]);
    545545          (*_excess)[u] += rem;
    546           if (u != _target && !_level->active(u)) {
    547             _level->activate(u);
    548           }
    549546        }
    550547      }
     
    556553          _flow->set(e, 0);
    557554          (*_excess)[v] += rem;
    558           if (v != _target && !_level->active(v)) {
    559             _level->activate(v);
    560           }
    561         }
    562       }
     555        }
     556      }
     557      for (NodeIt n(_graph); n != INVALID; ++n)
     558        if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))
     559          _level->activate(n);
     560         
    563561      return true;
    564562    }
     
    577575      _phase = true;
    578576
    579       Node n = _level->highestActive();
    580       int level = _level->highestActiveLevel();
    581       while (n != INVALID) {
     577      while (true) {
    582578        int num = _node_num;
    583579
    584         while (num > 0 && n != INVALID) {
     580        Node n = INVALID;
     581        int level = -1;
     582
     583        while (num > 0) {
     584          n = _level->highestActive();
     585          if (n == INVALID) goto first_phase_done;
     586          level = _level->highestActiveLevel();
     587          --num;
     588         
    585589          Value excess = (*_excess)[n];
    586590          int new_level = _level->maxLevel();
     
    648652            _level->deactivate(n);
    649653          }
    650 
    651           n = _level->highestActive();
    652           level = _level->highestActiveLevel();
     654        }
     655
     656        num = _node_num * 20;
     657        while (num > 0) {
     658          while (level >= 0 && _level->activeFree(level)) {
     659            --level;
     660          }
     661          if (level == -1) {
     662            n = _level->highestActive();
     663            level = _level->highestActiveLevel();
     664            if (n == INVALID) goto first_phase_done;
     665          } else {
     666            n = _level->activeOn(level);
     667          }
    653668          --num;
    654         }
    655 
    656         num = _node_num * 20;
    657         while (num > 0 && n != INVALID) {
     669
    658670          Value excess = (*_excess)[n];
    659671          int new_level = _level->maxLevel();
     
    721733            _level->deactivate(n);
    722734          }
    723 
    724           while (level >= 0 && _level->activeFree(level)) {
    725             --level;
    726           }
    727           if (level == -1) {
    728             n = _level->highestActive();
    729             level = _level->highestActiveLevel();
    730           } else {
    731             n = _level->activeOn(level);
    732           }
    733           --num;
    734         }
    735       }
     735        }
     736      }
     737    first_phase_done:;
    736738    }
    737739
  • test/CMakeLists.txt

    r953 r1050  
    77  ${PROJECT_BINARY_DIR}/lemon
    88)
     9
     10SET(TEST_WITH_VALGRIND "NO" CACHE STRING
     11  "Run the test with valgrind (YES/NO).")
     12SET(VALGRIND_FLAGS "" CACHE STRING "Valgrind flags used by the tests.")
    913
    1014SET(TESTS
     
    3236  maps_test
    3337  matching_test
     38  max_cardinality_search_test
     39  max_clique_test
    3440  min_cost_arborescence_test
    3541  min_cost_flow_test
    3642  min_mean_cycle_test
     43  nagamochi_ibaraki_test
    3744  path_test
    3845  planarity_test
     
    4653
    4754IF(LEMON_HAVE_LP)
    48   ADD_EXECUTABLE(lp_test lp_test.cc)
     55  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     56    ADD_EXECUTABLE(lp_test lp_test.cc)
     57  ELSE()
     58    ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc)
     59  ENDIF()
     60
    4961  SET(LP_TEST_LIBS lemon)
    5062
     
    8294
    8395IF(LEMON_HAVE_MIP)
    84   ADD_EXECUTABLE(mip_test mip_test.cc)
     96  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     97    ADD_EXECUTABLE(mip_test mip_test.cc)
     98  ELSE()
     99    ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc)
     100  ENDIF()
     101
    85102  SET(MIP_TEST_LIBS lemon)
    86103
     
    118135
    119136FOREACH(TEST_NAME ${TESTS})
    120   ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
     137  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     138    ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
     139  ELSE()
     140    ADD_EXECUTABLE(${TEST_NAME} EXCLUDE_FROM_ALL ${TEST_NAME}.cc)
     141  ENDIF()
    121142  TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
    122   ADD_TEST(${TEST_NAME} ${TEST_NAME})
     143    IF(TEST_WITH_VALGRIND)
     144      ADD_TEST(${TEST_NAME}
     145        valgrind --error-exitcode=1 ${VALGRIND_FLAGS}
     146        ${CMAKE_CURRENT_BINARY_DIR}/${TEST_NAME} )
     147    ELSE()
     148      ADD_TEST(${TEST_NAME} ${TEST_NAME})
     149    ENDIF()
     150  ADD_DEPENDENCIES(check ${TEST_NAME})
    123151ENDFOREACH()
  • test/Makefile.am

    r953 r1021  
    3434        test/maps_test \
    3535        test/matching_test \
     36        test/max_cardinality_search_test \
     37        test/max_clique_test \
    3638        test/min_cost_arborescence_test \
    3739        test/min_cost_flow_test \
    3840        test/min_mean_cycle_test \
     41        test/nagamochi_ibaraki_test \
    3942        test/path_test \
    4043        test/planarity_test \
     
    8588test_mip_test_SOURCES = test/mip_test.cc
    8689test_matching_test_SOURCES = test/matching_test.cc
     90test_max_cardinality_search_test_SOURCES = test/max_cardinality_search_test.cc
     91test_max_clique_test_SOURCES = test/max_clique_test.cc
    8792test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
    8893test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
    8994test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
     95test_nagamochi_ibaraki_test_SOURCES = test/nagamochi_ibaraki_test.cc
    9096test_path_test_SOURCES = test/path_test.cc
    9197test_planarity_test_SOURCES = test/planarity_test.cc
  • test/bellman_ford_test.cc

    r956 r960  
    105105      ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
    106106      ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
    107       ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> >
    108107      ::Create bf_test(gr,length);
    109108
  • test/dfs_test.cc

    r956 r1010  
    5151  "@attributes\n"
    5252  "source 0\n"
    53   "target 5\n";
     53  "target 5\n"
     54  "source1 6\n"
     55  "target1 3\n";
     56
    5457
    5558void checkDfsCompile()
     
    180183  Digraph G;
    181184  Node s, t;
     185  Node s1, t1;
    182186
    183187  std::istringstream input(test_lgf);
     
    185189    node("source", s).
    186190    node("target", t).
     191    node("source1", s1).
     192    node("target1", t1).
    187193    run();
    188194
     
    211217
    212218  {
     219  Dfs<Digraph> dfs(G);
     220  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
     221  }
     222 
     223  {
    213224    NullMap<Node,Arc> myPredMap;
    214225    dfs(G).predMap(myPredMap).run(s);
  • test/graph_copy_test.cc

    r463 r989  
    1919#include <lemon/smart_graph.h>
    2020#include <lemon/list_graph.h>
     21#include <lemon/static_graph.h>
    2122#include <lemon/lgf_reader.h>
    2223#include <lemon/error.h>
     
    2728using namespace lemon;
    2829
     30template <typename GR>
    2931void digraph_copy_test() {
    3032  const int nn = 10;
    3133
     34  // Build a digraph
    3235  SmartDigraph from;
    3336  SmartDigraph::NodeMap<int> fnm(from);
     
    5154    }
    5255  }
    53 
    54   ListDigraph to;
    55   ListDigraph::NodeMap<int> tnm(to);
    56   ListDigraph::ArcMap<int> tam(to);
    57   ListDigraph::Node tn;
    58   ListDigraph::Arc ta;
    59 
    60   SmartDigraph::NodeMap<ListDigraph::Node> nr(from);
    61   SmartDigraph::ArcMap<ListDigraph::Arc> er(from);
    62 
    63   ListDigraph::NodeMap<SmartDigraph::Node> ncr(to);
    64   ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to);
     56 
     57  // Test digraph copy
     58  GR to;
     59  typename GR::template NodeMap<int> tnm(to);
     60  typename GR::template ArcMap<int> tam(to);
     61  typename GR::Node tn;
     62  typename GR::Arc ta;
     63
     64  SmartDigraph::NodeMap<typename GR::Node> nr(from);
     65  SmartDigraph::ArcMap<typename GR::Arc> er(from);
     66
     67  typename GR::template NodeMap<SmartDigraph::Node> ncr(to);
     68  typename GR::template ArcMap<SmartDigraph::Arc> ecr(to);
    6569
    6670  digraphCopy(from, to).
     
    6973    nodeCrossRef(ncr).arcCrossRef(ecr).
    7074    node(fn, tn).arc(fa, ta).run();
     75 
     76  check(countNodes(from) == countNodes(to), "Wrong copy.");
     77  check(countArcs(from) == countArcs(to), "Wrong copy.");
    7178
    7279  for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
     
    8289  }
    8390
    84   for (ListDigraph::NodeIt it(to); it != INVALID; ++it) {
     91  for (typename GR::NodeIt it(to); it != INVALID; ++it) {
    8592    check(nr[ncr[it]] == it, "Wrong copy.");
    8693  }
    8794
    88   for (ListDigraph::ArcIt it(to); it != INVALID; ++it) {
     95  for (typename GR::ArcIt it(to); it != INVALID; ++it) {
    8996    check(er[ecr[it]] == it, "Wrong copy.");
    9097  }
    9198  check(tn == nr[fn], "Wrong copy.");
    9299  check(ta == er[fa], "Wrong copy.");
     100
     101  // Test repeated copy
     102  digraphCopy(from, to).run();
     103 
     104  check(countNodes(from) == countNodes(to), "Wrong copy.");
     105  check(countArcs(from) == countArcs(to), "Wrong copy.");
    93106}
    94107
     108template <typename GR>
    95109void graph_copy_test() {
    96110  const int nn = 10;
    97111
     112  // Build a graph
    98113  SmartGraph from;
    99114  SmartGraph::NodeMap<int> fnm(from);
     
    123138  }
    124139
    125   ListGraph to;
    126   ListGraph::NodeMap<int> tnm(to);
    127   ListGraph::ArcMap<int> tam(to);
    128   ListGraph::EdgeMap<int> tem(to);
    129   ListGraph::Node tn;
    130   ListGraph::Arc ta;
    131   ListGraph::Edge te;
    132 
    133   SmartGraph::NodeMap<ListGraph::Node> nr(from);
    134   SmartGraph::ArcMap<ListGraph::Arc> ar(from);
    135   SmartGraph::EdgeMap<ListGraph::Edge> er(from);
    136 
    137   ListGraph::NodeMap<SmartGraph::Node> ncr(to);
    138   ListGraph::ArcMap<SmartGraph::Arc> acr(to);
    139   ListGraph::EdgeMap<SmartGraph::Edge> ecr(to);
     140  // Test graph copy
     141  GR to;
     142  typename GR::template NodeMap<int> tnm(to);
     143  typename GR::template ArcMap<int> tam(to);
     144  typename GR::template EdgeMap<int> tem(to);
     145  typename GR::Node tn;
     146  typename GR::Arc ta;
     147  typename GR::Edge te;
     148
     149  SmartGraph::NodeMap<typename GR::Node> nr(from);
     150  SmartGraph::ArcMap<typename GR::Arc> ar(from);
     151  SmartGraph::EdgeMap<typename GR::Edge> er(from);
     152
     153  typename GR::template NodeMap<SmartGraph::Node> ncr(to);
     154  typename GR::template ArcMap<SmartGraph::Arc> acr(to);
     155  typename GR::template EdgeMap<SmartGraph::Edge> ecr(to);
    140156
    141157  graphCopy(from, to).
     
    144160    nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
    145161    node(fn, tn).arc(fa, ta).edge(fe, te).run();
     162
     163  check(countNodes(from) == countNodes(to), "Wrong copy.");
     164  check(countEdges(from) == countEdges(to), "Wrong copy.");
     165  check(countArcs(from) == countArcs(to), "Wrong copy.");
    146166
    147167  for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
     
    168188  }
    169189
    170   for (ListGraph::NodeIt it(to); it != INVALID; ++it) {
     190  for (typename GR::NodeIt it(to); it != INVALID; ++it) {
    171191    check(nr[ncr[it]] == it, "Wrong copy.");
    172192  }
    173193
    174   for (ListGraph::ArcIt it(to); it != INVALID; ++it) {
     194  for (typename GR::ArcIt it(to); it != INVALID; ++it) {
    175195    check(ar[acr[it]] == it, "Wrong copy.");
    176196  }
    177   for (ListGraph::EdgeIt it(to); it != INVALID; ++it) {
     197  for (typename GR::EdgeIt it(to); it != INVALID; ++it) {
    178198    check(er[ecr[it]] == it, "Wrong copy.");
    179199  }
     
    181201  check(ta == ar[fa], "Wrong copy.");
    182202  check(te == er[fe], "Wrong copy.");
     203
     204  // Test repeated copy
     205  graphCopy(from, to).run();
     206 
     207  check(countNodes(from) == countNodes(to), "Wrong copy.");
     208  check(countEdges(from) == countEdges(to), "Wrong copy.");
     209  check(countArcs(from) == countArcs(to), "Wrong copy.");
    183210}
    184211
    185212
    186213int main() {
    187   digraph_copy_test();
    188   graph_copy_test();
     214  digraph_copy_test<SmartDigraph>();
     215  digraph_copy_test<ListDigraph>();
     216  digraph_copy_test<StaticDigraph>();
     217  graph_copy_test<SmartGraph>();
     218  graph_copy_test<ListGraph>();
    189219
    190220  return 0;
  • test/preflow_test.cc

    r956 r1029  
    157157}
    158158
     159void initFlowTest()
     160{
     161  DIGRAPH_TYPEDEFS(SmartDigraph);
     162 
     163  SmartDigraph g;
     164  SmartDigraph::ArcMap<int> cap(g),iflow(g);
     165  Node s=g.addNode(); Node t=g.addNode();
     166  Node n1=g.addNode(); Node n2=g.addNode();
     167  Arc a;
     168  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
     169  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
     170  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
     171
     172  Preflow<SmartDigraph> pre(g,cap,s,t);
     173  pre.init(iflow);
     174  pre.startFirstPhase();
     175  check(pre.flowValue() == 10, "The incorrect max flow value.");
     176  check(pre.minCut(s), "Wrong min cut (Node s).");
     177  check(pre.minCut(n1), "Wrong min cut (Node n1).");
     178  check(!pre.minCut(n2), "Wrong min cut (Node n2).");
     179  check(!pre.minCut(t), "Wrong min cut (Node t).");
     180}
     181
     182
    159183int main() {
    160184
     
    247271        "The max flow value or the three min cut values are incorrect.");
    248272
     273  initFlowTest();
     274 
    249275  return 0;
    250276}
Note: See TracChangeset for help on using the changeset viewer.