Changes in / [906:e24922c56bc2:907:1937b6455b7d] in lemon-main
- Files:
-
- 100 added
- 1 deleted
- 110 edited
Legend:
- Unmodified
- Added
- Removed
-
.hgignore
r494 r866 23 23 lemon/stamp-h2 24 24 doc/Doxyfile 25 cmake/cmake.version 25 doc/references.dox 26 cmake/version.cmake 26 27 .dirstamp 27 28 .libs/* 28 29 .deps/* 29 30 demo/*.eps 31 m4/libtool.m4 32 m4/ltoptions.m4 33 m4/ltsugar.m4 34 m4/ltversion.m4 35 m4/lt~obsolete.m4 30 36 31 37 syntax: regexp … … 36 42 ^autom4te.cache/.* 37 43 ^build-aux/.* 38 ^ objs.*/.*44 ^.*objs.*/.* 39 45 ^test/[a-z_]*$ 46 ^tools/[a-z-_]*$ 40 47 ^demo/.*_demo$ 41 ^ build/.*48 ^.*build.*/.* 42 49 ^doc/gen-images/.* 43 50 CMakeFiles -
CMakeLists.txt
r511 r902 1 1 CMAKE_MINIMUM_REQUIRED(VERSION 2.6) 2 2 3 IF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake) 4 INCLUDE(${CMAKE_SOURCE_DIR}/cmake/version.cmake) 5 ELSE(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake) 6 SET(PROJECT_NAME "LEMON") 7 SET(PROJECT_VERSION "hg-tip" CACHE STRING "LEMON version string.") 8 ENDIF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake) 9 3 SET(PROJECT_NAME "LEMON") 10 4 PROJECT(${PROJECT_NAME}) 11 5 12 SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake) 13 14 INCLUDE(FindDoxygen) 15 INCLUDE(FindGhostscript) 16 17 ADD_DEFINITIONS(-DHAVE_CONFIG_H) 6 INCLUDE(FindPythonInterp) 7 8 IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake) 9 INCLUDE(${PROJECT_SOURCE_DIR}/cmake/version.cmake) 10 ELSEIF(DEFINED ENV{LEMON_VERSION}) 11 SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.") 12 ELSE() 13 EXECUTE_PROCESS( 14 COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py 15 WORKING_DIRECTORY ${PROJECT_SOURCE_DIR} 16 OUTPUT_VARIABLE HG_REVISION_PATH 17 ERROR_QUIET 18 OUTPUT_STRIP_TRAILING_WHITESPACE 19 ) 20 EXECUTE_PROCESS( 21 COMMAND hg id -i 22 WORKING_DIRECTORY ${PROJECT_SOURCE_DIR} 23 OUTPUT_VARIABLE HG_REVISION 24 ERROR_QUIET 25 OUTPUT_STRIP_TRAILING_WHITESPACE 26 ) 27 IF(HG_REVISION STREQUAL "") 28 SET(HG_REVISION_ID "hg-tip") 29 ELSE() 30 IF(HG_REVISION_PATH STREQUAL "") 31 SET(HG_REVISION_ID ${HG_REVISION}) 32 ELSE() 33 SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION}) 34 ENDIF() 35 ENDIF() 36 SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.") 37 ENDIF() 38 39 SET(PROJECT_VERSION ${LEMON_VERSION}) 40 41 SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake) 42 43 FIND_PACKAGE(Doxygen) 44 FIND_PACKAGE(Ghostscript) 45 FIND_PACKAGE(GLPK 4.33) 46 FIND_PACKAGE(CPLEX) 47 FIND_PACKAGE(COIN) 48 49 IF(DEFINED ENV{LEMON_CXX_WARNING}) 50 SET(CXX_WARNING $ENV{LEMON_CXX_WARNING}) 51 ELSE() 52 IF(CMAKE_COMPILER_IS_GNUCXX) 53 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") 54 SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb") 55 SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb") 56 ELSEIF(MSVC) 57 # This part is unnecessary 'casue the same is set by the lemon/core.h. 58 # Still keep it as an example. 59 SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996") 60 # Suppressed warnings: 61 # C4250: 'class1' : inherits 'class2::member' via dominance 62 # C4355: 'this' : used in base member initializer list 63 # C4503: 'function' : decorated name length exceeded, name was truncated 64 # C4800: 'type' : forcing value to bool 'true' or 'false' 65 # (performance warning) 66 # C4996: 'function': was declared deprecated 67 ELSE() 68 SET(CXX_WARNING "-Wall -W") 69 ENDIF() 70 ENDIF() 71 SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.") 72 73 SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}") 74 75 SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb" CACHE STRING 76 "Flags used by the C++ compiler during maintainer builds." 77 FORCE ) 78 SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING 79 "Flags used by the C compiler during maintainer builds." 80 FORCE ) 81 SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER 82 "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING 83 "Flags used for linking binaries during maintainer builds." 84 FORCE ) 85 SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER 86 "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING 87 "Flags used by the shared libraries linker during maintainer builds." 88 FORCE ) 89 MARK_AS_ADVANCED( 90 CMAKE_CXX_FLAGS_MAINTAINER 91 CMAKE_C_FLAGS_MAINTAINER 92 CMAKE_EXE_LINKER_FLAGS_MAINTAINER 93 CMAKE_SHARED_LINKER_FLAGS_MAINTAINER ) 94 95 IF(CMAKE_CONFIGURATION_TYPES) 96 LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer) 97 LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES) 98 SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING 99 "Add the configurations that we need" 100 FORCE) 101 endif() 102 103 IF(NOT CMAKE_BUILD_TYPE) 104 SET(CMAKE_BUILD_TYPE "Release") 105 ENDIF() 106 107 SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING 108 "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer." 109 FORCE ) 110 18 111 19 112 INCLUDE(CheckTypeSize) 20 CHECK_TYPE_SIZE("long long" LEMON_LONG_LONG) 113 CHECK_TYPE_SIZE("long long" LONG_LONG) 114 SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG}) 21 115 22 116 ENABLE_TESTING() 23 117 118 IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer") 119 ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND}) 120 ELSE() 121 ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND}) 122 ENDIF() 123 24 124 ADD_SUBDIRECTORY(lemon) 25 ADD_SUBDIRECTORY(demo) 26 ADD_SUBDIRECTORY(doc) 27 ADD_SUBDIRECTORY(test) 28 29 IF(WIN32) 125 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR}) 126 ADD_SUBDIRECTORY(demo) 127 ADD_SUBDIRECTORY(tools) 128 ADD_SUBDIRECTORY(doc) 129 ADD_SUBDIRECTORY(test) 130 ENDIF() 131 132 CONFIGURE_FILE( 133 ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in 134 ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake 135 @ONLY 136 ) 137 IF(UNIX) 138 INSTALL( 139 FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake 140 DESTINATION share/lemon/cmake 141 ) 142 ELSEIF(WIN32) 143 INSTALL( 144 FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake 145 DESTINATION cmake 146 ) 147 ENDIF() 148 149 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR}) 30 150 SET(CPACK_PACKAGE_NAME ${PROJECT_NAME}) 31 151 SET(CPACK_PACKAGE_VENDOR "EGRES") 32 152 SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY 33 "LEMON - Library of Efficient Modelsand Optimization in Networks")34 SET(CPACK_RESOURCE_FILE_LICENSE "${ CMAKE_SOURCE_DIR}/LICENSE")153 "LEMON - Library for Efficient Modeling and Optimization in Networks") 154 SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE") 35 155 36 156 SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION}) … … 41 161 "${PROJECT_NAME} ${PROJECT_VERSION}") 42 162 43 SET(CPACK_COMPONENTS_ALL headers library html_documentation )163 SET(CPACK_COMPONENTS_ALL headers library html_documentation bin) 44 164 45 165 SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers") 46 166 SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library") 167 SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities") 47 168 SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation") 48 169 … … 51 172 SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION 52 173 "DLL and import library") 174 SET(CPACK_COMPONENT_BIN_DESCRIPTION 175 "Command line utilities") 53 176 SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION 54 177 "Doxygen generated documentation") … … 72 195 73 196 SET(CPACK_GENERATOR "NSIS") 74 SET(CPACK_NSIS_MUI_ICON "${ CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")75 SET(CPACK_NSIS_MUI_UNIICON "${ CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")76 #SET(CPACK_PACKAGE_ICON "${ CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")197 SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico") 198 SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico") 199 #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp") 77 200 SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico") 78 201 SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}") … … 89 212 90 213 INCLUDE(CPack) 91 ENDIF( WIN32)214 ENDIF() -
INSTALL
r504 r824 28 28 29 29 This command compiles the non-template part of LEMON into libemon.a 30 file. It also compiles the programs in the tools and demo subdirectories31 when enabled.30 file. It also compiles the programs in the tools subdirectory by 31 default. 32 32 33 33 4. `make check' … … 75 75 76 76 Set the installation prefix to PREFIX. By default it is /usr/local. 77 78 --enable-demo79 80 Build the examples in the demo subdirectory.81 82 --disable-demo83 84 Do not build the examples in the demo subdirectory (default).85 77 86 78 --enable-tools … … 159 151 160 152 Disable SoPlex support. 153 154 --with-coin[=PREFIX] 155 156 Enable support for COIN-OR solvers (CLP and CBC). You should 157 specify the prefix too. (by default, COIN-OR tools install 158 themselves to the source code directory). This command enables the 159 solvers that are actually found. 160 161 --with-coin-includedir=DIR 162 163 The directory where the COIN-OR header files are located. This is 164 only useful when the COIN-OR headers and libraries are not under 165 the same prefix (which is unlikely). 166 167 --with-coin-libdir=DIR 168 169 The directory where the COIN-OR libraries are located. This is only 170 useful when the COIN-OR headers and libraries are not under the 171 same prefix (which is unlikely). 172 173 --without-coin 174 175 Disable COIN-OR support. 176 177 178 Makefile Variables 179 ================== 180 181 Some Makefile variables are reserved by the GNU Coding Standards for 182 the use of the "user" - the person building the package. For instance, 183 CXX and CXXFLAGS are such variables, and have the same meaning as 184 explained in the previous section. These variables can be set on the 185 command line when invoking `make' like this: 186 `make [VARIABLE=VALUE]...' 187 188 WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us 189 to hold several compiler flags related to warnings. Its default value 190 can be overridden when invoking `make'. For example to disable all 191 warning flags use `make WARNINGCXXFLAGS='. 192 193 In order to turn off a single flag from the default set of warning 194 flags, you can use the CXXFLAGS variable, since this is passed after 195 WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is 196 used by default when g++ is detected) you can use 197 `make CXXFLAGS="-g -O2 -Wno-old-style-cast"'. -
LICENSE
r506 r879 2 2 copyright/license. 3 3 4 Copyright (C) 2003-20 08Egervary Jeno Kombinatorikus Optimalizalasi4 Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi 5 5 Kutatocsoport (Egervary Combinatorial Optimization Research Group, 6 6 EGRES). -
Makefile.am
r480 r793 1 1 ACLOCAL_AMFLAGS = -I m4 2 3 AM_CXXFLAGS = $(WARNINGCXXFLAGS) 2 4 3 5 AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir) … … 10 12 m4/lx_check_glpk.m4 \ 11 13 m4/lx_check_soplex.m4 \ 14 m4/lx_check_coin.m4 \ 12 15 CMakeLists.txt \ 13 16 cmake/FindGhostscript.cmake \ 17 cmake/FindCPLEX.cmake \ 18 cmake/FindGLPK.cmake \ 19 cmake/FindCOIN.cmake \ 20 cmake/LEMONConfig.cmake.in \ 14 21 cmake/version.cmake.in \ 15 22 cmake/version.cmake \ … … 37 44 include test/Makefile.am 38 45 include doc/Makefile.am 39 include demo/Makefile.am40 46 include tools/Makefile.am 47 include scripts/Makefile.am 48 49 DIST_SUBDIRS = demo 50 51 demo: 52 $(MAKE) $(AM_MAKEFLAGS) -C demo 41 53 42 54 MRPROPERFILES = \ … … 66 78 bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2 67 79 68 .PHONY: mrproper dist-bz2 distcheck-bz280 .PHONY: demo mrproper dist-bz2 distcheck-bz2 -
NEWS
r507 r881 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 81 2009-05-13 Version 1.1 released 82 83 This is the second stable release of the 1.x series. It 84 features a better coverage of the tools available in the 0.x 85 series, a thoroughly reworked LP/MIP interface plus various 86 improvements in the existing tools. 87 88 * Much improved M$ Windows support 89 * Various improvements in the CMAKE build system 90 * Compilation warnings are fixed/suppressed 91 * Support IBM xlC compiler 92 * New algorithms 93 * Connectivity related algorithms (#61) 94 * Euler walks (#65) 95 * Preflow push-relabel max. flow algorithm (#176) 96 * Circulation algorithm (push-relabel based) (#175) 97 * Suurballe algorithm (#47) 98 * Gomory-Hu algorithm (#66) 99 * Hao-Orlin algorithm (#58) 100 * Edmond's maximum cardinality and weighted matching algorithms 101 in general graphs (#48,#265) 102 * Minimum cost arborescence/branching (#60) 103 * Network Simplex min. cost flow algorithm (#234) 104 * New data structures 105 * Full graph structure (#57) 106 * Grid graph structure (#57) 107 * Hypercube graph structure (#57) 108 * Graph adaptors (#67) 109 * ArcSet and EdgeSet classes (#67) 110 * Elevator class (#174) 111 * Other new tools 112 * LP/MIP interface (#44) 113 * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC 114 * Reader for the Nauty file format (#55) 115 * DIMACS readers (#167) 116 * Radix sort algorithms (#72) 117 * RangeIdMap and CrossRefMap (#160) 118 * New command line tools 119 * DIMACS to LGF converter (#182) 120 * lgf-gen - a graph generator (#45) 121 * DIMACS solver utility (#226) 122 * Other code improvements 123 * Lognormal distribution added to Random (#102) 124 * Better (i.e. O(1) time) item counting in SmartGraph (#3) 125 * The standard maps of graphs are guaranteed to be 126 reference maps (#190) 127 * Miscellaneous 128 * Various doc improvements 129 * Improved 0.x -> 1.x converter script 130 131 * Several bugfixes (compared to release 1.0): 132 #170: Bugfix SmartDigraph::split() 133 #171: Bugfix in SmartGraph::restoreSnapshot() 134 #172: Extended test cases for graphs and digraphs 135 #173: Bugfix in Random 136 * operator()s always return a double now 137 * the faulty real<Num>(Num) and real<Num>(Num,Num) 138 have been removed 139 #187: Remove DijkstraWidestPathOperationTraits 140 #61: Bugfix in DfsVisit 141 #193: Bugfix in GraphReader::skipSection() 142 #195: Bugfix in ConEdgeIt() 143 #197: Bugfix in heap unionfind 144 * This bug affects Edmond's general matching algorithms 145 #207: Fix 'make install' without 'make html' using CMAKE 146 #208: Suppress or fix VS2008 compilation warnings 147 ----: Update the LEMON icon 148 ----: Enable the component-based installer 149 (in installers made by CPACK) 150 ----: Set the proper version for CMAKE in the tarballs 151 (made by autotools) 152 ----: Minor clarification in the LICENSE file 153 ----: Add missing unistd.h include to time_measure.h 154 #204: Compilation bug fixed in graph_to_eps.h with VS2005 155 #214,#215: windows.h should never be included by LEMON headers 156 #230: Build systems check the availability of 'long long' type 157 #229: Default implementation of Tolerance<> is used for integer types 158 #211,#212: Various fixes for compiling on AIX 159 ----: Improvements in CMAKE config 160 - docs is installed in share/doc/ 161 - detects newer versions of Ghostscript 162 #239: Fix missing 'inline' specifier in time_measure.h 163 #274,#280: Install lemon/config.h 164 #275: Prefix macro names with LEMON_ in lemon/config.h 165 ----: Small script for making the release tarballs added 166 ----: Minor improvement in unify-sources.sh (a76f55d7d397) 167 1 168 2009-03-27 LEMON joins to the COIN-OR initiative 2 169 … … 8 175 2008-10-13 Version 1.0 released 9 176 10 11 12 13 14 15 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 16 183 Migration Guide in the doc for more details) 17 184 * Graph -> Digraph, UGraph -> Graph 18 185 * Edge -> Arc, UEdge -> Edge 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 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) 37 204 * Concepts 38 205 * graph structure concepts (concepts/digraph.h, concepts/graph.h, 39 206 concepts/graph_components.h) 40 41 42 43 44 45 46 47 48 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 49 216 (lgf_reader.h, lgf_writer.h) 50 217 * tools to handle the anomalies of calculations with 51 218 floating point numbers (tolerance.h) 52 219 * tools to manage RGB colors (color.h) 53 54 55 56 57 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) -
README
r318 r848 1 ================================================================== 2 LEMON - a Library of Efficient Modelsand Optimization in Networks3 ================================================================== 1 ===================================================================== 2 LEMON - a Library for Efficient Modeling and Optimization in Networks 3 ===================================================================== 4 4 5 5 LEMON is an open source library written in C++. It provides … … 17 17 18 18 Copying, distribution and modification conditions and terms. 19 20 NEWS 21 22 News and version history. 19 23 20 24 INSTALL … … 34 38 Some example programs to make you easier to get familiar with LEMON. 35 39 40 scripts/ 41 42 Scripts that make it easier to develop LEMON. 43 36 44 test/ 37 45 -
cmake/version.cmake.in
r480 r678 1 SET(PROJECT_NAME "@PACKAGE_NAME@") 2 SET(PROJECT_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.") 1 SET(LEMON_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.") -
configure.ac
r511 r793 3 3 dnl Version information. 4 4 m4_define([lemon_version_number], 5 5 [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))]) 6 6 dnl m4_define([lemon_version_number], []) 7 7 m4_define([lemon_hg_path], [m4_normalize(esyscmd([./scripts/chg-len.py]))]) 8 m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i ]))])8 m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i 2> /dev/null]))]) 9 9 m4_define([lemon_version], [ifelse(lemon_version_number(), 10 [], 11 [lemon_hg_path().lemon_hg_revision()], 12 [lemon_version_number()])]) 10 [], 11 [ifelse(lemon_hg_revision(), 12 [], 13 [hg-tip], 14 [lemon_hg_path().lemon_hg_revision()])], 15 [lemon_version_number()])]) 13 16 14 17 AC_PREREQ([2.59]) … … 20 23 AC_CONFIG_HEADERS([config.h lemon/config.h]) 21 24 22 lx_cmdline_cxxflags_set=${CXXFLAGS+set} 25 AC_DEFINE([LEMON_VERSION], [lemon_version()], [The version string]) 23 26 24 27 dnl Do compilation tests using the C++ compiler. … … 39 42 40 43 AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no]) 44 AC_CHECK_PROG([python_found],[python],[yes],[no]) 41 45 AC_CHECK_PROG([gs_found],[gs],[yes],[no]) 42 46 … … 53 57 54 58 dnl Set custom compiler flags when using g++. 55 if test x"$lx_cmdline_cxxflags_set" != x"set" -a"$GXX" = yes -a "$ICC" = no; then56 CXXFLAGS="$CXXFLAGS -Wall -W -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-Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"59 if test "$GXX" = yes -a "$ICC" = no; then 60 WARNINGCXXFLAGS="-Wall -W -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" 57 61 fi 62 AC_SUBST([WARNINGCXXFLAGS]) 58 63 59 64 dnl Checks for libraries. 60 #LX_CHECK_GLPK 61 #LX_CHECK_CPLEX 62 #LX_CHECK_SOPLEX 65 LX_CHECK_GLPK 66 LX_CHECK_CPLEX 67 LX_CHECK_SOPLEX 68 LX_CHECK_COIN 63 69 64 dnl Disable/enable building the demo programs. 65 AC_ARG_ENABLE([demo], 66 AS_HELP_STRING([--enable-demo], [build the demo programs]) 67 AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]), 68 [], [enable_demo=no]) 69 AC_MSG_CHECKING([whether to build the demo programs]) 70 if test x"$enable_demo" != x"no"; then 71 AC_MSG_RESULT([yes]) 72 else 73 AC_MSG_RESULT([no]) 74 fi 75 AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"]) 70 AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"]) 71 AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"]) 76 72 77 73 dnl Disable/enable building the binary tools. … … 87 83 fi 88 84 AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"]) 85 86 dnl Support for running test cases using valgrind. 87 use_valgrind=no 88 AC_ARG_ENABLE([valgrind], 89 AS_HELP_STRING([--enable-valgrind], [use valgrind when running tests]), 90 [use_valgrind=yes]) 91 92 if [[ "$use_valgrind" = "yes" ]]; then 93 AC_CHECK_PROG(HAVE_VALGRIND, valgrind, yes, no) 94 95 if [[ "$HAVE_VALGRIND" = "no" ]]; then 96 AC_MSG_ERROR([Valgrind not found in PATH.]) 97 fi 98 fi 99 AM_CONDITIONAL(USE_VALGRIND, [test "$use_valgrind" = "yes"]) 89 100 90 101 dnl Checks for header files. … … 108 119 AC_CONFIG_FILES([ 109 120 Makefile 121 demo/Makefile 110 122 cmake/version.cmake 111 123 doc/Doxyfile … … 121 133 echo 122 134 echo C++ compiler.................. : $CXX 123 echo C++ compiles flags............ : $ CXXFLAGS135 echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS 124 136 echo 125 137 echo Compiler supports long long... : $long_long_found 126 138 echo 127 #echo GLPK support.................. : $lx_glpk_found 128 #echo CPLEX support................. : $lx_cplex_found 129 #echo SOPLEX support................ : $lx_soplex_found 130 #echo 131 echo Build demo programs........... : $enable_demo 139 echo GLPK support.................. : $lx_glpk_found 140 echo CPLEX support................. : $lx_cplex_found 141 echo SOPLEX support................ : $lx_soplex_found 142 echo CLP support................... : $lx_clp_found 143 echo CBC support................... : $lx_cbc_found 144 echo 132 145 echo Build additional tools........ : $enable_tools 146 echo Use valgrind for tests........ : $use_valgrind 133 147 echo 134 148 echo The packace will be installed in -
demo/CMakeLists.txt
r510 r679 1 1 INCLUDE_DIRECTORIES( 2 ${ CMAKE_SOURCE_DIR}2 ${PROJECT_SOURCE_DIR} 3 3 ${PROJECT_BINARY_DIR} 4 4 ) 5 5 6 LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon) 6 LINK_DIRECTORIES( 7 ${PROJECT_BINARY_DIR}/lemon 8 ) 7 9 8 10 SET(DEMOS 9 11 arg_parser_demo 10 12 graph_to_eps_demo 11 lgf_demo) 13 lgf_demo 14 ) 12 15 13 16 FOREACH(DEMO_NAME ${DEMOS}) 14 17 ADD_EXECUTABLE(${DEMO_NAME} ${DEMO_NAME}.cc) 15 18 TARGET_LINK_LIBRARIES(${DEMO_NAME} lemon) 16 ENDFOREACH( DEMO_NAME)19 ENDFOREACH() -
demo/Makefile.am
r164 r564 1 EXTRA_DIST += \ 2 demo/CMakeLists.txt \ 3 demo/digraph.lgf 1 AM_CXXFLAGS = $(WARNINGCXXFLAGS) 4 2 5 if WANT_DEMO 3 AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir) 4 LDADD = $(top_builddir)/lemon/libemon.la 6 5 7 noinst_PROGRAMS += \ 8 demo/arg_parser_demo \ 9 demo/graph_to_eps_demo \ 10 demo/lgf_demo 6 EXTRA_DIST = \ 7 CMakeLists.txt \ 8 digraph.lgf 11 9 12 endif WANT_DEMO 10 noinst_PROGRAMS = \ 11 arg_parser_demo \ 12 graph_to_eps_demo \ 13 lgf_demo 13 14 14 demo_arg_parser_demo_SOURCES = demo/arg_parser_demo.cc15 demo_graph_to_eps_demo_SOURCES = demo/graph_to_eps_demo.cc16 demo_lgf_demo_SOURCES = demo/lgf_demo.cc15 arg_parser_demo_SOURCES = arg_parser_demo.cc 16 graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc 17 lgf_demo_SOURCES = lgf_demo.cc -
demo/arg_parser_demo.cc
r311 r877 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 66 66 .other("..."); 67 67 68 // Throw an exception when problems occurs. The default behavior is to 69 // exit(1) on these cases, but this makes Valgrind falsely warn 70 // about memory leaks. 71 ap.throwOnProblems(); 72 68 73 // Perform the parsing process 69 74 // (in case of any error it terminates the program) 70 ap.parse(); 75 // The try {} construct is necessary only if the ap.trowOnProblems() 76 // setting is in use. 77 try { 78 ap.parse(); 79 } catch (ArgParserException &) { return 1; } 71 80 72 81 // Check each option if it has been given and print its value -
demo/graph_to_eps_demo.cc
r313 r612 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 86 86 coords(coords). 87 87 title("Sample .eps figure"). 88 copyright("(C) 2003-200 8LEMON Project").88 copyright("(C) 2003-2009 LEMON Project"). 89 89 run(); 90 90 … … 93 93 coords(coords). 94 94 title("Sample .eps figure"). 95 copyright("(C) 2003-200 8LEMON Project").95 copyright("(C) 2003-2009 LEMON Project"). 96 96 absoluteNodeSizes().absoluteArcWidths(). 97 97 nodeScale(2).nodeSizes(sizes). … … 106 106 graphToEps(g,"graph_to_eps_demo_out_3_arr.eps"). 107 107 title("Sample .eps figure (with arrowheads)"). 108 copyright("(C) 2003-200 8LEMON Project").108 copyright("(C) 2003-2009 LEMON Project"). 109 109 absoluteNodeSizes().absoluteArcWidths(). 110 110 nodeColors(composeMap(palette,colors)). … … 133 133 graphToEps(g,"graph_to_eps_demo_out_4_par.eps"). 134 134 title("Sample .eps figure (parallel arcs)"). 135 copyright("(C) 2003-200 8LEMON Project").135 copyright("(C) 2003-2009 LEMON Project"). 136 136 absoluteNodeSizes().absoluteArcWidths(). 137 137 nodeShapes(shapes). … … 148 148 graphToEps(g,"graph_to_eps_demo_out_5_par_arr.eps"). 149 149 title("Sample .eps figure (parallel arcs and arrowheads)"). 150 copyright("(C) 2003-200 8LEMON Project").150 copyright("(C) 2003-2009 LEMON Project"). 151 151 absoluteNodeSizes().absoluteArcWidths(). 152 152 nodeScale(2).nodeSizes(sizes). … … 164 164 graphToEps(g,"graph_to_eps_demo_out_6_par_arr_a4.eps"). 165 165 title("Sample .eps figure (fits to A4)"). 166 copyright("(C) 2003-200 8LEMON Project").166 copyright("(C) 2003-2009 LEMON Project"). 167 167 scaleToA4(). 168 168 absoluteNodeSizes().absoluteArcWidths(). … … 183 183 ListDigraph::NodeMap<Point> hcoords(h); 184 184 185 int cols=int(s qrt(double(palette.size())));185 int cols=int(std::sqrt(double(palette.size()))); 186 186 for(int i=0;i<int(paletteW.size());i++) { 187 187 Node n=h.addNode(); … … 194 194 scale(60). 195 195 title("Sample .eps figure (Palette demo)"). 196 copyright("(C) 2003-200 8LEMON Project").196 copyright("(C) 2003-2009 LEMON Project"). 197 197 coords(hcoords). 198 198 absoluteNodeSizes().absoluteArcWidths(). -
demo/lgf_demo.cc
r294 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/CMakeLists.txt
r500 r865 1 1 SET(PACKAGE_NAME ${PROJECT_NAME}) 2 2 SET(PACKAGE_VERSION ${PROJECT_VERSION}) 3 SET(abs_top_srcdir ${ CMAKE_SOURCE_DIR})4 SET(abs_top_builddir ${ CMAKE_BINARY_DIR})3 SET(abs_top_srcdir ${PROJECT_SOURCE_DIR}) 4 SET(abs_top_builddir ${PROJECT_BINARY_DIR}) 5 5 6 6 CONFIGURE_FILE( 7 ${CMAKE_SOURCE_DIR}/doc/Doxyfile.in 8 ${CMAKE_BINARY_DIR}/doc/Doxyfile 9 @ONLY) 7 ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in 8 ${PROJECT_BINARY_DIR}/doc/Doxyfile 9 @ONLY 10 ) 10 11 11 IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)12 IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE) 12 13 FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/) 14 SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha) 15 ADD_CUSTOM_TARGET(html 16 COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images 17 COMMAND ${CMAKE_COMMAND} -E make_directory gen-images 18 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps 19 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps 20 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps 21 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps 22 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps 23 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps 24 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps 25 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps 26 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps 27 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps 28 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps 29 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps 30 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps 31 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps 32 COMMAND ${CMAKE_COMMAND} -E remove_directory html 33 COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox 34 COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile 35 WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR} 36 ) 37 38 SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC) 39 13 40 IF(UNIX) 14 ADD_CUSTOM_TARGET(html 15 COMMAND rm -rf gen-images 16 COMMAND mkdir gen-images 17 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps 18 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps 19 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps 20 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps 21 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps 22 COMMAND rm -rf html 23 COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile 24 WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}) 41 INSTALL( 42 DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/ 43 DESTINATION share/doc/lemon/html 44 COMPONENT html_documentation 45 ) 25 46 ELSEIF(WIN32) 26 ADD_CUSTOM_TARGET(html 27 COMMAND if exist gen-images rmdir /s /q gen-images 28 COMMAND mkdir gen-images 29 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps 30 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps 31 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps 32 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps 33 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps 34 COMMAND if exist html rmdir /s /q html 35 COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile 36 WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}) 37 ENDIF(UNIX) 38 INSTALL( 39 DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/ 40 DESTINATION share/doc 41 COMPONENT html_documentation) 42 ENDIF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE) 47 INSTALL( 48 DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/ 49 DESTINATION doc 50 COMPONENT html_documentation 51 ) 52 ENDIF() 53 54 ENDIF() -
doc/Doxyfile.in
r316 r756 1 # Doxyfile 1.5. 7.11 # Doxyfile 1.5.9 2 2 3 3 #--------------------------------------------------------------------------- … … 22 22 QT_AUTOBRIEF = NO 23 23 MULTILINE_CPP_IS_BRIEF = NO 24 DETAILS_AT_TOP = YES25 24 INHERIT_DOCS = NO 26 25 SEPARATE_MEMBER_PAGES = NO … … 67 66 ENABLED_SECTIONS = 68 67 MAX_INITIALIZER_LINES = 5 69 SHOW_USED_FILES = YES68 SHOW_USED_FILES = NO 70 69 SHOW_DIRECTORIES = YES 71 70 SHOW_FILES = YES … … 92 91 "@abs_top_srcdir@/demo" \ 93 92 "@abs_top_srcdir@/tools" \ 94 "@abs_top_srcdir@/test/test_tools.h" 93 "@abs_top_srcdir@/test/test_tools.h" \ 94 "@abs_top_builddir@/doc/references.dox" 95 95 INPUT_ENCODING = UTF-8 96 96 FILE_PATTERNS = *.h \ … … 224 224 SKIP_FUNCTION_MACROS = YES 225 225 #--------------------------------------------------------------------------- 226 # Configuration::additions related to external references226 # Options related to the search engine 227 227 #--------------------------------------------------------------------------- 228 228 TAGFILES = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ " -
doc/Makefile.am
r317 r865 9 9 doc/mainpage.dox \ 10 10 doc/migration.dox \ 11 doc/min_cost_flow.dox \ 11 12 doc/named-param.dox \ 12 13 doc/namespaces.dox \ … … 15 16 16 17 DOC_EPS_IMAGES18 = \ 18 grid_graph.eps \ 17 19 nodeshape_0.eps \ 18 20 nodeshape_1.eps \ … … 21 23 nodeshape_4.eps 22 24 25 DOC_EPS_IMAGES27 = \ 26 bipartite_matching.eps \ 27 bipartite_partitions.eps \ 28 connected_components.eps \ 29 edge_biconnected_components.eps \ 30 matching.eps \ 31 node_biconnected_components.eps \ 32 planar.eps \ 33 strongly_connected_components.eps 34 23 35 DOC_EPS_IMAGES = \ 24 $(DOC_EPS_IMAGES18) 36 $(DOC_EPS_IMAGES18) \ 37 $(DOC_EPS_IMAGES27) 25 38 26 39 DOC_PNG_IMAGES = \ … … 45 58 fi 46 59 47 html-local: $(DOC_PNG_IMAGES) 60 $(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps 61 -mkdir doc/gen-images 62 if test ${gs_found} = yes; then \ 63 $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<; \ 64 else \ 65 echo; \ 66 echo "Ghostscript not found."; \ 67 echo; \ 68 exit 1; \ 69 fi 70 71 references.dox: doc/references.bib 72 if test ${python_found} = yes; then \ 73 cd doc; \ 74 python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \ 75 cd ..; \ 76 else \ 77 echo; \ 78 echo "Python not found."; \ 79 echo; \ 80 exit 1; \ 81 fi 82 83 html-local: $(DOC_PNG_IMAGES) references.dox 48 84 if test ${doxygen_found} = yes; then \ 49 85 cd doc; \ … … 70 106 install-html-local: doc/html 71 107 @$(NORMAL_INSTALL) 72 $(mkinstalldirs) $(DESTDIR)$(htmldir)/ docs108 $(mkinstalldirs) $(DESTDIR)$(htmldir)/html 73 109 for p in doc/html/*.{html,css,png,map,gif,tag} ; do \ 74 110 f="`echo $$p | sed -e 's|^.*/||'`"; \ 75 echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/ docs/$$f"; \76 $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/ docs/$$f; \111 echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f"; \ 112 $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f; \ 77 113 done 78 114 … … 81 117 for p in doc/html/*.{html,css,png,map,gif,tag} ; do \ 82 118 f="`echo $$p | sed -e 's|^.*/||'`"; \ 83 echo " rm -f $(DESTDIR)$(htmldir)/ docs/$$f"; \84 rm -f $(DESTDIR)$(htmldir)/ docs/$$f; \119 echo " rm -f $(DESTDIR)$(htmldir)/html/$$f"; \ 120 rm -f $(DESTDIR)$(htmldir)/html/$$f; \ 85 121 done 86 122 -
doc/coding_style.dox
r210 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/dirs.dox
r318 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 72 72 \brief Auxiliary tools for implementation. 73 73 74 This directory contains some auxiliary classes for implementing graphs, 74 This directory contains some auxiliary classes for implementing graphs, 75 75 maps and some other classes. 76 76 As a user you typically don't have to deal with these files. -
doc/groups.dox
r318 r904 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 17 17 */ 18 18 19 namespace lemon { 20 19 21 /** 20 22 @defgroup datas Data Structures 21 This group describes the several data structures implemented in LEMON.23 This group contains the several data structures implemented in LEMON. 22 24 */ 23 25 … … 61 63 62 64 /** 63 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs65 @defgroup graph_adaptors Adaptor Classes for Graphs 64 66 @ingroup graphs 65 \brief Graph types between real graphs and graph adaptors. 66 67 This group describes some graph types between real graphs and graph adaptors. 68 These classes wrap graphs to give new functionality as the adaptors do it. 69 On the other hand they are not light-weight structures as the adaptors. 67 \brief Adaptor classes for digraphs and graphs 68 69 This group contains several useful adaptor classes for digraphs and graphs. 70 71 The main parts of LEMON are the different graph structures, generic 72 graph algorithms, graph concepts, which couple them, and graph 73 adaptors. While the previous notions are more or less clear, the 74 latter one needs further explanation. Graph adaptors are graph classes 75 which serve for considering graph structures in different ways. 76 77 A short example makes this much clearer. Suppose that we have an 78 instance \c g of a directed graph type, say ListDigraph and an algorithm 79 \code 80 template <typename Digraph> 81 int algorithm(const Digraph&); 82 \endcode 83 is needed to run on the reverse oriented graph. It may be expensive 84 (in time or in memory usage) to copy \c g with the reversed 85 arcs. In this case, an adaptor class is used, which (according 86 to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph. 87 The adaptor uses the original digraph structure and digraph operations when 88 methods of the reversed oriented graph are called. This means that the adaptor 89 have minor memory usage, and do not perform sophisticated algorithmic 90 actions. The purpose of it is to give a tool for the cases when a 91 graph have to be used in a specific alteration. If this alteration is 92 obtained by a usual construction like filtering the node or the arc set or 93 considering a new orientation, then an adaptor is worthwhile to use. 94 To come back to the reverse oriented graph, in this situation 95 \code 96 template<typename Digraph> class ReverseDigraph; 97 \endcode 98 template class can be used. The code looks as follows 99 \code 100 ListDigraph g; 101 ReverseDigraph<ListDigraph> rg(g); 102 int result = algorithm(rg); 103 \endcode 104 During running the algorithm, the original digraph \c g is untouched. 105 This techniques give rise to an elegant code, and based on stable 106 graph adaptors, complex algorithms can be implemented easily. 107 108 In flow, circulation and matching problems, the residual 109 graph is of particular importance. Combining an adaptor implementing 110 this with shortest path algorithms or minimum mean cycle algorithms, 111 a range of weighted and cardinality optimization algorithms can be 112 obtained. For other examples, the interested user is referred to the 113 detailed documentation of particular adaptors. 114 115 The behavior of graph adaptors can be very different. Some of them keep 116 capabilities of the original graph while in other cases this would be 117 meaningless. This means that the concepts that they meet depend 118 on the graph adaptor, and the wrapped graph. 119 For example, if an arc of a reversed digraph is deleted, this is carried 120 out by deleting the corresponding arc of the original digraph, thus the 121 adaptor modifies the original digraph. 122 However in case of a residual digraph, this operation has no sense. 123 124 Let us stand one more example here to simplify your work. 125 ReverseDigraph has constructor 126 \code 127 ReverseDigraph(Digraph& digraph); 128 \endcode 129 This means that in a situation, when a <tt>const %ListDigraph&</tt> 130 reference to a graph is given, then it have to be instantiated with 131 <tt>Digraph=const %ListDigraph</tt>. 132 \code 133 int algorithm1(const ListDigraph& g) { 134 ReverseDigraph<const ListDigraph> rg(g); 135 return algorithm2(rg); 136 } 137 \endcode 70 138 */ 71 139 … … 75 143 \brief Map structures implemented in LEMON. 76 144 77 This group describes the map structures implemented in LEMON.145 This group contains the map structures implemented in LEMON. 78 146 79 147 LEMON provides several special purpose maps and map adaptors that e.g. combine … … 88 156 \brief Special graph-related maps. 89 157 90 This group describes maps that are specifically designed to assign 91 values to the nodes and arcs of graphs. 158 This group contains maps that are specifically designed to assign 159 values to the nodes and arcs/edges of graphs. 160 161 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap, 162 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts". 92 163 */ 93 164 … … 97 168 \brief Tools to create new maps from existing ones 98 169 99 This group describes map adaptors that are used to create "implicit"170 This group contains map adaptors that are used to create "implicit" 100 171 maps from other maps. 101 172 102 Most of them are \ref lemon::concepts::ReadMap "read-only maps".173 Most of them are \ref concepts::ReadMap "read-only maps". 103 174 They can make arithmetic and logical operations between one or two maps 104 175 (negation, shifting, addition, multiplication, logical 'and', 'or', … … 156 227 157 228 /** 158 @defgroup matrices Matrices159 @ingroup datas160 \brief Two dimensional data storages implemented in LEMON.161 162 This group describes two dimensional data storages implemented in LEMON.163 */164 165 /**166 229 @defgroup paths Path Structures 167 230 @ingroup datas 168 231 \brief %Path structures implemented in LEMON. 169 232 170 This group describes the path structures implemented in LEMON.233 This group contains the path structures implemented in LEMON. 171 234 172 235 LEMON provides flexible data structures to work with paths. … … 176 239 any kind of path structure. 177 240 178 \sa lemon::concepts::Path 241 \sa \ref concepts::Path "Path concept" 242 */ 243 244 /** 245 @defgroup heaps Heap Structures 246 @ingroup datas 247 \brief %Heap structures implemented in LEMON. 248 249 This group contains the heap structures implemented in LEMON. 250 251 LEMON provides several heap classes. They are efficient implementations 252 of the abstract data type \e priority \e queue. They store items with 253 specified values called \e priorities in such a way that finding and 254 removing the item with minimum priority are efficient. 255 The basic operations are adding and erasing items, changing the priority 256 of an item, etc. 257 258 Heaps are crucial in several algorithms, such as Dijkstra and Prim. 259 The heap implementations have the same interface, thus any of them can be 260 used easily in such algorithms. 261 262 \sa \ref concepts::Heap "Heap concept" 179 263 */ 180 264 … … 184 268 \brief Auxiliary data structures implemented in LEMON. 185 269 186 This group describes some data structures implemented in LEMON in270 This group contains some data structures implemented in LEMON in 187 271 order to make it easier to implement combinatorial algorithms. 188 272 */ 189 273 190 274 /** 275 @defgroup geomdat Geometric Data Structures 276 @ingroup auxdat 277 \brief Geometric data structures implemented in LEMON. 278 279 This group contains geometric data structures implemented in LEMON. 280 281 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional 282 vector with the usual operations. 283 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the 284 rectangular bounding box of a set of \ref lemon::dim2::Point 285 "dim2::Point"'s. 286 */ 287 288 /** 289 @defgroup matrices Matrices 290 @ingroup auxdat 291 \brief Two dimensional data storages implemented in LEMON. 292 293 This group contains two dimensional data storages implemented in LEMON. 294 */ 295 296 /** 191 297 @defgroup algs Algorithms 192 \brief This group describes the several algorithms298 \brief This group contains the several algorithms 193 299 implemented in LEMON. 194 300 195 This group describes the several algorithms301 This group contains the several algorithms 196 302 implemented in LEMON. 197 303 */ … … 202 308 \brief Common graph search algorithms. 203 309 204 This group describes the common graph search algorithms like 205 Breadth-First Search (BFS) and Depth-First Search (DFS). 310 This group contains the common graph search algorithms, namely 311 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) 312 \ref clrs01algorithms. 206 313 */ 207 314 … … 211 318 \brief Algorithms for finding shortest paths. 212 319 213 This group describes the algorithms for finding shortest paths in graphs. 320 This group contains the algorithms for finding shortest paths in digraphs 321 \ref clrs01algorithms. 322 323 - \ref Dijkstra algorithm for finding shortest paths from a source node 324 when all arc lengths are non-negative. 325 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths 326 from a source node when arc lenghts can be either positive or negative, 327 but the digraph should not contain directed cycles with negative total 328 length. 329 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms 330 for solving the \e all-pairs \e shortest \e paths \e problem when arc 331 lenghts can be either positive or negative, but the digraph should 332 not contain directed cycles with negative total length. 333 - \ref Suurballe A successive shortest path algorithm for finding 334 arc-disjoint paths between two nodes having minimum total length. 335 */ 336 337 /** 338 @defgroup spantree Minimum Spanning Tree Algorithms 339 @ingroup algs 340 \brief Algorithms for finding minimum cost spanning trees and arborescences. 341 342 This group contains the algorithms for finding minimum cost spanning 343 trees and arborescences \ref clrs01algorithms. 214 344 */ 215 345 … … 219 349 \brief Algorithms for finding maximum flows. 220 350 221 This group describes the algorithms for finding maximum flows and 222 feasible circulations. 223 224 The maximum flow problem is to find a flow between a single source and 225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$ 226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity 227 function and given \f$s, t \in V\f$ source and target node. The 228 maximum flow is the \f$f_a\f$ solution of the next optimization problem: 229 230 \f[ 0 \le f_a \le c_a \f] 231 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} 232 \qquad \forall u \in V \setminus \{s,t\}\f] 233 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f] 351 This group contains the algorithms for finding maximum flows and 352 feasible circulations \ref clrs01algorithms, \ref amo93networkflows. 353 354 The \e maximum \e flow \e problem is to find a flow of maximum value between 355 a single source and a single target. Formally, there is a \f$G=(V,A)\f$ 356 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and 357 \f$s, t \in V\f$ source and target nodes. 358 A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the 359 following optimization problem. 360 361 \f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f] 362 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) 363 \quad \forall u\in V\setminus\{s,t\} \f] 364 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 234 365 235 366 LEMON contains several algorithms for solving maximum flow problems: 236 - \ref lemon::EdmondsKarp "Edmonds-Karp" 237 - \ref lemon::Preflow "Goldberg's Preflow algorithm" 238 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees" 239 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees" 240 241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the 242 fastest method to compute the maximum flow. All impelementations 243 provides functions to query the minimum cut, which is the dual linear 244 programming problem of the maximum flow. 245 */ 246 247 /** 248 @defgroup min_cost_flow Minimum Cost Flow Algorithms 367 - \ref EdmondsKarp Edmonds-Karp algorithm 368 \ref edmondskarp72theoretical. 369 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm 370 \ref goldberg88newapproach. 371 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 372 \ref dinic70algorithm, \ref sleator83dynamic. 373 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees 374 \ref goldberg88newapproach, \ref sleator83dynamic. 375 376 In most cases the \ref Preflow algorithm provides the 377 fastest method for computing a maximum flow. All implementations 378 also provide functions to query the minimum cut, which is the dual 379 problem of maximum flow. 380 381 \ref Circulation is a preflow push-relabel algorithm implemented directly 382 for finding feasible circulations, which is a somewhat different problem, 383 but it is strongly related to maximum flow. 384 For more information, see \ref Circulation. 385 */ 386 387 /** 388 @defgroup min_cost_flow_algs Minimum Cost Flow Algorithms 249 389 @ingroup algs 250 390 251 391 \brief Algorithms for finding minimum cost flows and circulations. 252 392 253 This group describes the algorithms for finding minimum cost flows and 254 circulations. 393 This group contains the algorithms for finding minimum cost flows and 394 circulations \ref amo93networkflows. For more information about this 395 problem and its dual solution, see \ref min_cost_flow 396 "Minimum Cost Flow Problem". 397 398 LEMON contains several algorithms for this problem. 399 - \ref NetworkSimplex Primal Network Simplex algorithm with various 400 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. 401 - \ref CostScaling Cost Scaling algorithm based on push/augment and 402 relabel operations \ref goldberg90approximation, \ref goldberg97efficient, 403 \ref bunnagel98efficient. 404 - \ref CapacityScaling Capacity Scaling algorithm based on the successive 405 shortest path method \ref edmondskarp72theoretical. 406 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are 407 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. 408 409 In general NetworkSimplex is the most efficient implementation, 410 but in special cases other algorithms could be faster. 411 For example, if the total supply and/or capacities are rather small, 412 CapacityScaling is usually the fastest algorithm (without effective scaling). 255 413 */ 256 414 … … 261 419 \brief Algorithms for finding minimum cut in graphs. 262 420 263 This group describes the algorithms for finding minimum cut in graphs.264 265 The minimum cutproblem is to find a non-empty and non-complete266 \f$X\f$ subset of the vertices with minimum overall capacity on267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an268 \f$c _a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum421 This group contains the algorithms for finding minimum cut in graphs. 422 423 The \e minimum \e cut \e problem is to find a non-empty and non-complete 424 \f$X\f$ subset of the nodes with minimum overall capacity on 425 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a 426 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum 269 427 cut is the \f$X\f$ solution of the next optimization problem: 270 428 271 429 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} 272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]430 \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f] 273 431 274 432 LEMON contains several algorithms related to minimum cut problems: 275 433 276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculateminimum cut277 in directed graphs 278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to279 calculat e minimum cut in undirected graphs280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all281 pairs minimum cut in undirected graphs434 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut 435 in directed graphs. 436 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for 437 calculating minimum cut in undirected graphs. 438 - \ref GomoryHu "Gomory-Hu tree computation" for calculating 439 all-pairs minimum cut in undirected graphs. 282 440 283 441 If you want to find minimum cut just between two distinict nodes, 284 please see the \ref max_flow "Maximum Flow page". 285 */ 286 287 /** 288 @defgroup graph_prop Connectivity and Other Graph Properties 289 @ingroup algs 290 \brief Algorithms for discovering the graph properties 291 292 This group describes the algorithms for discovering the graph properties 293 like connectivity, bipartiteness, euler property, simplicity etc. 294 295 \image html edge_biconnected_components.png 296 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 297 */ 298 299 /** 300 @defgroup planar Planarity Embedding and Drawing 301 @ingroup algs 302 \brief Algorithms for planarity checking, embedding and drawing 303 304 This group describes the algorithms for planarity checking, 305 embedding and drawing. 306 307 \image html planar.png 308 \image latex planar.eps "Plane graph" width=\textwidth 442 see the \ref max_flow "maximum flow problem". 443 */ 444 445 /** 446 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms 447 @ingroup algs 448 \brief Algorithms for finding minimum mean cycles. 449 450 This group contains the algorithms for finding minimum mean cycles 451 \ref clrs01algorithms, \ref amo93networkflows. 452 453 The \e minimum \e mean \e cycle \e problem is to find a directed cycle 454 of minimum mean length (cost) in a digraph. 455 The mean length of a cycle is the average length of its arcs, i.e. the 456 ratio between the total length of the cycle and the number of arcs on it. 457 458 This problem has an important connection to \e conservative \e length 459 \e functions, too. A length function on the arcs of a digraph is called 460 conservative if and only if there is no directed cycle of negative total 461 length. For an arbitrary length function, the negative of the minimum 462 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the 463 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length 464 function. 465 466 LEMON contains three algorithms for solving the minimum mean cycle problem: 467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows, 468 \ref dasdan98minmeancycle. 469 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved 470 version of Karp's algorithm \ref dasdan98minmeancycle. 471 - \ref HowardMmc Howard's policy iteration algorithm 472 \ref dasdan98minmeancycle. 473 474 In practice, the \ref HowardMmc "Howard" algorithm proved 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. 309 480 */ 310 481 … … 314 485 \brief Algorithms for finding matchings in graphs and bipartite graphs. 315 486 316 This group contains algorithm objects and functions to calculate487 This group contains the algorithms for calculating 317 488 matchings in graphs and bipartite graphs. The general matching problem is 318 finding a subset of the arcs which does not shares common endpoints. 489 finding a subset of the edges for which each node has at most one incident 490 edge. 319 491 320 492 There are several different algorithms for calculate matchings in 321 493 graphs. The matching problems in bipartite graphs are generally 322 494 easier than in general graphs. The goal of the matching optimization 323 can be thefinding maximum cardinality, maximum weight or minimum cost495 can be finding maximum cardinality, maximum weight or minimum cost 324 496 matching. The search can be constrained to find perfect or 325 497 maximum cardinality matching. 326 498 327 LEMON contains the next algorithms: 328 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp 329 augmenting path algorithm for calculate maximum cardinality matching in 330 bipartite graphs 331 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel 332 algorithm for calculate maximum cardinality matching in bipartite graphs 333 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" 334 Successive shortest path algorithm for calculate maximum weighted matching 335 and maximum weighted bipartite matching in bipartite graph 336 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" 337 Successive shortest path algorithm for calculate minimum cost maximum 338 matching in bipartite graph 339 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm 340 for calculate maximum cardinality matching in general graph 341 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom 342 shrinking algorithm for calculate maximum weighted matching in general 343 graph 344 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching" 345 Edmond's blossom shrinking algorithm for calculate maximum weighted 346 perfect matching in general graph 347 348 \image html bipartite_matching.png 349 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth 350 */ 351 352 /** 353 @defgroup spantree Minimum Spanning Tree Algorithms 354 @ingroup algs 355 \brief Algorithms for finding a minimum cost spanning tree in a graph. 356 357 This group describes the algorithms for finding a minimum cost spanning 358 tree in a graph 499 The matching algorithms implemented in LEMON: 500 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm 501 for calculating maximum cardinality matching in bipartite graphs. 502 - \ref PrBipartiteMatching Push-relabel algorithm 503 for calculating maximum cardinality matching in bipartite graphs. 504 - \ref MaxWeightedBipartiteMatching 505 Successive shortest path algorithm for calculating maximum weighted 506 matching and maximum weighted bipartite matching in bipartite graphs. 507 - \ref MinCostMaxBipartiteMatching 508 Successive shortest path algorithm for calculating minimum cost maximum 509 matching in bipartite graphs. 510 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 511 maximum cardinality matching in general graphs. 512 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating 513 maximum weighted matching in general graphs. 514 - \ref MaxWeightedPerfectMatching 515 Edmond's blossom shrinking algorithm for calculating maximum weighted 516 perfect matching in general graphs. 517 - \ref MaxFractionalMatching Push-relabel algorithm for calculating 518 maximum cardinality fractional matching in general graphs. 519 - \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating 520 maximum weighted fractional matching in general graphs. 521 - \ref MaxWeightedPerfectFractionalMatching 522 Augmenting path algorithm for calculating maximum weighted 523 perfect fractional matching in general graphs. 524 525 \image html matching.png 526 \image latex matching.eps "Min Cost Perfect Matching" width=\textwidth 527 */ 528 529 /** 530 @defgroup graph_properties Connectivity and Other Graph Properties 531 @ingroup algs 532 \brief Algorithms for discovering the graph properties 533 534 This group contains the algorithms for discovering the graph properties 535 like connectivity, bipartiteness, euler property, simplicity etc. 536 537 \image html connected_components.png 538 \image latex connected_components.eps "Connected components" width=\textwidth 539 */ 540 541 /** 542 @defgroup planar Planarity Embedding and Drawing 543 @ingroup algs 544 \brief Algorithms for planarity checking, embedding and drawing 545 546 This group contains the algorithms for planarity checking, 547 embedding and drawing. 548 549 \image html planar.png 550 \image latex planar.eps "Plane graph" width=\textwidth 551 */ 552 553 /** 554 @defgroup approx_algs Approximation Algorithms 555 @ingroup algs 556 \brief Approximation algorithms. 557 558 This group contains the approximation and heuristic algorithms 559 implemented in LEMON. 560 561 <b>Maximum Clique Problem</b> 562 - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of 563 Grosso, Locatelli, and Pullan. 359 564 */ 360 565 … … 364 569 \brief Auxiliary algorithms implemented in LEMON. 365 570 366 This group describes some algorithms implemented in LEMON571 This group contains some algorithms implemented in LEMON 367 572 in order to make it easier to implement complex algorithms. 368 573 */ 369 574 370 575 /** 371 @defgroup approx Approximation Algorithms 372 @ingroup algs 373 \brief Approximation algorithms. 374 375 This group describes the approximation and heuristic algorithms 576 @defgroup gen_opt_group General Optimization Tools 577 \brief This group contains some general optimization frameworks 376 578 implemented in LEMON. 377 */ 378 379 /** 380 @defgroup gen_opt_group General Optimization Tools 381 \brief This group describes some general optimization frameworks 579 580 This group contains some general optimization frameworks 382 581 implemented in LEMON. 383 384 This group describes some general optimization frameworks 385 implemented in LEMON. 386 */ 387 388 /** 389 @defgroup lp_group Lp and Mip Solvers 582 */ 583 584 /** 585 @defgroup lp_group LP and MIP Solvers 390 586 @ingroup gen_opt_group 391 \brief Lp and Mip solver interfaces for LEMON. 392 393 This group describes Lp and Mip solver interfaces for LEMON. The 394 various LP solvers could be used in the same manner with this 395 interface. 587 \brief LP and MIP solver interfaces for LEMON. 588 589 This group contains LP and MIP solver interfaces for LEMON. 590 Various LP solvers could be used in the same manner with this 591 high-level interface. 592 593 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 594 \ref cplex, \ref soplex. 396 595 */ 397 596 … … 410 609 \brief Metaheuristics for LEMON library. 411 610 412 This group describes some metaheuristic optimization tools.611 This group contains some metaheuristic optimization tools. 413 612 */ 414 613 … … 425 624 \brief Simple basic graph utilities. 426 625 427 This group describes some simple basic graph utilities.626 This group contains some simple basic graph utilities. 428 627 */ 429 628 … … 433 632 \brief Tools for development, debugging and testing. 434 633 435 This group describes several useful tools for development,634 This group contains several useful tools for development, 436 635 debugging and testing. 437 636 */ … … 442 641 \brief Simple tools for measuring the performance of algorithms. 443 642 444 This group describes simple tools for measuring the performance643 This group contains simple tools for measuring the performance 445 644 of algorithms. 446 645 */ … … 451 650 \brief Exceptions defined in LEMON. 452 651 453 This group describes the exceptions defined in LEMON.652 This group contains the exceptions defined in LEMON. 454 653 */ 455 654 … … 458 657 \brief Graph Input-Output methods 459 658 460 This group describes the tools for importing and exporting graphs659 This group contains the tools for importing and exporting graphs 461 660 and graph related data. Now it supports the \ref lgf-format 462 661 "LEMON Graph Format", the \c DIMACS format and the encapsulated … … 465 664 466 665 /** 467 @defgroup lemon_io LEMON Input-Output666 @defgroup lemon_io LEMON Graph Format 468 667 @ingroup io_group 469 668 \brief Reading and writing LEMON Graph Format. 470 669 471 This group describes methods for reading and writing670 This group contains methods for reading and writing 472 671 \ref lgf-format "LEMON Graph Format". 473 672 */ … … 478 677 \brief General \c EPS drawer and graph exporter 479 678 480 This group describes general \c EPS drawing methods and special679 This group contains general \c EPS drawing methods and special 481 680 graph exporting tools. 681 */ 682 683 /** 684 @defgroup dimacs_group DIMACS Format 685 @ingroup io_group 686 \brief Read and write files in DIMACS format 687 688 Tools to read a digraph from or write it to a file in DIMACS format data. 689 */ 690 691 /** 692 @defgroup nauty_group NAUTY Format 693 @ingroup io_group 694 \brief Read \e Nauty format 695 696 Tool to read graphs from \e Nauty format data. 482 697 */ 483 698 … … 486 701 \brief Skeleton classes and concept checking classes 487 702 488 This group describes the data/algorithm skeletons and concept checking703 This group contains the data/algorithm skeletons and concept checking 489 704 classes implemented in LEMON. 490 705 … … 516 731 \brief Skeleton and concept checking classes for graph structures 517 732 518 This group describes the skeletons and concept checking classes of LEMON's519 graph structures and helper classes used to implement these.733 This group contains the skeletons and concept checking classes of 734 graph structures. 520 735 */ 521 736 … … 525 740 \brief Skeleton and concept checking classes for maps 526 741 527 This group describes the skeletons and concept checking classes of maps. 742 This group contains the skeletons and concept checking classes of maps. 743 */ 744 745 /** 746 @defgroup tools Standalone Utility Applications 747 748 Some utility applications are listed here. 749 750 The standard compilation procedure (<tt>./configure;make</tt>) will compile 751 them, as well. 528 752 */ 529 753 … … 531 755 \anchor demoprograms 532 756 533 @defgroup demos Demo programs757 @defgroup demos Demo Programs 534 758 535 759 Some demo programs are listed here. Their full source codes can be found in 536 760 the \c demo subdirectory of the source tree. 537 761 538 It order to compile them, use <tt>--enable-demo</tt> configure option when 539 build the library. 540 */ 541 542 /** 543 @defgroup tools Standalone utility applications 544 545 Some utility applications are listed here. 546 547 The standard compilation procedure (<tt>./configure;make</tt>) will compile 548 them, as well. 549 */ 550 762 In order to compile them, use the <tt>make demo</tt> or the 763 <tt>make check</tt> commands. 764 */ 765 766 } -
doc/lgf.dox
r313 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/license.dox
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/mainpage.dox
r314 r877 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 22 22 \section intro Introduction 23 23 24 \subsection whatis What is LEMON 25 26 LEMON stands for 27 <b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels 28 and <b>O</b>ptimization in <b>N</b>etworks. 29 It is a C++ template 30 library aimed at combinatorial optimization tasks which 31 often involve in working 32 with graphs. 24 <b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling 25 and <b>O</b>ptimization in <b>N</b>etworks</i>. 26 It is a C++ template library providing efficient implementations of common 27 data structures and algorithms with focus on combinatorial optimization 28 tasks connected mainly with graphs and networks. 33 29 34 30 <b> … … 40 36 </b> 41 37 42 \subsection howtoread How to read the documentation 38 The project is maintained by the 39 <a href="http://www.cs.elte.hu/egres/">Egerváry Research Group on 40 Combinatorial Optimization</a> \ref egres 41 at the Operations Research Department of the 42 <a href="http://www.elte.hu/en/">Eötvös Loránd University</a>, 43 Budapest, Hungary. 44 LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a> 45 initiative \ref coinor. 43 46 44 If you want to get a quick start and see the most important features then 45 take a look at our \ref quicktour 46 "Quick Tour to LEMON" which will guide you along. 47 \section howtoread How to Read the Documentation 47 48 48 If you already feel like using our library, see the page that tells you49 \ref getstart "How to start using LEMON".49 If you would like to get to know the library, see 50 <a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>. 50 51 51 If you 52 want to see how LEMON works, see 53 some \ref demoprograms "demo programs".52 If you are interested in starting to use the library, see the <a class="el" 53 href="http://lemon.cs.elte.hu/trac/lemon/wiki/InstallGuide/">Installation 54 Guide</a>. 54 55 55 If you know what you are looking for then try to find it under the 56 <a class="el" href="modules.html">Modules</a> 57 section. 56 If you know what you are looking for, then try to find it under the 57 <a class="el" href="modules.html">Modules</a> section. 58 58 59 59 If you are a user of the old (0.x) series of LEMON, please check out the -
doc/migration.dox
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 26 26 27 27 Many of these changes adjusted automatically by the 28 <tt> script/lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual28 <tt>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual 29 29 update are typeset <b>boldface</b>. 30 30 … … 54 54 55 55 \warning 56 <b>The <tt>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of 57 the words \c graph, \c digraph, \c edge and \c arc, so it replaces them 58 in strings, comments etc. as well as in all identifiers.</b> 56 <b>The <tt>lemon-0.x-to-1.x.sh</tt> script replaces the words \c graph, 57 \c ugraph, \c edge and \c uedge in your own identifiers and in 58 strings, comments etc. as well as in all LEMON specific identifiers. 59 So use the script carefully and make a backup copy of your source files 60 before applying the script to them.</b> 59 61 60 62 \section migration-lgf LGF tools -
doc/named-param.dox
r269 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/namespaces.dox
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
doc/template.h
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/CMakeLists.txt
r510 r679 1 1 INCLUDE_DIRECTORIES( 2 ${ CMAKE_SOURCE_DIR}2 ${PROJECT_SOURCE_DIR} 3 3 ${PROJECT_BINARY_DIR} 4 4 ) … … 9 9 ) 10 10 11 ADD_LIBRARY(lemon 11 SET(LEMON_SOURCES 12 12 arg_parser.cc 13 13 base.cc 14 14 color.cc 15 lp_base.cc 16 lp_skeleton.cc 15 17 random.cc 16 18 bits/windows.cc 17 19 ) 18 20 21 IF(LEMON_HAVE_GLPK) 22 SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc) 23 INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS}) 24 IF(WIN32) 25 INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin) 26 INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin) 27 INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin) 28 ENDIF() 29 ENDIF() 30 31 IF(LEMON_HAVE_CPLEX) 32 SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc) 33 INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS}) 34 ENDIF() 35 36 IF(LEMON_HAVE_CLP) 37 SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc) 38 INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS}) 39 ENDIF() 40 41 IF(LEMON_HAVE_CBC) 42 SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc) 43 INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS}) 44 ENDIF() 45 46 ADD_LIBRARY(lemon ${LEMON_SOURCES}) 47 IF(UNIX) 48 SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon) 49 ENDIF() 50 19 51 INSTALL( 20 52 TARGETS lemon 21 53 ARCHIVE DESTINATION lib 22 COMPONENT library) 54 COMPONENT library 55 ) 23 56 24 57 INSTALL( … … 26 59 DESTINATION include/lemon 27 60 COMPONENT headers 28 FILES_MATCHING PATTERN "*.h") 61 FILES_MATCHING PATTERN "*.h" 62 ) 29 63 30 64 INSTALL( 31 65 FILES ${CMAKE_CURRENT_BINARY_DIR}/config.h 32 66 DESTINATION include/lemon 33 COMPONENT headers) 67 COMPONENT headers 68 ) -
lemon/Makefile.am
r512 r904 1 1 EXTRA_DIST += \ 2 2 lemon/lemon.pc.in \ 3 lemon/CMakeLists.txt 3 lemon/CMakeLists.txt \ 4 lemon/config.h.cmake 4 5 5 6 pkgconfig_DATA += lemon/lemon.pc … … 8 9 9 10 lemon_libemon_la_SOURCES = \ 10 lemon/arg_parser.cc \ 11 lemon/base.cc \ 12 lemon/color.cc \ 13 lemon/random.cc \ 11 lemon/arg_parser.cc \ 12 lemon/base.cc \ 13 lemon/color.cc \ 14 lemon/lp_base.cc \ 15 lemon/lp_skeleton.cc \ 16 lemon/random.cc \ 14 17 lemon/bits/windows.cc 15 18 16 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) 17 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS) 19 nodist_lemon_HEADERS = lemon/config.h 18 20 19 nodist_lemon_HEADERS = lemon/config.h 21 lemon_libemon_la_CXXFLAGS = \ 22 $(AM_CXXFLAGS) \ 23 $(GLPK_CFLAGS) \ 24 $(CPLEX_CFLAGS) \ 25 $(SOPLEX_CXXFLAGS) \ 26 $(CLP_CXXFLAGS) \ 27 $(CBC_CXXFLAGS) 28 29 lemon_libemon_la_LDFLAGS = \ 30 $(GLPK_LIBS) \ 31 $(CPLEX_LIBS) \ 32 $(SOPLEX_LIBS) \ 33 $(CLP_LIBS) \ 34 $(CBC_LIBS) 35 36 if HAVE_GLPK 37 lemon_libemon_la_SOURCES += lemon/glpk.cc 38 endif 39 40 if HAVE_CPLEX 41 lemon_libemon_la_SOURCES += lemon/cplex.cc 42 endif 43 44 if HAVE_SOPLEX 45 lemon_libemon_la_SOURCES += lemon/soplex.cc 46 endif 47 48 if HAVE_CLP 49 lemon_libemon_la_SOURCES += lemon/clp.cc 50 endif 51 52 if HAVE_CBC 53 lemon_libemon_la_SOURCES += lemon/cbc.cc 54 endif 20 55 21 56 lemon_HEADERS += \ 22 lemon/arg_parser.h \ 57 lemon/adaptors.h \ 58 lemon/arg_parser.h \ 23 59 lemon/assert.h \ 24 lemon/bfs.h \ 25 lemon/bin_heap.h \ 26 lemon/color.h \ 60 lemon/bellman_ford.h \ 61 lemon/bfs.h \ 62 lemon/bin_heap.h \ 63 lemon/binomial_heap.h \ 64 lemon/bucket_heap.h \ 65 lemon/capacity_scaling.h \ 66 lemon/cbc.h \ 67 lemon/circulation.h \ 68 lemon/clp.h \ 69 lemon/color.h \ 27 70 lemon/concept_check.h \ 28 lemon/counter.h \71 lemon/connectivity.h \ 29 72 lemon/core.h \ 30 lemon/dfs.h \ 31 lemon/dijkstra.h \ 32 lemon/dim2.h \ 73 lemon/cost_scaling.h \ 74 lemon/counter.h \ 75 lemon/cplex.h \ 76 lemon/cycle_canceling.h \ 77 lemon/dfs.h \ 78 lemon/dheap.h \ 79 lemon/dijkstra.h \ 80 lemon/dim2.h \ 81 lemon/dimacs.h \ 82 lemon/edge_set.h \ 83 lemon/elevator.h \ 33 84 lemon/error.h \ 34 lemon/graph_to_eps.h \ 85 lemon/euler.h \ 86 lemon/fib_heap.h \ 87 lemon/fractional_matching.h \ 88 lemon/full_graph.h \ 89 lemon/glpk.h \ 90 lemon/gomory_hu.h \ 91 lemon/graph_to_eps.h \ 92 lemon/grid_graph.h \ 93 lemon/grosso_locatelli_pullan_mc.h \ 94 lemon/hartmann_orlin_mmc.h \ 95 lemon/howard_mmc.h \ 96 lemon/hypercube_graph.h \ 97 lemon/karp_mmc.h \ 35 98 lemon/kruskal.h \ 99 lemon/hao_orlin.h \ 36 100 lemon/lgf_reader.h \ 37 101 lemon/lgf_writer.h \ 38 102 lemon/list_graph.h \ 103 lemon/lp.h \ 104 lemon/lp_base.h \ 105 lemon/lp_skeleton.h \ 39 106 lemon/maps.h \ 107 lemon/matching.h \ 40 108 lemon/math.h \ 109 lemon/min_cost_arborescence.h \ 110 lemon/nauty_reader.h \ 111 lemon/network_simplex.h \ 112 lemon/pairing_heap.h \ 41 113 lemon/path.h \ 42 lemon/random.h \ 114 lemon/planarity.h \ 115 lemon/preflow.h \ 116 lemon/quad_heap.h \ 117 lemon/radix_heap.h \ 118 lemon/radix_sort.h \ 119 lemon/random.h \ 43 120 lemon/smart_graph.h \ 44 lemon/time_measure.h \ 45 lemon/tolerance.h \ 121 lemon/soplex.h \ 122 lemon/static_graph.h \ 123 lemon/suurballe.h \ 124 lemon/time_measure.h \ 125 lemon/tolerance.h \ 46 126 lemon/unionfind.h \ 47 127 lemon/bits/windows.h … … 50 130 lemon/bits/alteration_notifier.h \ 51 131 lemon/bits/array_map.h \ 52 lemon/bits/base_extender.h \ 53 lemon/bits/bezier.h \ 132 lemon/bits/bezier.h \ 54 133 lemon/bits/default_map.h \ 55 lemon/bits/enable_if.h \ 134 lemon/bits/edge_set_extender.h \ 135 lemon/bits/enable_if.h \ 136 lemon/bits/graph_adaptor_extender.h \ 56 137 lemon/bits/graph_extender.h \ 57 138 lemon/bits/map_extender.h \ 58 139 lemon/bits/path_dump.h \ 140 lemon/bits/solver_bits.h \ 59 141 lemon/bits/traits.h \ 142 lemon/bits/variant.h \ 60 143 lemon/bits/vector_map.h 61 144 -
lemon/arg_parser.cc
r311 r877 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 21 21 namespace lemon { 22 22 23 void ArgParser::_terminate(ArgParserException::Reason reason) const 24 { 25 if(_exit_on_problems) 26 exit(1); 27 else throw(ArgParserException(reason)); 28 } 29 30 23 31 void ArgParser::_showHelp(void *p) 24 32 { 25 33 (static_cast<ArgParser*>(p))->showHelp(); 26 exit(1);34 (static_cast<ArgParser*>(p))->_terminate(ArgParserException::HELP); 27 35 } 28 36 29 37 ArgParser::ArgParser(int argc, const char * const *argv) 30 :_argc(argc), _argv(argv), _command_name(argv[0]) { 38 :_argc(argc), _argv(argv), _command_name(argv[0]), 39 _exit_on_problems(true) { 31 40 funcOption("-help","Print a short help message",_showHelp,this); 32 41 synonym("help","-help"); … … 343 352 i!=_others_help.end();++i) showHelp(i); 344 353 for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i); 345 exit(1);354 _terminate(ArgParserException::HELP); 346 355 } 347 356 … … 352 361 std::cerr << "\nType '" << _command_name << 353 362 " --help' to obtain a short summary on the usage.\n\n"; 354 exit(1);363 _terminate(ArgParserException::UNKNOWN_OPT); 355 364 } 356 365 … … 415 424 std::cerr << "\nType '" << _command_name << 416 425 " --help' to obtain a short summary on the usage.\n\n"; 417 exit(1);426 _terminate(ArgParserException::INVALID_OPT); 418 427 } 419 428 } -
lemon/arg_parser.h
r311 r879 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 35 35 namespace lemon { 36 36 37 ///Exception used by ArgParser 38 39 ///Exception used by ArgParser. 40 /// 41 class ArgParserException : public Exception { 42 public: 43 /// Reasons for failure 44 45 /// Reasons for failure. 46 /// 47 enum Reason { 48 HELP, ///< <tt>--help</tt> option was given. 49 UNKNOWN_OPT, ///< Unknown option was given. 50 INVALID_OPT ///< Invalid combination of options. 51 }; 52 53 private: 54 Reason _reason; 55 56 public: 57 ///Constructor 58 ArgParserException(Reason r) throw() : _reason(r) {} 59 ///Virtual destructor 60 virtual ~ArgParserException() throw() {} 61 ///A short description of the exception 62 virtual const char* what() const throw() { 63 switch(_reason) 64 { 65 case HELP: 66 return "lemon::ArgParseException: ask for help"; 67 break; 68 case UNKNOWN_OPT: 69 return "lemon::ArgParseException: unknown option"; 70 break; 71 case INVALID_OPT: 72 return "lemon::ArgParseException: invalid combination of options"; 73 break; 74 } 75 return ""; 76 } 77 ///Return the reason for the failure 78 Reason reason() const {return _reason; } 79 }; 80 81 37 82 ///Command line arguments parser 38 83 … … 116 161 const std::string &help, 117 162 void (*func)(void *),void *data); 163 164 bool _exit_on_problems; 165 166 void _terminate(ArgParserException::Reason reason) const; 118 167 119 168 public: … … 381 430 const std::vector<std::string> &files() const { return _file_args; } 382 431 432 ///Throw instead of exit in case of problems 433 void throwOnProblems() 434 { 435 _exit_on_problems=false; 436 } 383 437 }; 384 438 } -
lemon/assert.h
r290 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/base.cc
r220 r477 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 24 24 namespace lemon { 25 25 26 float Tolerance<float>::def_epsilon = 1e-4;26 float Tolerance<float>::def_epsilon = static_cast<float>(1e-4); 27 27 double Tolerance<double>::def_epsilon = 1e-10; 28 28 long double Tolerance<long double>::def_epsilon = 1e-14; -
lemon/bfs.h
r301 r877 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 48 48 ///The type of the map that stores the predecessor 49 49 ///arcs of the shortest paths. 50 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.50 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 51 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 ///Instantiates a PredMap.53 54 ///This function instantiates a PredMap.52 ///Instantiates a \c PredMap. 53 54 ///This function instantiates a \ref PredMap. 55 55 ///\param g is the digraph, to which we would like to define the 56 /// PredMap.56 ///\ref PredMap. 57 57 static PredMap *createPredMap(const Digraph &g) 58 58 { … … 63 63 64 64 ///The type of the map that indicates which nodes are processed. 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 65 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 66 ///By default, it is a NullMap. 66 67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 ///Instantiates a ProcessedMap.68 69 ///This function instantiates a ProcessedMap.68 ///Instantiates a \c ProcessedMap. 69 70 ///This function instantiates a \ref ProcessedMap. 70 71 ///\param g is the digraph, to which 71 ///we would like to define the ProcessedMap72 ///we would like to define the \ref ProcessedMap 72 73 #ifdef DOXYGEN 73 74 static ProcessedMap *createProcessedMap(const Digraph &g) … … 82 83 83 84 ///The type of the map that indicates which nodes are reached. 84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 ///It must conform to 86 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 87 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 ///Instantiates a ReachedMap.87 88 ///This function instantiates a ReachedMap.88 ///Instantiates a \c ReachedMap. 89 90 ///This function instantiates a \ref ReachedMap. 89 91 ///\param g is the digraph, to which 90 ///we would like to define the ReachedMap.92 ///we would like to define the \ref ReachedMap. 91 93 static ReachedMap *createReachedMap(const Digraph &g) 92 94 { … … 97 99 98 100 ///The type of the map that stores the distances of the nodes. 99 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.101 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 100 102 typedef typename Digraph::template NodeMap<int> DistMap; 101 ///Instantiates a DistMap.102 103 ///This function instantiates a DistMap.103 ///Instantiates a \c DistMap. 104 105 ///This function instantiates a \ref DistMap. 104 106 ///\param g is the digraph, to which we would like to define the 105 /// DistMap.107 ///\ref DistMap. 106 108 static DistMap *createDistMap(const Digraph &g) 107 109 { … … 120 122 /// 121 123 ///\tparam GR The type of the digraph the algorithm runs on. 122 ///The default value is \ref ListDigraph. The value of GR is not used 123 ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits. 124 ///\tparam TR Traits class to set various data types used by the algorithm. 125 ///The default traits class is 126 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>". 127 ///See \ref BfsDefaultTraits for the documentation of 128 ///a Bfs traits class. 124 ///The default type is \ref ListDigraph. 125 ///\tparam TR The traits class that defines various types used by the 126 ///algorithm. By default, it is \ref BfsDefaultTraits 127 ///"BfsDefaultTraits<GR>". 128 ///In most cases, this parameter should not be set directly, 129 ///consider to use the named template parameters instead. 129 130 #ifdef DOXYGEN 130 131 template <typename GR, … … 152 153 typedef PredMapPath<Digraph, PredMap> Path; 153 154 154 ///The traits class.155 ///The \ref BfsDefaultTraits "traits class" of the algorithm. 155 156 typedef TR Traits; 156 157 … … 214 215 typedef Bfs Create; 215 216 216 ///\name Named template parameters217 ///\name Named Template Parameters 217 218 218 219 ///@{ … … 228 229 }; 229 230 ///\brief \ref named-templ-param "Named parameter" for setting 230 /// PredMap type.231 ///\c PredMap type. 231 232 /// 232 233 ///\ref named-templ-param "Named parameter" for setting 233 ///PredMap type. 234 ///\c PredMap type. 235 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 234 236 template <class T> 235 237 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 247 249 }; 248 250 ///\brief \ref named-templ-param "Named parameter" for setting 249 /// DistMap type.251 ///\c DistMap type. 250 252 /// 251 253 ///\ref named-templ-param "Named parameter" for setting 252 ///DistMap type. 254 ///\c DistMap type. 255 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 253 256 template <class T> 254 257 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 266 269 }; 267 270 ///\brief \ref named-templ-param "Named parameter" for setting 268 /// ReachedMap type.271 ///\c ReachedMap type. 269 272 /// 270 273 ///\ref named-templ-param "Named parameter" for setting 271 ///ReachedMap type. 274 ///\c ReachedMap type. 275 ///It must conform to 276 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 272 277 template <class T> 273 278 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 285 290 }; 286 291 ///\brief \ref named-templ-param "Named parameter" for setting 287 /// ProcessedMap type.292 ///\c ProcessedMap type. 288 293 /// 289 294 ///\ref named-templ-param "Named parameter" for setting 290 ///ProcessedMap type. 295 ///\c ProcessedMap type. 296 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 291 297 template <class T> 292 298 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 303 309 }; 304 310 ///\brief \ref named-templ-param "Named parameter" for setting 305 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.311 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 306 312 /// 307 313 ///\ref named-templ-param "Named parameter" for setting 308 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.314 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 309 315 ///If you don't set it explicitly, it will be automatically allocated. 310 316 struct SetStandardProcessedMap : … … 341 347 342 348 ///Sets the map that stores the predecessor arcs. 343 ///If you don't use this function before calling \ref run(), 344 ///it will allocate one. The destructor deallocates this 345 ///automatically allocated map, of course. 349 ///If you don't use this function before calling \ref run(Node) "run()" 350 ///or \ref init(), an instance will be allocated automatically. 351 ///The destructor deallocates this automatically allocated map, 352 ///of course. 346 353 ///\return <tt> (*this) </tt> 347 354 Bfs &predMap(PredMap &m) … … 358 365 359 366 ///Sets the map that indicates which nodes are reached. 360 ///If you don't use this function before calling \ref run(), 361 ///it will allocate one. The destructor deallocates this 362 ///automatically allocated map, of course. 367 ///If you don't use this function before calling \ref run(Node) "run()" 368 ///or \ref init(), an instance will be allocated automatically. 369 ///The destructor deallocates this automatically allocated map, 370 ///of course. 363 371 ///\return <tt> (*this) </tt> 364 372 Bfs &reachedMap(ReachedMap &m) … … 375 383 376 384 ///Sets the map that indicates which nodes are processed. 377 ///If you don't use this function before calling \ref run(), 378 ///it will allocate one. The destructor deallocates this 379 ///automatically allocated map, of course. 385 ///If you don't use this function before calling \ref run(Node) "run()" 386 ///or \ref init(), an instance will be allocated automatically. 387 ///The destructor deallocates this automatically allocated map, 388 ///of course. 380 389 ///\return <tt> (*this) </tt> 381 390 Bfs &processedMap(ProcessedMap &m) … … 393 402 ///Sets the map that stores the distances of the nodes calculated by 394 403 ///the algorithm. 395 ///If you don't use this function before calling \ref run(), 396 ///it will allocate one. The destructor deallocates this 397 ///automatically allocated map, of course. 404 ///If you don't use this function before calling \ref run(Node) "run()" 405 ///or \ref init(), an instance will be allocated automatically. 406 ///The destructor deallocates this automatically allocated map, 407 ///of course. 398 408 ///\return <tt> (*this) </tt> 399 409 Bfs &distMap(DistMap &m) … … 409 419 public: 410 420 411 ///\name Execution control 412 ///The simplest way to execute the algorithm is to use 413 ///one of the member functions called \ref lemon::Bfs::run() "run()". 414 ///\n 415 ///If you need more control on the execution, first you must call 416 ///\ref lemon::Bfs::init() "init()", then you can add several source 417 ///nodes with \ref lemon::Bfs::addSource() "addSource()". 418 ///Finally \ref lemon::Bfs::start() "start()" will perform the 419 ///actual path computation. 421 ///\name Execution Control 422 ///The simplest way to execute the BFS algorithm is to use one of the 423 ///member functions called \ref run(Node) "run()".\n 424 ///If you need better control on the execution, you have to call 425 ///\ref init() first, then you can add several source nodes with 426 ///\ref addSource(). Finally the actual path computation can be 427 ///performed with one of the \ref start() functions. 420 428 421 429 ///@{ 422 430 431 ///\brief Initializes the internal data structures. 432 /// 423 433 ///Initializes the internal data structures. 424 425 ///Initializes the internal data structures.426 ///427 434 void init() 428 435 { … … 558 565 } 559 566 560 ///\brief Returns \c false if there are nodes 561 ///to be processed. 562 /// 563 ///Returns \c false if there are nodes 564 ///to be processed in the queue. 567 ///Returns \c false if there are nodes to be processed. 568 569 ///Returns \c false if there are nodes to be processed 570 ///in the queue. 565 571 bool emptyQueue() const { return _queue_tail==_queue_head; } 566 572 567 573 ///Returns the number of the nodes to be processed. 568 574 569 ///Returns the number of the nodes to be processed in the queue. 575 ///Returns the number of the nodes to be processed 576 ///in the queue. 570 577 int queueSize() const { return _queue_head-_queue_tail; } 571 578 … … 702 709 ///Runs the algorithm to visit all nodes in the digraph. 703 710 704 ///This method runs the %BFS algorithm in order to 705 ///compute the shortest path to each node. 706 /// 707 ///The algorithm computes 708 ///- the shortest path tree (forest), 709 ///- the distance of each node from the root(s). 711 ///This method runs the %BFS algorithm in order to visit all nodes 712 ///in the digraph. 710 713 /// 711 714 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 732 735 733 736 ///\name Query Functions 734 ///The result of the %BFS algorithm can be obtained using these737 ///The results of the BFS algorithm can be obtained using these 735 738 ///functions.\n 736 ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()737 /// "start()" must be calledbefore using them.739 ///Either \ref run(Node) "run()" or \ref start() should be called 740 ///before using them. 738 741 739 742 ///@{ 740 743 741 ///The shortest path to anode.742 743 ///Returns the shortest path to a node.744 /// 745 ///\warning \c t should be reach ablefrom the root(s).746 /// 747 ///\pre Either \ref run( ) or \ref start() must be called before748 /// using this function.744 ///The shortest path to the given node. 745 746 ///Returns the shortest path to the given node from the root(s). 747 /// 748 ///\warning \c t should be reached from the root(s). 749 /// 750 ///\pre Either \ref run(Node) "run()" or \ref init() 751 ///must be called before using this function. 749 752 Path path(Node t) const { return Path(*G, *_pred, t); } 750 753 751 ///The distance of anode from the root(s).752 753 ///Returns the distance of anode from the root(s).754 /// 755 ///\warning If node \c v is not reach ablefrom the root(s), then754 ///The distance of the given node from the root(s). 755 756 ///Returns the distance of the given node from the root(s). 757 /// 758 ///\warning If node \c v is not reached from the root(s), then 756 759 ///the return value of this function is undefined. 757 760 /// 758 ///\pre Either \ref run( ) or \ref start() must be called before759 /// using this function.761 ///\pre Either \ref run(Node) "run()" or \ref init() 762 ///must be called before using this function. 760 763 int dist(Node v) const { return (*_dist)[v]; } 761 764 762 ///Returns the 'previous arc' of the shortest path tree for a node. 763 765 ///\brief Returns the 'previous arc' of the shortest path tree for 766 ///the given node. 767 /// 764 768 ///This function returns the 'previous arc' of the shortest path 765 769 ///tree for the node \c v, i.e. it returns the last arc of a 766 ///shortest path from the root(s)to \c v. It is \c INVALID if \c v767 ///is not reach ablefrom the root(s) or if \c v is a root.770 ///shortest path from a root to \c v. It is \c INVALID if \c v 771 ///is not reached from the root(s) or if \c v is a root. 768 772 /// 769 773 ///The shortest path tree used here is equal to the shortest path 770 ///tree used in \ref predNode() .771 /// 772 ///\pre Either \ref run( ) or \ref start() must be called before773 /// using this function.774 ///tree used in \ref predNode() and \ref predMap(). 775 /// 776 ///\pre Either \ref run(Node) "run()" or \ref init() 777 ///must be called before using this function. 774 778 Arc predArc(Node v) const { return (*_pred)[v];} 775 779 776 ///Returns the 'previous node' of the shortest path tree for a node. 777 780 ///\brief Returns the 'previous node' of the shortest path tree for 781 ///the given node. 782 /// 778 783 ///This function returns the 'previous node' of the shortest path 779 784 ///tree for the node \c v, i.e. it returns the last but one node 780 /// from a shortest path from the root(s)to \c v. It is \c INVALID781 ///if \c v is not reach ablefrom the root(s) or if \c v is a root.785 ///of a shortest path from a root to \c v. It is \c INVALID 786 ///if \c v is not reached from the root(s) or if \c v is a root. 782 787 /// 783 788 ///The shortest path tree used here is equal to the shortest path 784 ///tree used in \ref predArc() .785 /// 786 ///\pre Either \ref run( ) or \ref start() must be called before787 /// using this function.789 ///tree used in \ref predArc() and \ref predMap(). 790 /// 791 ///\pre Either \ref run(Node) "run()" or \ref init() 792 ///must be called before using this function. 788 793 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 789 794 G->source((*_pred)[v]); } … … 795 800 ///of the nodes calculated by the algorithm. 796 801 /// 797 ///\pre Either \ref run( )or \ref init()802 ///\pre Either \ref run(Node) "run()" or \ref init() 798 803 ///must be called before using this function. 799 804 const DistMap &distMap() const { return *_dist;} … … 803 808 /// 804 809 ///Returns a const reference to the node map that stores the predecessor 805 ///arcs, which form the shortest path tree .806 /// 807 ///\pre Either \ref run( )or \ref init()810 ///arcs, which form the shortest path tree (forest). 811 /// 812 ///\pre Either \ref run(Node) "run()" or \ref init() 808 813 ///must be called before using this function. 809 814 const PredMap &predMap() const { return *_pred;} 810 815 811 ///Checks if a node is reachable from the root(s). 812 813 ///Returns \c true if \c v is reachable from the root(s). 814 ///\pre Either \ref run() or \ref start() 816 ///Checks if the given node is reached from the root(s). 817 818 ///Returns \c true if \c v is reached from the root(s). 819 /// 820 ///\pre Either \ref run(Node) "run()" or \ref init() 815 821 ///must be called before using this function. 816 822 bool reached(Node v) const { return (*_reached)[v]; } … … 834 840 ///The type of the map that stores the predecessor 835 841 ///arcs of the shortest paths. 836 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.842 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 837 843 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 838 844 ///Instantiates a PredMap. … … 849 855 850 856 ///The type of the map that indicates which nodes are processed. 851 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.852 ///By default it is a NullMap.857 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 858 ///By default, it is a NullMap. 853 859 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 854 860 ///Instantiates a ProcessedMap. … … 869 875 870 876 ///The type of the map that indicates which nodes are reached. 871 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 877 ///It must conform to 878 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 872 879 typedef typename Digraph::template NodeMap<bool> ReachedMap; 873 880 ///Instantiates a ReachedMap. … … 884 891 885 892 ///The type of the map that stores the distances of the nodes. 886 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.893 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 887 894 typedef typename Digraph::template NodeMap<int> DistMap; 888 895 ///Instantiates a DistMap. … … 899 906 900 907 ///The type of the shortest paths. 901 ///It must meetthe \ref concepts::Path "Path" concept.908 ///It must conform to the \ref concepts::Path "Path" concept. 902 909 typedef lemon::Path<Digraph> Path; 903 910 }; … … 905 912 /// Default traits class used by BfsWizard 906 913 907 /// To make it easier to use Bfs algorithm 908 /// we have created a wizard class. 909 /// This \ref BfsWizard class needs default traits, 910 /// as well as the \ref Bfs class. 911 /// The \ref BfsWizardBase is a class to be the default traits of the 912 /// \ref BfsWizard class. 914 /// Default traits class used by BfsWizard. 915 /// \tparam GR The type of the digraph. 913 916 template<class GR> 914 917 class BfsWizardBase : public BfsWizardDefaultTraits<GR> … … 938 941 /// Constructor. 939 942 940 /// This constructor does not require parameters, thereforeit initiates943 /// This constructor does not require parameters, it initiates 941 944 /// all of the attributes to \c 0. 942 945 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 958 961 /// This auxiliary class is created to implement the 959 962 /// \ref bfs() "function-type interface" of \ref Bfs algorithm. 960 /// It does not have own \ref run( ) method, it uses the functions961 /// and features of the plain \ref Bfs.963 /// It does not have own \ref run(Node) "run()" method, it uses the 964 /// functions and features of the plain \ref Bfs. 962 965 /// 963 966 /// This class should only be used through the \ref bfs() function, 964 967 /// which makes it easier to use the algorithm. 968 /// 969 /// \tparam TR The traits class that defines various types used by the 970 /// algorithm. 965 971 template<class TR> 966 972 class BfsWizard : public TR … … 968 974 typedef TR Base; 969 975 970 ///The type of the digraph the algorithm runs on.971 976 typedef typename TR::Digraph Digraph; 972 977 … … 976 981 typedef typename Digraph::OutArcIt OutArcIt; 977 982 978 ///\brief The type of the map that stores the predecessor979 ///arcs of the shortest paths.980 983 typedef typename TR::PredMap PredMap; 981 ///\brief The type of the map that stores the distances of the nodes.982 984 typedef typename TR::DistMap DistMap; 983 ///\brief The type of the map that indicates which nodes are reached.984 985 typedef typename TR::ReachedMap ReachedMap; 985 ///\brief The type of the map that indicates which nodes are processed.986 986 typedef typename TR::ProcessedMap ProcessedMap; 987 ///The type of the shortest paths988 987 typedef typename TR::Path Path; 989 988 … … 1055 1054 ///Runs BFS algorithm to visit all nodes in the digraph. 1056 1055 1057 ///This method runs BFS algorithm in order to compute1058 /// the shortest path to each node.1056 ///This method runs BFS algorithm in order to visit all nodes 1057 ///in the digraph. 1059 1058 void run() 1060 1059 { … … 1068 1067 SetPredMapBase(const TR &b) : TR(b) {} 1069 1068 }; 1070 ///\brief \ref named-func-param "Named parameter" 1071 ///for setting PredMap object. 1072 /// 1073 ///\ref named-func-param "Named parameter" 1074 ///for setting PredMap object. 1069 1070 ///\brief \ref named-templ-param "Named parameter" for setting 1071 ///the predecessor map. 1072 /// 1073 ///\ref named-templ-param "Named parameter" function for setting 1074 ///the map that stores the predecessor arcs of the nodes. 1075 1075 template<class T> 1076 1076 BfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1086 1086 SetReachedMapBase(const TR &b) : TR(b) {} 1087 1087 }; 1088 ///\brief \ref named-func-param "Named parameter" 1089 ///for setting ReachedMap object. 1090 /// 1091 /// \ref named-func-param "Named parameter" 1092 ///for setting ReachedMap object. 1088 1089 ///\brief \ref named-templ-param "Named parameter" for setting 1090 ///the reached map. 1091 /// 1092 ///\ref named-templ-param "Named parameter" function for setting 1093 ///the map that indicates which nodes are reached. 1093 1094 template<class T> 1094 1095 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1104 1105 SetDistMapBase(const TR &b) : TR(b) {} 1105 1106 }; 1106 ///\brief \ref named-func-param "Named parameter" 1107 ///for setting DistMap object. 1108 /// 1109 /// \ref named-func-param "Named parameter" 1110 ///for setting DistMap object. 1107 1108 ///\brief \ref named-templ-param "Named parameter" for setting 1109 ///the distance map. 1110 /// 1111 ///\ref named-templ-param "Named parameter" function for setting 1112 ///the map that stores the distances of the nodes calculated 1113 ///by the algorithm. 1111 1114 template<class T> 1112 1115 BfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1122 1125 SetProcessedMapBase(const TR &b) : TR(b) {} 1123 1126 }; 1124 ///\brief \ref named-func-param "Named parameter" 1125 ///for setting ProcessedMap object. 1126 /// 1127 /// \ref named-func-param "Named parameter" 1128 ///for setting ProcessedMap object. 1127 1128 ///\brief \ref named-func-param "Named parameter" for setting 1129 ///the processed map. 1130 /// 1131 ///\ref named-templ-param "Named parameter" function for setting 1132 ///the map that indicates which nodes are processed. 1129 1133 template<class T> 1130 1134 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1179 1183 /// bool reached = bfs(g).path(p).dist(d).run(s,t); 1180 1184 ///\endcode 1181 ///\warning Don't forget to put the \ref BfsWizard::run( ) "run()"1185 ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()" 1182 1186 ///to the end of the parameter list. 1183 1187 ///\sa BfsWizard … … 1195 1199 /// This class defines the interface of the BfsVisit events, and 1196 1200 /// it could be the base of a real visitor class. 1197 template <typename _Digraph>1201 template <typename GR> 1198 1202 struct BfsVisitor { 1199 typedef _DigraphDigraph;1203 typedef GR Digraph; 1200 1204 typedef typename Digraph::Arc Arc; 1201 1205 typedef typename Digraph::Node Node; … … 1225 1229 }; 1226 1230 #else 1227 template <typename _Digraph>1231 template <typename GR> 1228 1232 struct BfsVisitor { 1229 typedef _DigraphDigraph;1233 typedef GR Digraph; 1230 1234 typedef typename Digraph::Arc Arc; 1231 1235 typedef typename Digraph::Node Node; … … 1255 1259 /// 1256 1260 /// Default traits class of BfsVisit class. 1257 /// \tparam _DigraphThe type of the digraph the algorithm runs on.1258 template<class _Digraph>1261 /// \tparam GR The type of the digraph the algorithm runs on. 1262 template<class GR> 1259 1263 struct BfsVisitDefaultTraits { 1260 1264 1261 1265 /// \brief The type of the digraph the algorithm runs on. 1262 typedef _DigraphDigraph;1266 typedef GR Digraph; 1263 1267 1264 1268 /// \brief The type of the map that indicates which nodes are reached. 1265 1269 /// 1266 1270 /// The type of the map that indicates which nodes are reached. 1267 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1271 /// It must conform to 1272 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1268 1273 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1269 1274 … … 1281 1286 /// \ingroup search 1282 1287 /// 1283 /// \brief %BFS algorithm class with visitor interface.1288 /// \brief BFS algorithm class with visitor interface. 1284 1289 /// 1285 /// This class provides an efficient implementation of the %BFS algorithm1290 /// This class provides an efficient implementation of the BFS algorithm 1286 1291 /// with visitor interface. 1287 1292 /// 1288 /// The %BfsVisit class provides an alternative interface to the Bfs1293 /// The BfsVisit class provides an alternative interface to the Bfs 1289 1294 /// class. It works with callback mechanism, the BfsVisit object calls 1290 1295 /// the member functions of the \c Visitor class on every BFS event. … … 1295 1300 /// instead. 1296 1301 /// 1297 /// \tparam _DigraphThe type of the digraph the algorithm runs on.1298 /// The default value is1299 /// \ref ListDigraph. The value of _Digraph is not used directly by1300 /// \ref BfsVisit,it is only passed to \ref BfsVisitDefaultTraits.1301 /// \tparam _VisitorThe Visitor type that is used by the algorithm.1302 /// \ref BfsVisitor "BfsVisitor< _Digraph>" is an empty visitor, which1302 /// \tparam GR The type of the digraph the algorithm runs on. 1303 /// The default type is \ref ListDigraph. 1304 /// The value of GR is not used directly by \ref BfsVisit, 1305 /// it is only passed to \ref BfsVisitDefaultTraits. 1306 /// \tparam VS The Visitor type that is used by the algorithm. 1307 /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which 1303 1308 /// does not observe the BFS events. If you want to observe the BFS 1304 1309 /// events, you should implement your own visitor class. 1305 /// \tparam _Traits Traits class to set various datatypes used by the1306 /// algorithm. The default traits class is1307 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".1308 /// See \ref BfsVisitDefaultTraits for the documentation of1309 /// a BFS visit traits class.1310 /// \tparam TR The traits class that defines various types used by the 1311 /// algorithm. By default, it is \ref BfsVisitDefaultTraits 1312 /// "BfsVisitDefaultTraits<GR>". 1313 /// In most cases, this parameter should not be set directly, 1314 /// consider to use the named template parameters instead. 1310 1315 #ifdef DOXYGEN 1311 template <typename _Digraph, typename _Visitor, typename _Traits>1316 template <typename GR, typename VS, typename TR> 1312 1317 #else 1313 template <typename _Digraph= ListDigraph,1314 typename _Visitor = BfsVisitor<_Digraph>,1315 typename _Traits = BfsVisitDefaultTraits<_Digraph> >1318 template <typename GR = ListDigraph, 1319 typename VS = BfsVisitor<GR>, 1320 typename TR = BfsVisitDefaultTraits<GR> > 1316 1321 #endif 1317 1322 class BfsVisit { … … 1319 1324 1320 1325 ///The traits class. 1321 typedef _TraitsTraits;1326 typedef TR Traits; 1322 1327 1323 1328 ///The type of the digraph the algorithm runs on. … … 1325 1330 1326 1331 ///The visitor type used by the algorithm. 1327 typedef _VisitorVisitor;1332 typedef VS Visitor; 1328 1333 1329 1334 ///The type of the map that indicates which nodes are reached. … … 1365 1370 typedef BfsVisit Create; 1366 1371 1367 /// \name Named template parameters1372 /// \name Named Template Parameters 1368 1373 1369 1374 ///@{ … … 1407 1412 /// 1408 1413 /// Sets the map that indicates which nodes are reached. 1409 /// If you don't use this function before calling \ref run(), 1410 /// it will allocate one. The destructor deallocates this 1411 /// automatically allocated map, of course. 1414 /// If you don't use this function before calling \ref run(Node) "run()" 1415 /// or \ref init(), an instance will be allocated automatically. 1416 /// The destructor deallocates this automatically allocated map, 1417 /// of course. 1412 1418 /// \return <tt> (*this) </tt> 1413 1419 BfsVisit &reachedMap(ReachedMap &m) { … … 1422 1428 public: 1423 1429 1424 /// \name Execution control 1425 /// The simplest way to execute the algorithm is to use 1426 /// one of the member functions called \ref lemon::BfsVisit::run() 1427 /// "run()". 1428 /// \n 1429 /// If you need more control on the execution, first you must call 1430 /// \ref lemon::BfsVisit::init() "init()", then you can add several 1431 /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()". 1432 /// Finally \ref lemon::BfsVisit::start() "start()" will perform the 1433 /// actual path computation. 1430 /// \name Execution Control 1431 /// The simplest way to execute the BFS algorithm is to use one of the 1432 /// member functions called \ref run(Node) "run()".\n 1433 /// If you need better control on the execution, you have to call 1434 /// \ref init() first, then you can add several source nodes with 1435 /// \ref addSource(). Finally the actual path computation can be 1436 /// performed with one of the \ref start() functions. 1434 1437 1435 1438 /// @{ … … 1701 1704 /// \brief Runs the algorithm to visit all nodes in the digraph. 1702 1705 /// 1703 /// This method runs the %BFS algorithm in order to 1704 /// compute the shortest path to each node. 1705 /// 1706 /// The algorithm computes 1707 /// - the shortest path tree (forest), 1708 /// - the distance of each node from the root(s). 1706 /// This method runs the %BFS algorithm in order to visit all nodes 1707 /// in the digraph. 1709 1708 /// 1710 1709 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 1731 1730 1732 1731 /// \name Query Functions 1733 /// The result of the %BFS algorithm can be obtained using these1732 /// The results of the BFS algorithm can be obtained using these 1734 1733 /// functions.\n 1735 /// Either \ref lemon::BfsVisit::run() "run()" or1736 /// \ref lemon::BfsVisit::start() "start()" must be called before1737 /// using them. 1734 /// Either \ref run(Node) "run()" or \ref start() should be called 1735 /// before using them. 1736 1738 1737 ///@{ 1739 1738 1740 /// \brief Checks if a node is reachable from the root(s). 1741 /// 1742 /// Returns \c true if \c v is reachable from the root(s). 1743 /// \pre Either \ref run() or \ref start() 1739 /// \brief Checks if the given node is reached from the root(s). 1740 /// 1741 /// Returns \c true if \c v is reached from the root(s). 1742 /// 1743 /// \pre Either \ref run(Node) "run()" or \ref init() 1744 1744 /// must be called before using this function. 1745 bool reached(Node v) { return (*_reached)[v]; }1745 bool reached(Node v) const { return (*_reached)[v]; } 1746 1746 1747 1747 ///@} -
lemon/bin_heap.h
r209 r711 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 20 20 #define LEMON_BIN_HEAP_H 21 21 22 ///\ingroup auxdat22 ///\ingroup heaps 23 23 ///\file 24 ///\brief Binary Heap implementation.24 ///\brief Binary heap implementation. 25 25 26 26 #include <vector> … … 30 30 namespace lemon { 31 31 32 /// \ingroup auxdat32 /// \ingroup heaps 33 33 /// 34 /// \brief A Binary Heap implementation.34 /// \brief Binary heap data structure. 35 35 /// 36 ///This class implements the \e binary \e heap data structure. A \e heap 37 ///is a data structure for storing items with specified values called \e 38 ///priorities in such a way that finding the item with minimum priority is 39 ///efficient. \c Compare specifies the ordering of the priorities. In a heap 40 ///one can change the priority of an item, add or erase an item, etc. 36 /// This class implements the \e binary \e heap data structure. 37 /// It fully conforms to the \ref concepts::Heap "heap concept". 41 38 /// 42 /// \tparam _Prio Type of the priorityof the items.43 /// \tparam _ItemIntMap A read and writable Item int map, used internally44 /// to handle the cross references.45 /// \tparam _Compare A class for the ordering of the priorities. The46 /// default is \c std::less<_Prio>.47 /// 48 ///\sa FibHeap49 ///\sa Dijkstra 50 template <typename _Prio, typename _ItemIntMap,51 typename _Compare = std::less<_Prio> > 39 /// \tparam PR Type of the priorities of the items. 40 /// \tparam IM A read-writable item map with \c int values, used 41 /// internally to handle the cross references. 42 /// \tparam CMP A functor class for comparing the priorities. 43 /// The default is \c std::less<PR>. 44 #ifdef DOXYGEN 45 template <typename PR, typename IM, typename CMP> 46 #else 47 template <typename PR, typename IM, typename CMP = std::less<PR> > 48 #endif 52 49 class BinHeap { 53 54 50 public: 55 ///\e 56 typedef _ItemIntMap ItemIntMap; 57 ///\e 58 typedef _Prio Prio; 59 ///\e 51 52 /// Type of the item-int map. 53 typedef IM ItemIntMap; 54 /// Type of the priorities. 55 typedef PR Prio; 56 /// Type of the items stored in the heap. 60 57 typedef typename ItemIntMap::Key Item; 61 /// \e58 /// Type of the item-priority pairs. 62 59 typedef std::pair<Item,Prio> Pair; 63 /// \e64 typedef _CompareCompare;65 66 /// \brief Type to represent the items states.67 /// 68 /// Each Item element have a state associated to it. It maybe "in heap",69 /// "pre heap" or "postheap". The latter two are indifferent from the60 /// Functor type for comparing the priorities. 61 typedef CMP Compare; 62 63 /// \brief Type to represent the states of the items. 64 /// 65 /// Each item has a state associated to it. It can be "in heap", 66 /// "pre-heap" or "post-heap". The latter two are indifferent from the 70 67 /// heap's point of view, but may be useful to the user. 71 68 /// 72 /// The ItemIntMap \e should be initialized in such way that it maps73 /// PRE_HEAP (-1) to any element to be put in the heap...69 /// The item-int map must be initialized in such way that it assigns 70 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 74 71 enum State { 75 IN_HEAP = 0, 76 PRE_HEAP = -1, 77 POST_HEAP = -2 72 IN_HEAP = 0, ///< = 0. 73 PRE_HEAP = -1, ///< = -1. 74 POST_HEAP = -2 ///< = -2. 78 75 }; 79 76 80 77 private: 81 std::vector<Pair> data;82 Compare comp;83 ItemIntMap & iim;78 std::vector<Pair> _data; 79 Compare _comp; 80 ItemIntMap &_iim; 84 81 85 82 public: 86 /// \brief The constructor. 87 /// 88 /// The constructor. 89 /// \param _iim should be given to the constructor, since it is used 90 /// internally to handle the cross references. The value of the map 91 /// should be PRE_HEAP (-1) for each element. 92 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {} 93 94 /// \brief The constructor. 95 /// 96 /// The constructor. 97 /// \param _iim should be given to the constructor, since it is used 98 /// internally to handle the cross references. The value of the map 99 /// should be PRE_HEAP (-1) for each element. 100 /// 101 /// \param _comp The comparator function object. 102 BinHeap(ItemIntMap &_iim, const Compare &_comp) 103 : iim(_iim), comp(_comp) {} 104 105 106 /// The number of items stored in the heap. 107 /// 108 /// \brief Returns the number of items stored in the heap. 109 int size() const { return data.size(); } 110 111 /// \brief Checks if the heap stores no items. 112 /// 113 /// Returns \c true if and only if the heap stores no items. 114 bool empty() const { return data.empty(); } 115 116 /// \brief Make empty this heap. 117 /// 118 /// Make empty this heap. It does not change the cross reference map. 119 /// If you want to reuse what is not surely empty you should first clear 120 /// the heap and after that you should set the cross reference map for 121 /// each item to \c PRE_HEAP. 83 84 /// \brief Constructor. 85 /// 86 /// Constructor. 87 /// \param map A map that assigns \c int values to the items. 88 /// It is used internally to handle the cross references. 89 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 90 explicit BinHeap(ItemIntMap &map) : _iim(map) {} 91 92 /// \brief Constructor. 93 /// 94 /// Constructor. 95 /// \param map A map that assigns \c int values to the items. 96 /// It is used internally to handle the cross references. 97 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 98 /// \param comp The function object used for comparing the priorities. 99 BinHeap(ItemIntMap &map, const Compare &comp) 100 : _iim(map), _comp(comp) {} 101 102 103 /// \brief The number of items stored in the heap. 104 /// 105 /// This function returns the number of items stored in the heap. 106 int size() const { return _data.size(); } 107 108 /// \brief Check if the heap is empty. 109 /// 110 /// This function returns \c true if the heap is empty. 111 bool empty() const { return _data.empty(); } 112 113 /// \brief Make the heap empty. 114 /// 115 /// This functon makes the heap empty. 116 /// It does not change the cross reference map. If you want to reuse 117 /// a heap that is not surely empty, you should first clear it and 118 /// then you should set the cross reference map to \c PRE_HEAP 119 /// for each item. 122 120 void clear() { 123 data.clear();121 _data.clear(); 124 122 } 125 123 … … 127 125 static int parent(int i) { return (i-1)/2; } 128 126 129 static int second _child(int i) { return 2*i+2; }127 static int secondChild(int i) { return 2*i+2; } 130 128 bool less(const Pair &p1, const Pair &p2) const { 131 return comp(p1.second, p2.second);132 } 133 134 int bubble _up(int hole, Pair p) {129 return _comp(p1.second, p2.second); 130 } 131 132 int bubbleUp(int hole, Pair p) { 135 133 int par = parent(hole); 136 while( hole>0 && less(p, data[par]) ) {137 move( data[par],hole);134 while( hole>0 && less(p,_data[par]) ) { 135 move(_data[par],hole); 138 136 hole = par; 139 137 par = parent(hole); … … 143 141 } 144 142 145 int bubble _down(int hole, Pair p, int length) {146 int child = second _child(hole);143 int bubbleDown(int hole, Pair p, int length) { 144 int child = secondChild(hole); 147 145 while(child < length) { 148 if( less( data[child-1],data[child]) ) {146 if( less(_data[child-1], _data[child]) ) { 149 147 --child; 150 148 } 151 if( !less( data[child], p) )149 if( !less(_data[child], p) ) 152 150 goto ok; 153 move( data[child], hole);151 move(_data[child], hole); 154 152 hole = child; 155 child = second _child(hole);153 child = secondChild(hole); 156 154 } 157 155 child--; 158 if( child<length && less( data[child], p) ) {159 move( data[child], hole);156 if( child<length && less(_data[child], p) ) { 157 move(_data[child], hole); 160 158 hole=child; 161 159 } … … 166 164 167 165 void move(const Pair &p, int i) { 168 data[i] = p;169 iim.set(p.first, i);166 _data[i] = p; 167 _iim.set(p.first, i); 170 168 } 171 169 172 170 public: 171 173 172 /// \brief Insert a pair of item and priority into the heap. 174 173 /// 175 /// Adds \c p.first to the heap with priority \c p.second. 174 /// This function inserts \c p.first to the heap with priority 175 /// \c p.second. 176 176 /// \param p The pair to insert. 177 /// \pre \c p.first must not be stored in the heap. 177 178 void push(const Pair &p) { 178 int n = data.size(); 179 data.resize(n+1); 180 bubble_up(n, p); 181 } 182 183 /// \brief Insert an item into the heap with the given heap. 184 /// 185 /// Adds \c i to the heap with priority \c p. 179 int n = _data.size(); 180 _data.resize(n+1); 181 bubbleUp(n, p); 182 } 183 184 /// \brief Insert an item into the heap with the given priority. 185 /// 186 /// This function inserts the given item into the heap with the 187 /// given priority. 186 188 /// \param i The item to insert. 187 189 /// \param p The priority of the item. 190 /// \pre \e i must not be stored in the heap. 188 191 void push(const Item &i, const Prio &p) { push(Pair(i,p)); } 189 192 190 /// \brief Returns the item with minimum priority relative to \c Compare. 191 /// 192 /// This method returns the item with minimum priority relative to \c 193 /// Compare. 194 /// \pre The heap must be nonempty. 193 /// \brief Return the item having minimum priority. 194 /// 195 /// This function returns the item having minimum priority. 196 /// \pre The heap must be non-empty. 195 197 Item top() const { 196 return data[0].first;197 } 198 199 /// \brief Returns the minimum priority relative to \c Compare.200 /// 201 /// It returns the minimum priority relative to \c Compare.202 /// \pre The heap must be non empty.198 return _data[0].first; 199 } 200 201 /// \brief The minimum priority. 202 /// 203 /// This function returns the minimum priority. 204 /// \pre The heap must be non-empty. 203 205 Prio prio() const { 204 return data[0].second; 205 } 206 207 /// \brief Deletes the item with minimum priority relative to \c Compare. 208 /// 209 /// This method deletes the item with minimum priority relative to \c 210 /// Compare from the heap. 206 return _data[0].second; 207 } 208 209 /// \brief Remove the item having minimum priority. 210 /// 211 /// This function removes the item having minimum priority. 211 212 /// \pre The heap must be non-empty. 212 213 void pop() { 213 int n = data.size()-1;214 iim.set(data[0].first, POST_HEAP);214 int n = _data.size()-1; 215 _iim.set(_data[0].first, POST_HEAP); 215 216 if (n > 0) { 216 bubble_down(0, data[n], n); 217 } 218 data.pop_back(); 219 } 220 221 /// \brief Deletes \c i from the heap. 222 /// 223 /// This method deletes item \c i from the heap. 224 /// \param i The item to erase. 225 /// \pre The item should be in the heap. 217 bubbleDown(0, _data[n], n); 218 } 219 _data.pop_back(); 220 } 221 222 /// \brief Remove the given item from the heap. 223 /// 224 /// This function removes the given item from the heap if it is 225 /// already stored. 226 /// \param i The item to delete. 227 /// \pre \e i must be in the heap. 226 228 void erase(const Item &i) { 227 int h = iim[i];228 int n = data.size()-1;229 iim.set(data[h].first, POST_HEAP);229 int h = _iim[i]; 230 int n = _data.size()-1; 231 _iim.set(_data[h].first, POST_HEAP); 230 232 if( h < n ) { 231 if ( bubble _up(h,data[n]) == h) {232 bubble _down(h,data[n], n);233 if ( bubbleUp(h, _data[n]) == h) { 234 bubbleDown(h, _data[n], n); 233 235 } 234 236 } 235 data.pop_back(); 236 } 237 238 239 /// \brief Returns the priority of \c i. 240 /// 241 /// This function returns the priority of item \c i. 242 /// \pre \c i must be in the heap. 243 /// \param i The item. 237 _data.pop_back(); 238 } 239 240 /// \brief The priority of the given item. 241 /// 242 /// This function returns the priority of the given item. 243 /// \param i The item. 244 /// \pre \e i must be in the heap. 244 245 Prio operator[](const Item &i) const { 245 int idx = iim[i]; 246 return data[idx].second; 247 } 248 249 /// \brief \c i gets to the heap with priority \c p independently 250 /// if \c i was already there. 251 /// 252 /// This method calls \ref push(\c i, \c p) if \c i is not stored 253 /// in the heap and sets the priority of \c i to \c p otherwise. 246 int idx = _iim[i]; 247 return _data[idx].second; 248 } 249 250 /// \brief Set the priority of an item or insert it, if it is 251 /// not stored in the heap. 252 /// 253 /// This method sets the priority of the given item if it is 254 /// already stored in the heap. Otherwise it inserts the given 255 /// item into the heap with the given priority. 254 256 /// \param i The item. 255 257 /// \param p The priority. 256 258 void set(const Item &i, const Prio &p) { 257 int idx = iim[i];259 int idx = _iim[i]; 258 260 if( idx < 0 ) { 259 261 push(i,p); 260 262 } 261 else if( comp(p,data[idx].second) ) {262 bubble _up(idx, Pair(i,p));263 else if( _comp(p, _data[idx].second) ) { 264 bubbleUp(idx, Pair(i,p)); 263 265 } 264 266 else { 265 bubble_down(idx, Pair(i,p), data.size()); 266 } 267 } 268 269 /// \brief Decreases the priority of \c i to \c p. 270 /// 271 /// This method decreases the priority of item \c i to \c p. 272 /// \pre \c i must be stored in the heap with priority at least \c 273 /// p relative to \c Compare. 267 bubbleDown(idx, Pair(i,p), _data.size()); 268 } 269 } 270 271 /// \brief Decrease the priority of an item to the given value. 272 /// 273 /// This function decreases the priority of an item to the given value. 274 274 /// \param i The item. 275 275 /// \param p The priority. 276 /// \pre \e i must be stored in the heap with priority at least \e p. 276 277 void decrease(const Item &i, const Prio &p) { 277 int idx = iim[i]; 278 bubble_up(idx, Pair(i,p)); 279 } 280 281 /// \brief Increases the priority of \c i to \c p. 282 /// 283 /// This method sets the priority of item \c i to \c p. 284 /// \pre \c i must be stored in the heap with priority at most \c 285 /// p relative to \c Compare. 278 int idx = _iim[i]; 279 bubbleUp(idx, Pair(i,p)); 280 } 281 282 /// \brief Increase the priority of an item to the given value. 283 /// 284 /// This function increases the priority of an item to the given value. 286 285 /// \param i The item. 287 286 /// \param p The priority. 287 /// \pre \e i must be stored in the heap with priority at most \e p. 288 288 void increase(const Item &i, const Prio &p) { 289 int idx = iim[i];290 bubble _down(idx, Pair(i,p),data.size());291 } 292 293 /// \brief Return s if \c item is in, has already been in, or has294 /// never been in the heap.295 /// 296 /// This method returns PRE_HEAP if \c item has never been in the297 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP298 /// otherwise. In the latter case it is possible that \c item will299 /// get backto the heap again.289 int idx = _iim[i]; 290 bubbleDown(idx, Pair(i,p), _data.size()); 291 } 292 293 /// \brief Return the state of an item. 294 /// 295 /// This method returns \c PRE_HEAP if the given item has never 296 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 297 /// and \c POST_HEAP otherwise. 298 /// In the latter case it is possible that the item will get back 299 /// to the heap again. 300 300 /// \param i The item. 301 301 State state(const Item &i) const { 302 int s = iim[i];302 int s = _iim[i]; 303 303 if( s>=0 ) 304 304 s=0; … … 306 306 } 307 307 308 /// \brief Set s the state of the \citem in the heap.309 /// 310 /// Sets the state of the \c item in the heap. It can be used to311 /// manually clear the heap when it is important to achive the312 /// better time complexity.308 /// \brief Set the state of an item in the heap. 309 /// 310 /// This function sets the state of the given item in the heap. 311 /// It can be used to manually clear the heap when it is important 312 /// to achive better time complexity. 313 313 /// \param i The item. 314 314 /// \param st The state. It should not be \c IN_HEAP. … … 320 320 erase(i); 321 321 } 322 iim[i] = st;322 _iim[i] = st; 323 323 break; 324 324 case IN_HEAP: … … 327 327 } 328 328 329 /// \brief Replaces an item in the heap. 330 /// 331 /// The \c i item is replaced with \c j item. The \c i item should 332 /// be in the heap, while the \c j should be out of the heap. The 333 /// \c i item will out of the heap and \c j will be in the heap 334 /// with the same prioriority as prevoiusly the \c i item. 329 /// \brief Replace an item in the heap. 330 /// 331 /// This function replaces item \c i with item \c j. 332 /// Item \c i must be in the heap, while \c j must be out of the heap. 333 /// After calling this method, item \c i will be out of the 334 /// heap and \c j will be in the heap with the same prioriority 335 /// as item \c i had before. 335 336 void replace(const Item& i, const Item& j) { 336 int idx = iim[i];337 iim.set(i,iim[j]);338 iim.set(j, idx);339 data[idx].first = j;337 int idx = _iim[i]; 338 _iim.set(i, _iim[j]); 339 _iim.set(j, idx); 340 _data[idx].first = j; 340 341 } 341 342 -
lemon/bits/alteration_notifier.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 36 36 // a container. 37 37 // 38 // The simple graph 's can be refered as two containers, onenode container39 // and one edge container. But they are not standard containersthey40 // does not store values directly they are just key continars for more41 // value containers which are thenode and edge maps.42 // 43 // The graph's node and edge sets can be changed as we add or erase38 // The simple graphs can be refered as two containers: a node container 39 // and an edge container. But they do not store values directly, they 40 // are just key continars for more value containers, which are the 41 // node and edge maps. 42 // 43 // The node and edge sets of the graphs can be changed as we add or erase 44 44 // nodes and edges in the graph. LEMON would like to handle easily 45 45 // that the node and edge maps should contain values for all nodes or 46 46 // edges. If we want to check on every indicing if the map contains 47 47 // the current indicing key that cause a drawback in the performance 48 // in the library. We use another solution we notify all maps about48 // in the library. We use another solution: we notify all maps about 49 49 // an alteration in the graph, which cause only drawback on the 50 50 // alteration of the graph. 51 51 // 52 // This class provides an interface to the container. The \e first() and \e 53 // next() member functions make possible to iterate on the keys of the 54 // container. The \e id() function returns an integer id for each key. 55 // The \e maxId() function gives back an upper bound of the ids. 52 // This class provides an interface to a node or edge container. 53 // The first() and next() member functions make possible 54 // to iterate on the keys of the container. 55 // The id() function returns an integer id for each key. 56 // The maxId() function gives back an upper bound of the ids. 56 57 // 57 58 // For the proper functonality of this class, we should notify it 58 // about each alteration in the container. The alterations have four type 59 // a s \e add(), \e erase(), \e build() and \e clear(). The \e add() and60 // \e erase() signalsthat only one or few items added or erased to or61 // from the graph. If all items are erased from the graph or from an empty62 // graph a new graph is buildedthen it can be signaled with the59 // about each alteration in the container. The alterations have four type: 60 // add(), erase(), build() and clear(). The add() and 61 // erase() signal that only one or few items added or erased to or 62 // from the graph. If all items are erased from the graph or if a new graph 63 // is built from an empty graph, then it can be signaled with the 63 64 // clear() and build() members. Important rule that if we erase items 64 // from graph we should first signal the alteration and after that erase65 // from graphs we should first signal the alteration and after that erase 65 66 // them from the container, on the other way on item addition we should 66 67 // first extend the container and just after that signal the alteration. 67 68 // 68 69 // The alteration can be observed with a class inherited from the 69 // \eObserverBase nested class. The signals can be handled with70 // ObserverBase nested class. The signals can be handled with 70 71 // overriding the virtual functions defined in the base class. The 71 72 // observer base can be attached to the notifier with the 72 // \eattach() member and can be detached with detach() function. The73 // attach() member and can be detached with detach() function. The 73 74 // alteration handlers should not call any function which signals 74 75 // an other alteration in the same notifier and should not 75 76 // detach any observer from the notifier. 76 77 // 77 // Alteration observers try to be exception safe. If an \eadd() or78 // a \eclear() function throws an exception then the remaining78 // Alteration observers try to be exception safe. If an add() or 79 // a clear() function throws an exception then the remaining 79 80 // observeres will not be notified and the fulfilled additions will 80 // be rolled back by calling the \e erase() or \e clear()81 // functions. Thence the \e erase() and \e clear() should not throw82 // exception. Actullay, it can be throw only \ref ImmediateDetach83 // exceptionwhich detach the observer from the notifier.84 // 85 // There are some placewhen the alteration observing is not completly81 // be rolled back by calling the erase() or clear() functions. 82 // Hence erase() and clear() should not throw exception. 83 // Actullay, they can throw only \ref ImmediateDetach exception, 84 // which detach the observer from the notifier. 85 // 86 // There are some cases, when the alteration observing is not completly 86 87 // reliable. If we want to carry out the node degree in the graph 87 // as in the \ref InDegMap and we use the reverse Edge that cause88 // as in the \ref InDegMap and we use the reverseArc(), then it cause 88 89 // unreliable functionality. Because the alteration observing signals 89 // only erasing and adding but not the reversing it will stores bad90 // degrees. The sub graph adaptors cannot signal the alterations because91 // just a setting in the filter map can modify the graph and this cannot92 // be watched in any way.90 // only erasing and adding but not the reversing, it will stores bad 91 // degrees. Apart form that the subgraph adaptors cannot even signal 92 // the alterations because just a setting in the filter map can modify 93 // the graph and this cannot be watched in any way. 93 94 // 94 95 // \param _Container The container which is observed. … … 104 105 typedef _Item Item; 105 106 106 // \brief Exception which can be called from \eclear() and107 // \eerase().108 // 109 // From the \e clear() and \eerase() function only this107 // \brief Exception which can be called from clear() and 108 // erase(). 109 // 110 // From the clear() and erase() function only this 110 111 // exception is allowed to throw. The exception immediatly 111 112 // detaches the current observer from the notifier. Because the 112 // \e clear() and \eerase() should not throw other exceptions113 // clear() and erase() should not throw other exceptions 113 114 // it can be used to invalidate the observer. 114 115 struct ImmediateDetach {}; … … 122 123 // The observer interface contains some pure virtual functions 123 124 // to override. The add() and erase() functions are 124 // to notify the oberver when one item is added or 125 // erased. 125 // to notify the oberver when one item is added or erased. 126 126 // 127 127 // The build() and clear() members are to notify the observer -
lemon/bits/array_map.h
r314 r877 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 37 37 // \brief Graph map based on the array storage. 38 38 // 39 // The ArrayMap template class is graph map structure what 40 // automatically updates the map when a key is added to or erased from 41 // the map. This map uses the allocators to implement 42 // the container functionality. 39 // The ArrayMap template class is graph map structure that automatically 40 // updates the map when a key is added to or erased from the graph. 41 // This map uses the allocators to implement the container functionality. 43 42 // 44 // The template parameters are the Graph the current Item type and43 // The template parameters are the Graph, the current Item type and 45 44 // the Value type of the map. 46 45 template <typename _Graph, typename _Item, typename _Value> … … 48 47 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { 49 48 public: 50 // The graph type of the maps.51 typedef _Graph Graph ;52 // The item type of the map.49 // The graph type. 50 typedef _Graph GraphType; 51 // The item type. 53 52 typedef _Item Item; 54 53 // The reference map tag. 55 54 typedef True ReferenceMapTag; 56 55 57 // The key type of the map s.56 // The key type of the map. 58 57 typedef _Item Key; 59 58 // The value type of the map. … … 65 64 typedef _Value& Reference; 66 65 66 // The map type. 67 typedef ArrayMap Map; 68 67 69 // The notifier type. 68 70 typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; 69 71 72 private: 73 70 74 // The MapBase of the Map which imlements the core regisitry function. 71 75 typedef typename Notifier::ObserverBase Parent; 72 76 73 private:74 77 typedef std::allocator<Value> Allocator; 75 78 … … 79 82 // 80 83 // Graph initialized map constructor. 81 explicit ArrayMap(const Graph & graph) {84 explicit ArrayMap(const GraphType& graph) { 82 85 Parent::attach(graph.notifier(Item())); 83 86 allocate_memory(); … … 93 96 // 94 97 // It constructs a map and initialize all of the the map. 95 ArrayMap(const Graph & graph, const Value& value) {98 ArrayMap(const GraphType& graph, const Value& value) { 96 99 Parent::attach(graph.notifier(Item())); 97 100 allocate_memory(); … … 137 140 // \brief Template assign operator. 138 141 // 139 // The given parameter should beconform to the ReadMap142 // The given parameter should conform to the ReadMap 140 143 // concecpt and could be indiced by the current item set of 141 144 // the NodeMap. In this case the value for each item … … 201 204 // \brief Adds a new key to the map. 202 205 // 203 // It adds a new key to the map. It called by the observer notifier206 // It adds a new key to the map. It is called by the observer notifier 204 207 // and it overrides the add() member function of the observer base. 205 208 virtual void add(const Key& key) { … … 229 232 // \brief Adds more new keys to the map. 230 233 // 231 // It adds more new keys to the map. It called by the observer notifier234 // It adds more new keys to the map. It is called by the observer notifier 232 235 // and it overrides the add() member function of the observer base. 233 236 virtual void add(const std::vector<Key>& keys) { … … 273 276 // \brief Erase a key from the map. 274 277 // 275 // Erase a key from the map. It called by the observer notifier278 // Erase a key from the map. It is called by the observer notifier 276 279 // and it overrides the erase() member function of the observer base. 277 280 virtual void erase(const Key& key) { … … 282 285 // \brief Erase more keys from the map. 283 286 // 284 // Erase more keys from the map. It called by the observer notifier287 // Erase more keys from the map. It is called by the observer notifier 285 288 // and it overrides the erase() member function of the observer base. 286 289 virtual void erase(const std::vector<Key>& keys) { … … 291 294 } 292 295 293 // \brief Build es the map.294 // 295 // It build es the map. Itcalled by the observer notifier296 // \brief Builds the map. 297 // 298 // It builds the map. It is called by the observer notifier 296 299 // and it overrides the build() member function of the observer base. 297 300 virtual void build() { … … 307 310 // \brief Clear the map. 308 311 // 309 // It erase all items from the map. It called by the observer notifier312 // It erase all items from the map. It is called by the observer notifier 310 313 // and it overrides the clear() member function of the observer base. 311 314 virtual void clear() { -
lemon/bits/bezier.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/default_map.h
r511 r877 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 154 154 class DefaultMap 155 155 : public DefaultMapSelector<_Graph, _Item, _Value>::Map { 156 typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent; 157 156 158 public: 157 typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;158 159 typedef DefaultMap<_Graph, _Item, _Value> Map; 159 160 160 typedef typename Parent::Graph Graph;161 typedef typename Parent::GraphType GraphType; 161 162 typedef typename Parent::Value Value; 162 163 163 explicit DefaultMap(const Graph & graph) : Parent(graph) {}164 DefaultMap(const Graph & graph, const Value& value)164 explicit DefaultMap(const GraphType& graph) : Parent(graph) {} 165 DefaultMap(const GraphType& graph, const Value& value) 165 166 : Parent(graph, value) {} 166 167 -
lemon/bits/enable_if.h
r314 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/graph_extender.h
r314 r778 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 30 30 //\ingroup graphbits 31 31 //\file 32 //\brief Extenders for the digraph types32 //\brief Extenders for the graph types 33 33 namespace lemon { 34 34 35 35 // \ingroup graphbits 36 36 // 37 // \brief Extender for the Digraphs37 // \brief Extender for the digraph implementations 38 38 template <typename Base> 39 39 class DigraphExtender : public Base { 40 typedef Base Parent; 41 40 42 public: 41 43 42 typedef Base Parent;43 44 typedef DigraphExtender Digraph; 44 45 … … 56 57 } 57 58 58 Node fromId(int id, Node) const{59 static Node fromId(int id, Node) { 59 60 return Parent::nodeFromId(id); 60 61 } 61 62 62 Arc fromId(int id, Arc) const{63 static Arc fromId(int id, Arc) { 63 64 return Parent::arcFromId(id); 64 65 } … … 219 220 class NodeMap 220 221 : public MapExtender<DefaultMap<Digraph, Node, _Value> > { 221 public:222 typedef DigraphExtender Digraph;223 222 typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent; 224 223 224 public: 225 225 explicit NodeMap(const Digraph& digraph) 226 226 : Parent(digraph) {} … … 244 244 class ArcMap 245 245 : public MapExtender<DefaultMap<Digraph, Arc, _Value> > { 246 public:247 typedef DigraphExtender Digraph;248 246 typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent; 249 247 248 public: 250 249 explicit ArcMap(const Digraph& digraph) 251 250 : Parent(digraph) {} … … 331 330 template <typename Base> 332 331 class GraphExtender : public Base { 332 typedef Base Parent; 333 333 334 public: 334 335 335 typedef Base Parent;336 336 typedef GraphExtender Graph; 337 337 … … 356 356 } 357 357 358 Node fromId(int id, Node) const{358 static Node fromId(int id, Node) { 359 359 return Parent::nodeFromId(id); 360 360 } 361 361 362 Arc fromId(int id, Arc) const{362 static Arc fromId(int id, Arc) { 363 363 return Parent::arcFromId(id); 364 364 } 365 365 366 Edge fromId(int id, Edge) const{366 static Edge fromId(int id, Edge) { 367 367 return Parent::edgeFromId(id); 368 368 } … … 602 602 class NodeMap 603 603 : public MapExtender<DefaultMap<Graph, Node, _Value> > { 604 public:605 typedef GraphExtender Graph;606 604 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent; 607 605 608 NodeMap(const Graph& graph) 606 public: 607 explicit NodeMap(const Graph& graph) 609 608 : Parent(graph) {} 610 609 NodeMap(const Graph& graph, const _Value& value) … … 627 626 class ArcMap 628 627 : public MapExtender<DefaultMap<Graph, Arc, _Value> > { 629 public:630 typedef GraphExtender Graph;631 628 typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent; 632 629 633 ArcMap(const Graph& graph) 630 public: 631 explicit ArcMap(const Graph& graph) 634 632 : Parent(graph) {} 635 633 ArcMap(const Graph& graph, const _Value& value) … … 652 650 class EdgeMap 653 651 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 654 public:655 typedef GraphExtender Graph;656 652 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 657 653 658 EdgeMap(const Graph& graph) 654 public: 655 explicit EdgeMap(const Graph& graph) 659 656 : Parent(graph) {} 660 657 -
lemon/bits/map_extender.h
r801 r802 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 37 37 template <typename _Map> 38 38 class MapExtender : public _Map { 39 public:40 41 39 typedef _Map Parent; 40 typedef typename Parent::GraphType GraphType; 41 42 public: 43 42 44 typedef MapExtender Map; 43 44 45 typedef typename Parent::Graph Graph;46 45 typedef typename Parent::Key Item; 47 46 48 47 typedef typename Parent::Key Key; 49 48 typedef typename Parent::Value Value; 49 typedef typename Parent::Reference Reference; 50 typedef typename Parent::ConstReference ConstReference; 51 52 typedef typename Parent::ReferenceMapTag ReferenceMapTag; 50 53 51 54 class MapIt; … … 57 60 public: 58 61 59 MapExtender(const Graph & graph)62 MapExtender(const GraphType& graph) 60 63 : Parent(graph) {} 61 64 62 MapExtender(const Graph & graph, const Value& value)65 MapExtender(const GraphType& graph, const Value& value) 63 66 : Parent(graph, value) {} 64 67 … … 76 79 public: 77 80 class MapIt : public Item { 78 public: 79 80 typedef Item Parent; 81 typedef Item Parent; 82 83 public: 84 81 85 typedef typename Map::Value Value; 82 86 … … 115 119 116 120 class ConstMapIt : public Item { 117 public:118 119 typedef Item Parent;121 typedef Item Parent; 122 123 public: 120 124 121 125 typedef typename Map::Value Value; … … 146 150 147 151 class ItemIt : public Item { 148 public: 149 150 typedef Item Parent; 151 152 typedef Item Parent; 153 154 public: 152 155 ItemIt() : map(NULL) {} 156 153 157 154 158 ItemIt(Invalid i) : Parent(i), map(NULL) {} … … 177 181 template <typename _Graph, typename _Map> 178 182 class SubMapExtender : public _Map { 179 public:180 181 183 typedef _Map Parent; 184 typedef _Graph GraphType; 185 186 public: 187 182 188 typedef SubMapExtender Map; 183 184 typedef _Graph Graph;185 186 189 typedef typename Parent::Key Item; 187 190 188 191 typedef typename Parent::Key Key; 189 192 typedef typename Parent::Value Value; 193 typedef typename Parent::Reference Reference; 194 typedef typename Parent::ConstReference ConstReference; 195 196 typedef typename Parent::ReferenceMapTag ReferenceMapTag; 190 197 191 198 class MapIt; … … 197 204 public: 198 205 199 SubMapExtender(const Graph & _graph)206 SubMapExtender(const GraphType& _graph) 200 207 : Parent(_graph), graph(_graph) {} 201 208 202 SubMapExtender(const Graph & _graph, const Value& _value)209 SubMapExtender(const GraphType& _graph, const Value& _value) 203 210 : Parent(_graph, _value), graph(_graph) {} 204 211 … … 220 227 public: 221 228 class MapIt : public Item { 222 public:223 224 typedef Item Parent;229 typedef Item Parent; 230 231 public: 225 232 typedef typename Map::Value Value; 226 233 … … 259 266 260 267 class ConstMapIt : public Item { 261 public:262 263 typedef Item Parent;268 typedef Item Parent; 269 270 public: 264 271 265 272 typedef typename Map::Value Value; … … 290 297 291 298 class ItemIt : public Item { 292 public: 293 294 typedef Item Parent; 295 299 typedef Item Parent; 300 301 public: 296 302 ItemIt() : map(NULL) {} 303 297 304 298 305 ItemIt(Invalid i) : Parent(i), map(NULL) { } … … 317 324 private: 318 325 319 const Graph & graph;326 const GraphType& graph; 320 327 321 328 }; -
lemon/bits/path_dump.h
r886 r887 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 17 17 */ 18 18 19 #ifndef LEMON_BITS_PRED_MAP_PATH_H 20 #define LEMON_BITS_PRED_MAP_PATH_H 19 #ifndef LEMON_BITS_PATH_DUMP_H 20 #define LEMON_BITS_PATH_DUMP_H 21 22 #include <lemon/core.h> 23 #include <lemon/concept_check.h> 21 24 22 25 namespace lemon { -
lemon/bits/traits.h
r314 r616 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 30 30 struct InvalidType {}; 31 31 32 template <typename _Graph, typename _Item>32 template <typename GR, typename _Item> 33 33 class ItemSetTraits {}; 34 34 35 35 36 template <typename G raph, typename Enable = void>36 template <typename GR, typename Enable = void> 37 37 struct NodeNotifierIndicator { 38 38 typedef InvalidType Type; 39 39 }; 40 template <typename G raph>40 template <typename GR> 41 41 struct NodeNotifierIndicator< 42 G raph,43 typename enable_if<typename G raph::NodeNotifier::Notifier, void>::type44 > { 45 typedef typename G raph::NodeNotifier Type;46 }; 47 48 template <typename _Graph>49 class ItemSetTraits< _Graph, typename _Graph::Node> {42 GR, 43 typename enable_if<typename GR::NodeNotifier::Notifier, void>::type 44 > { 45 typedef typename GR::NodeNotifier Type; 46 }; 47 48 template <typename GR> 49 class ItemSetTraits<GR, typename GR::Node> { 50 50 public: 51 51 52 typedef _Graph Graph; 53 54 typedef typename Graph::Node Item; 55 typedef typename Graph::NodeIt ItemIt; 56 57 typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier; 58 59 template <typename _Value> 60 class Map : public Graph::template NodeMap<_Value> { 52 typedef GR Graph; 53 typedef GR Digraph; 54 55 typedef typename GR::Node Item; 56 typedef typename GR::NodeIt ItemIt; 57 58 typedef typename NodeNotifierIndicator<GR>::Type ItemNotifier; 59 60 template <typename V> 61 class Map : public GR::template NodeMap<V> { 62 typedef typename GR::template NodeMap<V> Parent; 63 61 64 public: 62 typedef typename Graph::template NodeMap<_Value> Parent; 63 typedef typename Graph::template NodeMap<_Value> Type; 65 typedef typename GR::template NodeMap<V> Type; 64 66 typedef typename Parent::Value Value; 65 67 66 Map(const G raph& _digraph) : Parent(_digraph) {}67 Map(const G raph& _digraph, const Value& _value)68 Map(const GR& _digraph) : Parent(_digraph) {} 69 Map(const GR& _digraph, const Value& _value) 68 70 : Parent(_digraph, _value) {} 69 71 … … 72 74 }; 73 75 74 template <typename G raph, typename Enable = void>76 template <typename GR, typename Enable = void> 75 77 struct ArcNotifierIndicator { 76 78 typedef InvalidType Type; 77 79 }; 78 template <typename G raph>80 template <typename GR> 79 81 struct ArcNotifierIndicator< 80 G raph,81 typename enable_if<typename G raph::ArcNotifier::Notifier, void>::type82 > { 83 typedef typename G raph::ArcNotifier Type;84 }; 85 86 template <typename _Graph>87 class ItemSetTraits< _Graph, typename _Graph::Arc> {82 GR, 83 typename enable_if<typename GR::ArcNotifier::Notifier, void>::type 84 > { 85 typedef typename GR::ArcNotifier Type; 86 }; 87 88 template <typename GR> 89 class ItemSetTraits<GR, typename GR::Arc> { 88 90 public: 89 91 90 typedef _Graph Graph; 91 92 typedef typename Graph::Arc Item; 93 typedef typename Graph::ArcIt ItemIt; 94 95 typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier; 96 97 template <typename _Value> 98 class Map : public Graph::template ArcMap<_Value> { 92 typedef GR Graph; 93 typedef GR Digraph; 94 95 typedef typename GR::Arc Item; 96 typedef typename GR::ArcIt ItemIt; 97 98 typedef typename ArcNotifierIndicator<GR>::Type ItemNotifier; 99 100 template <typename V> 101 class Map : public GR::template ArcMap<V> { 102 typedef typename GR::template ArcMap<V> Parent; 103 99 104 public: 100 typedef typename Graph::template ArcMap<_Value> Parent; 101 typedef typename Graph::template ArcMap<_Value> Type; 105 typedef typename GR::template ArcMap<V> Type; 102 106 typedef typename Parent::Value Value; 103 107 104 Map(const G raph& _digraph) : Parent(_digraph) {}105 Map(const G raph& _digraph, const Value& _value)108 Map(const GR& _digraph) : Parent(_digraph) {} 109 Map(const GR& _digraph, const Value& _value) 106 110 : Parent(_digraph, _value) {} 107 111 }; … … 109 113 }; 110 114 111 template <typename G raph, typename Enable = void>115 template <typename GR, typename Enable = void> 112 116 struct EdgeNotifierIndicator { 113 117 typedef InvalidType Type; 114 118 }; 115 template <typename G raph>119 template <typename GR> 116 120 struct EdgeNotifierIndicator< 117 G raph,118 typename enable_if<typename G raph::EdgeNotifier::Notifier, void>::type119 > { 120 typedef typename G raph::EdgeNotifier Type;121 }; 122 123 template <typename _Graph>124 class ItemSetTraits< _Graph, typename _Graph::Edge> {121 GR, 122 typename enable_if<typename GR::EdgeNotifier::Notifier, void>::type 123 > { 124 typedef typename GR::EdgeNotifier Type; 125 }; 126 127 template <typename GR> 128 class ItemSetTraits<GR, typename GR::Edge> { 125 129 public: 126 130 127 typedef _Graph Graph; 128 129 typedef typename Graph::Edge Item; 130 typedef typename Graph::EdgeIt ItemIt; 131 132 typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier; 133 134 template <typename _Value> 135 class Map : public Graph::template EdgeMap<_Value> { 131 typedef GR Graph; 132 typedef GR Digraph; 133 134 typedef typename GR::Edge Item; 135 typedef typename GR::EdgeIt ItemIt; 136 137 typedef typename EdgeNotifierIndicator<GR>::Type ItemNotifier; 138 139 template <typename V> 140 class Map : public GR::template EdgeMap<V> { 141 typedef typename GR::template EdgeMap<V> Parent; 142 136 143 public: 137 typedef typename Graph::template EdgeMap<_Value> Parent; 138 typedef typename Graph::template EdgeMap<_Value> Type; 144 typedef typename GR::template EdgeMap<V> Type; 139 145 typedef typename Parent::Value Value; 140 146 141 Map(const G raph& _digraph) : Parent(_digraph) {}142 Map(const G raph& _digraph, const Value& _value)147 Map(const GR& _digraph) : Parent(_digraph) {} 148 Map(const GR& _digraph, const Value& _value) 143 149 : Parent(_digraph, _value) {} 144 150 }; … … 205 211 // Indicators for the tags 206 212 207 template <typename G raph, typename Enable = void>213 template <typename GR, typename Enable = void> 208 214 struct NodeNumTagIndicator { 209 215 static const bool value = false; 210 216 }; 211 217 212 template <typename G raph>218 template <typename GR> 213 219 struct NodeNumTagIndicator< 214 Graph, 215 typename enable_if<typename Graph::NodeNumTag, void>::type 216 > { 217 static const bool value = true; 218 }; 219 220 template <typename Graph, typename Enable = void> 220 GR, 221 typename enable_if<typename GR::NodeNumTag, void>::type 222 > { 223 static const bool value = true; 224 }; 225 226 template <typename GR, typename Enable = void> 227 struct ArcNumTagIndicator { 228 static const bool value = false; 229 }; 230 231 template <typename GR> 232 struct ArcNumTagIndicator< 233 GR, 234 typename enable_if<typename GR::ArcNumTag, void>::type 235 > { 236 static const bool value = true; 237 }; 238 239 template <typename GR, typename Enable = void> 221 240 struct EdgeNumTagIndicator { 222 241 static const bool value = false; 223 242 }; 224 243 225 template <typename G raph>244 template <typename GR> 226 245 struct EdgeNumTagIndicator< 227 Graph, 228 typename enable_if<typename Graph::EdgeNumTag, void>::type 229 > { 230 static const bool value = true; 231 }; 232 233 template <typename Graph, typename Enable = void> 246 GR, 247 typename enable_if<typename GR::EdgeNumTag, void>::type 248 > { 249 static const bool value = true; 250 }; 251 252 template <typename GR, typename Enable = void> 253 struct FindArcTagIndicator { 254 static const bool value = false; 255 }; 256 257 template <typename GR> 258 struct FindArcTagIndicator< 259 GR, 260 typename enable_if<typename GR::FindArcTag, void>::type 261 > { 262 static const bool value = true; 263 }; 264 265 template <typename GR, typename Enable = void> 234 266 struct FindEdgeTagIndicator { 235 267 static const bool value = false; 236 268 }; 237 269 238 template <typename G raph>270 template <typename GR> 239 271 struct FindEdgeTagIndicator< 240 G raph,241 typename enable_if<typename G raph::FindEdgeTag, void>::type242 > { 243 static const bool value = true; 244 }; 245 246 template <typename G raph, typename Enable = void>272 GR, 273 typename enable_if<typename GR::FindEdgeTag, void>::type 274 > { 275 static const bool value = true; 276 }; 277 278 template <typename GR, typename Enable = void> 247 279 struct UndirectedTagIndicator { 248 280 static const bool value = false; 249 281 }; 250 282 251 template <typename G raph>283 template <typename GR> 252 284 struct UndirectedTagIndicator< 253 G raph,254 typename enable_if<typename G raph::UndirectedTag, void>::type255 > { 256 static const bool value = true; 257 }; 258 259 template <typename G raph, typename Enable = void>285 GR, 286 typename enable_if<typename GR::UndirectedTag, void>::type 287 > { 288 static const bool value = true; 289 }; 290 291 template <typename GR, typename Enable = void> 260 292 struct BuildTagIndicator { 261 293 static const bool value = false; 262 294 }; 263 295 264 template <typename G raph>296 template <typename GR> 265 297 struct BuildTagIndicator< 266 G raph,267 typename enable_if<typename G raph::BuildTag, void>::type298 GR, 299 typename enable_if<typename GR::BuildTag, void>::type 268 300 > { 269 301 static const bool value = true; -
lemon/bits/vector_map.h
r314 r617 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 39 39 // \brief Graph map based on the std::vector storage. 40 40 // 41 // The VectorMap template class is graph map structure what42 // automatically updates the map when a key is added to or erased from43 // the map. This map type uses thestd::vector to store the values.41 // The VectorMap template class is graph map structure that automatically 42 // updates the map when a key is added to or erased from the graph. 43 // This map type uses std::vector to store the values. 44 44 // 45 45 // \tparam _Graph The graph this map is attached to. … … 57 57 58 58 // The graph type of the map. 59 typedef _Graph Graph ;59 typedef _Graph GraphType; 60 60 // The item type of the map. 61 61 typedef _Item Item; … … 73 73 // The map type. 74 74 typedef VectorMap Map; 75 // The base class of the map.76 typedef typename Notifier::ObserverBase Parent;77 75 78 76 // The reference type of the map; … … 81 79 typedef typename Container::const_reference ConstReference; 82 80 81 private: 82 83 // The base class of the map. 84 typedef typename Notifier::ObserverBase Parent; 85 86 public: 83 87 84 88 // \brief Constructor to attach the new map into the notifier. … … 86 90 // It constructs a map and attachs it into the notifier. 87 91 // It adds all the items of the graph to the map. 88 VectorMap(const Graph & graph) {92 VectorMap(const GraphType& graph) { 89 93 Parent::attach(graph.notifier(Item())); 90 94 container.resize(Parent::notifier()->maxId() + 1); … … 95 99 // It constructs a map uses a given value to initialize the map. 96 100 // It adds all the items of the graph to the map. 97 VectorMap(const Graph & graph, const Value& value) {101 VectorMap(const GraphType& graph, const Value& value) { 98 102 Parent::attach(graph.notifier(Item())); 99 103 container.resize(Parent::notifier()->maxId() + 1, value); … … 125 129 // \brief Template assign operator. 126 130 // 127 // The given parameter should beconform to the ReadMap131 // The given parameter should conform to the ReadMap 128 132 // concecpt and could be indiced by the current item set of 129 133 // the NodeMap. In this case the value for each item … … 170 174 // \brief Adds a new key to the map. 171 175 // 172 // It adds a new key to the map. It called by the observer notifier176 // It adds a new key to the map. It is called by the observer notifier 173 177 // and it overrides the add() member function of the observer base. 174 178 virtual void add(const Key& key) { … … 181 185 // \brief Adds more new keys to the map. 182 186 // 183 // It adds more new keys to the map. It called by the observer notifier187 // It adds more new keys to the map. It is called by the observer notifier 184 188 // and it overrides the add() member function of the observer base. 185 189 virtual void add(const std::vector<Key>& keys) { … … 196 200 // \brief Erase a key from the map. 197 201 // 198 // Erase a key from the map. It called by the observer notifier202 // Erase a key from the map. It is called by the observer notifier 199 203 // and it overrides the erase() member function of the observer base. 200 204 virtual void erase(const Key& key) { … … 204 208 // \brief Erase more keys from the map. 205 209 // 206 // Erase more keys from the map. Itcalled by the observer notifier210 // It erases more keys from the map. It is called by the observer notifier 207 211 // and it overrides the erase() member function of the observer base. 208 212 virtual void erase(const std::vector<Key>& keys) { … … 212 216 } 213 217 214 // \brief Build esthe map.215 // 216 // It build es the map. Itcalled by the observer notifier218 // \brief Build the map. 219 // 220 // It builds the map. It is called by the observer notifier 217 221 // and it overrides the build() member function of the observer base. 218 222 virtual void build() { … … 224 228 // \brief Clear the map. 225 229 // 226 // It erase all items from the map. Itcalled by the observer notifier230 // It erases all items from the map. It is called by the observer notifier 227 231 // and it overrides the clear() member function of the observer base. 228 232 virtual void clear() { -
lemon/bits/windows.cc
r493 r877 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 97 97 GetSystemTime(&time); 98 98 char buf1[11], buf2[9], buf3[5]; 99 99 if (GetDateFormat(MY_LOCALE, 0, &time, 100 100 ("ddd MMM dd"), buf1, 11) && 101 101 GetTimeFormat(MY_LOCALE, 0, &time, -
lemon/bits/windows.h
r491 r529 17 17 */ 18 18 19 #ifndef LEMON_ WINDOWS_H20 #define LEMON_ WINDOWS_H19 #ifndef LEMON_BITS_WINDOWS_H 20 #define LEMON_BITS_WINDOWS_H 21 21 22 22 #include <string> -
lemon/color.cc
r209 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/color.h
r313 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concept_check.h
r285 r440 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concepts/digraph.h
r263 r877 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 17 17 */ 18 18 19 #ifndef LEMON_CONCEPT _DIGRAPH_H20 #define LEMON_CONCEPT _DIGRAPH_H19 #ifndef LEMON_CONCEPTS_DIGRAPH_H 20 #define LEMON_CONCEPTS_DIGRAPH_H 21 21 22 22 ///\ingroup graph_concepts … … 36 36 /// \brief Class describing the concept of directed graphs. 37 37 /// 38 /// This class describes the \ref concept "concept" of the39 /// immutable directed digraphs.38 /// This class describes the common interface of all directed 39 /// graphs (digraphs). 40 40 /// 41 /// Note that actual digraph implementation like @ref ListDigraph or 42 /// @ref SmartDigraph may have several additional functionality. 41 /// Like all concept classes, it only provides an interface 42 /// without any sensible implementation. So any general algorithm for 43 /// directed graphs should compile with this class, but it will not 44 /// run properly, of course. 45 /// An actual digraph implementation like \ref ListDigraph or 46 /// \ref SmartDigraph may have additional functionality. 43 47 /// 44 /// \sa concept48 /// \sa Graph 45 49 class Digraph { 46 50 private: 47 ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. 48 49 ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. 50 /// 51 Digraph(const Digraph &) {}; 52 ///\brief Assignment of \ref Digraph "Digraph"s to another ones are 53 ///\e not allowed. Use DigraphCopy() instead. 54 55 ///Assignment of \ref Digraph "Digraph"s to another ones are 56 ///\e not allowed. Use DigraphCopy() instead. 57 51 /// Diraphs are \e not copy constructible. Use DigraphCopy instead. 52 Digraph(const Digraph &) {} 53 /// \brief Assignment of a digraph to another one is \e not allowed. 54 /// Use DigraphCopy instead. 58 55 void operator=(const Digraph &) {} 56 59 57 public: 60 ///\e 61 62 /// Defalult constructor. 63 64 /// Defalult constructor. 65 /// 58 /// Default constructor. 66 59 Digraph() { } 67 /// Class for identifying a node of the digraph 60 61 /// The node type of the digraph 68 62 69 63 /// This class identifies a node of the digraph. It also serves 70 64 /// as a base class of the node iterators, 71 /// thus they willconvert to this type.65 /// thus they convert to this type. 72 66 class Node { 73 67 public: 74 68 /// Default constructor 75 69 76 /// @warning The default constructor sets the iterator77 /// to an undefined value.70 /// Default constructor. 71 /// \warning It sets the object to an undefined value. 78 72 Node() { } 79 73 /// Copy constructor. … … 83 77 Node(const Node&) { } 84 78 85 /// Invalid constructor \& conversion.86 87 /// This constructor initializes the iteratorto be invalid.79 /// %Invalid constructor \& conversion. 80 81 /// Initializes the object to be invalid. 88 82 /// \sa Invalid for more details. 89 83 Node(Invalid) { } 90 84 /// Equality operator 91 85 86 /// Equality operator. 87 /// 92 88 /// Two iterators are equal if and only if they point to the 93 /// same object or both are invalid.89 /// same object or both are \c INVALID. 94 90 bool operator==(Node) const { return true; } 95 91 96 92 /// Inequality operator 97 93 98 /// \sa operator==(Node n) 99 /// 94 /// Inequality operator. 100 95 bool operator!=(Node) const { return true; } 101 96 102 97 /// Artificial ordering operator. 103 98 104 /// To allow the use of digraph descriptors as key type in std::map or 105 /// similar associative container we require this. 106 /// 107 /// \note This operator only have to define some strict ordering of 108 /// the items; this order has nothing to do with the iteration 109 /// ordering of the items. 99 /// Artificial ordering operator. 100 /// 101 /// \note This operator only has to define some strict ordering of 102 /// the nodes; this order has nothing to do with the iteration 103 /// ordering of the nodes. 110 104 bool operator<(Node) const { return false; } 111 112 }; 113 114 /// This iterator goes through each node. 115 116 /// This iterator goes through each node. 117 /// Its usage is quite simple, for example you can count the number 118 /// of nodes in digraph \c g of type \c Digraph like this: 105 }; 106 107 /// Iterator class for the nodes. 108 109 /// This iterator goes through each node of the digraph. 110 /// Its usage is quite simple, for example, you can count the number 111 /// of nodes in a digraph \c g of type \c %Digraph like this: 119 112 ///\code 120 113 /// int count=0; … … 125 118 /// Default constructor 126 119 127 /// @warning The default constructor sets the iterator128 /// to an undefined value.120 /// Default constructor. 121 /// \warning It sets the iterator to an undefined value. 129 122 NodeIt() { } 130 123 /// Copy constructor. … … 133 126 /// 134 127 NodeIt(const NodeIt& n) : Node(n) { } 135 /// Invalid constructor \& conversion.136 137 /// Initialize the iterator to be invalid.128 /// %Invalid constructor \& conversion. 129 130 /// Initializes the iterator to be invalid. 138 131 /// \sa Invalid for more details. 139 132 NodeIt(Invalid) { } 140 133 /// Sets the iterator to the first node. 141 134 142 /// Sets the iterator to the first node of \c g. 143 /// 144 NodeIt(const Digraph&) { } 145 /// Node -> NodeIt conversion. 146 147 /// Sets the iterator to the node of \c the digraph pointed by 148 /// the trivial iterator. 149 /// This feature necessitates that each time we 150 /// iterate the arc-set, the iteration order is the same. 135 /// Sets the iterator to the first node of the given digraph. 136 /// 137 explicit NodeIt(const Digraph&) { } 138 /// Sets the iterator to the given node. 139 140 /// Sets the iterator to the given node of the given digraph. 141 /// 151 142 NodeIt(const Digraph&, const Node&) { } 152 143 /// Next node. … … 158 149 159 150 160 /// Class for identifying an arcof the digraph151 /// The arc type of the digraph 161 152 162 153 /// This class identifies an arc of the digraph. It also serves … … 167 158 /// Default constructor 168 159 169 /// @warning The default constructor sets the iterator170 /// to an undefined value.160 /// Default constructor. 161 /// \warning It sets the object to an undefined value. 171 162 Arc() { } 172 163 /// Copy constructor. … … 175 166 /// 176 167