Changes in / [929:d3b041452dd8:930:8e39ccaabf48] in lemon-main
- Files:
-
- 35 added
- 112 edited
Legend:
- Unmodified
- Added
- Removed
-
.hgignore
r563 r866 23 23 lemon/stamp-h2 24 24 doc/Doxyfile 25 doc/references.dox 25 26 cmake/version.cmake 26 27 .dirstamp -
CMakeLists.txt
r927 r930 125 125 ADD_SUBDIRECTORY(lemon) 126 126 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR}) 127 ADD_SUBDIRECTORY(contrib) 127 128 ADD_SUBDIRECTORY(demo) 128 129 ADD_SUBDIRECTORY(tools) -
INSTALL
r568 r824 174 174 175 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
r553 r879 2 2 copyright/license. 3 3 4 Copyright (C) 2003-20 09Egervary Jeno Kombinatorikus Optimalizalasi4 Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi 5 5 Kutatocsoport (Egervary Combinatorial Optimization Research Group, 6 6 EGRES). -
Makefile.am
r752 r793 45 45 include doc/Makefile.am 46 46 include tools/Makefile.am 47 include scripts/Makefile.am 47 48 48 49 DIST_SUBDIRS = demo -
NEWS
r665 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 1 81 2009-05-13 Version 1.1 released 2 82 … … 73 153 ----: Add missing unistd.h include to time_measure.h 74 154 #204: Compilation bug fixed in graph_to_eps.h with VS2005 75 #214,#215: windows.h should never be included by lemonheaders155 #214,#215: windows.h should never be included by LEMON headers 76 156 #230: Build systems check the availability of 'long long' type 77 157 #229: Default implementation of Tolerance<> is used for integer types … … 95 175 2008-10-13 Version 1.0 released 96 176 97 98 99 100 101 102 177 This is the first stable release of LEMON. Compared to the 0.x 178 release series, it features a considerably smaller but more 179 matured set of tools. The API has also completely revised and 180 changed in several places. 181 182 * The major name changes compared to the 0.x series (see the 103 183 Migration Guide in the doc for more details) 104 184 * Graph -> Digraph, UGraph -> Graph 105 185 * Edge -> Arc, UEdge -> Edge 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 186 * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge) 187 * Other improvements 188 * Better documentation 189 * Reviewed and cleaned up codebase 190 * CMake based build system (along with the autotools based one) 191 * Contents of the library (ported from 0.x) 192 * Algorithms 193 * breadth-first search (bfs.h) 194 * depth-first search (dfs.h) 195 * Dijkstra's algorithm (dijkstra.h) 196 * Kruskal's algorithm (kruskal.h) 197 * Data structures 198 * graph data structures (list_graph.h, smart_graph.h) 199 * path data structures (path.h) 200 * binary heap data structure (bin_heap.h) 201 * union-find data structures (unionfind.h) 202 * miscellaneous property maps (maps.h) 203 * two dimensional vector and bounding box (dim2.h) 124 204 * Concepts 125 205 * graph structure concepts (concepts/digraph.h, concepts/graph.h, 126 206 concepts/graph_components.h) 127 128 129 130 131 132 133 134 135 207 * concepts for other structures (concepts/heap.h, concepts/maps.h, 208 concepts/path.h) 209 * Tools 210 * Mersenne twister random number generator (random.h) 211 * tools for measuring cpu and wall clock time (time_measure.h) 212 * tools for counting steps and events (counter.h) 213 * tool for parsing command line arguments (arg_parser.h) 214 * tool for visualizing graphs (graph_to_eps.h) 215 * tools for reading and writing data in LEMON Graph Format 136 216 (lgf_reader.h, lgf_writer.h) 137 217 * tools to handle the anomalies of calculations with 138 218 floating point numbers (tolerance.h) 139 219 * tools to manage RGB colors (color.h) 140 141 142 143 144 220 * Infrastructure 221 * extended assertion handling (assert.h) 222 * exception classes and error handling (error.h) 223 * concept checking (concept_check.h) 224 * commonly used mathematical constants (math.h) -
README
r658 r848 18 18 Copying, distribution and modification conditions and terms. 19 19 20 NEWS 21 22 News and version history. 23 20 24 INSTALL 21 25 … … 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 -
configure.ac
r929 r930 42 42 43 43 AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no]) 44 AC_CHECK_PROG([python_found],[python],[yes],[no]) 44 45 AC_CHECK_PROG([gs_found],[gs],[yes],[no]) 45 46 … … 82 83 fi 83 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"]) 84 100 85 101 dnl Checks for header files. … … 129 145 echo 130 146 echo Build additional tools........ : $enable_tools 147 echo Use valgrind for tests........ : $use_valgrind 131 148 echo 132 149 echo The packace will be installed in -
demo/arg_parser_demo.cc
r440 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). … … 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 -
doc/CMakeLists.txt
r929 r930 18 18 ) 19 19 20 IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)20 IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE) 21 21 FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/) 22 22 SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha) … … 29 29 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps 30 30 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps 31 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps 31 32 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps 32 33 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps … … 35 36 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps 36 37 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps 38 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps 37 39 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps 38 40 COMMAND ${CMAKE_COMMAND} -E remove_directory html 41 COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox 39 42 COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile 40 43 WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR} -
doc/Doxyfile.in
r929 r930 96 96 "@abs_top_srcdir@/lemon/concepts" \ 97 97 "@abs_top_srcdir@/demo" \ 98 "@abs_top_srcdir@/contrib" \ 98 99 "@abs_top_srcdir@/tools" \ 99 100 "@abs_top_srcdir@/test/test_tools.h" \ 100 "@abs_top_builddir@/doc/mainpage.dox" 101 "@abs_top_builddir@/doc/mainpage.dox" \ 102 "@abs_top_builddir@/doc/references.dox" 101 103 INPUT_ENCODING = UTF-8 102 104 FILE_PATTERNS = *.h \ -
doc/Makefile.am
r673 r865 28 28 connected_components.eps \ 29 29 edge_biconnected_components.eps \ 30 matching.eps \ 30 31 node_biconnected_components.eps \ 32 planar.eps \ 31 33 strongly_connected_components.eps 32 34 … … 67 69 fi 68 70 69 html-local: $(DOC_PNG_IMAGES) 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 70 84 if test ${doxygen_found} = yes; then \ 71 85 cd doc; \ -
doc/coding_style.dox
r440 r919 99 99 \subsection pri-loc-var Private member variables 100 100 101 Private member variables should start with underscore 101 Private member variables should start with underscore. 102 102 103 103 \code 104 _start_with_underscore s104 _start_with_underscore 105 105 \endcode 106 106 -
doc/dirs.dox
r440 r925 32 32 documentation. 33 33 */ 34 35 /** 36 \dir contrib 37 \brief Directory for user contributed source codes. 38 39 You can place your own C++ code using LEMON into this directory, which 40 will compile to an executable along with LEMON when you build the 41 library. This is probably the easiest way of compiling short to medium 42 codes, for this does require neither a LEMON installed system-wide nor 43 adding several paths to the compiler. 44 45 Please have a look at <tt>contrib/CMakeLists.txt</tt> for 46 instruction on how to add your own files into the build process. */ 34 47 35 48 /** -
doc/groups.dox
r663 r919 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). … … 227 227 228 228 /** 229 @defgroup matrices Matrices230 @ingroup datas231 \brief Two dimensional data storages implemented in LEMON.232 233 This group contains two dimensional data storages implemented in LEMON.234 */235 236 /**237 229 @defgroup paths Path Structures 238 230 @ingroup datas … … 247 239 any kind of path structure. 248 240 249 \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" 250 263 */ 251 264 … … 260 273 261 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 /** 262 297 @defgroup algs Algorithms 263 298 \brief This group contains the several algorithms … … 274 309 275 310 This group contains the common graph search algorithms, namely 276 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). 311 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) 312 \ref clrs01algorithms. 277 313 */ 278 314 … … 282 318 \brief Algorithms for finding shortest paths. 283 319 284 This group contains the algorithms for finding shortest paths in digraphs. 320 This group contains the algorithms for finding shortest paths in digraphs 321 \ref clrs01algorithms. 285 322 286 323 - \ref Dijkstra algorithm for finding shortest paths from a source node … … 299 336 300 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. 344 */ 345 346 /** 301 347 @defgroup max_flow Maximum Flow Algorithms 302 348 @ingroup algs … … 304 350 305 351 This group contains the algorithms for finding maximum flows and 306 feasible circulations .352 feasible circulations \ref clrs01algorithms, \ref amo93networkflows. 307 353 308 354 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 319 365 320 366 LEMON contains several algorithms for solving maximum flow problems: 321 - \ref EdmondsKarp Edmonds-Karp algorithm. 322 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. 323 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. 324 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. 325 326 In most cases the \ref Preflow "Preflow" algorithm provides the 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 327 377 fastest method for computing a maximum flow. All implementations 328 378 also provide functions to query the minimum cut, which is the dual 329 379 problem of maximum flow. 330 380 331 \ref Circulation is a preflow push-relabel algorithm implemented directly 381 \ref Circulation is a preflow push-relabel algorithm implemented directly 332 382 for finding feasible circulations, which is a somewhat different problem, 333 383 but it is strongly related to maximum flow. … … 342 392 343 393 This group contains the algorithms for finding minimum cost flows and 344 circulations. For more information about this problem and its dual 345 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 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". 346 397 347 398 LEMON contains several algorithms for this problem. 348 399 - \ref NetworkSimplex Primal Network Simplex algorithm with various 349 pivot strategies. 350 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on 351 cost scaling. 352 - \ref CapacityScaling Successive Shortest %Path algorithm with optional 353 capacity scaling. 354 - \ref CancelAndTighten The Cancel and Tighten algorithm. 355 - \ref CycleCanceling Cycle-Canceling algorithms. 356 357 In general NetworkSimplex is the most efficient implementation, 358 but in special cases other algorithms could be faster. 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, \ref NetworkSimplex and \ref CostScaling are the most efficient 410 implementations, but the other two algorithms could be faster in special cases. 359 411 For example, if the total supply and/or capacities are rather small, 360 CapacityScaling is usually the fastest algorithm (without effective scaling).412 \ref CapacityScaling is usually the fastest algorithm (without effective scaling). 361 413 */ 362 414 … … 376 428 377 429 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} 378 \sum_{uv\in A ,u\in X, v\not\in X}cap(uv) \f]430 \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f] 379 431 380 432 LEMON contains several algorithms related to minimum cut problems: … … 392 444 393 445 /** 394 @defgroup graph_properties Connectivity and Other Graph Properties 395 @ingroup algs 396 \brief Algorithms for discovering the graph properties 397 398 This group contains the algorithms for discovering the graph properties 399 like connectivity, bipartiteness, euler property, simplicity etc. 400 401 \image html edge_biconnected_components.png 402 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 403 */ 404 405 /** 406 @defgroup planar Planarity Embedding and Drawing 407 @ingroup algs 408 \brief Algorithms for planarity checking, embedding and drawing 409 410 This group contains the algorithms for planarity checking, 411 embedding and drawing. 412 413 \image html planar.png 414 \image latex planar.eps "Plane graph" width=\textwidth 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 turned out to be by far the 475 most efficient one, though the best known theoretical bound on its running 476 time is exponential. 477 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms 478 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is 479 typically faster due to the applied early termination scheme. 415 480 */ 416 481 … … 450 515 Edmond's blossom shrinking algorithm for calculating maximum weighted 451 516 perfect matching in general graphs. 452 453 \image html bipartite_matching.png 454 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth 455 */ 456 457 /** 458 @defgroup spantree Minimum Spanning Tree Algorithms 459 @ingroup algs 460 \brief Algorithms for finding minimum cost spanning trees and arborescences. 461 462 This group contains the algorithms for finding minimum cost spanning 463 trees and arborescences. 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 Planar 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. 464 564 */ 465 565 … … 471 571 This group contains some algorithms implemented in LEMON 472 572 in order to make it easier to implement complex algorithms. 473 */474 475 /**476 @defgroup approx Approximation Algorithms477 @ingroup algs478 \brief Approximation algorithms.479 480 This group contains the approximation and heuristic algorithms481 implemented in LEMON.482 573 */ 483 574 … … 492 583 493 584 /** 494 @defgroup lp_group L p and MipSolvers585 @defgroup lp_group LP and MIP Solvers 495 586 @ingroup gen_opt_group 496 \brief Lp and Mip solver interfaces for LEMON. 497 498 This group contains Lp and Mip solver interfaces for LEMON. The 499 various LP solvers could be used in the same manner with this 500 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. 501 595 */ 502 596 … … 588 682 589 683 /** 590 @defgroup dimacs_group DIMACS format684 @defgroup dimacs_group DIMACS Format 591 685 @ingroup io_group 592 686 \brief Read and write files in DIMACS format … … 637 731 \brief Skeleton and concept checking classes for graph structures 638 732 639 This group contains the skeletons and concept checking classes of LEMON's640 graph structures and helper classes used to implement these.733 This group contains the skeletons and concept checking classes of 734 graph structures. 641 735 */ 642 736 … … 650 744 651 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. 752 */ 753 754 /** 652 755 \anchor demoprograms 653 756 … … 661 764 */ 662 765 663 /**664 @defgroup tools Standalone Utility Applications665 666 Some utility applications are listed here.667 668 The standard compilation procedure (<tt>./configure;make</tt>) will compile669 them, as well.670 */671 672 766 } -
doc/mainpage.dox.in
r929 r930 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). … … 22 22 \section intro Introduction 23 23 24 \subsection whatis What is LEMON 25 26 LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling 27 and <b>O</b>ptimization in <b>N</b>etworks. 28 It is a C++ template 29 library aimed at combinatorial optimization tasks which 30 often involve in working 31 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. 32 29 33 30 <b> … … 39 36 </b> 40 37 41 \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. 46 47 \section howtoread How to Read the Documentation 42 48 43 49 If you would like to get to know the library, see 44 50 <a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>. 51 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>. 45 55 46 56 If you know what you are looking for, then try to find it under the -
doc/min_cost_flow.dox
r663 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). … … 27 27 minimum total cost from a set of supply nodes to a set of demand nodes 28 28 in a network with capacity constraints (lower and upper bounds) 29 and arc costs .29 and arc costs \ref amo93networkflows. 30 30 31 31 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$, … … 79 79 - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. 80 80 - For all \f$u\in V\f$ nodes: 81 - \f$\pi(u) <=0\f$;81 - \f$\pi(u)\leq 0\f$; 82 82 - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, 83 83 then \f$\pi(u)=0\f$. 84 84 85 85 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc 86 86 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e. … … 120 120 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] 121 121 122 It means that the total demand must be less or equal to the 122 It means that the total demand must be less or equal to the 123 123 total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or 124 124 positive) and all the demands have to be satisfied, but there … … 146 146 - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. 147 147 - For all \f$u\in V\f$ nodes: 148 - \f$\pi(u) >=0\f$;148 - \f$\pi(u)\geq 0\f$; 149 149 - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, 150 150 then \f$\pi(u)=0\f$. -
lemon/Makefile.am
r667 r917 58 58 lemon/arg_parser.h \ 59 59 lemon/assert.h \ 60 lemon/bellman_ford.h \ 60 61 lemon/bfs.h \ 61 62 lemon/bin_heap.h \ 63 lemon/binomial_heap.h \ 64 lemon/bucket_heap.h \ 65 lemon/capacity_scaling.h \ 62 66 lemon/cbc.h \ 63 67 lemon/circulation.h \ … … 66 70 lemon/concept_check.h \ 67 71 lemon/connectivity.h \ 72 lemon/core.h \ 73 lemon/cost_scaling.h \ 68 74 lemon/counter.h \ 69 lemon/core.h \70 75 lemon/cplex.h \ 76 lemon/cycle_canceling.h \ 71 77 lemon/dfs.h \ 78 lemon/dheap.h \ 72 79 lemon/dijkstra.h \ 73 80 lemon/dim2.h \ … … 77 84 lemon/error.h \ 78 85 lemon/euler.h \ 86 lemon/fib_heap.h \ 87 lemon/fractional_matching.h \ 79 88 lemon/full_graph.h \ 80 89 lemon/glpk.h \ … … 82 91 lemon/graph_to_eps.h \ 83 92 lemon/grid_graph.h \ 93 lemon/grosso_locatelli_pullan_mc.h \ 94 lemon/hartmann_orlin_mmc.h \ 95 lemon/howard_mmc.h \ 84 96 lemon/hypercube_graph.h \ 97 lemon/karp_mmc.h \ 85 98 lemon/kruskal.h \ 86 99 lemon/hao_orlin.h \ … … 91 104 lemon/lp_base.h \ 92 105 lemon/lp_skeleton.h \ 93 lemon/list_graph.h \94 106 lemon/maps.h \ 95 107 lemon/matching.h \ 96 108 lemon/math.h \ 97 109 lemon/min_cost_arborescence.h \ 110 lemon/max_cardinality_search.h \ 111 lemon/nagamochi_ibaraki.h \ 98 112 lemon/nauty_reader.h \ 99 113 lemon/network_simplex.h \ 114 lemon/pairing_heap.h \ 100 115 lemon/path.h \ 116 lemon/planarity.h \ 101 117 lemon/preflow.h \ 118 lemon/quad_heap.h \ 119 lemon/radix_heap.h \ 102 120 lemon/radix_sort.h \ 103 121 lemon/random.h \ 104 122 lemon/smart_graph.h \ 105 123 lemon/soplex.h \ 124 lemon/static_graph.h \ 106 125 lemon/suurballe.h \ 107 126 lemon/time_measure.h \ -
lemon/adaptors.h
r656 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). … … 361 361 /// parameter is set to be \c const. 362 362 /// 363 /// This class provides item counting in the same time as the adapted 364 /// digraph structure. 365 /// 363 366 /// \tparam DGR The type of the adapted digraph. 364 367 /// It must conform to the \ref concepts::Digraph "Digraph" concept. … … 419 422 Parent::initialize(digraph); 420 423 _node_filter = &node_filter; 421 _arc_filter = &arc_filter; 424 _arc_filter = &arc_filter; 422 425 } 423 426 … … 506 509 507 510 template <typename V> 508 class NodeMap 509 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 510 511 class NodeMap 512 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 513 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> { 511 514 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 512 515 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent; 513 516 514 517 public: … … 533 536 534 537 template <typename V> 535 class ArcMap 538 class ArcMap 536 539 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 537 540 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> { 538 541 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 539 542 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent; … … 580 583 Parent::initialize(digraph); 581 584 _node_filter = &node_filter; 582 _arc_filter = &arc_filter; 585 _arc_filter = &arc_filter; 583 586 } 584 587 … … 649 652 650 653 template <typename V> 651 class NodeMap 654 class NodeMap 652 655 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 653 656 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> { 654 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 657 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 655 658 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent; 656 659 … … 676 679 677 680 template <typename V> 678 class ArcMap 681 class ArcMap 679 682 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 680 683 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> { … … 719 722 /// by adding or removing nodes or arcs, unless the \c GR template 720 723 /// parameter is set to be \c const. 724 /// 725 /// This class provides only linear time counting for nodes and arcs. 721 726 /// 722 727 /// \tparam DGR The type of the adapted digraph. … … 1017 1022 1018 1023 template <typename V> 1019 class NodeMap 1024 class NodeMap 1020 1025 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1021 1026 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> { 1022 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1027 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1023 1028 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent; 1024 1029 … … 1044 1049 1045 1050 template <typename V> 1046 class ArcMap 1051 class ArcMap 1047 1052 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1048 1053 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> { 1049 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1054 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1050 1055 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent; 1051 1056 … … 1071 1076 1072 1077 template <typename V> 1073 class EdgeMap 1078 class EdgeMap 1074 1079 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1075 1080 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> { 1076 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1081 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1077 1082 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent; 1078 1083 … … 1113 1118 NF* _node_filter; 1114 1119 EF* _edge_filter; 1115 SubGraphBase() 1116 1120 SubGraphBase() 1121 : Parent(), _node_filter(0), _edge_filter(0) { } 1117 1122 1118 1123 void initialize(GR& graph, NF& node_filter, EF& edge_filter) { … … 1215 1220 1216 1221 template <typename V> 1217 class NodeMap 1222 class NodeMap 1218 1223 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1219 1224 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> { 1220 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1225 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1221 1226 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent; 1222 1227 … … 1242 1247 1243 1248 template <typename V> 1244 class ArcMap 1249 class ArcMap 1245 1250 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1246 1251 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> { 1247 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1252 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1248 1253 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent; 1249 1254 … … 1269 1274 1270 1275 template <typename V> 1271 class EdgeMap 1276 class EdgeMap 1272 1277 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1273 1278 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> { 1274 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1275 1279 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1280 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent; 1276 1281 1277 1282 public: … … 1314 1319 /// by adding or removing nodes or edges, unless the \c GR template 1315 1320 /// parameter is set to be \c const. 1321 /// 1322 /// This class provides only linear time counting for nodes, edges and arcs. 1316 1323 /// 1317 1324 /// \tparam GR The type of the adapted graph. … … 1471 1478 /// by adding or removing nodes or arcs/edges, unless the \c GR template 1472 1479 /// parameter is set to be \c const. 1480 /// 1481 /// This class provides only linear time item counting. 1473 1482 /// 1474 1483 /// \tparam GR The type of the adapted digraph or graph. … … 1496 1505 #endif 1497 1506 typedef DigraphAdaptorExtender< 1498 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 1507 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 1499 1508 true> > Parent; 1500 1509 … … 1517 1526 /// Creates a subgraph for the given digraph or graph with the 1518 1527 /// given node filter map. 1519 FilterNodes(GR& graph, NF& node_filter) 1528 FilterNodes(GR& graph, NF& node_filter) 1520 1529 : Parent(), const_true_map() 1521 1530 { … … 1555 1564 typename enable_if<UndirectedTagIndicator<GR> >::type> : 1556 1565 public GraphAdaptorExtender< 1557 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 1566 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 1558 1567 true> > { 1559 1568 1560 1569 typedef GraphAdaptorExtender< 1561 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 1570 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 1562 1571 true> > Parent; 1563 1572 … … 1619 1628 /// by adding or removing nodes or arcs, unless the \c GR template 1620 1629 /// parameter is set to be \c const. 1630 /// 1631 /// This class provides only linear time counting for nodes and arcs. 1621 1632 /// 1622 1633 /// \tparam DGR The type of the adapted digraph. … … 1643 1654 #endif 1644 1655 typedef DigraphAdaptorExtender< 1645 SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 1656 SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 1646 1657 AF, false> > Parent; 1647 1658 … … 1729 1740 /// by adding or removing nodes or edges, unless the \c GR template 1730 1741 /// parameter is set to be \c const. 1742 /// 1743 /// This class provides only linear time counting for nodes, edges and arcs. 1731 1744 /// 1732 1745 /// \tparam GR The type of the adapted graph. … … 1749 1762 class FilterEdges : 1750 1763 public GraphAdaptorExtender< 1751 SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 1764 SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 1752 1765 EF, false> > { 1753 1766 #endif 1754 1767 typedef GraphAdaptorExtender< 1755 SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 1768 SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 1756 1769 EF, false> > Parent; 1757 1770 … … 1778 1791 /// Creates a subgraph for the given graph with the given edge 1779 1792 /// filter map. 1780 FilterEdges(GR& graph, EF& edge_filter) 1793 FilterEdges(GR& graph, EF& edge_filter) 1781 1794 : Parent(), const_true_map() { 1782 1795 Parent::initialize(graph, const_true_map, edge_filter); … … 1846 1859 bool _forward; 1847 1860 1848 Arc(const Edge& edge, bool forward) 1861 Arc(const Edge& edge, bool forward) 1849 1862 : _edge(edge), _forward(forward) {} 1850 1863 … … 2086 2099 2087 2100 ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value) 2088 : _forward(*adaptor._digraph, value), 2101 : _forward(*adaptor._digraph, value), 2089 2102 _backward(*adaptor._digraph, value) {} 2090 2103 … … 2204 2217 typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier; 2205 2218 EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); } 2206 2219 2207 2220 typedef EdgeNotifier ArcNotifier; 2208 2221 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); } … … 2232 2245 /// by adding or removing nodes or edges, unless the \c GR template 2233 2246 /// parameter is set to be \c const. 2247 /// 2248 /// This class provides item counting in the same time as the adapted 2249 /// digraph structure. 2234 2250 /// 2235 2251 /// \tparam DGR The type of the adapted digraph. … … 2535 2551 /// by adding or removing nodes or arcs, unless the \c GR template 2536 2552 /// parameter is set to be \c const. 2553 /// 2554 /// This class provides item counting in the same time as the adapted 2555 /// graph structure. 2537 2556 /// 2538 2557 /// \tparam GR The type of the adapted graph. … … 2679 2698 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. 2680 2699 /// 2700 /// This class provides only linear time counting for nodes and arcs. 2701 /// 2681 2702 /// \tparam DGR The type of the adapted digraph. 2682 2703 /// It must conform to the \ref concepts::Digraph "Digraph" concept. … … 2708 2729 typename FM = CM, 2709 2730 typename TL = Tolerance<typename CM::Value> > 2710 class ResidualDigraph 2731 class ResidualDigraph 2711 2732 : public SubDigraph< 2712 2733 Undirector<const DGR>, … … 2765 2786 ResidualDigraph(const DGR& digraph, const CM& capacity, 2766 2787 FM& flow, const TL& tolerance = Tolerance()) 2767 : Parent(), _capacity(&capacity), _flow(&flow), 2788 : Parent(), _capacity(&capacity), _flow(&flow), 2768 2789 _graph(digraph), _node_filter(), 2769 2790 _forward_filter(capacity, flow, tolerance), … … 2847 2868 2848 2869 /// Constructor 2849 ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 2870 ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 2850 2871 : _adaptor(&adaptor) {} 2851 2872 … … 3326 3347 /// in the adaptor. 3327 3348 /// 3349 /// This class provides item counting in the same time as the adapted 3350 /// digraph structure. 3351 /// 3328 3352 /// \tparam DGR The type of the adapted digraph. 3329 3353 /// It must conform to the \ref concepts::Digraph "Digraph" concept. … … 3424 3448 /// to get a node map of the split digraph. 3425 3449 /// Its value type is inherited from the first node map type (\c IN). 3426 /// \tparam IN The type of the node map for the in-nodes. 3450 /// \tparam IN The type of the node map for the in-nodes. 3427 3451 /// \tparam OUT The type of the node map for the out-nodes. 3428 3452 template <typename IN, typename OUT> -
lemon/arg_parser.cc
r440 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). … … 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
r440 r879 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). … … 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/bfs.h
r503 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). … … 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 52 ///Instantiates a \c PredMap. … … 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 68 ///Instantiates a \c ProcessedMap. … … 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 88 ///Instantiates a \c ReachedMap. … … 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 103 ///Instantiates a \c DistMap. … … 121 123 ///\tparam GR The type of the digraph the algorithm runs on. 122 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. 123 130 #ifdef DOXYGEN 124 131 template <typename GR, … … 226 233 ///\ref named-templ-param "Named parameter" for setting 227 234 ///\c PredMap type. 228 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.235 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 229 236 template <class T> 230 237 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 246 253 ///\ref named-templ-param "Named parameter" for setting 247 254 ///\c DistMap type. 248 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.255 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 249 256 template <class T> 250 257 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 266 273 ///\ref named-templ-param "Named parameter" for setting 267 274 ///\c ReachedMap type. 268 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 275 ///It must conform to 276 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 269 277 template <class T> 270 278 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 286 294 ///\ref named-templ-param "Named parameter" for setting 287 295 ///\c ProcessedMap type. 288 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.296 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 289 297 template <class T> 290 298 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 414 422 ///The simplest way to execute the BFS algorithm is to use one of the 415 423 ///member functions called \ref run(Node) "run()".\n 416 ///If you need more control on the execution, firstyou have to call417 ///\ref init() , then you can add several source nodes with424 ///If you need better control on the execution, you have to call 425 ///\ref init() first, then you can add several source nodes with 418 426 ///\ref addSource(). Finally the actual path computation can be 419 427 ///performed with one of the \ref start() functions. … … 701 709 ///Runs the algorithm to visit all nodes in the digraph. 702 710 703 ///This method runs the %BFS algorithm in order to 704 ///compute the shortest path to each node. 705 /// 706 ///The algorithm computes 707 ///- the shortest path tree (forest), 708 ///- 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. 709 713 /// 710 714 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 738 742 ///@{ 739 743 740 ///The shortest path to anode.741 742 ///Returns the shortest path to a node.744 ///The shortest path to the given node. 745 746 ///Returns the shortest path to the given node from the root(s). 743 747 /// 744 748 ///\warning \c t should be reached from the root(s). … … 748 752 Path path(Node t) const { return Path(*G, *_pred, t); } 749 753 750 ///The distance of anode from the root(s).751 752 ///Returns the distance of anode from the root(s).754 ///The distance of the given node from the root(s). 755 756 ///Returns the distance of the given node from the root(s). 753 757 /// 754 758 ///\warning If node \c v is not reached from the root(s), then … … 759 763 int dist(Node v) const { return (*_dist)[v]; } 760 764 761 ///Returns the 'previous arc' of the shortest path tree for a node. 762 765 ///\brief Returns the 'previous arc' of the shortest path tree for 766 ///the given node. 767 /// 763 768 ///This function returns the 'previous arc' of the shortest path 764 769 ///tree for the node \c v, i.e. it returns the last arc of a … … 767 772 /// 768 773 ///The shortest path tree used here is equal to the shortest path 769 ///tree used in \ref predNode() .774 ///tree used in \ref predNode() and \ref predMap(). 770 775 /// 771 776 ///\pre Either \ref run(Node) "run()" or \ref init() … … 773 778 Arc predArc(Node v) const { return (*_pred)[v];} 774 779 775 ///Returns the 'previous node' of the shortest path tree for a node. 776 780 ///\brief Returns the 'previous node' of the shortest path tree for 781 ///the given node. 782 /// 777 783 ///This function returns the 'previous node' of the shortest path 778 784 ///tree for the node \c v, i.e. it returns the last but one node 779 /// froma shortest path from a root to \c v. It is \c INVALID785 ///of a shortest path from a root to \c v. It is \c INVALID 780 786 ///if \c v is not reached from the root(s) or if \c v is a root. 781 787 /// 782 788 ///The shortest path tree used here is equal to the shortest path 783 ///tree used in \ref predArc() .789 ///tree used in \ref predArc() and \ref predMap(). 784 790 /// 785 791 ///\pre Either \ref run(Node) "run()" or \ref init() … … 802 808 /// 803 809 ///Returns a const reference to the node map that stores the predecessor 804 ///arcs, which form the shortest path tree .810 ///arcs, which form the shortest path tree (forest). 805 811 /// 806 812 ///\pre Either \ref run(Node) "run()" or \ref init() … … 808 814 const PredMap &predMap() const { return *_pred;} 809 815 810 ///Checks if anode is reached from the root(s).816 ///Checks if the given node is reached from the root(s). 811 817 812 818 ///Returns \c true if \c v is reached from the root(s). … … 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), … … 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) … … 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 … … 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 TR T raits class to set various datatypes used by the1306 /// algorithm. The default traits class is1307 /// \ref BfsVisitDefaultTraits"BfsVisitDefaultTraits<GR>".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 1316 template <typename GR, typename VS, typename TR> … … 1426 1431 /// The simplest way to execute the BFS algorithm is to use one of the 1427 1432 /// member functions called \ref run(Node) "run()".\n 1428 /// If you need more control on the execution, firstyou have to call1429 /// \ref init() , then you can add several source nodes with1433 /// If you need better control on the execution, you have to call 1434 /// \ref init() first, then you can add several source nodes with 1430 1435 /// \ref addSource(). Finally the actual path computation can be 1431 1436 /// performed with one of the \ref start() functions. … … 1699 1704 /// \brief Runs the algorithm to visit all nodes in the digraph. 1700 1705 /// 1701 /// This method runs the %BFS algorithm in order to 1702 /// compute the shortest path to each node. 1703 /// 1704 /// The algorithm computes 1705 /// - the shortest path tree (forest), 1706 /// - 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. 1707 1708 /// 1708 1709 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 1736 1737 ///@{ 1737 1738 1738 /// \brief Checks if anode is reached from the root(s).1739 /// \brief Checks if the given node is reached from the root(s). 1739 1740 /// 1740 1741 /// Returns \c true if \c v is reached from the root(s). -
lemon/bin_heap.h
r584 r711 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. 37 /// 38 ///A \e heap is a data structure for storing items with specified values 39 ///called \e priorities in such a way that finding the item with minimum 40 ///priority is efficient. \c Comp specifies the ordering of the priorities. 41 ///In a heap one can change the priority of an item, add or erase an 42 ///item, etc. 36 /// This class implements the \e binary \e heap data structure. 37 /// It fully conforms to the \ref concepts::Heap "heap concept". 43 38 /// 44 ///\tparam PR Type of the priority of the items. 45 ///\tparam IM A read and writable item map with int values, used internally 46 ///to handle the cross references. 47 ///\tparam Comp A functor class for the ordering of the priorities. 48 ///The default is \c std::less<PR>. 49 /// 50 ///\sa FibHeap 51 ///\sa Dijkstra 52 template <typename PR, typename IM, typename Comp = std::less<PR> > 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 53 49 class BinHeap { 54 55 50 public: 56 ///\e 51 52 /// Type of the item-int map. 57 53 typedef IM ItemIntMap; 58 /// \e54 /// Type of the priorities. 59 55 typedef PR Prio; 60 /// \e56 /// Type of the items stored in the heap. 61 57 typedef typename ItemIntMap::Key Item; 62 /// \e58 /// Type of the item-priority pairs. 63 59 typedef std::pair<Item,Prio> Pair; 64 /// \e65 typedef C ompCompare;66 67 /// \brief Type to represent the items states.68 /// 69 /// Each Item element have a state associated to it. It maybe "in heap",70 /// "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 71 67 /// heap's point of view, but may be useful to the user. 72 68 /// … … 85 81 86 82 public: 87 /// \brief The constructor. 88 /// 89 /// The constructor. 90 /// \param map should be given to the constructor, since it is used 91 /// internally to handle the cross references. The value of the map 92 /// must be \c PRE_HEAP (<tt>-1</tt>) for every item. 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. 93 90 explicit BinHeap(ItemIntMap &map) : _iim(map) {} 94 91 95 /// \brief The constructor. 96 /// 97 /// The constructor. 98 /// \param map should be given to the constructor, since it is used 99 /// internally to handle the cross references. The value of the map 100 /// should be PRE_HEAP (-1) for each element. 101 /// 102 /// \param comp The comparator function object. 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. 103 99 BinHeap(ItemIntMap &map, const Compare &comp) 104 100 : _iim(map), _comp(comp) {} 105 101 106 102 107 /// The number of items stored in the heap.108 /// 109 /// \brief Returns the number of items stored in the heap.103 /// \brief The number of items stored in the heap. 104 /// 105 /// This function returns the number of items stored in the heap. 110 106 int size() const { return _data.size(); } 111 107 112 /// \brief Check s if the heap stores no items.113 /// 114 /// Returns \c true if and only if the heap stores no items.108 /// \brief Check if the heap is empty. 109 /// 110 /// This function returns \c true if the heap is empty. 115 111 bool empty() const { return _data.empty(); } 116 112 117 /// \brief Make empty this heap. 118 /// 119 /// Make empty this heap. It does not change the cross reference map. 120 /// If you want to reuse what is not surely empty you should first clear 121 /// the heap and after that you should set the cross reference map for 122 /// each item to \c PRE_HEAP. 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. 123 120 void clear() { 124 121 _data.clear(); … … 128 125 static int parent(int i) { return (i-1)/2; } 129 126 130 static int second _child(int i) { return 2*i+2; }127 static int secondChild(int i) { return 2*i+2; } 131 128 bool less(const Pair &p1, const Pair &p2) const { 132 129 return _comp(p1.second, p2.second); 133 130 } 134 131 135 int bubble _up(int hole, Pair p) {132 int bubbleUp(int hole, Pair p) { 136 133 int par = parent(hole); 137 134 while( hole>0 && less(p,_data[par]) ) { … … 144 141 } 145 142 146 int bubble _down(int hole, Pair p, int length) {147 int child = second _child(hole);143 int bubbleDown(int hole, Pair p, int length) { 144 int child = secondChild(hole); 148 145 while(child < length) { 149 146 if( less(_data[child-1], _data[child]) ) { … … 154 151 move(_data[child], hole); 155 152 hole = child; 156 child = second _child(hole);153 child = secondChild(hole); 157 154 } 158 155 child--; … … 172 169 173 170 public: 171 174 172 /// \brief Insert a pair of item and priority into the heap. 175 173 /// 176 /// 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. 177 176 /// \param p The pair to insert. 177 /// \pre \c p.first must not be stored in the heap. 178 178 void push(const Pair &p) { 179 179 int n = _data.size(); 180 180 _data.resize(n+1); 181 bubble_up(n, p); 182 } 183 184 /// \brief Insert an item into the heap with the given heap. 185 /// 186 /// Adds \c i to the heap with priority \c p. 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. 187 188 /// \param i The item to insert. 188 189 /// \param p The priority of the item. 190 /// \pre \e i must not be stored in the heap. 189 191 void push(const Item &i, const Prio &p) { push(Pair(i,p)); } 190 192 191 /// \brief Returns the item with minimum priority relative to \c Compare. 192 /// 193 /// This method returns the item with minimum priority relative to \c 194 /// Compare. 195 /// \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. 196 197 Item top() const { 197 198 return _data[0].first; 198 199 } 199 200 200 /// \brief Returns the minimum priority relative to \c Compare.201 /// 202 /// It returns the minimum priority relative to \c Compare.203 /// \pre The heap must be non empty.201 /// \brief The minimum priority. 202 /// 203 /// This function returns the minimum priority. 204 /// \pre The heap must be non-empty. 204 205 Prio prio() const { 205 206 return _data[0].second; 206 207 } 207 208 208 /// \brief Deletes the item with minimum priority relative to \c Compare. 209 /// 210 /// This method deletes the item with minimum priority relative to \c 211 /// Compare from the heap. 209 /// \brief Remove the item having minimum priority. 210 /// 211 /// This function removes the item having minimum priority. 212 212 /// \pre The heap must be non-empty. 213 213 void pop() { … … 215 215 _iim.set(_data[0].first, POST_HEAP); 216 216 if (n > 0) { 217 bubble _down(0, _data[n], n);217 bubbleDown(0, _data[n], n); 218 218 } 219 219 _data.pop_back(); 220 220 } 221 221 222 /// \brief Deletes \c i from the heap. 223 /// 224 /// This method deletes item \c i from the heap. 225 /// \param i The item to erase. 226 /// \pre The item should be in the heap. 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. 227 228 void erase(const Item &i) { 228 229 int h = _iim[i]; … … 230 231 _iim.set(_data[h].first, POST_HEAP); 231 232 if( h < n ) { 232 if ( bubble _up(h, _data[n]) == h) {233 bubble _down(h, _data[n], n);233 if ( bubbleUp(h, _data[n]) == h) { 234 bubbleDown(h, _data[n], n); 234 235 } 235 236 } … … 237 238 } 238 239 239 240 /// \brief Returns the priority of \c i. 241 /// 242 /// This function returns the priority of item \c i. 243 /// \param i The item. 244 /// \pre \c i must be in the heap. 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. 245 245 Prio operator[](const Item &i) const { 246 246 int idx = _iim[i]; … … 248 248 } 249 249 250 /// \brief \c i gets to the heap with priority \c p independently 251 /// if \c i was already there. 252 /// 253 /// This method calls \ref push(\c i, \c p) if \c i is not stored 254 /// in the heap and sets the priority of \c i to \c p otherwise. 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. 255 256 /// \param i The item. 256 257 /// \param p The priority. … … 261 262 } 262 263 else if( _comp(p, _data[idx].second) ) { 263 bubble _up(idx, Pair(i,p));264 bubbleUp(idx, Pair(i,p)); 264 265 } 265 266 else { 266 bubble _down(idx, Pair(i,p), _data.size());267 } 268 } 269 270 /// \brief Decrease s the priority of \c i to \c p.271 /// 272 /// This method decreases the priority of item \c i to \c p.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. 273 274 /// \param i The item. 274 275 /// \param p The priority. 275 /// \pre \c i must be stored in the heap with priority at least \c 276 /// p relative to \c Compare. 276 /// \pre \e i must be stored in the heap with priority at least \e p. 277 277 void decrease(const Item &i, const Prio &p) { 278 278 int idx = _iim[i]; 279 bubble _up(idx, Pair(i,p));280 } 281 282 /// \brief Increase s the priority of \c i to \c p.283 /// 284 /// This method sets the priority of item \c i to \c p.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. 285 285 /// \param i The item. 286 286 /// \param p The priority. 287 /// \pre \c i must be stored in the heap with priority at most \c 288 /// p relative to \c Compare. 287 /// \pre \e i must be stored in the heap with priority at most \e p. 289 288 void increase(const Item &i, const Prio &p) { 290 289 int idx = _iim[i]; 291 bubble _down(idx, Pair(i,p), _data.size());292 } 293 294 /// \brief Return s if \c item is in, has already been in, or has295 /// never been in the heap.296 /// 297 /// This method returns PRE_HEAP if \c item has never been in the298 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP299 /// otherwise. In the latter case it is possible that \c item will300 /// get backto the heap again.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. 301 300 /// \param i The item. 302 301 State state(const Item &i) const { … … 307 306 } 308 307 309 /// \brief Set s the state of the \citem in the heap.310 /// 311 /// Sets the state of the \c item in the heap. It can be used to312 /// manually clear the heap when it is important to achive the313 /// 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. 314 313 /// \param i The item. 315 314 /// \param st The state. It should not be \c IN_HEAP. … … 328 327 } 329 328 330 /// \brief Replaces an item in the heap. 331 /// 332 /// The \c i item is replaced with \c j item. The \c i item should 333 /// be in the heap, while the \c j should be out of the heap. The 334 /// \c i item will out of the heap and \c j will be in the heap 335 /// 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. 336 336 void replace(const Item& i, const Item& j) { 337 337 int idx = _iim[i]; -
lemon/bits/array_map.h
r617 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). … … 71 71 72 72 private: 73 73 74 74 // The MapBase of the Map which imlements the core regisitry function. 75 75 typedef typename Notifier::ObserverBase Parent; -
lemon/bits/default_map.h
r627 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). … … 158 158 public: 159 159 typedef DefaultMap<_Graph, _Item, _Value> Map; 160 160 161 161 typedef typename Parent::GraphType GraphType; 162 162 typedef typename Parent::Value Value; -
lemon/bits/edge_set_extender.h
r617 r884 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 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). … … 64 64 Node oppositeNode(const Node &n, const Arc &e) const { 65 65 if (n == Parent::source(e)) 66 66 return Parent::target(e); 67 67 else if(n==Parent::target(e)) 68 68 return Parent::source(e); 69 69 else 70 70 return INVALID; 71 71 } 72 72 … … 92 92 // Iterable extensions 93 93 94 class NodeIt : public Node { 94 class NodeIt : public Node { 95 95 const Digraph* digraph; 96 96 public: … … 101 101 102 102 explicit NodeIt(const Digraph& _graph) : digraph(&_graph) { 103 104 } 105 106 NodeIt(const Digraph& _graph, const Node& node) 107 108 109 NodeIt& operator++() { 110 111 return *this; 112 } 113 114 }; 115 116 117 class ArcIt : public Arc { 103 _graph.first(static_cast<Node&>(*this)); 104 } 105 106 NodeIt(const Digraph& _graph, const Node& node) 107 : Node(node), digraph(&_graph) {} 108 109 NodeIt& operator++() { 110 digraph->next(*this); 111 return *this; 112 } 113 114 }; 115 116 117 class ArcIt : public Arc { 118 118 const Digraph* digraph; 119 119 public: … … 124 124 125 125 explicit ArcIt(const Digraph& _graph) : digraph(&_graph) { 126 127 } 128 129 ArcIt(const Digraph& _graph, const Arc& e) : 130 131 132 ArcIt& operator++() { 133 134 return *this; 135 } 136 137 }; 138 139 140 class OutArcIt : public Arc { 126 _graph.first(static_cast<Arc&>(*this)); 127 } 128 129 ArcIt(const Digraph& _graph, const Arc& e) : 130 Arc(e), digraph(&_graph) { } 131 132 ArcIt& operator++() { 133 digraph->next(*this); 134 return *this; 135 } 136 137 }; 138 139 140 class OutArcIt : public Arc { 141 141 const Digraph* digraph; 142 142 public: … … 146 146 OutArcIt(Invalid i) : Arc(i) { } 147 147 148 OutArcIt(const Digraph& _graph, const Node& node) 149 150 151 } 152 153 OutArcIt(const Digraph& _graph, const Arc& arc) 154 155 156 OutArcIt& operator++() { 157 158 return *this; 159 } 160 161 }; 162 163 164 class InArcIt : public Arc { 148 OutArcIt(const Digraph& _graph, const Node& node) 149 : digraph(&_graph) { 150 _graph.firstOut(*this, node); 151 } 152 153 OutArcIt(const Digraph& _graph, const Arc& arc) 154 : Arc(arc), digraph(&_graph) {} 155 156 OutArcIt& operator++() { 157 digraph->nextOut(*this); 158 return *this; 159 } 160 161 }; 162 163 164 class InArcIt : public Arc { 165 165 const Digraph* digraph; 166 166 public: … … 170 170 InArcIt(Invalid i) : Arc(i) { } 171 171 172 InArcIt(const Digraph& _graph, const Node& node) 173 174 175 } 176 177 InArcIt(const Digraph& _graph, const Arc& arc) : 178 179 180 InArcIt& operator++() { 181 182 return *this; 172 InArcIt(const Digraph& _graph, const Node& node) 173 : digraph(&_graph) { 174 _graph.firstIn(*this, node); 175 } 176 177 InArcIt(const Digraph& _graph, const Arc& arc) : 178 Arc(arc), digraph(&_graph) {} 179 180 InArcIt& operator++() { 181 digraph->nextIn(*this); 182 return *this; 183 183 } 184 184 … … 216 216 217 217 // Mappable extension 218 218 219 219 template <typename _Value> 220 class ArcMap 220 class ArcMap 221 221 : public MapExtender<DefaultMap<Digraph, Arc, _Value> > { 222 222 typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent; 223 223 224 224 public: 225 explicit ArcMap(const Digraph& _g) 226 227 ArcMap(const Digraph& _g, const _Value& _v) 228 225 explicit ArcMap(const Digraph& _g) 226 : Parent(_g) {} 227 ArcMap(const Digraph& _g, const _Value& _v) 228 : Parent(_g, _v) {} 229 229 230 230 ArcMap& operator=(const ArcMap& cmap) { 231 231 return operator=<ArcMap>(cmap); 232 232 } 233 233 … … 235 235 ArcMap& operator=(const CMap& cmap) { 236 236 Parent::operator=(cmap); 237 237 return *this; 238 238 } 239 239 … … 248 248 return arc; 249 249 } 250 250 251 251 void clear() { 252 252 notifier(Arc()).clear(); … … 281 281 typedef EdgeSetExtender Graph; 282 282 283 typedef True UndirectedTag; 284 283 285 typedef typename Parent::Node Node; 284 286 typedef typename Parent::Arc Arc; … … 311 313 Node oppositeNode(const Node &n, const Edge &e) const { 312 314 if( n == Parent::u(e)) 313 315 return Parent::v(e); 314 316 else if( n == Parent::v(e)) 315 317 return Parent::u(e); 316 318 else 317 319 return INVALID; 318 320 } 319 321 … … 339 341 340 342 using Parent::notifier; 341 343 342 344 ArcNotifier& notifier(Arc) const { 343 345 return arc_notifier; … … 349 351 350 352 351 class NodeIt : public Node { 353 class NodeIt : public Node { 352 354 const Graph* graph; 353 355 public: … … 358 360 359 361 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 360 361 } 362 363 NodeIt(const Graph& _graph, const Node& node) 364 365 366 NodeIt& operator++() { 367 368 return *this; 369 } 370 371 }; 372 373 374 class ArcIt : public Arc { 362 _graph.first(static_cast<Node&>(*this)); 363 } 364 365 NodeIt(const Graph& _graph, const Node& node) 366 : Node(node), graph(&_graph) {} 367 368 NodeIt& operator++() { 369 graph->next(*this); 370 return *this; 371 } 372 373 }; 374 375 376 class ArcIt : public Arc { 375 377 const Graph* graph; 376 378 public: … … 381 383 382 384 explicit ArcIt(const Graph& _graph) : graph(&_graph) { 383 384 } 385 386 ArcIt(const Graph& _graph, const Arc& e) : 387 388 389 ArcIt& operator++() { 390 391 return *this; 392 } 393 394 }; 395 396 397 class OutArcIt : public Arc { 385 _graph.first(static_cast<Arc&>(*this)); 386 } 387 388 ArcIt(const Graph& _graph, const Arc& e) : 389 Arc(e), graph(&_graph) { } 390 391 ArcIt& operator++() { 392 graph->next(*this); 393 return *this; 394 } 395 396 }; 397 398 399 class OutArcIt : public Arc { 398 400 const Graph* graph; 399 401 public: … … 403 405 OutArcIt(Invalid i) : Arc(i) { } 404 406 405 OutArcIt(const Graph& _graph, const Node& node) 406 407 408 } 409 410 OutArcIt(const Graph& _graph, const Arc& arc) 411 412 413 OutArcIt& operator++() { 414 415 return *this; 416 } 417 418 }; 419 420 421 class InArcIt : public Arc { 407 OutArcIt(const Graph& _graph, const Node& node) 408 : graph(&_graph) { 409 _graph.firstOut(*this, node); 410 } 411 412 OutArcIt(const Graph& _graph, const Arc& arc) 413 : Arc(arc), graph(&_graph) {} 414 415 OutArcIt& operator++() { 416 graph->nextOut(*this); 417 return *this; 418 } 419 420 }; 421 422 423 class InArcIt : public Arc { 422 424 const Graph* graph; 423 425 public: … … 427 429 InArcIt(Invalid i) : Arc(i) { } 428 430 429 InArcIt(const Graph& _graph, const Node& node) 430 431 432 } 433 434 InArcIt(const Graph& _graph, const Arc& arc) : 435 436 437 InArcIt& operator++() { 438 439 return *this; 440 } 441 442 }; 443 444 445 class EdgeIt : public Parent::Edge { 431 InArcIt(const Graph& _graph, const Node& node) 432 : graph(&_graph) { 433 _graph.firstIn(*this, node); 434 } 435 436 InArcIt(const Graph& _graph, const Arc& arc) : 437 Arc(arc), graph(&_graph) {} 438 439 InArcIt& operator++() { 440 graph->nextIn(*this); 441 return *this; 442 } 443 444 }; 445 446 447 class EdgeIt : public Parent::Edge { 446 448 const Graph* graph; 447 449 public: … … 452 454 453 455 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 454 455 } 456 457 EdgeIt(const Graph& _graph, const Edge& e) : 458 459 460 EdgeIt& operator++() { 461 462 return *this; 456 _graph.first(static_cast<Edge&>(*this)); 457 } 458 459 EdgeIt(const Graph& _graph, const Edge& e) : 460 Edge(e), graph(&_graph) { } 461 462 EdgeIt& operator++() { 463 graph->next(*this); 464 return *this; 463 465 } 464 466 … … 476 478 477 479 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { 478 480 _graph.firstInc(*this, direction, n); 479 481 } 480 482 481 483 IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n) 482 483 484 : graph(&_graph), Edge(ue) { 485 direction = (_graph.source(ue) == n); 484 486 } 485 487 486 488 IncEdgeIt& operator++() { 487 488 return *this; 489 graph->nextInc(*this, direction); 490 return *this; 489 491 } 490 492 }; … … 533 535 534 536 template <typename _Value> 535 class ArcMap 537 class ArcMap 536 538 : public MapExtender<DefaultMap<Graph, Arc, _Value> > { 537 539 typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent; 538 540 539 541 public: 540 ArcMap(const Graph& _g)541 542 ArcMap(const Graph& _g, const _Value& _v) 543 542 explicit ArcMap(const Graph& _g) 543 : Parent(_g) {} 544 ArcMap(const Graph& _g, const _Value& _v) 545 : Parent(_g, _v) {} 544 546 545 547 ArcMap& operator=(const ArcMap& cmap) { 546 548 return operator=<ArcMap>(cmap); 547 549 } 548 550 … … 550 552 ArcMap& operator=(const CMap& cmap) { 551 553 Parent::operator=(cmap); 552 554 return *this; 553 555 } 554 556 … … 557 559 558 560 template <typename _Value> 559 class EdgeMap 561 class EdgeMap 560 562 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 561 563 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 562 564 563 565 public: 564 EdgeMap(const Graph& _g)565 566 567 EdgeMap(const Graph& _g, const _Value& _v) 568 566 explicit EdgeMap(const Graph& _g) 567 : Parent(_g) {} 568 569 EdgeMap(const Graph& _g, const _Value& _v) 570 : Parent(_g, _v) {} 569 571 570 572 EdgeMap& operator=(const EdgeMap& cmap) { 571 573 return operator=<EdgeMap>(cmap); 572 574 } 573 575 … … 575 577 EdgeMap& operator=(const CMap& cmap) { 576 578 Parent::operator=(cmap); 577 579 return *this; 578 580 } 579 581 … … 592 594 return edge; 593 595 } 594 596 595 597 void clear() { 596 598 notifier(Arc()).clear(); … … 618 620 arc_notifier.clear(); 619 621 } 620 622 621 623 }; 622 624 -
lemon/bits/graph_adaptor_extender.h
r617 r882 182 182 typedef GraphAdaptorExtender Adaptor; 183 183 184 typedef True UndirectedTag; 185 184 186 typedef typename Parent::Node Node; 185 187 typedef typename Parent::Arc Arc; -
lemon/bits/graph_extender.h
r617 r778 57 57 } 58 58 59 Node fromId(int id, Node) const{59 static Node fromId(int id, Node) { 60 60 return Parent::nodeFromId(id); 61 61 } 62 62 63 Arc fromId(int id, Arc) const{63 static Arc fromId(int id, Arc) { 64 64 return Parent::arcFromId(id); 65 65 } … … 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 } … … 605 605 606 606 public: 607 NodeMap(const Graph& graph)607 explicit NodeMap(const Graph& graph) 608 608 : Parent(graph) {} 609 609 NodeMap(const Graph& graph, const _Value& value) … … 629 629 630 630 public: 631 ArcMap(const Graph& graph)631 explicit ArcMap(const Graph& graph) 632 632 : Parent(graph) {} 633 633 ArcMap(const Graph& graph, const _Value& value) … … 653 653 654 654 public: 655 EdgeMap(const Graph& graph)655 explicit EdgeMap(const Graph& graph) 656 656 : Parent(graph) {} 657 657 -
lemon/bits/map_extender.h
r617 r802 50 50 typedef typename Parent::ConstReference ConstReference; 51 51 52 typedef typename Parent::ReferenceMapTag ReferenceMapTag; 53 52 54 class MapIt; 53 55 class ConstMapIt; … … 83 85 typedef typename Map::Value Value; 84 86 85 MapIt() {}86 87 MapIt(Invalid i) : Parent(i) {}88 89 explicit MapIt(Map& _map) : map( _map) {90 map .notifier()->first(*this);87 MapIt() : map(NULL) {} 88 89 MapIt(Invalid i) : Parent(i), map(NULL) {} 90 91 explicit MapIt(Map& _map) : map(&_map) { 92 map->notifier()->first(*this); 91 93 } 92 94 93 95 MapIt(const Map& _map, const Item& item) 96 : Parent(item), map(&_map) {} 97 98 MapIt& operator++() { 99 map->notifier()->next(*this); 100 return *this; 101 } 102 103 typename MapTraits<Map>::ConstReturnValue operator*() const { 104 return (*map)[*this]; 105 } 106 107 typename MapTraits<Map>::ReturnValue operator*() { 108 return (*map)[*this]; 109 } 110 111 void set(const Value& value) { 112 map->set(*this, value); 113 } 114 115 protected: 116 Map* map; 117 118 }; 119 120 class ConstMapIt : public Item { 121 typedef Item Parent; 122 123 public: 124 125 typedef typename Map::Value Value; 126 127 ConstMapIt() : map(NULL) {} 128 129 ConstMapIt(Invalid i) : Parent(i), map(NULL) {} 130 131 explicit ConstMapIt(Map& _map) : map(&_map) { 132 map->notifier()->first(*this); 133 } 134 135 ConstMapIt(const Map& _map, const Item& item) 94 136 : Parent(item), map(_map) {} 95 137 96 MapIt& operator++() {97 map .notifier()->next(*this);138 ConstMapIt& operator++() { 139 map->notifier()->next(*this); 98 140 return *this; 99 141 } … … 103 145 } 104 146 105 typename MapTraits<Map>::ReturnValue operator*() { 106 return map[*this]; 107 } 108 109 void set(const Value& value) { 110 map.set(*this, value); 111 } 112 113 protected: 114 Map& map; 115 116 }; 117 118 class ConstMapIt : public Item { 119 typedef Item Parent; 120 121 public: 122 123 typedef typename Map::Value Value; 124 125 ConstMapIt() {} 126 127 ConstMapIt(Invalid i) : Parent(i) { } 128 129 explicit ConstMapIt(Map& _map) : map(_map) { 130 map.notifier()->first(*this); 131 } 132 133 ConstMapIt(const Map& _map, const Item& item) 134 : Parent(item), map(_map) {} 135 136 ConstMapIt& operator++() { 137 map.notifier()->next(*this); 138 return *this; 139 } 140 141 typename MapTraits<Map>::ConstReturnValue operator*() const { 142 return map[*this]; 143 } 144 145 protected: 146 const Map& map; 147 protected: 148 const Map* map; 147 149 }; 148 150 … … 151 153 152 154 public: 153 154 ItemIt() {} 155 156 ItemIt(Invalid i) : Parent(i) {}157 158 explicit ItemIt(Map& _map) : map( _map) {159 map .notifier()->first(*this);155 ItemIt() : map(NULL) {} 156 157 158 ItemIt(Invalid i) : Parent(i), map(NULL) {} 159 160 explicit ItemIt(Map& _map) : map(&_map) { 161 map->notifier()->first(*this); 160 162 } 161 163 162 164 ItemIt(const Map& _map, const Item& item) 163 : Parent(item), map( _map) {}165 : Parent(item), map(&_map) {} 164 166 165 167 ItemIt& operator++() { 166 map .notifier()->next(*this);167 return *this; 168 } 169 170 protected: 171 const Map ↦168 map->notifier()->next(*this); 169 return *this; 170 } 171 172 protected: 173 const Map* map; 172 174 173 175 }; … … 192 194 typedef typename Parent::ConstReference ConstReference; 193 195 196 typedef typename Parent::ReferenceMapTag ReferenceMapTag; 197 194 198 class MapIt; 195 199 class ConstMapIt; … … 228 232 typedef typename Map::Value Value; 229 233 230 MapIt() {}231 232 MapIt(Invalid i) : Parent(i) { }233 234 explicit MapIt(Map& _map) : map( _map) {235 map .graph.first(*this);234 MapIt() : map(NULL) {} 235 236 MapIt(Invalid i) : Parent(i), map(NULL) { } 237 238 explicit MapIt(Map& _map) : map(&_map) { 239 map->graph.first(*this); 236 240 } 237 241 238 242 MapIt(const Map& _map, const Item& item) 239 : Parent(item), map( _map) {}243 : Parent(item), map(&_map) {} 240 244 241 245 MapIt& operator++() { 242 map .graph.next(*this);246 map->graph.next(*this); 243 247 return *this; 244 248 } 245 249 246 250 typename MapTraits<Map>::ConstReturnValue operator*() const { 247 return map[*this];251 return (*map)[*this]; 248 252 } 249 253 250 254 typename MapTraits<Map>::ReturnValue operator*() { 251 return map[*this];255 return (*map)[*this]; 252 256 } 253 257 254 258 void set(const Value& value) { 255 map .set(*this, value);256 } 257 258 protected: 259 Map ↦259 map->set(*this, value); 260 } 261 262 protected: 263 Map* map; 260 264 261 265 }; … … 268 272 typedef typename Map::Value Value; 269 273 270 ConstMapIt() {}271 272 ConstMapIt(Invalid i) : Parent(i) { }273 274 explicit ConstMapIt(Map& _map) : map( _map) {275 map .graph.first(*this);274 ConstMapIt() : map(NULL) {} 275 276 ConstMapIt(Invalid i) : Parent(i), map(NULL) { } 277 278 explicit ConstMapIt(Map& _map) : map(&_map) { 279 map->graph.first(*this); 276 280 } 277 281 278 282 ConstMapIt(const Map& _map, const Item& item) 279 : Parent(item), map( _map) {}283 : Parent(item), map(&_map) {} 280 284 281 285 ConstMapIt& operator++() { 282 map .graph.next(*this);286 map->graph.next(*this); 283 287 return *this; 284 288 } 285 289 286 290 typename MapTraits<Map>::ConstReturnValue operator*() const { 287 return map[*this];288 } 289 290 protected: 291 const Map ↦291 return (*map)[*this]; 292 } 293 294 protected: 295 const Map* map; 292 296 }; 293 297 … … 296 300 297 301 public: 298 299 ItemIt() {} 300 301 ItemIt(Invalid i) : Parent(i) { }302 303 explicit ItemIt(Map& _map) : map( _map) {304 map .graph.first(*this);302 ItemIt() : map(NULL) {} 303 304 305 ItemIt(Invalid i) : Parent(i), map(NULL) { } 306 307 explicit ItemIt(Map& _map) : map(&_map) { 308 map->graph.first(*this); 305 309 } 306 310 307 311 ItemIt(const Map& _map, const Item& item) 308 : Parent(item), map( _map) {}312 : Parent(item), map(&_map) {} 309 313 310 314 ItemIt& operator++() { 311 map .graph.next(*this);312 return *this; 313 } 314 315 protected: 316 const Map ↦315 map->graph.next(*this); 316 return *this; 317 } 318 319 protected: 320 const Map* map; 317 321 318 322 }; -
lemon/bits/path_dump.h
r529 r887 50 50 51 51 bool empty() const { 52 return predMap[target] != INVALID;52 return predMap[target] == INVALID; 53 53 } 54 54 … … 124 124 125 125 bool empty() const { 126 return source != target;126 return predMatrixMap(source, target) == INVALID; 127 127 } 128 128 -
lemon/bits/solver_bits.h
r519 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). -
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/cbc.cc
r576 r746 95 95 } 96 96 97 int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) { 98 std::vector<int> indexes; 99 std::vector<Value> values; 100 101 for(ExprIterator it = b; it != e; ++it) { 102 indexes.push_back(it->first); 103 values.push_back(it->second); 104 } 105 106 _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u); 107 return _prob->numberRows() - 1; 108 } 97 109 98 110 void CbcMip::_eraseCol(int i) { -
lemon/cbc.h
r576 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). … … 63 63 virtual int _addCol(); 64 64 virtual int _addRow(); 65 virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); 65 66 66 67 virtual void _eraseCol(int i); … … 121 122 int _message_level; 122 123 123 124 124 125 125 126 }; -
lemon/circulation.h
r688 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). … … 60 60 /// \brief The type of supply map. 61 61 /// 62 /// The type of the map that stores the signed supply values of the 63 /// nodes. 62 /// The type of the map that stores the signed supply values of the 63 /// nodes. 64 64 /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. 65 65 typedef SM SupplyMap; … … 73 73 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" 74 74 /// concept. 75 #ifdef DOXYGEN 76 typedef GR::ArcMap<Value> FlowMap; 77 #else 75 78 typedef typename Digraph::template ArcMap<Value> FlowMap; 79 #endif 76 80 77 81 /// \brief Instantiates a FlowMap. … … 88 92 /// The elevator type used by the algorithm. 89 93 /// 90 /// \sa Elevator 91 /// \sa LinkedElevator 94 /// \sa Elevator, LinkedElevator 95 #ifdef DOXYGEN 96 typedef lemon::Elevator<GR, GR::Node> Elevator; 97 #else 92 98 typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator; 99 #endif 93 100 94 101 /// \brief Instantiates an Elevator. … … 135 142 \geq sup(u) \quad \forall u\in V, \f] 136 143 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f] 137 144 138 145 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be 139 146 zero or negative in order to have a feasible solution (since the sum … … 145 152 constraints have to be satisfied with equality, i.e. all demands 146 153 have to be satisfied and all supplies have to be used. 147 154 148 155 If you need the opposite inequalities in the supply/demand constraints 149 156 (i.e. the total demand is less than the total supply and all the demands … … 167 174 \tparam SM The type of the supply map. The default map type is 168 175 \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>". 176 \tparam TR The traits class that defines various types used by the 177 algorithm. By default, it is \ref CirculationDefaultTraits 178 "CirculationDefaultTraits<GR, LM, UM, SM>". 179 In most cases, this parameter should not be set directly, 180 consider to use the named template parameters instead. 169 181 */ 170 182 #ifdef DOXYGEN … … 300 312 /// able to automatically created by the algorithm (i.e. the 301 313 /// digraph and the maximum level should be passed to it). 302 /// However an external elevator object could also be passed to the314 /// However, an external elevator object could also be passed to the 303 315 /// algorithm with the \ref elevator(Elevator&) "elevator()" function 304 316 /// before calling \ref run() or \ref init(). … … 326 338 /// \param graph The digraph the algorithm runs on. 327 339 /// \param lower The lower bounds for the flow values on the arcs. 328 /// \param upper The upper bounds (capacities) for the flow values 340 /// \param upper The upper bounds (capacities) for the flow values 329 341 /// on the arcs. 330 342 /// \param supply The signed supply values of the nodes. … … 451 463 } 452 464 453 /// \brief Sets the tolerance used by algorithm. 454 /// 455 /// Sets the tolerance used by algorithm. 465 /// \brief Sets the tolerance used by the algorithm. 466 /// 467 /// Sets the tolerance object used by the algorithm. 468 /// \return <tt>(*this)</tt> 456 469 Circulation& tolerance(const Tolerance& tolerance) { 457 470 _tol = tolerance; … … 461 474 /// \brief Returns a const reference to the tolerance. 462 475 /// 463 /// Returns a const reference to the tolerance. 476 /// Returns a const reference to the tolerance object used by 477 /// the algorithm. 464 478 const Tolerance& tolerance() const { 465 479 return _tol; … … 468 482 /// \name Execution Control 469 483 /// The simplest way to execute the algorithm is to call \ref run().\n 470 /// If you need morecontrol on the initial solution or the execution,471 /// first you have to call one of the \ref init() functions, then484 /// If you need better control on the initial solution or the execution, 485 /// you have to call one of the \ref init() functions first, then 472 486 /// the \ref start() function. 473 487 -
lemon/clp.cc
r576 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). … … 76 76 int ClpLp::_addRow() { 77 77 _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX); 78 return _prob->numberRows() - 1; 79 } 80 81 int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) { 82 std::vector<int> indexes; 83 std::vector<Value> values; 84 85 for(ExprIterator it = b; it != e; ++it) { 86 indexes.push_back(it->first); 87 values.push_back(it->second); 88 } 89 90 _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u); 78 91 return _prob->numberRows() - 1; 79 92 } -
lemon/clp.h
r576 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). … … 76 76 virtual int _addCol(); 77 77 virtual int _addRow(); 78 virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); 78 79 79 80 virtual void _eraseCol(int i); … … 138 139 139 140 virtual void _messageLevel(MessageLevel); 140 141 141 142 public: 142 143 -
lemon/concepts/digraph.h
r580 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). … … 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 Arc(const Arc&) { } 177 /// Initialize the iterator to be invalid.178 179 /// Initialize the iteratorto be invalid.180 /// 168 /// %Invalid constructor \& conversion. 169 170 /// Initializes the object to be invalid. 171 /// \sa Invalid for more details. 181 172 Arc(Invalid) { } 182 173 /// Equality operator 183 174 175 /// Equality operator. 176 /// 184 177 /// Two iterators are equal if and only if they point to the 185 /// same object or both are invalid.178 /// same object or both are \c INVALID. 186 179 bool operator==(Arc) const { return true; } 187 180 /// Inequality operator 188 181 189 /// \sa operator==(Arc n) 190 /// 182 /// Inequality operator. 191 183 bool operator!=(Arc) const { return true; } 192 184 193 185 /// Artificial ordering operator. 194 186 195 /// To allow the use of digraph descriptors as key type in std::map or 196 /// similar associative container we require this. 197 /// 198 /// \note This operator only have to define some strict ordering of 199 /// the items; this order has nothing to do with the iteration 200 /// ordering of the items. 187 /// Artificial ordering operator. 188 /// 189 /// \note This operator only has to define some strict ordering of 190 /// the arcs; this order has nothing to do with the iteration 191 /// ordering of the arcs. 201 192 bool operator<(Arc) const { return false; } 202 193 }; 203 194 204 /// This iterator goes troughthe outgoing arcs of a node.195 /// Iterator class for the outgoing arcs of a node. 205 196 206 197 /// This iterator goes trough the \e outgoing arcs of a certain node 207 198 /// of a digraph. 208 /// Its usage is quite simple, for example you can count the number199 /// Its usage is quite simple, for example, you can count the number 209 200 /// of outgoing arcs of a node \c n 210 /// in digraph \c g of type \cDigraph as follows.201 /// in a digraph \c g of type \c %Digraph as follows. 211 202 ///\code 212 203 /// int count=0; 213 /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;204 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; 214 205 ///\endcode 215 216 206 class OutArcIt : public Arc { 217 207 public: 218 208 /// Default constructor 219 209 220 /// @warning The default constructor sets the iterator221 /// to an undefined value.210 /// Default constructor. 211 /// \warning It sets the iterator to an undefined value. 222 212 OutArcIt() { } 223 213 /// Copy constructor. … … 226 216 /// 227 217 OutArcIt(const OutArcIt& e) : Arc(e) { } 228 /// Initialize the iterator to be invalid.229 230 /// Initialize the iterator to be invalid.231 /// 218 /// %Invalid constructor \& conversion. 219 220 /// Initializes the iterator to be invalid. 221 /// \sa Invalid for more details. 232 222 OutArcIt(Invalid) { } 233 /// This constructor sets the iterator to the first outgoing arc.234 235 /// This constructor sets the iterator to the first outgoing arc of236 /// the node.223 /// Sets the iterator to the first outgoing arc. 224 225 /// Sets the iterator to the first outgoing arc of the given node. 226 /// 237 227 OutArcIt(const Digraph&, const Node&) { } 238 /// Arc -> OutArcIt conversion 239 240 /// Sets the iterator to the value of the trivial iterator. 241 /// This feature necessitates that each time we 242 /// iterate the arc-set, the iteration order is the same. 228 /// Sets the iterator to the given arc. 229 230 /// Sets the iterator to the given arc of the given digraph. 231 /// 243 232 OutArcIt(const Digraph&, const Arc&) { } 244 /// Next outgoing arc233 /// Next outgoing arc 245 234 246 235 /// Assign the iterator to the next … … 249 238 }; 250 239 251 /// This iterator goes troughthe incoming arcs of a node.240 /// Iterator class for the incoming arcs of a node. 252 241 253 242 /// This iterator goes trough the \e incoming arcs of a certain node 254 243 /// of a digraph. 255 /// Its usage is quite simple, for example you can count the number256 /// of outgoing arcs of a node \c n257 /// in digraph \c g of type \cDigraph as follows.244 /// Its usage is quite simple, for example, you can count the number 245 /// of incoming arcs of a node \c n 246 /// in a digraph \c g of type \c %Digraph as follows. 258 247 ///\code 259 248 /// int count=0; 260 /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;249 /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; 261 250 ///\endcode 262 263 251 class InArcIt : public Arc { 264 252 public: 265 253 /// Default constructor 266 254 267 /// @warning The default constructor sets the iterator268 /// to an undefined value.255 /// Default constructor. 256 /// \warning It sets the iterator to an undefined value. 269 257 InArcIt() { } 270 258 /// Copy constructor. … … 273 261 /// 274 262 InArcIt(const InArcIt& e) : Arc(e) { } 275 /// Initialize the iterator to be invalid.276 277 /// Initialize the iterator to be invalid.278 /// 263 /// %Invalid constructor \& conversion. 264 265 /// Initializes the iterator to be invalid. 266 /// \sa Invalid for more details. 279 267 InArcIt(Invalid) { } 280 /// This constructor sets the iterator tofirst incoming arc.281 282 /// This constructor set the iterator to the first incoming arc of283 /// the node.268 /// Sets the iterator to the first incoming arc. 269 270 /// Sets the iterator to the first incoming arc of the given node. 271 /// 284 272 InArcIt(const Digraph&, const Node&) { } 285 /// Arc -> InArcIt conversion 286 287 /// Sets the iterator to the value of the trivial iterator \c e. 288 /// This feature necessitates that each time we 289 /// iterate the arc-set, the iteration order is the same. 273 /// Sets the iterator to the given arc. 274 275 /// Sets the iterator to the given arc of the given digraph. 276 /// 290 277 InArcIt(const Digraph&, const Arc&) { } 291 278 /// Next incoming arc 292 279 293 /// Assign the iterator to the next inarc of the corresponding node.294 /// 280 /// Assign the iterator to the next 281 /// incoming arc of the corresponding node. 295 282 InArcIt& operator++() { return *this; } 296 283 }; 297 /// This iterator goes through each arc. 298 299 /// This iterator goes through each arc of a digraph. 300 /// Its usage is quite simple, for example you can count the number 301 /// of arcs in a digraph \c g of type \c Digraph as follows: 284 285 /// Iterator class for the arcs. 286 287 /// This iterator goes through each arc of the digraph. 288 /// Its usage is quite simple, for example, you can count the number 289 /// of arcs in a digraph \c g of type \c %Digraph as follows: 302 290 ///\code 303 291 /// int count=0; 304 /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;292 /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count; 305 293 ///\endcode 306 294 class ArcIt : public Arc { … … 308 296 /// Default constructor 309 297 310 /// @warning The default constructor sets the iterator311 /// to an undefined value.298 /// Default constructor. 299 /// \warning It sets the iterator to an undefined value. 312 300 ArcIt() { } 313 301 /// Copy constructor. … … 316 304 /// 317 305 ArcIt(const ArcIt& e) : Arc(e) { } 318 /// Initialize the iterator to be invalid.319 320 /// Initialize the iterator to be invalid.321 /// 306 /// %Invalid constructor \& conversion. 307 308 /// Initializes the iterator to be invalid. 309 /// \sa Invalid for more details. 322 310 ArcIt(Invalid) { } 323 /// This constructor sets the iterator to the first arc. 324 325 /// This constructor sets the iterator to the first arc of \c g. 326 ///@param g the digraph 327 ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); } 328 /// Arc -> ArcIt conversion 329 330 /// Sets the iterator to the value of the trivial iterator \c e. 331 /// This feature necessitates that each time we 332 /// iterate the arc-set, the iteration order is the same. 311 /// Sets the iterator to the first arc. 312 313 /// Sets the iterator to the first arc of the given digraph. 314 /// 315 explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); } 316 /// Sets the iterator to the given arc. 317 318 /// Sets the iterator to the given arc of the given digraph. 319 /// 333 320 ArcIt(const Digraph&, const Arc&) { } 334 /// Next arc321 /// Next arc 335 322 336 323 /// Assign the iterator to the next arc. 324 /// 337 325 ArcIt& operator++() { return *this; } 338 326 }; 339 ///Gives back the target node of an arc. 340 341 ///Gives back the target node of an arc. 342 /// 327 328 /// \brief The source node of the arc. 329 /// 330 /// Returns the source node of the given arc. 331 Node source(Arc) const { return INVALID; } 332 333 /// \brief The target node of the arc. 334 /// 335 /// Returns the target node of the given arc. 343 336 Node target(Arc) const { return INVALID; } 344 ///Gives back the source node of an arc. 345 346 ///Gives back the source node of an arc. 347 /// 348 Node source(Arc) const { return INVALID; } 349 350 /// \brief Returns the ID of the node. 337 338 /// \brief The ID of the node. 339 /// 340 /// Returns the ID of the given node. 351 341 int id(Node) const { return -1; } 352 342 353 /// \brief Returns the ID of the arc. 343 /// \brief The ID of the arc. 344 /// 345 /// Returns the ID of the given arc. 354 346 int id(Arc) const { return -1; } 355 347 356 /// \brief Returns the node with the given ID. 357 /// 358 /// \pre The argument should be a valid node ID in the graph. 348 /// \brief The node with the given ID. 349 /// 350 /// Returns the node with the given ID. 351 /// \pre The argument should be a valid node ID in the digraph. 359 352 Node nodeFromId(int) const { return INVALID; } 360 353 361 /// \brief Returns the arc with the given ID. 362 /// 363 /// \pre The argument should be a valid arc ID in the graph. 354 /// \brief The arc with the given ID. 355 /// 356 /// Returns the arc with the given ID. 357 /// \pre The argument should be a valid arc ID in the digraph. 364 358 Arc arcFromId(int) const { return INVALID; } 365 359 366 /// \brief Returns an upper bound on the node IDs. 360 /// \brief An upper bound on the node IDs. 361 /// 362 /// Returns an upper bound on the node IDs. 367 363 int maxNodeId() const { return -1; } 368 364 369 /// \brief Returns an upper bound on the arc IDs. 365 /// \brief An upper bound on the arc IDs. 366 /// 367 /// Returns an upper bound on the arc IDs. 370 368 int maxArcId() const { return -1; } 371 369 … … 393 391 int maxId(Arc) const { return -1; } 394 392 393 /// \brief The opposite node on the arc. 394 /// 395 /// Returns the opposite node on the given arc. 396 Node oppositeNode(Node, Arc) const { return INVALID; } 397 395 398 /// \brief The base node of the iterator. 396 399 /// 397 /// Gives back the base node of the iterator.398 /// It is always the target of the pointed arc.399 Node baseNode( const InArcIt&) const { return INVALID; }400 /// Returns the base node of the given outgoing arc iterator 401 /// (i.e. the source node of the corresponding arc). 402 Node baseNode(OutArcIt) const { return INVALID; } 400 403 401 404 /// \brief The running node of the iterator. 402 405 /// 403 /// Gives back the running node of the iterator.404 /// It is always the source of the pointed arc.405 Node runningNode( const InArcIt&) const { return INVALID; }406 /// Returns the running node of the given outgoing arc iterator 407 /// (i.e. the target node of the corresponding arc). 408 Node runningNode(OutArcIt) const { return INVALID; } 406 409 407 410 /// \brief The base node of the iterator. 408 411 /// 409 /// Gives back the base node of the iterator.410 /// It is always the source of the pointed arc.411 Node baseNode( const OutArcIt&) const { return INVALID; }412 /// Returns the base node of the given incomming arc iterator 413 /// (i.e. the target node of the corresponding arc). 414 Node baseNode(InArcIt) const { return INVALID; } 412 415 413 416 /// \brief The running node of the iterator. 414 417 /// 415 /// Gives back the running node of the iterator. 416 /// It is always the target of the pointed arc. 417 Node runningNode(const OutArcIt&) const { return INVALID; } 418 419 /// \brief The opposite node on the given arc. 420 /// 421 /// Gives back the opposite node on the given arc. 422 Node oppositeNode(const Node&, const Arc&) const { return INVALID; } 423 424 /// \brief Reference map of the nodes to type \c T. 425 /// 426 /// Reference map of the nodes to type \c T. 418 /// Returns the running node of the given incomming arc iterator 419 /// (i.e. the source node of the corresponding arc). 420 Node runningNode(InArcIt) const { return INVALID; } 421 422 /// \brief Standard graph map type for the nodes. 423 /// 424 /// Standard graph map type for the nodes. 425 /// It conforms to the ReferenceMap concept. 427 426 template<class T> 428 427 class NodeMap : public ReferenceMap<Node, T, T&, const T&> { 429 428 public: 430 429 431 /// \e432 NodeMap(const Digraph&) { }433 /// \e430 /// Constructor 431 explicit NodeMap(const Digraph&) { } 432 /// Constructor with given initial value 434 433 NodeMap(const Digraph&, T) { } 435 434 436 435 private: 437 436 ///Copy constructor 438 NodeMap(const NodeMap& nm) : 437 NodeMap(const NodeMap& nm) : 439 438 ReferenceMap<Node, T, T&, const T&>(nm) { } 440 439 ///Assignment operator … … 446 445 }; 447 446 448 /// \brief Reference map of the arcs to type \c T. 449 /// 450 /// Reference map of the arcs to type \c T. 447 /// \brief Standard graph map type for the arcs. 448 /// 449 /// Standard graph map type for the arcs. 450 /// It conforms to the ReferenceMap concept. 451 451 template<class T> 452 452 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> { 453 453 public: 454 454 455 /// \e456 ArcMap(const Digraph&) { }457 /// \e455 /// Constructor 456 explicit ArcMap(const Digraph&) { } 457 /// Constructor with given initial value 458 458 ArcMap(const Digraph&, T) { } 459 459 460 private: 460 461 ///Copy constructor -
lemon/concepts/graph.h
r657 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). … … 19 19 ///\ingroup graph_concepts 20 20 ///\file 21 ///\brief The concept of Undirected Graphs.21 ///\brief The concept of undirected graphs. 22 22 23 23 #ifndef LEMON_CONCEPTS_GRAPH_H … … 25 25 26 26 #include <lemon/concepts/graph_components.h> 27 #include <lemon/concepts/maps.h> 28 #include <lemon/concept_check.h> 27 29 #include <lemon/core.h> 28 30 … … 32 34 /// \ingroup graph_concepts 33 35 /// 34 /// \brief Class describing the concept of Undirected Graphs.36 /// \brief Class describing the concept of undirected graphs. 35 37 /// 36 /// This class describes the common interface of all Undirected37 /// Graphs.38 /// This class describes the common interface of all undirected 39 /// graphs. 38 40 /// 39 /// As all concept describing classes it provides onlyinterface40 /// without any sensible implementation. So any algorithm for41 /// undirected graph should compile with this class, but it will not41 /// Like all concept classes, it only provides an interface 42 /// without any sensible implementation. So any general algorithm for 43 /// undirected graphs should compile with this class, but it will not 42 44 /// run properly, of course. 45 /// An actual graph implementation like \ref ListGraph or 46 /// \ref SmartGraph may have additional functionality. 43 47 /// 44 /// The LEMON undirected graphs also fulfill the concept of 45 /// directed graphs (\ref lemon::concepts::Digraph "Digraph 46 /// Concept"). Each edges can be seen as two opposite 47 /// directed arc and consequently the undirected graph can be 48 /// seen as the direceted graph of these directed arcs. The 49 /// Graph has the Edge inner class for the edges and 50 /// the Arc type for the directed arcs. The Arc type is 51 /// convertible to Edge or inherited from it so from a directed 52 /// arc we can get the represented edge. 48 /// The undirected graphs also fulfill the concept of \ref Digraph 49 /// "directed graphs", since each edge can also be regarded as two 50 /// oppositely directed arcs. 51 /// Undirected graphs provide an Edge type for the undirected edges and 52 /// an Arc type for the directed arcs. The Arc type is convertible to 53 /// Edge or inherited from it, i.e. the corresponding edge can be 54 /// obtained from an arc. 55 /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt 56 /// and ArcMap classes can be used for the arcs (just like in digraphs). 57 /// Both InArcIt and OutArcIt iterates on the same edges but with 58 /// opposite direction. IncEdgeIt also iterates on the same edges 59 /// as OutArcIt and InArcIt, but it is not convertible to Arc, 60 /// only to Edge. 53 61 /// 54 /// In the sense of the LEMON each edge has a default 55 /// direction (it should be in every computer implementation, 56 /// because the order of edge's nodes defines an 57 /// orientation). With the default orientation we can define that 58 /// the directed arc is forward or backward directed. With the \c 59 /// direction() and \c direct() function we can get the direction 60 /// of the directed arc and we can direct an edge. 62 /// In LEMON, each undirected edge has an inherent orientation. 63 /// Thus it can defined if an arc is forward or backward oriented in 64 /// an undirected graph with respect to this default oriantation of 65 /// the represented edge. 66 /// With the direction() and direct() functions the direction 67 /// of an arc can be obtained and set, respectively. 61 68 /// 62 /// The EdgeIt is an iterator for the edges. We can use 63 /// the EdgeMap to map values for the edges. The InArcIt and 64 /// OutArcIt iterates on the same edges but with opposite 65 /// direction. The IncEdgeIt iterates also on the same edges 66 /// as the OutArcIt and InArcIt but it is not convertible to Arc just 67 /// to Edge. 69 /// Only nodes and edges can be added to or removed from an undirected 70 /// graph and the corresponding arcs are added or removed automatically. 71 /// 72 /// \sa Digraph 68 73 class Graph { 74 private: 75 /// Graphs are \e not copy constructible. Use DigraphCopy instead. 76 Graph(const Graph&) {} 77 /// \brief Assignment of a graph to another one is \e not allowed. 78 /// Use DigraphCopy instead. 79 void operator=(const Graph&) {} 80 69 81 public: 70 /// \brief The undirected graph should be tagged by the 71 /// UndirectedTag. 72 /// 73 /// The undirected graph should be tagged by the UndirectedTag. This 74 /// tag helps the enable_if technics to make compile time 82 /// Default constructor. 83 Graph() {} 84 85 /// \brief Undirected graphs should be tagged with \c UndirectedTag. 86 /// 87 /// Undirected graphs should be tagged with \c UndirectedTag. 88 /// 89 /// This tag helps the \c enable_if technics to make compile time 75 90 /// specializations for undirected graphs. 76 91 typedef True UndirectedTag; 77 92 78 /// \brief The base type of node iterators, 79 /// or in other words, the trivial node iterator. 80 /// 81 /// This is the base type of each node iterator, 82 /// thus each kind of node iterator converts to this. 83 /// More precisely each kind of node iterator should be inherited 84 /// from the trivial node iterator. 93 /// The node type of the graph 94 95 /// This class identifies a node of the graph. It also serves 96 /// as a base class of the node iterators, 97 /// thus they convert to this type. 85 98 class Node { 86 99 public: 87 100 /// Default constructor 88 101 89 /// @warning The default constructor sets the iterator90 /// to an undefined value.102 /// Default constructor. 103 /// \warning It sets the object to an undefined value. 91 104 Node() { } 92 105 /// Copy constructor. … … 96 109 Node(const Node&) { } 97 110 98 /// Invalid constructor \& conversion.99 100 /// This constructor initializes the iteratorto be invalid.111 /// %Invalid constructor \& conversion. 112 113 /// Initializes the object to be invalid. 101 114 /// \sa Invalid for more details. 102 115 Node(Invalid) { } 103 116 /// Equality operator 104 117 118 /// Equality operator. 119 /// 105 120 /// Two iterators are equal if and only if they point to the 106 /// same object or both are invalid.121 /// same object or both are \c INVALID. 107 122 bool operator==(Node) const { return true; } 108 123 109 124 /// Inequality operator 110 125 111 /// \sa operator==(Node n) 112 /// 126 /// Inequality operator. 113 127 bool operator!=(Node) const { return true; } 114 128 115 129 /// Artificial ordering operator. 116 130 117 /// To allow the use of graph descriptors as key type in std::map or 118 /// similar associative container we require this. 119 /// 120 /// \note This operator only have to define some strict ordering of 131 /// Artificial ordering operator. 132 /// 133 /// \note This operator only has to define some strict ordering of 121 134 /// the items; this order has nothing to do with the iteration 122 135 /// ordering of the items. … … 125 138 }; 126 139 127 /// This iterator goes through each node.128 129 /// This iterator goes through each node .130 /// Its usage is quite simple, for example you can count the number131 /// of nodes in graph \c g of type \cGraph like this:140 /// Iterator class for the nodes. 141 142 /// This iterator goes through each node of the graph. 143 /// Its usage is quite simple, for example, you can count the number 144 /// of nodes in a graph \c g of type \c %Graph like this: 132 145 ///\code 133 146 /// int count=0; … … 138 151 /// Default constructor 139 152 140 /// @warning The default constructor sets the iterator141 /// to an undefined value.153 /// Default constructor. 154 /// \warning It sets the iterator to an undefined value. 142 155 NodeIt() { } 143 156 /// Copy constructor. … … 146 159 /// 147 160 NodeIt(const NodeIt& n) : Node(n) { } 148 /// Invalid constructor \& conversion.149 150 /// Initialize the iterator to be invalid.161 /// %Invalid constructor \& conversion. 162 163 /// Initializes the iterator to be invalid. 151 164 /// \sa Invalid for more details. 152 165 NodeIt(Invalid) { } 153 166 /// Sets the iterator to the first node. 154 167 155 /// Sets the iterator to the first node of \c g. 156 /// 157 NodeIt(const Graph&) { } 158 /// Node -> NodeIt conversion. 159 160 /// Sets the iterator to the node of \c the graph pointed by 161 /// the trivial iterator. 162 /// This feature necessitates that each time we 163 /// iterate the arc-set, the iteration order is the same. 168 /// Sets the iterator to the first node of the given digraph. 169 /// 170 explicit NodeIt(const Graph&) { } 171 /// Sets the iterator to the given node. 172 173 /// Sets the iterator to the given node of the given digraph. 174 /// 164 175 NodeIt(const Graph&, const Node&) { } 165 176 /// Next node. … … 171 182 172 183 173 /// The base type of the edge iterators. 174 175 /// The base type of the edge iterators. 176 /// 184 /// The edge type of the graph 185 186 /// This class identifies an edge of the graph. It also serves 187 /// as a base class of the edge iterators, 188 /// thus they will convert to this type. 177 189 class Edge { 178 190 public: 179 191 /// Default constructor 180 192 181 /// @warning The default constructor sets the iterator182 /// to an undefined value.193 /// Default constructor. 194 /// \warning It sets the object to an undefined value. 183 195 Edge() { } 184 196 /// Copy constructor. … … 187 199 /// 188 200 Edge(const Edge&) { } 189 /// Initialize the iterator to be invalid.190 191 /// Initialize the iteratorto be invalid.192 /// 201 /// %Invalid constructor \& conversion. 202 203 /// Initializes the object to be invalid. 204 /// \sa Invalid for more details. 193 205 Edge(Invalid) { } 194 206 /// Equality operator 195 207 208 /// Equality operator. 209 /// 196 210 /// Two iterators are equal if and only if they point to the 197 /// same object or both are invalid.211 /// same object or both are \c INVALID. 198 212 bool operator==(Edge) const { return true; } 199 213 /// Inequality operator 200 214 201 /// \sa operator==(Edge n) 202 /// 215 /// Inequality operator. 203 216 bool operator!=(Edge) const { return true; } 204 217 205 218 /// Artificial ordering operator. 206 219 207 /// To allow the use of graph descriptors as key type in std::map or 208 /// similar associative container we require this. 209 /// 210 /// \note This operator only have to define some strict ordering of 211 /// the items; this order has nothing to do with the iteration 212 /// ordering of the items. 220 /// Artificial ordering operator. 221 /// 222 /// \note This operator only has to define some strict ordering of 223 /// the edges; this order has nothing to do with the iteration 224 /// ordering of the edges. 213 225 bool operator<(Edge) const { return false; } 214 226 }; 215 227 216 /// This iterator goes through each edge.217 218 /// This iterator goes through each edge of agraph.219 /// Its usage is quite simple, for example you can count the number220 /// of edges in a graph \c g of type \c Graph as follows:228 /// Iterator class for the edges. 229 230 /// This iterator goes through each edge of the graph. 231 /// Its usage is quite simple, for example, you can count the number 232 /// of edges in a graph \c g of type \c %Graph as follows: 221 233 ///\code 222 234 /// int count=0; … … 227 239 /// Default constructor 228 240 229 /// @warning The default constructor sets the iterator230 /// to an undefined value.241 /// Default constructor. 242 /// \warning It sets the iterator to an undefined value. 231 243 EdgeIt() { } 232 244 /// Copy constructor. … … 235 247 /// 236 248 EdgeIt(const EdgeIt& e) : Edge(e) { } 237 /// Initialize the iterator to be invalid.238 239 /// Initialize the iterator to be invalid.240 /// 249 /// %Invalid constructor \& conversion. 250 251 /// Initializes the iterator to be invalid. 252 /// \sa Invalid for more details. 241 253 EdgeIt(Invalid) { } 242 /// This constructor sets the iterator to the first edge. 243 244 /// This constructor sets the iterator to the first edge. 245 EdgeIt(const Graph&) { } 246 /// Edge -> EdgeIt conversion 247 248 /// Sets the iterator to the value of the trivial iterator. 249 /// This feature necessitates that each time we 250 /// iterate the edge-set, the iteration order is the 251 /// same. 254 /// Sets the iterator to the first edge. 255 256 /// Sets the iterator to the first edge of the given graph. 257 /// 258 explicit EdgeIt(const Graph&) { } 259 /// Sets the iterator to the given edge. 260 261 /// Sets the iterator to the given edge of the given graph. 262 /// 252 263 EdgeIt(const Graph&, const Edge&) { } 253 264 /// Next edge 254 265 255 266 /// Assign the iterator to the next edge. 267 /// 256 268 EdgeIt& operator++() { return *this; } 257 269 }; 258 270 259 /// \brief This iterator goes trough the incident undirected 260 /// arcs of a node. 261 /// 262 /// This iterator goes trough the incident edges 263 /// of a certain node of a graph. You should assume that the 264 /// loop arcs will be iterated twice. 265 /// 266 /// Its usage is quite simple, for example you can compute the 267 /// degree (i.e. count the number of incident arcs of a node \c n 268 /// in graph \c g of type \c Graph as follows. 271 /// Iterator class for the incident edges of a node. 272 273 /// This iterator goes trough the incident undirected edges 274 /// of a certain node of a graph. 275 /// Its usage is quite simple, for example, you can compute the 276 /// degree (i.e. the number of incident edges) of a node \c n 277 /// in a graph \c g of type \c %Graph as follows. 269 278 /// 270 279 ///\code … … 272 281 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; 273 282 ///\endcode 283 /// 284 /// \warning Loop edges will be iterated twice. 274 285 class IncEdgeIt : public Edge { 275 286 public: 276 287 /// Default constructor 277 288 278 /// @warning The default constructor sets the iterator279 /// to an undefined value.289 /// Default constructor. 290 /// \warning It sets the iterator to an undefined value. 280 291 IncEdgeIt() { } 281 292 /// Copy constructor. … … 284 295 /// 285 296 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } 286 /// Initialize the iterator to be invalid.287 288 /// Initialize the iterator to be invalid.289 /// 297 /// %Invalid constructor \& conversion. 298 299 /// Initializes the iterator to be invalid. 300 /// \sa Invalid for more details. 290 301 IncEdgeIt(Invalid) { } 291 /// This constructor sets the iterator to first incident arc.292 293 /// This constructor set the iterator to the first incident arc of294 /// the node.302 /// Sets the iterator to the first incident edge. 303 304 /// Sets the iterator to the first incident edge of the given node. 305 /// 295 306 IncEdgeIt(const Graph&, const Node&) { } 296 /// Edge -> IncEdgeIt conversion 297 298 /// Sets the iterator to the value of the trivial iterator \c e. 299 /// This feature necessitates that each time we 300 /// iterate the arc-set, the iteration order is the same. 307 /// Sets the iterator to the given edge. 308 309 /// Sets the iterator to the given edge of the given graph. 310 /// 301 311 IncEdgeIt(const Graph&, const Edge&) { } 302 /// Next incident arc303 304 /// Assign the iterator to the next incident arc312 /// Next incident edge 313 314 /// Assign the iterator to the next incident edge 305 315 /// of the corresponding node. 306 316 IncEdgeIt& operator++() { return *this; } 307 317 }; 308 318 309 /// The directed arc type.310 311 /// Th e directed arc type. It can be converted to the312 /// edge or it should be inherited from the undirected313 /// edge.319 /// The arc type of the graph 320 321 /// This class identifies a directed arc of the graph. It also serves 322 /// as a base class of the arc iterators, 323 /// thus they will convert to this type. 314 324 class Arc { 315 325 public: 316 326 /// Default constructor 317 327 318 /// @warning The default constructor sets the iterator319 /// to an undefined value.328 /// Default constructor. 329 /// \warning It sets the object to an undefined value. 320 330 Arc() { } 321 331 /// Copy constructor. … … 324 334 /// 325 335 Arc(const Arc&) { } 326 /// Initialize the iterator to be invalid.327 328 /// Initialize the iteratorto be invalid.329 /// 336 /// %Invalid constructor \& conversion. 337 338 /// Initializes the object to be invalid. 339 /// \sa Invalid for more details. 330 340 Arc(Invalid) { } 331 341 /// Equality operator 332 342 343 /// Equality operator. 344 /// 333 345 /// Two iterators are equal if and only if they point to the 334 /// same object or both are invalid.346 /// same object or both are \c INVALID. 335 347 bool operator==(Arc) const { return true; } 336 348 /// Inequality operator 337 349 338 /// \sa operator==(Arc n) 339 /// 350 /// Inequality operator. 340 351 bool operator!=(Arc) const { return true; } 341 352 342 353 /// Artificial ordering operator. 343 354 344 /// To allow the use of graph descriptors as key type in std::map or 345 /// similar associative container we require this. 346 /// 347 /// \note This operator only have to define some strict ordering of 348 /// the items; this order has nothing to do with the iteration 349 /// ordering of the items. 355 /// Artificial ordering operator. 356 /// 357 /// \note This operator only has to define some strict ordering of 358 /// the arcs; this order has nothing to do with the iteration 359 /// ordering of the arcs. 350 360 bool operator<(Arc) const { return false; } 351 361 352 /// Converison to Edge 362 /// Converison to \c Edge 363 364 /// Converison to \c Edge. 365 /// 353 366 operator Edge() const { return Edge(); } 354 367 }; 355 /// This iterator goes through each directed arc. 356 357 /// This iterator goes through each arc of a graph. 358 /// Its usage is quite simple, for example you can count the number 359 /// of arcs in a graph \c g of type \c Graph as follows: 368 369 /// Iterator class for the arcs. 370 371 /// This iterator goes through each directed arc of the graph. 372 /// Its usage is quite simple, for example, you can count the number 373 /// of arcs in a graph \c g of type \c %Graph as follows: 360 374 ///\code 361 375 /// int count=0; 362 /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;376 /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count; 363 377 ///\endcode 364 378 class ArcIt : public Arc { … … 366 380 /// Default constructor 367 381 368 /// @warning The default constructor sets the iterator369 /// to an undefined value.382 /// Default constructor. 383 /// \warning It sets the iterator to an undefined value. 370 384 ArcIt() { } 371 385 /// Copy constructor. … … 374 388 /// 375 389 ArcIt(const ArcIt& e) : Arc(e) { } 376 /// Initialize the iterator to be invalid.377 378 /// Initialize the iterator to be invalid.379 /// 390 /// %Invalid constructor \& conversion. 391 392 /// Initializes the iterator to be invalid. 393 /// \sa Invalid for more details. 380 394 ArcIt(Invalid) { } 381 /// This constructor sets the iterator to the first arc. 382 383 /// This constructor sets the iterator to the first arc of \c g. 384 ///@param g the graph 385 ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } 386 /// Arc -> ArcIt conversion 387 388 /// Sets the iterator to the value of the trivial iterator \c e. 389 /// This feature necessitates that each time we 390 /// iterate the arc-set, the iteration order is the same. 395 /// Sets the iterator to the first arc. 396 397 /// Sets the iterator to the first arc of the given graph. 398 /// 399 explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } 400 /// Sets the iterator to the given arc. 401 402 /// Sets the iterator to the given arc of the given graph. 403 /// 391 404 ArcIt(const Graph&, const Arc&) { } 392 /// Next arc405 /// Next arc 393 406 394 407 /// Assign the iterator to the next arc. 408 /// 395 409 ArcIt& operator++() { return *this; } 396 410 }; 397 411 398 /// This iterator goes trough the outgoing directedarcs of a node.399 400 /// This iterator goes trough the \e outgoing arcs of a certain node401 /// of a graph.402 /// Its usage is quite simple, for example you can count the number412 /// Iterator class for the outgoing arcs of a node. 413 414 /// This iterator goes trough the \e outgoing directed arcs of a 415 /// certain node of a graph. 416 /// Its usage is quite simple, for example, you can count the number 403 417 /// of outgoing arcs of a node \c n 404 /// in graph \c g of type \cGraph as follows.418 /// in a graph \c g of type \c %Graph as follows. 405 419 ///\code 406 420 /// int count=0; 407 /// for ( Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;421 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; 408 422 ///\endcode 409 410 423 class OutArcIt : public Arc { 411 424 public: 412 425 /// Default constructor 413 426 414 /// @warning The default constructor sets the iterator415 /// to an undefined value.427 /// Default constructor. 428 /// \warning It sets the iterator to an undefined value. 416 429 OutArcIt() { } 417 430 /// Copy constructor. … … 420 433 /// 421 434 OutArcIt(const OutArcIt& e) : Arc(e) { } 422 /// Initialize the iterator to be invalid.423 424 /// Initialize the iterator to be invalid.425 /// 435 /// %Invalid constructor \& conversion. 436 437 /// Initializes the iterator to be invalid. 438 /// \sa Invalid for more details. 426 439 OutArcIt(Invalid) { } 427 /// This constructor sets the iterator to the first outgoing arc. 428 429 /// This constructor sets the iterator to the first outgoing arc of 430 /// the node. 431 ///@param n the node 432 ///@param g the graph 440 /// Sets the iterator to the first outgoing arc. 441 442 /// Sets the iterator to the first outgoing arc of the given node. 443 /// 433 444 OutArcIt(const Graph& n, const Node& g) { 434 445 ignore_unused_variable_warning(n); 435 446 ignore_unused_variable_warning(g); 436 447 } 437 /// Arc -> OutArcIt conversion 438 439 /// Sets the iterator to the value of the trivial iterator. 440 /// This feature necessitates that each time we 441 /// iterate the arc-set, the iteration order is the same. 448 /// Sets the iterator to the given arc. 449 450 /// Sets the iterator to the given arc of the given graph. 451 /// 442 452 OutArcIt(const Graph&, const Arc&) { } 443 /// Next outgoing arc453 /// Next outgoing arc 444 454 445 455 /// Assign the iterator to the next … … 448 458 }; 449 459 450 /// This iterator goes trough the incoming directedarcs of a node.451 452 /// This iterator goes trough the \e incoming arcs of a certain node453 /// of a graph.454 /// Its usage is quite simple, for example you can count the number455 /// of outgoing arcs of a node \c n456 /// in graph \c g of type \cGraph as follows.460 /// Iterator class for the incoming arcs of a node. 461 462 /// This iterator goes trough the \e incoming directed arcs of a 463 /// certain node of a graph. 464 /// Its usage is quite simple, for example, you can count the number 465 /// of incoming arcs of a node \c n 466 /// in a graph \c g of type \c %Graph as follows. 457 467 ///\code 458 468 /// int count=0; 459 /// for (Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;469 /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; 460 470 ///\endcode 461 462 471 class InArcIt : public Arc { 463 472 public: 464 473 /// Default constructor 465 474 466 /// @warning The default constructor sets the iterator467 /// to an undefined value.475 /// Default constructor. 476 /// \warning It sets the iterator to an undefined value. 468 477 InArcIt() { } 469 478 /// Copy constructor. … … 472 481 /// 473 482 InArcIt(const InArcIt& e) : Arc(e) { } 474 /// Initialize the iterator to be invalid.475 476 /// Initialize the iterator to be invalid.477 /// 483 /// %Invalid constructor \& conversion. 484 485 /// Initializes the iterator to be invalid. 486 /// \sa Invalid for more details. 478 487 InArcIt(Invalid) { } 479 /// This constructor sets the iterator to first incoming arc. 480 481 /// This constructor set the iterator to the first incoming arc of 482 /// the node. 483 ///@param n the node 484 ///@param g the graph 488 /// Sets the iterator to the first incoming arc. 489 490 /// Sets the iterator to the first incoming arc of the given node. 491 /// 485 492 InArcIt(const Graph& g, const Node& n) { 486 493 ignore_unused_variable_warning(n); 487 494 ignore_unused_variable_warning(g); 488 495 } 489 /// Arc -> InArcIt conversion 490 491 /// Sets the iterator to the value of the trivial iterator \c e. 492 /// This feature necessitates that each time we 493 /// iterate the arc-set, the iteration order is the same. 496 /// Sets the iterator to the given arc. 497 498 /// Sets the iterator to the given arc of the given graph. 499 /// 494 500 InArcIt(const Graph&, const Arc&) { } 495 501 /// Next incoming arc 496 502 497 /// Assign the iterator to the next inarc of the corresponding node.498 /// 503 /// Assign the iterator to the next 504 /// incoming arc of the corresponding node. 499 505 InArcIt& operator++() { return *this; } 500 506 }; 501 507 502 /// \brief Reference map of the nodes to type \c T. 503 /// 504 /// Reference map of the nodes to type \c T. 508 /// \brief Standard graph map type for the nodes. 509 /// 510 /// Standard graph map type for the nodes. 511 /// It conforms to the ReferenceMap concept. 505 512 template<class T> 506 513 class NodeMap : public ReferenceMap<Node, T, T&, const T&> … … 508 515 public: 509 516 510 /// \e511 NodeMap(const Graph&) { }512 /// \e517 /// Constructor 518 explicit NodeMap(const Graph&) { } 519 /// Constructor with given initial value 513 520 NodeMap(const Graph&, T) { } 514 521 … … 525 532 }; 526 533 527 /// \brief Reference map of the arcs to type \c T. 528 /// 529 /// Reference map of the arcs to type \c T. 534 /// \brief Standard graph map type for the arcs. 535 /// 536 /// Standard graph map type for the arcs. 537 /// It conforms to the ReferenceMap concept. 530 538 template<class T> 531 539 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> … … 533 541 public: 534 542 535 /// \e536 ArcMap(const Graph&) { }537 /// \e543 /// Constructor 544 explicit ArcMap(const Graph&) { } 545 /// Constructor with given initial value 538 546 ArcMap(const Graph&, T) { } 547 539 548 private: 540 549 ///Copy constructor … … 549 558 }; 550 559 551 /// Reference map of the edges to type \c T. 552 553 /// Reference map of the edges to type \c T. 560 /// \brief Standard graph map type for the edges. 561 /// 562 /// Standard graph map type for the edges. 563 /// It conforms to the ReferenceMap concept. 554 564 template<class T> 555 565 class EdgeMap : public ReferenceMap<Edge, T, T&, const T&> … … 557 567 public: 558 568 559 /// \e560 EdgeMap(const Graph&) { }561 /// \e569 /// Constructor 570 explicit EdgeMap(const Graph&) { } 571 /// Constructor with given initial value 562 572 EdgeMap(const Graph&, T) { } 573 563 574 private: 564 575 ///Copy constructor … … 573 584 }; 574 585 575 /// \brief Direct the given edge. 576 /// 577 /// Direct the given edge. The returned arc source 578 /// will be the given node. 579 Arc direct(const Edge&, const Node&) const { 580 return INVALID; 581 } 582 583 /// \brief Direct the given edge. 584 /// 585 /// Direct the given edge. The returned arc 586 /// represents the given edge and the direction comes 587 /// from the bool parameter. The source of the edge and 588 /// the directed arc is the same when the given bool is true. 589 Arc direct(const Edge&, bool) const { 590 return INVALID; 591 } 592 593 /// \brief Returns true if the arc has default orientation. 594 /// 595 /// Returns whether the given directed arc is same orientation as 596 /// the corresponding edge's default orientation. 597 bool direction(Arc) const { return true; } 598 599 /// \brief Returns the opposite directed arc. 600 /// 601 /// Returns the opposite directed arc. 602 Arc oppositeArc(Arc) const { return INVALID; } 603 604 /// \brief Opposite node on an arc 605 /// 606 /// \return The opposite of the given node on the given edge. 607 Node oppositeNode(Node, Edge) const { return INVALID; } 608 609 /// \brief First node of the edge. 610 /// 611 /// \return The first node of the given edge. 612 /// 613 /// Naturally edges don't have direction and thus 614 /// don't have source and target node. However we use \c u() and \c v() 615 /// methods to query the two nodes of the arc. The direction of the 616 /// arc which arises this way is called the inherent direction of the 617 /// edge, and is used to define the "default" direction 618 /// of the directed versions of the arcs. 586 /// \brief The first node of the edge. 587 /// 588 /// Returns the first node of the given edge. 589 /// 590 /// Edges don't have source and target nodes, however, methods 591 /// u() and v() are used to query the two end-nodes of an edge. 592 /// The orientation of an edge that arises this way is called 593 /// the inherent direction, it is used to define the default 594 /// direction for the corresponding arcs. 619 595 /// \sa v() 620 596 /// \sa direction() 621 597 Node u(Edge) const { return INVALID; } 622 598 623 /// \brief Second node of the edge. 624 /// 625 /// \return The second node of the given edge. 626 /// 627 /// Naturally edges don't have direction and thus 628 /// don't have source and target node. However we use \c u() and \c v() 629 /// methods to query the two nodes of the arc. The direction of the 630 /// arc which arises this way is called the inherent direction of the 631 /// edge, and is used to define the "default" direction 632 /// of the directed versions of the arcs. 599 /// \brief The second node of the edge. 600 /// 601 /// Returns the second node of the given edge. 602 /// 603 /// Edges don't have source and target nodes, however, methods 604 /// u() and v() are used to query the two end-nodes of an edge. 605 /// The orientation of an edge that arises this way is called 606 /// the inherent direction, it is used to define the default 607 /// direction for the corresponding arcs. 633 608 /// \sa u() 634 609 /// \sa direction() 635 610 Node v(Edge) const { return INVALID; } 636 611 637 /// \brief Source node of the directed arc. 612 /// \brief The source node of the arc. 613 /// 614 /// Returns the source node of the given arc. 638 615 Node source(Arc) const { return INVALID; } 639 616 640 /// \brief Target node of the directed arc. 617 /// \brief The target node of the arc. 618 /// 619 /// Returns the target node of the given arc. 641 620 Node target(Arc) const { return INVALID; } 642 621 643 /// \brief Returns the id of the node. 622 /// \brief The ID of the node. 623 /// 624 /// Returns the ID of the given node. 644 625 int id(Node) const { return -1; } 645 626 646 /// \brief Returns the id of the edge. 627 /// \brief The ID of the edge. 628 /// 629 /// Returns the ID of the given edge. 647 630 int id(Edge) const { return -1; } 648 631 649 /// \brief Returns the id of the arc. 632 /// \brief The ID of the arc. 633 /// 634 /// Returns the ID of the given arc. 650 635 int id(Arc) const { return -1; } 651 636 652 /// \brief Returns the node with the given id. 653 /// 654 /// \pre The argument should be a valid node id in the graph. 637 /// \brief The node with the given ID. 638 /// 639 /// Returns the node with the given ID. 640 /// \pre The argument should be a valid node ID in the graph. 655 641 Node nodeFromId(int) const { return INVALID; } 656 642 657 /// \brief Returns the edge with the given id. 658 /// 659 /// \pre The argument should be a valid edge id in the graph. 643 /// \brief The edge with the given ID. 644 /// 645 /// Returns the edge with the given ID. 646 /// \pre The argument should be a valid edge ID in the graph. 660 647 Edge edgeFromId(int) const { return INVALID; } 661 648 662 /// \brief Returns the arc with the given id. 663 /// 664 /// \pre The argument should be a valid arc id in the graph. 649 /// \brief The arc with the given ID. 650 /// 651 /// Returns the arc with the given ID. 652 /// \pre The argument should be a valid arc ID in the graph. 665 653 Arc arcFromId(int) const { return INVALID; } 666 654 667 /// \brief Returns an upper bound on the node IDs. 655 /// \brief An upper bound on the node IDs. 656 /// 657 /// Returns an upper bound on the node IDs. 668 658 int maxNodeId() const { return -1; } 669 659 670 /// \brief Returns an upper bound on the edge IDs. 660 /// \brief An upper bound on the edge IDs. 661 /// 662 /// Returns an upper bound on the edge IDs. 671 663 int maxEdgeId() const { return -1; } 672 664 673 /// \brief Returns an upper bound on the arc IDs. 665 /// \brief An upper bound on the arc IDs. 666 /// 667 /// Returns an upper bound on the arc IDs. 674 668 int maxArcId() const { return -1; } 669 670 /// \brief The direction of the arc. 671 /// 672 /// Returns \c true if the direction of the given arc is the same as 673 /// the inherent orientation of the represented edge. 674 bool direction(Arc) const { return true; } 675 676 /// \brief Direct the edge. 677 /// 678 /// Direct the given edge. The returned arc 679 /// represents the given edge and its direction comes 680 /// from the bool parameter. If it is \c true, then the direction 681 /// of the arc is the same as the inherent orientation of the edge. 682 Arc direct(Edge, bool) const { 683 return INVALID; 684 } 685 686 /// \brief Direct the edge. 687 /// 688 /// Direct the given edge. The returned arc represents the given 689 /// edge and its source node is the given node. 690 Arc direct(Edge, Node) const { 691 return INVALID; 692 } 693 694 /// \brief The oppositely directed arc. 695 /// 696 /// Returns the oppositely directed arc representing the same edge. 697 Arc oppositeArc(Arc) const { return INVALID; } 698 699 /// \brief The opposite node on the edge. 700 /// 701 /// Returns the opposite node on the given edge. 702 Node oppositeNode(Node, Edge) const { return INVALID; } 675 703 676 704 void first(Node&) const {} … … 706 734 int maxId(Arc) const { return -1; } 707 735 708 /// \brief Base node of the iterator 709 /// 710 /// Returns the base node (the source in this case) of the iterator 711 Node baseNode(OutArcIt e) const { 712 return source(e); 713 } 714 /// \brief Running node of the iterator 715 /// 716 /// Returns the running node (the target in this case) of the 717 /// iterator 718 Node runningNode(OutArcIt e) const { 719 return target(e); 720 } 721 722 /// \brief Base node of the iterator 723 /// 724 /// Returns the base node (the target in this case) of the iterator 725 Node baseNode(InArcIt e) const { 726 return target(e); 727 } 728 /// \brief Running node of the iterator 729 /// 730 /// Returns the running node (the source in this case) of the 731 /// iterator 732 Node runningNode(InArcIt e) const { 733 return source(e); 734 } 735 736 /// \brief Base node of the iterator 737 /// 738 /// Returns the base node of the iterator 739 Node baseNode(IncEdgeIt) const { 740 return INVALID; 741 } 742 743 /// \brief Running node of the iterator 744 /// 745 /// Returns the running node of the iterator 746 Node runningNode(IncEdgeIt) const { 747 return INVALID; 748 } 736 /// \brief The base node of the iterator. 737 /// 738 /// Returns the base node of the given incident edge iterator. 739 Node baseNode(IncEdgeIt) const { return INVALID; } 740 741 /// \brief The running node of the iterator. 742 /// 743 /// Returns the running node of the given incident edge iterator. 744 Node runningNode(IncEdgeIt) const { return INVALID; } 745 746 /// \brief The base node of the iterator. 747 /// 748 /// Returns the base node of the given outgoing arc iterator 749 /// (i.e. the source node of the corresponding arc). 750 Node baseNode(OutArcIt) const { return INVALID; } 751 752 /// \brief The running node of the iterator. 753 /// 754 /// Returns the running node of the given outgoing arc iterator 755 /// (i.e. the target node of the corresponding arc). 756 Node runningNode(OutArcIt) const { return INVALID; } 757 758 /// \brief The base node of the iterator. 759 /// 760 /// Returns the base node of the given incomming arc iterator 761 /// (i.e. the target node of the corresponding arc). 762 Node baseNode(InArcIt) const { return INVALID; } 763 764 /// \brief The running node of the iterator. 765 /// 766 /// Returns the running node of the given incomming arc iterator 767 /// (i.e. the source node of the corresponding arc). 768 Node runningNode(InArcIt) const { return INVALID; } 749 769 750 770 template <typename _Graph> -
lemon/concepts/graph_components.h
r666 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). … … 19 19 ///\ingroup graph_concepts 20 20 ///\file 21 ///\brief The concept of graph components.21 ///\brief The concepts of graph components. 22 22 23 23 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H … … 39 39 /// \note This class is a template class so that we can use it to 40 40 /// create graph skeleton classes. The reason for this is that \c Node 41 /// and \c Arc (or \c Edge) types should \e not derive from the same 41 /// and \c Arc (or \c Edge) types should \e not derive from the same 42 42 /// base class. For \c Node you should instantiate it with character 43 43 /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'. … … 90 90 /// 91 91 /// This operator defines an ordering of the items. 92 /// It makes possible to use graph item types as key types in 92 /// It makes possible to use graph item types as key types in 93 93 /// associative containers (e.g. \c std::map). 94 94 /// 95 /// \note This operator only ha veto define some strict ordering of95 /// \note This operator only has to define some strict ordering of 96 96 /// the items; this order has nothing to do with the iteration 97 97 /// ordering of the items. … … 123 123 /// This class describes the base interface of directed graph types. 124 124 /// All digraph %concepts have to conform to this class. 125 /// It just provides types for nodes and arcs and functions 125 /// It just provides types for nodes and arcs and functions 126 126 /// to get the source and the target nodes of arcs. 127 127 class BaseDigraphComponent { … … 427 427 /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types. 428 428 /// 429 /// This class describes the concept of \c NodeIt, \c ArcIt and 429 /// This class describes the concept of \c NodeIt, \c ArcIt and 430 430 /// \c EdgeIt subtypes of digraph and graph types. 431 431 template <typename GR, typename Item> … … 467 467 /// next item. 468 468 GraphItemIt& operator++() { return *this; } 469 469 470 470 /// \brief Equality operator 471 471 /// … … 502 502 }; 503 503 504 /// \brief Concept class for \c InArcIt, \c OutArcIt and 504 /// \brief Concept class for \c InArcIt, \c OutArcIt and 505 505 /// \c IncEdgeIt types. 506 506 /// 507 /// This class describes the concept of \c InArcIt, \c OutArcIt 507 /// This class describes the concept of \c InArcIt, \c OutArcIt 508 508 /// and \c IncEdgeIt subtypes of digraph and graph types. 509 509 /// 510 510 /// \note Since these iterator classes do not inherit from the same 511 511 /// base class, there is an additional template parameter (selector) 512 /// \c sel. For \c InArcIt you should instantiate it with character 512 /// \c sel. For \c InArcIt you should instantiate it with character 513 513 /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'. 514 514 template <typename GR, … … 531 531 GraphIncIt(const GraphIncIt& it) : Item(it) {} 532 532 533 /// \brief Constructor that sets the iterator to the first 533 /// \brief Constructor that sets the iterator to the first 534 534 /// incoming or outgoing arc. 535 535 /// 536 /// Constructor that sets the iterator to the first arc 536 /// Constructor that sets the iterator to the first arc 537 537 /// incoming to or outgoing from the given node. 538 538 explicit GraphIncIt(const GR&, const Base&) {} … … 805 805 /// \brief Return the first edge incident to the given node. 806 806 /// 807 /// This function gives back the first edge incident to the given 807 /// This function gives back the first edge incident to the given 808 808 /// node. T