COIN-OR::LEMON - Graph Library

Changes in / [931:f112c18bc304:932:773dd96ecdd8] in lemon-main


Ignore:
Files:
9 added
1 deleted
36 edited

Legend:

Unmodified
Added
Removed
  • CMakeLists.txt

    r744 r930  
    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 -ansi -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

    r553 r879  
    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

    r665 r881  
     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

    r793 r930  
    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

    r865 r930  
    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

    r756 r930  
    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 r928  
    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

    r440 r919  
    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

    r440 r925  
    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

    r877 r919  
    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

    r755 r904  
    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

    r679 r908  
    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

    r874 r917  
    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

    r877 r879  
    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

    r877 r880  
    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

    r877 r884  
    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

    r617 r882  
    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

    r529 r887  
    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/capacity_scaling.h

    r877 r922  
    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

    r877 r919  
    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

    r931 r932  
    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()
     
    448452    ///
    449453    /// 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
     454    /// with a map in which \c k is assigned to \c s, \c -k is
    451455    /// assigned to \c t and all other nodes have zero supply value.
    452456    ///
  • lemon/cycle_canceling.h

    r877 r922  
    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

    r877 r907  
    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

    r877 r919  
    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

    r877 r915  
    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

    r877 r879  
    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

    r584 r921  
    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

    r877 r922  
    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

    r877 r920  
    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

    r877 r924  
    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

    r874 r930  
    3232  maps_test
    3333  matching_test
     34  max_cardinality_search_test
     35  max_clique_test
    3436  min_cost_arborescence_test
    3537  min_cost_flow_test
    3638  min_mean_cycle_test
     39  nagamochi_ibaraki_test
    3740  path_test
    3841  planarity_test
     
    4649
    4750IF(LEMON_HAVE_LP)
    48   ADD_EXECUTABLE(lp_test lp_test.cc)
     51  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     52    ADD_EXECUTABLE(lp_test lp_test.cc)
     53  ELSE()
     54    ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc)
     55  ENDIF()
     56
    4957  SET(LP_TEST_LIBS lemon)
    5058
     
    8290
    8391IF(LEMON_HAVE_MIP)
    84   ADD_EXECUTABLE(mip_test mip_test.cc)
     92  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     93    ADD_EXECUTABLE(mip_test mip_test.cc)
     94  ELSE()
     95    ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc)
     96  ENDIF()
     97
    8598  SET(MIP_TEST_LIBS lemon)
    8699
     
    118131
    119132FOREACH(TEST_NAME ${TESTS})
    120   ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
     133  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     134    ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
     135  ELSE()
     136    ADD_EXECUTABLE(${TEST_NAME} EXCLUDE_FROM_ALL ${TEST_NAME}.cc)
     137  ENDIF()
    121138  TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
    122139  ADD_TEST(${TEST_NAME} ${TEST_NAME})
     140  ADD_DEPENDENCIES(check ${TEST_NAME})
    123141ENDFOREACH()
  • test/Makefile.am

    r874 r917  
    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

    r877 r880  
    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

    r877 r907  
    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

    r440 r894  
    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

    r877 r924  
    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.