COIN-OR::LEMON - Graph Library

Ignore:
Files:
29 deleted
108 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

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

    r791 r727  
    3535CHECK_TYPE_SIZE("long long" LONG_LONG)
    3636SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
    37 
    38 INCLUDE(FindPythonInterp)
    3937
    4038ENABLE_TESTING()
  • 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

    r962 r712  
    1 2010-03-19 Version 1.2 released
    2 
    3         This is major feature release
    4 
    5         * New algorithms
    6           * Bellman-Ford algorithm (#51)
    7           * Minimum mean cycle algorithms (#179)
    8             * Karp, Hartman-Orlin and Howard algorithms
    9           * New minimum cost flow algorithms (#180)
    10             * Cost Scaling algorithms
    11             * Capacity Scaling algorithm
    12             * Cycle-Canceling algorithms
    13           * Planarity related algorithms (#62)
    14             * Planarity checking algorithm
    15             * Planar embedding algorithm
    16             * Schnyder's planar drawing algorithm
    17             * Coloring planar graphs with five or six colors
    18           * Fractional matching algorithms (#314)
    19         * New data structures
    20           * StaticDigraph structure (#68)
    21           * Several new priority queue structures (#50, #301)
    22             * Fibonacci, Radix, Bucket, Pairing, Binomial
    23               D-ary and fourary heaps (#301)
    24           * Iterable map structures (#73)
    25         * Other new tools and functionality
    26           * Map utility functions (#320)
    27           * Reserve functions are added to ListGraph and SmartGraph (#311)
    28           * A resize() function is added to HypercubeGraph (#311)
    29           * A count() function is added to CrossRefMap (#302)
    30           * Support for multiple targets in Suurballe using fullInit() (#181)
    31           * Traits class and named parameters for Suurballe (#323)
    32           * Separate reset() and resetParams() functions in NetworkSimplex
    33             to handle graph changes (#327)
    34           * tolerance() functions are added to HaoOrlin (#306)
    35         * Implementation improvements
    36           * Improvements in weighted matching algorithms (#314)
    37             * Jumpstart initialization
    38           * ArcIt iteration is based on out-arc lists instead of in-arc lists
    39             in ListDigraph (#311)
    40           * Faster add row operation in CbcMip (#203)
    41           * Better implementation for split() in ListDigraph (#311)
    42           * ArgParser can also throw exception instead of exit(1) (#332)
    43         * Miscellaneous
    44           * A simple interactive bootstrap script
    45           * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,
    46                 #316,#319)
    47             * BibTeX references in the doc (#184)
    48           * Optionally use valgrind when running tests
    49           * Also check ReferenceMapTag in concept checks (#312)
    50           * dimacs-solver uses long long type by default.
    51         * Several bugfixes (compared to release 1.1):
    52           #295: Suppress MSVC warnings using pragmas
    53           ----: Various CMAKE related improvements
    54                 * Remove duplications from doc/CMakeLists.txt
    55                 * Rename documentation install folder from 'docs' to 'html'
    56                 * Add tools/CMakeLists.txt to the tarball
    57                 * Generate and install LEMONConfig.cmake
    58                 * Change the label of the html project in Visual Studio
    59                 * Fix the check for the 'long long' type
    60                 * Put the version string into config.h
    61                 * Minor CMake improvements
    62                 * Set the version to 'hg-tip' if everything fails
    63           #311: Add missing 'explicit' keywords
    64           #302: Fix the implementation and doc of CrossRefMap
    65           #308: Remove duplicate list_graph.h entry from source list
    66           #307: Bugfix in Preflow and Circulation
    67           #305: Bugfix and extension in the rename script
    68           #312: Also check ReferenceMapTag in concept checks
    69           #250: Bugfix in pathSource() and pathTarget()
    70           #321: Use pathCopy(from,to) instead of copyPath(to,from)
    71           #322: Distribure LEMONConfig.cmake.in
    72           #330: Bug fix in map_extender.h
    73           #336: Fix the date field comment of graphToEps() output
    74           #323: Bug fix in Suurballe
    75           #335: Fix clear() function in ExtendFindEnum
    76           #337: Use void* as the LPX object pointer
    77           #317: Fix (and improve) error message in mip_test.cc
    78                 Remove unnecessary OsiCbc dependency
    79           #356: Allow multiple executions of weighted matching algorithms (#356)
    80 
    8112009-05-13 Version 1.1 released
    822
     
    15373          ----: Add missing unistd.h include to time_measure.h
    15474          #204: Compilation bug fixed in graph_to_eps.h with VS2005
    155           #214,#215: windows.h should never be included by LEMON headers
     75          #214,#215: windows.h should never be included by lemon headers
    15676          #230: Build systems check the availability of 'long long' type
    15777          #229: Default implementation of Tolerance<> is used for integer types
     
    175952008-10-13 Version 1.0 released
    17696
    177         This is the first stable release of LEMON. Compared to the 0.x
    178         release series, it features a considerably smaller but more
    179         matured set of tools. The API has also completely revised and
    180         changed in several places.
     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.
    181101
    182         * 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
    183103          Migration Guide in the doc for more details)
    184104          * Graph -> Digraph, UGraph -> Graph
    185105          * Edge -> Arc, UEdge -> Edge
    186           * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
    187         * Other improvements
    188           * Better documentation
    189           * Reviewed and cleaned up codebase
    190           * CMake based build system (along with the autotools based one)
    191         * Contents of the library (ported from 0.x)
    192           * Algorithms
    193             * breadth-first search (bfs.h)
    194             * depth-first search (dfs.h)
    195             * Dijkstra's algorithm (dijkstra.h)
    196             * Kruskal's algorithm (kruskal.h)
    197           * Data structures
    198             * graph data structures (list_graph.h, smart_graph.h)
    199             * path data structures (path.h)
    200             * binary heap data structure (bin_heap.h)
    201             * union-find data structures (unionfind.h)
    202             * miscellaneous property maps (maps.h)
    203             * two dimensional vector and bounding box (dim2.h)
     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)
    204124          * Concepts
    205             * graph structure concepts (concepts/digraph.h, concepts/graph.h,
     125            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
    206126              concepts/graph_components.h)
    207             * concepts for other structures (concepts/heap.h, concepts/maps.h,
    208               concepts/path.h)
    209           * Tools
    210             * Mersenne twister random number generator (random.h)
    211             * tools for measuring cpu and wall clock time (time_measure.h)
    212             * tools for counting steps and events (counter.h)
    213             * tool for parsing command line arguments (arg_parser.h)
    214             * tool for visualizing graphs (graph_to_eps.h)
    215             * tools for reading and writing data in LEMON Graph Format
     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
    216136              (lgf_reader.h, lgf_writer.h)
    217137            * tools to handle the anomalies of calculations with
    218               floating point numbers (tolerance.h)
     138              floating point numbers (tolerance.h)
    219139            * tools to manage RGB colors (color.h)
    220           * Infrastructure
    221             * extended assertion handling (assert.h)
    222             * exception classes and error handling (error.h)
    223             * concept checking (concept_check.h)
    224             * commonly used mathematical constants (math.h)
     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

    r840 r727  
    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.
     
    144128echo
    145129echo Build additional tools........ : $enable_tools
    146 echo Use valgrind for tests........ : $use_valgrind
    147130echo
    148131echo 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

    r943 r726  
    1010)
    1111
    12 IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
     12IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
    1313  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
    1414  SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
     
    2121    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
    2222    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
    23     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
    2423    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
    2524    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
     
    2827    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
    2928    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
    30     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
    3129    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
    3230    COMMAND ${CMAKE_COMMAND} -E remove_directory html
    33     COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
    3431    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    3532    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
  • doc/Doxyfile.in

    r803 r379  
    1 # Doxyfile 1.5.9
     1# Doxyfile 1.5.7.1
    22
    33#---------------------------------------------------------------------------
     
    2222QT_AUTOBRIEF           = NO
    2323MULTILINE_CPP_IS_BRIEF = NO
     24DETAILS_AT_TOP         = YES
    2425INHERIT_DOCS           = NO
    2526SEPARATE_MEMBER_PAGES  = NO
     
    9192                         "@abs_top_srcdir@/demo" \
    9293                         "@abs_top_srcdir@/tools" \
    93                          "@abs_top_srcdir@/test/test_tools.h" \
    94                          "@abs_top_builddir@/doc/references.dox"
     94                         "@abs_top_srcdir@/test/test_tools.h"
    9595INPUT_ENCODING         = UTF-8
    9696FILE_PATTERNS          = *.h \
     
    224224SKIP_FUNCTION_MACROS   = YES
    225225#---------------------------------------------------------------------------
    226 # Options related to the search engine   
     226# Configuration::additions related to external references   
    227227#---------------------------------------------------------------------------
    228228TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
  • doc/Makefile.am

    r943 r720  
    2828        connected_components.eps \
    2929        edge_biconnected_components.eps \
    30         matching.eps \
    3130        node_biconnected_components.eps \
    32         planar.eps \
    3331        strongly_connected_components.eps
    3432
     
    6967        fi
    7068
    71 references.dox: doc/references.bib
    72         if test ${python_found} = yes; then \
    73           cd doc; \
    74           python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \
    75           cd ..; \
    76         else \
    77           echo; \
    78           echo "Python not found."; \
    79           echo; \
    80           exit 1; \
    81         fi
    82 
    83 html-local: $(DOC_PNG_IMAGES) references.dox
     69html-local: $(DOC_PNG_IMAGES)
    8470        if test ${doxygen_found} = yes; then \
    8571          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/mainpage.dox

    r956 r705  
    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

    r953 r714  
    5858        lemon/arg_parser.h \
    5959        lemon/assert.h \
    60         lemon/bellman_ford.h \
    6160        lemon/bfs.h \
    6261        lemon/bin_heap.h \
    63         lemon/binomial_heap.h \
    64         lemon/bucket_heap.h \
    65         lemon/capacity_scaling.h \
    6662        lemon/cbc.h \
    6763        lemon/circulation.h \
     
    7066        lemon/concept_check.h \
    7167        lemon/connectivity.h \
     68        lemon/counter.h \
    7269        lemon/core.h \
    73         lemon/cost_scaling.h \
    74         lemon/counter.h \
    7570        lemon/cplex.h \
    76         lemon/cycle_canceling.h \
    7771        lemon/dfs.h \
    78         lemon/dheap.h \
    7972        lemon/dijkstra.h \
    8073        lemon/dim2.h \
     
    8477        lemon/error.h \
    8578        lemon/euler.h \
    86         lemon/fib_heap.h \
    87         lemon/fractional_matching.h \
    8879        lemon/full_graph.h \
    8980        lemon/glpk.h \
     
    9182        lemon/graph_to_eps.h \
    9283        lemon/grid_graph.h \
    93         lemon/hartmann_orlin_mmc.h \
    94         lemon/howard_mmc.h \
    9584        lemon/hypercube_graph.h \
    96         lemon/karp_mmc.h \
    9785        lemon/kruskal.h \
    9886        lemon/hao_orlin.h \
     
    10391        lemon/lp_base.h \
    10492        lemon/lp_skeleton.h \
     93        lemon/list_graph.h \
    10594        lemon/maps.h \
    10695        lemon/matching.h \
     
    10998        lemon/nauty_reader.h \
    11099        lemon/network_simplex.h \
    111         lemon/pairing_heap.h \
    112100        lemon/path.h \
    113         lemon/planarity.h \
    114101        lemon/preflow.h \
    115         lemon/quad_heap.h \
    116         lemon/radix_heap.h \
    117102        lemon/radix_sort.h \
    118103        lemon/random.h \
    119104        lemon/smart_graph.h \
    120105        lemon/soplex.h \
    121         lemon/static_graph.h \
    122106        lemon/suurballe.h \
    123107        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 r631  
    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
     32  ///\ingroup auxdat
    3333  ///
    34   /// \brief Binary heap data structure.
     34  ///\brief A Binary Heap implementation.
    3535  ///
    36   /// This class implements the \e binary \e heap data structure.
    37   /// It fully conforms to the \ref concepts::Heap "heap concept".
     36  ///This class implements the \e binary \e heap data structure.
     37  ///
     38  ///A \e heap is a data structure for storing items with specified values
     39  ///called \e priorities in such a way that finding the item with minimum
     40  ///priority is efficient. \c Comp specifies the ordering of the priorities.
     41  ///In a heap one can change the priority of an item, add or erase an
     42  ///item, etc.
    3843  ///
    39   /// \tparam PR Type of the priorities of the items.
    40   /// \tparam IM A read-writable item map with \c int values, used
    41   /// internally to handle the cross references.
    42   /// \tparam CMP A functor class for comparing the priorities.
    43   /// The default is \c std::less<PR>.
    44 #ifdef DOXYGEN
    45   template <typename PR, typename IM, typename CMP>
    46 #else
    47   template <typename PR, typename IM, typename CMP = std::less<PR> >
    48 #endif
     44  ///\tparam PR Type of the priority of the items.
     45  ///\tparam IM A read and writable item map with int values, used internally
     46  ///to handle the cross references.
     47  ///\tparam Comp A functor class for the ordering of the priorities.
     48  ///The default is \c std::less<PR>.
     49  ///
     50  ///\sa FibHeap
     51  ///\sa Dijkstra
     52  template <typename PR, typename IM, typename Comp = std::less<PR> >
    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.
    61     typedef CMP Compare;
    62 
    63     /// \brief Type to represent the states of the items.
    64     ///
    65     /// Each item has a state associated to it. It can be "in heap",
    66     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     64    ///\e
     65    typedef Comp Compare;
     66
     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

    r968 r664  
    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();
     
    281281    typedef EdgeSetExtender Graph;
    282282
    283     typedef True UndirectedTag;
    284 
    285283    typedef typename Parent::Node Node;
    286284    typedef typename Parent::Arc Arc;
     
    313311    Node oppositeNode(const Node &n, const Edge &e) const {
    314312      if( n == Parent::u(e))
    315         return Parent::v(e);
     313        return Parent::v(e);
    316314      else if( n == Parent::v(e))
    317         return Parent::u(e);
     315        return Parent::u(e);
    318316      else
    319         return INVALID;
     317        return INVALID;
    320318    }
    321319
     
    341339
    342340    using Parent::notifier;
    343 
     341   
    344342    ArcNotifier& notifier(Arc) const {
    345343      return arc_notifier;
     
    351349
    352350
    353     class NodeIt : public Node {
     351    class NodeIt : public Node { 
    354352      const Graph* graph;
    355353    public:
     
    360358
    361359      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 {
     360        _graph.first(static_cast<Node&>(*this));
     361      }
     362
     363      NodeIt(const Graph& _graph, const Node& node) 
     364        : Node(node), graph(&_graph) {}
     365
     366      NodeIt& operator++() { 
     367        graph->next(*this);
     368        return *this;
     369      }
     370
     371    };
     372
     373
     374    class ArcIt : public Arc { 
    377375      const Graph* graph;
    378376    public:
     
    383381
    384382      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 {
     383        _graph.first(static_cast<Arc&>(*this));
     384      }
     385
     386      ArcIt(const Graph& _graph, const Arc& e) : 
     387        Arc(e), graph(&_graph) { }
     388
     389      ArcIt& operator++() { 
     390        graph->next(*this);
     391        return *this;
     392      }
     393
     394    };
     395
     396
     397    class OutArcIt : public Arc { 
    400398      const Graph* graph;
    401399    public:
     
    405403      OutArcIt(Invalid i) : Arc(i) { }
    406404
    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 {
     405      OutArcIt(const Graph& _graph, const Node& node) 
     406        : graph(&_graph) {
     407        _graph.firstOut(*this, node);
     408      }
     409
     410      OutArcIt(const Graph& _graph, const Arc& arc) 
     411        : Arc(arc), graph(&_graph) {}
     412
     413      OutArcIt& operator++() { 
     414        graph->nextOut(*this);
     415        return *this;
     416      }
     417
     418    };
     419
     420
     421    class InArcIt : public Arc { 
    424422      const Graph* graph;
    425423    public:
     
    429427      InArcIt(Invalid i) : Arc(i) { }
    430428
    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 {
     429      InArcIt(const Graph& _graph, const Node& node) 
     430        : graph(&_graph) {
     431        _graph.firstIn(*this, node);
     432      }
     433
     434      InArcIt(const Graph& _graph, const Arc& arc) : 
     435        Arc(arc), graph(&_graph) {}
     436
     437      InArcIt& operator++() { 
     438        graph->nextIn(*this);
     439        return *this;
     440      }
     441
     442    };
     443
     444
     445    class EdgeIt : public Parent::Edge { 
    448446      const Graph* graph;
    449447    public:
     
    454452
    455453      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;
     454        _graph.first(static_cast<Edge&>(*this));
     455      }
     456
     457      EdgeIt(const Graph& _graph, const Edge& e) : 
     458        Edge(e), graph(&_graph) { }
     459
     460      EdgeIt& operator++() { 
     461        graph->next(*this);
     462        return *this;
    465463      }
    466464
     
    478476
    479477      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
    480         _graph.firstInc(*this, direction, n);
     478        _graph.firstInc(*this, direction, n);
    481479      }
    482480
    483481      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
    484         : graph(&_graph), Edge(ue) {
    485         direction = (_graph.source(ue) == n);
     482        : graph(&_graph), Edge(ue) {
     483        direction = (_graph.source(ue) == n);
    486484      }
    487485
    488486      IncEdgeIt& operator++() {
    489         graph->nextInc(*this, direction);
    490         return *this;
     487        graph->nextInc(*this, direction);
     488        return *this;
    491489      }
    492490    };
     
    535533
    536534    template <typename _Value>
    537     class ArcMap
     535    class ArcMap 
    538536      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    539537      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    540538
    541539    public:
    542       explicit ArcMap(const Graph& _g)
    543         : Parent(_g) {}
    544       ArcMap(const Graph& _g, const _Value& _v)
    545         : Parent(_g, _v) {}
     540      ArcMap(const Graph& _g)
     541        : Parent(_g) {}
     542      ArcMap(const Graph& _g, const _Value& _v) 
     543        : Parent(_g, _v) {}
    546544
    547545      ArcMap& operator=(const ArcMap& cmap) {
    548         return operator=<ArcMap>(cmap);
     546        return operator=<ArcMap>(cmap);
    549547      }
    550548
     
    552550      ArcMap& operator=(const CMap& cmap) {
    553551        Parent::operator=(cmap);
    554         return *this;
     552        return *this;
    555553      }
    556554
     
    559557
    560558    template <typename _Value>
    561     class EdgeMap
     559    class EdgeMap 
    562560      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    563561      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    564562
    565563    public:
    566       explicit EdgeMap(const Graph& _g)
    567         : Parent(_g) {}
    568 
    569       EdgeMap(const Graph& _g, const _Value& _v)
    570         : Parent(_g, _v) {}
     564      EdgeMap(const Graph& _g)
     565        : Parent(_g) {}
     566
     567      EdgeMap(const Graph& _g, const _Value& _v) 
     568        : Parent(_g, _v) {}
    571569
    572570      EdgeMap& operator=(const EdgeMap& cmap) {
    573         return operator=<EdgeMap>(cmap);
     571        return operator=<EdgeMap>(cmap);
    574572      }
    575573
     
    577575      EdgeMap& operator=(const CMap& cmap) {
    578576        Parent::operator=(cmap);
    579         return *this;
     577        return *this;
    580578      }
    581579
     
    594592      return edge;
    595593    }
    596 
     594   
    597595    void clear() {
    598596      notifier(Arc()).clear();
     
    620618      arc_notifier.clear();
    621619    }
    622 
     620   
    623621  };
    624622
  • lemon/bits/graph_adaptor_extender.h

    r965 r664  
    182182    typedef GraphAdaptorExtender Adaptor;
    183183
    184     typedef True UndirectedTag;
    185 
    186184    typedef typename Parent::Node Node;
    187185    typedef typename Parent::Arc Arc;
  • lemon/bits/graph_extender.h

    r825 r664  
    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    }
     
    605605
    606606    public:
    607       explicit NodeMap(const Graph& graph)
     607      NodeMap(const Graph& graph)
    608608        : Parent(graph) {}
    609609      NodeMap(const Graph& graph, const _Value& value)
     
    629629
    630630    public:
    631       explicit ArcMap(const Graph& graph)
     631      ArcMap(const Graph& graph)
    632632        : Parent(graph) {}
    633633      ArcMap(const Graph& graph, const _Value& value)
     
    653653
    654654    public:
    655       explicit EdgeMap(const Graph& graph)
     655      EdgeMap(const Graph& graph)
    656656        : Parent(graph) {}
    657657
  • lemon/bits/map_extender.h

    r867 r664  
    5050    typedef typename Parent::ConstReference ConstReference;
    5151
    52     typedef typename Parent::ReferenceMapTag ReferenceMapTag;
    53 
    5452    class MapIt;
    5553    class ConstMapIt;
     
    8583      typedef typename Map::Value Value;
    8684
    87       MapIt() : map(NULL) {}
    88 
    89       MapIt(Invalid i) : Parent(i), map(NULL) {}
    90 
    91       explicit MapIt(Map& _map) : map(&_map) {
    92         map->notifier()->first(*this);
     85      MapIt() {}
     86
     87      MapIt(Invalid i) : Parent(i) { }
     88
     89      explicit MapIt(Map& _map) : map(_map) {
     90        map.notifier()->first(*this);
    9391      }
    9492
    9593      MapIt(const Map& _map, const Item& item)
    96         : Parent(item), map(&_map) {}
     94        : Parent(item), map(_map) {}
    9795
    9896      MapIt& operator++() {
    99         map->notifier()->next(*this);
     97        map.notifier()->next(*this);
    10098        return *this;
    10199      }
    102100
    103101      typename MapTraits<Map>::ConstReturnValue operator*() const {
    104         return (*map)[*this];
     102        return map[*this];
    105103      }
    106104
    107105      typename MapTraits<Map>::ReturnValue operator*() {
    108         return (*map)[*this];
     106        return map[*this];
    109107      }
    110108
    111109      void set(const Value& value) {
    112         map->set(*this, value);
    113       }
    114 
    115     protected:
    116       Map* map;
     110        map.set(*this, value);
     111      }
     112
     113    protected:
     114      Map& map;
    117115
    118116    };
     
    125123      typedef typename Map::Value Value;
    126124
    127       ConstMapIt() : map(NULL) {}
    128 
    129       ConstMapIt(Invalid i) : Parent(i), map(NULL) {}
    130 
    131       explicit ConstMapIt(Map& _map) : map(&_map) {
    132         map->notifier()->first(*this);
     125      ConstMapIt() {}
     126
     127      ConstMapIt(Invalid i) : Parent(i) { }
     128
     129      explicit ConstMapIt(Map& _map) : map(_map) {
     130        map.notifier()->first(*this);
    133131      }
    134132
     
    137135
    138136      ConstMapIt& operator++() {
    139         map->notifier()->next(*this);
     137        map.notifier()->next(*this);
    140138        return *this;
    141139      }
     
    146144
    147145    protected:
    148       const Map* map;
     146      const Map& map;
    149147    };
    150148
     
    153151
    154152    public:
    155       ItemIt() : map(NULL) {}
    156 
    157 
    158       ItemIt(Invalid i) : Parent(i), map(NULL) {}
    159 
    160       explicit ItemIt(Map& _map) : map(&_map) {
    161         map->notifier()->first(*this);
     153
     154      ItemIt() {}
     155
     156      ItemIt(Invalid i) : Parent(i) { }
     157
     158      explicit ItemIt(Map& _map) : map(_map) {
     159        map.notifier()->first(*this);
    162160      }
    163161
    164162      ItemIt(const Map& _map, const Item& item)
    165         : Parent(item), map(&_map) {}
     163        : Parent(item), map(_map) {}
    166164
    167165      ItemIt& operator++() {
    168         map->notifier()->next(*this);
    169         return *this;
    170       }
    171 
    172     protected:
    173       const Map* map;
     166        map.notifier()->next(*this);
     167        return *this;
     168      }
     169
     170    protected:
     171      const Map& map;
    174172
    175173    };
     
    194192    typedef typename Parent::ConstReference ConstReference;
    195193
    196     typedef typename Parent::ReferenceMapTag ReferenceMapTag;
    197 
    198194    class MapIt;
    199195    class ConstMapIt;
     
    232228      typedef typename Map::Value Value;
    233229
    234       MapIt() : map(NULL) {}
    235 
    236       MapIt(Invalid i) : Parent(i), map(NULL) { }
    237 
    238       explicit MapIt(Map& _map) : map(&_map) {
    239         map->graph.first(*this);
     230      MapIt() {}
     231
     232      MapIt(Invalid i) : Parent(i) { }
     233
     234      explicit MapIt(Map& _map) : map(_map) {
     235        map.graph.first(*this);
    240236      }
    241237
    242238      MapIt(const Map& _map, const Item& item)
    243         : Parent(item), map(&_map) {}
     239        : Parent(item), map(_map) {}
    244240
    245241      MapIt& operator++() {
    246         map->graph.next(*this);
     242        map.graph.next(*this);
    247243        return *this;
    248244      }
    249245
    250246      typename MapTraits<Map>::ConstReturnValue operator*() const {
    251         return (*map)[*this];
     247        return map[*this];
    252248      }
    253249
    254250      typename MapTraits<Map>::ReturnValue operator*() {
    255         return (*map)[*this];
     251        return map[*this];
    256252      }
    257253
    258254      void set(const Value& value) {
    259         map->set(*this, value);
    260       }
    261 
    262     protected:
    263       Map* map;
     255        map.set(*this, value);
     256      }
     257
     258    protected:
     259      Map& map;
    264260
    265261    };
     
    272268      typedef typename Map::Value Value;
    273269
    274       ConstMapIt() : map(NULL) {}
    275 
    276       ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
    277 
    278       explicit ConstMapIt(Map& _map) : map(&_map) {
    279         map->graph.first(*this);
     270      ConstMapIt() {}
     271
     272      ConstMapIt(Invalid i) : Parent(i) { }
     273
     274      explicit ConstMapIt(Map& _map) : map(_map) {
     275        map.graph.first(*this);
    280276      }
    281277
    282278      ConstMapIt(const Map& _map, const Item& item)
    283         : Parent(item), map(&_map) {}
     279        : Parent(item), map(_map) {}
    284280
    285281      ConstMapIt& operator++() {
    286         map->graph.next(*this);
     282        map.graph.next(*this);
    287283        return *this;
    288284      }
    289285
    290286      typename MapTraits<Map>::ConstReturnValue operator*() const {
    291         return (*map)[*this];
    292       }
    293 
    294     protected:
    295       const Map* map;
     287        return map[*this];
     288      }
     289
     290    protected:
     291      const Map& map;
    296292    };
    297293
     
    300296
    301297    public:
    302       ItemIt() : map(NULL) {}
    303 
    304 
    305       ItemIt(Invalid i) : Parent(i), map(NULL) { }
    306 
    307       explicit ItemIt(Map& _map) : map(&_map) {
    308         map->graph.first(*this);
     298
     299      ItemIt() {}
     300
     301      ItemIt(Invalid i) : Parent(i) { }
     302
     303      explicit ItemIt(Map& _map) : map(_map) {
     304        map.graph.first(*this);
    309305      }
    310306
    311307      ItemIt(const Map& _map, const Item& item)
    312         : Parent(item), map(&_map) {}
     308        : Parent(item), map(_map) {}
    313309
    314310      ItemIt& operator++() {
    315         map->graph.next(*this);
    316         return *this;
    317       }
    318 
    319     protected:
    320       const Map* map;
     311        map.graph.next(*this);
     312        return *this;
     313      }
     314
     315    protected:
     316      const Map& map;
    321317
    322318    };
  • lemon/bits/path_dump.h

    r973 r576  
    5050
    5151    bool empty() const {
    52       return predMap[target] == INVALID;
     52      return predMap[target] != INVALID;
    5353    }
    5454
     
    124124
    125125    bool empty() const {
    126       return predMatrixMap(source, target) == INVALID;
     126      return source != target;
    127127    }
    128128
  • 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

    r956 r513  
    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).
     
    9797      GetSystemTime(&time);
    9898      char buf1[11], buf2[9], buf3[5];
    99           if (GetDateFormat(MY_LOCALE, 0, &time,
     99          if (GetDateFormat(MY_LOCALE, 0, &time,
    100100                        ("ddd MMM dd"), buf1, 11) &&
    101101          GetTimeFormat(MY_LOCALE, 0, &time,
  • lemon/cbc.cc

    r793 r623  
    9595  }
    9696
    97   int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
    98     std::vector<int> indexes;
    99     std::vector<Value> values;
    100 
    101     for(ExprIterator it = b; it != e; ++it) {
    102       indexes.push_back(it->first);
    103       values.push_back(it->second);
    104     }
    105 
    106     _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
    107     return _prob->numberRows() - 1;
    108   }
    10997
    11098  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.
     653      ///
     654      /// \pre The argument should be a valid node id in the graph.
    641655      Node nodeFromId(int) const { return INVALID; }
    642656
    643       /// \brief The edge with the given ID.
    644       ///
    645       /// Returns the edge with the given ID.
    646       /// \pre The argument should be a valid edge ID in the graph.
     657      /// \brief Returns the edge with the given id.
     658      ///
     659      /// \pre The argument should be a valid edge id in the graph.
    647660      Edge edgeFromId(int) const { return INVALID; }
    648661
    649       /// \brief The arc with the given ID.
    650       ///
    651       /// Returns the arc with the given ID.
    652       /// \pre The argument should be a valid arc ID in the graph.
     662      /// \brief Returns the arc with the given id.
     663      ///
     664      /// \pre The argument should be a valid arc id in the graph.
    653665      Arc arcFromId(int) const { return INVALID; }
    654666
    655       /// \brief An upper bound on the node IDs.
    656       ///
    657       /// Returns an upper bound on the node IDs.
     667      /// \brief Returns an upper bound on the node IDs.
    658668      int maxNodeId() const { return -1; }
    659669
    660       /// \brief An upper bound on the edge IDs.
    661       ///
    662       /// Returns an upper bound on the edge IDs.
     670      /// \brief Returns an upper bound on the edge IDs.
    663671      int maxEdgeId() const { return -1; }
    664672
    665       /// \brief An upper bound on the arc IDs.
    666       ///
    667       /// Returns an upper bound on the arc IDs.
     673      /// \brief Returns an upper bound on the arc IDs.
    668674      int maxArcId() const { return -1; }
    669 
    670       /// \brief The direction of the arc.
    671       ///
    672       /// Returns \c true if the direction of the given arc is the same as
    673       /// the inherent orientation of the represented edge.
    674       bool direction(Arc) const { return true; }
    675 
    676       /// \brief Direct the edge.
    677       ///
    678       /// Direct the given edge. The returned arc
    679       /// represents the given edge and its direction comes
    680       /// from the bool parameter. If it is \c true, then the direction
    681       /// of the arc is the same as the inherent orientation of the edge.
    682       Arc direct(Edge, bool) const {
    683         return INVALID;
    684       }
    685 
    686       /// \brief Direct the edge.
    687       ///
    688       /// Direct the given edge. The returned arc represents the given
    689       /// edge and its source node is the given node.
    690       Arc direct(Edge, Node) const {
    691         return INVALID;
    692       }
    693 
    694       /// \brief The oppositely directed arc.
    695       ///
    696       /// Returns the oppositely directed arc representing the same edge.
    697       Arc oppositeArc(Arc) const { return INVALID; }
    698 
    699       /// \brief The opposite node on the edge.
    700       ///
    701       /// Returns the opposite node on the given edge.
    702       Node oppositeNode(Node, Edge) const { return INVALID; }
    703675
    704676      void first(Node&) const {}
     
    734706      int maxId(Arc) const { return -1; }
    735707
    736       /// \brief The base node of the iterator.
    737       ///
    738       /// Returns the base node of the given incident edge iterator.
    739       Node baseNode(IncEdgeIt) const { return INVALID; }
    740 
    741       /// \brief The running node of the iterator.
    742       ///
    743       /// Returns the running node of the given incident edge iterator.
    744       Node runningNode(IncEdgeIt) const { return INVALID; }
    745 
    746       /// \brief The base node of the iterator.
    747       ///
    748       /// Returns the base node of the given outgoing arc iterator
    749       /// (i.e. the source node of the corresponding arc).
    750       Node baseNode(OutArcIt) const { return INVALID; }
    751 
    752       /// \brief The running node of the iterator.
    753       ///
    754       /// Returns the running node of the given outgoing arc iterator
    755       /// (i.e. the target node of the corresponding arc).
    756       Node runningNode(OutArcIt) const { return INVALID; }
    757 
    758       /// \brief The base node of the iterator.
    759       ///
    760       /// Returns the base node of the given incomming arc iterator
    761       /// (i.e. the target node of the corresponding arc).
    762       Node baseNode(InArcIt) const { return INVALID; }
    763 
    764       /// \brief The running node of the iterator.
    765       ///
    766       /// Returns the running node of the given incomming arc iterator
    767       /// (i.e. the source node of the corresponding arc).
    768       Node runningNode(InArcIt) const { return INVALID; }
     708      /// \brief Base node of the iterator
     709      ///
     710      /// Returns the base node (the source in this case) of the iterator
     711      Node baseNode(OutArcIt e) const {
     712        return source(e);
     713      }
     714      /// \brief Running node of the iterator
     715      ///
     716      /// Returns the running node (the target in this case) of the
     717      /// iterator
     718      Node runningNode(OutArcIt e) const {
     719        return target(e);
     720      }
     721
     722      /// \brief Base node of the iterator
     723      ///
     724      /// Returns the base node (the target in this case) of the iterator
     725      Node baseNode(InArcIt e) const {
     726        return target(e);
     727      }
     728      /// \brief Running node of the iterator
     729      ///
     730      /// Returns the running node (the source in this case) of the
     731      /// iterator
     732      Node runningNode(InArcIt e) const {
     733        return source(e);
     734      }
     735
     736      /// \brief Base node of the iterator
     737      ///
     738      /// Returns the base node of the iterator
     739      Node baseNode(IncEdgeIt) const {
     740        return INVALID;
     741      }
     742
     743      /// \brief Running node of the iterator
     744      ///
     745      /// Returns the running node of the iterator
     746      Node runningNode(IncEdgeIt) const {
     747        return INVALID;
     748      }
    769749
    770750      template <typename _Graph>
  • lemon/concepts/graph_components.h

    r956 r713  
    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 concepts of graph components.
     21///\brief The concept of graph components.
    2222
    2323#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
     
    3939    /// \note This class is a template class so that we can use it to
    4040    /// create graph skeleton classes. The reason for this is that \c Node
    41     /// and \c Arc (or \c Edge) types should \e not derive from the same
     41    /// and \c Arc (or \c Edge) types should \e not derive from the same 
    4242    /// base class. For \c Node you should instantiate it with character
    4343    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
     
    9090      ///
    9191      /// This operator defines an ordering of the items.
    92       /// It makes possible to use graph item types as key types in
     92      /// It makes possible to use graph item types as key types in 
    9393      /// associative containers (e.g. \c std::map).
    9494      ///
    95       /// \note This operator only has to define some strict ordering of
     95      /// \note This operator only have to define some strict ordering of
    9696      /// the items; this order has nothing to do with the iteration
    9797      /// ordering of the items.
     
    123123    /// This class describes the base interface of directed graph types.
    124124    /// All digraph %concepts have to conform to this class.
    125     /// It just provides types for nodes and arcs and functions
     125    /// It just provides types for nodes and arcs and functions 
    126126    /// to get the source and the target nodes of arcs.
    127127    class BaseDigraphComponent {
     
    427427    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
    428428    ///
    429     /// This class describes the concept of \c NodeIt, \c ArcIt and
     429    /// This class describes the concept of \c NodeIt, \c ArcIt and 
    430430    /// \c EdgeIt subtypes of digraph and graph types.
    431431    template <typename GR, typename Item>
     
    467467      /// next item.
    468468      GraphItemIt& operator++() { return *this; }
    469 
     469 
    470470      /// \brief Equality operator
    471471      ///
     
    502502    };
    503503
    504     /// \brief Concept class for \c InArcIt, \c OutArcIt and
     504    /// \brief Concept class for \c InArcIt, \c OutArcIt and 
    505505    /// \c IncEdgeIt types.
    506506    ///
    507     /// This class describes the concept of \c InArcIt, \c OutArcIt
     507    /// This class describes the concept of \c InArcIt, \c OutArcIt 
    508508    /// and \c IncEdgeIt subtypes of digraph and graph types.
    509509    ///
    510510    /// \note Since these iterator classes do not inherit from the same
    511511    /// base class, there is an additional template parameter (selector)
    512     /// \c sel. For \c InArcIt you should instantiate it with character
     512    /// \c sel. For \c InArcIt you should instantiate it with character 
    513513    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
    514514    template <typename GR,
     
    531531      GraphIncIt(const GraphIncIt& it) : Item(it) {}
    532532
    533       /// \brief Constructor that sets the iterator to the first
     533      /// \brief Constructor that sets the iterator to the first 
    534534      /// incoming or outgoing arc.
    535535      ///
    536       /// Constructor that sets the iterator to the first arc
     536      /// Constructor that sets the iterator to the first arc 
    537537      /// incoming to or outgoing from the given node.
    538538      explicit GraphIncIt(const GR&, const Base&) {}
     
    805805      /// \brief Return the first edge incident to the given node.
    806806      ///
    807       /// This function gives back the first edge incident to the given
     807      /// This function gives back the first edge incident to the given 
    808808      /// node. The bool parameter gives back the direction for which the
    809       /// source node of the directed arc representing the edge is the
     809      /// source node of the directed arc representing the edge is the 
    810810      /// given node.
    811811      void firstInc(Edge&, bool&, const Node&) const {}
     
    814814      /// given node.
    815815      ///
    816       /// This function gives back the next edge incident to the given
     816      /// This function gives back the next edge incident to the given 
    817817      /// node. The bool parameter should be used as \c firstInc() use it.
    818818      void nextInc(Edge&, bool&) const {}
     
    991991    ///
    992992    /// This class describes the concept of standard graph maps, i.e.
    993     /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
     993    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 
    994994    /// graph types, which can be used for associating data to graph items.
    995995    /// The standard graph maps must conform to the ReferenceMap concept.
     
    10461046          _Map m1(g);
    10471047          _Map m2(g,t);
    1048 
     1048         
    10491049          // Copy constructor
    10501050          // _Map m3(m);
     
    10691069    ///
    10701070    /// This class describes the interface of mappable directed graphs.
    1071     /// It extends \ref BaseDigraphComponent with the standard digraph
     1071    /// It extends \ref BaseDigraphComponent with the standard digraph 
    10721072    /// map classes, namely \c NodeMap and \c ArcMap.
    10731073    /// This concept is part of the Digraph concept.
     
    12061206    ///
    12071207    /// This class describes the interface of mappable undirected graphs.