COIN-OR::LEMON - Graph Library

Ignore:
Files:
26 deleted
113 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r944 r610  
    2323lemon/stamp-h2
    2424doc/Doxyfile
    25 doc/references.dox
    2625cmake/version.cmake
    2726.dirstamp
  • CMakeLists.txt

    r1110 r1053  
    115115SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
    116116
    117 INCLUDE(FindPythonInterp)
    118 
    119117ENABLE_TESTING()
    120118
  • INSTALL

    r890 r615  
    174174
    175175   Disable COIN-OR support.
    176 
    177 
    178 Makefile Variables
    179 ==================
    180 
    181 Some Makefile variables are reserved by the GNU Coding Standards for
    182 the use of the "user" - the person building the package. For instance,
    183 CXX and CXXFLAGS are such variables, and have the same meaning as
    184 explained in the previous section. These variables can be set on the
    185 command line when invoking `make' like this:
    186 `make [VARIABLE=VALUE]...'
    187 
    188 WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us
    189 to hold several compiler flags related to warnings. Its default value
    190 can be overridden when invoking `make'. For example to disable all
    191 warning flags use `make WARNINGCXXFLAGS='.
    192 
    193 In order to turn off a single flag from the default set of warning
    194 flags, you can use the CXXFLAGS variable, since this is passed after
    195 WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is
    196 used by default when g++ is detected) you can use
    197 `make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.
  • LICENSE

    r959 r600  
    22copyright/license.
    33
    4 Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi
     4Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi
    55Kutatocsoport (Egervary Combinatorial Optimization Research Group,
    66EGRES).
  • Makefile.am

    r840 r799  
    4545include doc/Makefile.am
    4646include tools/Makefile.am
    47 include scripts/Makefile.am
    4847
    4948DIST_SUBDIRS = demo
  • NEWS

    r1099 r712  
    1 2011-11-09 Version 1.2.3 released
    2 
    3         Bugfix release.
    4 
    5         #428: Add missing lemon/lemon.pc.cmake to the release tarball
    6         #429: Fix VS warnings
    7         #430: Fix LpBase::Constr two-side limit bug
    8 
    9 2011-08-08 Version 1.2.2 released
    10 
    11         Bugfix release.
    12 
    13         #392: Bug fix in Dfs::start(s,t)
    14         #414: Fix wrong initialization in Preflow
    15         #404: Update Doxygen configuration
    16         #416: Support tests with valgrind
    17         #418: Better Win CodeBlock/MinGW support
    18         #419: Backport build environment improvements from the main branch
    19               - Build of mip_test and lp_test precede the running of the tests
    20               - Also search for coin libs under ${COIN_ROOT_DIR}/lib/coin
    21               - Do not look for COIN_VOL libraries
    22         #382: Allow lgf file without Arc maps
    23         #417: Bug fix in CostScaling
    24 
    25 2010-10-21 Version 1.2.1 released
    26 
    27         Bugfix release.
    28 
    29         #366: Fix Pred[Matrix]MapPath::empty()
    30         #371: Bug fix in (di)graphCopy()
    31               The target graph is cleared before adding nodes and arcs/edges.
    32 
    33         #364: Add missing UndirectedTags
    34         #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
    35         #372: Fix a critical bug in preflow
    36 
    37 2010-03-19 Version 1.2 released
    38 
    39         This is major feature release
    40 
    41         * New algorithms
    42           * Bellman-Ford algorithm (#51)
    43           * Minimum mean cycle algorithms (#179)
    44             * Karp, Hartman-Orlin and Howard algorithms
    45           * New minimum cost flow algorithms (#180)
    46             * Cost Scaling algorithms
    47             * Capacity Scaling algorithm
    48             * Cycle-Canceling algorithms
    49           * Planarity related algorithms (#62)
    50             * Planarity checking algorithm
    51             * Planar embedding algorithm
    52             * Schnyder's planar drawing algorithm
    53             * Coloring planar graphs with five or six colors
    54           * Fractional matching algorithms (#314)
    55         * New data structures
    56           * StaticDigraph structure (#68)
    57           * Several new priority queue structures (#50, #301)
    58             * Fibonacci, Radix, Bucket, Pairing, Binomial
    59               D-ary and fourary heaps (#301)
    60           * Iterable map structures (#73)
    61         * Other new tools and functionality
    62           * Map utility functions (#320)
    63           * Reserve functions are added to ListGraph and SmartGraph (#311)
    64           * A resize() function is added to HypercubeGraph (#311)
    65           * A count() function is added to CrossRefMap (#302)
    66           * Support for multiple targets in Suurballe using fullInit() (#181)
    67           * Traits class and named parameters for Suurballe (#323)
    68           * Separate reset() and resetParams() functions in NetworkSimplex
    69             to handle graph changes (#327)
    70           * tolerance() functions are added to HaoOrlin (#306)
    71         * Implementation improvements
    72           * Improvements in weighted matching algorithms (#314)
    73             * Jumpstart initialization
    74           * ArcIt iteration is based on out-arc lists instead of in-arc lists
    75             in ListDigraph (#311)
    76           * Faster add row operation in CbcMip (#203)
    77           * Better implementation for split() in ListDigraph (#311)
    78           * ArgParser can also throw exception instead of exit(1) (#332)
    79         * Miscellaneous
    80           * A simple interactive bootstrap script
    81           * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,
    82                 #316,#319)
    83             * BibTeX references in the doc (#184)
    84           * Optionally use valgrind when running tests
    85           * Also check ReferenceMapTag in concept checks (#312)
    86           * dimacs-solver uses long long type by default.
    87         * Several bugfixes (compared to release 1.1):
    88           #295: Suppress MSVC warnings using pragmas
    89           ----: Various CMAKE related improvements
    90                 * Remove duplications from doc/CMakeLists.txt
    91                 * Rename documentation install folder from 'docs' to 'html'
    92                 * Add tools/CMakeLists.txt to the tarball
    93                 * Generate and install LEMONConfig.cmake
    94                 * Change the label of the html project in Visual Studio
    95                 * Fix the check for the 'long long' type
    96                 * Put the version string into config.h
    97                 * Minor CMake improvements
    98                 * Set the version to 'hg-tip' if everything fails
    99           #311: Add missing 'explicit' keywords
    100           #302: Fix the implementation and doc of CrossRefMap
    101           #308: Remove duplicate list_graph.h entry from source list
    102           #307: Bugfix in Preflow and Circulation
    103           #305: Bugfix and extension in the rename script
    104           #312: Also check ReferenceMapTag in concept checks
    105           #250: Bugfix in pathSource() and pathTarget()
    106           #321: Use pathCopy(from,to) instead of copyPath(to,from)
    107           #322: Distribure LEMONConfig.cmake.in
    108           #330: Bug fix in map_extender.h
    109           #336: Fix the date field comment of graphToEps() output
    110           #323: Bug fix in Suurballe
    111           #335: Fix clear() function in ExtendFindEnum
    112           #337: Use void* as the LPX object pointer
    113           #317: Fix (and improve) error message in mip_test.cc
    114                 Remove unnecessary OsiCbc dependency
    115           #356: Allow multiple executions of weighted matching algorithms (#356)
    116 
    11712009-05-13 Version 1.1 released
    1182
     
    18973          ----: Add missing unistd.h include to time_measure.h
    19074          #204: Compilation bug fixed in graph_to_eps.h with VS2005
    191           #214,#215: windows.h should never be included by LEMON headers
     75          #214,#215: windows.h should never be included by lemon headers
    19276          #230: Build systems check the availability of 'long long' type
    19377          #229: Default implementation of Tolerance<> is used for integer types
     
    211952008-10-13 Version 1.0 released
    21296
    213         This is the first stable release of LEMON. Compared to the 0.x
    214         release series, it features a considerably smaller but more
    215         matured set of tools. The API has also completely revised and
    216         changed in several places.
     97        This is the first stable release of LEMON. Compared to the 0.x
     98        release series, it features a considerably smaller but more
     99        matured set of tools. The API has also completely revised and
     100        changed in several places.
    217101
    218         * The major name changes compared to the 0.x series (see the
     102        * The major name changes compared to the 0.x series (see the
    219103          Migration Guide in the doc for more details)
    220104          * Graph -> Digraph, UGraph -> Graph
    221105          * Edge -> Arc, UEdge -> Edge
    222           * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
    223         * Other improvements
    224           * Better documentation
    225           * Reviewed and cleaned up codebase
    226           * CMake based build system (along with the autotools based one)
    227         * Contents of the library (ported from 0.x)
    228           * Algorithms
    229             * breadth-first search (bfs.h)
    230             * depth-first search (dfs.h)
    231             * Dijkstra's algorithm (dijkstra.h)
    232             * Kruskal's algorithm (kruskal.h)
    233           * Data structures
    234             * graph data structures (list_graph.h, smart_graph.h)
    235             * path data structures (path.h)
    236             * binary heap data structure (bin_heap.h)
    237             * union-find data structures (unionfind.h)
    238             * miscellaneous property maps (maps.h)
    239             * two dimensional vector and bounding box (dim2.h)
     106          * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
     107        * Other improvements
     108          * Better documentation
     109          * Reviewed and cleaned up codebase
     110          * CMake based build system (along with the autotools based one)
     111        * Contents of the library (ported from 0.x)
     112          * Algorithms
     113            * breadth-first search (bfs.h)
     114            * depth-first search (dfs.h)
     115            * Dijkstra's algorithm (dijkstra.h)
     116            * Kruskal's algorithm (kruskal.h)
     117          * Data structures
     118            * graph data structures (list_graph.h, smart_graph.h)
     119            * path data structures (path.h)
     120            * binary heap data structure (bin_heap.h)
     121            * union-find data structures (unionfind.h)
     122            * miscellaneous property maps (maps.h)
     123            * two dimensional vector and bounding box (dim2.h)
    240124          * Concepts
    241             * graph structure concepts (concepts/digraph.h, concepts/graph.h,
     125            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
    242126              concepts/graph_components.h)
    243             * concepts for other structures (concepts/heap.h, concepts/maps.h,
    244               concepts/path.h)
    245           * Tools
    246             * Mersenne twister random number generator (random.h)
    247             * tools for measuring cpu and wall clock time (time_measure.h)
    248             * tools for counting steps and events (counter.h)
    249             * tool for parsing command line arguments (arg_parser.h)
    250             * tool for visualizing graphs (graph_to_eps.h)
    251             * tools for reading and writing data in LEMON Graph Format
     127            * concepts for other structures (concepts/heap.h, concepts/maps.h,
     128              concepts/path.h)
     129          * Tools
     130            * Mersenne twister random number generator (random.h)
     131            * tools for measuring cpu and wall clock time (time_measure.h)
     132            * tools for counting steps and events (counter.h)
     133            * tool for parsing command line arguments (arg_parser.h)
     134            * tool for visualizing graphs (graph_to_eps.h)
     135            * tools for reading and writing data in LEMON Graph Format
    252136              (lgf_reader.h, lgf_writer.h)
    253137            * tools to handle the anomalies of calculations with
    254               floating point numbers (tolerance.h)
     138              floating point numbers (tolerance.h)
    255139            * tools to manage RGB colors (color.h)
    256           * Infrastructure
    257             * extended assertion handling (assert.h)
    258             * exception classes and error handling (error.h)
    259             * concept checking (concept_check.h)
    260             * commonly used mathematical constants (math.h)
     140          * Infrastructure
     141            * extended assertion handling (assert.h)
     142            * exception classes and error handling (error.h)
     143            * concept checking (concept_check.h)
     144            * commonly used mathematical constants (math.h)
  • README

    r921 r705  
    1818   Copying, distribution and modification conditions and terms.
    1919
    20 NEWS
    21 
    22    News and version history.
    23 
    2420INSTALL
    2521
     
    3834   Some example programs to make you easier to get familiar with LEMON.
    3935
    40 scripts/
    41 
    42    Scripts that make it easier to develop LEMON.
    43 
    4436test/
    4537
  • configure.ac

    r1039 r1037  
    4242
    4343AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
    44 AC_CHECK_PROG([python_found],[python],[yes],[no])
    4544AC_CHECK_PROG([gs_found],[gs],[yes],[no])
    4645
     
    8382fi
    8483AM_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"])
    10084
    10185dnl Checks for header files.
     
    145129echo
    146130echo Build additional tools........ : $enable_tools
    147 echo Use valgrind for tests........ : $use_valgrind
    148131echo
    149132echo The packace will be installed in
  • demo/arg_parser_demo.cc

    r956 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6666    .other("...");
    6767
    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 
    7368  // Perform the parsing process
    7469  // (in case of any error it terminates the program)
    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; }
     70  ap.parse();
    8071
    8172  // Check each option if it has been given and print its value
  • doc/CMakeLists.txt

    r1110 r1037  
    1818)
    1919
    20 IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
     20IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
    2121  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
    2222  SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
     
    2929    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
    3030    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
    31     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
    3231    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
    3332    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
     
    3635    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
    3736    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
    38     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
    3937    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
    4038    COMMAND ${CMAKE_COMMAND} -E remove_directory html
    41     COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
    4239    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    4340    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
  • doc/Doxyfile.in

    r1110 r1037  
    9898                         "@abs_top_srcdir@/tools" \
    9999                         "@abs_top_srcdir@/test/test_tools.h" \
    100                          "@abs_top_builddir@/doc/mainpage.dox" \
    101                          "@abs_top_builddir@/doc/references.dox"
     100                         "@abs_top_builddir@/doc/mainpage.dox"
    102101INPUT_ENCODING         = UTF-8
    103102FILE_PATTERNS          = *.h \
  • doc/Makefile.am

    r1115 r1112  
    1212        doc/named-param.dox \
    1313        doc/namespaces.dox \
    14         doc/references.bib \
    1514        doc/template.h \
    1615        doc/html \
     
    3029        connected_components.eps \
    3130        edge_biconnected_components.eps \
    32         matching.eps \
    3331        node_biconnected_components.eps \
    34         planar.eps \
    3532        strongly_connected_components.eps
    3633
     
    7168        fi
    7269
    73 references.dox: doc/references.bib
    74         if test ${python_found} = yes; then \
    75           cd doc; \
    76           python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \
    77           cd ..; \
    78         else \
    79           echo; \
    80           echo "Python not found."; \
    81           echo; \
    82           exit 1; \
    83         fi
    84 
    85 html-local: $(DOC_PNG_IMAGES) references.dox
     70html-local: $(DOC_PNG_IMAGES)
    8671        if test ${doxygen_found} = yes; then \
    8772          cd doc; \
  • doc/groups.dox

    r963 r710  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    227227
    228228/**
     229@defgroup matrices Matrices
     230@ingroup datas
     231\brief Two dimensional data storages implemented in LEMON.
     232
     233This group contains two dimensional data storages implemented in LEMON.
     234*/
     235
     236/**
    229237@defgroup paths Path Structures
    230238@ingroup datas
     
    239247any kind of path structure.
    240248
    241 \sa \ref concepts::Path "Path concept"
    242 */
    243 
    244 /**
    245 @defgroup heaps Heap Structures
    246 @ingroup datas
    247 \brief %Heap structures implemented in LEMON.
    248 
    249 This group contains the heap structures implemented in LEMON.
    250 
    251 LEMON provides several heap classes. They are efficient implementations
    252 of the abstract data type \e priority \e queue. They store items with
    253 specified values called \e priorities in such a way that finding and
    254 removing the item with minimum priority are efficient.
    255 The basic operations are adding and erasing items, changing the priority
    256 of an item, etc.
    257 
    258 Heaps are crucial in several algorithms, such as Dijkstra and Prim.
    259 The heap implementations have the same interface, thus any of them can be
    260 used easily in such algorithms.
    261 
    262 \sa \ref concepts::Heap "Heap concept"
     249\sa lemon::concepts::Path
    263250*/
    264251
     
    273260
    274261/**
    275 @defgroup geomdat Geometric Data Structures
    276 @ingroup auxdat
    277 \brief Geometric data structures implemented in LEMON.
    278 
    279 This group contains geometric data structures implemented in LEMON.
    280 
    281  - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
    282    vector with the usual operations.
    283  - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
    284    rectangular bounding box of a set of \ref lemon::dim2::Point
    285    "dim2::Point"'s.
    286 */
    287 
    288 /**
    289262@defgroup algs Algorithms
    290263\brief This group contains the several algorithms
     
    301274
    302275This group contains the common graph search algorithms, namely
    303 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
    304 \ref clrs01algorithms.
     276\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    305277*/
    306278
     
    310282\brief Algorithms for finding shortest paths.
    311283
    312 This group contains the algorithms for finding shortest paths in digraphs
    313 \ref clrs01algorithms.
     284This group contains the algorithms for finding shortest paths in digraphs.
    314285
    315286 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    319290   but the digraph should not contain directed cycles with negative total
    320291   length.
     292 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
     293   for solving the \e all-pairs \e shortest \e paths \e problem when arc
     294   lenghts can be either positive or negative, but the digraph should
     295   not contain directed cycles with negative total length.
    321296 - \ref Suurballe A successive shortest path algorithm for finding
    322297   arc-disjoint paths between two nodes having minimum total length.
     
    324299
    325300/**
    326 @defgroup spantree Minimum Spanning Tree Algorithms
    327 @ingroup algs
    328 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    329 
    330 This group contains the algorithms for finding minimum cost spanning
    331 trees and arborescences \ref clrs01algorithms.
    332 */
    333 
    334 /**
    335301@defgroup max_flow Maximum Flow Algorithms
    336302@ingroup algs
     
    338304
    339305This group contains the algorithms for finding maximum flows and
    340 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
     306feasible circulations.
    341307
    342308The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    352318\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    353319
    354 \ref Preflow is an efficient implementation of Goldberg-Tarjan's
    355 preflow push-relabel algorithm \ref goldberg88newapproach for finding
    356 maximum flows. It also provides functions to query the minimum cut,
    357 which is the dual problem of maximum flow.
    358 
    359 \ref Circulation is a preflow push-relabel algorithm implemented directly
     320LEMON contains several algorithms for solving maximum flow problems:
     321- \ref EdmondsKarp Edmonds-Karp algorithm.
     322- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
     323- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
     324- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
     325
     326In most cases the \ref Preflow "Preflow" algorithm provides the
     327fastest method for computing a maximum flow. All implementations
     328also provide functions to query the minimum cut, which is the dual
     329problem of maximum flow.
     330
     331\ref Circulation is a preflow push-relabel algorithm implemented directly
    360332for finding feasible circulations, which is a somewhat different problem,
    361333but it is strongly related to maximum flow.
     
    370342
    371343This group contains the algorithms for finding minimum cost flows and
    372 circulations \ref amo93networkflows. For more information about this
    373 problem and its dual solution, see \ref min_cost_flow
    374 "Minimum Cost Flow Problem".
     344circulations. For more information about this problem and its dual
     345solution see \ref min_cost_flow "Minimum Cost Flow Problem".
    375346
    376347LEMON contains several algorithms for this problem.
    377348 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    378    pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
    379  - \ref CostScaling Cost Scaling algorithm based on push/augment and
    380    relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
    381    \ref bunnagel98efficient.
    382  - \ref CapacityScaling Capacity Scaling algorithm based on the successive
    383    shortest path method \ref edmondskarp72theoretical.
    384  - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
    385    strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
     349   pivot strategies.
     350 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
     351   cost scaling.
     352 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
     353   capacity scaling.
     354 - \ref CancelAndTighten The Cancel and Tighten algorithm.
     355 - \ref CycleCanceling Cycle-Canceling algorithms.
    386356
    387357In general NetworkSimplex is the most efficient implementation,
     
    406376
    407377\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    408     \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
     378    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    409379
    410380LEMON contains several algorithms related to minimum cut problems:
     
    412382- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    413383  in directed graphs.
     384- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     385  calculating minimum cut in undirected graphs.
    414386- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    415387  all-pairs minimum cut in undirected graphs.
     
    420392
    421393/**
    422 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms
    423 @ingroup algs
    424 \brief Algorithms for finding minimum mean cycles.
    425 
    426 This group contains the algorithms for finding minimum mean cycles
    427 \ref clrs01algorithms, \ref amo93networkflows.
    428 
    429 The \e minimum \e mean \e cycle \e problem is to find a directed cycle
    430 of minimum mean length (cost) in a digraph.
    431 The mean length of a cycle is the average length of its arcs, i.e. the
    432 ratio between the total length of the cycle and the number of arcs on it.
    433 
    434 This problem has an important connection to \e conservative \e length
    435 \e functions, too. A length function on the arcs of a digraph is called
    436 conservative if and only if there is no directed cycle of negative total
    437 length. For an arbitrary length function, the negative of the minimum
    438 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
    439 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
    440 function.
    441 
    442 LEMON contains three algorithms for solving the minimum mean cycle problem:
    443 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
    444   \ref dasdan98minmeancycle.
    445 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    446   version of Karp's algorithm \ref dasdan98minmeancycle.
    447 - \ref HowardMmc Howard's policy iteration algorithm
    448   \ref dasdan98minmeancycle.
    449 
    450 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
    451 most efficient one, though the best known theoretical bound on its running
    452 time is exponential.
    453 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
    454 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
    455 typically faster due to the applied early termination scheme.
     394@defgroup graph_properties Connectivity and Other Graph Properties
     395@ingroup algs
     396\brief Algorithms for discovering the graph properties
     397
     398This group contains the algorithms for discovering the graph properties
     399like connectivity, bipartiteness, euler property, simplicity etc.
     400
     401\image html edge_biconnected_components.png
     402\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
     403*/
     404
     405/**
     406@defgroup planar Planarity Embedding and Drawing
     407@ingroup algs
     408\brief Algorithms for planarity checking, embedding and drawing
     409
     410This group contains the algorithms for planarity checking,
     411embedding and drawing.
     412
     413\image html planar.png
     414\image latex planar.eps "Plane graph" width=\textwidth
    456415*/
    457416
     
    474433
    475434The matching algorithms implemented in LEMON:
     435- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
     436  for calculating maximum cardinality matching in bipartite graphs.
     437- \ref PrBipartiteMatching Push-relabel algorithm
     438  for calculating maximum cardinality matching in bipartite graphs.
     439- \ref MaxWeightedBipartiteMatching
     440  Successive shortest path algorithm for calculating maximum weighted
     441  matching and maximum weighted bipartite matching in bipartite graphs.
     442- \ref MinCostMaxBipartiteMatching
     443  Successive shortest path algorithm for calculating minimum cost maximum
     444  matching in bipartite graphs.
    476445- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    477446  maximum cardinality matching in general graphs.
     
    481450  Edmond's blossom shrinking algorithm for calculating maximum weighted
    482451  perfect matching in general graphs.
    483 - \ref MaxFractionalMatching Push-relabel algorithm for calculating
    484   maximum cardinality fractional matching in general graphs.
    485 - \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
    486   maximum weighted fractional matching in general graphs.
    487 - \ref MaxWeightedPerfectFractionalMatching
    488   Augmenting path algorithm for calculating maximum weighted
    489   perfect fractional matching in general graphs.
    490 
    491 \image html matching.png
    492 \image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
    493 */
    494 
    495 /**
    496 @defgroup graph_properties Connectivity and Other Graph Properties
    497 @ingroup algs
    498 \brief Algorithms for discovering the graph properties
    499 
    500 This group contains the algorithms for discovering the graph properties
    501 like connectivity, bipartiteness, euler property, simplicity etc.
    502 
    503 \image html connected_components.png
    504 \image latex connected_components.eps "Connected components" width=\textwidth
    505 */
    506 
    507 /**
    508 @defgroup planar Planarity Embedding and Drawing
    509 @ingroup algs
    510 \brief Algorithms for planarity checking, embedding and drawing
    511 
    512 This group contains the algorithms for planarity checking,
    513 embedding and drawing.
    514 
    515 \image html planar.png
    516 \image latex planar.eps "Plane graph" width=\textwidth
     452
     453\image html bipartite_matching.png
     454\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
     455*/
     456
     457/**
     458@defgroup spantree Minimum Spanning Tree Algorithms
     459@ingroup algs
     460\brief Algorithms for finding minimum cost spanning trees and arborescences.
     461
     462This group contains the algorithms for finding minimum cost spanning
     463trees and arborescences.
    517464*/
    518465
     
    524471This group contains some algorithms implemented in LEMON
    525472in order to make it easier to implement complex algorithms.
     473*/
     474
     475/**
     476@defgroup approx Approximation Algorithms
     477@ingroup algs
     478\brief Approximation algorithms.
     479
     480This group contains the approximation and heuristic algorithms
     481implemented in LEMON.
    526482*/
    527483
     
    536492
    537493/**
    538 @defgroup lp_group LP and MIP Solvers
     494@defgroup lp_group Lp and Mip Solvers
    539495@ingroup gen_opt_group
    540 \brief LP and MIP solver interfaces for LEMON.
    541 
    542 This group contains LP and MIP solver interfaces for LEMON.
    543 Various LP solvers could be used in the same manner with this
    544 high-level interface.
    545 
    546 The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
    547 \ref cplex, \ref soplex.
     496\brief Lp and Mip solver interfaces for LEMON.
     497
     498This group contains Lp and Mip solver interfaces for LEMON. The
     499various LP solvers could be used in the same manner with this
     500interface.
     501*/
     502
     503/**
     504@defgroup lp_utils Tools for Lp and Mip Solvers
     505@ingroup lp_group
     506\brief Helper tools to the Lp and Mip solvers.
     507
     508This group adds some helper tools to general optimization framework
     509implemented in LEMON.
     510*/
     511
     512/**
     513@defgroup metah Metaheuristics
     514@ingroup gen_opt_group
     515\brief Metaheuristics for LEMON library.
     516
     517This group contains some metaheuristic optimization tools.
    548518*/
    549519
     
    618588
    619589/**
    620 @defgroup dimacs_group DIMACS Format
     590@defgroup dimacs_group DIMACS format
    621591@ingroup io_group
    622592\brief Read and write files in DIMACS format
     
    667637\brief Skeleton and concept checking classes for graph structures
    668638
    669 This group contains the skeletons and concept checking classes of
    670 graph structures.
     639This group contains the skeletons and concept checking classes of LEMON's
     640graph structures and helper classes used to implement these.
    671641*/
    672642
     
    680650
    681651/**
     652\anchor demoprograms
     653
     654@defgroup demos Demo Programs
     655
     656Some demo programs are listed here. Their full source codes can be found in
     657the \c demo subdirectory of the source tree.
     658
     659In order to compile them, use the <tt>make demo</tt> or the
     660<tt>make check</tt> commands.
     661*/
     662
     663/**
    682664@defgroup tools Standalone Utility Applications
    683665
     
    688670*/
    689671
    690 /**
    691 \anchor demoprograms
    692 
    693 @defgroup demos Demo Programs
    694 
    695 Some demo programs are listed here. Their full source codes can be found in
    696 the \c demo subdirectory of the source tree.
    697 
    698 In order to compile them, use the <tt>make demo</tt> or the
    699 <tt>make check</tt> commands.
    700 */
    701 
    702672}
  • doc/lgf.dox

    r1081 r1069  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/mainpage.dox.in

    r1039 r1037  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2222\section intro Introduction
    2323
    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.
     24\subsection whatis What is LEMON
     25
     26LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
     27and <b>O</b>ptimization in <b>N</b>etworks.
     28It is a C++ template
     29library aimed at combinatorial optimization tasks which
     30often involve in working
     31with graphs.
    2932
    3033<b>
     
    3639</b>
    3740
    38 The project is maintained by the
    39 <a href="http://www.cs.elte.hu/egres/">Egerv&aacute;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&ouml;tv&ouml;s Lor&aacute;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
     41\subsection howtoread How to read the documentation
    4842
    4943If you would like to get to know the library, see
    5044<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>.
    5545
    5646If you know what you are looking for, then try to find it under the
  • doc/min_cost_flow.dox

    r956 r710  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2727minimum total cost from a set of supply nodes to a set of demand nodes
    2828in a network with capacity constraints (lower and upper bounds)
    29 and arc costs \ref amo93networkflows.
     29and arc costs.
    3030
    3131Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
     
    7979   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
    8080 - For all \f$u\in V\f$ nodes:
    81    - \f$\pi(u)\leq 0\f$;
     81   - \f$\pi(u)<=0\f$;
    8282   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    8383     then \f$\pi(u)=0\f$.
    84 
     84 
    8585Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
    8686\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
     
    120120\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
    121121
    122 It means that the total demand must be less or equal to the
     122It means that the total demand must be less or equal to the 
    123123total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
    124124positive) and all the demands have to be satisfied, but there
     
    146146   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
    147147 - For all \f$u\in V\f$ nodes:
    148    - \f$\pi(u)\geq 0\f$;
     148   - \f$\pi(u)>=0\f$;
    149149   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    150150     then \f$\pi(u)=0\f$.
  • lemon/Makefile.am

    r1110 r1106  
    5959        lemon/arg_parser.h \
    6060        lemon/assert.h \
    61         lemon/bellman_ford.h \
    6261        lemon/bfs.h \
    6362        lemon/bin_heap.h \
    64         lemon/binomial_heap.h \
    6563        lemon/bucket_heap.h \
    66         lemon/capacity_scaling.h \
    6764        lemon/cbc.h \
    6865        lemon/circulation.h \
     
    7168        lemon/concept_check.h \
    7269        lemon/connectivity.h \
     70        lemon/counter.h \
    7371        lemon/core.h \
    74         lemon/cost_scaling.h \
    75         lemon/counter.h \
    7672        lemon/cplex.h \
    77         lemon/cycle_canceling.h \
    7873        lemon/dfs.h \
    79         lemon/dheap.h \
    8074        lemon/dijkstra.h \
    8175        lemon/dim2.h \
     
    8680        lemon/euler.h \
    8781        lemon/fib_heap.h \
    88         lemon/fractional_matching.h \
    8982        lemon/full_graph.h \
    9083        lemon/glpk.h \
     
    9285        lemon/graph_to_eps.h \
    9386        lemon/grid_graph.h \
    94         lemon/hartmann_orlin_mmc.h \
    95         lemon/howard_mmc.h \
    9687        lemon/hypercube_graph.h \
    97         lemon/karp_mmc.h \
    9888        lemon/kruskal.h \
    9989        lemon/hao_orlin.h \
     
    110100        lemon/nauty_reader.h \
    111101        lemon/network_simplex.h \
    112         lemon/pairing_heap.h \
    113102        lemon/path.h \
    114         lemon/planarity.h \
    115103        lemon/preflow.h \
    116         lemon/quad_heap.h \
    117104        lemon/radix_heap.h \
    118105        lemon/radix_sort.h \
     
    120107        lemon/smart_graph.h \
    121108        lemon/soplex.h \
    122         lemon/static_graph.h \
    123109        lemon/suurballe.h \
    124110        lemon/time_measure.h \
  • lemon/adaptors.h

    r956 r703  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    361361  /// parameter is set to be \c const.
    362362  ///
    363   /// This class provides item counting in the same time as the adapted
    364   /// digraph structure.
    365   ///
    366363  /// \tparam DGR The type of the adapted digraph.
    367364  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    422419      Parent::initialize(digraph);
    423420      _node_filter = &node_filter;
    424       _arc_filter = &arc_filter;
     421      _arc_filter = &arc_filter;     
    425422    }
    426423
     
    509506
    510507    template <typename V>
    511     class NodeMap
    512       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    513               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
     508    class NodeMap 
     509      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 
     510              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    514511      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    515         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     512        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    516513
    517514    public:
     
    536533
    537534    template <typename V>
    538     class ArcMap
     535    class ArcMap 
    539536      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    540               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     537              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    541538      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    542539        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
     
    583580      Parent::initialize(digraph);
    584581      _node_filter = &node_filter;
    585       _arc_filter = &arc_filter;
     582      _arc_filter = &arc_filter;     
    586583    }
    587584
     
    652649
    653650    template <typename V>
    654     class NodeMap
     651    class NodeMap 
    655652      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    656653          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    657       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     654      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 
    658655        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    659656
     
    679676
    680677    template <typename V>
    681     class ArcMap
     678    class ArcMap 
    682679      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    683680          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     
    722719  /// by adding or removing nodes or arcs, unless the \c GR template
    723720  /// parameter is set to be \c const.
    724   ///
    725   /// This class provides only linear time counting for nodes and arcs.
    726721  ///
    727722  /// \tparam DGR The type of the adapted digraph.
     
    10221017
    10231018    template <typename V>
    1024     class NodeMap
     1019    class NodeMap 
    10251020      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10261021          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1027       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1022      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
    10281023        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    10291024
     
    10491044
    10501045    template <typename V>
    1051     class ArcMap
     1046    class ArcMap 
    10521047      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10531048          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1054       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1049      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
    10551050        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    10561051
     
    10761071
    10771072    template <typename V>
    1078     class EdgeMap
     1073    class EdgeMap 
    10791074      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10801075        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1081       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1076      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
    10821077        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    10831078
     
    11181113    NF* _node_filter;
    11191114    EF* _edge_filter;
    1120     SubGraphBase()
    1121           : Parent(), _node_filter(0), _edge_filter(0) { }
     1115    SubGraphBase() 
     1116          : Parent(), _node_filter(0), _edge_filter(0) { }
    11221117
    11231118    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
     
    12201215
    12211216    template <typename V>
    1222     class NodeMap
     1217    class NodeMap 
    12231218      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12241219          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1225       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1220      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
    12261221        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    12271222
     
    12471242
    12481243    template <typename V>
    1249     class ArcMap
     1244    class ArcMap 
    12501245      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12511246          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1252       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1247      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
    12531248        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    12541249
     
    12741269
    12751270    template <typename V>
    1276     class EdgeMap
     1271    class EdgeMap 
    12771272      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12781273        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1279       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1280         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1274      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
     1275        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    12811276
    12821277    public:
     
    13191314  /// by adding or removing nodes or edges, unless the \c GR template
    13201315  /// parameter is set to be \c const.
    1321   ///
    1322   /// This class provides only linear time counting for nodes, edges and arcs.
    13231316  ///
    13241317  /// \tparam GR The type of the adapted graph.
     
    14781471  /// by adding or removing nodes or arcs/edges, unless the \c GR template
    14791472  /// parameter is set to be \c const.
    1480   ///
    1481   /// This class provides only linear time item counting.
    14821473  ///
    14831474  /// \tparam GR The type of the adapted digraph or graph.
     
    15051496#endif
    15061497    typedef DigraphAdaptorExtender<
    1507       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
     1498      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 
    15081499                     true> > Parent;
    15091500
     
    15261517    /// Creates a subgraph for the given digraph or graph with the
    15271518    /// given node filter map.
    1528     FilterNodes(GR& graph, NF& node_filter)
     1519    FilterNodes(GR& graph, NF& node_filter) 
    15291520      : Parent(), const_true_map()
    15301521    {
     
    15641555                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
    15651556    public GraphAdaptorExtender<
    1566       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
     1557      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
    15671558                   true> > {
    15681559
    15691560    typedef GraphAdaptorExtender<
    1570       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
     1561      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
    15711562                   true> > Parent;
    15721563
     
    16281619  /// by adding or removing nodes or arcs, unless the \c GR template
    16291620  /// parameter is set to be \c const.
    1630   ///
    1631   /// This class provides only linear time counting for nodes and arcs.
    16321621  ///
    16331622  /// \tparam DGR The type of the adapted digraph.
     
    16541643#endif
    16551644    typedef DigraphAdaptorExtender<
    1656       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
     1645      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 
    16571646                     AF, false> > Parent;
    16581647
     
    17401729  /// by adding or removing nodes or edges, unless the \c GR template
    17411730  /// parameter is set to be \c const.
    1742   ///
    1743   /// This class provides only linear time counting for nodes, edges and arcs.
    17441731  ///
    17451732  /// \tparam GR The type of the adapted graph.
     
    17621749  class FilterEdges :
    17631750    public GraphAdaptorExtender<
    1764       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
     1751      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
    17651752                   EF, false> > {
    17661753#endif
    17671754    typedef GraphAdaptorExtender<
    1768       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
     1755      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 
    17691756                   EF, false> > Parent;
    17701757
     
    17911778    /// Creates a subgraph for the given graph with the given edge
    17921779    /// filter map.
    1793     FilterEdges(GR& graph, EF& edge_filter)
     1780    FilterEdges(GR& graph, EF& edge_filter) 
    17941781      : Parent(), const_true_map() {
    17951782      Parent::initialize(graph, const_true_map, edge_filter);
     
    18591846      bool _forward;
    18601847
    1861       Arc(const Edge& edge, bool forward)
     1848      Arc(const Edge& edge, bool forward) 
    18621849        : _edge(edge), _forward(forward) {}
    18631850
     
    20992086
    21002087      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
    2101         : _forward(*adaptor._digraph, value),
     2088        : _forward(*adaptor._digraph, value), 
    21022089          _backward(*adaptor._digraph, value) {}
    21032090
     
    22172204    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
    22182205    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
    2219 
     2206   
    22202207    typedef EdgeNotifier ArcNotifier;
    22212208    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
     
    22452232  /// by adding or removing nodes or edges, unless the \c GR template
    22462233  /// parameter is set to be \c const.
    2247   ///
    2248   /// This class provides item counting in the same time as the adapted
    2249   /// digraph structure.
    22502234  ///
    22512235  /// \tparam DGR The type of the adapted digraph.
     
    25512535  /// by adding or removing nodes or arcs, unless the \c GR template
    25522536  /// parameter is set to be \c const.
    2553   ///
    2554   /// This class provides item counting in the same time as the adapted
    2555   /// graph structure.
    25562537  ///
    25572538  /// \tparam GR The type of the adapted graph.
     
    26982679  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
    26992680  ///
    2700   /// This class provides only linear time counting for nodes and arcs.
    2701   ///
    27022681  /// \tparam DGR The type of the adapted digraph.
    27032682  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    27292708           typename FM = CM,
    27302709           typename TL = Tolerance<typename CM::Value> >
    2731   class ResidualDigraph
     2710  class ResidualDigraph 
    27322711    : public SubDigraph<
    27332712        Undirector<const DGR>,
     
    27862765    ResidualDigraph(const DGR& digraph, const CM& capacity,
    27872766                    FM& flow, const TL& tolerance = Tolerance())
    2788       : Parent(), _capacity(&capacity), _flow(&flow),
     2767      : Parent(), _capacity(&capacity), _flow(&flow), 
    27892768        _graph(digraph), _node_filter(),
    27902769        _forward_filter(capacity, flow, tolerance),
     
    28682847
    28692848      /// Constructor
    2870       ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
     2849      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 
    28712850        : _adaptor(&adaptor) {}
    28722851
     
    33473326  /// in the adaptor.
    33483327  ///
    3349   /// This class provides item counting in the same time as the adapted
    3350   /// digraph structure.
    3351   ///
    33523328  /// \tparam DGR The type of the adapted digraph.
    33533329  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    34483424    /// to get a node map of the split digraph.
    34493425    /// Its value type is inherited from the first node map type (\c IN).
    3450     /// \tparam IN The type of the node map for the in-nodes.
     3426    /// \tparam IN The type of the node map for the in-nodes. 
    34513427    /// \tparam OUT The type of the node map for the out-nodes.
    34523428    template <typename IN, typename OUT>
  • lemon/arg_parser.cc

    r956 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2121namespace lemon {
    2222
    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 
    3123  void ArgParser::_showHelp(void *p)
    3224  {
    3325    (static_cast<ArgParser*>(p))->showHelp();
    34     (static_cast<ArgParser*>(p))->_terminate(ArgParserException::HELP);
     26    exit(1);
    3527  }
    3628
    3729  ArgParser::ArgParser(int argc, const char * const *argv)
    38     :_argc(argc), _argv(argv), _command_name(argv[0]),
    39     _exit_on_problems(true) {
     30    :_argc(argc), _argv(argv), _command_name(argv[0]) {
    4031    funcOption("-help","Print a short help message",_showHelp,this);
    4132    synonym("help","-help");
     
    352343        i!=_others_help.end();++i) showHelp(i);
    353344    for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i);
    354     _terminate(ArgParserException::HELP);
     345    exit(1);
    355346  }
    356347
     
    361352    std::cerr << "\nType '" << _command_name <<
    362353      " --help' to obtain a short summary on the usage.\n\n";
    363     _terminate(ArgParserException::UNKNOWN_OPT);
     354    exit(1);
    364355  }
    365356
     
    424415      std::cerr << "\nType '" << _command_name <<
    425416        " --help' to obtain a short summary on the usage.\n\n";
    426       _terminate(ArgParserException::INVALID_OPT);
     417      exit(1);
    427418    }
    428419  }
  • lemon/arg_parser.h

    r959 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3434
    3535namespace lemon {
    36 
    37   ///Exception used by ArgParser
    38 
    39   ///Exception used by ArgParser.
    40   ///
    41   class ArgParserException : public Exception {
    42   public:
    43     /// Reasons for failure
    44 
    45     /// Reasons for failure.
    46     ///
    47     enum Reason {
    48       HELP,         ///< <tt>--help</tt> option was given.
    49       UNKNOWN_OPT,  ///< Unknown option was given.
    50       INVALID_OPT   ///< Invalid combination of options.
    51     };
    52 
    53   private:
    54     Reason _reason;
    55 
    56   public:
    57     ///Constructor
    58     ArgParserException(Reason r) throw() : _reason(r) {}
    59     ///Virtual destructor
    60     virtual ~ArgParserException() throw() {}
    61     ///A short description of the exception
    62     virtual const char* what() const throw() {
    63       switch(_reason)
    64         {
    65         case HELP:
    66           return "lemon::ArgParseException: ask for help";
    67           break;
    68         case UNKNOWN_OPT:
    69           return "lemon::ArgParseException: unknown option";
    70           break;
    71         case INVALID_OPT:
    72           return "lemon::ArgParseException: invalid combination of options";
    73           break;
    74         }
    75       return "";
    76     }
    77     ///Return the reason for the failure
    78     Reason reason() const {return _reason; }
    79   };
    80 
    8136
    8237  ///Command line arguments parser
     
    162117                    void (*func)(void *),void *data);
    163118
    164     bool _exit_on_problems;
    165 
    166     void _terminate(ArgParserException::Reason reason) const;
    167 
    168119  public:
    169120
     
    430381    const std::vector<std::string> &files() const { return _file_args; }
    431382
    432     ///Throw instead of exit in case of problems
    433     void throwOnProblems()
    434     {
    435       _exit_on_problems=false;
    436     }
    437383  };
    438384}
  • lemon/bfs.h

    r956 r525  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the shortest paths.
    50     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    5252    ///Instantiates a \c PredMap.
     
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    65     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    66     ///By default, it is a NullMap.
     65    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6766    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6867    ///Instantiates a \c ProcessedMap.
     
    8382
    8483    ///The type of the map that indicates which nodes are reached.
    85     ///It must conform to
    86     ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     84    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8785    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8886    ///Instantiates a \c ReachedMap.
     
    9997
    10098    ///The type of the map that stores the distances of the nodes.
    101     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     99    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    102100    typedef typename Digraph::template NodeMap<int> DistMap;
    103101    ///Instantiates a \c DistMap.
     
    123121  ///\tparam GR The type of the digraph the algorithm runs on.
    124122  ///The default type is \ref ListDigraph.
    125   ///\tparam TR The traits class that defines various types used by the
    126   ///algorithm. By default, it is \ref BfsDefaultTraits
    127   ///"BfsDefaultTraits<GR>".
    128   ///In most cases, this parameter should not be set directly,
    129   ///consider to use the named template parameters instead.
    130123#ifdef DOXYGEN
    131124  template <typename GR,
     
    233226    ///\ref named-templ-param "Named parameter" for setting
    234227    ///\c PredMap type.
    235     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     228    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    236229    template <class T>
    237230    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    253246    ///\ref named-templ-param "Named parameter" for setting
    254247    ///\c DistMap type.
    255     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     248    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    256249    template <class T>
    257250    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    273266    ///\ref named-templ-param "Named parameter" for setting
    274267    ///\c ReachedMap type.
    275     ///It must conform to
    276     ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     268    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    277269    template <class T>
    278270    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    294286    ///\ref named-templ-param "Named parameter" for setting
    295287    ///\c ProcessedMap type.
    296     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     288    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    297289    template <class T>
    298290    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    422414    ///The simplest way to execute the BFS algorithm is to use one of the
    423415    ///member functions called \ref run(Node) "run()".\n
    424     ///If you need better control on the execution, you have to call
    425     ///\ref init() first, then you can add several source nodes with
     416    ///If you need more control on the execution, first you have to call
     417    ///\ref init(), then you can add several source nodes with
    426418    ///\ref addSource(). Finally the actual path computation can be
    427419    ///performed with one of the \ref start() functions.
     
    709701    ///Runs the algorithm to visit all nodes in the digraph.
    710702
    711     ///This method runs the %BFS algorithm in order to visit all nodes
    712     ///in the digraph.
     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).
    713709    ///
    714710    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
     
    742738    ///@{
    743739
    744     ///The shortest path to the given node.
    745 
    746     ///Returns the shortest path to the given node from the root(s).
     740    ///The shortest path to a node.
     741
     742    ///Returns the shortest path to a node.
    747743    ///
    748744    ///\warning \c t should be reached from the root(s).
     
    752748    Path path(Node t) const { return Path(*G, *_pred, t); }
    753749
    754     ///The distance of the given node from the root(s).
    755 
    756     ///Returns the distance of the given node from the root(s).
     750    ///The distance of a node from the root(s).
     751
     752    ///Returns the distance of a node from the root(s).
    757753    ///
    758754    ///\warning If node \c v is not reached from the root(s), then
     
    763759    int dist(Node v) const { return (*_dist)[v]; }
    764760
    765     ///\brief Returns the 'previous arc' of the shortest path tree for
    766     ///the given node.
    767     ///
     761    ///Returns the 'previous arc' of the shortest path tree for a node.
     762
    768763    ///This function returns the 'previous arc' of the shortest path
    769764    ///tree for the node \c v, i.e. it returns the last arc of a
     
    772767    ///
    773768    ///The shortest path tree used here is equal to the shortest path
    774     ///tree used in \ref predNode() and \ref predMap().
     769    ///tree used in \ref predNode().
    775770    ///
    776771    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    778773    Arc predArc(Node v) const { return (*_pred)[v];}
    779774
    780     ///\brief Returns the 'previous node' of the shortest path tree for
    781     ///the given node.
    782     ///
     775    ///Returns the 'previous node' of the shortest path tree for a node.
     776
    783777    ///This function returns the 'previous node' of the shortest path
    784778    ///tree for the node \c v, i.e. it returns the last but one node
    785     ///of a shortest path from a root to \c v. It is \c INVALID
     779    ///from a shortest path from a root to \c v. It is \c INVALID
    786780    ///if \c v is not reached from the root(s) or if \c v is a root.
    787781    ///
    788782    ///The shortest path tree used here is equal to the shortest path
    789     ///tree used in \ref predArc() and \ref predMap().
     783    ///tree used in \ref predArc().
    790784    ///
    791785    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    808802    ///
    809803    ///Returns a const reference to the node map that stores the predecessor
    810     ///arcs, which form the shortest path tree (forest).
     804    ///arcs, which form the shortest path tree.
    811805    ///
    812806    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    814808    const PredMap &predMap() const { return *_pred;}
    815809
    816     ///Checks if the given node is reached from the root(s).
     810    ///Checks if a node is reached from the root(s).
    817811
    818812    ///Returns \c true if \c v is reached from the root(s).
     
    840834    ///The type of the map that stores the predecessor
    841835    ///arcs of the shortest paths.
    842     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     836    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    843837    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    844838    ///Instantiates a PredMap.
     
    855849
    856850    ///The type of the map that indicates which nodes are processed.
    857     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    858     ///By default, it is a NullMap.
     851    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     852    ///By default it is a NullMap.
    859853    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    860854    ///Instantiates a ProcessedMap.
     
    875869
    876870    ///The type of the map that indicates which nodes are reached.
    877     ///It must conform to
    878     ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     871    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    879872    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    880873    ///Instantiates a ReachedMap.
     
    891884
    892885    ///The type of the map that stores the distances of the nodes.
    893     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     886    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    894887    typedef typename Digraph::template NodeMap<int> DistMap;
    895888    ///Instantiates a DistMap.
     
    906899
    907900    ///The type of the shortest paths.
    908     ///It must conform to the \ref concepts::Path "Path" concept.
     901    ///It must meet the \ref concepts::Path "Path" concept.
    909902    typedef lemon::Path<Digraph> Path;
    910903  };
     
    912905  /// Default traits class used by BfsWizard
    913906
    914   /// Default traits class used by BfsWizard.
    915   /// \tparam GR The type of the digraph.
     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.
    916913  template<class GR>
    917914  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
     
    941938    /// Constructor.
    942939
    943     /// This constructor does not require parameters, it initiates
     940    /// This constructor does not require parameters, therefore it initiates
    944941    /// all of the attributes to \c 0.
    945942    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    966963  /// This class should only be used through the \ref bfs() function,
    967964  /// which makes it easier to use the algorithm.
    968   ///
    969   /// \tparam TR The traits class that defines various types used by the
    970   /// algorithm.
    971965  template<class TR>
    972966  class BfsWizard : public TR
     
    974968    typedef TR Base;
    975969
     970    ///The type of the digraph the algorithm runs on.
    976971    typedef typename TR::Digraph Digraph;
    977972
     
    981976    typedef typename Digraph::OutArcIt OutArcIt;
    982977
     978    ///\brief The type of the map that stores the predecessor
     979    ///arcs of the shortest paths.
    983980    typedef typename TR::PredMap PredMap;
     981    ///\brief The type of the map that stores the distances of the nodes.
    984982    typedef typename TR::DistMap DistMap;
     983    ///\brief The type of the map that indicates which nodes are reached.
    985984    typedef typename TR::ReachedMap ReachedMap;
     985    ///\brief The type of the map that indicates which nodes are processed.
    986986    typedef typename TR::ProcessedMap ProcessedMap;
     987    ///The type of the shortest paths
    987988    typedef typename TR::Path Path;
    988989
     
    10541055    ///Runs BFS algorithm to visit all nodes in the digraph.
    10551056
    1056     ///This method runs BFS algorithm in order to visit all nodes
    1057     ///in the digraph.
     1057    ///This method runs BFS algorithm in order to compute
     1058    ///the shortest path to each node.
    10581059    void run()
    10591060    {
     
    10671068      SetPredMapBase(const TR &b) : TR(b) {}
    10681069    };
    1069 
    1070     ///\brief \ref named-templ-param "Named parameter" for setting
    1071     ///the predecessor map.
    1072     ///
    1073     ///\ref named-templ-param "Named parameter" function for setting
    1074     ///the map that stores the predecessor arcs of the nodes.
     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.
    10751075    template<class T>
    10761076    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10861086      SetReachedMapBase(const TR &b) : TR(b) {}
    10871087    };
    1088 
    1089     ///\brief \ref named-templ-param "Named parameter" for setting
    1090     ///the reached map.
    1091     ///
    1092     ///\ref named-templ-param "Named parameter" function for setting
    1093     ///the map that indicates which nodes are reached.
     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.
    10941093    template<class T>
    10951094    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    11051104      SetDistMapBase(const TR &b) : TR(b) {}
    11061105    };
    1107 
    1108     ///\brief \ref named-templ-param "Named parameter" for setting
    1109     ///the distance map.
    1110     ///
    1111     ///\ref named-templ-param "Named parameter" function for setting
    1112     ///the map that stores the distances of the nodes calculated
    1113     ///by the algorithm.
     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.
    11141111    template<class T>
    11151112    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    11251122      SetProcessedMapBase(const TR &b) : TR(b) {}
    11261123    };
    1127 
    1128     ///\brief \ref named-func-param "Named parameter" for setting
    1129     ///the processed map.
    1130     ///
    1131     ///\ref named-templ-param "Named parameter" function for setting
    1132     ///the map that indicates which nodes are processed.
     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.
    11331129    template<class T>
    11341130    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12691265    ///
    12701266    /// The type of the map that indicates which nodes are reached.
    1271     /// It must conform to
    1272     ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1267    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12731268    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12741269
     
    13081303  /// does not observe the BFS events. If you want to observe the BFS
    13091304  /// events, you should implement your own visitor class.
    1310   /// \tparam TR The traits class that defines various types used by the
    1311   /// algorithm. By default, it is \ref BfsVisitDefaultTraits
    1312   /// "BfsVisitDefaultTraits<GR>".
    1313   /// In most cases, this parameter should not be set directly,
    1314   /// consider to use the named template parameters instead.
     1305  /// \tparam TR Traits class to set various data types used by the
     1306  /// algorithm. The default traits class is
     1307  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
     1308  /// See \ref BfsVisitDefaultTraits for the documentation of
     1309  /// a BFS visit traits class.
    13151310#ifdef DOXYGEN
    13161311  template <typename GR, typename VS, typename TR>
     
    14311426    /// The simplest way to execute the BFS algorithm is to use one of the
    14321427    /// member functions called \ref run(Node) "run()".\n
    1433     /// If you need better control on the execution, you have to call
    1434     /// \ref init() first, then you can add several source nodes with
     1428    /// If you need more control on the execution, first you have to call
     1429    /// \ref init(), then you can add several source nodes with
    14351430    /// \ref addSource(). Finally the actual path computation can be
    14361431    /// performed with one of the \ref start() functions.
     
    17041699    /// \brief Runs the algorithm to visit all nodes in the digraph.
    17051700    ///
    1706     /// This method runs the %BFS algorithm in order to visit all nodes
    1707     /// in the digraph.
     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).
    17081707    ///
    17091708    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
     
    17371736    ///@{
    17381737
    1739     /// \brief Checks if the given node is reached from the root(s).
     1738    /// \brief Checks if a node is reached from the root(s).
    17401739    ///
    17411740    /// Returns \c true if \c v is reached from the root(s).
  • lemon/bin_heap.h

    r758 r730  
    2020#define LEMON_BIN_HEAP_H
    2121
    22 ///\ingroup heaps
     22///\ingroup auxdat
    2323///\file
    24 ///\brief Binary heap implementation.
     24///\brief Binary Heap implementation.
    2525
    2626#include <vector>
     
    3030namespace lemon {
    3131
    32   /// \ingroup heaps
    33   ///
    34   /// \brief Binary heap data structure.
    35   ///
    36   /// This class implements the \e binary \e heap data structure.
    37   /// It fully conforms to the \ref concepts::Heap "heap concept".
    38   ///
    39   /// \tparam PR Type of the priorities of the items.
    40   /// \tparam IM A read-writable item map with \c int values, used
    41   /// internally to handle the cross references.
    42   /// \tparam CMP A functor class for comparing the priorities.
    43   /// The default is \c std::less<PR>.
    44 #ifdef DOXYGEN
    45   template <typename PR, typename IM, typename CMP>
    46 #else
     32  ///\ingroup auxdat
     33  ///
     34  ///\brief A Binary Heap implementation.
     35  ///
     36  ///This class implements the \e binary \e heap data structure.
     37  ///
     38  ///A \e heap is a data structure for storing items with specified values
     39  ///called \e priorities in such a way that finding the item with minimum
     40  ///priority is efficient. \c CMP specifies the ordering of the priorities.
     41  ///In a heap one can change the priority of an item, add or erase an
     42  ///item, etc.
     43  ///
     44  ///\tparam PR Type of the priority of the items.
     45  ///\tparam IM A read and writable item map with int values, used internally
     46  ///to handle the cross references.
     47  ///\tparam CMP A functor class for the ordering of the priorities.
     48  ///The default is \c std::less<PR>.
     49  ///
     50  ///\sa FibHeap
     51  ///\sa Dijkstra
    4752  template <typename PR, typename IM, typename CMP = std::less<PR> >
    48 #endif
    4953  class BinHeap {
     54
    5055  public:
    51 
    52     /// Type of the item-int map.
     56    ///\e
    5357    typedef IM ItemIntMap;
    54     /// Type of the priorities.
     58    ///\e
    5559    typedef PR Prio;
    56     /// Type of the items stored in the heap.
     60    ///\e
    5761    typedef typename ItemIntMap::Key Item;
    58     /// Type of the item-priority pairs.
     62    ///\e
    5963    typedef std::pair<Item,Prio> Pair;
    60     /// Functor type for comparing the priorities.
     64    ///\e
    6165    typedef CMP Compare;
    6266
    63     /// \brief Type to represent the states of the items.
    64     ///
    65     /// Each item has a state associated to it. It can be "in heap",
    66     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     67    /// \brief Type to represent the items states.
     68    ///
     69    /// Each Item element have a state associated to it. It may be "in heap",
     70    /// "pre heap" or "post heap". The latter two are indifferent from the
    6771    /// heap's point of view, but may be useful to the user.
    6872    ///
     
    8185
    8286  public:
    83 
    84     /// \brief Constructor.
    85     ///
    86     /// Constructor.
    87     /// \param map A map that assigns \c int values to the items.
    88     /// It is used internally to handle the cross references.
    89     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     87    /// \brief The constructor.
     88    ///
     89    /// The constructor.
     90    /// \param map should be given to the constructor, since it is used
     91    /// internally to handle the cross references. The value of the map
     92    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
    9093    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
    9194
    92     /// \brief Constructor.
    93     ///
    94     /// Constructor.
    95     /// \param map A map that assigns \c int values to the items.
    96     /// It is used internally to handle the cross references.
    97     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    98     /// \param comp The function object used for comparing the priorities.
     95    /// \brief The constructor.
     96    ///
     97    /// The constructor.
     98    /// \param map should be given to the constructor, since it is used
     99    /// internally to handle the cross references. The value of the map
     100    /// should be PRE_HEAP (-1) for each element.
     101    ///
     102    /// \param comp The comparator function object.
    99103    BinHeap(ItemIntMap &map, const Compare &comp)
    100104      : _iim(map), _comp(comp) {}
    101105
    102106
    103     /// \brief The number of items stored in the heap.
    104     ///
    105     /// This function returns the number of items stored in the heap.
     107    /// The number of items stored in the heap.
     108    ///
     109    /// \brief Returns the number of items stored in the heap.
    106110    int size() const { return _data.size(); }
    107111
    108     /// \brief Check if the heap is empty.
    109     ///
    110     /// This function returns \c true if the heap is empty.
     112    /// \brief Checks if the heap stores no items.
     113    ///
     114    /// Returns \c true if and only if the heap stores no items.
    111115    bool empty() const { return _data.empty(); }
    112116
    113     /// \brief Make the heap empty.
    114     ///
    115     /// This functon makes the heap empty.
    116     /// It does not change the cross reference map. If you want to reuse
    117     /// a heap that is not surely empty, you should first clear it and
    118     /// then you should set the cross reference map to \c PRE_HEAP
    119     /// for each item.
     117    /// \brief Make empty this heap.
     118    ///
     119    /// Make empty this heap. It does not change the cross reference map.
     120    /// If you want to reuse what is not surely empty you should first clear
     121    /// the heap and after that you should set the cross reference map for
     122    /// each item to \c PRE_HEAP.
    120123    void clear() {
    121124      _data.clear();
     
    125128    static int parent(int i) { return (i-1)/2; }
    126129
    127     static int secondChild(int i) { return 2*i+2; }
     130    static int second_child(int i) { return 2*i+2; }
    128131    bool less(const Pair &p1, const Pair &p2) const {
    129132      return _comp(p1.second, p2.second);
    130133    }
    131134
    132     int bubbleUp(int hole, Pair p) {
     135    int bubble_up(int hole, Pair p) {
    133136      int par = parent(hole);
    134137      while( hole>0 && less(p,_data[par]) ) {
     
    141144    }
    142145
    143     int bubbleDown(int hole, Pair p, int length) {
    144       int child = secondChild(hole);
     146    int bubble_down(int hole, Pair p, int length) {
     147      int child = second_child(hole);
    145148      while(child < length) {
    146149        if( less(_data[child-1], _data[child]) ) {
     
    151154        move(_data[child], hole);
    152155        hole = child;
    153         child = secondChild(hole);
     156        child = second_child(hole);
    154157      }
    155158      child--;
     
    169172
    170173  public:
    171 
    172174    /// \brief Insert a pair of item and priority into the heap.
    173175    ///
    174     /// This function inserts \c p.first to the heap with priority
    175     /// \c p.second.
     176    /// Adds \c p.first to the heap with priority \c p.second.
    176177    /// \param p The pair to insert.
    177     /// \pre \c p.first must not be stored in the heap.
    178178    void push(const Pair &p) {
    179179      int n = _data.size();
    180180      _data.resize(n+1);
    181       bubbleUp(n, p);
    182     }
    183 
    184     /// \brief Insert an item into the heap with the given priority.
    185     ///
    186     /// This function inserts the given item into the heap with the
    187     /// given priority.
     181      bubble_up(n, p);
     182    }
     183
     184    /// \brief Insert an item into the heap with the given heap.
     185    ///
     186    /// Adds \c i to the heap with priority \c p.
    188187    /// \param i The item to insert.
    189188    /// \param p The priority of the item.
    190     /// \pre \e i must not be stored in the heap.
    191189    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    192190
    193     /// \brief Return the item having minimum priority.
    194     ///
    195     /// This function returns the item having minimum priority.
    196     /// \pre The heap must be non-empty.
     191    /// \brief Returns the item with minimum priority relative to \c Compare.
     192    ///
     193    /// This method returns the item with minimum priority relative to \c
     194    /// Compare.
     195    /// \pre The heap must be nonempty.
    197196    Item top() const {
    198197      return _data[0].first;
    199198    }
    200199
    201     /// \brief The minimum priority.
    202     ///
    203     /// This function returns the minimum priority.
    204     /// \pre The heap must be non-empty.
     200    /// \brief Returns the minimum priority relative to \c Compare.
     201    ///
     202    /// It returns the minimum priority relative to \c Compare.
     203    /// \pre The heap must be nonempty.
    205204    Prio prio() const {
    206205      return _data[0].second;
    207206    }
    208207
    209     /// \brief Remove the item having minimum priority.
    210     ///
    211     /// This function removes the item having minimum priority.
     208    /// \brief Deletes the item with minimum priority relative to \c Compare.
     209    ///
     210    /// This method deletes the item with minimum priority relative to \c
     211    /// Compare from the heap.
    212212    /// \pre The heap must be non-empty.
    213213    void pop() {
     
    215215      _iim.set(_data[0].first, POST_HEAP);
    216216      if (n > 0) {
    217         bubbleDown(0, _data[n], n);
     217        bubble_down(0, _data[n], n);
    218218      }
    219219      _data.pop_back();
    220220    }
    221221
    222     /// \brief Remove the given item from the heap.
    223     ///
    224     /// This function removes the given item from the heap if it is
    225     /// already stored.
    226     /// \param i The item to delete.
    227     /// \pre \e i must be in the heap.
     222    /// \brief Deletes \c i from the heap.
     223    ///
     224    /// This method deletes item \c i from the heap.
     225    /// \param i The item to erase.
     226    /// \pre The item should be in the heap.
    228227    void erase(const Item &i) {
    229228      int h = _iim[i];
     
    231230      _iim.set(_data[h].first, POST_HEAP);
    232231      if( h < n ) {
    233         if ( bubbleUp(h, _data[n]) == h) {
    234           bubbleDown(h, _data[n], n);
     232        if ( bubble_up(h, _data[n]) == h) {
     233          bubble_down(h, _data[n], n);
    235234        }
    236235      }
     
    238237    }
    239238
    240     /// \brief The priority of the given item.
    241     ///
    242     /// This function returns the priority of the given item.
    243     /// \param i The item.
    244     /// \pre \e i must be in the heap.
     239
     240    /// \brief Returns the priority of \c i.
     241    ///
     242    /// This function returns the priority of item \c i.
     243    /// \param i The item.
     244    /// \pre \c i must be in the heap.
    245245    Prio operator[](const Item &i) const {
    246246      int idx = _iim[i];
     
    248248    }
    249249
    250     /// \brief Set the priority of an item or insert it, if it is
    251     /// not stored in the heap.
    252     ///
    253     /// This method sets the priority of the given item if it is
    254     /// already stored in the heap. Otherwise it inserts the given
    255     /// item into the heap with the given priority.
     250    /// \brief \c i gets to the heap with priority \c p independently
     251    /// if \c i was already there.
     252    ///
     253    /// This method calls \ref push(\c i, \c p) if \c i is not stored
     254    /// in the heap and sets the priority of \c i to \c p otherwise.
    256255    /// \param i The item.
    257256    /// \param p The priority.
     
    262261      }
    263262      else if( _comp(p, _data[idx].second) ) {
    264         bubbleUp(idx, Pair(i,p));
     263        bubble_up(idx, Pair(i,p));
    265264      }
    266265      else {
    267         bubbleDown(idx, Pair(i,p), _data.size());
    268       }
    269     }
    270 
    271     /// \brief Decrease the priority of an item to the given value.
    272     ///
    273     /// This function decreases the priority of an item to the given value.
     266        bubble_down(idx, Pair(i,p), _data.size());
     267      }
     268    }
     269
     270    /// \brief Decreases the priority of \c i to \c p.
     271    ///
     272    /// This method decreases the priority of item \c i to \c p.
    274273    /// \param i The item.
    275274    /// \param p The priority.
    276     /// \pre \e i must be stored in the heap with priority at least \e p.
     275    /// \pre \c i must be stored in the heap with priority at least \c
     276    /// p relative to \c Compare.
    277277    void decrease(const Item &i, const Prio &p) {
    278278      int idx = _iim[i];
    279       bubbleUp(idx, Pair(i,p));
    280     }
    281 
    282     /// \brief Increase the priority of an item to the given value.
    283     ///
    284     /// This function increases the priority of an item to the given value.
     279      bubble_up(idx, Pair(i,p));
     280    }
     281
     282    /// \brief Increases the priority of \c i to \c p.
     283    ///
     284    /// This method sets the priority of item \c i to \c p.
    285285    /// \param i The item.
    286286    /// \param p The priority.
    287     /// \pre \e i must be stored in the heap with priority at most \e p.
     287    /// \pre \c i must be stored in the heap with priority at most \c
     288    /// p relative to \c Compare.
    288289    void increase(const Item &i, const Prio &p) {
    289290      int idx = _iim[i];
    290       bubbleDown(idx, Pair(i,p), _data.size());
    291     }
    292 
    293     /// \brief Return the state of an item.
    294     ///
    295     /// This method returns \c PRE_HEAP if the given item has never
    296     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    297     /// and \c POST_HEAP otherwise.
    298     /// In the latter case it is possible that the item will get back
    299     /// to the heap again.
     291      bubble_down(idx, Pair(i,p), _data.size());
     292    }
     293
     294    /// \brief Returns if \c item is in, has already been in, or has
     295    /// never been in the heap.
     296    ///
     297    /// This method returns PRE_HEAP if \c item has never been in the
     298    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     299    /// otherwise. In the latter case it is possible that \c item will
     300    /// get back to the heap again.
    300301    /// \param i The item.
    301302    State state(const Item &i) const {
     
    306307    }
    307308
    308     /// \brief Set the state of an item in the heap.
    309     ///
    310     /// This function sets the state of the given item in the heap.
    311     /// It can be used to manually clear the heap when it is important
    312     /// to achive better time complexity.
     309    /// \brief Sets the state of the \c item in the heap.
     310    ///
     311    /// Sets the state of the \c item in the heap. It can be used to
     312    /// manually clear the heap when it is important to achive the
     313    /// better time complexity.
    313314    /// \param i The item.
    314315    /// \param st The state. It should not be \c IN_HEAP.
     
    327328    }
    328329
    329     /// \brief Replace an item in the heap.
    330     ///
    331     /// This function replaces item \c i with item \c j.
    332     /// Item \c i must be in the heap, while \c j must be out of the heap.
    333     /// After calling this method, item \c i will be out of the
    334     /// heap and \c j will be in the heap with the same prioriority
    335     /// as item \c i had before.
     330    /// \brief Replaces an item in the heap.
     331    ///
     332    /// The \c i item is replaced with \c j item. The \c i item should
     333    /// be in the heap, while the \c j should be out of the heap. The
     334    /// \c i item will out of the heap and \c j will be in the heap
     335    /// with the same prioriority as prevoiusly the \c i item.
    336336    void replace(const Item& i, const Item& j) {
    337337      int idx = _iim[i];
  • lemon/bits/array_map.h

    r956 r664  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7171
    7272  private:
    73 
     73 
    7474    // The MapBase of the Map which imlements the core regisitry function.
    7575    typedef typename Notifier::ObserverBase Parent;
  • lemon/bits/default_map.h

    r956 r674  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    158158  public:
    159159    typedef DefaultMap<_Graph, _Item, _Value> Map;
    160 
     160   
    161161    typedef typename Parent::GraphType GraphType;
    162162    typedef typename Parent::Value Value;
  • lemon/bits/edge_set_extender.h

    r1110 r967  
    1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1/* -*- C++ -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library.
     3 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6464    Node oppositeNode(const Node &n, const Arc &e) const {
    6565      if (n == Parent::source(e))
    66         return Parent::target(e);
     66        return Parent::target(e);
    6767      else if(n==Parent::target(e))
    68         return Parent::source(e);
     68        return Parent::source(e);
    6969      else
    70         return INVALID;
     70        return INVALID;
    7171    }
    7272
     
    9292    // Iterable extensions
    9393
    94     class NodeIt : public Node {
     94    class NodeIt : public Node { 
    9595      const Digraph* digraph;
    9696    public:
     
    101101
    102102      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
    103         _graph.first(static_cast<Node&>(*this));
    104       }
    105 
    106       NodeIt(const Digraph& _graph, const Node& node)
    107         : Node(node), digraph(&_graph) {}
    108 
    109       NodeIt& operator++() {
    110         digraph->next(*this);
    111         return *this;
    112       }
    113 
    114     };
    115 
    116 
    117     class ArcIt : public Arc {
     103        _graph.first(static_cast<Node&>(*this));
     104      }
     105
     106      NodeIt(const Digraph& _graph, const Node& node) 
     107        : Node(node), digraph(&_graph) {}
     108
     109      NodeIt& operator++() { 
     110        digraph->next(*this);
     111        return *this;
     112      }
     113
     114    };
     115
     116
     117    class ArcIt : public Arc { 
    118118      const Digraph* digraph;
    119119    public:
     
    124124
    125125      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
    126         _graph.first(static_cast<Arc&>(*this));
    127       }
    128 
    129       ArcIt(const Digraph& _graph, const Arc& e) :
    130         Arc(e), digraph(&_graph) { }
    131 
    132       ArcIt& operator++() {
    133         digraph->next(*this);
    134         return *this;
    135       }
    136 
    137     };
    138 
    139 
    140     class OutArcIt : public Arc {
     126        _graph.first(static_cast<Arc&>(*this));
     127      }
     128
     129      ArcIt(const Digraph& _graph, const Arc& e) : 
     130        Arc(e), digraph(&_graph) { }
     131
     132      ArcIt& operator++() { 
     133        digraph->next(*this);
     134        return *this;
     135      }
     136
     137    };
     138
     139
     140    class OutArcIt : public Arc { 
    141141      const Digraph* digraph;
    142142    public:
     
    146146      OutArcIt(Invalid i) : Arc(i) { }
    147147
    148       OutArcIt(const Digraph& _graph, const Node& node)
    149         : digraph(&_graph) {
    150         _graph.firstOut(*this, node);
    151       }
    152 
    153       OutArcIt(const Digraph& _graph, const Arc& arc)
    154         : Arc(arc), digraph(&_graph) {}
    155 
    156       OutArcIt& operator++() {
    157         digraph->nextOut(*this);
    158         return *this;
    159       }
    160 
    161     };
    162 
    163 
    164     class InArcIt : public Arc {
     148      OutArcIt(const Digraph& _graph, const Node& node) 
     149        : digraph(&_graph) {
     150        _graph.firstOut(*this, node);
     151      }
     152
     153      OutArcIt(const Digraph& _graph, const Arc& arc) 
     154        : Arc(arc), digraph(&_graph) {}
     155
     156      OutArcIt& operator++() { 
     157        digraph->nextOut(*this);
     158        return *this;
     159      }
     160
     161    };
     162
     163
     164    class InArcIt : public Arc { 
    165165      const Digraph* digraph;
    166166    public:
     
    170170      InArcIt(Invalid i) : Arc(i) { }
    171171
    172       InArcIt(const Digraph& _graph, const Node& node)
    173         : digraph(&_graph) {
    174         _graph.firstIn(*this, node);
    175       }
    176 
    177       InArcIt(const Digraph& _graph, const Arc& arc) :
    178         Arc(arc), digraph(&_graph) {}
    179 
    180       InArcIt& operator++() {
    181         digraph->nextIn(*this);
    182         return *this;
     172      InArcIt(const Digraph& _graph, const Node& node) 
     173        : digraph(&_graph) {
     174        _graph.firstIn(*this, node);
     175      }
     176
     177      InArcIt(const Digraph& _graph, const Arc& arc) : 
     178        Arc(arc), digraph(&_graph) {}
     179
     180      InArcIt& operator++() { 
     181        digraph->nextIn(*this);
     182        return *this;
    183183      }
    184184
     
    216216
    217217    // Mappable extension
    218 
     218   
    219219    template <typename _Value>
    220     class ArcMap
     220    class ArcMap 
    221221      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    222222      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    223223
    224224    public:
    225       explicit ArcMap(const Digraph& _g)
    226         : Parent(_g) {}
    227       ArcMap(const Digraph& _g, const _Value& _v)
    228         : Parent(_g, _v) {}
     225      explicit ArcMap(const Digraph& _g) 
     226        : Parent(_g) {}
     227      ArcMap(const Digraph& _g, const _Value& _v) 
     228        : Parent(_g, _v) {}
    229229
    230230      ArcMap& operator=(const ArcMap& cmap) {
    231         return operator=<ArcMap>(cmap);
     231        return operator=<ArcMap>(cmap);
    232232      }
    233233
     
    235235      ArcMap& operator=(const CMap& cmap) {
    236236        Parent::operator=(cmap);
    237         return *this;
     237        return *this;
    238238      }
    239239
     
    248248      return arc;
    249249    }
    250 
     250   
    251251    void clear() {
    252252      notifier(Arc()).clear();
     
    313313    Node oppositeNode(const Node &n, const Edge &e) const {
    314314      if( n == Parent::u(e))
    315         return Parent::v(e);
     315        return Parent::v(e);
    316316      else if( n == Parent::v(e))
    317         return Parent::u(e);
     317        return Parent::u(e);
    318318      else
    319         return INVALID;
     319        return INVALID;
    320320    }
    321321
     
    341341
    342342    using Parent::notifier;
    343 
     343   
    344344    ArcNotifier& notifier(Arc) const {
    345345      return arc_notifier;
     
    351351
    352352
    353     class NodeIt : public Node {
     353    class NodeIt : public Node { 
    354354      const Graph* graph;
    355355    public:
     
    360360
    361361      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
    362         _graph.first(static_cast<Node&>(*this));
    363       }
    364 
    365       NodeIt(const Graph& _graph, const Node& node)
    366         : Node(node), graph(&_graph) {}
    367 
    368       NodeIt& operator++() {
    369         graph->next(*this);
    370         return *this;
    371       }
    372 
    373     };
    374 
    375 
    376     class ArcIt : public Arc {
     362        _graph.first(static_cast<Node&>(*this));
     363      }
     364
     365      NodeIt(const Graph& _graph, const Node& node) 
     366        : Node(node), graph(&_graph) {}
     367
     368      NodeIt& operator++() { 
     369        graph->next(*this);
     370        return *this;
     371      }
     372
     373    };
     374
     375
     376    class ArcIt : public Arc { 
    377377      const Graph* graph;
    378378    public:
     
    383383
    384384      explicit ArcIt(const Graph& _graph) : graph(&_graph) {
    385         _graph.first(static_cast<Arc&>(*this));
    386       }
    387 
    388       ArcIt(const Graph& _graph, const Arc& e) :
    389         Arc(e), graph(&_graph) { }
    390 
    391       ArcIt& operator++() {
    392         graph->next(*this);
    393         return *this;
    394       }
    395 
    396     };
    397 
    398 
    399     class OutArcIt : public Arc {
     385        _graph.first(static_cast<Arc&>(*this));
     386      }
     387
     388      ArcIt(const Graph& _graph, const Arc& e) : 
     389        Arc(e), graph(&_graph) { }
     390
     391      ArcIt& operator++() { 
     392        graph->next(*this);
     393        return *this;
     394      }
     395
     396    };
     397
     398
     399    class OutArcIt : public Arc { 
    400400      const Graph* graph;
    401401    public:
     
    405405      OutArcIt(Invalid i) : Arc(i) { }
    406406
    407       OutArcIt(const Graph& _graph, const Node& node)
    408         : graph(&_graph) {
    409         _graph.firstOut(*this, node);
    410       }
    411 
    412       OutArcIt(const Graph& _graph, const Arc& arc)
    413         : Arc(arc), graph(&_graph) {}
    414 
    415       OutArcIt& operator++() {
    416         graph->nextOut(*this);
    417         return *this;
    418       }
    419 
    420     };
    421 
    422 
    423     class InArcIt : public Arc {
     407      OutArcIt(const Graph& _graph, const Node& node) 
     408        : graph(&_graph) {
     409        _graph.firstOut(*this, node);
     410      }
     411
     412      OutArcIt(const Graph& _graph, const Arc& arc) 
     413        : Arc(arc), graph(&_graph) {}
     414
     415      OutArcIt& operator++() { 
     416        graph->nextOut(*this);
     417        return *this;
     418      }
     419
     420    };
     421
     422
     423    class InArcIt : public Arc { 
    424424      const Graph* graph;
    425425    public:
     
    429429      InArcIt(Invalid i) : Arc(i) { }
    430430
    431       InArcIt(const Graph& _graph, const Node& node)
    432         : graph(&_graph) {
    433         _graph.firstIn(*this, node);
    434       }
    435 
    436       InArcIt(const Graph& _graph, const Arc& arc) :
    437         Arc(arc), graph(&_graph) {}
    438 
    439       InArcIt& operator++() {
    440         graph->nextIn(*this);
    441         return *this;
    442       }
    443 
    444     };
    445 
    446 
    447     class EdgeIt : public Parent::Edge {
     431      InArcIt(const Graph& _graph, const Node& node) 
     432        : graph(&_graph) {
     433        _graph.firstIn(*this, node);
     434      }
     435
     436      InArcIt(const Graph& _graph, const Arc& arc) : 
     437        Arc(arc), graph(&_graph) {}
     438
     439      InArcIt& operator++() { 
     440        graph->nextIn(*this);
     441        return *this;
     442      }
     443
     444    };
     445
     446
     447    class EdgeIt : public Parent::Edge { 
    448448      const Graph* graph;
    449449    public:
     
    454454
    455455      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
    456         _graph.first(static_cast<Edge&>(*this));
    457       }
    458 
    459       EdgeIt(const Graph& _graph, const Edge& e) :
    460         Edge(e), graph(&_graph) { }
    461 
    462       EdgeIt& operator++() {
    463         graph->next(*this);
    464         return *this;
     456        _graph.first(static_cast<Edge&>(*this));
     457      }
     458
     459      EdgeIt(const Graph& _graph, const Edge& e) : 
     460        Edge(e), graph(&_graph) { }
     461
     462      EdgeIt& operator++() { 
     463        graph->next(*this);
     464        return *this;
    465465      }
    466466
     
    478478
    479479      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
    480         _graph.firstInc(*this, direction, n);
     480        _graph.firstInc(*this, direction, n);
    481481      }
    482482
    483483      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
    484         : graph(&_graph), Edge(ue) {
    485         direction = (_graph.source(ue) == n);
     484        : graph(&_graph), Edge(ue) {
     485        direction = (_graph.source(ue) == n);
    486486      }
    487487
    488488      IncEdgeIt& operator++() {
    489         graph->nextInc(*this, direction);
    490         return *this;
     489        graph->nextInc(*this, direction);
     490        return *this;
    491491      }
    492492    };
     
    535535
    536536    template <typename _Value>
    537     class ArcMap
     537    class ArcMap 
    538538      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    539539      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    540540
    541541    public:
    542       explicit ArcMap(const Graph& _g)
    543         : Parent(_g) {}
    544       ArcMap(const Graph& _g, const _Value& _v)
    545         : Parent(_g, _v) {}
     542      explicit ArcMap(const Graph& _g) 
     543        : Parent(_g) {}
     544      ArcMap(const Graph& _g, const _Value& _v) 
     545        : Parent(_g, _v) {}
    546546
    547547      ArcMap& operator=(const ArcMap& cmap) {
    548         return operator=<ArcMap>(cmap);
     548        return operator=<ArcMap>(cmap);
    549549      }
    550550
     
    552552      ArcMap& operator=(const CMap& cmap) {
    553553        Parent::operator=(cmap);
    554         return *this;
     554        return *this;
    555555      }
    556556
     
    559559
    560560    template <typename _Value>
    561     class EdgeMap
     561    class EdgeMap 
    562562      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    563563      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    564564
    565565    public:
    566       explicit EdgeMap(const Graph& _g)
    567         : Parent(_g) {}
    568 
    569       EdgeMap(const Graph& _g, const _Value& _v)
    570         : Parent(_g, _v) {}
     566      explicit EdgeMap(const Graph& _g) 
     567        : Parent(_g) {}
     568
     569      EdgeMap(const Graph& _g, const _Value& _v) 
     570        : Parent(_g, _v) {}
    571571
    572572      EdgeMap& operator=(const EdgeMap& cmap) {
    573         return operator=<EdgeMap>(cmap);
     573        return operator=<EdgeMap>(cmap);
    574574      }
    575575
     
    577577      EdgeMap& operator=(const CMap& cmap) {
    578578        Parent::operator=(cmap);
    579         return *this;
     579        return *this;
    580580      }
    581581
     
    594594      return edge;
    595595    }
    596 
     596   
    597597    void clear() {
    598598      notifier(Arc()).clear();
     
    620620      arc_notifier.clear();
    621621    }
    622 
     622   
    623623  };
    624624
  • lemon/bits/graph_adaptor_extender.h

    r1081 r965  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/graph_extender.h

    r825 r732  
    5757    }
    5858
    59     static Node fromId(int id, Node) {
     59    Node fromId(int id, Node) const {
    6060      return Parent::nodeFromId(id);
    6161    }
    6262
    63     static Arc fromId(int id, Arc) {
     63    Arc fromId(int id, Arc) const {
    6464      return Parent::arcFromId(id);
    6565    }
     
    356356    }
    357357
    358     static Node fromId(int id, Node) {
     358    Node fromId(int id, Node) const {
    359359      return Parent::nodeFromId(id);
    360360    }
    361361
    362     static Arc fromId(int id, Arc) {
     362    Arc fromId(int id, Arc) const {
    363363      return Parent::arcFromId(id);
    364364    }
    365365
    366     static Edge fromId(int id, Edge) {
     366    Edge fromId(int id, Edge) const {
    367367      return Parent::edgeFromId(id);
    368368    }
  • lemon/bits/path_dump.h

    r1081 r973  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/solver_bits.h

    r956 r566  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/windows.cc

    r1084 r1053  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9999      GetSystemTime(&time);
    100100      char buf1[11], buf2[9], buf3[5];
    101           if (GetDateFormat(MY_LOCALE, 0, &time,
     101          if (GetDateFormat(MY_LOCALE, 0, &time,
    102102                        ("ddd MMM dd"), buf1, 11) &&
    103103          GetTimeFormat(MY_LOCALE, 0, &time,
  • lemon/bucket_heap.h

    r956 r730  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2020#define LEMON_BUCKET_HEAP_H
    2121
    22 ///\ingroup heaps
     22///\ingroup auxdat
    2323///\file
    24 ///\brief Bucket heap implementation.
     24///\brief Bucket Heap implementation.
    2525
    2626#include <vector>
     
    5454  }
    5555
    56   /// \ingroup heaps
    57   ///
    58   /// \brief Bucket heap data structure.
    59   ///
    60   /// This class implements the \e bucket \e heap data structure.
    61   /// It practically conforms to the \ref concepts::Heap "heap concept",
    62   /// but it has some limitations.
    63   ///
    64   /// The bucket heap is a very simple structure. It can store only
    65   /// \c int priorities and it maintains a list of items for each priority
    66   /// in the range <tt>[0..C)</tt>. So it should only be used when the
    67   /// priorities are small. It is not intended to use as a Dijkstra heap.
    68   ///
    69   /// \tparam IM A read-writable item map with \c int values, used
    70   /// internally to handle the cross references.
    71   /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
    72   /// The default is \e min-heap. If this parameter is set to \c false,
    73   /// then the comparison is reversed, so the top(), prio() and pop()
    74   /// functions deal with the item having maximum priority instead of the
    75   /// minimum.
    76   ///
    77   /// \sa SimpleBucketHeap
     56  /// \ingroup auxdat
     57  ///
     58  /// \brief A Bucket Heap implementation.
     59  ///
     60  /// This class implements the \e bucket \e heap data structure. A \e heap
     61  /// is a data structure for storing items with specified values called \e
     62  /// priorities in such a way that finding the item with minimum priority is
     63  /// efficient. The bucket heap is very simple implementation, it can store
     64  /// only integer priorities and it stores for each priority in the
     65  /// \f$ [0..C) \f$ range a list of items. So it should be used only when
     66  /// the priorities are small. It is not intended to use as dijkstra heap.
     67  ///
     68  /// \param IM A read and write Item int map, used internally
     69  /// to handle the cross references.
     70  /// \param MIN If the given parameter is false then instead of the
     71  /// minimum value the maximum can be retrivied with the top() and
     72  /// prio() member functions.
    7873  template <typename IM, bool MIN = true>
    7974  class BucketHeap {
    8075
    8176  public:
    82 
    83     /// Type of the item-int map.
     77    /// \e
     78    typedef typename IM::Key Item;
     79    /// \e
     80    typedef int Prio;
     81    /// \e
     82    typedef std::pair<Item, Prio> Pair;
     83    /// \e
    8484    typedef IM ItemIntMap;
    85     /// Type of the priorities.
    86     typedef int Prio;
    87     /// Type of the items stored in the heap.
    88     typedef typename ItemIntMap::Key Item;
    89     /// Type of the item-priority pairs.
    90     typedef std::pair<Item,Prio> Pair;
    9185
    9286  private:
     
    9690  public:
    9791
    98     /// \brief Type to represent the states of the items.
    99     ///
    100     /// Each item has a state associated to it. It can be "in heap",
    101     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     92    /// \brief Type to represent the items states.
     93    ///
     94    /// Each Item element have a state associated to it. It may be "in heap",
     95    /// "pre heap" or "post heap". The latter two are indifferent from the
    10296    /// heap's point of view, but may be useful to the user.
    10397    ///
     
    111105
    112106  public:
    113 
    114     /// \brief Constructor.
    115     ///
    116     /// Constructor.
    117     /// \param map A map that assigns \c int values to the items.
    118     /// It is used internally to handle the cross references.
    119     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     107    /// \brief The constructor.
     108    ///
     109    /// The constructor.
     110    /// \param map should be given to the constructor, since it is used
     111    /// internally to handle the cross references. The value of the map
     112    /// should be PRE_HEAP (-1) for each element.
    120113    explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
    121114
    122     /// \brief The number of items stored in the heap.
    123     ///
    124     /// This function returns the number of items stored in the heap.
     115    /// The number of items stored in the heap.
     116    ///
     117    /// \brief Returns the number of items stored in the heap.
    125118    int size() const { return _data.size(); }
    126119
    127     /// \brief Check if the heap is empty.
    128     ///
    129     /// This function returns \c true if the heap is empty.
     120    /// \brief Checks if the heap stores no items.
     121    ///
     122    /// Returns \c true if and only if the heap stores no items.
    130123    bool empty() const { return _data.empty(); }
    131124
    132     /// \brief Make the heap empty.
    133     ///
    134     /// This functon makes the heap empty.
    135     /// It does not change the cross reference map. If you want to reuse
    136     /// a heap that is not surely empty, you should first clear it and
    137     /// then you should set the cross reference map to \c PRE_HEAP
    138     /// for each item.
     125    /// \brief Make empty this heap.
     126    ///
     127    /// Make empty this heap. It does not change the cross reference
     128    /// map.  If you want to reuse a heap what is not surely empty you
     129    /// should first clear the heap and after that you should set the
     130    /// cross reference map for each item to \c PRE_HEAP.
    139131    void clear() {
    140132      _data.clear(); _first.clear(); _minimum = 0;
     
    143135  private:
    144136
    145     void relocateLast(int idx) {
     137    void relocate_last(int idx) {
    146138      if (idx + 1 < int(_data.size())) {
    147139        _data[idx] = _data.back();
     
    183175
    184176  public:
    185 
    186177    /// \brief Insert a pair of item and priority into the heap.
    187178    ///
    188     /// This function inserts \c p.first to the heap with priority
    189     /// \c p.second.
     179    /// Adds \c p.first to the heap with priority \c p.second.
    190180    /// \param p The pair to insert.
    191     /// \pre \c p.first must not be stored in the heap.
    192181    void push(const Pair& p) {
    193182      push(p.first, p.second);
     
    196185    /// \brief Insert an item into the heap with the given priority.
    197186    ///
    198     /// This function inserts the given item into the heap with the
    199     /// given priority.
     187    /// Adds \c i to the heap with priority \c p.
    200188    /// \param i The item to insert.
    201189    /// \param p The priority of the item.
    202     /// \pre \e i must not be stored in the heap.
    203190    void push(const Item &i, const Prio &p) {
    204191      int idx = _data.size();
     
    211198    }
    212199
    213     /// \brief Return the item having minimum priority.
    214     ///
    215     /// This function returns the item having minimum priority.
    216     /// \pre The heap must be non-empty.
     200    /// \brief Returns the item with minimum priority.
     201    ///
     202    /// This method returns the item with minimum priority.
     203    /// \pre The heap must be nonempty.
    217204    Item top() const {
    218205      while (_first[_minimum] == -1) {
     
    222209    }
    223210
    224     /// \brief The minimum priority.
    225     ///
    226     /// This function returns the minimum priority.
    227     /// \pre The heap must be non-empty.
     211    /// \brief Returns the minimum priority.
     212    ///
     213    /// It returns the minimum priority.
     214    /// \pre The heap must be nonempty.
    228215    Prio prio() const {
    229216      while (_first[_minimum] == -1) {
     
    233220    }
    234221
    235     /// \brief Remove the item having minimum priority.
    236     ///
    237     /// This function removes the item having minimum priority.
     222    /// \brief Deletes the item with minimum priority.
     223    ///
     224    /// This method deletes the item with minimum priority from the heap.
    238225    /// \pre The heap must be non-empty.
    239226    void pop() {
     
    244231      _iim[_data[idx].item] = -2;
    245232      unlace(idx);
    246       relocateLast(idx);
    247     }
    248 
    249     /// \brief Remove the given item from the heap.
    250     ///
    251     /// This function removes the given item from the heap if it is
    252     /// already stored.
    253     /// \param i The item to delete.
    254     /// \pre \e i must be in the heap.
     233      relocate_last(idx);
     234    }
     235
     236    /// \brief Deletes \c i from the heap.
     237    ///
     238    /// This method deletes item \c i from the heap, if \c i was
     239    /// already stored in the heap.
     240    /// \param i The item to erase.
    255241    void erase(const Item &i) {
    256242      int idx = _iim[i];
    257243      _iim[_data[idx].item] = -2;
    258244      unlace(idx);
    259       relocateLast(idx);
    260     }
    261 
    262     /// \brief The priority of the given item.
    263     ///
    264     /// This function returns the priority of the given item.
    265     /// \param i The item.
    266     /// \pre \e i must be in the heap.
     245      relocate_last(idx);
     246    }
     247
     248
     249    /// \brief Returns the priority of \c i.
     250    ///
     251    /// This function returns the priority of item \c i.
     252    /// \pre \c i must be in the heap.
     253    /// \param i The item.
    267254    Prio operator[](const Item &i) const {
    268255      int idx = _iim[i];
     
    270257    }
    271258
    272     /// \brief Set the priority of an item or insert it, if it is
    273     /// not stored in the heap.
    274     ///
    275     /// This method sets the priority of the given item if it is
    276     /// already stored in the heap. Otherwise it inserts the given
    277     /// item into the heap with the given priority.
     259    /// \brief \c i gets to the heap with priority \c p independently
     260    /// if \c i was already there.
     261    ///
     262    /// This method calls \ref push(\c i, \c p) if \c i is not stored
     263    /// in the heap and sets the priority of \c i to \c p otherwise.
    278264    /// \param i The item.
    279265    /// \param p The priority.
     
    289275    }
    290276
    291     /// \brief Decrease the priority of an item to the given value.
    292     ///
    293     /// This function decreases the priority of an item to the given value.
     277    /// \brief Decreases the priority of \c i to \c p.
     278    ///
     279    /// This method decreases the priority of item \c i to \c p.
     280    /// \pre \c i must be stored in the heap with priority at least \c
     281    /// p relative to \c Compare.
    294282    /// \param i The item.
    295283    /// \param p The priority.
    296     /// \pre \e i must be stored in the heap with priority at least \e p.
    297284    void decrease(const Item &i, const Prio &p) {
    298285      int idx = _iim[i];
     
    305292    }
    306293
    307     /// \brief Increase the priority of an item to the given value.
    308     ///
    309     /// This function increases the priority of an item to the given value.
     294    /// \brief Increases the priority of \c i to \c p.
     295    ///
     296    /// This method sets the priority of item \c i to \c p.
     297    /// \pre \c i must be stored in the heap with priority at most \c
     298    /// p relative to \c Compare.
    310299    /// \param i The item.
    311300    /// \param p The priority.
    312     /// \pre \e i must be stored in the heap with priority at most \e p.
    313301    void increase(const Item &i, const Prio &p) {
    314302      int idx = _iim[i];
     
    318306    }
    319307
    320     /// \brief Return the state of an item.
    321     ///
    322     /// This method returns \c PRE_HEAP if the given item has never
    323     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    324     /// and \c POST_HEAP otherwise.
    325     /// In the latter case it is possible that the item will get back
    326     /// to the heap again.
     308    /// \brief Returns if \c item is in, has already been in, or has
     309    /// never been in the heap.
     310    ///
     311    /// This method returns PRE_HEAP if \c item has never been in the
     312    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     313    /// otherwise. In the latter case it is possible that \c item will
     314    /// get back to the heap again.
    327315    /// \param i The item.
    328316    State state(const Item &i) const {
     
    332320    }
    333321
    334     /// \brief Set the state of an item in the heap.
    335     ///
    336     /// This function sets the state of the given item in the heap.
    337     /// It can be used to manually clear the heap when it is important
    338     /// to achive better time complexity.
     322    /// \brief Sets the state of the \c item in the heap.
     323    ///
     324    /// Sets the state of the \c item in the heap. It can be used to
     325    /// manually clear the heap when it is important to achive the
     326    /// better time complexity.
    339327    /// \param i The item.
    340328    /// \param st The state. It should not be \c IN_HEAP.
     
    372360  }; // class BucketHeap
    373361
    374   /// \ingroup heaps
    375   ///
    376   /// \brief Simplified bucket heap data structure.
     362  /// \ingroup auxdat
     363  ///
     364  /// \brief A Simplified Bucket Heap implementation.
    377365  ///
    378366  /// This class implements a simplified \e bucket \e heap data
    379   /// structure. It does not provide some functionality, but it is
    380   /// faster and simpler than BucketHeap. The main difference is
    381   /// that BucketHeap stores a doubly-linked list for each key while
    382   /// this class stores only simply-linked lists. It supports erasing
    383   /// only for the item having minimum priority and it does not support
    384   /// key increasing and decreasing.
    385   ///
    386   /// Note that this implementation does not conform to the
    387   /// \ref concepts::Heap "heap concept" due to the lack of some
    388   /// functionality.
    389   ///
    390   /// \tparam IM A read-writable item map with \c int values, used
    391   /// internally to handle the cross references.
    392   /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
    393   /// The default is \e min-heap. If this parameter is set to \c false,
    394   /// then the comparison is reversed, so the top(), prio() and pop()
    395   /// functions deal with the item having maximum priority instead of the
    396   /// minimum.
     367  /// structure.  It does not provide some functionality but it faster
     368  /// and simplier data structure than the BucketHeap. The main
     369  /// difference is that the BucketHeap stores for every key a double
     370  /// linked list while this class stores just simple lists. In the
     371  /// other way it does not support erasing each elements just the
     372  /// minimal and it does not supports key increasing, decreasing.
     373  ///
     374  /// \param IM A read and write Item int map, used internally
     375  /// to handle the cross references.
     376  /// \param MIN If the given parameter is false then instead of the
     377  /// minimum value the maximum can be retrivied with the top() and
     378  /// prio() member functions.
    397379  ///
    398380  /// \sa BucketHeap
     
    401383
    402384  public:
    403 
    404     /// Type of the item-int map.
     385    typedef typename IM::Key Item;
     386    typedef int Prio;
     387    typedef std::pair<Item, Prio> Pair;
    405388    typedef IM ItemIntMap;
    406     /// Type of the priorities.
    407     typedef int Prio;
    408     /// Type of the items stored in the heap.
    409     typedef typename ItemIntMap::Key Item;
    410     /// Type of the item-priority pairs.
    411     typedef std::pair<Item,Prio> Pair;
    412389
    413390  private:
     
    417394  public:
    418395
    419     /// \brief Type to represent the states of the items.
    420     ///
    421     /// Each item has a state associated to it. It can be "in heap",
    422     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     396    /// \brief Type to represent the items states.
     397    ///
     398    /// Each Item element have a state associated to it. It may be "in heap",
     399    /// "pre heap" or "post heap". The latter two are indifferent from the
    423400    /// heap's point of view, but may be useful to the user.
    424401    ///
     
    433410  public:
    434411
    435     /// \brief Constructor.
    436     ///
    437     /// Constructor.
    438     /// \param map A map that assigns \c int values to the items.
    439     /// It is used internally to handle the cross references.
    440     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     412    /// \brief The constructor.
     413    ///
     414    /// The constructor.
     415    /// \param map should be given to the constructor, since it is used
     416    /// internally to handle the cross references. The value of the map
     417    /// should be PRE_HEAP (-1) for each element.
    441418    explicit SimpleBucketHeap(ItemIntMap &map)
    442419      : _iim(map), _free(-1), _num(0), _minimum(0) {}
    443420
    444     /// \brief The number of items stored in the heap.
    445     ///
    446     /// This function returns the number of items stored in the heap.
     421    /// \brief Returns the number of items stored in the heap.
     422    ///
     423    /// The number of items stored in the heap.
    447424    int size() const { return _num; }
    448425
    449     /// \brief Check if the heap is empty.
    450     ///
    451     /// This function returns \c true if the heap is empty.
     426    /// \brief Checks if the heap stores no items.
     427    ///
     428    /// Returns \c true if and only if the heap stores no items.
    452429    bool empty() const { return _num == 0; }
    453430
    454     /// \brief Make the heap empty.
    455     ///
    456     /// This functon makes the heap empty.
    457     /// It does not change the cross reference map. If you want to reuse
    458     /// a heap that is not surely empty, you should first clear it and
    459     /// then you should set the cross reference map to \c PRE_HEAP
    460     /// for each item.
     431    /// \brief Make empty this heap.
     432    ///
     433    /// Make empty this heap. It does not change the cross reference
     434    /// map.  If you want to reuse a heap what is not surely empty you
     435    /// should first clear the heap and after that you should set the
     436    /// cross reference map for each item to \c PRE_HEAP.
    461437    void clear() {
    462438      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
     
    465441    /// \brief Insert a pair of item and priority into the heap.
    466442    ///
    467     /// This function inserts \c p.first to the heap with priority
    468     /// \c p.second.
     443    /// Adds \c p.first to the heap with priority \c p.second.
    469444    /// \param p The pair to insert.
    470     /// \pre \c p.first must not be stored in the heap.
    471445    void push(const Pair& p) {
    472446      push(p.first, p.second);
     
    475449    /// \brief Insert an item into the heap with the given priority.
    476450    ///
    477     /// This function inserts the given item into the heap with the
    478     /// given priority.
     451    /// Adds \c i to the heap with priority \c p.
    479452    /// \param i The item to insert.
    480453    /// \param p The priority of the item.
    481     /// \pre \e i must not be stored in the heap.
    482454    void push(const Item &i, const Prio &p) {
    483455      int idx;
     
    500472    }
    501473
    502     /// \brief Return the item having minimum priority.
    503     ///
    504     /// This function returns the item having minimum priority.
    505     /// \pre The heap must be non-empty.
     474    /// \brief Returns the item with minimum priority.
     475    ///
     476    /// This method returns the item with minimum priority.
     477    /// \pre The heap must be nonempty.
    506478    Item top() const {
    507479      while (_first[_minimum] == -1) {
     
    511483    }
    512484
    513     /// \brief The minimum priority.
    514     ///
    515     /// This function returns the minimum priority.
    516     /// \pre The heap must be non-empty.
     485    /// \brief Returns the minimum priority.
     486    ///
     487    /// It returns the minimum priority.
     488    /// \pre The heap must be nonempty.
    517489    Prio prio() const {
    518490      while (_first[_minimum] == -1) {
     
    522494    }
    523495
    524     /// \brief Remove the item having minimum priority.
    525     ///
    526     /// This function removes the item having minimum priority.
     496    /// \brief Deletes the item with minimum priority.
     497    ///
     498    /// This method deletes the item with minimum priority from the heap.
    527499    /// \pre The heap must be non-empty.
    528500    void pop() {
     
    538510    }
    539511
    540     /// \brief The priority of the given item.
    541     ///
    542     /// This function returns the priority of the given item.
    543     /// \param i The item.
    544     /// \pre \e i must be in the heap.
    545     /// \warning This operator is not a constant time function because
    546     /// it scans the whole data structure to find the proper value.
     512    /// \brief Returns the priority of \c i.
     513    ///
     514    /// This function returns the priority of item \c i.
     515    /// \warning This operator is not a constant time function
     516    /// because it scans the whole data structure to find the proper
     517    /// value.
     518    /// \pre \c i must be in the heap.
     519    /// \param i The item.
    547520    Prio operator[](const Item &i) const {
    548       for (int k = 0; k < int(_first.size()); ++k) {
     521      for (int k = 0; k < _first.size(); ++k) {
    549522        int idx = _first[k];
    550523        while (idx != -1) {
     
    558531    }
    559532
    560     /// \brief Return the state of an item.
    561     ///
    562     /// This method returns \c PRE_HEAP if the given item has never
    563     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    564     /// and \c POST_HEAP otherwise.
    565     /// In the latter case it is possible that the item will get back
    566     /// to the heap again.
     533    /// \brief Returns if \c item is in, has already been in, or has
     534    /// never been in the heap.
     535    ///
     536    /// This method returns PRE_HEAP if \c item has never been in the
     537    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     538    /// otherwise. In the latter case it is possible that \c item will
     539    /// get back to the heap again.
    567540    /// \param i The item.
    568541    State state(const Item &i) const {
  • lemon/cbc.cc

    r1122 r1120  
    9090  }
    9191
    92   int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
    93     std::vector<int> indexes;
    94     std::vector<Value> values;
    95 
    96     for(ExprIterator it = b; it != e; ++it) {
    97       indexes.push_back(it->first);
    98       values.push_back(it->second);
    99     }
    100 
    101     _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
    102     return _prob->numberRows() - 1;
    103   }
    10492
    10593  void CbcMip::_eraseCol(int i) {
  • lemon/cbc.h

    r956 r623  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6363    virtual int _addCol();
    6464    virtual int _addRow();
    65     virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
    6665
    6766    virtual void _eraseCol(int i);
     
    122121    int _message_level;
    123122
    124 
     123   
    125124
    126125  };
  • lemon/circulation.h

    r956 r735  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6060    /// \brief The type of supply map.
    6161    ///
    62     /// The type of the map that stores the signed supply values of the
    63     /// nodes.
     62    /// The type of the map that stores the signed supply values of the 
     63    /// nodes. 
    6464    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    6565    typedef SM SupplyMap;
     
    7373    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    7474    /// concept.
    75 #ifdef DOXYGEN
    76     typedef GR::ArcMap<Value> FlowMap;
    77 #else
    7875    typedef typename Digraph::template ArcMap<Value> FlowMap;
    79 #endif
    8076
    8177    /// \brief Instantiates a FlowMap.
     
    9288    /// The elevator type used by the algorithm.
    9389    ///
    94     /// \sa Elevator, LinkedElevator
    95 #ifdef DOXYGEN
    96     typedef lemon::Elevator<GR, GR::Node> Elevator;
    97 #else
     90    /// \sa Elevator
     91    /// \sa LinkedElevator
    9892    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
    99 #endif
    10093
    10194    /// \brief Instantiates an Elevator.
     
    142135     \geq sup(u) \quad \forall u\in V, \f]
    143136     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
    144 
     137     
    145138     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
    146139     zero or negative in order to have a feasible solution (since the sum
     
    152145     constraints have to be satisfied with equality, i.e. all demands
    153146     have to be satisfied and all supplies have to be used.
    154 
     147     
    155148     If you need the opposite inequalities in the supply/demand constraints
    156149     (i.e. the total demand is less than the total supply and all the demands
     
    174167     \tparam SM The type of the supply map. The default map type is
    175168     \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.
    181169  */
    182170#ifdef DOXYGEN
     
    312300    /// able to automatically created by the algorithm (i.e. the
    313301    /// digraph and the maximum level should be passed to it).
    314     /// However, an external elevator object could also be passed to the
     302    /// However an external elevator object could also be passed to the
    315303    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
    316304    /// before calling \ref run() or \ref init().
     
    338326    /// \param graph The digraph the algorithm runs on.
    339327    /// \param lower The lower bounds for the flow values on the arcs.
    340     /// \param upper The upper bounds (capacities) for the flow values
     328    /// \param upper The upper bounds (capacities) for the flow values 
    341329    /// on the arcs.
    342330    /// \param supply The signed supply values of the nodes.
     
    463451    }
    464452
    465     /// \brief Sets the tolerance used by the algorithm.
    466     ///
    467     /// Sets the tolerance object used by the algorithm.
    468     /// \return <tt>(*this)</tt>
     453    /// \brief Sets the tolerance used by algorithm.
     454    ///
     455    /// Sets the tolerance used by algorithm.
    469456    Circulation& tolerance(const Tolerance& tolerance) {
    470457      _tol = tolerance;
     
    474461    /// \brief Returns a const reference to the tolerance.
    475462    ///
    476     /// Returns a const reference to the tolerance object used by
    477     /// the algorithm.
     463    /// Returns a const reference to the tolerance.
    478464    const Tolerance& tolerance() const {
    479465      return _tol;
     
    482468    /// \name Execution Control
    483469    /// The simplest way to execute the algorithm is to call \ref run().\n
    484     /// 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
     470    /// If you need more control on the initial solution or the execution,
     471    /// first you have to call one of the \ref init() functions, then
    486472    /// the \ref start() function.
    487473
  • lemon/clp.cc

    r956 r623  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7676  int ClpLp::_addRow() {
    7777    _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
    78     return _prob->numberRows() - 1;
    79   }
    80 
    81   int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
    82     std::vector<int> indexes;
    83     std::vector<Value> values;
    84 
    85     for(ExprIterator it = b; it != e; ++it) {
    86       indexes.push_back(it->first);
    87       values.push_back(it->second);
    88     }
    89 
    90     _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
    9178    return _prob->numberRows() - 1;
    9279  }
  • lemon/clp.h

    r956 r623  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7676    virtual int _addCol();
    7777    virtual int _addRow();
    78     virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
    7978
    8079    virtual void _eraseCol(int i);
     
    139138
    140139    virtual void _messageLevel(MessageLevel);
    141 
     140   
    142141  public:
    143142
  • lemon/concepts/digraph.h

    r956 r627  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3636    /// \brief Class describing the concept of directed graphs.
    3737    ///
    38     /// This class describes the common interface of all directed
    39     /// graphs (digraphs).
     38    /// This class describes the \ref concept "concept" of the
     39    /// immutable directed digraphs.
    4040    ///
    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.
     41    /// Note that actual digraph implementation like @ref ListDigraph or
     42    /// @ref SmartDigraph may have several additional functionality.
    4743    ///
    48     /// \sa Graph
     44    /// \sa concept
    4945    class Digraph {
    5046    private:
    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.
     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
    5558      void operator=(const Digraph &) {}
    56 
    5759    public:
    58       /// Default constructor.
     60      ///\e
     61
     62      /// Defalult constructor.
     63
     64      /// Defalult constructor.
     65      ///
    5966      Digraph() { }
    60 
    61       /// The node type of the digraph
     67      /// Class for identifying a node of the digraph
    6268
    6369      /// This class identifies a node of the digraph. It also serves
    6470      /// as a base class of the node iterators,
    65       /// thus they convert to this type.
     71      /// thus they will convert to this type.
    6672      class Node {
    6773      public:
    6874        /// Default constructor
    6975
    70         /// Default constructor.
    71         /// \warning It sets the object to an undefined value.
     76        /// @warning The default constructor sets the iterator
     77        /// to an undefined value.
    7278        Node() { }
    7379        /// Copy constructor.
     
    7783        Node(const Node&) { }
    7884
    79         /// %Invalid constructor \& conversion.
    80 
    81         /// Initializes the object to be invalid.
     85        /// Invalid constructor \& conversion.
     86
     87        /// This constructor initializes the iterator to be invalid.
    8288        /// \sa Invalid for more details.
    8389        Node(Invalid) { }
    8490        /// Equality operator
    8591
    86         /// Equality operator.
    87         ///
    8892        /// Two iterators are equal if and only if they point to the
    89         /// same object or both are \c INVALID.
     93        /// same object or both are invalid.
    9094        bool operator==(Node) const { return true; }
    9195
    9296        /// Inequality operator
    9397
    94         /// Inequality operator.
     98        /// \sa operator==(Node n)
     99        ///
    95100        bool operator!=(Node) const { return true; }
    96101
    97102        /// Artificial ordering operator.
    98103
    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.
     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.
    104110        bool operator<(Node) const { return false; }
    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:
     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:
    112119      ///\code
    113120      /// int count=0;
     
    118125        /// Default constructor
    119126
    120         /// Default constructor.
    121         /// \warning It sets the iterator to an undefined value.
     127        /// @warning The default constructor sets the iterator
     128        /// to an undefined value.
    122129        NodeIt() { }
    123130        /// Copy constructor.
     
    126133        ///
    127134        NodeIt(const NodeIt& n) : Node(n) { }
    128         /// %Invalid constructor \& conversion.
    129 
    130         /// Initializes the iterator to be invalid.
     135        /// Invalid constructor \& conversion.
     136
     137        /// Initialize the iterator to be invalid.
    131138        /// \sa Invalid for more details.
    132139        NodeIt(Invalid) { }
    133140        /// Sets the iterator to the first node.
    134141
    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         ///
     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.
    142151        NodeIt(const Digraph&, const Node&) { }
    143152        /// Next node.
     
    149158
    150159
    151       /// The arc type of the digraph
     160      /// Class for identifying an arc of the digraph
    152161
    153162      /// This class identifies an arc of the digraph. It also serves
     
    158167        /// Default constructor
    159168
    160         /// Default constructor.
    161         /// \warning It sets the object to an undefined value.
     169        /// @warning The default constructor sets the iterator
     170        /// to an undefined value.
    162171        Arc() { }
    163172        /// Copy constructor.
     
    166175        ///
    167176        Arc(const Arc&) { }
    168         /// %Invalid constructor \& conversion.
    169 
    170         /// Initializes the object to be invalid.
    171         /// \sa Invalid for more details.
     177        /// Initialize the iterator to be invalid.
     178
     179        /// Initialize the iterator to be invalid.
     180        ///
    172181        Arc(Invalid) { }
    173182        /// Equality operator
    174183
    175         /// Equality operator.
    176         ///
    177184        /// Two iterators are equal if and only if they point to the
    178         /// same object or both are \c INVALID.
     185        /// same object or both are invalid.
    179186        bool operator==(Arc) const { return true; }
    180187        /// Inequality operator
    181188
    182         /// Inequality operator.
     189        /// \sa operator==(Arc n)
     190        ///
    183191        bool operator!=(Arc) const { return true; }
    184192
    185193        /// Artificial ordering operator.
    186194
    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.
     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.
    192201        bool operator<(Arc) const { return false; }
    193202      };
    194203
    195       /// Iterator class for the outgoing arcs of a node.
     204      /// This iterator goes trough the outgoing arcs of a node.
    196205
    197206      /// This iterator goes trough the \e outgoing arcs of a certain node
    198207      /// of a digraph.
    199       /// Its usage is quite simple, for example, you can count the number
     208      /// Its usage is quite simple, for example you can count the number
    200209      /// of outgoing arcs of a node \c n
    201       /// in a digraph \c g of type \c %Digraph as follows.
     210      /// in digraph \c g of type \c Digraph as follows.
    202211      ///\code
    203212      /// int count=0;
    204       /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
     213      /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
    205214      ///\endcode
     215
    206216      class OutArcIt : public Arc {
    207217      public:
    208218        /// Default constructor
    209219
    210         /// Default constructor.
    211         /// \warning It sets the iterator to an undefined value.
     220        /// @warning The default constructor sets the iterator
     221        /// to an undefined value.
    212222        OutArcIt() { }
    213223        /// Copy constructor.
     
    216226        ///
    217227        OutArcIt(const OutArcIt& e) : Arc(e) { }
    218         /// %Invalid constructor \& conversion.
    219 
    220         /// Initializes the iterator to be invalid.
    221         /// \sa Invalid for more details.
     228        /// Initialize the iterator to be invalid.
     229
     230        /// Initialize the iterator to be invalid.
     231        ///
    222232        OutArcIt(Invalid) { }
    223         /// Sets the iterator to the first outgoing arc.
    224 
    225         /// Sets the iterator to the first outgoing arc of the given node.
    226         ///
     233        /// This constructor sets the iterator to the first outgoing arc.
     234
     235        /// This constructor sets the iterator to the first outgoing arc of
     236        /// the node.
    227237        OutArcIt(const Digraph&, const Node&) { }
    228         /// Sets the iterator to the given arc.
    229 
    230         /// Sets the iterator to the given arc of the given digraph.
    231         ///
     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.
    232243        OutArcIt(const Digraph&, const Arc&) { }
    233         /// Next outgoing arc
     244        ///Next outgoing arc
    234245
    235246        /// Assign the iterator to the next
     
    238249      };
    239250
    240       /// Iterator class for the incoming arcs of a node.
     251      /// This iterator goes trough the incoming arcs of a node.
    241252
    242253      /// This iterator goes trough the \e incoming arcs of a certain node
    243254      /// of a digraph.
    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.
     255      /// Its usage is quite simple, for example you can count the number
     256      /// of outgoing arcs of a node \c n
     257      /// in digraph \c g of type \c Digraph as follows.
    247258      ///\code
    248259      /// int count=0;
    249       /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
     260      /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
    250261      ///\endcode
     262
    251263      class InArcIt : public Arc {
    252264      public:
    253265        /// Default constructor
    254266
    255         /// Default constructor.
    256         /// \warning It sets the iterator to an undefined value.
     267        /// @warning The default constructor sets the iterator
     268        /// to an undefined value.
    257269        InArcIt() { }
    258270        /// Copy constructor.
     
    261273        ///
    262274        InArcIt(const InArcIt& e) : Arc(e) { }
    263         /// %Invalid constructor \& conversion.
    264 
    265         /// Initializes the iterator to be invalid.
    266         /// \sa Invalid for more details.
     275        /// Initialize the iterator to be invalid.
     276
     277        /// Initialize the iterator to be invalid.
     278        ///
    267279        InArcIt(Invalid) { }
    268         /// Sets the iterator to the first incoming arc.
    269 
    270         /// Sets the iterator to the first incoming arc of the given node.
    271         ///
     280        /// This constructor sets the iterator to first incoming arc.
     281
     282        /// This constructor set the iterator to the first incoming arc of
     283        /// the node.
    272284        InArcIt(const Digraph&, const Node&) { }
    273         /// Sets the iterator to the given arc.
    274 
    275         /// Sets the iterator to the given arc of the given digraph.
    276         ///
     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.
    277290        InArcIt(const Digraph&, const Arc&) { }
    278291        /// Next incoming arc
    279292
    280         /// Assign the iterator to the next
    281         /// incoming arc of the corresponding node.
     293        /// Assign the iterator to the next inarc of the corresponding node.
     294        ///
    282295        InArcIt& operator++() { return *this; }
    283296      };
    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:
     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:
    290302      ///\code
    291303      /// int count=0;
    292       /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
     304      /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
    293305      ///\endcode
    294306      class ArcIt : public Arc {
     
    296308        /// Default constructor
    297309
    298         /// Default constructor.
    299         /// \warning It sets the iterator to an undefined value.
     310        /// @warning The default constructor sets the iterator
     311        /// to an undefined value.
    300312        ArcIt() { }
    301313        /// Copy constructor.
     
    304316        ///
    305317        ArcIt(const ArcIt& e) : Arc(e) { }
    306         /// %Invalid constructor \& conversion.
    307 
    308         /// Initializes the iterator to be invalid.
    309         /// \sa Invalid for more details.
     318        /// Initialize the iterator to be invalid.
     319
     320        /// Initialize the iterator to be invalid.
     321        ///
    310322        ArcIt(Invalid) { }
    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         ///
     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.
    320333        ArcIt(const Digraph&, const Arc&) { }
    321         /// Next arc
     334        ///Next arc
    322335
    323336        /// Assign the iterator to the next arc.
    324         ///
    325337        ArcIt& operator++() { return *this; }
    326338      };
    327 
    328       /// \brief The source node of the arc.
    329       ///
    330       /// Returns the source node of the given arc.
     339      ///Gives back the target node of an arc.
     340
     341      ///Gives back the target node of an arc.
     342      ///
     343      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      ///
    331348      Node source(Arc) const { return INVALID; }
    332349
    333       /// \brief The target node of the arc.
    334       ///
    335       /// Returns the target node of the given arc.
    336       Node target(Arc) const { return INVALID; }
    337 
    338       /// \brief The ID of the node.
    339       ///
    340       /// Returns the ID of the given node.
     350      /// \brief Returns the ID of the node.
    341351      int id(Node) const { return -1; }
    342352
    343       /// \brief The ID of the arc.
    344       ///
    345       /// Returns the ID of the given arc.
     353      /// \brief Returns the ID of the arc.
    346354      int id(Arc) const { return -1; }
    347355
    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.
     356      /// \brief Returns the node with the given ID.
     357      ///
     358      /// \pre The argument should be a valid node ID in the graph.
    352359      Node nodeFromId(int) const { return INVALID; }
    353360
    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.
     361      /// \brief Returns the arc with the given ID.
     362      ///
     363      /// \pre The argument should be a valid arc ID in the graph.
    358364      Arc arcFromId(int) const { return INVALID; }
    359365
    360       /// \brief An upper bound on the node IDs.
    361       ///
    362       /// Returns an upper bound on the node IDs.
     366      /// \brief Returns an upper bound on the node IDs.
    363367      int maxNodeId() const { return -1; }
    364368
    365       /// \brief An upper bound on the arc IDs.
    366       ///
    367       /// Returns an upper bound on the arc IDs.
     369      /// \brief Returns an upper bound on the arc IDs.
    368370      int maxArcId() const { return -1; }
    369371
     
    391393      int maxId(Arc) const { return -1; }
    392394
    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 
    398395      /// \brief The base node of the iterator.
    399396      ///
    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; }
     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; }
    403400
    404401      /// \brief The running node of the iterator.
    405402      ///
    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; }
     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; }
    409406
    410407      /// \brief The base node of the iterator.
    411408      ///
    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; }
     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; }
    415412
    416413      /// \brief The running node of the iterator.
    417414      ///
    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.
     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.
    426427      template<class T>
    427428      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
    428429      public:
    429430
    430         /// Constructor
    431         explicit NodeMap(const Digraph&) { }
    432         /// Constructor with given initial value
     431        ///\e
     432        NodeMap(const Digraph&) { }
     433        ///\e
    433434        NodeMap(const Digraph&, T) { }
    434435
    435436      private:
    436437        ///Copy constructor
    437         NodeMap(const NodeMap& nm) :
     438        NodeMap(const NodeMap& nm) : 
    438439          ReferenceMap<Node, T, T&, const T&>(nm) { }
    439440        ///Assignment operator
     
    445446      };
    446447
    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.
     448      /// \brief Reference map of the arcs to type \c T.
     449      ///
     450      /// Reference map of the arcs to type \c T.
    451451      template<class T>
    452452      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
    453453      public:
    454454
    455         /// Constructor
    456         explicit ArcMap(const Digraph&) { }
    457         /// Constructor with given initial value
     455        ///\e
     456        ArcMap(const Digraph&) { }
     457        ///\e
    458458        ArcMap(const Digraph&, T) { }
    459 
    460459      private:
    461460        ///Copy constructor
  • lemon/concepts/graph.h

    r956 r704  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1919///\ingroup graph_concepts
    2020///\file
    21 ///\brief The concept of undirected graphs.
     21///\brief The concept of Undirected Graphs.
    2222
    2323#ifndef LEMON_CONCEPTS_GRAPH_H
     
    2525
    2626#include <lemon/concepts/graph_components.h>
    27 #include <lemon/concepts/maps.h>
    28 #include <lemon/concept_check.h>
    2927#include <lemon/core.h>
    3028
     
    3432    /// \ingroup graph_concepts
    3533    ///
    36     /// \brief Class describing the concept of undirected graphs.
     34    /// \brief Class describing the concept of Undirected Graphs.
    3735    ///
    38     /// This class describes the common interface of all undirected
    39     /// graphs.
     36    /// This class describes the common interface of all Undirected
     37    /// Graphs.
    4038    ///
    41     /// 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
     39    /// As all concept describing classes it provides only interface
     40    /// without any sensible implementation. So any algorithm for
     41    /// undirected graph should compile with this class, but it will not
    4442    /// run properly, of course.
    45     /// An actual graph implementation like \ref ListGraph or
    46     /// \ref SmartGraph may have additional functionality.
    4743    ///
    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.
     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.
    6153    ///
    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.
     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.
    6861    ///
    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
     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.
    7368    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 
    8169    public:
    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
     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
    9075      /// specializations for undirected graphs.
    9176      typedef True UndirectedTag;
    9277
    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.
     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.
    9885      class Node {
    9986      public:
    10087        /// Default constructor
    10188
    102         /// Default constructor.
    103         /// \warning It sets the object to an undefined value.
     89        /// @warning The default constructor sets the iterator
     90        /// to an undefined value.
    10491        Node() { }
    10592        /// Copy constructor.
     
    10996        Node(const Node&) { }
    11097
    111         /// %Invalid constructor \& conversion.
    112 
    113         /// Initializes the object to be invalid.
     98        /// Invalid constructor \& conversion.
     99
     100        /// This constructor initializes the iterator to be invalid.
    114101        /// \sa Invalid for more details.
    115102        Node(Invalid) { }
    116103        /// Equality operator
    117104
    118         /// Equality operator.
    119         ///
    120105        /// Two iterators are equal if and only if they point to the
    121         /// same object or both are \c INVALID.
     106        /// same object or both are invalid.
    122107        bool operator==(Node) const { return true; }
    123108
    124109        /// Inequality operator
    125110
    126         /// Inequality operator.
     111        /// \sa operator==(Node n)
     112        ///
    127113        bool operator!=(Node) const { return true; }
    128114
    129115        /// Artificial ordering operator.
    130116
    131         /// Artificial ordering operator.
    132         ///
    133         /// \note This operator only has to define some strict ordering of
     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
    134121        /// the items; this order has nothing to do with the iteration
    135122        /// ordering of the items.
     
    138125      };
    139126
    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:
     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 number
     131      /// of nodes in graph \c g of type \c Graph like this:
    145132      ///\code
    146133      /// int count=0;
     
    151138        /// Default constructor
    152139
    153         /// Default constructor.
    154         /// \warning It sets the iterator to an undefined value.
     140        /// @warning The default constructor sets the iterator
     141        /// to an undefined value.
    155142        NodeIt() { }
    156143        /// Copy constructor.
     
    159146        ///
    160147        NodeIt(const NodeIt& n) : Node(n) { }
    161         /// %Invalid constructor \& conversion.
    162 
    163         /// Initializes the iterator to be invalid.
     148        /// Invalid constructor \& conversion.
     149
     150        /// Initialize the iterator to be invalid.
    164151        /// \sa Invalid for more details.
    165152        NodeIt(Invalid) { }
    166153        /// Sets the iterator to the first node.
    167154
    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         ///
     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.
    175164        NodeIt(const Graph&, const Node&) { }
    176165        /// Next node.
     
    182171
    183172
    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.
     173      /// The base type of the edge iterators.
     174
     175      /// The base type of the edge iterators.
     176      ///
    189177      class Edge {
    190178      public:
    191179        /// Default constructor
    192180
    193         /// Default constructor.
    194         /// \warning It sets the object to an undefined value.
     181        /// @warning The default constructor sets the iterator
     182        /// to an undefined value.
    195183        Edge() { }
    196184        /// Copy constructor.
     
    199187        ///
    200188        Edge(const Edge&) { }
    201         /// %Invalid constructor \& conversion.
    202 
    203         /// Initializes the object to be invalid.
    204         /// \sa Invalid for more details.
     189        /// Initialize the iterator to be invalid.
     190
     191        /// Initialize the iterator to be invalid.
     192        ///
    205193        Edge(Invalid) { }
    206194        /// Equality operator
    207195
    208         /// Equality operator.
    209         ///
    210196        /// Two iterators are equal if and only if they point to the
    211         /// same object or both are \c INVALID.
     197        /// same object or both are invalid.
    212198        bool operator==(Edge) const { return true; }
    213199        /// Inequality operator
    214200
    215         /// Inequality operator.
     201        /// \sa operator==(Edge n)
     202        ///
    216203        bool operator!=(Edge) const { return true; }
    217204
    218205        /// Artificial ordering operator.
    219206
    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.
     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.
    225213        bool operator<(Edge) const { return false; }
    226214      };
    227215
    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:
     216      /// This iterator goes through each edge.
     217
     218      /// This iterator goes through each edge of a graph.
     219      /// Its usage is quite simple, for example you can count the number
     220      /// of edges in a graph \c g of type \c Graph as follows:
    233221      ///\code
    234222      /// int count=0;
     
    239227        /// Default constructor
    240228
    241         /// Default constructor.
    242         /// \warning It sets the iterator to an undefined value.
     229        /// @warning The default constructor sets the iterator
     230        /// to an undefined value.
    243231        EdgeIt() { }
    244232        /// Copy constructor.
     
    247235        ///
    248236        EdgeIt(const EdgeIt& e) : Edge(e) { }
    249         /// %Invalid constructor \& conversion.
    250 
    251         /// Initializes the iterator to be invalid.
    252         /// \sa Invalid for more details.
     237        /// Initialize the iterator to be invalid.
     238
     239        /// Initialize the iterator to be invalid.
     240        ///
    253241        EdgeIt(Invalid) { }
    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         ///
     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.
    263252        EdgeIt(const Graph&, const Edge&) { }
    264253        /// Next edge
    265254
    266255        /// Assign the iterator to the next edge.
    267         ///
    268256        EdgeIt& operator++() { return *this; }
    269257      };
    270258
    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.
     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.
    278269      ///
    279270      ///\code
     
    281272      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    282273      ///\endcode
    283       ///
    284       /// \warning Loop edges will be iterated twice.
    285274      class IncEdgeIt : public Edge {
    286275      public:
    287276        /// Default constructor
    288277
    289         /// Default constructor.
    290         /// \warning It sets the iterator to an undefined value.
     278        /// @warning The default constructor sets the iterator
     279        /// to an undefined value.
    291280        IncEdgeIt() { }
    292281        /// Copy constructor.
     
    295284        ///
    296285        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
    297         /// %Invalid constructor \& conversion.
    298 
    299         /// Initializes the iterator to be invalid.
    300         /// \sa Invalid for more details.
     286        /// Initialize the iterator to be invalid.
     287
     288        /// Initialize the iterator to be invalid.
     289        ///
    301290        IncEdgeIt(Invalid) { }
    302         /// Sets the iterator to the first incident edge.
    303 
    304         /// Sets the iterator to the first incident edge of the given node.
    305         ///
     291        /// This constructor sets the iterator to first incident arc.
     292
     293        /// This constructor set the iterator to the first incident arc of
     294        /// the node.
    306295        IncEdgeIt(const Graph&, const Node&) { }
    307         /// Sets the iterator to the given edge.
    308 
    309         /// Sets the iterator to the given edge of the given graph.
    310         ///
     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.
    311301        IncEdgeIt(const Graph&, const Edge&) { }
    312         /// Next incident edge
    313 
    314         /// Assign the iterator to the next incident edge
     302        /// Next incident arc
     303
     304        /// Assign the iterator to the next incident arc
    315305        /// of the corresponding node.
    316306        IncEdgeIt& operator++() { return *this; }
    317307      };
    318308
    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.
     309      /// The directed arc type.
     310
     311      /// The directed arc type. It can be converted to the
     312      /// edge or it should be inherited from the undirected
     313      /// edge.
    324314      class Arc {
    325315      public:
    326316        /// Default constructor
    327317
    328         /// Default constructor.
    329         /// \warning It sets the object to an undefined value.
     318        /// @warning The default constructor sets the iterator
     319        /// to an undefined value.
    330320        Arc() { }
    331321        /// Copy constructor.
     
    334324        ///
    335325        Arc(const Arc&) { }
    336         /// %Invalid constructor \& conversion.
    337 
    338         /// Initializes the object to be invalid.
    339         /// \sa Invalid for more details.
     326        /// Initialize the iterator to be invalid.
     327
     328        /// Initialize the iterator to be invalid.
     329        ///
    340330        Arc(Invalid) { }
    341331        /// Equality operator
    342332
    343         /// Equality operator.
    344         ///
    345333        /// Two iterators are equal if and only if they point to the
    346         /// same object or both are \c INVALID.
     334        /// same object or both are invalid.
    347335        bool operator==(Arc) const { return true; }
    348336        /// Inequality operator
    349337
    350         /// Inequality operator.
     338        /// \sa operator==(Arc n)
     339        ///
    351340        bool operator!=(Arc) const { return true; }
    352341
    353342        /// Artificial ordering operator.
    354343
    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.
     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.
    360350        bool operator<(Arc) const { return false; }
    361351
    362         /// Converison to \c Edge
    363 
    364         /// Converison to \c Edge.
    365         ///
     352        /// Converison to Edge
    366353        operator Edge() const { return Edge(); }
    367354      };
    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:
     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:
    374360      ///\code
    375361      /// int count=0;
    376       /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
     362      /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
    377363      ///\endcode
    378364      class ArcIt : public Arc {
     
    380366        /// Default constructor
    381367
    382         /// Default constructor.
    383         /// \warning It sets the iterator to an undefined value.
     368        /// @warning The default constructor sets the iterator
     369        /// to an undefined value.
    384370        ArcIt() { }
    385371        /// Copy constructor.
     
    388374        ///
    389375        ArcIt(const ArcIt& e) : Arc(e) { }
    390         /// %Invalid constructor \& conversion.
    391 
    392         /// Initializes the iterator to be invalid.
    393         /// \sa Invalid for more details.
     376        /// Initialize the iterator to be invalid.
     377
     378        /// Initialize the iterator to be invalid.
     379        ///
    394380        ArcIt(Invalid) { }
    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         ///
     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.
    404391        ArcIt(const Graph&, const Arc&) { }
    405         /// Next arc
     392        ///Next arc
    406393
    407394        /// Assign the iterator to the next arc.
    408         ///
    409395        ArcIt& operator++() { return *this; }
    410396      };
    411397
    412       /// 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
     398      /// This iterator goes trough the outgoing directed arcs of a node.
     399
     400      /// This iterator goes trough the \e outgoing arcs of a certain node
     401      /// of a graph.
     402      /// Its usage is quite simple, for example you can count the number
    417403      /// of outgoing arcs of a node \c n
    418       /// in a graph \c g of type \c %Graph as follows.
     404      /// in graph \c g of type \c Graph as follows.
    419405      ///\code
    420406      /// int count=0;
    421       /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
     407      /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
    422408      ///\endcode
     409
    423410      class OutArcIt : public Arc {
    424411      public:
    425412        /// Default constructor
    426413
    427         /// Default constructor.
    428         /// \warning It sets the iterator to an undefined value.
     414        /// @warning The default constructor sets the iterator
     415        /// to an undefined value.
    429416        OutArcIt() { }
    430417        /// Copy constructor.
     
    433420        ///
    434421        OutArcIt(const OutArcIt& e) : Arc(e) { }
    435         /// %Invalid constructor \& conversion.
    436 
    437         /// Initializes the iterator to be invalid.
    438         /// \sa Invalid for more details.
     422        /// Initialize the iterator to be invalid.
     423
     424        /// Initialize the iterator to be invalid.
     425        ///
    439426        OutArcIt(Invalid) { }
    440         /// Sets the iterator to the first outgoing arc.
    441 
    442         /// Sets the iterator to the first outgoing arc of the given node.
    443         ///
     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
    444433        OutArcIt(const Graph& n, const Node& g) {
    445434          ignore_unused_variable_warning(n);
    446435          ignore_unused_variable_warning(g);
    447436        }
    448         /// Sets the iterator to the given arc.
    449 
    450         /// Sets the iterator to the given arc of the given graph.
    451         ///
     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.
    452442        OutArcIt(const Graph&, const Arc&) { }
    453         /// Next outgoing arc
     443        ///Next outgoing arc
    454444
    455445        /// Assign the iterator to the next
     
    458448      };
    459449
    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.
     450      /// This iterator goes trough the incoming directed arcs of a node.
     451
     452      /// This iterator goes trough the \e incoming arcs of a certain node
     453      /// of a graph.
     454      /// Its usage is quite simple, for example you can count the number
     455      /// of outgoing arcs of a node \c n
     456      /// in graph \c g of type \c Graph as follows.
    467457      ///\code
    468458      /// int count=0;
    469       /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
     459      /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
    470460      ///\endcode
     461
    471462      class InArcIt : public Arc {
    472463      public:
    473464        /// Default constructor
    474465
    475         /// Default constructor.
    476         /// \warning It sets the iterator to an undefined value.
     466        /// @warning The default constructor sets the iterator
     467        /// to an undefined value.
    477468        InArcIt() { }
    478469        /// Copy constructor.
     
    481472        ///
    482473        InArcIt(const InArcIt& e) : Arc(e) { }
    483         /// %Invalid constructor \& conversion.
    484 
    485         /// Initializes the iterator to be invalid.
    486         /// \sa Invalid for more details.
     474        /// Initialize the iterator to be invalid.
     475
     476        /// Initialize the iterator to be invalid.
     477        ///
    487478        InArcIt(Invalid) { }
    488         /// Sets the iterator to the first incoming arc.
    489 
    490         /// Sets the iterator to the first incoming arc of the given node.
    491         ///
     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
    492485        InArcIt(const Graph& g, const Node& n) {
    493486          ignore_unused_variable_warning(n);
    494487          ignore_unused_variable_warning(g);
    495488        }
    496         /// Sets the iterator to the given arc.
    497 
    498         /// Sets the iterator to the given arc of the given graph.
    499         ///
     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.
    500494        InArcIt(const Graph&, const Arc&) { }
    501495        /// Next incoming arc
    502496
    503         /// Assign the iterator to the next
    504         /// incoming arc of the corresponding node.
     497        /// Assign the iterator to the next inarc of the corresponding node.
     498        ///
    505499        InArcIt& operator++() { return *this; }
    506500      };
    507501
    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.
     502      /// \brief Reference map of the nodes to type \c T.
     503      ///
     504      /// Reference map of the nodes to type \c T.
    512505      template<class T>
    513506      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
     
    515508      public:
    516509
    517         /// Constructor
    518         explicit NodeMap(const Graph&) { }
    519         /// Constructor with given initial value
     510        ///\e
     511        NodeMap(const Graph&) { }
     512        ///\e
    520513        NodeMap(const Graph&, T) { }
    521514
     
    532525      };
    533526
    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.
     527      /// \brief Reference map of the arcs to type \c T.
     528      ///
     529      /// Reference map of the arcs to type \c T.
    538530      template<class T>
    539531      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
     
    541533      public:
    542534
    543         /// Constructor
    544         explicit ArcMap(const Graph&) { }
    545         /// Constructor with given initial value
     535        ///\e
     536        ArcMap(const Graph&) { }
     537        ///\e
    546538        ArcMap(const Graph&, T) { }
    547 
    548539      private:
    549540        ///Copy constructor
     
    558549      };
    559550
    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.
     551      /// Reference map of the edges to type \c T.
     552
     553      /// Reference map of the edges to type \c T.
    564554      template<class T>
    565555      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
     
    567557      public:
    568558
    569         /// Constructor
    570         explicit EdgeMap(const Graph&) { }
    571         /// Constructor with given initial value
     559        ///\e
     560        EdgeMap(const Graph&) { }
     561        ///\e
    572562        EdgeMap(const Graph&, T) { }
    573 
    574563      private:
    575564        ///Copy constructor
     
    584573      };
    585574
    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.
     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.
    595619      /// \sa v()
    596620      /// \sa direction()
    597621      Node u(Edge) const { return INVALID; }
    598622
    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.
     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.
    608633      /// \sa u()
    609634      /// \sa direction()
    610635      Node v(Edge) const { return INVALID; }
    611636
    612       /// \brief The source node of the arc.
    613       ///
    614       /// Returns the source node of the given arc.
     637      /// \brief Source node of the directed arc.
    615638      Node source(Arc) const { return INVALID; }
    616639
    617       /// \brief The target node of the arc.
    618       ///
    619       /// Returns the target node of the given arc.
     640      /// \brief Target node of the directed arc.
    620641      Node target(Arc) const { return INVALID; }
    621642
    622       /// \brief The ID of the node.
    623       ///
    624       /// Returns the ID of the given node.
     643      /// \brief Returns the id of the node.
    625644      int id(Node) const { return -1; }
    626645
    627       /// \brief The ID of the edge.
    628       ///
    629       /// Returns the ID of the given edge.
     646      /// \brief Returns the id of the edge.
    630647      int id(Edge) const { return -1; }
    631648
    632       /// \brief The ID of the arc.
    633       ///
    634       /// Returns the ID of the given arc.
     649      /// \brief Returns the id of the arc.
    635650      int id(Arc) const { return -1; }
    636651
    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.
     652      /// \brief Returns the node with the given id.