Changes in / [883:87569cb5734d:943:a1fd7008a052] in lemon-1.2
- Files:
-
- 3 added
- 1 deleted
- 30 edited
-
AUTHORS (modified) (1 diff)
-
CMakeLists.txt (modified) (6 diffs)
-
cmake/FindCOIN.cmake (modified) (2 diffs)
-
configure.ac (modified) (2 diffs)
-
doc/CMakeLists.txt (modified) (2 diffs)
-
doc/Doxyfile.in (modified) (14 diffs)
-
doc/DoxygenLayout.xml (modified) (1 diff)
-
doc/lgf.dox (modified) (2 diffs)
-
doc/mainpage.dox (deleted)
-
doc/mainpage.dox.in (added)
-
lemon/CMakeLists.txt (modified) (2 diffs)
-
lemon/Makefile.am (modified) (1 diff)
-
lemon/bits/edge_set_extender.h (modified) (1 diff)
-
lemon/bits/graph_adaptor_extender.h (modified) (1 diff)
-
lemon/bits/path_dump.h (modified) (2 diffs)
-
lemon/bits/windows.cc (modified) (1 diff)
-
lemon/core.h (modified) (2 diffs)
-
lemon/cost_scaling.h (modified) (2 diffs)
-
lemon/dfs.h (modified) (2 diffs)
-
lemon/lemon.pc.cmake (added)
-
lemon/lgf_reader.h (modified) (3 diffs)
-
lemon/lp_base.h (modified) (4 diffs)
-
lemon/maps.h (modified) (1 diff)
-
lemon/network_simplex.h (modified) (2 diffs)
-
lemon/preflow.h (modified) (5 diffs)
-
test/CMakeLists.txt (modified) (7 diffs)
-
test/Makefile.am (modified) (2 diffs)
-
test/dfs_test.cc (modified) (4 diffs)
-
test/graph_copy_test.cc (modified) (8 diffs)
-
test/heap_test.cc (modified) (1 diff)
-
test/lgf_test.cc (added)
-
test/lp_test.cc (modified) (1 diff)
-
test/maps_test.cc (modified) (3 diffs)
-
test/preflow_test.cc (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
AUTHORS
r320 r924 24 24 25 25 Again, please visit the history of the old LEMON repository for more 26 details: http://lemon.cs.elte.hu/ svn/lemon/trunk26 details: http://lemon.cs.elte.hu/hg/lemon-0.x -
CMakeLists.txt
r744 r942 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) … … 39 118 40 119 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() 41 126 42 127 ADD_SUBDIRECTORY(lemon) … … 65 150 ENDIF() 66 151 67 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)152 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR}) 68 153 SET(CPACK_PACKAGE_NAME ${PROJECT_NAME}) 69 154 SET(CPACK_PACKAGE_VENDOR "EGRES") -
cmake/FindCOIN.cmake
r634 r920 6 6 FIND_LIBRARY(COIN_CBC_LIBRARY 7 7 NAMES Cbc libCbc 8 HINTS ${COIN_ROOT_DIR}/lib/coin 8 9 HINTS ${COIN_ROOT_DIR}/lib 9 10 ) 10 11 FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY 11 12 NAMES CbcSolver libCbcSolver 13 HINTS ${COIN_ROOT_DIR}/lib/coin 12 14 HINTS ${COIN_ROOT_DIR}/lib 13 15 ) 14 16 FIND_LIBRARY(COIN_CGL_LIBRARY 15 17 NAMES Cgl libCgl 18 HINTS ${COIN_ROOT_DIR}/lib/coin 16 19 HINTS ${COIN_ROOT_DIR}/lib 17 20 ) 18 21 FIND_LIBRARY(COIN_CLP_LIBRARY 19 22 NAMES Clp libClp 23 HINTS ${COIN_ROOT_DIR}/lib/coin 20 24 HINTS ${COIN_ROOT_DIR}/lib 21 25 ) 22 26 FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY 23 27 NAMES CoinUtils libCoinUtils 28 HINTS ${COIN_ROOT_DIR}/lib/coin 24 29 HINTS ${COIN_ROOT_DIR}/lib 25 30 ) 26 31 FIND_LIBRARY(COIN_OSI_LIBRARY 27 32 NAMES Osi libOsi 33 HINTS ${COIN_ROOT_DIR}/lib/coin 28 34 HINTS ${COIN_ROOT_DIR}/lib 29 35 ) 30 36 FIND_LIBRARY(COIN_OSI_CBC_LIBRARY 31 37 NAMES OsiCbc libOsiCbc 38 HINTS ${COIN_ROOT_DIR}/lib/coin 32 39 HINTS ${COIN_ROOT_DIR}/lib 33 40 ) 34 41 FIND_LIBRARY(COIN_OSI_CLP_LIBRARY 35 42 NAMES OsiClp libOsiClp 43 HINTS ${COIN_ROOT_DIR}/lib/coin 36 44 HINTS ${COIN_ROOT_DIR}/lib 37 45 ) 38 46 FIND_LIBRARY(COIN_OSI_VOL_LIBRARY 39 47 NAMES OsiVol libOsiVol 48 HINTS ${COIN_ROOT_DIR}/lib/coin 40 49 HINTS ${COIN_ROOT_DIR}/lib 41 50 ) 42 51 FIND_LIBRARY(COIN_VOL_LIBRARY 43 52 NAMES Vol libVol 53 HINTS ${COIN_ROOT_DIR}/lib/coin 44 54 HINTS ${COIN_ROOT_DIR}/lib 45 55 ) … … 56 66 COIN_OSI_CBC_LIBRARY 57 67 COIN_OSI_CLP_LIBRARY 58 COIN_OSI_VOL_LIBRARY59 COIN_VOL_LIBRARY68 # COIN_OSI_VOL_LIBRARY 69 # COIN_VOL_LIBRARY 60 70 ) 61 71 62 72 IF(COIN_FOUND) 63 73 SET(COIN_INCLUDE_DIRS ${COIN_INCLUDE_DIR}) 64 SET(COIN_LIBRARIES "${COIN_CBC_LIBRARY};${COIN_CBC_SOLVER_LIBRARY};${COIN_CGL_LIBRARY};${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY};${COIN_OSI_LIBRARY};${COIN_OSI_CBC_LIBRARY};${COIN_OSI_CLP_LIBRARY} ;${COIN_OSI_VOL_LIBRARY};${COIN_VOL_LIBRARY}")74 SET(COIN_LIBRARIES "${COIN_CBC_LIBRARY};${COIN_CBC_SOLVER_LIBRARY};${COIN_CGL_LIBRARY};${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY};${COIN_OSI_LIBRARY};${COIN_OSI_CBC_LIBRARY};${COIN_OSI_CLP_LIBRARY}") 65 75 SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY}") 66 76 SET(COIN_CBC_LIBRARIES ${COIN_LIBRARIES}) -
configure.ac
r793 r908 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
r865 r942 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
r756 r942 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 … … 92 98 "@abs_top_srcdir@/tools" \ 93 99 "@abs_top_srcdir@/test/test_tools.h" \ 100 "@abs_top_builddir@/doc/mainpage.dox" \ 94 101 "@abs_top_builddir@/doc/references.dox" 95 102 INPUT_ENCODING = UTF-8 … … 112 119 FILTER_PATTERNS = 113 120 FILTER_SOURCE_FILES = NO 121 FILTER_SOURCE_PATTERNS = 114 122 #--------------------------------------------------------------------------- 115 123 # configuration options related to source browsing 116 124 #--------------------------------------------------------------------------- 117 SOURCE_BROWSER = NO125 SOURCE_BROWSER = @LEMON_DOC_SOURCE_BROWSER@ 118 126 INLINE_SOURCES = NO 119 127 STRIP_CODE_COMMENTS = YES … … 138 146 HTML_FOOTER = 139 147 HTML_STYLESHEET = 148 HTML_COLORSTYLE_HUE = 220 149 HTML_COLORSTYLE_SAT = 100 150 HTML_COLORSTYLE_GAMMA = 80 151 HTML_TIMESTAMP = YES 140 152 HTML_ALIGN_MEMBERS = YES 141 HTML_DYNAMIC_SECTIONS = NO153 HTML_DYNAMIC_SECTIONS = YES 142 154 GENERATE_DOCSET = NO 143 155 DOCSET_FEEDNAME = "Doxygen generated docs" 144 156 DOCSET_BUNDLE_ID = org.doxygen.Project 157 DOCSET_PUBLISHER_ID = org.doxygen.Publisher 158 DOCSET_PUBLISHER_NAME = Publisher 145 159 GENERATE_HTMLHELP = NO 146 160 CHM_FILE = … … 154 168 QHP_NAMESPACE = org.doxygen.Project 155 169 QHP_VIRTUAL_FOLDER = doc 170 QHP_CUST_FILTER_NAME = 171 QHP_CUST_FILTER_ATTRS = 172 QHP_SECT_FILTER_ATTRS = 156 173 QHG_LOCATION = 174 GENERATE_ECLIPSEHELP = NO 175 ECLIPSE_DOC_ID = org.doxygen.Project 157 176 DISABLE_INDEX = NO 158 177 ENUM_VALUES_PER_LINE = 4 159 178 GENERATE_TREEVIEW = NO 179 USE_INLINE_TREES = NO 160 180 TREEVIEW_WIDTH = 250 181 EXT_LINKS_IN_WINDOW = NO 161 182 FORMULA_FONTSIZE = 10 183 FORMULA_TRANSPARENT = YES 184 USE_MATHJAX = NO 185 MATHJAX_RELPATH = http://www.mathjax.org/mathjax 186 SEARCHENGINE = YES 187 SERVER_BASED_SEARCH = NO 162 188 #--------------------------------------------------------------------------- 163 189 # configuration options related to the LaTeX output … … 176 202 LATEX_BATCHMODE = NO 177 203 LATEX_HIDE_INDICES = NO 204 LATEX_SOURCE_CODE = NO 178 205 #--------------------------------------------------------------------------- 179 206 # configuration options related to the RTF output … … 224 251 SKIP_FUNCTION_MACROS = YES 225 252 #--------------------------------------------------------------------------- 226 # Options related to the search engine227 #--------------------------------------------------------------------------- 228 TAGFILES = "@abs_top_ srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ "253 # Configuration::additions related to external references 254 #--------------------------------------------------------------------------- 255 TAGFILES = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ " 229 256 GENERATE_TAGFILE = html/lemon.tag 230 257 ALLEXTERNALS = NO … … 238 265 HIDE_UNDOC_RELATIONS = YES 239 266 HAVE_DOT = YES 267 DOT_NUM_THREADS = 0 240 268 DOT_FONTNAME = FreeSans 241 269 DOT_FONTSIZE = 10 … … 255 283 DOT_PATH = 256 284 DOTFILE_DIRS = 285 MSCFILE_DIRS = 257 286 DOT_GRAPH_MAX_NODES = 50 258 287 MAX_DOT_GRAPH_DEPTH = 0 … … 261 290 GENERATE_LEGEND = YES 262 291 DOT_CLEANUP = YES 263 #---------------------------------------------------------------------------264 # Configuration::additions related to the search engine265 #---------------------------------------------------------------------------266 SEARCHENGINE = NO -
doc/DoxygenLayout.xml
r316 r906 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/lgf.dox
r440 r923 64 64 \endcode 65 65 66 The \c \@arcs section is very similar to the \c \@nodes section, 67 it again starts with a header line describing the names of the maps, 68 butthe \c "label" map is not obligatory here. The following lines69 describe the arcs. The first two tokens of each line are 70 the sourceand the target node of the arc, respectively, then come the map66 The \c \@arcs section is very similar to the \c \@nodes section, it 67 again starts with a header line describing the names of the maps, but 68 the \c "label" map is not obligatory here. The following lines 69 describe the arcs. The first two tokens of each line are the source 70 and the target node of the arc, respectively, then come the map 71 71 values. The source and target tokens must be node labels. 72 72 … … 79 79 \endcode 80 80 81 If there is no map in the \c \@arcs section at all, then it must be 82 indicated by a sole '-' sign in the first line. 83 84 \code 85 @arcs 86 - 87 1 2 88 1 3 89 2 3 90 \endcode 91 81 92 The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can 82 93 also store the edge set of an undirected graph. In such case there is 83 94 a conventional method for store arc maps in the file, if two columns 84 ha sthe same caption with \c '+' and \c '-' prefix, then these columns95 have the same caption with \c '+' and \c '-' prefix, then these columns 85 96 can be regarded as the values of an arc map. 86 97 -
lemon/CMakeLists.txt
r679 r904 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
r874 r942 1 1 EXTRA_DIST += \ 2 2 lemon/lemon.pc.in \ 3 lemon/lemon.pc.cmake \ 3 4 lemon/CMakeLists.txt \ 4 5 lemon/config.h.cmake -
lemon/bits/edge_set_extender.h
r877 r942 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
r617 r886 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
r529 r890 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
r877 r914 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/core.h
r877 r942 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(); -
lemon/cost_scaling.h
r877 r909 908 908 break; 909 909 case AUGMENT: 910 startAugment( );910 startAugment(_res_node_num - 1); 911 911 break; 912 912 case PARTIAL_AUGMENT: … … 1085 1085 1086 1086 /// Execute the algorithm performing augment and relabel operations 1087 void startAugment(int max_length = std::numeric_limits<int>::max()) {1087 void startAugment(int max_length) { 1088 1088 // Paramters for heuristics 1089 1089 const int EARLY_TERM_EPSILON_LIMIT = 1000; -
lemon/dfs.h
r877 r942 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/lgf_reader.h
r877 r942 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 05 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 965 965 int index = 0; 966 966 while (_reader_bits::readToken(line, map)) { 967 if(map == "-") { 968 if(index!=0) 969 throw FormatError("'-' is not allowed as a map name"); 970 else if (line >> std::ws >> c) 971 throw FormatError("Extra character at the end of line"); 972 else break; 973 } 967 974 if (maps.find(map) != maps.end()) { 968 975 std::ostringstream msg; … … 1835 1842 int index = 0; 1836 1843 while (_reader_bits::readToken(line, map)) { 1844 if(map == "-") { 1845 if(index!=0) 1846 throw FormatError("'-' is not allowed as a map name"); 1847 else if (line >> std::ws >> c) 1848 throw FormatError("Extra character at the end of line"); 1849 else break; 1850 } 1837 1851 if (maps.find(map) != maps.end()) { 1838 1852 std::ostringstream msg; -
lemon/lp_base.h
r877 r933 1619 1619 inline LpBase::Constr operator<=(const LpBase::Expr &e, 1620 1620 const LpBase::Expr &f) { 1621 return LpBase::Constr(0, f - e, LpBase:: INF);1621 return LpBase::Constr(0, f - e, LpBase::NaN); 1622 1622 } 1623 1623 … … 1637 1637 inline LpBase::Constr operator<=(const LpBase::Expr &e, 1638 1638 const LpBase::Value &f) { 1639 return LpBase::Constr( - LpBase::INF, e, f);1639 return LpBase::Constr(LpBase::NaN, e, f); 1640 1640 } 1641 1641 … … 1646 1646 inline LpBase::Constr operator>=(const LpBase::Expr &e, 1647 1647 const LpBase::Expr &f) { 1648 return LpBase::Constr(0, e - f, LpBase:: INF);1648 return LpBase::Constr(0, e - f, LpBase::NaN); 1649 1649 } 1650 1650 … … 1666 1666 inline LpBase::Constr operator>=(const LpBase::Expr &e, 1667 1667 const LpBase::Value &f) { 1668 return LpBase::Constr(f, e, LpBase:: INF);1668 return LpBase::Constr(f, e, LpBase::NaN); 1669 1669 } 1670 1670 -
lemon/maps.h
r877 r915 3253 3253 virtual void add(const Key& key) { 3254 3254 Parent::add(key); 3255 unlace(key);3255 lace(key); 3256 3256 } 3257 3257 -
lemon/network_simplex.h
r877 r892 1078 1078 ART_COST = std::numeric_limits<Cost>::max() / 2 + 1; 1079 1079 } else { 1080 ART_COST = std::numeric_limits<Cost>::min();1080 ART_COST = 0; 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>::min();1592 Cost max_pot = -std::numeric_limits<Cost>::max(); 1593 1593 for (int i = 0; i != _node_num; ++i) { 1594 1594 if (_pi[i] > max_pot) max_pot = _pi[i]; -
lemon/preflow.h
r877 r942 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
r874 r942 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 … … 30 34 heap_test 31 35 kruskal_test 36 lgf_test 32 37 maps_test 33 38 matching_test … … 46 51 47 52 IF(LEMON_HAVE_LP) 48 ADD_EXECUTABLE(lp_test lp_test.cc) 53 IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer") 54 ADD_EXECUTABLE(lp_test lp_test.cc) 55 ELSE() 56 ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc) 57 ENDIF() 58 49 59 SET(LP_TEST_LIBS lemon) 50 60 … … 61 71 TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS}) 62 72 ADD_TEST(lp_test lp_test) 73 ADD_DEPENDENCIES(check lp_test) 63 74 64 75 IF(WIN32 AND LEMON_HAVE_GLPK) … … 82 93 83 94 IF(LEMON_HAVE_MIP) 84 ADD_EXECUTABLE(mip_test mip_test.cc) 95 IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer") 96 ADD_EXECUTABLE(mip_test mip_test.cc) 97 ELSE() 98 ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc) 99 ENDIF() 100 85 101 SET(MIP_TEST_LIBS lemon) 86 102 … … 97 113 TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS}) 98 114 ADD_TEST(mip_test mip_test) 115 ADD_DEPENDENCIES(check mip_test) 99 116 100 117 IF(WIN32 AND LEMON_HAVE_GLPK) … … 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
r874 r942 32 32 test/heap_test \ 33 33 test/kruskal_test \ 34 test/lgf_test \ 34 35 test/maps_test \ 35 36 test/matching_test \ … … 81 82 test_kruskal_test_SOURCES = test/kruskal_test.cc 82 83 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc 84 test_lgf_test_SOURCES = test/lgf_test.cc 83 85 test_lp_test_SOURCES = test/lp_test.cc 84 86 test_maps_test_SOURCES = test/maps_test.cc -
test/dfs_test.cc
r877 r942 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
r440 r896 30 30 const int nn = 10; 31 31 32 // Build a digraph 32 33 SmartDigraph from; 33 34 SmartDigraph::NodeMap<int> fnm(from); … … 52 53 } 53 54 55 // Test digraph copy 54 56 ListDigraph to; 55 57 ListDigraph::NodeMap<int> tnm(to); … … 69 71 nodeCrossRef(ncr).arcCrossRef(ecr). 70 72 node(fn, tn).arc(fa, ta).run(); 73 74 check(countNodes(from) == countNodes(to), "Wrong copy."); 75 check(countArcs(from) == countArcs(to), "Wrong copy."); 71 76 72 77 for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) { … … 91 96 check(tn == nr[fn], "Wrong copy."); 92 97 check(ta == er[fa], "Wrong copy."); 98 99 // Test repeated copy 100 digraphCopy(from, to).run(); 101 102 check(countNodes(from) == countNodes(to), "Wrong copy."); 103 check(countArcs(from) == countArcs(to), "Wrong copy."); 93 104 } 94 105 … … 96 107 const int nn = 10; 97 108 109 // Build a graph 98 110 SmartGraph from; 99 111 SmartGraph::NodeMap<int> fnm(from); … … 123 135 } 124 136 137 // Test graph copy 125 138 ListGraph to; 126 139 ListGraph::NodeMap<int> tnm(to); … … 144 157 nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr). 145 158 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."); 146 163 147 164 for (SmartGraph::NodeIt it(from); it != INVALID; ++it) { … … 181 198 check(ta == ar[fa], "Wrong copy."); 182 199 check(te == er[fe], "Wrong copy."); 200 201 // Test repeated copy 202 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."); 183 207 } 184 208 -
test/heap_test.cc
r855 r921 273 273 } 274 274 275 { 276 typedef FibHeap<Prio, ItemIntMap> IntHeap; 277 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 278 heapSortTest<IntHeap>(); 279 heapIncreaseTest<IntHeap>(); 280 281 typedef FibHeap<Prio, IntNodeMap > NodeHeap; 282 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 283 dijkstraHeapTest<NodeHeap>(digraph, length, source); 284 } 285 286 { 287 typedef RadixHeap<ItemIntMap> IntHeap; 288 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 289 heapSortTest<IntHeap>(); 290 heapIncreaseTest<IntHeap>(); 291 292 typedef RadixHeap<IntNodeMap > NodeHeap; 293 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 294 dijkstraHeapTest<NodeHeap>(digraph, length, source); 295 } 296 297 { 298 typedef BucketHeap<ItemIntMap> IntHeap; 299 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 300 heapSortTest<IntHeap>(); 301 heapIncreaseTest<IntHeap>(); 302 303 typedef BucketHeap<IntNodeMap > NodeHeap; 304 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 305 dijkstraHeapTest<NodeHeap>(digraph, length, source); 306 } 307 308 275 309 return 0; 276 310 } -
test/lp_test.cc
r631 r932 167 167 c = ((2 >= p1) >= 3); 168 168 169 { //Tests for #430 170 LP::Col v=lp.addCol(); 171 LP::Constr c = v >= -3; 172 c = c <= 4; 173 LP::Constr c2; 174 c2 = -3 <= v <= 4; 175 } 176 169 177 e[x[3]]=2; 170 178 e[x[3]]=4; -
test/maps_test.cc
r877 r915 642 642 const int num = 10; 643 643 Graph g; 644 Ibm map0(g, true); 644 645 std::vector<Item> items; 645 646 for (int i = 0; i < num; ++i) { … … 723 724 const int num = 10; 724 725 Graph g; 726 Iim map0(g, 0); 725 727 std::vector<Item> items; 726 728 for (int i = 0; i < num; ++i) { … … 773 775 const int num = 10; 774 776 Graph g; 777 Ivm map0(g, 0.0); 775 778 std::vector<Item> items; 776 779 for (int i = 0; i < num; ++i) { -
test/preflow_test.cc
r877 r902 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.
