Changes in / [951:41d7ac528c3a:953:d8ea85825e02] in lemon
- Files:
-
- 20 added
- 3 deleted
- 80 edited
Legend:
- Unmodified
- Added
- Removed
-
.hgignore
r610 r944 23 23 lemon/stamp-h2 24 24 doc/Doxyfile 25 doc/references.dox 25 26 cmake/version.cmake 26 27 .dirstamp -
CMakeLists.txt
r727 r791 35 35 CHECK_TYPE_SIZE("long long" LONG_LONG) 36 36 SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG}) 37 38 INCLUDE(FindPythonInterp) 37 39 38 40 ENABLE_TESTING() -
INSTALL
r615 r890 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"'. -
Makefile.am
r676 r840 18 18 cmake/FindGLPK.cmake \ 19 19 cmake/FindCOIN.cmake \ 20 cmake/LEMONConfig.cmake.in \ 20 21 cmake/version.cmake.in \ 21 22 cmake/version.cmake \ … … 44 45 include doc/Makefile.am 45 46 include tools/Makefile.am 47 include scripts/Makefile.am 46 48 47 49 DIST_SUBDIRS = demo -
README
r705 r921 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
r727 r840 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. … … 128 144 echo 129 145 echo Build additional tools........ : $enable_tools 146 echo Use valgrind for tests........ : $use_valgrind 130 147 echo 131 148 echo The packace will be installed in -
demo/arg_parser_demo.cc
r463 r915 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
r726 r943 10 10 ) 11 11 12 IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)12 IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE) 13 13 FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/) 14 14 SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha) … … 21 21 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps 22 22 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps 23 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps 23 24 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps 24 25 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps … … 27 28 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps 28 29 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps 30 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps 29 31 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps 30 32 COMMAND ${CMAKE_COMMAND} -E remove_directory html 33 COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox 31 34 COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile 32 35 WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR} -
doc/Doxyfile.in
r379 r803 1 # Doxyfile 1.5. 7.11 # Doxyfile 1.5.9 2 2 3 3 #--------------------------------------------------------------------------- … … 22 22 QT_AUTOBRIEF = NO 23 23 MULTILINE_CPP_IS_BRIEF = NO 24 DETAILS_AT_TOP = YES25 24 INHERIT_DOCS = NO 26 25 SEPARATE_MEMBER_PAGES = NO … … 92 91 "@abs_top_srcdir@/demo" \ 93 92 "@abs_top_srcdir@/tools" \ 94 "@abs_top_srcdir@/test/test_tools.h" 93 "@abs_top_srcdir@/test/test_tools.h" \ 94 "@abs_top_builddir@/doc/references.dox" 95 95 INPUT_ENCODING = UTF-8 96 96 FILE_PATTERNS = *.h \ … … 224 224 SKIP_FUNCTION_MACROS = YES 225 225 #--------------------------------------------------------------------------- 226 # Configuration::additions related to external references226 # Options related to the search engine 227 227 #--------------------------------------------------------------------------- 228 228 TAGFILES = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ " -
doc/Makefile.am
r720 r943 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/groups.dox
r948 r953 281 281 282 282 /** 283 @defgroup geomdat Geometric Data Structures 284 @ingroup auxdat 285 \brief Geometric data structures implemented in LEMON. 286 287 This group contains geometric data structures implemented in LEMON. 288 289 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional 290 vector with the usual operations. 291 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the 292 rectangular bounding box of a set of \ref lemon::dim2::Point 293 "dim2::Point"'s. 294 */ 295 296 /** 297 @defgroup matrices Matrices 298 @ingroup auxdat 299 \brief Two dimensional data storages implemented in LEMON. 300 301 This group contains two dimensional data storages implemented in LEMON. 302 */ 303 304 /** 283 305 @defgroup algs Algorithms 284 306 \brief This group contains the several algorithms … … 295 317 296 318 This group contains the common graph search algorithms, namely 297 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). 319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) 320 \ref clrs01algorithms. 298 321 */ 299 322 … … 303 326 \brief Algorithms for finding shortest paths. 304 327 305 This group contains the algorithms for finding shortest paths in digraphs. 328 This group contains the algorithms for finding shortest paths in digraphs 329 \ref clrs01algorithms. 306 330 307 331 - \ref Dijkstra algorithm for finding shortest paths from a source node … … 320 344 321 345 /** 346 @defgroup spantree Minimum Spanning Tree Algorithms 347 @ingroup algs 348 \brief Algorithms for finding minimum cost spanning trees and arborescences. 349 350 This group contains the algorithms for finding minimum cost spanning 351 trees and arborescences \ref clrs01algorithms. 352 */ 353 354 /** 322 355 @defgroup max_flow Maximum Flow Algorithms 323 356 @ingroup algs … … 325 358 326 359 This group contains the algorithms for finding maximum flows and 327 feasible circulations .360 feasible circulations \ref clrs01algorithms, \ref amo93networkflows. 328 361 329 362 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 340 373 341 374 LEMON contains several algorithms for solving maximum flow problems: 342 - \ref EdmondsKarp Edmonds-Karp algorithm. 343 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. 344 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. 345 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. 346 347 In most cases the \ref Preflow "Preflow" algorithm provides the 375 - \ref EdmondsKarp Edmonds-Karp algorithm 376 \ref edmondskarp72theoretical. 377 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm 378 \ref goldberg88newapproach. 379 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 380 \ref dinic70algorithm, \ref sleator83dynamic. 381 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees 382 \ref goldberg88newapproach, \ref sleator83dynamic. 383 384 In most cases the \ref Preflow algorithm provides the 348 385 fastest method for computing a maximum flow. All implementations 349 386 also provide functions to query the minimum cut, which is the dual … … 363 400 364 401 This group contains the algorithms for finding minimum cost flows and 365 circulations. For more information about this problem and its dual 366 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 402 circulations \ref amo93networkflows. For more information about this 403 problem and its dual solution, see \ref min_cost_flow 404 "Minimum Cost Flow Problem". 367 405 368 406 LEMON contains several algorithms for this problem. 369 407 - \ref NetworkSimplex Primal Network Simplex algorithm with various 370 pivot strategies. 371 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on 372 cost scaling. 373 - \ref CapacityScaling Successive Shortest %Path algorithm with optional 374 capacity scaling. 375 - \ref CancelAndTighten The Cancel and Tighten algorithm. 376 - \ref CycleCanceling Cycle-Canceling algorithms. 408 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. 409 - \ref CostScaling Cost Scaling algorithm based on push/augment and 410 relabel operations \ref goldberg90approximation, \ref goldberg97efficient, 411 \ref bunnagel98efficient. 412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive 413 shortest path method \ref edmondskarp72theoretical. 414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are 415 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. 377 416 378 417 In general NetworkSimplex is the most efficient implementation, … … 397 436 398 437 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} 399 \sum_{uv\in A ,u\in X, v\not\in X}cap(uv) \f]438 \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f] 400 439 401 440 LEMON contains several algorithms related to minimum cut problems: … … 413 452 414 453 /** 415 @defgroup graph_properties Connectivity and Other Graph Properties 416 @ingroup algs 417 \brief Algorithms for discovering the graph properties 418 419 This group contains the algorithms for discovering the graph properties 420 like connectivity, bipartiteness, euler property, simplicity etc. 421 422 \image html edge_biconnected_components.png 423 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 424 */ 425 426 /** 427 @defgroup planar Planarity Embedding and Drawing 428 @ingroup algs 429 \brief Algorithms for planarity checking, embedding and drawing 430 431 This group contains the algorithms for planarity checking, 432 embedding and drawing. 433 434 \image html planar.png 435 \image latex planar.eps "Plane graph" width=\textwidth 454 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms 455 @ingroup algs 456 \brief Algorithms for finding minimum mean cycles. 457 458 This group contains the algorithms for finding minimum mean cycles 459 \ref clrs01algorithms, \ref amo93networkflows. 460 461 The \e minimum \e mean \e cycle \e problem is to find a directed cycle 462 of minimum mean length (cost) in a digraph. 463 The mean length of a cycle is the average length of its arcs, i.e. the 464 ratio between the total length of the cycle and the number of arcs on it. 465 466 This problem has an important connection to \e conservative \e length 467 \e functions, too. A length function on the arcs of a digraph is called 468 conservative if and only if there is no directed cycle of negative total 469 length. For an arbitrary length function, the negative of the minimum 470 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the 471 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length 472 function. 473 474 LEMON contains three algorithms for solving the minimum mean cycle problem: 475 - \ref Karp "Karp"'s original algorithm \ref amo93networkflows, 476 \ref dasdan98minmeancycle. 477 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved 478 version of Karp's algorithm \ref dasdan98minmeancycle. 479 - \ref Howard "Howard"'s policy iteration algorithm 480 \ref dasdan98minmeancycle. 481 482 In practice, the Howard algorithm proved to be by far the most efficient 483 one, though the best known theoretical bound on its running time is 484 exponential. 485 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space 486 O(n<sup>2</sup>+e), but the latter one is typically faster due to the 487 applied early termination scheme. 436 488 */ 437 489 … … 479 531 perfect fractional matching in general graphs. 480 532 481 \image html bipartite_matching.png 482 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth 483 */ 484 485 /** 486 @defgroup spantree Minimum Spanning Tree Algorithms 487 @ingroup algs 488 \brief Algorithms for finding minimum cost spanning trees and arborescences. 489 490 This group contains the algorithms for finding minimum cost spanning 491 trees and arborescences. 533 \image html matching.png 534 \image latex matching.eps "Min Cost Perfect Matching" width=\textwidth 535 */ 536 537 /** 538 @defgroup graph_properties Connectivity and Other Graph Properties 539 @ingroup algs 540 \brief Algorithms for discovering the graph properties 541 542 This group contains the algorithms for discovering the graph properties 543 like connectivity, bipartiteness, euler property, simplicity etc. 544 545 \image html connected_components.png 546 \image latex connected_components.eps "Connected components" width=\textwidth 547 */ 548 549 /** 550 @defgroup planar Planarity Embedding and Drawing 551 @ingroup algs 552 \brief Algorithms for planarity checking, embedding and drawing 553 554 This group contains the algorithms for planarity checking, 555 embedding and drawing. 556 557 \image html planar.png 558 \image latex planar.eps "Plane graph" width=\textwidth 559 */ 560 561 /** 562 @defgroup approx Approximation Algorithms 563 @ingroup algs 564 \brief Approximation algorithms. 565 566 This group contains the approximation and heuristic algorithms 567 implemented in LEMON. 492 568 */ 493 569 … … 499 575 This group contains some algorithms implemented in LEMON 500 576 in order to make it easier to implement complex algorithms. 501 */502 503 /**504 @defgroup approx Approximation Algorithms505 @ingroup algs506 \brief Approximation algorithms.507 508 This group contains the approximation and heuristic algorithms509 implemented in LEMON.510 577 */ 511 578 … … 520 587 521 588 /** 522 @defgroup lp_group L p and MipSolvers589 @defgroup lp_group LP and MIP Solvers 523 590 @ingroup gen_opt_group 524 \brief Lp and Mip solver interfaces for LEMON. 525 526 This group contains Lp and Mip solver interfaces for LEMON. The 527 various LP solvers could be used in the same manner with this 528 interface. 591 \brief LP and MIP solver interfaces for LEMON. 592 593 This group contains LP and MIP solver interfaces for LEMON. 594 Various LP solvers could be used in the same manner with this 595 high-level interface. 596 597 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 598 \ref cplex, \ref soplex. 529 599 */ 530 600 … … 616 686 617 687 /** 618 @defgroup dimacs_group DIMACS format688 @defgroup dimacs_group DIMACS Format 619 689 @ingroup io_group 620 690 \brief Read and write files in DIMACS format … … 665 735 \brief Skeleton and concept checking classes for graph structures 666 736 667 This group contains the skeletons and concept checking classes of LEMON's668 graph structures and helper classes used to implement these.737 This group contains the skeletons and concept checking classes of 738 graph structures. 669 739 */ 670 740 … … 678 748 679 749 /** 750 @defgroup tools Standalone Utility Applications 751 752 Some utility applications are listed here. 753 754 The standard compilation procedure (<tt>./configure;make</tt>) will compile 755 them, as well. 756 */ 757 758 /** 680 759 \anchor demoprograms 681 760 … … 689 768 */ 690 769 691 /**692 @defgroup tools Standalone Utility Applications693 694 Some utility applications are listed here.695 696 The standard compilation procedure (<tt>./configure;make</tt>) will compile697 them, as well.698 */699 700 770 } -
doc/mainpage.dox
r705 r921 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
r710 r835 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$. … … 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
r948 r953 61 61 lemon/bfs.h \ 62 62 lemon/bin_heap.h \ 63 lemon/binom _heap.h \63 lemon/binomial_heap.h \ 64 64 lemon/bucket_heap.h \ 65 lemon/capacity_scaling.h \ 65 66 lemon/cbc.h \ 66 67 lemon/circulation.h \ … … 69 70 lemon/concept_check.h \ 70 71 lemon/connectivity.h \ 72 lemon/core.h \ 73 lemon/cost_scaling.h \ 71 74 lemon/counter.h \ 72 lemon/core.h \73 75 lemon/cplex.h \ 76 lemon/cycle_canceling.h \ 74 77 lemon/dfs.h \ 78 lemon/dheap.h \ 75 79 lemon/dijkstra.h \ 76 80 lemon/dim2.h \ … … 81 85 lemon/euler.h \ 82 86 lemon/fib_heap.h \ 83 lemon/fourary_heap.h \84 87 lemon/fractional_matching.h \ 85 88 lemon/full_graph.h \ … … 88 91 lemon/graph_to_eps.h \ 89 92 lemon/grid_graph.h \ 93 lemon/hartmann_orlin_mmc.h \ 94 lemon/howard_mmc.h \ 90 95 lemon/hypercube_graph.h \ 91 lemon/kar y_heap.h \96 lemon/karp_mmc.h \ 92 97 lemon/kruskal.h \ 93 98 lemon/hao_orlin.h \ … … 106 111 lemon/pairing_heap.h \ 107 112 lemon/path.h \ 113 lemon/planarity.h \ 108 114 lemon/preflow.h \ 115 lemon/quad_heap.h \ 109 116 lemon/radix_heap.h \ 110 117 lemon/radix_sort.h \ … … 112 119 lemon/smart_graph.h \ 113 120 lemon/soplex.h \ 121 lemon/static_graph.h \ 114 122 lemon/suurballe.h \ 115 123 lemon/time_measure.h \ -
lemon/adaptors.h
r703 r834 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. … … 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. … … 1315 1320 /// parameter is set to be \c const. 1316 1321 /// 1322 /// This class provides only linear time counting for nodes, edges and arcs. 1323 /// 1317 1324 /// \tparam GR The type of the adapted graph. 1318 1325 /// It must conform to the \ref concepts::Graph "Graph" concept. … … 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. … … 1620 1629 /// parameter is set to be \c const. 1621 1630 /// 1631 /// This class provides only linear time counting for nodes and arcs. 1632 /// 1622 1633 /// \tparam DGR The type of the adapted digraph. 1623 1634 /// It must conform to the \ref concepts::Digraph "Digraph" concept. … … 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. … … 2233 2246 /// parameter is set to be \c const. 2234 2247 /// 2248 /// This class provides item counting in the same time as the adapted 2249 /// digraph structure. 2250 /// 2235 2251 /// \tparam DGR The type of the adapted digraph. 2236 2252 /// It must conform to the \ref concepts::Digraph "Digraph" concept. … … 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. … … 2678 2697 /// arcs). 2679 2698 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. 2699 /// 2700 /// This class provides only linear time counting for nodes and arcs. 2680 2701 /// 2681 2702 /// \tparam DGR The type of the adapted digraph. … … 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. -
lemon/arg_parser.cc
r463 r915 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
r463 r915 35 35 namespace lemon { 36 36 37 ///Exception used by ArgParser 38 class ArgParserException : public Exception { 39 public: 40 enum Reason { 41 HELP, /// <tt>--help</tt> option was given 42 UNKNOWN_OPT, /// Unknown option was given 43 INVALID_OPT /// Invalid combination of options 44 }; 45 46 private: 47 Reason _reason; 48 49 public: 50 ///Constructor 51 ArgParserException(Reason r) throw() : _reason(r) {} 52 ///Virtual destructor 53 virtual ~ArgParserException() throw() {} 54 ///A short description of the exception 55 virtual const char* what() const throw() { 56 switch(_reason) 57 { 58 case HELP: 59 return "lemon::ArgParseException: ask for help"; 60 break; 61 case UNKNOWN_OPT: 62 return "lemon::ArgParseException: unknown option"; 63 break; 64 case INVALID_OPT: 65 return "lemon::ArgParseException: invalid combination of options"; 66 break; 67 } 68 return ""; 69 } 70 ///Return the reason for the failure 71 Reason reason() const {return _reason; } 72 }; 73 74 37 75 ///Command line arguments parser 38 76 … … 104 142 std::string _command_name; 105 143 106 144 107 145 private: 108 146 //Bind a function to an option. … … 116 154 const std::string &help, 117 155 void (*func)(void *),void *data); 156 157 bool _exit_on_problems; 158 159 void _terminate(ArgParserException::Reason reason) const; 118 160 119 161 public: … … 381 423 const std::vector<std::string> &files() const { return _file_args; } 382 424 425 ///Throw instead of exit in case of problems 426 void throwOnProblems() 427 { 428 _exit_on_problems=false; 429 } 383 430 }; 384 431 } -
lemon/bellman_ford.h
r746 r917 24 24 /// \brief Bellman-Ford algorithm. 25 25 26 #include <lemon/list_graph.h> 26 27 #include <lemon/bits/path_dump.h> 27 28 #include <lemon/core.h> 28 29 #include <lemon/error.h> 29 30 #include <lemon/maps.h> 31 #include <lemon/tolerance.h> 30 32 #include <lemon/path.h> 31 33 … … 34 36 namespace lemon { 35 37 36 /// \brief Default OperationTraits for the BellmanFord algorithm class.38 /// \brief Default operation traits for the BellmanFord algorithm class. 37 39 /// 38 40 /// This operation traits class defines all computational operations … … 41 43 /// If the numeric type does not have infinity value, then the maximum 42 44 /// value is used as extremal infinity value. 45 /// 46 /// \see BellmanFordToleranceOperationTraits 43 47 template < 44 48 typename V, 45 49 bool has_inf = std::numeric_limits<V>::has_infinity> 46 50 struct BellmanFordDefaultOperationTraits { 47 /// \ e51 /// \brief Value type for the algorithm. 48 52 typedef V Value; 49 53 /// \brief Gives back the zero value of the type. … … 84 88 }; 85 89 90 /// \brief Operation traits for the BellmanFord algorithm class 91 /// using tolerance. 92 /// 93 /// This operation traits class defines all computational operations 94 /// and constants that are used in the Bellman-Ford algorithm. 95 /// The only difference between this implementation and 96 /// \ref BellmanFordDefaultOperationTraits is that this class uses 97 /// the \ref Tolerance "tolerance technique" in its \ref less() 98 /// function. 99 /// 100 /// \tparam V The value type. 101 /// \tparam eps The epsilon value for the \ref less() function. 102 /// By default, it is the epsilon value used by \ref Tolerance 103 /// "Tolerance<V>". 104 /// 105 /// \see BellmanFordDefaultOperationTraits 106 #ifdef DOXYGEN 107 template <typename V, V eps> 108 #else 109 template < 110 typename V, 111 V eps = Tolerance<V>::def_epsilon> 112 #endif 113 struct BellmanFordToleranceOperationTraits { 114 /// \brief Value type for the algorithm. 115 typedef V Value; 116 /// \brief Gives back the zero value of the type. 117 static Value zero() { 118 return static_cast<Value>(0); 119 } 120 /// \brief Gives back the positive infinity value of the type. 121 static Value infinity() { 122 return std::numeric_limits<Value>::infinity(); 123 } 124 /// \brief Gives back the sum of the given two elements. 125 static Value plus(const Value& left, const Value& right) { 126 return left + right; 127 } 128 /// \brief Gives back \c true only if the first value is less than 129 /// the second. 130 static bool less(const Value& left, const Value& right) { 131 return left + eps < right; 132 } 133 }; 134 86 135 /// \brief Default traits class of BellmanFord class. 87 136 /// … … 107 156 /// It defines the used operations and the infinity value for the 108 157 /// given \c Value type. 109 /// \see BellmanFordDefaultOperationTraits 158 /// \see BellmanFordDefaultOperationTraits, 159 /// BellmanFordToleranceOperationTraits 110 160 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 111 161 … … 171 221 /// the lengths of the arcs. The default map type is 172 222 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 223 /// \tparam TR The traits class that defines various types used by the 224 /// algorithm. By default, it is \ref BellmanFordDefaultTraits 225 /// "BellmanFordDefaultTraits<GR, LEN>". 226 /// In most cases, this parameter should not be set directly, 227 /// consider to use the named template parameters instead. 173 228 #ifdef DOXYGEN 174 229 template <typename GR, typename LEN, typename TR> … … 237 292 _dist = Traits::createDistMap(*_gr); 238 293 } 239 _mask = new MaskMap(*_gr, false); 294 if(!_mask) { 295 _mask = new MaskMap(*_gr); 296 } 240 297 } 241 298 … … 300 357 /// \ref named-templ-param "Named parameter" for setting 301 358 /// \c OperationTraits type. 302 /// For more information see \ref BellmanFordDefaultOperationTraits.359 /// For more information, see \ref BellmanFordDefaultOperationTraits. 303 360 template <class T> 304 361 struct SetOperationTraits … … 403 460 _process.push_back(it); 404 461 _mask->set(it, true); 462 } 463 } else { 464 for (NodeIt it(*_gr); it != INVALID; ++it) { 465 _mask->set(it, false); 405 466 } 406 467 } … … 718 779 /// 719 780 /// The shortest path tree used here is equal to the shortest path 720 /// tree used in \ref predNode() and \ predMap().781 /// tree used in \ref predNode() and \ref predMap(). 721 782 /// 722 783 /// \pre Either \ref run() or \ref init() must be called before … … 733 794 /// 734 795 /// The shortest path tree used here is equal to the shortest path 735 /// tree used in \ref predArc() and \ predMap().796 /// tree used in \ref predArc() and \ref predMap(). 736 797 /// 737 798 /// \pre Either \ref run() or \ref init() must be called before … … 776 837 /// length if the algorithm has already found one. 777 838 /// Otherwise it gives back an empty path. 778 lemon::Path<Digraph> negativeCycle() {839 lemon::Path<Digraph> negativeCycle() const { 779 840 typename Digraph::template NodeMap<int> state(*_gr, -1); 780 841 lemon::Path<Digraph> cycle; … … 826 887 /// It defines the used operations and the infinity value for the 827 888 /// given \c Value type. 828 /// \see BellmanFordDefaultOperationTraits 889 /// \see BellmanFordDefaultOperationTraits, 890 /// BellmanFordToleranceOperationTraits 829 891 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 830 892 … … 927 989 /// This class should only be used through the \ref bellmanFord() 928 990 /// function, which makes it easier to use the algorithm. 991 /// 992 /// \tparam TR The traits class that defines various types used by the 993 /// algorithm. 929 994 template<class TR> 930 995 class BellmanFordWizard : public TR { -
lemon/bfs.h
r525 r891 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 meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.85 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 86 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 87 ///Instantiates a \c ReachedMap. … … 97 98 98 99 ///The type of the map that stores the distances of the nodes. 99 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.100 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 100 101 typedef typename Digraph::template NodeMap<int> DistMap; 101 102 ///Instantiates a \c DistMap. … … 121 122 ///\tparam GR The type of the digraph the algorithm runs on. 122 123 ///The default type is \ref ListDigraph. 124 ///\tparam TR The traits class that defines various types used by the 125 ///algorithm. By default, it is \ref BfsDefaultTraits 126 ///"BfsDefaultTraits<GR>". 127 ///In most cases, this parameter should not be set directly, 128 ///consider to use the named template parameters instead. 123 129 #ifdef DOXYGEN 124 130 template <typename GR, … … 226 232 ///\ref named-templ-param "Named parameter" for setting 227 233 ///\c PredMap type. 228 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.234 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 229 235 template <class T> 230 236 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 246 252 ///\ref named-templ-param "Named parameter" for setting 247 253 ///\c DistMap type. 248 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.254 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 249 255 template <class T> 250 256 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 266 272 ///\ref named-templ-param "Named parameter" for setting 267 273 ///\c ReachedMap type. 268 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.274 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 269 275 template <class T> 270 276 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 286 292 ///\ref named-templ-param "Named parameter" for setting 287 293 ///\c ProcessedMap type. 288 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.294 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 289 295 template <class T> 290 296 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 414 420 ///The simplest way to execute the BFS algorithm is to use one of the 415 421 ///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 with422 ///If you need better control on the execution, you have to call 423 ///\ref init() first, then you can add several source nodes with 418 424 ///\ref addSource(). Finally the actual path computation can be 419 425 ///performed with one of the \ref start() functions. … … 701 707 ///Runs the algorithm to visit all nodes in the digraph. 702 708 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). 709 ///This method runs the %BFS algorithm in order to visit all nodes 710 ///in the digraph. 709 711 /// 710 712 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 738 740 ///@{ 739 741 740 ///The shortest path to anode.741 742 ///Returns the shortest path to a node.742 ///The shortest path to the given node. 743 744 ///Returns the shortest path to the given node from the root(s). 743 745 /// 744 746 ///\warning \c t should be reached from the root(s). … … 748 750 Path path(Node t) const { return Path(*G, *_pred, t); } 749 751 750 ///The distance of anode from the root(s).751 752 ///Returns the distance of anode from the root(s).752 ///The distance of the given node from the root(s). 753 754 ///Returns the distance of the given node from the root(s). 753 755 /// 754 756 ///\warning If node \c v is not reached from the root(s), then … … 759 761 int dist(Node v) const { return (*_dist)[v]; } 760 762 761 ///Returns the 'previous arc' of the shortest path tree for a node. 762 763 ///\brief Returns the 'previous arc' of the shortest path tree for 764 ///the given node. 765 /// 763 766 ///This function returns the 'previous arc' of the shortest path 764 767 ///tree for the node \c v, i.e. it returns the last arc of a … … 767 770 /// 768 771 ///The shortest path tree used here is equal to the shortest path 769 ///tree used in \ref predNode() .772 ///tree used in \ref predNode() and \ref predMap(). 770 773 /// 771 774 ///\pre Either \ref run(Node) "run()" or \ref init() … … 773 776 Arc predArc(Node v) const { return (*_pred)[v];} 774 777 775 ///Returns the 'previous node' of the shortest path tree for a node. 776 778 ///\brief Returns the 'previous node' of the shortest path tree for 779 ///the given node. 780 /// 777 781 ///This function returns the 'previous node' of the shortest path 778 782 ///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 INVALID783 ///of a shortest path from a root to \c v. It is \c INVALID 780 784 ///if \c v is not reached from the root(s) or if \c v is a root. 781 785 /// 782 786 ///The shortest path tree used here is equal to the shortest path 783 ///tree used in \ref predArc() .787 ///tree used in \ref predArc() and \ref predMap(). 784 788 /// 785 789 ///\pre Either \ref run(Node) "run()" or \ref init() … … 802 806 /// 803 807 ///Returns a const reference to the node map that stores the predecessor 804 ///arcs, which form the shortest path tree .808 ///arcs, which form the shortest path tree (forest). 805 809 /// 806 810 ///\pre Either \ref run(Node) "run()" or \ref init() … … 808 812 const PredMap &predMap() const { return *_pred;} 809 813 810 ///Checks if anode is reached from the root(s).814 ///Checks if the given node is reached from the root(s). 811 815 812 816 ///Returns \c true if \c v is reached from the root(s). … … 834 838 ///The type of the map that stores the predecessor 835 839 ///arcs of the shortest paths. 836 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.840 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 837 841 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 838 842 ///Instantiates a PredMap. … … 849 853 850 854 ///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.855 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 856 ///By default, it is a NullMap. 853 857 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 854 858 ///Instantiates a ProcessedMap. … … 869 873 870 874 ///The type of the map that indicates which nodes are reached. 871 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.875 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 872 876 typedef typename Digraph::template NodeMap<bool> ReachedMap; 873 877 ///Instantiates a ReachedMap. … … 884 888 885 889 ///The type of the map that stores the distances of the nodes. 886 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.890 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 887 891 typedef typename Digraph::template NodeMap<int> DistMap; 888 892 ///Instantiates a DistMap. … … 899 903 900 904 ///The type of the shortest paths. 901 ///It must meetthe \ref concepts::Path "Path" concept.905 ///It must conform to the \ref concepts::Path "Path" concept. 902 906 typedef lemon::Path<Digraph> Path; 903 907 }; … … 905 909 /// Default traits class used by BfsWizard 906 910 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. 911 /// Default traits class used by BfsWizard. 912 /// \tparam GR The type of the digraph. 913 913 template<class GR> 914 914 class BfsWizardBase : public BfsWizardDefaultTraits<GR> … … 938 938 /// Constructor. 939 939 940 /// This constructor does not require parameters, thereforeit initiates940 /// This constructor does not require parameters, it initiates 941 941 /// all of the attributes to \c 0. 942 942 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 963 963 /// This class should only be used through the \ref bfs() function, 964 964 /// which makes it easier to use the algorithm. 965 /// 966 /// \tparam TR The traits class that defines various types used by the 967 /// algorithm. 965 968 template<class TR> 966 969 class BfsWizard : public TR … … 968 971 typedef TR Base; 969 972 970 ///The type of the digraph the algorithm runs on.971 973 typedef typename TR::Digraph Digraph; 972 974 … … 976 978 typedef typename Digraph::OutArcIt OutArcIt; 977 979 978 ///\brief The type of the map that stores the predecessor979 ///arcs of the shortest paths.980 980 typedef typename TR::PredMap PredMap; 981 ///\brief The type of the map that stores the distances of the nodes.982 981 typedef typename TR::DistMap DistMap; 983 ///\brief The type of the map that indicates which nodes are reached.984 982 typedef typename TR::ReachedMap ReachedMap; 985 ///\brief The type of the map that indicates which nodes are processed.986 983 typedef typename TR::ProcessedMap ProcessedMap; 987 ///The type of the shortest paths988 984 typedef typename TR::Path Path; 989 985 … … 1055 1051 ///Runs BFS algorithm to visit all nodes in the digraph. 1056 1052 1057 ///This method runs BFS algorithm in order to compute1058 /// the shortest path to each node.1053 ///This method runs BFS algorithm in order to visit all nodes 1054 ///in the digraph. 1059 1055 void run() 1060 1056 { … … 1068 1064 SetPredMapBase(const TR &b) : TR(b) {} 1069 1065 }; 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. 1066 1067 ///\brief \ref named-templ-param "Named parameter" for setting 1068 ///the predecessor map. 1069 /// 1070 ///\ref named-templ-param "Named parameter" function for setting 1071 ///the map that stores the predecessor arcs of the nodes. 1075 1072 template<class T> 1076 1073 BfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1086 1083 SetReachedMapBase(const TR &b) : TR(b) {} 1087 1084 }; 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. 1085 1086 ///\brief \ref named-templ-param "Named parameter" for setting 1087 ///the reached map. 1088 /// 1089 ///\ref named-templ-param "Named parameter" function for setting 1090 ///the map that indicates which nodes are reached. 1093 1091 template<class T> 1094 1092 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1104 1102 SetDistMapBase(const TR &b) : TR(b) {} 1105 1103 }; 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. 1104 1105 ///\brief \ref named-templ-param "Named parameter" for setting 1106 ///the distance map. 1107 /// 1108 ///\ref named-templ-param "Named parameter" function for setting 1109 ///the map that stores the distances of the nodes calculated 1110 ///by the algorithm. 1111 1111 template<class T> 1112 1112 BfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1122 1122 SetProcessedMapBase(const TR &b) : TR(b) {} 1123 1123 }; 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. 1124 1125 ///\brief \ref named-func-param "Named parameter" for setting 1126 ///the processed map. 1127 /// 1128 ///\ref named-templ-param "Named parameter" function for setting 1129 ///the map that indicates which nodes are processed. 1129 1130 template<class T> 1130 1131 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1265 1266 /// 1266 1267 /// The type of the map that indicates which nodes are reached. 1267 /// It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.1268 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1268 1269 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1269 1270 … … 1303 1304 /// does not observe the BFS events. If you want to observe the BFS 1304 1305 /// 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.1306 /// \tparam TR The traits class that defines various types used by the 1307 /// algorithm. By default, it is \ref BfsVisitDefaultTraits 1308 /// "BfsVisitDefaultTraits<GR>". 1309 /// In most cases, this parameter should not be set directly, 1310 /// consider to use the named template parameters instead. 1310 1311 #ifdef DOXYGEN 1311 1312 template <typename GR, typename VS, typename TR> … … 1426 1427 /// The simplest way to execute the BFS algorithm is to use one of the 1427 1428 /// 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 with1429 /// If you need better control on the execution, you have to call 1430 /// \ref init() first, then you can add several source nodes with 1430 1431 /// \ref addSource(). Finally the actual path computation can be 1431 1432 /// performed with one of the \ref start() functions. … … 1699 1700 /// \brief Runs the algorithm to visit all nodes in the digraph. 1700 1701 /// 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). 1702 /// This method runs the %BFS algorithm in order to visit all nodes 1703 /// in the digraph. 1707 1704 /// 1708 1705 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 1736 1733 ///@{ 1737 1734 1738 /// \brief Checks if anode is reached from the root(s).1735 /// \brief Checks if the given node is reached from the root(s). 1739 1736 /// 1740 1737 /// Returns \c true if \c v is reached from the root(s). -
lemon/bits/graph_extender.h
r732 r825 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 } -
lemon/bits/map_extender.h
r664 r867 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/cbc.cc
r623 r793 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
r623 r793 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); -
lemon/circulation.h
r736 r891 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. … … 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(). … … 470 482 /// \name Execution Control 471 483 /// The simplest way to execute the algorithm is to call \ref run().\n 472 /// If you need morecontrol on the initial solution or the execution,473 /// 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 474 486 /// the \ref start() function. 475 487 -
lemon/clp.cc
r623 r793 79 79 } 80 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); 91 return _prob->numberRows() - 1; 92 } 93 81 94 82 95 void ClpLp::_eraseCol(int c) { -
lemon/clp.h
r623 r793 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); -
lemon/concepts/digraph.h
r627 r833 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 … … 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
r704 r833 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
r713 r833 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 … … 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. -
lemon/concepts/heap.h
r757 r883 89 89 /// handle the cross references. The assigned value must be 90 90 /// \c PRE_HEAP (<tt>-1</tt>) for each item. 91 #ifdef DOXYGEN 91 92 explicit Heap(ItemIntMap &map) {} 93 #else 94 explicit Heap(ItemIntMap&) {} 95 #endif 92 96 93 97 /// \brief Constructor. … … 99 103 /// \c PRE_HEAP (<tt>-1</tt>) for each item. 100 104 /// \param comp The function object used for comparing the priorities. 105 #ifdef DOXYGEN 101 106 explicit Heap(ItemIntMap &map, const CMP &comp) {} 107 #else 108 explicit Heap(ItemIntMap&, const CMP&) {} 109 #endif 102 110 103 111 /// \brief The number of items stored in the heap. … … 127 135 /// \param p The priority of the item. 128 136 /// \pre \e i must not be stored in the heap. 137 #ifdef DOXYGEN 129 138 void push(const Item &i, const Prio &p) {} 139 #else 140 void push(const Item&, const Prio&) {} 141 #endif 130 142 131 143 /// \brief Return the item having minimum priority. … … 133 145 /// This function returns the item having minimum priority. 134 146 /// \pre The heap must be non-empty. 135 Item top() const { }147 Item top() const { return Item(); } 136 148 137 149 /// \brief The minimum priority. … … 139 151 /// This function returns the minimum priority. 140 152 /// \pre The heap must be non-empty. 141 Prio prio() const { }153 Prio prio() const { return Prio(); } 142 154 143 155 /// \brief Remove the item having minimum priority. … … 153 165 /// \param i The item to delete. 154 166 /// \pre \e i must be in the heap. 167 #ifdef DOXYGEN 155 168 void erase(const Item &i) {} 169 #else 170 void erase(const Item&) {} 171 #endif 156 172 157 173 /// \brief The priority of the given item. … … 160 176 /// \param i The item. 161 177 /// \pre \e i must be in the heap. 178 #ifdef DOXYGEN 162 179 Prio operator[](const Item &i) const {} 180 #else 181 Prio operator[](const Item&) const { return Prio(); } 182 #endif 163 183 164 184 /// \brief Set the priority of an item or insert it, if it is … … 171 191 /// \param i The item. 172 192 /// \param p The priority. 193 #ifdef DOXYGEN 173 194 void set(const Item &i, const Prio &p) {} 195 #else 196 void set(const Item&, const Prio&) {} 197 #endif 174 198 175 199 /// \brief Decrease the priority of an item to the given value. … … 179 203 /// \param p The priority. 180 204 /// \pre \e i must be stored in the heap with priority at least \e p. 205 #ifdef DOXYGEN 181 206 void decrease(const Item &i, const Prio &p) {} 207 #else 208 void decrease(const Item&, const Prio&) {} 209 #endif 182 210 183 211 /// \brief Increase the priority of an item to the given value. … … 187 215 /// \param p The priority. 188 216 /// \pre \e i must be stored in the heap with priority at most \e p. 217 #ifdef DOXYGEN 189 218 void increase(const Item &i, const Prio &p) {} 219 #else 220 void increase(const Item&, const Prio&) {} 221 #endif 190 222 191 223 /// \brief Return the state of an item. … … 197 229 /// to the heap again. 198 230 /// \param i The item. 231 #ifdef DOXYGEN 199 232 State state(const Item &i) const {} 233 #else 234 State state(const Item&) const { return PRE_HEAP; } 235 #endif 200 236 201 237 /// \brief Set the state of an item in the heap. … … 206 242 /// \param i The item. 207 243 /// \param st The state. It should not be \c IN_HEAP. 244 #ifdef DOXYGEN 208 245 void state(const Item& i, State st) {} 246 #else 247 void state(const Item&, State) {} 248 #endif 209 249 210 250 -
lemon/concepts/maps.h
r576 r765 183 183 template<typename _ReferenceMap> 184 184 struct Constraints { 185 void constraints() { 185 typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type 186 constraints() { 186 187 checkConcept<ReadWriteMap<K, T>, _ReferenceMap >(); 187 188 ref = m[key]; -
lemon/concepts/path.h
r606 r832 19 19 ///\ingroup concept 20 20 ///\file 21 ///\brief Classes for representing paths in digraphs.21 ///\brief The concept of paths 22 22 /// 23 23 … … 39 39 /// A skeleton structure for representing directed paths in a 40 40 /// digraph. 41 /// In a sense, a path can be treated as a list of arcs. 42 /// LEMON path types just store this list. As a consequence, they cannot 43 /// enumerate the nodes on the path directly and a zero length path 44 /// cannot store its source node. 45 /// 46 /// The arcs of a path should be stored in the order of their directions, 47 /// i.e. the target node of each arc should be the same as the source 48 /// node of the next arc. This consistency could be checked using 49 /// \ref checkPath(). 50 /// The source and target nodes of a (consistent) path can be obtained 51 /// using \ref pathSource() and \ref pathTarget(). 52 /// 53 /// A path can be constructed from another path of any type using the 54 /// copy constructor or the assignment operator. 55 /// 41 56 /// \tparam GR The digraph type in which the path is. 42 ///43 /// In a sense, the path can be treated as a list of arcs. The44 /// lemon path type stores just this list. As a consequence it45 /// cannot enumerate the nodes in the path and the zero length46 /// paths cannot store the source.47 ///48 57 template <typename GR> 49 58 class Path { … … 60 69 Path() {} 61 70 62 /// \brief Template co nstructor71 /// \brief Template copy constructor 63 72 template <typename CPath> 64 73 Path(const CPath& cpath) {} 65 74 66 /// \brief Template assigment 75 /// \brief Template assigment operator 67 76 template <typename CPath> 68 77 Path& operator=(const CPath& cpath) { … … 71 80 } 72 81 73 /// Length of the path ie. the number of arcs in the path.82 /// Length of the path, i.e. the number of arcs on the path. 74 83 int length() const { return 0;} 75 84 … … 80 89 void clear() {} 81 90 82 /// \brief LEMON style iterator for path arcs91 /// \brief LEMON style iterator for enumerating the arcs of a path. 83 92 /// 84 /// This class is used to iterate on the arcs of the paths.93 /// LEMON style iterator class for enumerating the arcs of a path. 85 94 class ArcIt { 86 95 public: … … 89 98 /// Invalid constructor 90 99 ArcIt(Invalid) {} 91 /// Constructor for first arc100 /// Sets the iterator to the first arc of the given path 92 101 ArcIt(const Path &) {} 93 102 94 /// Conversion to Arc103 /// Conversion to \c Arc 95 104 operator Arc() const { return INVALID; } 96 105 … … 193 202 /// 194 203 /// A skeleton structure for path dumpers. The path dumpers are 195 /// the generalization of the paths. The path dumpers can 196 /// enumerate the arcs of the path wheter in forward or in 197 /// backward order. In most time these classes are not used 198 /// directly rather it used to assign a dumped class to a real 199 /// path type. 204 /// the generalization of the paths, they can enumerate the arcs 205 /// of the path either in forward or in backward order. 206 /// These classes are typically not used directly, they are rather 207 /// used to be assigned to a real path type. 200 208 /// 201 209 /// The main purpose of this concept is that the shortest path 202 /// algorithms can enumerate easily the arcs in reverse order. 203 /// If we would like to give back a real path from these 204 /// algorithms then we should create a temporarly path object. In 205 /// LEMON such algorithms gives back a path dumper what can 206 /// assigned to a real path and the dumpers can be implemented as 210 /// algorithms can enumerate the arcs easily in reverse order. 211 /// In LEMON, such algorithms give back a (reverse) path dumper that 212 /// can be assigned to a real path. The dumpers can be implemented as 207 213 /// an adaptor class to the predecessor map. 208 214 /// 209 215 /// \tparam GR The digraph type in which the path is. 210 ///211 /// The paths can be constructed from any path type by a212 /// template constructor or a template assignment operator.213 216 template <typename GR> 214 217 class PathDumper { … … 220 223 typedef typename Digraph::Arc Arc; 221 224 222 /// Length of the path ie. the number of arcs in the path.225 /// Length of the path, i.e. the number of arcs on the path. 223 226 int length() const { return 0;} 224 227 … … 228 231 /// \brief Forward or reverse dumping 229 232 /// 230 /// If the RevPathTag is defined and true then reverse dumping 231 /// is provided in the path dumper. In this case instead of the 232 /// ArcIt the RevArcIt iterator should be implemented in the 233 /// dumper. 233 /// If this tag is defined to be \c True, then reverse dumping 234 /// is provided in the path dumper. In this case, \c RevArcIt 235 /// iterator should be implemented instead of \c ArcIt iterator. 234 236 typedef False RevPathTag; 235 237 236 /// \brief LEMON style iterator for path arcs238 /// \brief LEMON style iterator for enumerating the arcs of a path. 237 239 /// 238 /// This class is used to iterate on the arcs of the paths.240 /// LEMON style iterator class for enumerating the arcs of a path. 239 241 class ArcIt { 240 242 public: … … 243 245 /// Invalid constructor 244 246 ArcIt(Invalid) {} 245 /// Constructor for first arc247 /// Sets the iterator to the first arc of the given path 246 248 ArcIt(const PathDumper&) {} 247 249 248 /// Conversion to Arc250 /// Conversion to \c Arc 249 251 operator Arc() const { return INVALID; } 250 252 … … 261 263 }; 262 264 263 /// \brief LEMON style iterator for path arcs 265 /// \brief LEMON style iterator for enumerating the arcs of a path 266 /// in reverse direction. 264 267 /// 265 /// This class is used to iterate on the arcs of the paths in266 /// reverse direction.268 /// LEMON style iterator class for enumerating the arcs of a path 269 /// in reverse direction. 267 270 class RevArcIt { 268 271 public: … … 271 274 /// Invalid constructor 272 275 RevArcIt(Invalid) {} 273 /// Constructor for first arc276 /// Sets the iterator to the last arc of the given path 274 277 RevArcIt(const PathDumper &) {} 275 278 276 /// Conversion to Arc279 /// Conversion to \c Arc 277 280 operator Arc() const { return INVALID; } 278 281 -
lemon/counter.h
r463 r833 213 213 /// 'Do nothing' version of Counter. 214 214 215 /// This class can be used in the same way as \ref Counter howeverit215 /// This class can be used in the same way as \ref Counter, but it 216 216 /// does not count at all and does not print report on destruction. 217 217 /// -
lemon/cplex.cc
r623 r793 112 112 } 113 113 114 int CplexBase::_addRow(Value lb, ExprIterator b, 115 ExprIterator e, Value ub) { 116 int i = CPXgetnumrows(cplexEnv(), _prob); 117 if (lb == -INF) { 118 const char s = 'L'; 119 CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0); 120 } else if (ub == INF) { 121 const char s = 'G'; 122 CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0); 123 } else if (lb == ub){ 124 const char s = 'E'; 125 CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0); 126 } else { 127 const char s = 'R'; 128 double len = ub - lb; 129 CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0); 130 } 131 132 std::vector<int> indices; 133 std::vector<int> rowlist; 134 std::vector<Value> values; 135 136 for(ExprIterator it=b; it!=e; ++it) { 137 indices.push_back(it->first); 138 values.push_back(it->second); 139 rowlist.push_back(i); 140 } 141 142 CPXchgcoeflist(cplexEnv(), _prob, values.size(), 143 &rowlist.front(), &indices.front(), &values.front()); 144 145 return i; 146 } 114 147 115 148 void CplexBase::_eraseCol(int i) { -
lemon/cplex.h
r623 r793 94 94 virtual int _addCol(); 95 95 virtual int _addRow(); 96 virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); 96 97 97 98 virtual void _eraseCol(int i); -
lemon/dfs.h
r631 r891 48 48 ///The type of the map that stores the predecessor 49 49 ///arcs of the %DFS 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 meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.85 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 86 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 87 ///Instantiates a \c ReachedMap. … … 97 98 98 99 ///The type of the map that stores the distances of the nodes. 99 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.100 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 100 101 typedef typename Digraph::template NodeMap<int> DistMap; 101 102 ///Instantiates a \c DistMap. … … 121 122 ///\tparam GR The type of the digraph the algorithm runs on. 122 123 ///The default type is \ref ListDigraph. 124 ///\tparam TR The traits class that defines various types used by the 125 ///algorithm. By default, it is \ref DfsDefaultTraits 126 ///"DfsDefaultTraits<GR>". 127 ///In most cases, this parameter should not be set directly, 128 ///consider to use the named template parameters instead. 123 129 #ifdef DOXYGEN 124 130 template <typename GR, … … 225 231 ///\ref named-templ-param "Named parameter" for setting 226 232 ///\c PredMap type. 227 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.233 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 228 234 template <class T> 229 235 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > { … … 245 251 ///\ref named-templ-param "Named parameter" for setting 246 252 ///\c DistMap type. 247 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.253 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 248 254 template <class T> 249 255 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > { … … 265 271 ///\ref named-templ-param "Named parameter" for setting 266 272 ///\c ReachedMap type. 267 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.273 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 268 274 template <class T> 269 275 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { … … 285 291 ///\ref named-templ-param "Named parameter" for setting 286 292 ///\c ProcessedMap type. 287 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.293 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 288 294 template <class T> 289 295 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { … … 412 418 ///The simplest way to execute the DFS algorithm is to use one of the 413 419 ///member functions called \ref run(Node) "run()".\n 414 ///If you need more control on the execution, firstyou have to call415 ///\ref init() , then you can add a source node with \ref addSource()420 ///If you need better control on the execution, you have to call 421 ///\ref init() first, then you can add a source node with \ref addSource() 416 422 ///and perform the actual computation with \ref start(). 417 423 ///This procedure can be repeated if there are nodes that have not … … 633 639 ///Runs the algorithm to visit all nodes in the digraph. 634 640 635 ///This method runs the %DFS algorithm in order to compute the 636 ///%DFS path to each node. 637 /// 638 ///The algorithm computes 639 ///- the %DFS tree (forest), 640 ///- the distance of each node from the root(s) in the %DFS tree. 641 ///This method runs the %DFS algorithm in order to visit all nodes 642 ///in the digraph. 641 643 /// 642 644 ///\note <tt>d.run()</tt> is just a shortcut of the following code. … … 670 672 ///@{ 671 673 672 ///The DFS path to anode.673 674 ///Returns the DFS path to a node.674 ///The DFS path to the given node. 675 676 ///Returns the DFS path to the given node from the root(s). 675 677 /// 676 678 ///\warning \c t should be reached from the root(s). … … 680 682 Path path(Node t) const { return Path(*G, *_pred, t); } 681 683 682 ///The distance of anode from the root(s).683 684 ///Returns the distance of anode from the root(s).684 ///The distance of the given node from the root(s). 685 686 ///Returns the distance of the given node from the root(s). 685 687 /// 686 688 ///\warning If node \c v is not reached from the root(s), then … … 691 693 int dist(Node v) const { return (*_dist)[v]; } 692 694 693 ///Returns the 'previous arc' of the %DFS tree for anode.695 ///Returns the 'previous arc' of the %DFS tree for the given node. 694 696 695 697 ///This function returns the 'previous arc' of the %DFS tree for the … … 699 701 /// 700 702 ///The %DFS tree used here is equal to the %DFS tree used in 701 ///\ref predNode() .703 ///\ref predNode() and \ref predMap(). 702 704 /// 703 705 ///\pre Either \ref run(Node) "run()" or \ref init() … … 705 707 Arc predArc(Node v) const { return (*_pred)[v];} 706 708 707 ///Returns the 'previous node' of the %DFS tree .709 ///Returns the 'previous node' of the %DFS tree for the given node. 708 710 709 711 ///This function returns the 'previous node' of the %DFS 710 712 ///tree for the node \c v, i.e. it returns the last but one node 711 /// froma %DFS path from a root to \c v. It is \c INVALID713 ///of a %DFS path from a root to \c v. It is \c INVALID 712 714 ///if \c v is not reached from the root(s) or if \c v is a root. 713 715 /// 714 716 ///The %DFS tree used here is equal to the %DFS tree used in 715 ///\ref predArc() .717 ///\ref predArc() and \ref predMap(). 716 718 /// 717 719 ///\pre Either \ref run(Node) "run()" or \ref init() … … 734 736 /// 735 737 ///Returns a const reference to the node map that stores the predecessor 736 ///arcs, which form the DFS tree .738 ///arcs, which form the DFS tree (forest). 737 739 /// 738 740 ///\pre Either \ref run(Node) "run()" or \ref init() … … 740 742 const PredMap &predMap() const { return *_pred;} 741 743 742 ///Checks if anode is reached from the root(s).744 ///Checks if the given node. node is reached from the root(s). 743 745 744 746 ///Returns \c true if \c v is reached from the root(s). … … 766 768 ///The type of the map that stores the predecessor 767 769 ///arcs of the %DFS paths. 768 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.770 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 769 771 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 770 772 ///Instantiates a PredMap. … … 781 783 782 784 ///The type of the map that indicates which nodes are processed. 783 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.784 ///By default it is a NullMap.785 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 786 ///By default, it is a NullMap. 785 787 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 786 788 ///Instantiates a ProcessedMap. … … 801 803 802 804 ///The type of the map that indicates which nodes are reached. 803 ///It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.805 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 804 806 typedef typename Digraph::template NodeMap<bool> ReachedMap; 805 807 ///Instantiates a ReachedMap. … … 816 818 817 819 ///The type of the map that stores the distances of the nodes. 818 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.820 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 819 821 typedef typename Digraph::template NodeMap<int> DistMap; 820 822 ///Instantiates a DistMap. … … 831 833 832 834 ///The type of the DFS paths. 833 ///It must meetthe \ref concepts::Path "Path" concept.835 ///It must conform to the \ref concepts::Path "Path" concept. 834 836 typedef lemon::Path<Digraph> Path; 835 837 }; … … 837 839 /// Default traits class used by DfsWizard 838 840 839 /// To make it easier to use Dfs algorithm 840 /// we have created a wizard class. 841 /// This \ref DfsWizard class needs default traits, 842 /// as well as the \ref Dfs class. 843 /// The \ref DfsWizardBase is a class to be the default traits of the 844 /// \ref DfsWizard class. 841 /// Default traits class used by DfsWizard. 842 /// \tparam GR The type of the digraph. 845 843 template<class GR> 846 844 class DfsWizardBase : public DfsWizardDefaultTraits<GR> … … 870 868 /// Constructor. 871 869 872 /// This constructor does not require parameters, thereforeit initiates870 /// This constructor does not require parameters, it initiates 873 871 /// all of the attributes to \c 0. 874 872 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 895 893 /// This class should only be used through the \ref dfs() function, 896 894 /// which makes it easier to use the algorithm. 895 /// 896 /// \tparam TR The traits class that defines various types used by the 897 /// algorithm. 897 898 template<class TR> 898 899 class DfsWizard : public TR … … 900 901 typedef TR Base; 901 902 902 ///The type of the digraph the algorithm runs on.903 903 typedef typename TR::Digraph Digraph; 904 904 … … 908 908 typedef typename Digraph::OutArcIt OutArcIt; 909 909 910 ///\brief The type of the map that stores the predecessor911 ///arcs of the DFS paths.912 910 typedef typename TR::PredMap PredMap; 913 ///\brief The type of the map that stores the distances of the nodes.914 911 typedef typename TR::DistMap DistMap; 915 ///\brief The type of the map that indicates which nodes are reached.916 912 typedef typename TR::ReachedMap ReachedMap; 917 ///\brief The type of the map that indicates which nodes are processed.918 913 typedef typename TR::ProcessedMap ProcessedMap; 919 ///The type of the DFS paths920 914 typedef typename TR::Path Path; 921 915 … … 987 981 ///Runs DFS algorithm to visit all nodes in the digraph. 988 982 989 ///This method runs DFS algorithm in order to compute990 /// the DFS path to each node.983 ///This method runs DFS algorithm in order to visit all nodes 984 ///in the digraph. 991 985 void run() 992 986 { … … 1000 994 SetPredMapBase(const TR &b) : TR(b) {} 1001 995 }; 1002 ///\brief \ref named-func-param "Named parameter" 1003 ///for setting PredMap object. 1004 /// 1005 ///\ref named-func-param "Named parameter" 1006 ///for setting PredMap object. 996 997 ///\brief \ref named-templ-param "Named parameter" for setting 998 ///the predecessor map. 999 /// 1000 ///\ref named-templ-param "Named parameter" function for setting 1001 ///the map that stores the predecessor arcs of the nodes. 1007 1002 template<class T> 1008 1003 DfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1018 1013 SetReachedMapBase(const TR &b) : TR(b) {} 1019 1014 }; 1020 ///\brief \ref named-func-param "Named parameter" 1021 ///for setting ReachedMap object. 1022 /// 1023 /// \ref named-func-param "Named parameter" 1024 ///for setting ReachedMap object. 1015 1016 ///\brief \ref named-templ-param "Named parameter" for setting 1017 ///the reached map. 1018 /// 1019 ///\ref named-templ-param "Named parameter" function for setting 1020 ///the map that indicates which nodes are reached. 1025 1021 template<class T> 1026 1022 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1036 1032 SetDistMapBase(const TR &b) : TR(b) {} 1037 1033 }; 1038 ///\brief \ref named-func-param "Named parameter" 1039 ///for setting DistMap object. 1040 /// 1041 /// \ref named-func-param "Named parameter" 1042 ///for setting DistMap object. 1034 1035 ///\brief \ref named-templ-param "Named parameter" for setting 1036 ///the distance map. 1037 /// 1038 ///\ref named-templ-param "Named parameter" function for setting 1039 ///the map that stores the distances of the nodes calculated 1040 ///by the algorithm. 1043 1041 template<class T> 1044 1042 DfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1054 1052 SetProcessedMapBase(const TR &b) : TR(b) {} 1055 1053 }; 1056 ///\brief \ref named-func-param "Named parameter" 1057 ///for setting ProcessedMap object. 1058 /// 1059 /// \ref named-func-param "Named parameter" 1060 ///for setting ProcessedMap object. 1054 1055 ///\brief \ref named-func-param "Named parameter" for setting 1056 ///the processed map. 1057 /// 1058 ///\ref named-templ-param "Named parameter" function for setting 1059 ///the map that indicates which nodes are processed. 1061 1060 template<class T> 1062 1061 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1209 1208 /// 1210 1209 /// The type of the map that indicates which nodes are reached. 1211 /// It must meetthe \ref concepts::ReadWriteMap "ReadWriteMap" concept.1210 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1212 1211 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1213 1212 … … 1247 1246 /// does not observe the DFS events. If you want to observe the DFS 1248 1247 /// events, you should implement your own visitor class. 1249 /// \tparam TR T raits class to set various datatypes used by the1250 /// algorithm. The default traits class is1251 /// \ref DfsVisitDefaultTraits"DfsVisitDefaultTraits<GR>".1252 /// See \ref DfsVisitDefaultTraits for the documentation of1253 /// a DFS visit traits class.1248 /// \tparam TR The traits class that defines various types used by the 1249 /// algorithm. By default, it is \ref DfsVisitDefaultTraits 1250 /// "DfsVisitDefaultTraits<GR>". 1251 /// In most cases, this parameter should not be set directly, 1252 /// consider to use the named template parameters instead. 1254 1253 #ifdef DOXYGEN 1255 1254 template <typename GR, typename VS, typename TR> … … 1370 1369 /// The simplest way to execute the DFS algorithm is to use one of the 1371 1370 /// member functions called \ref run(Node) "run()".\n 1372 /// If you need more control on the execution, firstyou have to call1373 /// \ref init() , then you can add a source node with \ref addSource()1371 /// If you need better control on the execution, you have to call 1372 /// \ref init() first, then you can add a source node with \ref addSource() 1374 1373 /// and perform the actual computation with \ref start(). 1375 1374 /// This procedure can be repeated if there are nodes that have not … … 1584 1583 /// \brief Runs the algorithm to visit all nodes in the digraph. 1585 1584 1586 /// This method runs the %DFS algorithm in order to 1587 /// compute the %DFS path to each node. 1588 /// 1589 /// The algorithm computes 1590 /// - the %DFS tree (forest), 1591 /// - the distance of each node from the root(s) in the %DFS tree. 1585 /// This method runs the %DFS algorithm in order to visit all nodes 1586 /// in the digraph. 1592 1587 /// 1593 1588 /// \note <tt>d.run()</tt> is just a shortcut of the following code. … … 1621 1616 ///@{ 1622 1617 1623 /// \brief Checks if anode is reached from the root(s).1618 /// \brief Checks if the given node is reached from the root(s). 1624 1619 /// 1625 1620 /// Returns \c true if \c v is reached from the root(s). -
lemon/dijkstra.h
r631 r891 71 71 72 72 ///The type of the map that stores the arc lengths. 73 ///It must meetthe \ref concepts::ReadMap "ReadMap" concept.73 ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. 74 74 typedef LEN LengthMap; 75 ///The type of the length of the arcs.75 ///The type of the arc lengths. 76 76 typedef typename LEN::Value Value; 77 77 … … 117 117 ///The type of the map that stores the predecessor 118 118 ///arcs of the shortest paths. 119 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.119 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 120 120 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 121 121 ///Instantiates a \c PredMap. … … 132 132 133 133 ///The type of the map that indicates which nodes are processed. 134 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.135 ///By default it is a NullMap.134 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 135 ///By default, it is a NullMap. 136 136 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 137 137 ///Instantiates a \c ProcessedMap. … … 152 152 153 153 ///The type of the map that stores the distances of the nodes. 154 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.154 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 155 155 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap; 156 156 ///Instantiates a \c DistMap. … … 169 169 /// \ingroup shortest_path 170 170 ///This class provides an efficient implementation of the %Dijkstra algorithm. 171 /// 172 ///The %Dijkstra algorithm solves the single-source shortest path problem 173 ///when all arc lengths are non-negative. If there are negative lengths, 174 ///the BellmanFord algorithm should be used instead. 171 175 /// 172 176 ///The arc lengths are passed to the algorithm using a … … 189 193 ///it is necessary. The default map type is \ref 190 194 ///concepts::Digraph::ArcMap "GR::ArcMap<int>". 195 ///\tparam TR The traits class that defines various types used by the 196 ///algorithm. By default, it is \ref DijkstraDefaultTraits 197 ///"DijkstraDefaultTraits<GR, LEN>". 198 ///In most cases, this parameter should not be set directly, 199 ///consider to use the named template parameters instead. 191 200 #ifdef DOXYGEN 192 201 template <typename GR, typename LEN, typename TR> … … 202 211 typedef typename TR::Digraph Digraph; 203 212 204 ///The type of the length of the arcs.205 typedef typename TR:: LengthMap::Value Value;213 ///The type of the arc lengths. 214 typedef typename TR::Value Value; 206 215 ///The type of the map that stores the arc lengths. 207 216 typedef typename TR::LengthMap LengthMap; … … 305 314 ///\ref named-templ-param "Named parameter" for setting 306 315 ///\c PredMap type. 307 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.316 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 308 317 template <class T> 309 318 struct SetPredMap … … 326 335 ///\ref named-templ-param "Named parameter" for setting 327 336 ///\c DistMap type. 328 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.337 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 329 338 template <class T> 330 339 struct SetDistMap … … 347 356 ///\ref named-templ-param "Named parameter" for setting 348 357 ///\c ProcessedMap type. 349 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.358 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 350 359 template <class T> 351 360 struct SetProcessedMap … … 423 432 ///passed to the constructor of the cross reference and the cross 424 433 ///reference should be passed to the constructor of the heap). 425 ///However external heap and cross reference objects could also be434 ///However, external heap and cross reference objects could also be 426 435 ///passed to the algorithm using the \ref heap() function before 427 436 ///calling \ref run(Node) "run()" or \ref init(). … … 444 453 ///\ref named-templ-param "Named parameter" for setting 445 454 ///\c OperationTraits type. 455 /// For more information, see \ref DijkstraDefaultOperationTraits. 446 456 template <class T> 447 457 struct SetOperationTraits … … 585 595 ///The simplest way to execute the %Dijkstra algorithm is to use 586 596 ///one of the member functions called \ref run(Node) "run()".\n 587 ///If you need more control on the execution, firstyou have to call588 ///\ref init() , then you can add several source nodes with597 ///If you need better control on the execution, you have to call 598 ///\ref init() first, then you can add several source nodes with 589 599 ///\ref addSource(). Finally the actual path computation can be 590 600 ///performed with one of the \ref start() functions. … … 802 812 ///The results of the %Dijkstra algorithm can be obtained using these 803 813 ///functions.\n 804 ///Either \ref run(Node) "run()" or \ref start() should be called814 ///Either \ref run(Node) "run()" or \ref init() should be called 805 815 ///before using them. 806 816 807 817 ///@{ 808 818 809 ///The shortest path to anode.810 811 ///Returns the shortest path to a node.819 ///The shortest path to the given node. 820 821 ///Returns the shortest path to the given node from the root(s). 812 822 /// 813 823 ///\warning \c t should be reached from the root(s). … … 817 827 Path path(Node t) const { return Path(*G, *_pred, t); } 818 828 819 ///The distance of anode from the root(s).820 821 ///Returns the distance of anode from the root(s).829 ///The distance of the given node from the root(s). 830 831 ///Returns the distance of the given node from the root(s). 822 832 /// 823 833 ///\warning If node \c v is not reached from the root(s), then … … 828 838 Value dist(Node v) const { return (*_dist)[v]; } 829 839 830 ///Returns the 'previous arc' of the shortest path tree for a node. 831 840 ///\brief Returns the 'previous arc' of the shortest path tree for 841 ///the given node. 842 /// 832 843 ///This function returns the 'previous arc' of the shortest path 833 844 ///tree for the node \c v, i.e. it returns the last arc of a … … 836 847 /// 837 848 ///The shortest path tree used here is equal to the shortest path 838 ///tree used in \ref predNode() .849 ///tree used in \ref predNode() and \ref predMap(). 839 850 /// 840 851 ///\pre Either \ref run(Node) "run()" or \ref init() … … 842 853 Arc predArc(Node v) const { return (*_pred)[v]; } 843 854 844 ///Returns the 'previous node' of the shortest path tree for a node. 845 855 ///\brief Returns the 'previous node' of the shortest path tree for 856 ///the given node. 857 /// 846 858 ///This function returns the 'previous node' of the shortest path 847 859 ///tree for the node \c v, i.e. it returns the last but one node 848 /// froma shortest path from a root to \c v. It is \c INVALID860 ///of a shortest path from a root to \c v. It is \c INVALID 849 861 ///if \c v is not reached from the root(s) or if \c v is a root. 850 862 /// 851 863 ///The shortest path tree used here is equal to the shortest path 852 ///tree used in \ref predArc() .864 ///tree used in \ref predArc() and \ref predMap(). 853 865 /// 854 866 ///\pre Either \ref run(Node) "run()" or \ref init() … … 871 883 /// 872 884 ///Returns a const reference to the node map that stores the predecessor 873 ///arcs, which form the shortest path tree .885 ///arcs, which form the shortest path tree (forest). 874 886 /// 875 887 ///\pre Either \ref run(Node) "run()" or \ref init() … … 877 889 const PredMap &predMap() const { return *_pred;} 878 890 879 ///Checks if anode is reached from the root(s).891 ///Checks if the given node is reached from the root(s). 880 892 881 893 ///Returns \c true if \c v is reached from the root(s). … … 896 908 Heap::POST_HEAP; } 897 909 898 ///The current distance of anode from the root(s).899 900 ///Returns the current distance of anode from the root(s).910 ///The current distance of the given node from the root(s). 911 912 ///Returns the current distance of the given node from the root(s). 901 913 ///It may be decreased in the following processes. 902 914 /// … … 925 937 926 938 ///The type of the map that stores the arc lengths. 927 ///It must meetthe \ref concepts::ReadMap "ReadMap" concept.939 ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. 928 940 typedef LEN LengthMap; 929 ///The type of the length of the arcs.941 ///The type of the arc lengths. 930 942 typedef typename LEN::Value Value; 931 943 … … 974 986 ///The type of the map that stores the predecessor 975 987 ///arcs of the shortest paths. 976 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.988 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 977 989 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 978 990 ///Instantiates a PredMap. … … 989 1001 990 1002 ///The type of the map that indicates which nodes are processed. 991 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.992 ///By default it is a NullMap.1003 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 1004 ///By default, it is a NullMap. 993 1005 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 994 1006 ///Instantiates a ProcessedMap. … … 1009 1021 1010 1022 ///The type of the map that stores the distances of the nodes. 1011 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.1023 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 1012 1024 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap; 1013 1025 ///Instantiates a DistMap. … … 1024 1036 1025 1037 ///The type of the shortest paths. 1026 ///It must meetthe \ref concepts::Path "Path" concept.1038 ///It must conform to the \ref concepts::Path "Path" concept. 1027 1039 typedef lemon::Path<Digraph> Path; 1028 1040 }; … … 1030 1042 /// Default traits class used by DijkstraWizard 1031 1043 1032 /// To make it easier to use Dijkstra algorithm 1033 /// we have created a wizard class. 1034 /// This \ref DijkstraWizard class needs default traits, 1035 /// as well as the \ref Dijkstra class. 1036 /// The \ref DijkstraWizardBase is a class to be the default traits of the 1037 /// \ref DijkstraWizard class. 1044 /// Default traits class used by DijkstraWizard. 1045 /// \tparam GR The type of the digraph. 1046 /// \tparam LEN The type of the length map. 1038 1047 template<typename GR, typename LEN> 1039 1048 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN> … … 1089 1098 /// This class should only be used through the \ref dijkstra() function, 1090 1099 /// which makes it easier to use the algorithm. 1100 /// 1101 /// \tparam TR The traits class that defines various types used by the 1102 /// algorithm. 1091 1103 template<class TR> 1092 1104 class DijkstraWizard : public TR … … 1094 1106 typedef TR Base; 1095 1107 1096 ///The type of the digraph the algorithm runs on.1097 1108 typedef typename TR::Digraph Digraph; 1098 1109 … … 1102 1113 typedef typename Digraph::OutArcIt OutArcIt; 1103 1114 1104 ///The type of the map that stores the arc lengths.1105 1115 typedef typename TR::LengthMap LengthMap; 1106 ///The type of the length of the arcs.1107 1116 typedef typename LengthMap::Value Value; 1108 ///\brief The type of the map that stores the predecessor1109 ///arcs of the shortest paths.1110 1117 typedef typename TR::PredMap PredMap; 1111 ///The type of the map that stores the distances of the nodes.1112 1118 typedef typename TR::DistMap DistMap; 1113 ///The type of the map that indicates which nodes are processed.1114 1119 typedef typename TR::ProcessedMap ProcessedMap; 1115 ///The type of the shortest paths1116 1120 typedef typename TR::Path Path; 1117 ///The heap type used by the dijkstra algorithm.1118 1121 typedef typename TR::Heap Heap; 1119 1122 … … 1187 1190 SetPredMapBase(const TR &b) : TR(b) {} 1188 1191 }; 1189 ///\brief \ref named-func-param "Named parameter" 1190 ///for setting PredMap object. 1191 /// 1192 ///\ref named-func-param "Named parameter" 1193 ///for setting PredMap object. 1192 1193 ///\brief \ref named-templ-param "Named parameter" for setting 1194 ///the predecessor map. 1195 /// 1196 ///\ref named-templ-param "Named parameter" function for setting 1197 ///the map that stores the predecessor arcs of the nodes. 1194 1198 template<class T> 1195 1199 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t) … … 1205 1209 SetDistMapBase(const TR &b) : TR(b) {} 1206 1210 }; 1207 ///\brief \ref named-func-param "Named parameter" 1208 ///for setting DistMap object. 1209 /// 1210 ///\ref named-func-param "Named parameter" 1211 ///for setting DistMap object. 1211 1212 ///\brief \ref named-templ-param "Named parameter" for setting 1213 ///the distance map. 1214 /// 1215 ///\ref named-templ-param "Named parameter" function for setting 1216 ///the map that stores the distances of the nodes calculated 1217 ///by the algorithm. 1212 1218 template<class T> 1213 1219 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t) … … 1223 1229 SetProcessedMapBase(const TR &b) : TR(b) {} 1224 1230 }; 1225 ///\brief \ref named-func-param "Named parameter" 1226 ///for setting ProcessedMap object. 1227 /// 1228 /// \ref named-func-param "Named parameter" 1229 ///for setting ProcessedMap object. 1231 1232 ///\brief \ref named-func-param "Named parameter" for setting 1233 ///the processed map. 1234 /// 1235 ///\ref named-templ-param "Named parameter" function for setting 1236 ///the map that indicates which nodes are processed. 1230 1237 template<class T> 1231 1238 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1240 1247 SetPathBase(const TR &b) : TR(b) {} 1241 1248 }; 1249 1242 1250 ///\brief \ref named-func-param "Named parameter" 1243 1251 ///for getting the shortest path to the target node. -
lemon/dim2.h
r463 r761 22 22 #include <iostream> 23 23 24 ///\ingroup misc24 ///\ingroup geomdat 25 25 ///\file 26 26 ///\brief A simple two dimensional vector and a bounding box implementation 27 ///28 /// The class \ref lemon::dim2::Point "dim2::Point" implements29 /// a two dimensional vector with the usual operations.30 ///31 /// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine32 /// the rectangular bounding box of a set of33 /// \ref lemon::dim2::Point "dim2::Point"'s.34 27 35 28 namespace lemon { … … 41 34 namespace dim2 { 42 35 43 /// \addtogroup misc36 /// \addtogroup geomdat 44 37 /// @{ 45 38 -
lemon/edge_set.h
r717 r834 256 256 /// all arcs incident to the given node is erased from the arc set. 257 257 /// 258 /// This class fully conforms to the \ref concepts::Digraph 259 /// "Digraph" concept. 260 /// It provides only linear time counting for nodes and arcs. 261 /// 258 262 /// \param GR The type of the graph which shares its node set with 259 263 /// this class. Its interface must conform to the 260 264 /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" 261 265 /// concept. 262 ///263 /// This class fully conforms to the \ref concepts::Digraph264 /// "Digraph" concept.265 266 template <typename GR> 266 267 class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > { … … 686 687 /// incident to the given node is erased from the arc set. 687 688 /// 689 /// This class fully conforms to the \ref concepts::Graph "Graph" 690 /// concept. 691 /// It provides only linear time counting for nodes, edges and arcs. 692 /// 688 693 /// \param GR The type of the graph which shares its node set 689 694 /// with this class. Its interface must conform to the 690 695 /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" 691 /// concept.692 ///693 /// This class fully conforms to the \ref concepts::Graph "Graph"694 696 /// concept. 695 697 template <typename GR> … … 868 870 } 869 871 870 void next(Arc& arc) const{872 static void next(Arc& arc) { 871 873 --arc.id; 872 874 } … … 955 957 /// arcs. Therefore the arcs cannot be erased from the arc sets. 956 958 /// 959 /// This class fully conforms to the \ref concepts::Digraph "Digraph" 960 /// concept. 961 /// It provides only linear time counting for nodes and arcs. 962 /// 957 963 /// \warning If a node is erased from the underlying graph and this 958 964 /// node is the source or target of one arc in the arc set, then 959 965 /// the arc set is invalidated, and it cannot be used anymore. The 960 966 /// validity can be checked with the \c valid() member function. 961 ///962 /// This class fully conforms to the \ref concepts::Digraph963 /// "Digraph" concept.964 967 template <typename GR> 965 968 class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > { … … 1174 1177 } 1175 1178 1176 void next(Arc& arc) const{1179 static void next(Arc& arc) { 1177 1180 --arc.id; 1178 1181 } … … 1182 1185 } 1183 1186 1184 void next(Edge& arc) const{1187 static void next(Edge& arc) { 1185 1188 --arc.id; 1186 1189 } … … 1305 1308 /// edges cannot be erased from the edge sets. 1306 1309 /// 1310 /// This class fully conforms to the \ref concepts::Graph "Graph" 1311 /// concept. 1312 /// It provides only linear time counting for nodes, edges and arcs. 1313 /// 1307 1314 /// \warning If a node is erased from the underlying graph and this 1308 1315 /// node is incident to one edge in the edge set, then the edge set 1309 1316 /// is invalidated, and it cannot be used anymore. The validity can 1310 1317 /// be checked with the \c valid() member function. 1311 ///1312 /// This class fully conforms to the \ref concepts::Graph1313 /// "Graph" concept.1314 1318 template <typename GR> 1315 1319 class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > { -
lemon/full_graph.h
r664 r834 25 25 ///\ingroup graphs 26 26 ///\file 27 ///\brief Full Graph and FullDigraph classes.27 ///\brief FullDigraph and FullGraph classes. 28 28 29 29 namespace lemon { … … 52 52 53 53 Node operator()(int ix) const { return Node(ix); } 54 int index(const Node& node) const{ return node._id; }54 static int index(const Node& node) { return node._id; } 55 55 56 56 Arc arc(const Node& s, const Node& t) const { … … 149 149 /// \ingroup graphs 150 150 /// 151 /// \brief A full digraph class. 152 /// 153 /// This is a simple and fast directed full graph implementation. 154 /// From each node go arcs to each node (including the source node), 155 /// therefore the number of the arcs in the digraph is the square of 156 /// the node number. This digraph type is completely static, so you 157 /// can neither add nor delete either arcs or nodes, and it needs 158 /// constant space in memory. 159 /// 160 /// This class fully conforms to the \ref concepts::Digraph 161 /// "Digraph concept". 162 /// 163 /// The \c FullDigraph and \c FullGraph classes are very similar, 151 /// \brief A directed full graph class. 152 /// 153 /// FullDigraph is a simple and fast implmenetation of directed full 154 /// (complete) graphs. It contains an arc from each node to each node 155 /// (including a loop for each node), therefore the number of arcs 156 /// is the square of the number of nodes. 157 /// This class is completely static and it needs constant memory space. 158 /// Thus you can neither add nor delete nodes or arcs, however 159 /// the structure can be resized using resize(). 160 /// 161 /// This type fully conforms to the \ref concepts::Digraph "Digraph concept". 162 /// Most of its member functions and nested classes are documented 163 /// only in the concept class. 164 /// 165 /// This class provides constant time counting for nodes and arcs. 166 /// 167 /// \note FullDigraph and FullGraph classes are very similar, 164 168 /// but there are two differences. While this class conforms only 165 /// to the \ref concepts::Digraph "Digraph" concept, the \cFullGraph166 /// c lass conforms to the \ref concepts::Graph "Graph" concept,167 /// moreover \c FullGraph does not contain a loop arcfor each168 /// node as \c FullDigraphdoes.169 /// to the \ref concepts::Digraph "Digraph" concept, FullGraph 170 /// conforms to the \ref concepts::Graph "Graph" concept, 171 /// moreover FullGraph does not contain a loop for each 172 /// node as this class does. 169 173 /// 170 174 /// \sa FullGraph … … 174 178 public: 175 179 176 /// \brief Constructor 180 /// \brief Default constructor. 181 /// 182 /// Default constructor. The number of nodes and arcs will be zero. 177 183 FullDigraph() { construct(0); } 178 184 … … 185 191 /// \brief Resizes the digraph 186 192 /// 187 /// Resizes the digraph. The function will fully destroyand188 /// rebuild the digraph. This cause that the maps of the digraph will193 /// This function resizes the digraph. It fully destroys and 194 /// rebuilds the structure, therefore the maps of the digraph will be 189 195 /// reallocated automatically and the previous values will be lost. 190 196 void resize(int n) { … … 198 204 /// \brief Returns the node with the given index. 199 205 /// 200 /// Returns the node with the given index. Since it is a static 201 /// digraph its nodes can be indexed with integers from the range 202 /// <tt>[0..nodeNum()-1]</tt>. 206 /// Returns the node with the given index. Since this structure is 207 /// completely static, the nodes can be indexed with integers from 208 /// the range <tt>[0..nodeNum()-1]</tt>. 209 /// The index of a node is the same as its ID. 203 210 /// \sa index() 204 211 Node operator()(int ix) const { return Parent::operator()(ix); } … … 206 213 /// \brief Returns the index of the given node. 207 214 /// 208 /// Returns the index of the given node. Since it is a static 209 /// digraph its nodes can be indexed with integers from the range 210 /// <tt>[0..nodeNum()-1]</tt>. 211 /// \sa operator() 212 int index(const Node& node) const { return Parent::index(node); } 215 /// Returns the index of the given node. Since this structure is 216 /// completely static, the nodes can be indexed with integers from 217 /// the range <tt>[0..nodeNum()-1]</tt>. 218 /// The index of a node is the same as its ID. 219 /// \sa operator()() 220 static int index(const Node& node) { return Parent::index(node); } 213 221 214 222 /// \brief Returns the arc connecting the given nodes. 215 223 /// 216 224 /// Returns the arc connecting the given nodes. 217 Arc arc( const Node& u, const Node&v) const {225 Arc arc(Node u, Node v) const { 218 226 return Parent::arc(u, v); 219 227 } … … 284 292 285 293 Node operator()(int ix) const { return Node(ix); } 286 int index(const Node& node) const{ return node._id; }294 static int index(const Node& node) { return node._id; } 287 295 288 296 Edge edge(const Node& u, const Node& v) const { … … 521 529 /// \brief An undirected full graph class. 522 530 /// 523 /// This is a simple and fast undirected full graph 524 /// implementation. From each node go edge to each other node, 525 /// therefore the number of edges in the graph is \f$n(n-1)/2\f$. 526 /// This graph type is completely static, so you can neither 527 /// add nor delete either edges or nodes, and it needs constant 528 /// space in memory. 529 /// 530 /// This class fully conforms to the \ref concepts::Graph "Graph concept". 531 /// 532 /// The \c FullGraph and \c FullDigraph classes are very similar, 533 /// but there are two differences. While the \c FullDigraph class 531 /// FullGraph is a simple and fast implmenetation of undirected full 532 /// (complete) graphs. It contains an edge between every distinct pair 533 /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>. 534 /// This class is completely static and it needs constant memory space. 535 /// Thus you can neither add nor delete nodes or edges, however 536 /// the structure can be resized using resize(). 537 /// 538 /// This type fully conforms to the \ref concepts::Graph "Graph concept". 539 /// Most of its member functions and nested classes are documented 540 /// only in the concept class. 541 /// 542 /// This class provides constant time counting for nodes, edges and arcs. 543 /// 544 /// \note FullDigraph and FullGraph classes are very similar, 545 /// but there are two differences. While FullDigraph 534 546 /// conforms only to the \ref concepts::Digraph "Digraph" concept, 535 547 /// this class conforms to the \ref concepts::Graph "Graph" concept, 536 /// moreover \c FullGraph does not contain a loop arcfor each537 /// node as \cFullDigraph does.548 /// moreover this class does not contain a loop for each 549 /// node as FullDigraph does. 538 550 /// 539 551 /// \sa FullDigraph … … 543 555 public: 544 556 545 /// \brief Constructor 557 /// \brief Default constructor. 558 /// 559 /// Default constructor. The number of nodes and edges will be zero. 546 560 FullGraph() { construct(0); } 547 561 … … 554 568 /// \brief Resizes the graph 555 569 /// 556 /// Resizes the graph. The function will fully destroyand557 /// rebuild the graph. This cause that the maps of the graph will570 /// This function resizes the graph. It fully destroys and 571 /// rebuilds the structure, therefore the maps of the graph will be 558 572 /// reallocated automatically and the previous values will be lost. 559 573 void resize(int n) { … … 569 583 /// \brief Returns the node with the given index. 570 584 /// 571 /// Returns the node with the given index. Since it is a static 572 /// graph its nodes can be indexed with integers from the range 573 /// <tt>[0..nodeNum()-1]</tt>. 585 /// Returns the node with the given index. Since this structure is 586 /// completely static, the nodes can be indexed with integers from 587 /// the range <tt>[0..nodeNum()-1]</tt>. 588 /// The index of a node is the same as its ID. 574 589 /// \sa index() 575 590 Node operator()(int ix) const { return Parent::operator()(ix); } … … 577 592 /// \brief Returns the index of the given node. 578 593 /// 579 /// Returns the index of the given node. Since it is a static 580 /// graph its nodes can be indexed with integers from the range 581 /// <tt>[0..nodeNum()-1]</tt>. 582 /// \sa operator() 583 int index(const Node& node) const { return Parent::index(node); } 594 /// Returns the index of the given node. Since this structure is 595 /// completely static, the nodes can be indexed with integers from 596 /// the range <tt>[0..nodeNum()-1]</tt>. 597 /// The index of a node is the same as its ID. 598 /// \sa operator()() 599 static int index(const Node& node) { return Parent::index(node); } 584 600 585 601 /// \brief Returns the arc connecting the given nodes. 586 602 /// 587 603 /// Returns the arc connecting the given nodes. 588 Arc arc( const Node& s, const Node&t) const {604 Arc arc(Node s, Node t) const { 589 605 return Parent::arc(s, t); 590 606 } 591 607 592 /// \brief Returns the edge connect sthe given nodes.593 /// 594 /// Returns the edge connect sthe given nodes.595 Edge edge( const Node& u, const Node&v) const {608 /// \brief Returns the edge connecting the given nodes. 609 /// 610 /// Returns the edge connecting the given nodes. 611 Edge edge(Node u, Node v) const { 596 612 return Parent::edge(u, v); 597 613 } -
lemon/glpk.cc
r623 r793 57 57 int i = glp_add_rows(lp, 1); 58 58 glp_set_row_bnds(lp, i, GLP_FR, 0.0, 0.0); 59 return i; 60 } 61 62 int GlpkBase::_addRow(Value lo, ExprIterator b, 63 ExprIterator e, Value up) { 64 int i = glp_add_rows(lp, 1); 65 66 if (lo == -INF) { 67 if (up == INF) { 68 glp_set_row_bnds(lp, i, GLP_FR, lo, up); 69 } else { 70 glp_set_row_bnds(lp, i, GLP_UP, lo, up); 71 } 72 } else { 73 if (up == INF) { 74 glp_set_row_bnds(lp, i, GLP_LO, lo, up); 75 } else if (lo != up) { 76 glp_set_row_bnds(lp, i, GLP_DB, lo, up); 77 } else { 78 glp_set_row_bnds(lp, i, GLP_FX, lo, up); 79 } 80 } 81 82 std::vector<int> indexes; 83 std::vector<Value> values; 84 85 indexes.push_back(0); 86 values.push_back(0); 87 88 for(ExprIterator it = b; it != e; ++it) { 89 indexes.push_back(it->first); 90 values.push_back(it->second); 91 } 92 93 glp_set_mat_row(lp, i, values.size() - 1, 94 &indexes.front(), &values.front()); 59 95 return i; 60 96 } -
lemon/glpk.h
r697 r902 26 26 #include <lemon/lp_base.h> 27 27 28 // forward declaration29 #if !defined _GLP_PROB && !defined GLP_PROB30 #define _GLP_PROB31 #define GLP_PROB32 typedef struct { double _opaque_prob; } glp_prob;33 /* LP/MIP problem object */34 #endif35 36 28 namespace lemon { 37 29 30 namespace _solver_bits { 31 class VoidPtr { 32 private: 33 void *_ptr; 34 public: 35 VoidPtr() : _ptr(0) {} 36 37 template <typename T> 38 VoidPtr(T* ptr) : _ptr(reinterpret_cast<void*>(ptr)) {} 39 40 template <typename T> 41 VoidPtr& operator=(T* ptr) { 42 _ptr = reinterpret_cast<void*>(ptr); 43 return *this; 44 } 45 46 template <typename T> 47 operator T*() const { return reinterpret_cast<T*>(_ptr); } 48 }; 49 } 38 50 39 51 /// \brief Base interface for the GLPK LP and MIP solver … … 44 56 protected: 45 57 46 typedef glp_prob LPX; 47 glp_prob* lp; 58 _solver_bits::VoidPtr lp; 48 59 49 60 GlpkBase(); … … 55 66 virtual int _addCol(); 56 67 virtual int _addRow(); 68 virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); 57 69 58 70 virtual void _eraseCol(int i); … … 123 135 124 136 ///Pointer to the underlying GLPK data structure. 125 LPX *lpx() {return lp;}137 _solver_bits::VoidPtr lpx() {return lp;} 126 138 ///Const pointer to the underlying GLPK data structure. 127 const LPX *lpx() const {return lp;}139 _solver_bits::VoidPtr lpx() const {return lp;} 128 140 129 141 ///Returns the constraint identifier understood by GLPK. -
lemon/gomory_hu.h
r643 r833 295 295 /// \pre \ref run() must be called before using this function. 296 296 template <typename CutMap> 297 Value minCutMap(const Node& s, ///<297 Value minCutMap(const Node& s, 298 298 const Node& t, 299 ///<300 299 CutMap& cutMap 301 ///<302 300 ) const { 303 301 Node sn = s, tn = t; … … 360 358 /// \c t. 361 359 /// \code 362 /// Gomor uHu<Graph> gom(g, capacities);360 /// GomoryHu<Graph> gom(g, capacities); 363 361 /// gom.run(); 364 362 /// int cnt=0; 365 /// for(Gomor uHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;363 /// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt; 366 364 /// \endcode 367 365 class MinCutNodeIt … … 395 393 /// \endcode 396 394 /// does not necessarily give the same set of nodes. 397 /// However it is ensured that395 /// However, it is ensured that 398 396 /// \code 399 397 /// MinCutNodeIt(gomory, s, t, true); … … 457 455 /// \c t. 458 456 /// \code 459 /// Gomor uHu<Graph> gom(g, capacities);457 /// GomoryHu<Graph> gom(g, capacities); 460 458 /// gom.run(); 461 459 /// int value=0; 462 /// for(Gomor uHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)460 /// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) 463 461 /// value+=capacities[e]; 464 462 /// \endcode -
lemon/graph_to_eps.h
r664 r909 143 143 ///\param gr Reference to the graph to be printed. 144 144 ///\param ost Reference to the output stream. 145 ///By default it is <tt>std::cout</tt>.145 ///By default, it is <tt>std::cout</tt>. 146 146 ///\param pros If it is \c true, then the \c ostream referenced by \c os 147 147 ///will be explicitly deallocated by the destructor. … … 513 513 ///Turn on/off pre-scaling 514 514 515 ///By default graphToEps() rescales the whole image in order to avoid515 ///By default, graphToEps() rescales the whole image in order to avoid 516 516 ///very big or very small bounding boxes. 517 517 /// … … 685 685 #else 686 686 os << bits::getWinFormattedDate(); 687 os << std::endl; 687 688 #endif 688 689 } 689 os << std::endl;690 690 691 691 if (_autoArcWidthScale) { … … 1115 1115 ///\param g Reference to the graph to be printed. 1116 1116 ///\param os Reference to the output stream. 1117 ///By default it is <tt>std::cout</tt>.1117 ///By default, it is <tt>std::cout</tt>. 1118 1118 /// 1119 1119 ///This function also has a lot of … … 1127 1127 ///\endcode 1128 1128 /// 1129 ///For more detailed examples see the \ref graph_to_eps_demo.cc demo file.1129 ///For more detailed examples, see the \ref graph_to_eps_demo.cc demo file. 1130 1130 /// 1131 1131 ///\warning Don't forget to put the \ref GraphToEps::run() "run()" -
lemon/grid_graph.h
r664 r834 471 471 /// \brief Grid graph class 472 472 /// 473 /// This classimplements a special graph type. The nodes of the474 /// graph can be indexed by two integer \c (i,j) valuewhere \c i is475 /// in the \c [0..width()-1] range and j is in the \c476 /// [0..height()-1] range.Two nodes are connected in the graph if477 /// the ind exes differ exactly on one position and exactly one is478 /// the difference. The nodes of the graph can be indexed by position479 /// with the \c operator()() function. The positions of the nodes can be480 /// get with\c pos(), \c col() and \c row() members. The outgoing473 /// GridGraph implements a special graph type. The nodes of the 474 /// graph can be indexed by two integer values \c (i,j) where \c i is 475 /// in the range <tt>[0..width()-1]</tt> and j is in the range 476 /// <tt>[0..height()-1]</tt>. Two nodes are connected in the graph if 477 /// the indices differ exactly on one position and the difference is 478 /// also exactly one. The nodes of the graph can be obtained by position 479 /// using the \c operator()() function and the indices of the nodes can 480 /// be obtained using \c pos(), \c col() and \c row() members. The outgoing 481 481 /// arcs can be retrieved with the \c right(), \c up(), \c left() 482 482 /// and \c down() functions, where the bottom-left corner is the 483 483 /// origin. 484 /// 485 /// This class is completely static and it needs constant memory space. 486 /// Thus you can neither add nor delete nodes or edges, however 487 /// the structure can be resized using resize(). 484 488 /// 485 489 /// \image html grid_graph.png … … 497 501 ///\endcode 498 502 /// 499 /// This graph type fully conforms to the \ref concepts::Graph 500 /// "Graph concept". 503 /// This type fully conforms to the \ref concepts::Graph "Graph concept". 504 /// Most of its member functions and nested classes are documented 505 /// only in the concept class. 506 /// 507 /// This class provides constant time counting for nodes, edges and arcs. 501 508 class GridGraph : public ExtendedGridGraphBase { 502 509 typedef ExtendedGridGraphBase Parent; … … 504 511 public: 505 512 506 /// \brief Map to get the indices of the nodes as dim2::Point<int>. 507 /// 508 /// Map to get the indices of the nodes as dim2::Point<int>. 513 /// \brief Map to get the indices of the nodes as \ref dim2::Point 514 /// "dim2::Point<int>". 515 /// 516 /// Map to get the indices of the nodes as \ref dim2::Point 517 /// "dim2::Point<int>". 509 518 class IndexMap { 510 519 public: … … 515 524 516 525 /// \brief Constructor 517 ///518 /// Constructor519 526 IndexMap(const GridGraph& graph) : _graph(graph) {} 520 527 521 528 /// \brief The subscript operator 522 ///523 /// The subscript operator.524 529 Value operator[](Key key) const { 525 530 return _graph.pos(key); … … 541 546 542 547 /// \brief Constructor 543 ///544 /// Constructor545 548 ColMap(const GridGraph& graph) : _graph(graph) {} 546 549 547 550 /// \brief The subscript operator 548 ///549 /// The subscript operator.550 551 Value operator[](Key key) const { 551 552 return _graph.col(key); … … 567 568 568 569 /// \brief Constructor 569 ///570 /// Constructor571 570 RowMap(const GridGraph& graph) : _graph(graph) {} 572 571 573 572 /// \brief The subscript operator 574 ///575 /// The subscript operator.576 573 Value operator[](Key key) const { 577