Changes in / [1057:633956ca9421:1059:4f9e5801224e] in lemon
- Files:
-
- 9 added
- 1 deleted
- 37 edited
Legend:
- Unmodified
- Added
- Removed
-
CMakeLists.txt
r791 r1056 3 3 SET(PROJECT_NAME "LEMON") 4 4 PROJECT(${PROJECT_NAME}) 5 6 INCLUDE(FindPythonInterp) 7 INCLUDE(FindWget) 5 8 6 9 IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake) … … 10 13 ELSE() 11 14 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( 12 22 COMMAND hg id -i 13 23 WORKING_DIRECTORY ${PROJECT_SOURCE_DIR} … … 17 27 ) 18 28 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() 20 36 ENDIF() 21 SET(LEMON_VERSION ${HG_REVISION } CACHE STRING "LEMON version string.")37 SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.") 22 38 ENDIF() 23 39 … … 32 48 FIND_PACKAGE(COIN) 33 49 50 IF(DEFINED ENV{LEMON_CXX_WARNING}) 51 SET(CXX_WARNING $ENV{LEMON_CXX_WARNING}) 52 ELSE() 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() 71 ENDIF() 72 SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.") 73 74 SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}") 75 76 SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb" CACHE STRING 77 "Flags used by the C++ compiler during maintainer builds." 78 FORCE ) 79 SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING 80 "Flags used by the C compiler during maintainer builds." 81 FORCE ) 82 SET( 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 ) 86 SET( 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 ) 90 MARK_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 96 IF(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 104 IF(NOT CMAKE_BUILD_TYPE) 105 SET(CMAKE_BUILD_TYPE "Release") 106 ENDIF() 107 108 SET( 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 34 113 INCLUDE(CheckTypeSize) 35 114 CHECK_TYPE_SIZE("long long" LONG_LONG) 36 115 SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG}) 37 116 38 INCLUDE(FindPythonInterp)39 40 117 ENABLE_TESTING() 118 119 IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer") 120 ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND}) 121 ELSE() 122 ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND}) 123 ENDIF() 41 124 42 125 ADD_SUBDIRECTORY(lemon) 43 126 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR}) 127 ADD_SUBDIRECTORY(contrib) 44 128 ADD_SUBDIRECTORY(demo) 45 129 ADD_SUBDIRECTORY(tools) … … 65 149 ENDIF() 66 150 67 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)151 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR}) 68 152 SET(CPACK_PACKAGE_NAME ${PROJECT_NAME}) 69 153 SET(CPACK_PACKAGE_VENDOR "EGRES") -
LICENSE
r600 r959 2 2 copyright/license. 3 3 4 Copyright (C) 2003-20 09Egervary Jeno Kombinatorikus Optimalizalasi4 Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi 5 5 Kutatocsoport (Egervary Combinatorial Optimization Research Group, 6 6 EGRES). -
NEWS
r712 r962 1 2010-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 1 81 2009-05-13 Version 1.1 released 2 82 … … 73 153 ----: Add missing unistd.h include to time_measure.h 74 154 #204: Compilation bug fixed in graph_to_eps.h with VS2005 75 #214,#215: windows.h should never be included by lemonheaders155 #214,#215: windows.h should never be included by LEMON headers 76 156 #230: Build systems check the availability of 'long long' type 77 157 #229: Default implementation of Tolerance<> is used for integer types … … 95 175 2008-10-13 Version 1.0 released 96 176 97 98 99 100 101 102 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 103 183 Migration Guide in the doc for more details) 104 184 * Graph -> Digraph, UGraph -> Graph 105 185 * Edge -> Arc, UEdge -> Edge 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 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) 124 204 * Concepts 125 205 * graph structure concepts (concepts/digraph.h, concepts/graph.h, 126 206 concepts/graph_components.h) 127 128 129 130 131 132 133 134 135 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 136 216 (lgf_reader.h, lgf_writer.h) 137 217 * tools to handle the anomalies of calculations with 138 218 floating point numbers (tolerance.h) 139 219 * tools to manage RGB colors (color.h) 140 141 142 143 144 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 115 115 dnl Add dependencies on files generated by configure. 116 116 AC_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']) 118 118 119 119 AC_CONFIG_FILES([ … … 122 122 cmake/version.cmake 123 123 doc/Doxyfile 124 doc/mainpage.dox 124 125 lemon/lemon.pc 125 126 ]) -
doc/CMakeLists.txt
r943 r1040 4 4 SET(abs_top_builddir ${PROJECT_BINARY_DIR}) 5 5 6 SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).") 7 6 8 CONFIGURE_FILE( 7 9 ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in 8 10 ${PROJECT_BINARY_DIR}/doc/Doxyfile 11 @ONLY 12 ) 13 14 CONFIGURE_FILE( 15 ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in 16 ${PROJECT_BINARY_DIR}/doc/mainpage.dox 9 17 @ONLY 10 18 ) … … 53 61 54 62 ENDIF() 63 64 IF(WGET_FOUND) 65 ADD_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 ) 74 ENDIF() -
doc/Doxyfile.in
r803 r1040 1 # Doxyfile 1. 5.91 # Doxyfile 1.7.3 2 2 3 3 #--------------------------------------------------------------------------- … … 5 5 #--------------------------------------------------------------------------- 6 6 DOXYFILE_ENCODING = UTF-8 7 PROJECT_NAME = @PACKAGE_NAME@ 8 PROJECT_NUMBER = @PACKAGE_VERSION@ 7 PROJECT_NAME = 8 PROJECT_NUMBER = 9 PROJECT_BRIEF = 10 PROJECT_LOGO = 9 11 OUTPUT_DIRECTORY = 10 12 CREATE_SUBDIRS = NO … … 30 32 OPTIMIZE_FOR_FORTRAN = NO 31 33 OPTIMIZE_OUTPUT_VHDL = NO 34 EXTENSION_MAPPING = 32 35 BUILTIN_STL_SUPPORT = YES 33 36 CPP_CLI_SUPPORT = NO … … 55 58 HIDE_SCOPE_NAMES = YES 56 59 SHOW_INCLUDE_FILES = YES 60 FORCE_LOCAL_INCLUDES = NO 57 61 INLINE_INFO = YES 58 62 SORT_MEMBER_DOCS = NO 59 63 SORT_BRIEF_DOCS = NO 64 SORT_MEMBERS_CTORS_1ST = NO 60 65 SORT_GROUP_NAMES = NO 61 66 SORT_BY_SCOPE_NAME = NO 67 STRICT_PROTO_MATCHING = NO 62 68 GENERATE_TODOLIST = YES 63 69 GENERATE_TESTLIST = YES … … 71 77 SHOW_NAMESPACES = YES 72 78 FILE_VERSION_FILTER = 73 LAYOUT_FILE = DoxygenLayout.xml79 LAYOUT_FILE = "@abs_top_srcdir@/doc/DoxygenLayout.xml" 74 80 #--------------------------------------------------------------------------- 75 81 # configuration options related to warning and progress messages … … 90 96 "@abs_top_srcdir@/lemon/concepts" \ 91 97 "@abs_top_srcdir@/demo" \ 98 "@abs_top_srcdir@/contrib" \ 92 99 "@abs_top_srcdir@/tools" \ 93 100 "@abs_top_srcdir@/test/test_tools.h" \ 101 "@abs_top_builddir@/doc/mainpage.dox" \ 94 102 "@abs_top_builddir@/doc/references.dox" 95 103 INPUT_ENCODING = UTF-8 … … 112 120 FILTER_PATTERNS = 113 121 FILTER_SOURCE_FILES = NO 122 FILTER_SOURCE_PATTERNS = 114 123 #--------------------------------------------------------------------------- 115 124 # configuration options related to source browsing 116 125 #--------------------------------------------------------------------------- 117 SOURCE_BROWSER = NO126 SOURCE_BROWSER = @LEMON_DOC_SOURCE_BROWSER@ 118 127 INLINE_SOURCES = NO 119 128 STRIP_CODE_COMMENTS = YES … … 138 147 HTML_FOOTER = 139 148 HTML_STYLESHEET = 149 HTML_COLORSTYLE_HUE = 220 150 HTML_COLORSTYLE_SAT = 100 151 HTML_COLORSTYLE_GAMMA = 80 152 HTML_TIMESTAMP = YES 140 153 HTML_ALIGN_MEMBERS = YES 141 HTML_DYNAMIC_SECTIONS = NO154 HTML_DYNAMIC_SECTIONS = YES 142 155 GENERATE_DOCSET = NO 143 156 DOCSET_FEEDNAME = "Doxygen generated docs" 144 157 DOCSET_BUNDLE_ID = org.doxygen.Project 158 DOCSET_PUBLISHER_ID = org.doxygen.Publisher 159 DOCSET_PUBLISHER_NAME = Publisher 145 160 GENERATE_HTMLHELP = NO 146 161 CHM_FILE = … … 154 169 QHP_NAMESPACE = org.doxygen.Project 155 170 QHP_VIRTUAL_FOLDER = doc 171 QHP_CUST_FILTER_NAME = 172 QHP_CUST_FILTER_ATTRS = 173 QHP_SECT_FILTER_ATTRS = 156 174 QHG_LOCATION = 175 GENERATE_ECLIPSEHELP = NO 176 ECLIPSE_DOC_ID = org.doxygen.Project 157 177 DISABLE_INDEX = NO 158 178 ENUM_VALUES_PER_LINE = 4 159 179 GENERATE_TREEVIEW = NO 180 USE_INLINE_TREES = NO 160 181 TREEVIEW_WIDTH = 250 182 EXT_LINKS_IN_WINDOW = NO 161 183 FORMULA_FONTSIZE = 10 184 FORMULA_TRANSPARENT = YES 185 USE_MATHJAX = NO 186 MATHJAX_RELPATH = http://www.mathjax.org/mathjax 187 SEARCHENGINE = YES 188 SERVER_BASED_SEARCH = NO 162 189 #--------------------------------------------------------------------------- 163 190 # configuration options related to the LaTeX output … … 176 203 LATEX_BATCHMODE = NO 177 204 LATEX_HIDE_INDICES = NO 205 LATEX_SOURCE_CODE = NO 178 206 #--------------------------------------------------------------------------- 179 207 # configuration options related to the RTF output … … 224 252 SKIP_FUNCTION_MACROS = YES 225 253 #--------------------------------------------------------------------------- 226 # Options related to the search engine227 #--------------------------------------------------------------------------- 228 TAGFILES = "@abs_top_ srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ "254 # Configuration::additions related to external references 255 #--------------------------------------------------------------------------- 256 TAGFILES = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ " 229 257 GENERATE_TAGFILE = html/lemon.tag 230 258 ALLEXTERNALS = NO … … 238 266 HIDE_UNDOC_RELATIONS = YES 239 267 HAVE_DOT = YES 268 DOT_NUM_THREADS = 0 240 269 DOT_FONTNAME = FreeSans 241 270 DOT_FONTSIZE = 10 … … 255 284 DOT_PATH = 256 285 DOTFILE_DIRS = 286 MSCFILE_DIRS = 257 287 DOT_GRAPH_MAX_NODES = 50 258 288 MAX_DOT_GRAPH_DEPTH = 0 … … 261 291 GENERATE_LEGEND = YES 262 292 DOT_CLEANUP = YES 263 #---------------------------------------------------------------------------264 # Configuration::additions related to the search engine265 #---------------------------------------------------------------------------266 SEARCHENGINE = NO -
doc/DoxygenLayout.xml
r316 r1036 3 3 <navindex> 4 4 <tab type="mainpage" visible="yes" title=""/> 5 <tab type="modules" visible="yes" title="" />5 <tab type="modules" visible="yes" title="" intro=""/> 6 6 <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=""/> 11 11 </tab> 12 12 <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=""/> 15 15 </tab> 16 16 <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=""/> 19 19 </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=""/> 23 23 </navindex> 24 24 -
doc/coding_style.dox
r463 r1023 99 99 \subsection pri-loc-var Private member variables 100 100 101 Private member variables should start with underscore 101 Private member variables should start with underscore. 102 102 103 103 \code 104 _start_with_underscore s104 _start_with_underscore 105 105 \endcode 106 106 -
doc/dirs.dox
r463 r1031 32 32 documentation. 33 33 */ 34 35 /** 36 \dir contrib 37 \brief Directory for user contributed source codes. 38 39 You can place your own C++ code using LEMON into this directory, which 40 will compile to an executable along with LEMON when you build the 41 library. This is probably the easiest way of compiling short to medium 42 codes, for this does require neither a LEMON installed system-wide nor 43 adding several paths to the compiler. 44 45 Please have a look at <tt>contrib/CMakeLists.txt</tt> for 46 instruction on how to add your own files into the build process. */ 34 47 35 48 /** -
doc/groups.dox
r956 r1023 264 264 265 265 /** 266 @defgroup matrices Matrices267 @ingroup datas268 \brief Two dimensional data storages implemented in LEMON.269 270 This group contains two dimensional data storages implemented in LEMON.271 */272 273 /**274 266 @defgroup auxdat Auxiliary Data Structures 275 267 @ingroup datas … … 415 407 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. 416 408 417 In general NetworkSimplex is the most efficient implementation,418 but in special cases other algorithms could be faster.409 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient 410 implementations, but the other two algorithms could be faster in special cases. 419 411 For 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). 421 413 */ 422 414 … … 473 465 474 466 LEMON 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, 476 468 \ref dasdan98minmeancycle. 477 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved469 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved 478 470 version of Karp's algorithm \ref dasdan98minmeancycle. 479 - \ref Howard "Howard"'s policy iteration algorithm471 - \ref HowardMmc Howard's policy iteration algorithm 480 472 \ref dasdan98minmeancycle. 481 473 482 In practice, the Howard algorithm proved to be by far the most efficient483 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 space486 O(n<sup>2</sup>+e), but the latter one is typically faster due to the 487 applied early termination scheme.474 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the 475 most efficient one, though the best known theoretical bound on its running 476 time is exponential. 477 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms 478 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is 479 typically faster due to the applied early termination scheme. 488 480 */ 489 481 … … 548 540 549 541 /** 550 @defgroup planar Planar ityEmbedding and Drawing542 @defgroup planar Planar Embedding and Drawing 551 543 @ingroup algs 552 544 \brief Algorithms for planarity checking, embedding and drawing … … 560 552 561 553 /** 562 @defgroup approx Approximation Algorithms554 @defgroup approx_algs Approximation Algorithms 563 555 @ingroup algs 564 556 \brief Approximation algorithms. … … 566 558 This group contains the approximation and heuristic algorithms 567 559 implemented in LEMON. 560 561 <b>Maximum Clique Problem</b> 562 - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of 563 Grosso, Locatelli, and Pullan. 568 564 */ 569 565 -
doc/references.bib
r802 r999 298 298 address = {Dublin, Ireland}, 299 299 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 7 7 ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake 8 8 ${CMAKE_CURRENT_BINARY_DIR}/config.h 9 ) 10 11 CONFIGURE_FILE( 12 ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake 13 ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc 14 @ONLY 9 15 ) 10 16 … … 67 73 COMPONENT headers 68 74 ) 75 76 INSTALL( 77 FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc 78 DESTINATION lib/pkgconfig 79 ) 80 -
lemon/Makefile.am
r953 r1021 91 91 lemon/graph_to_eps.h \ 92 92 lemon/grid_graph.h \ 93 lemon/grosso_locatelli_pullan_mc.h \ 93 94 lemon/hartmann_orlin_mmc.h \ 94 95 lemon/howard_mmc.h \ … … 107 108 lemon/math.h \ 108 109 lemon/min_cost_arborescence.h \ 110 lemon/max_cardinality_search.h \ 111 lemon/nagamochi_ibaraki.h \ 109 112 lemon/nauty_reader.h \ 110 113 lemon/network_simplex.h \ -
lemon/arg_parser.h
r956 r959 36 36 37 37 ///Exception used by ArgParser 38 39 ///Exception used by ArgParser. 40 /// 38 41 class ArgParserException : public Exception { 39 42 public: 43 /// Reasons for failure 44 45 /// Reasons for failure. 46 /// 40 47 enum Reason { 41 HELP, /// <tt>--help</tt> option was given42 UNKNOWN_OPT, /// Unknown option was given43 INVALID_OPT /// Invalid combination of options48 HELP, ///< <tt>--help</tt> option was given. 49 UNKNOWN_OPT, ///< Unknown option was given. 50 INVALID_OPT ///< Invalid combination of options. 44 51 }; 45 52 -
lemon/bellman_ford.h
r956 r960 29 29 #include <lemon/error.h> 30 30 #include <lemon/maps.h> 31 #include <lemon/tolerance.h>32 31 #include <lemon/path.h> 33 32 … … 36 35 namespace lemon { 37 36 38 /// \brief Default operation traits for the BellmanFord algorithm class.37 /// \brief Default OperationTraits for the BellmanFord algorithm class. 39 38 /// 40 39 /// This operation traits class defines all computational operations … … 43 42 /// If the numeric type does not have infinity value, then the maximum 44 43 /// value is used as extremal infinity value. 45 ///46 /// \see BellmanFordToleranceOperationTraits47 44 template < 48 45 typename V, 49 46 bool has_inf = std::numeric_limits<V>::has_infinity> 50 47 struct BellmanFordDefaultOperationTraits { 51 /// \ brief Value type for the algorithm.48 /// \e 52 49 typedef V Value; 53 50 /// \brief Gives back the zero value of the type. … … 85 82 static bool less(const Value& left, const Value& right) { 86 83 return left < right; 87 }88 };89 90 /// \brief Operation traits for the BellmanFord algorithm class91 /// using tolerance.92 ///93 /// This operation traits class defines all computational operations94 /// and constants that are used in the Bellman-Ford algorithm.95 /// The only difference between this implementation and96 /// \ref BellmanFordDefaultOperationTraits is that this class uses97 /// 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 Tolerance103 /// "Tolerance<V>".104 ///105 /// \see BellmanFordDefaultOperationTraits106 #ifdef DOXYGEN107 template <typename V, V eps>108 #else109 template <110 typename V,111 V eps = Tolerance<V>::def_epsilon>112 #endif113 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 than129 /// the second.130 static bool less(const Value& left, const Value& right) {131 return left + eps < right;132 84 } 133 85 }; … … 156 108 /// It defines the used operations and the infinity value for the 157 109 /// given \c Value type. 158 /// \see BellmanFordDefaultOperationTraits, 159 /// BellmanFordToleranceOperationTraits 110 /// \see BellmanFordDefaultOperationTraits 160 111 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 161 112 … … 887 838 /// It defines the used operations and the infinity value for the 888 839 /// given \c Value type. 889 /// \see BellmanFordDefaultOperationTraits, 890 /// BellmanFordToleranceOperationTraits 840 /// \see BellmanFordDefaultOperationTraits 891 841 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 892 842 -
lemon/bits/edge_set_extender.h
r956 r968 281 281 typedef EdgeSetExtender Graph; 282 282 283 typedef True UndirectedTag; 284 283 285 typedef typename Parent::Node Node; 284 286 typedef typename Parent::Arc Arc; -
lemon/bits/graph_adaptor_extender.h
r664 r965 182 182 typedef GraphAdaptorExtender Adaptor; 183 183 184 typedef True UndirectedTag; 185 184 186 typedef typename Parent::Node Node; 185 187 typedef typename Parent::Arc Arc; -
lemon/bits/path_dump.h
r576 r973 50 50 51 51 bool empty() const { 52 return predMap[target] != INVALID;52 return predMap[target] == INVALID; 53 53 } 54 54 … … 124 124 125 125 bool empty() const { 126 return source != target;126 return predMatrixMap(source, target) == INVALID; 127 127 } 128 128 -
lemon/bits/windows.cc
r956 r1055 41 41 #include <unistd.h> 42 42 #include <ctime> 43 #ifndef WIN32 43 44 #include <sys/times.h> 45 #endif 44 46 #include <sys/time.h> 45 47 #endif -
lemon/capacity_scaling.h
r956 r1026 87 87 /// consider to use the named template parameters instead. 88 88 /// 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 90 91 /// be integer. 91 /// \warning This algorithm does not support negative costs for such92 /// arcs that haveinfinite upper bound.92 /// \warning This algorithm does not support negative costs for 93 /// arcs having infinite upper bound. 93 94 #ifdef DOXYGEN 94 95 template <typename GR, typename V, typename C, typename TR> … … 423 424 /// 424 425 /// Using this function has the same effect as using \ref supplyMap() 425 /// with sucha map in which \c k is assigned to \c s, \c -k is426 /// with a map in which \c k is assigned to \c s, \c -k is 426 427 /// assigned to \c t and all other nodes have zero supply value. 427 428 /// -
lemon/core.h
r956 r1023 395 395 static void copy(const From& from, Digraph &to, 396 396 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { 397 to.clear(); 397 398 for (typename From::NodeIt it(from); it != INVALID; ++it) { 398 399 nodeRefMap[it] = to.addNode(); … … 422 423 static void copy(const From& from, Graph &to, 423 424 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 425 to.clear(); 424 426 for (typename From::NodeIt it(from); it != INVALID; ++it) { 425 427 nodeRefMap[it] = to.addNode(); … … 445 447 446 448 } 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 447 468 448 469 /// \brief Class to copy a digraph. -
lemon/cost_scaling.h
r1041 r1049 98 98 /// "preflow push-relabel" algorithm for the maximum flow problem. 99 99 /// 100 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest 101 /// implementations available in LEMON for this problem. 102 /// 100 103 /// Most of the parameters of the problem (except for the digraph) 101 104 /// can be given using separate functions, and the algorithm can be … … 114 117 /// consider to use the named template parameters instead. 115 118 /// 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 117 121 /// be integer. 118 /// \warning This algorithm does not support negative costs for such119 /// arcs that haveinfinite upper bound.122 /// \warning This algorithm does not support negative costs for 123 /// arcs having infinite upper bound. 120 124 /// 121 125 /// \note %CostScaling provides three different internal methods, … … 179 183 /// relabel operation. 180 184 /// By default, the so called \ref PARTIAL_AUGMENT 181 /// "Partial Augment-Relabel" method is used, which provedto be185 /// "Partial Augment-Relabel" method is used, which turned out to be 182 186 /// the most efficient and the most robust on various test inputs. 183 187 /// However, the other methods can be selected using the \ref run() … … 234 238 }; 235 239 236 typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;237 240 typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap; 238 241 … … 285 288 int _max_rank; 286 289 287 // Data for a StaticDigraph structure288 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 295 290 public: 296 291 … … 339 334 CostScaling(const GR& graph) : 340 335 _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph), 341 _cost_map(_cost_vec), _pi_map(_pi),342 336 INF(std::numeric_limits<Value>::has_infinity ? 343 337 std::numeric_limits<Value>::infinity() : … … 448 442 /// 449 443 /// Using this function has the same effect as using \ref supplyMap() 450 /// with sucha map in which \c k is assigned to \c s, \c -k is444 /// with a map in which \c k is assigned to \c s, \c -k is 451 445 /// assigned to \c t and all other nodes have zero supply value. 452 446 /// … … 494 488 /// \param method The internal method that will be used in the 495 489 /// 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. 497 491 /// 498 492 /// \return \c INFEASIBLE if no feasible flow exists, … … 508 502 /// \see ProblemType, Method 509 503 /// \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"); 511 506 _alpha = factor; 512 507 ProblemType pt = init(); … … 572 567 } 573 568 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 /// 585 585 /// \return <tt>(*this)</tt> 586 /// 587 /// \see resetParams(), run() 586 588 CostScaling& reset() { 587 589 // Resize vectors … … 608 610 _excess.resize(_res_node_num); 609 611 _next_out.resize(_res_node_num); 610 611 _arc_vec.reserve(_res_arc_num);612 _cost_vec.reserve(_res_arc_num);613 612 614 613 // Copy the graph … … 887 886 } 888 887 889 return OPTIMAL;890 }891 892 // Execute the algorithm and transform the results893 void start(Method method) {894 // Maximum path length for partial augment895 const int MAX_PATH_LENGTH = 4;896 897 888 // Initialize data structures for buckets 898 889 _max_rank = _alpha * _res_node_num; … … 902 893 _rank.resize(_res_node_num + 1); 903 894 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 905 902 switch (method) { 906 903 case PUSH: … … 911 908 break; 912 909 case PARTIAL_AUGMENT: 913 startAugment(MAX_PA TH_LENGTH);910 startAugment(MAX_PARTIAL_PATH_LENGTH); 914 911 break; 915 912 } 916 913 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 } 933 971 934 972 // Handle non-zero lower bounds … … 948 986 LargeCost pi_u = _pi[u]; 949 987 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 } 957 997 } 958 998 } … … 970 1010 } 971 1011 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); 996 1235 } 997 1236 998 1237 // Global potential update heuristic 999 1238 void globalUpdate() { 1000 int bucket_end = _root + 1;1239 const int bucket_end = _root + 1; 1001 1240 1002 1241 // Initialize buckets … … 1005 1244 } 1006 1245 Value total_excess = 0; 1246 int b0 = bucket_end; 1007 1247 for (int i = 0; i != _res_node_num; ++i) { 1008 1248 if (_excess[i] < 0) { 1009 1249 _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; 1013 1253 } else { 1014 1254 total_excess += _excess[i]; … … 1017 1257 } 1018 1258 if (total_excess == 0) return; 1259 _buckets[0] = b0; 1019 1260 1020 1261 // Search the buckets … … 1038 1279 LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon; 1039 1280 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 } 1042 1284 1043 1285 // Change the rank of v … … 1051 1293 _buckets[old_rank_v] = _bucket_next[v]; 1052 1294 } 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; 1055 1298 } 1056 1299 } 1057 1300 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; 1061 1305 _buckets[new_rank_v] = v; 1062 1306 } … … 1087 1331 void startAugment(int max_length) { 1088 1332 // 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 * 1093 1336 (_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); 1096 1342 int relabel_cnt = 0; 1097 1098 // Perform cost scaling phases 1099 std::vector<int> path; 1343 int eps_phase_cnt = 0; 1100 1344 for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ? 1101 1345 1 : _epsilon / _alpha ) 1102 1346 { 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; 1106 1352 } 1107 1353 … … 1120 1366 1121 1367 // Find an augmenting path from the start node 1122 path.clear();1123 1368 int tip = start; 1124 while ( _excess[tip] >= 0 && int(path.size()) < max_length) {1369 while (int(path.size()) < max_length && _excess[tip] >= 0) { 1125 1370 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]; 1127 1373 int last_out = _first_out[tip+1]; 1128 1374 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 } 1135 1391 } 1136 1392 } 1137 1393 1138 1394 // Relabel tip node 1139 min_red_cost = std::numeric_limits<LargeCost>::max();1140 1395 if (tip != start) { 1141 1396 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]]); 1143 1399 } 1400 last_out = _next_out[tip]; 1144 1401 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 } 1148 1407 } 1149 1408 } … … 1154 1413 // Step back 1155 1414 if (tip != start) { 1156 tip = _source[path.back()]; 1415 int pa = path.back(); 1416 path_arc[pa] = false; 1417 tip = _source[pa]; 1157 1418 path.pop_back(); 1158 1419 } … … 1162 1423 1163 1424 // Augment along the found path (as much flow as possible) 1425 augment: 1164 1426 Value delta; 1165 1427 int pa, u, v = start; … … 1168 1430 u = v; 1169 1431 v = _target[pa]; 1432 path_arc[pa] = false; 1170 1433 delta = std::min(_res_cap[pa], _excess[u]); 1171 1434 _res_cap[pa] -= delta; … … 1173 1436 _excess[u] -= delta; 1174 1437 _excess[v] += delta; 1175 if (_excess[v] > 0 && _excess[v] <= delta) 1438 if (_excess[v] > 0 && _excess[v] <= delta) { 1176 1439 _active_nodes.push_back(v); 1177 } 1440 } 1441 } 1442 path.clear(); 1178 1443 1179 1444 // Global update heuristic 1180 if (relabel_cnt >= next_ update_limit) {1445 if (relabel_cnt >= next_global_update_limit) { 1181 1446 globalUpdate(); 1182 next_update_limit += global_update_freq; 1183 } 1184 } 1185 } 1447 next_global_update_limit += global_update_skip; 1448 } 1449 } 1450 1451 } 1452 1186 1453 } 1187 1454 … … 1189 1456 void startPush() { 1190 1457 // Paramters for heuristics 1191 const int EARLY_TERM_EPSILON_LIMIT = 1000;1458 const int PRICE_REFINEMENT_LIMIT = 2; 1192 1459 const double GLOBAL_UPDATE_FACTOR = 2.0; 1193 1460 1194 const int global_update_ freq = int(GLOBAL_UPDATE_FACTOR *1461 const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR * 1195 1462 (_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; 1199 1464 1200 1465 // Perform cost scaling phases 1201 1466 BoolVector hyper(_res_node_num, false); 1202 1467 LargeCostVector hyper_cost(_res_node_num); 1468 int relabel_cnt = 0; 1469 int eps_phase_cnt = 0; 1203 1470 for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ? 1204 1471 1 : _epsilon / _alpha ) 1205 1472 { 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; 1209 1478 } 1210 1479 … … 1278 1547 std::numeric_limits<LargeCost>::max(); 1279 1548 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 } 1283 1554 } 1284 1555 } … … 1298 1569 1299 1570 // Global update heuristic 1300 if (relabel_cnt >= next_ update_limit) {1571 if (relabel_cnt >= next_global_update_limit) { 1301 1572 globalUpdate(); 1302 1573 for (int u = 0; u != _res_node_num; ++u) 1303 1574 hyper[u] = false; 1304 next_ update_limit += global_update_freq;1575 next_global_update_limit += global_update_skip; 1305 1576 } 1306 1577 } -
lemon/cycle_canceling.h
r956 r1026 66 66 /// algorithm. By default, it is the same as \c V. 67 67 /// 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 69 70 /// be integer. 70 /// \warning This algorithm does not support negative costs for such71 /// arcs that haveinfinite upper bound.71 /// \warning This algorithm does not support negative costs for 72 /// arcs having infinite upper bound. 72 73 /// 73 74 /// \note For more information about the three available methods, … … 117 118 /// \ref CycleCanceling provides three different cycle-canceling 118 119 /// 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. 121 121 /// However, the other methods can be selected using the \ref run() 122 122 /// function with the proper parameter. … … 350 350 /// 351 351 /// Using this function has the same effect as using \ref supplyMap() 352 /// with sucha map in which \c k is assigned to \c s, \c -k is352 /// with a map in which \c k is assigned to \c s, \c -k is 353 353 /// assigned to \c t and all other nodes have zero supply value. 354 354 /// -
lemon/dfs.h
r956 r1010 566 566 void start(Node t) 567 567 { 568 while ( !emptyQueue() && G->target(_stack[_stack_head])!=t)568 while ( !emptyQueue() && !(*_reached)[t] ) 569 569 processNextArc(); 570 570 } … … 1513 1513 /// with addSource() before using this function. 1514 1514 void start(Node t) { 1515 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t)1515 while ( !emptyQueue() && !(*_reached)[t] ) 1516 1516 processNextArc(); 1517 1517 } -
lemon/euler.h
r956 r1023 37 37 ///Euler tour iterator for digraphs. 38 38 39 /// \ingroup graph_prop 39 /// \ingroup graph_properties 40 40 ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed 41 41 ///graph (if there exists) and it converts to the \c Arc type of the digraph. -
lemon/hao_orlin.h
r956 r1019 54 54 /// preflow push-relabel algorithm. Our implementation calculates 55 55 /// 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. The57 /// 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. 58 58 /// 59 59 /// For an undirected graph you can run just the first phase of the … … 913 913 /// source-side (i.e. a set \f$ X\subsetneq V \f$ with 914 914 /// \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. 915 917 /// 916 918 /// \pre \ref init() must be called before using this function. … … 925 927 /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with 926 928 /// \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. 927 931 /// 928 932 /// \pre \ref init() must be called before using this function. … … 934 938 /// \brief Run the algorithm. 935 939 /// 936 /// This function runs the algorithm. It finds nodes \c source and937 /// \c target arbitrarily andthen calls \ref init(), \ref calculateOut()940 /// This function runs the algorithm. It chooses source node, 941 /// then calls \ref init(), \ref calculateOut() 938 942 /// and \ref calculateIn(). 939 943 void run() { … … 945 949 /// \brief Run the algorithm. 946 950 /// 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. 950 954 void run(const Node& s) { 951 955 init(s); … … 966 970 /// \brief Return the value of the minimum cut. 967 971 /// 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(). 969 975 /// 970 976 /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() … … 977 983 /// \brief Return a minimum cut. 978 984 /// 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 982 992 /// for the nodes of \f$ X \f$). 983 993 /// -
lemon/hartmann_orlin_mmc.h
r956 r959 39 39 /// \tparam GR The type of the digraph. 40 40 /// \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. 42 42 #ifdef DOXYGEN 43 43 template <typename GR, typename CM> … … 100 100 /// a directed cycle of minimum mean cost in a digraph 101 101 /// \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, 103 103 /// it applies an efficient early termination scheme. 104 104 /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e). -
lemon/kruskal.h
r631 r1025 31 31 ///\file 32 32 ///\brief Kruskal's algorithm to compute a minimum cost spanning tree 33 ///34 ///Kruskal's algorithm to compute a minimum cost spanning tree.35 ///36 33 37 34 namespace lemon { -
lemon/network_simplex.h
r956 r1026 48 48 /// flow problem. 49 49 /// 50 /// In general, %NetworkSimplex is the fastest implementation available51 /// i n LEMON for this problem.52 /// Moreover, it supports both directions of the supply/demand inequality53 /// 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. 54 54 /// 55 55 /// Most of the parameters of the problem (except for the digraph) … … 64 64 /// algorithm. By default, it is the same as \c V. 65 65 /// 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 67 68 /// be integer. 68 69 /// … … 126 127 /// of the algorithm. 127 128 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which 128 /// provedto be the most efficient and the most robust on various129 /// turend out to be the most efficient and the most robust on various 129 130 /// test inputs. 130 131 /// However, another pivot rule can be selected using the \ref run() … … 167 168 typedef std::vector<Value> ValueVector; 168 169 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 171 173 172 174 // State constants for arcs … … 177 179 }; 178 180 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 }; 182 186 183 187 private: … … 218 222 IntVector _succ_num; 219 223 IntVector _last_succ; 224 CharVector _pred_dir; 225 CharVector _state; 220 226 IntVector _dirty_revs; 221 BoolVector _forward;222 StateVector _state;223 227 int _root; 224 228 225 229 // Temporary data used in the current pivot iteration 226 230 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;229 231 Value delta; 230 232 … … 251 253 const IntVector &_target; 252 254 const CostVector &_cost; 253 const StateVector &_state;255 const CharVector &_state; 254 256 const CostVector &_pi; 255 257 int &_in_arc; … … 303 305 const IntVector &_target; 304 306 const CostVector &_cost; 305 const StateVector &_state;307 const CharVector &_state; 306 308 const CostVector &_pi; 307 309 int &_in_arc; … … 342 344 const IntVector &_target; 343 345 const CostVector &_cost; 344 const StateVector &_state;346 const CharVector &_state; 345 347 const CostVector &_pi; 346 348 int &_in_arc; … … 415 417 const IntVector &_target; 416 418 const CostVector &_cost; 417 const StateVector &_state;419 const CharVector &_state; 418 420 const CostVector &_pi; 419 421 int &_in_arc; … … 518 520 const IntVector &_target; 519 521 const CostVector &_cost; 520 const StateVector &_state;522 const CharVector &_state; 521 523 const CostVector &_pi; 522 524 int &_in_arc; … … 571 573 // Check the current candidate list 572 574 int e; 575 Cost c; 573 576 for (int i = 0; i != _curr_length; ++i) { 574 577 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 { 578 582 _candidates[i--] = _candidates[--_curr_length]; 579 583 } … … 585 589 586 590 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; 590 594 _candidates[_curr_length++] = e; 591 595 } … … 634 638 /// 635 639 /// \param graph The digraph the algorithm runs on. 636 /// \param arc_mixing Indicate if the arcs have tobe stored in a640 /// \param arc_mixing Indicate if the arcs will be stored in a 637 641 /// 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) : 641 646 _graph(graph), _node_id(graph), _arc_id(graph), 642 647 _arc_mixing(arc_mixing), … … 731 736 /// 732 737 /// \return <tt>(*this)</tt> 738 /// 739 /// \sa supplyType() 733 740 template<typename SupplyMap> 734 741 NetworkSimplex& supplyMap(const SupplyMap& map) { … … 747 754 /// 748 755 /// Using this function has the same effect as using \ref supplyMap() 749 /// with sucha map in which \c k is assigned to \c s, \c -k is756 /// with a map in which \c k is assigned to \c s, \c -k is 750 757 /// assigned to \c t and all other nodes have zero supply value. 751 758 /// … … 914 921 _parent.resize(all_node_num); 915 922 _pred.resize(all_node_num); 916 _ forward.resize(all_node_num);923 _pred_dir.resize(all_node_num); 917 924 _thread.resize(all_node_num); 918 925 _rev_thread.resize(all_node_num); … … 928 935 if (_arc_mixing) { 929 936 // 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); 931 938 int i = 0, j = 0; 932 939 for (ArcIt a(_graph); a != INVALID; ++a) { … … 934 941 _source[i] = _node_id[_graph.source(a)]; 935 942 _target[i] = _node_id[_graph.target(a)]; 936 if ((i += k) >= _arc_num) i = ++j;943 if ((i += skip) >= _arc_num) i = ++j; 937 944 } 938 945 } else { … … 1078 1085 ART_COST = std::numeric_limits<Cost>::max() / 2 + 1; 1079 1086 } else { 1080 ART_COST = std::numeric_limits<Cost>::min();1087 ART_COST = 0; 1081 1088 for (int i = 0; i != _arc_num; ++i) { 1082 1089 if (_cost[i] > ART_COST) ART_COST = _cost[i]; … … 1117 1124 _state[e] = STATE_TREE; 1118 1125 if (_supply[u] >= 0) { 1119 _ forward[u] = true;1126 _pred_dir[u] = DIR_UP; 1120 1127 _pi[u] = 0; 1121 1128 _source[e] = u; … … 1124 1131 _cost[e] = 0; 1125 1132 } else { 1126 _ forward[u] = false;1133 _pred_dir[u] = DIR_DOWN; 1127 1134 _pi[u] = ART_COST; 1128 1135 _source[e] = _root; … … 1144 1151 _last_succ[u] = u; 1145 1152 if (_supply[u] >= 0) { 1146 _ forward[u] = true;1153 _pred_dir[u] = DIR_UP; 1147 1154 _pi[u] = 0; 1148 1155 _pred[u] = e; … … 1154 1161 _state[e] = STATE_TREE; 1155 1162 } else { 1156 _ forward[u] = false;1163 _pred_dir[u] = DIR_DOWN; 1157 1164 _pi[u] = ART_COST; 1158 1165 _pred[u] = f; … … 1185 1192 _last_succ[u] = u; 1186 1193 if (_supply[u] <= 0) { 1187 _ forward[u] = false;1194 _pred_dir[u] = DIR_DOWN; 1188 1195 _pi[u] = 0; 1189 1196 _pred[u] = e; … … 1195 1202 _state[e] = STATE_TREE; 1196 1203 } else { 1197 _ forward[u] = true;1204 _pred_dir[u] = DIR_UP; 1198 1205 _pi[u] = -ART_COST; 1199 1206 _pred[u] = f; … … 1238 1245 // Initialize first and second nodes according to the direction 1239 1246 // of the cycle 1247 int first, second; 1240 1248 if (_state[in_arc] == STATE_LOWER) { 1241 1249 first = _source[in_arc]; … … 1247 1255 delta = _cap[in_arc]; 1248 1256 int result = 0; 1249 Value d;1257 Value c, d; 1250 1258 int e; 1251 1259 1252 // Search the cycle along the path form the first node to the root1260 // Search the cycle form the first node to the join node 1253 1261 for (int u = first; u != join; u = _parent[u]) { 1254 1262 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 } 1257 1268 if (d < delta) { 1258 1269 delta = d; … … 1261 1272 } 1262 1273 } 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 1264 1276 for (int u = second; u != join; u = _parent[u]) { 1265 1277 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 } 1268 1283 if (d <= delta) { 1269 1284 delta = d; … … 1290 1305 _flow[in_arc] += val; 1291 1306 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; 1293 1308 } 1294 1309 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; 1296 1311 } 1297 1312 } … … 1308 1323 // Update the tree structure 1309 1324 void updateTreeStructure() { 1310 int u, w;1311 1325 int old_rev_thread = _rev_thread[u_out]; 1312 1326 int old_succ_num = _succ_num[u_out]; … … 1314 1328 v_out = _parent[u_out]; 1315 1329 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 } 1323 1348 } 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; 1398 1416 } 1399 1417 1400 1418 // 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 1405 1425 // Update _last_succ from v_out towards the root 1406 1426 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; 1408 1428 u = _parent[u]) { 1409 1429 _last_succ[u] = old_rev_thread; 1410 1430 } 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; 1413 1434 u = _parent[u]) { 1414 _last_succ[u] = _last_succ[u_out];1435 _last_succ[u] = last_succ_out; 1415 1436 } 1416 1437 } 1417 1438 1418 1439 // 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]) { 1420 1441 _succ_num[u] += old_succ_num; 1421 1442 } 1422 1443 // 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]) { 1424 1445 _succ_num[u] -= old_succ_num; 1425 1446 } 1426 1447 } 1427 1448 1428 // Update potentials 1449 // Update potentials in the subtree that has been moved 1429 1450 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]; 1434 1453 int end = _thread[_last_succ[u_in]]; 1435 1454 for (int u = u_in; u != end; u = _thread[u]) { … … 1590 1609 if (_sum_supply == 0) { 1591 1610 if (_stype == GEQ) { 1592 Cost max_pot = std::numeric_limits<Cost>::min();1611 Cost max_pot = -std::numeric_limits<Cost>::max(); 1593 1612 for (int i = 0; i != _node_num; ++i) { 1594 1613 if (_pi[i] > max_pot) max_pot = _pi[i]; -
lemon/path.h
r956 r1024 44 44 /// 45 45 /// In a sense, the path can be treated as a list of arcs. The 46 /// lemonpath type stores just this list. As a consequence, it46 /// LEMON path type stores just this list. As a consequence, it 47 47 /// cannot enumerate the nodes of the path and the source node of 48 48 /// a zero length path is undefined. … … 136 136 void clear() { head.clear(); tail.clear(); } 137 137 138 /// \brief The n th arc.138 /// \brief The n-th arc. 139 139 /// 140 140 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. … … 144 144 } 145 145 146 /// \brief Initialize arc iterator to point to the n th arc146 /// \brief Initialize arc iterator to point to the n-th arc 147 147 /// 148 148 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. … … 232 232 /// 233 233 /// In a sense, the path can be treated as a list of arcs. The 234 /// lemonpath type stores just this list. As a consequence it234 /// LEMON path type stores just this list. As a consequence it 235 235 /// cannot enumerate the nodes in the path and the zero length paths 236 236 /// cannot store the source. … … 328 328 void clear() { data.clear(); } 329 329 330 /// \brief The n th arc.330 /// \brief The n-th arc. 331 331 /// 332 332 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. … … 335 335 } 336 336 337 /// \brief Initializes arc iterator to point to the n th arc.337 /// \brief Initializes arc iterator to point to the n-th arc. 338 338 ArcIt nthIt(int n) const { 339 339 return ArcIt(*this, n); … … 396 396 /// 397 397 /// In a sense, the path can be treated as a list of arcs. The 398 /// lemonpath type stores just this list. As a consequence it398 /// LEMON path type stores just this list. As a consequence it 399 399 /// cannot enumerate the nodes in the path and the zero length paths 400 400 /// cannot store the source. … … 505 505 }; 506 506 507 /// \brief The n th arc.508 /// 509 /// This function looks for the n th 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. 510 510 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. 511 511 const Arc& nth(int n) const { … … 517 517 } 518 518 519 /// \brief Initializes arc iterator to point to the n th arc.519 /// \brief Initializes arc iterator to point to the n-th arc. 520 520 ArcIt nthIt(int n) const { 521 521 Node *node = first; … … 736 736 /// 737 737 /// In a sense, the path can be treated as a list of arcs. The 738 /// lemonpath type stores just this list. As a consequence it738 /// LEMON path type stores just this list. As a consequence it 739 739 /// cannot enumerate the nodes in the path and the source node of 740 740 /// a zero length path is undefined. … … 832 832 }; 833 833 834 /// \brief The n th arc.834 /// \brief The n-th arc. 835 835 /// 836 836 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. … … 839 839 } 840 840 841 /// \brief The arc iterator pointing to the n th arc.841 /// \brief The arc iterator pointing to the n-th arc. 842 842 ArcIt nthIt(int n) const { 843 843 return ArcIt(*this, n); … … 1043 1043 /// 1044 1044 /// In a sense, the path can be treated as a list of arcs. The 1045 /// lemonpath type stores only this list. As a consequence, it1045 /// LEMON path type stores only this list. As a consequence, it 1046 1046 /// cannot enumerate the nodes in the path and the zero length paths 1047 1047 /// cannot have a source node. -
lemon/preflow.h
r956 r1029 544 544 _flow->set(e, (*_capacity)[e]); 545 545 (*_excess)[u] += rem; 546 if (u != _target && !_level->active(u)) {547 _level->activate(u);548 }549 546 } 550 547 } … … 556 553 _flow->set(e, 0); 557 554 (*_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 563 561 return true; 564 562 } … … 577 575 _phase = true; 578 576 579 Node n = _level->highestActive(); 580 int level = _level->highestActiveLevel(); 581 while (n != INVALID) { 577 while (true) { 582 578 int num = _node_num; 583 579 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 585 589 Value excess = (*_excess)[n]; 586 590 int new_level = _level->maxLevel(); … … 648 652 _level->deactivate(n); 649 653 } 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 } 653 668 --num; 654 } 655 656 num = _node_num * 20; 657 while (num > 0 && n != INVALID) { 669 658 670 Value excess = (*_excess)[n]; 659 671 int new_level = _level->maxLevel(); … … 721 733 _level->deactivate(n); 722 734 } 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:; 736 738 } 737 739 -
test/CMakeLists.txt
r953 r1050 7 7 ${PROJECT_BINARY_DIR}/lemon 8 8 ) 9 10 SET(TEST_WITH_VALGRIND "NO" CACHE STRING 11 "Run the test with valgrind (YES/NO).") 12 SET(VALGRIND_FLAGS "" CACHE STRING "Valgrind flags used by the tests.") 9 13 10 14 SET(TESTS … … 32 36 maps_test 33 37 matching_test 38 max_cardinality_search_test 39 max_clique_test 34 40 min_cost_arborescence_test 35 41 min_cost_flow_test 36 42 min_mean_cycle_test 43 nagamochi_ibaraki_test 37 44 path_test 38 45 planarity_test … … 46 53 47 54 IF(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 49 61 SET(LP_TEST_LIBS lemon) 50 62 … … 82 94 83 95 IF(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 85 102 SET(MIP_TEST_LIBS lemon) 86 103 … … 118 135 119 136 FOREACH(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() 121 142 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}) 123 151 ENDFOREACH() -
test/Makefile.am
r953 r1021 34 34 test/maps_test \ 35 35 test/matching_test \ 36 test/max_cardinality_search_test \ 37 test/max_clique_test \ 36 38 test/min_cost_arborescence_test \ 37 39 test/min_cost_flow_test \ 38 40 test/min_mean_cycle_test \ 41 test/nagamochi_ibaraki_test \ 39 42 test/path_test \ 40 43 test/planarity_test \ … … 85 88 test_mip_test_SOURCES = test/mip_test.cc 86 89 test_matching_test_SOURCES = test/matching_test.cc 90 test_max_cardinality_search_test_SOURCES = test/max_cardinality_search_test.cc 91 test_max_clique_test_SOURCES = test/max_clique_test.cc 87 92 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc 88 93 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc 89 94 test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc 95 test_nagamochi_ibaraki_test_SOURCES = test/nagamochi_ibaraki_test.cc 90 96 test_path_test_SOURCES = test/path_test.cc 91 97 test_planarity_test_SOURCES = test/planarity_test.cc -
test/bellman_ford_test.cc
r956 r960 105 105 ::SetDistMap<concepts::ReadWriteMap<Node,Value> > 106 106 ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> > 107 ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> >108 107 ::Create bf_test(gr,length); 109 108 -
test/dfs_test.cc
r956 r1010 51 51 "@attributes\n" 52 52 "source 0\n" 53 "target 5\n"; 53 "target 5\n" 54 "source1 6\n" 55 "target1 3\n"; 56 54 57 55 58 void checkDfsCompile() … … 180 183 Digraph G; 181 184 Node s, t; 185 Node s1, t1; 182 186 183 187 std::istringstream input(test_lgf); … … 185 189 node("source", s). 186 190 node("target", t). 191 node("source1", s1). 192 node("target1", t1). 187 193 run(); 188 194 … … 211 217 212 218 { 219 Dfs<Digraph> dfs(G); 220 check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6."); 221 } 222 223 { 213 224 NullMap<Node,Arc> myPredMap; 214 225 dfs(G).predMap(myPredMap).run(s); -
test/graph_copy_test.cc
r463 r989 19 19 #include <lemon/smart_graph.h> 20 20 #include <lemon/list_graph.h> 21 #include <lemon/static_graph.h> 21 22 #include <lemon/lgf_reader.h> 22 23 #include <lemon/error.h> … … 27 28 using namespace lemon; 28 29 30 template <typename GR> 29 31 void digraph_copy_test() { 30 32 const int nn = 10; 31 33 34 // Build a digraph 32 35 SmartDigraph from; 33 36 SmartDigraph::NodeMap<int> fnm(from); … … 51 54 } 52 55 } 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); 65 69 66 70 digraphCopy(from, to). … … 69 73 nodeCrossRef(ncr).arcCrossRef(ecr). 70 74 node(fn, tn).arc(fa, ta).run(); 75 76 check(countNodes(from) == countNodes(to), "Wrong copy."); 77 check(countArcs(from) == countArcs(to), "Wrong copy."); 71 78 72 79 for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) { … … 82 89 } 83 90 84 for ( ListDigraph::NodeIt it(to); it != INVALID; ++it) {91 for (typename GR::NodeIt it(to); it != INVALID; ++it) { 85 92 check(nr[ncr[it]] == it, "Wrong copy."); 86 93 } 87 94 88 for ( ListDigraph::ArcIt it(to); it != INVALID; ++it) {95 for (typename GR::ArcIt it(to); it != INVALID; ++it) { 89 96 check(er[ecr[it]] == it, "Wrong copy."); 90 97 } 91 98 check(tn == nr[fn], "Wrong copy."); 92 99 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."); 93 106 } 94 107 108 template <typename GR> 95 109 void graph_copy_test() { 96 110 const int nn = 10; 97 111 112 // Build a graph 98 113 SmartGraph from; 99 114 SmartGraph::NodeMap<int> fnm(from); … … 123 138 } 124 139 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); 140 156 141 157 graphCopy(from, to). … … 144 160 nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr). 145 161 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."); 146 166 147 167 for (SmartGraph::NodeIt it(from); it != INVALID; ++it) { … … 168 188 } 169 189 170 for ( ListGraph::NodeIt it(to); it != INVALID; ++it) {190 for (typename GR::NodeIt it(to); it != INVALID; ++it) { 171 191 check(nr[ncr[it]] == it, "Wrong copy."); 172 192 } 173 193 174 for ( ListGraph::ArcIt it(to); it != INVALID; ++it) {194 for (typename GR::ArcIt it(to); it != INVALID; ++it) { 175 195 check(ar[acr[it]] == it, "Wrong copy."); 176 196 } 177 for ( ListGraph::EdgeIt it(to); it != INVALID; ++it) {197 for (typename GR::EdgeIt it(to); it != INVALID; ++it) { 178 198 check(er[ecr[it]] == it, "Wrong copy."); 179 199 } … … 181 201 check(ta == ar[fa], "Wrong copy."); 182 202 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."); 183 210 } 184 211 185 212 186 213 int 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>(); 189 219 190 220 return 0; -
test/preflow_test.cc
r956 r1029 157 157 } 158 158 159 void 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 159 183 int main() { 160 184 … … 247 271 "The max flow value or the three min cut values are incorrect."); 248 272 273 initFlowTest(); 274 249 275 return 0; 250 276 }
Note: See TracChangeset
for help on using the changeset viewer.