Changes in / [1043:4e36fdf856b7:1041:f112c18bc304] in lemon
- Files:
-
- 1 added
- 3 deleted
- 24 edited
Legend:
- Unmodified
- Added
- Removed
-
CMakeLists.txt
r1035 r791 3 3 SET(PROJECT_NAME "LEMON") 4 4 PROJECT(${PROJECT_NAME}) 5 6 INCLUDE(FindPythonInterp)7 INCLUDE(FindWget)8 5 9 6 IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake) … … 12 9 SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.") 13 10 ELSE() 14 EXECUTE_PROCESS(15 COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py16 WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}17 OUTPUT_VARIABLE HG_REVISION_PATH18 ERROR_QUIET19 OUTPUT_STRIP_TRAILING_WHITESPACE20 )21 11 EXECUTE_PROCESS( 22 12 COMMAND hg id -i … … 27 17 ) 28 18 IF(HG_REVISION STREQUAL "") 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() 19 SET(HG_REVISION "hg-tip") 36 20 ENDIF() 37 SET(LEMON_VERSION ${HG_REVISION _ID} CACHE STRING "LEMON version string.")21 SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.") 38 22 ENDIF() 39 23 … … 48 32 FIND_PACKAGE(COIN) 49 33 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 -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")55 SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")56 SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")57 ELSEIF(MSVC)58 # This part is unnecessary 'casue the same is set by the lemon/core.h.59 # Still keep it as an example.60 SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")61 # Suppressed warnings:62 # C4250: 'class1' : inherits 'class2::member' via dominance63 # C4355: 'this' : used in base member initializer list64 # C4503: 'function' : decorated name length exceeded, name was truncated65 # C4800: 'type' : forcing value to bool 'true' or 'false'66 # (performance warning)67 # C4996: 'function': was declared deprecated68 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 STRING77 "Flags used by the C++ compiler during maintainer builds."78 FORCE )79 SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING80 "Flags used by the C compiler during maintainer builds."81 FORCE )82 SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER83 "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING84 "Flags used for linking binaries during maintainer builds."85 FORCE )86 SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER87 "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING88 "Flags used by the shared libraries linker during maintainer builds."89 FORCE )90 MARK_AS_ADVANCED(91 CMAKE_CXX_FLAGS_MAINTAINER92 CMAKE_C_FLAGS_MAINTAINER93 CMAKE_EXE_LINKER_FLAGS_MAINTAINER94 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 STRING100 "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 STRING109 "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 113 34 INCLUDE(CheckTypeSize) 114 35 CHECK_TYPE_SIZE("long long" LONG_LONG) … … 118 39 119 40 ENABLE_TESTING() 120 121 IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")122 ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})123 ELSE()124 ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})125 ENDIF()126 41 127 42 ADD_SUBDIRECTORY(lemon) … … 150 65 ENDIF() 151 66 152 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} )67 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32) 153 68 SET(CPACK_PACKAGE_NAME ${PROJECT_NAME}) 154 69 SET(CPACK_PACKAGE_VENDOR "EGRES") -
LICENSE
r959 r600 2 2 copyright/license. 3 3 4 Copyright (C) 2003-20 10Egervary Jeno Kombinatorikus Optimalizalasi4 Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi 5 5 Kutatocsoport (Egervary Combinatorial Optimization Research Group, 6 6 EGRES). -
NEWS
r1005 r712 1 2010-10-21 Version 1.2.1 released2 3 Bugfix release.4 5 #366: Fix Pred[Matrix]MapPath::empty()6 #371: Bug fix in (di)graphCopy()7 The target graph is cleared before adding nodes and arcs/edges.8 9 #364: Add missing UndirectedTags10 #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex11 #372: Fix a critical bug in preflow12 13 2010-03-19 Version 1.2 released14 15 This is major feature release16 17 * New algorithms18 * Bellman-Ford algorithm (#51)19 * Minimum mean cycle algorithms (#179)20 * Karp, Hartman-Orlin and Howard algorithms21 * New minimum cost flow algorithms (#180)22 * Cost Scaling algorithms23 * Capacity Scaling algorithm24 * Cycle-Canceling algorithms25 * Planarity related algorithms (#62)26 * Planarity checking algorithm27 * Planar embedding algorithm28 * Schnyder's planar drawing algorithm29 * Coloring planar graphs with five or six colors30 * Fractional matching algorithms (#314)31 * New data structures32 * StaticDigraph structure (#68)33 * Several new priority queue structures (#50, #301)34 * Fibonacci, Radix, Bucket, Pairing, Binomial35 D-ary and fourary heaps (#301)36 * Iterable map structures (#73)37 * Other new tools and functionality38 * Map utility functions (#320)39 * Reserve functions are added to ListGraph and SmartGraph (#311)40 * A resize() function is added to HypercubeGraph (#311)41 * A count() function is added to CrossRefMap (#302)42 * Support for multiple targets in Suurballe using fullInit() (#181)43 * Traits class and named parameters for Suurballe (#323)44 * Separate reset() and resetParams() functions in NetworkSimplex45 to handle graph changes (#327)46 * tolerance() functions are added to HaoOrlin (#306)47 * Implementation improvements48 * Improvements in weighted matching algorithms (#314)49 * Jumpstart initialization50 * ArcIt iteration is based on out-arc lists instead of in-arc lists51 in ListDigraph (#311)52 * Faster add row operation in CbcMip (#203)53 * Better implementation for split() in ListDigraph (#311)54 * ArgParser can also throw exception instead of exit(1) (#332)55 * Miscellaneous56 * A simple interactive bootstrap script57 * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,58 #316,#319)59 * BibTeX references in the doc (#184)60 * Optionally use valgrind when running tests61 * Also check ReferenceMapTag in concept checks (#312)62 * dimacs-solver uses long long type by default.63 * Several bugfixes (compared to release 1.1):64 #295: Suppress MSVC warnings using pragmas65 ----: Various CMAKE related improvements66 * Remove duplications from doc/CMakeLists.txt67 * Rename documentation install folder from 'docs' to 'html'68 * Add tools/CMakeLists.txt to the tarball69 * Generate and install LEMONConfig.cmake70 * Change the label of the html project in Visual Studio71 * Fix the check for the 'long long' type72 * Put the version string into config.h73 * Minor CMake improvements74 * Set the version to 'hg-tip' if everything fails75 #311: Add missing 'explicit' keywords76 #302: Fix the implementation and doc of CrossRefMap77 #308: Remove duplicate list_graph.h entry from source list78 #307: Bugfix in Preflow and Circulation79 #305: Bugfix and extension in the rename script80 #312: Also check ReferenceMapTag in concept checks81 #250: Bugfix in pathSource() and pathTarget()82 #321: Use pathCopy(from,to) instead of copyPath(to,from)83 #322: Distribure LEMONConfig.cmake.in84 #330: Bug fix in map_extender.h85 #336: Fix the date field comment of graphToEps() output86 #323: Bug fix in Suurballe87 #335: Fix clear() function in ExtendFindEnum88 #337: Use void* as the LPX object pointer89 #317: Fix (and improve) error message in mip_test.cc90 Remove unnecessary OsiCbc dependency91 #356: Allow multiple executions of weighted matching algorithms (#356)92 93 1 2009-05-13 Version 1.1 released 94 2 … … 165 73 ----: Add missing unistd.h include to time_measure.h 166 74 #204: Compilation bug fixed in graph_to_eps.h with VS2005 167 #214,#215: windows.h should never be included by LEMONheaders75 #214,#215: windows.h should never be included by lemon headers 168 76 #230: Build systems check the availability of 'long long' type 169 77 #229: Default implementation of Tolerance<> is used for integer types … … 187 95 2008-10-13 Version 1.0 released 188 96 189 190 191 192 97 This is the first stable release of LEMON. Compared to the 0.x 98 release series, it features a considerably smaller but more 99 matured set of tools. The API has also completely revised and 100 changed in several places. 193 101 194 102 * The major name changes compared to the 0.x series (see the 195 103 Migration Guide in the doc for more details) 196 104 * Graph -> Digraph, UGraph -> Graph 197 105 * Edge -> Arc, UEdge -> Edge 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 106 * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge) 107 * Other improvements 108 * Better documentation 109 * Reviewed and cleaned up codebase 110 * CMake based build system (along with the autotools based one) 111 * Contents of the library (ported from 0.x) 112 * Algorithms 113 * breadth-first search (bfs.h) 114 * depth-first search (dfs.h) 115 * Dijkstra's algorithm (dijkstra.h) 116 * Kruskal's algorithm (kruskal.h) 117 * Data structures 118 * graph data structures (list_graph.h, smart_graph.h) 119 * path data structures (path.h) 120 * binary heap data structure (bin_heap.h) 121 * union-find data structures (unionfind.h) 122 * miscellaneous property maps (maps.h) 123 * two dimensional vector and bounding box (dim2.h) 216 124 * Concepts 217 125 * graph structure concepts (concepts/digraph.h, concepts/graph.h, 218 126 concepts/graph_components.h) 219 220 221 222 223 224 225 226 227 127 * concepts for other structures (concepts/heap.h, concepts/maps.h, 128 concepts/path.h) 129 * Tools 130 * Mersenne twister random number generator (random.h) 131 * tools for measuring cpu and wall clock time (time_measure.h) 132 * tools for counting steps and events (counter.h) 133 * tool for parsing command line arguments (arg_parser.h) 134 * tool for visualizing graphs (graph_to_eps.h) 135 * tools for reading and writing data in LEMON Graph Format 228 136 (lgf_reader.h, lgf_writer.h) 229 137 * tools to handle the anomalies of calculations with 230 138 floating point numbers (tolerance.h) 231 139 * tools to manage RGB colors (color.h) 232 233 234 235 236 140 * Infrastructure 141 * extended assertion handling (assert.h) 142 * exception classes and error handling (error.h) 143 * concept checking (concept_check.h) 144 * commonly used mathematical constants (math.h) -
configure.ac
r1039 r840 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)/ doc/mainpage.dox.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])117 ['$(top_srcdir)/doc/Doxyfile.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.dox125 124 lemon/lemon.pc 126 125 ]) -
doc/CMakeLists.txt
r1039 r943 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 8 6 CONFIGURE_FILE( 9 7 ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in 10 8 ${PROJECT_BINARY_DIR}/doc/Doxyfile 11 @ONLY12 )13 14 CONFIGURE_FILE(15 ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in16 ${PROJECT_BINARY_DIR}/doc/mainpage.dox17 9 @ONLY 18 10 ) … … 61 53 62 54 ENDIF() 63 64 IF(WGET_FOUND)65 ADD_CUSTOM_TARGET(update-external-tags66 COMMAND ${CMAKE_COMMAND} -E make_directory dl67 # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl68 COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag69 COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag70 COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag71 COMMAND ${CMAKE_COMMAND} -E remove_directory dl72 WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}73 )74 ENDIF() -
doc/Doxyfile.in
r1039 r803 1 # Doxyfile 1. 7.31 # Doxyfile 1.5.9 2 2 3 3 #--------------------------------------------------------------------------- … … 5 5 #--------------------------------------------------------------------------- 6 6 DOXYFILE_ENCODING = UTF-8 7 PROJECT_NAME = 8 PROJECT_NUMBER = 9 PROJECT_BRIEF = 10 PROJECT_LOGO = 7 PROJECT_NAME = @PACKAGE_NAME@ 8 PROJECT_NUMBER = @PACKAGE_VERSION@ 11 9 OUTPUT_DIRECTORY = 12 10 CREATE_SUBDIRS = NO … … 32 30 OPTIMIZE_FOR_FORTRAN = NO 33 31 OPTIMIZE_OUTPUT_VHDL = NO 34 EXTENSION_MAPPING =35 32 BUILTIN_STL_SUPPORT = YES 36 33 CPP_CLI_SUPPORT = NO … … 58 55 HIDE_SCOPE_NAMES = YES 59 56 SHOW_INCLUDE_FILES = YES 60 FORCE_LOCAL_INCLUDES = NO61 57 INLINE_INFO = YES 62 58 SORT_MEMBER_DOCS = NO 63 59 SORT_BRIEF_DOCS = NO 64 SORT_MEMBERS_CTORS_1ST = NO65 60 SORT_GROUP_NAMES = NO 66 61 SORT_BY_SCOPE_NAME = NO 67 STRICT_PROTO_MATCHING = NO68 62 GENERATE_TODOLIST = YES 69 63 GENERATE_TESTLIST = YES … … 77 71 SHOW_NAMESPACES = YES 78 72 FILE_VERSION_FILTER = 79 LAYOUT_FILE = "@abs_top_srcdir@/doc/DoxygenLayout.xml"73 LAYOUT_FILE = DoxygenLayout.xml 80 74 #--------------------------------------------------------------------------- 81 75 # configuration options related to warning and progress messages … … 98 92 "@abs_top_srcdir@/tools" \ 99 93 "@abs_top_srcdir@/test/test_tools.h" \ 100 "@abs_top_builddir@/doc/mainpage.dox" \101 94 "@abs_top_builddir@/doc/references.dox" 102 95 INPUT_ENCODING = UTF-8 … … 119 112 FILTER_PATTERNS = 120 113 FILTER_SOURCE_FILES = NO 121 FILTER_SOURCE_PATTERNS =122 114 #--------------------------------------------------------------------------- 123 115 # configuration options related to source browsing 124 116 #--------------------------------------------------------------------------- 125 SOURCE_BROWSER = @LEMON_DOC_SOURCE_BROWSER@117 SOURCE_BROWSER = NO 126 118 INLINE_SOURCES = NO 127 119 STRIP_CODE_COMMENTS = YES … … 146 138 HTML_FOOTER = 147 139 HTML_STYLESHEET = 148 HTML_COLORSTYLE_HUE = 220149 HTML_COLORSTYLE_SAT = 100150 HTML_COLORSTYLE_GAMMA = 80151 HTML_TIMESTAMP = YES152 140 HTML_ALIGN_MEMBERS = YES 153 HTML_DYNAMIC_SECTIONS = YES141 HTML_DYNAMIC_SECTIONS = NO 154 142 GENERATE_DOCSET = NO 155 143 DOCSET_FEEDNAME = "Doxygen generated docs" 156 144 DOCSET_BUNDLE_ID = org.doxygen.Project 157 DOCSET_PUBLISHER_ID = org.doxygen.Publisher158 DOCSET_PUBLISHER_NAME = Publisher159 145 GENERATE_HTMLHELP = NO 160 146 CHM_FILE = … … 168 154 QHP_NAMESPACE = org.doxygen.Project 169 155 QHP_VIRTUAL_FOLDER = doc 170 QHP_CUST_FILTER_NAME =171 QHP_CUST_FILTER_ATTRS =172 QHP_SECT_FILTER_ATTRS =173 156 QHG_LOCATION = 174 GENERATE_ECLIPSEHELP = NO175 ECLIPSE_DOC_ID = org.doxygen.Project176 157 DISABLE_INDEX = NO 177 158 ENUM_VALUES_PER_LINE = 4 178 159 GENERATE_TREEVIEW = NO 179 USE_INLINE_TREES = NO180 160 TREEVIEW_WIDTH = 250 181 EXT_LINKS_IN_WINDOW = NO182 161 FORMULA_FONTSIZE = 10 183 FORMULA_TRANSPARENT = YES184 USE_MATHJAX = NO185 MATHJAX_RELPATH = http://www.mathjax.org/mathjax186 SEARCHENGINE = YES187 SERVER_BASED_SEARCH = NO188 162 #--------------------------------------------------------------------------- 189 163 # configuration options related to the LaTeX output … … 202 176 LATEX_BATCHMODE = NO 203 177 LATEX_HIDE_INDICES = NO 204 LATEX_SOURCE_CODE = NO205 178 #--------------------------------------------------------------------------- 206 179 # configuration options related to the RTF output … … 251 224 SKIP_FUNCTION_MACROS = YES 252 225 #--------------------------------------------------------------------------- 253 # Configuration::additions related to external references254 #--------------------------------------------------------------------------- 255 TAGFILES = "@abs_top_ builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ "226 # Options related to the search engine 227 #--------------------------------------------------------------------------- 228 TAGFILES = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ " 256 229 GENERATE_TAGFILE = html/lemon.tag 257 230 ALLEXTERNALS = NO … … 265 238 HIDE_UNDOC_RELATIONS = YES 266 239 HAVE_DOT = YES 267 DOT_NUM_THREADS = 0268 240 DOT_FONTNAME = FreeSans 269 241 DOT_FONTSIZE = 10 … … 283 255 DOT_PATH = 284 256 DOTFILE_DIRS = 285 MSCFILE_DIRS =286 257 DOT_GRAPH_MAX_NODES = 50 287 258 MAX_DOT_GRAPH_DEPTH = 0 … … 290 261 GENERATE_LEGEND = YES 291 262 DOT_CLEANUP = YES 263 #--------------------------------------------------------------------------- 264 # Configuration::additions related to the search engine 265 #--------------------------------------------------------------------------- 266 SEARCHENGINE = NO -
doc/DoxygenLayout.xml
r1036 r316 3 3 <navindex> 4 4 <tab type="mainpage" visible="yes" title=""/> 5 <tab type="modules" visible="yes" title="" intro=""/>5 <tab type="modules" visible="yes" title=""/> 6 6 <tab type="classes" 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=""/>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=""/> 11 11 </tab> 12 12 <tab type="namespaces" visible="yes" title=""> 13 <tab type="namespaces" visible="yes" title="" intro=""/>14 <tab type="namespacemembers" visible="yes" title="" intro=""/>13 <tab type="namespaces" visible="yes" title=""/> 14 <tab type="namespacemembers" visible="yes" title=""/> 15 15 </tab> 16 16 <tab type="files" visible="yes" title=""> 17 <tab type="files" visible="yes" title="" intro=""/>18 <tab type="globals" visible="yes" title="" intro=""/>17 <tab type="files" visible="yes" title=""/> 18 <tab type="globals" visible="yes" title=""/> 19 19 </tab> 20 <tab type="dirs" visible="yes" title="" intro=""/>21 <tab type="examples" visible="yes" title="" intro=""/>22 <tab type="pages" visible="yes" title="" intro=""/>20 <tab type="dirs" visible="yes" title=""/> 21 <tab type="examples" visible="yes" title=""/> 22 <tab type="pages" visible="yes" title=""/> 23 23 </navindex> 24 24 -
doc/groups.dox
r963 r956 264 264 265 265 /** 266 @defgroup matrices Matrices 267 @ingroup datas 268 \brief Two dimensional data storages implemented in LEMON. 269 270 This group contains two dimensional data storages implemented in LEMON. 271 */ 272 273 /** 266 274 @defgroup auxdat Auxiliary Data Structures 267 275 @ingroup datas … … 284 292 rectangular bounding box of a set of \ref lemon::dim2::Point 285 293 "dim2::Point"'s. 294 */ 295 296 /** 297 @defgroup matrices Matrices 298 @ingroup auxdat 299 \brief Two dimensional data storages implemented in LEMON. 300 301 This group contains two dimensional data storages implemented in LEMON. 286 302 */ 287 303 … … 319 335 but the digraph should not contain directed cycles with negative total 320 336 length. 337 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms 338 for solving the \e all-pairs \e shortest \e paths \e problem when arc 339 lenghts can be either positive or negative, but the digraph should 340 not contain directed cycles with negative total length. 321 341 - \ref Suurballe A successive shortest path algorithm for finding 322 342 arc-disjoint paths between two nodes having minimum total length. … … 352 372 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 353 373 354 \ref Preflow is an efficient implementation of Goldberg-Tarjan's 355 preflow push-relabel algorithm \ref goldberg88newapproach for finding 356 maximum flows. It also provides functions to query the minimum cut, 357 which is the dual problem of maximum flow. 374 LEMON contains several algorithms for solving maximum flow problems: 375 - \ref EdmondsKarp Edmonds-Karp algorithm 376 \ref edmondskarp72theoretical. 377 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm 378 \ref goldberg88newapproach. 379 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 380 \ref dinic70algorithm, \ref sleator83dynamic. 381 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees 382 \ref goldberg88newapproach, \ref sleator83dynamic. 383 384 In most cases the \ref Preflow algorithm provides the 385 fastest method for computing a maximum flow. All implementations 386 also provide functions to query the minimum cut, which is the dual 387 problem of maximum flow. 358 388 359 389 \ref Circulation is a preflow push-relabel algorithm implemented directly … … 412 442 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut 413 443 in directed graphs. 444 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for 445 calculating minimum cut in undirected graphs. 414 446 - \ref GomoryHu "Gomory-Hu tree computation" for calculating 415 447 all-pairs minimum cut in undirected graphs. … … 441 473 442 474 LEMON contains three algorithms for solving the minimum mean cycle problem: 443 - \ref Karp Mmc Karp's original algorithm \ref amo93networkflows,475 - \ref Karp "Karp"'s original algorithm \ref amo93networkflows, 444 476 \ref dasdan98minmeancycle. 445 - \ref HartmannOrlin Mmc Hartmann-Orlin's algorithm, which is an improved477 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved 446 478 version of Karp's algorithm \ref dasdan98minmeancycle. 447 - \ref Howard Mmc Howard's policy iteration algorithm479 - \ref Howard "Howard"'s policy iteration algorithm 448 480 \ref dasdan98minmeancycle. 449 481 450 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the451 most efficient one, though the best known theoretical bound on its running 452 time isexponential.453 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms454 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is 455 typically faster due to theapplied early termination scheme.482 In practice, the Howard algorithm proved to be by far the most efficient 483 one, though the best known theoretical bound on its running time is 484 exponential. 485 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space 486 O(n<sup>2</sup>+e), but the latter one is typically faster due to the 487 applied early termination scheme. 456 488 */ 457 489 … … 474 506 475 507 The matching algorithms implemented in LEMON: 508 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm 509 for calculating maximum cardinality matching in bipartite graphs. 510 - \ref PrBipartiteMatching Push-relabel algorithm 511 for calculating maximum cardinality matching in bipartite graphs. 512 - \ref MaxWeightedBipartiteMatching 513 Successive shortest path algorithm for calculating maximum weighted 514 matching and maximum weighted bipartite matching in bipartite graphs. 515 - \ref MinCostMaxBipartiteMatching 516 Successive shortest path algorithm for calculating minimum cost maximum 517 matching in bipartite graphs. 476 518 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 477 519 maximum cardinality matching in general graphs. … … 518 560 519 561 /** 562 @defgroup approx Approximation Algorithms 563 @ingroup algs 564 \brief Approximation algorithms. 565 566 This group contains the approximation and heuristic algorithms 567 implemented in LEMON. 568 */ 569 570 /** 520 571 @defgroup auxalg Auxiliary Algorithms 521 572 @ingroup algs … … 546 597 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 547 598 \ref cplex, \ref soplex. 599 */ 600 601 /** 602 @defgroup lp_utils Tools for Lp and Mip Solvers 603 @ingroup lp_group 604 \brief Helper tools to the Lp and Mip solvers. 605 606 This group adds some helper tools to general optimization framework 607 implemented in LEMON. 608 */ 609 610 /** 611 @defgroup metah Metaheuristics 612 @ingroup gen_opt_group 613 \brief Metaheuristics for LEMON library. 614 615 This group contains some metaheuristic optimization tools. 548 616 */ 549 617 -
lemon/CMakeLists.txt
r1012 r726 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.cmake13 ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc14 @ONLY15 9 ) 16 10 … … 73 67 COMPONENT headers 74 68 ) 75 76 INSTALL(77 FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc78 DESTINATION lib/pkgconfig79 )80 -
lemon/arg_parser.h
r959 r956 36 36 37 37 ///Exception used by ArgParser 38 39 ///Exception used by ArgParser.40 ///41 38 class ArgParserException : public Exception { 42 39 public: 43 /// Reasons for failure44 45 /// Reasons for failure.46 ///47 40 enum Reason { 48 HELP, /// < <tt>--help</tt> option was given.49 UNKNOWN_OPT, /// < Unknown option was given.50 INVALID_OPT /// < Invalid combination of options.41 HELP, /// <tt>--help</tt> option was given 42 UNKNOWN_OPT, /// Unknown option was given 43 INVALID_OPT /// Invalid combination of options 51 44 }; 52 45 -
lemon/bellman_ford.h
r960 r956 29 29 #include <lemon/error.h> 30 30 #include <lemon/maps.h> 31 #include <lemon/tolerance.h> 31 32 #include <lemon/path.h> 32 33 … … 35 36 namespace lemon { 36 37 37 /// \brief Default OperationTraits for the BellmanFord algorithm class.38 /// \brief Default operation traits for the BellmanFord algorithm class. 38 39 /// 39 40 /// This operation traits class defines all computational operations … … 42 43 /// If the numeric type does not have infinity value, then the maximum 43 44 /// value is used as extremal infinity value. 45 /// 46 /// \see BellmanFordToleranceOperationTraits 44 47 template < 45 48 typename V, 46 49 bool has_inf = std::numeric_limits<V>::has_infinity> 47 50 struct BellmanFordDefaultOperationTraits { 48 /// \ e51 /// \brief Value type for the algorithm. 49 52 typedef V Value; 50 53 /// \brief Gives back the zero value of the type. … … 82 85 static bool less(const Value& left, const Value& right) { 83 86 return left < right; 87 } 88 }; 89 90 /// \brief Operation traits for the BellmanFord algorithm class 91 /// using tolerance. 92 /// 93 /// This operation traits class defines all computational operations 94 /// and constants that are used in the Bellman-Ford algorithm. 95 /// The only difference between this implementation and 96 /// \ref BellmanFordDefaultOperationTraits is that this class uses 97 /// the \ref Tolerance "tolerance technique" in its \ref less() 98 /// function. 99 /// 100 /// \tparam V The value type. 101 /// \tparam eps The epsilon value for the \ref less() function. 102 /// By default, it is the epsilon value used by \ref Tolerance 103 /// "Tolerance<V>". 104 /// 105 /// \see BellmanFordDefaultOperationTraits 106 #ifdef DOXYGEN 107 template <typename V, V eps> 108 #else 109 template < 110 typename V, 111 V eps = Tolerance<V>::def_epsilon> 112 #endif 113 struct BellmanFordToleranceOperationTraits { 114 /// \brief Value type for the algorithm. 115 typedef V Value; 116 /// \brief Gives back the zero value of the type. 117 static Value zero() { 118 return static_cast<Value>(0); 119 } 120 /// \brief Gives back the positive infinity value of the type. 121 static Value infinity() { 122 return std::numeric_limits<Value>::infinity(); 123 } 124 /// \brief Gives back the sum of the given two elements. 125 static Value plus(const Value& left, const Value& right) { 126 return left + right; 127 } 128 /// \brief Gives back \c true only if the first value is less than 129 /// the second. 130 static bool less(const Value& left, const Value& right) { 131 return left + eps < right; 84 132 } 85 133 }; … … 108 156 /// It defines the used operations and the infinity value for the 109 157 /// given \c Value type. 110 /// \see BellmanFordDefaultOperationTraits 158 /// \see BellmanFordDefaultOperationTraits, 159 /// BellmanFordToleranceOperationTraits 111 160 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 112 161 … … 838 887 /// It defines the used operations and the infinity value for the 839 888 /// given \c Value type. 840 /// \see BellmanFordDefaultOperationTraits 889 /// \see BellmanFordDefaultOperationTraits, 890 /// BellmanFordToleranceOperationTraits 841 891 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 842 892 -
lemon/bits/edge_set_extender.h
r968 r956 281 281 typedef EdgeSetExtender Graph; 282 282 283 typedef True UndirectedTag;284 285 283 typedef typename Parent::Node Node; 286 284 typedef typename Parent::Arc Arc; -
lemon/bits/graph_adaptor_extender.h
r965 r664 182 182 typedef GraphAdaptorExtender Adaptor; 183 183 184 typedef True UndirectedTag;185 186 184 typedef typename Parent::Node Node; 187 185 typedef typename Parent::Arc Arc; -
lemon/bits/path_dump.h
r973 r576 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 predMatrixMap(source, target) == INVALID;126 return source != target; 127 127 } 128 128 -
lemon/core.h
r986 r956 395 395 static void copy(const From& from, Digraph &to, 396 396 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { 397 to.clear();398 397 for (typename From::NodeIt it(from); it != INVALID; ++it) { 399 398 nodeRefMap[it] = to.addNode(); … … 423 422 static void copy(const From& from, Graph &to, 424 423 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 425 to.clear();426 424 for (typename From::NodeIt it(from); it != INVALID; ++it) { 427 425 nodeRefMap[it] = to.addNode(); -
lemon/dfs.h
r1010 r956 566 566 void start(Node t) 567 567 { 568 while ( !emptyQueue() && !(*_reached)[t])568 while ( !emptyQueue() && G->target(_stack[_stack_head])!=t ) 569 569 processNextArc(); 570 570 } … … 1513 1513 /// with addSource() before using this function. 1514 1514 void start(Node t) { 1515 while ( !emptyQueue() && !(*_reached)[t])1515 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t ) 1516 1516 processNextArc(); 1517 1517 } -
lemon/hartmann_orlin_mmc.h
r959 r956 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 dMap "ReadMap" concept.41 /// It must conform to the \ref concepts::Rea_data "Rea_data" 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 Mmc"Karp"'s original algorithm,102 /// It is an improved version of \ref Karp "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/network_simplex.h
r978 r956 1078 1078 ART_COST = std::numeric_limits<Cost>::max() / 2 + 1; 1079 1079 } else { 1080 ART_COST = 0;1080 ART_COST = std::numeric_limits<Cost>::min(); 1081 1081 for (int i = 0; i != _arc_num; ++i) { 1082 1082 if (_cost[i] > ART_COST) ART_COST = _cost[i]; … … 1590 1590 if (_sum_supply == 0) { 1591 1591 if (_stype == GEQ) { 1592 Cost max_pot = -std::numeric_limits<Cost>::max();1592 Cost max_pot = std::numeric_limits<Cost>::min(); 1593 1593 for (int i = 0; i != _node_num; ++i) { 1594 1594 if (_pi[i] > max_pot) max_pot = _pi[i]; -
lemon/preflow.h
r1029 r956 544 544 _flow->set(e, (*_capacity)[e]); 545 545 (*_excess)[u] += rem; 546 if (u != _target && !_level->active(u)) { 547 _level->activate(u); 548 } 546 549 } 547 550 } … … 553 556 _flow->set(e, 0); 554 557 (*_excess)[v] += rem; 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 558 if (v != _target && !_level->active(v)) { 559 _level->activate(v); 560 } 561 } 562 } 561 563 return true; 562 564 } … … 575 577 _phase = true; 576 578 577 while (true) { 579 Node n = _level->highestActive(); 580 int level = _level->highestActiveLevel(); 581 while (n != INVALID) { 578 582 int num = _node_num; 579 583 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 584 while (num > 0 && n != INVALID) { 589 585 Value excess = (*_excess)[n]; 590 586 int new_level = _level->maxLevel(); … … 652 648 _level->deactivate(n); 653 649 } 650 651 n = _level->highestActive(); 652 level = _level->highestActiveLevel(); 653 --num; 654 654 } 655 655 656 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 } 668 --num; 669 657 while (num > 0 && n != INVALID) { 670 658 Value excess = (*_excess)[n]; 671 659 int new_level = _level->maxLevel(); … … 733 721 _level->deactivate(n); 734 722 } 735 } 736 } 737 first_phase_done:; 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 } 738 736 } 739 737 -
test/CMakeLists.txt
r1035 r953 46 46 47 47 IF(LEMON_HAVE_LP) 48 IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer") 49 ADD_EXECUTABLE(lp_test lp_test.cc) 50 ELSE() 51 ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc) 52 ENDIF() 53 48 ADD_EXECUTABLE(lp_test lp_test.cc) 54 49 SET(LP_TEST_LIBS lemon) 55 50 … … 87 82 88 83 IF(LEMON_HAVE_MIP) 89 IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer") 90 ADD_EXECUTABLE(mip_test mip_test.cc) 91 ELSE() 92 ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc) 93 ENDIF() 94 84 ADD_EXECUTABLE(mip_test mip_test.cc) 95 85 SET(MIP_TEST_LIBS lemon) 96 86 … … 128 118 129 119 FOREACH(TEST_NAME ${TESTS}) 130 IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer") 131 ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc) 132 ELSE() 133 ADD_EXECUTABLE(${TEST_NAME} EXCLUDE_FROM_ALL ${TEST_NAME}.cc) 134 ENDIF() 120 ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc) 135 121 TARGET_LINK_LIBRARIES(${TEST_NAME} lemon) 136 122 ADD_TEST(${TEST_NAME} ${TEST_NAME}) 137 ADD_DEPENDENCIES(check ${TEST_NAME})138 123 ENDFOREACH() -
test/bellman_ford_test.cc
r960 r956 105 105 ::SetDistMap<concepts::ReadWriteMap<Node,Value> > 106 106 ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> > 107 ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> > 107 108 ::Create bf_test(gr,length); 108 109 -
test/dfs_test.cc
r1010 r956 51 51 "@attributes\n" 52 52 "source 0\n" 53 "target 5\n" 54 "source1 6\n" 55 "target1 3\n"; 56 53 "target 5\n"; 57 54 58 55 void checkDfsCompile() … … 183 180 Digraph G; 184 181 Node s, t; 185 Node s1, t1;186 182 187 183 std::istringstream input(test_lgf); … … 189 185 node("source", s). 190 186 node("target", t). 191 node("source1", s1).192 node("target1", t1).193 187 run(); 194 188 … … 217 211 218 212 { 219 Dfs<Digraph> dfs(G);220 check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");221 }222 223 {224 213 NullMap<Node,Arc> myPredMap; 225 214 dfs(G).predMap(myPredMap).run(s); -
test/graph_copy_test.cc
r984 r463 30 30 const int nn = 10; 31 31 32 // Build a digraph33 32 SmartDigraph from; 34 33 SmartDigraph::NodeMap<int> fnm(from); … … 53 52 } 54 53 55 // Test digraph copy56 54 ListDigraph to; 57 55 ListDigraph::NodeMap<int> tnm(to); … … 71 69 nodeCrossRef(ncr).arcCrossRef(ecr). 72 70 node(fn, tn).arc(fa, ta).run(); 73 74 check(countNodes(from) == countNodes(to), "Wrong copy.");75 check(countArcs(from) == countArcs(to), "Wrong copy.");76 71 77 72 for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) { … … 96 91 check(tn == nr[fn], "Wrong copy."); 97 92 check(ta == er[fa], "Wrong copy."); 98 99 // Test repeated copy100 digraphCopy(from, to).run();101 102 check(countNodes(from) == countNodes(to), "Wrong copy.");103 check(countArcs(from) == countArcs(to), "Wrong copy.");104 93 } 105 94 … … 107 96 const int nn = 10; 108 97 109 // Build a graph110 98 SmartGraph from; 111 99 SmartGraph::NodeMap<int> fnm(from); … … 135 123 } 136 124 137 // Test graph copy138 125 ListGraph to; 139 126 ListGraph::NodeMap<int> tnm(to); … … 157 144 nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr). 158 145 node(fn, tn).arc(fa, ta).edge(fe, te).run(); 159 160 check(countNodes(from) == countNodes(to), "Wrong copy.");161 check(countEdges(from) == countEdges(to), "Wrong copy.");162 check(countArcs(from) == countArcs(to), "Wrong copy.");163 146 164 147 for (SmartGraph::NodeIt it(from); it != INVALID; ++it) { … … 198 181 check(ta == ar[fa], "Wrong copy."); 199 182 check(te == er[fe], "Wrong copy."); 200 201 // Test repeated copy202 graphCopy(from, to).run();203 204 check(countNodes(from) == countNodes(to), "Wrong copy.");205 check(countEdges(from) == countEdges(to), "Wrong copy.");206 check(countArcs(from) == countArcs(to), "Wrong copy.");207 183 } 208 184 -
test/preflow_test.cc
r1029 r956 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 183 159 int main() { 184 160 … … 271 247 "The max flow value or the three min cut values are incorrect."); 272 248 273 initFlowTest();274 275 249 return 0; 276 250 }
Note: See TracChangeset
for help on using the changeset viewer.