COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
29 added
108 edited

Legend:

Unmodified
Added
Removed

  • .hgignore

    r610 r944  
    2323lemon/stamp-h2
    2424doc/Doxyfile
     25doc/references.dox
    2526cmake/version.cmake
    2627.dirstamp

  • CMakeLists.txt

    r727 r791  
    3535CHECK_TYPE_SIZE("long long" LONG_LONG)
    3636SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
     37
     38INCLUDE(FindPythonInterp)
    3739
    3840ENABLE_TESTING()

  • INSTALL

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

  • LICENSE

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

  • Makefile.am

    r799 r840  
    4545include doc/Makefile.am
    4646include tools/Makefile.am
     47include scripts/Makefile.am
    4748
    4849DIST_SUBDIRS = demo

  • NEWS

    r712 r962  
     12010-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
    1812009-05-13 Version 1.1 released
    282
    … …  
    73153          ----: Add missing unistd.h include to time_measure.h
    74154          #204: Compilation bug fixed in graph_to_eps.h with VS2005
    75           #214,#215: windows.h should never be included by lemon headers
     155          #214,#215: windows.h should never be included by LEMON headers
    76156          #230: Build systems check the availability of 'long long' type
    77157          #229: Default implementation of Tolerance<> is used for integer types
    … …  
    951752008-10-13 Version 1.0 released
    96176
    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.
    101 
    102         * The major name changes compared to the 0.x series (see the
     177        This is the first stable release of LEMON. Compared to the 0.x
     178        release series, it features a considerably smaller but more
     179        matured set of tools. The API has also completely revised and
     180        changed in several places.
     181
     182        * The major name changes compared to the 0.x series (see the
    103183          Migration Guide in the doc for more details)
    104184          * Graph -> Digraph, UGraph -> Graph
    105185          * Edge -> Arc, UEdge -> Edge
    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)
     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)
    124204          * Concepts
    125             * graph structure concepts (concepts/digraph.h, concepts/graph.h,
     205            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
    126206              concepts/graph_components.h)
    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
     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
    136216              (lgf_reader.h, lgf_writer.h)
    137217            * tools to handle the anomalies of calculations with
    138               floating point numbers (tolerance.h)
     218              floating point numbers (tolerance.h)
    139219            * tools to manage RGB colors (color.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)
     220          * Infrastructure
     221            * extended assertion handling (assert.h)
     222            * exception classes and error handling (error.h)
     223            * concept checking (concept_check.h)
     224            * commonly used mathematical constants (math.h)

  • README

    r705 r921  
    1818   Copying, distribution and modification conditions and terms.
    1919
     20NEWS
     21
     22   News and version history.
     23
    2024INSTALL
    2125
    … …  
    3438   Some example programs to make you easier to get familiar with LEMON.
    3539
     40scripts/
     41
     42   Scripts that make it easier to develop LEMON.
     43
    3644test/
    3745

  • configure.ac

    r727 r840  
    4242
    4343AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
     44AC_CHECK_PROG([python_found],[python],[yes],[no])
    4445AC_CHECK_PROG([gs_found],[gs],[yes],[no])
    4546
    … …  
    8283fi
    8384AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
     85
     86dnl Support for running test cases using valgrind.
     87use_valgrind=no
     88AC_ARG_ENABLE([valgrind],
     89AS_HELP_STRING([--enable-valgrind], [use valgrind when running tests]),
     90              [use_valgrind=yes])
     91
     92if [[ "$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
     98fi
     99AM_CONDITIONAL(USE_VALGRIND, [test "$use_valgrind" = "yes"])
    84100
    85101dnl Checks for header files.
    … …  
    128144echo
    129145echo Build additional tools........ : $enable_tools
     146echo Use valgrind for tests........ : $use_valgrind
    130147echo
    131148echo The packace will be installed in

  • demo/arg_parser_demo.cc

    r463 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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
    6873  // Perform the parsing process
    6974  // (in case of any error it terminates the program)
    70   ap.parse();
     75  // The try {} construct is necessary only if the ap.trowOnProblems()
     76  // setting is in use.
     77  try {
     78    ap.parse();
     79  } catch (ArgParserException &) { return 1; }
    7180
    7281  // Check each option if it has been given and print its value

  • doc/CMakeLists.txt

    r726 r943  
    1010)
    1111
    12 IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
     12IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND 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
    2324    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
    2425    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
    … …  
    2728    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
    2829    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
    2931    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
    3032    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
    3134    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    3235    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}

  • doc/Doxyfile.in

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

  • doc/Makefile.am

    r720 r943  
    2828        connected_components.eps \
    2929        edge_biconnected_components.eps \
     30        matching.eps \
    3031        node_biconnected_components.eps \
     32        planar.eps \
    3133        strongly_connected_components.eps
    3234
    … …  
    6769        fi
    6870
    69 html-local: $(DOC_PNG_IMAGES)
     71references.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
     83html-local: $(DOC_PNG_IMAGES) references.dox
    7084        if test ${doxygen_found} = yes; then \
    7185          cd doc; \

  • doc/groups.dox

    r710 r963  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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 
    233 This group contains two dimensional data storages implemented in LEMON.
    234 */
    235 
    236 /**
    237229@defgroup paths Path Structures
    238230@ingroup datas
    … …  
    247239any kind of path structure.
    248240
    249 \sa lemon::concepts::Path
     241\sa \ref concepts::Path "Path concept"
     242*/
     243
     244/**
     245@defgroup heaps Heap Structures
     246@ingroup datas
     247\brief %Heap structures implemented in LEMON.
     248
     249This group contains the heap structures implemented in LEMON.
     250
     251LEMON provides several heap classes. They are efficient implementations
     252of the abstract data type \e priority \e queue. They store items with
     253specified values called \e priorities in such a way that finding and
     254removing the item with minimum priority are efficient.
     255The basic operations are adding and erasing items, changing the priority
     256of an item, etc.
     257
     258Heaps are crucial in several algorithms, such as Dijkstra and Prim.
     259The heap implementations have the same interface, thus any of them can be
     260used easily in such algorithms.
     261
     262\sa \ref concepts::Heap "Heap concept"
    250263*/
    251264
    … …  
    260273
    261274/**
     275@defgroup geomdat Geometric Data Structures
     276@ingroup auxdat
     277\brief Geometric data structures implemented in LEMON.
     278
     279This 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/**
    262289@defgroup algs Algorithms
    263290\brief This group contains the several algorithms
    … …  
    274301
    275302This group contains the common graph search algorithms, namely
    276 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     303\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
     304\ref clrs01algorithms.
    277305*/
    278306
    … …  
    282310\brief Algorithms for finding shortest paths.
    283311
    284 This group contains the algorithms for finding shortest paths in digraphs.
     312This group contains the algorithms for finding shortest paths in digraphs
     313\ref clrs01algorithms.
    285314
    286315 - \ref Dijkstra algorithm for finding shortest paths from a source node
    … …  
    290319   but the digraph should not contain directed cycles with negative total
    291320   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.
    296321 - \ref Suurballe A successive shortest path algorithm for finding
    297322   arc-disjoint paths between two nodes having minimum total length.
    … …  
    299324
    300325/**
     326@defgroup spantree Minimum Spanning Tree Algorithms
     327@ingroup algs
     328\brief Algorithms for finding minimum cost spanning trees and arborescences.
     329
     330This group contains the algorithms for finding minimum cost spanning
     331trees and arborescences \ref clrs01algorithms.
     332*/
     333
     334/**
    301335@defgroup max_flow Maximum Flow Algorithms
    302336@ingroup algs
    … …  
    304338
    305339This group contains the algorithms for finding maximum flows and
    306 feasible circulations.
     340feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    307341
    308342The \e maximum \e flow \e problem is to find a flow of maximum value between
    … …  
    318352\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    319353
    320 LEMON contains several algorithms for solving maximum flow problems:
    321 - \ref EdmondsKarp Edmonds-Karp algorithm.
    322 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    323 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    324 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    325 
    326 In most cases the \ref Preflow "Preflow" algorithm provides the
    327 fastest method for computing a maximum flow. All implementations
    328 also provide functions to query the minimum cut, which is the dual
    329 problem of maximum flow.
    330 
    331 \ref Circulation is a preflow push-relabel algorithm implemented directly
     354\ref Preflow is an efficient implementation of Goldberg-Tarjan's
     355preflow push-relabel algorithm \ref goldberg88newapproach for finding
     356maximum flows. It also provides functions to query the minimum cut,
     357which is the dual problem of maximum flow.
     358
     359\ref Circulation is a preflow push-relabel algorithm implemented directly
    332360for finding feasible circulations, which is a somewhat different problem,
    333361but it is strongly related to maximum flow.
    … …  
    342370
    343371This group contains the algorithms for finding minimum cost flows and
    344 circulations. For more information about this problem and its dual
    345 solution see \ref min_cost_flow "Minimum Cost Flow Problem".
     372circulations \ref amo93networkflows. For more information about this
     373problem and its dual solution, see \ref min_cost_flow
     374"Minimum Cost Flow Problem".
    346375
    347376LEMON contains several algorithms for this problem.
    348377 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    349    pivot strategies.
    350  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    351    cost scaling.
    352  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    353    capacity scaling.
    354  - \ref CancelAndTighten The Cancel and Tighten algorithm.
    355  - \ref CycleCanceling Cycle-Canceling algorithms.
     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.
    356386
    357387In general NetworkSimplex is the most efficient implementation,
    … …  
    376406
    377407\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    378     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
     408    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    379409
    380410LEMON contains several algorithms related to minimum cut problems:
    … …  
    382412- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    383413  in directed graphs.
    384 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    385   calculating minimum cut in undirected graphs.
    386414- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    387415  all-pairs minimum cut in undirected graphs.
    … …  
    392420
    393421/**
    394 @defgroup graph_properties Connectivity and Other Graph Properties
    395 @ingroup algs
    396 \brief Algorithms for discovering the graph properties
    397 
    398 This group contains the algorithms for discovering the graph properties
    399 like connectivity, bipartiteness, euler property, simplicity etc.
    400 
    401 \image html edge_biconnected_components.png
    402 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    403 */
    404 
    405 /**
    406 @defgroup planar Planarity Embedding and Drawing
    407 @ingroup algs
    408 \brief Algorithms for planarity checking, embedding and drawing
    409 
    410 This group contains the algorithms for planarity checking,
    411 embedding and drawing.
    412 
    413 \image html planar.png
    414 \image latex planar.eps "Plane graph" width=\textwidth
     422@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     423@ingroup algs
     424\brief Algorithms for finding minimum mean cycles.
     425
     426This group contains the algorithms for finding minimum mean cycles
     427\ref clrs01algorithms, \ref amo93networkflows.
     428
     429The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     430of minimum mean length (cost) in a digraph.
     431The mean length of a cycle is the average length of its arcs, i.e. the
     432ratio between the total length of the cycle and the number of arcs on it.
     433
     434This 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
     436conservative if and only if there is no directed cycle of negative total
     437length. For an arbitrary length function, the negative of the minimum
     438cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     439arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     440function.
     441
     442LEMON 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
     450In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
     451most efficient one, though the best known theoretical bound on its running
     452time is exponential.
     453Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
     454run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
     455typically faster due to the applied early termination scheme.
    415456*/
    416457
    … …  
    433474
    434475The 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.
    445476- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    446477  maximum cardinality matching in general graphs.
    … …  
    450481  Edmond's blossom shrinking algorithm for calculating maximum weighted
    451482  perfect matching in general graphs.
    452 
    453 \image html bipartite_matching.png
    454 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
    455 */
    456 
    457 /**
    458 @defgroup spantree Minimum Spanning Tree Algorithms
    459 @ingroup algs
    460 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    461 
    462 This group contains the algorithms for finding minimum cost spanning
    463 trees and arborescences.
     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
     500This group contains the algorithms for discovering the graph properties
     501like 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
     512This group contains the algorithms for planarity checking,
     513embedding and drawing.
     514
     515\image html planar.png
     516\image latex planar.eps "Plane graph" width=\textwidth
    464517*/
    465518
    … …  
    471524This group contains some algorithms implemented in LEMON
    472525in 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 
    480 This group contains the approximation and heuristic algorithms
    481 implemented in LEMON.
    482526*/
    483527
    … …  
    492536
    493537/**
    494 @defgroup lp_group Lp and Mip Solvers
     538@defgroup lp_group LP and MIP Solvers
    495539@ingroup gen_opt_group
    496 \brief Lp and Mip solver interfaces for LEMON.
    497 
    498 This group contains Lp and Mip solver interfaces for LEMON. The
    499 various LP solvers could be used in the same manner with this
    500 interface.
    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 
    508 This group adds some helper tools to general optimization framework
    509 implemented in LEMON.
    510 */
    511 
    512 /**
    513 @defgroup metah Metaheuristics
    514 @ingroup gen_opt_group
    515 \brief Metaheuristics for LEMON library.
    516 
    517 This group contains some metaheuristic optimization tools.
     540\brief LP and MIP solver interfaces for LEMON.
     541
     542This group contains LP and MIP solver interfaces for LEMON.
     543Various LP solvers could be used in the same manner with this
     544high-level interface.
     545
     546The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     547\ref cplex, \ref soplex.
    518548*/
    519549
    … …  
    588618
    589619/**
    590 @defgroup dimacs_group DIMACS format
     620@defgroup dimacs_group DIMACS Format
    591621@ingroup io_group
    592622\brief Read and write files in DIMACS format
    … …  
    637667\brief Skeleton and concept checking classes for graph structures
    638668
    639 This group contains the skeletons and concept checking classes of LEMON's
    640 graph structures and helper classes used to implement these.
     669This group contains the skeletons and concept checking classes of
     670graph structures.
    641671*/
    642672
    … …  
    650680
    651681/**
     682@defgroup tools Standalone Utility Applications
     683
     684Some utility applications are listed here.
     685
     686The standard compilation procedure (<tt>./configure;make</tt>) will compile
     687them, as well.
     688*/
     689
     690/**
    652691\anchor demoprograms
    653692
    … …  
    661700*/
    662701
    663 /**
    664 @defgroup tools Standalone Utility Applications
    665 
    666 Some utility applications are listed here.
    667 
    668 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    669 them, as well.
    670 */
    671 
    672702}

  • doc/mainpage.dox

    r705 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2222\section intro Introduction
    2323
    24 \subsection whatis What is LEMON
    25 
    26 LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
    27 and <b>O</b>ptimization in <b>N</b>etworks.
    28 It is a C++ template
    29 library aimed at combinatorial optimization tasks which
    30 often involve in working
    31 with graphs.
     24<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
     25and <b>O</b>ptimization in <b>N</b>etworks</i>.
     26It is a C++ template library providing efficient implementations of common
     27data structures and algorithms with focus on combinatorial optimization
     28tasks connected mainly with graphs and networks.
    3229
    3330<b>
    … …  
    3936</b>
    4037
    41 \subsection howtoread How to read the documentation
     38The project is maintained by the
     39<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
     40Combinatorial Optimization</a> \ref egres
     41at the Operations Research Department of the
     42<a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,
     43Budapest, Hungary.
     44LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
     45initiative \ref coinor.
     46
     47\section howtoread How to Read the Documentation
    4248
    4349If you would like to get to know the library, see
    4450<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
     51
     52If you are interested in starting to use the library, see the <a class="el"
     53href="http://lemon.cs.elte.hu/trac/lemon/wiki/InstallGuide/">Installation
     54Guide</a>.
    4555
    4656If you know what you are looking for, then try to find it under the

  • doc/min_cost_flow.dox

    r710 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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.
     29and arc costs \ref amo93networkflows.
    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)<=0\f$;
     81   - \f$\pi(u)\leq 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)>=0\f$;
     148   - \f$\pi(u)\geq 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

    r714 r953  
    5858        lemon/arg_parser.h \
    5959        lemon/assert.h \
     60        lemon/bellman_ford.h \
    6061        lemon/bfs.h \
    6162        lemon/bin_heap.h \
     63        lemon/binomial_heap.h \
     64        lemon/bucket_heap.h \
     65        lemon/capacity_scaling.h \
    6266        lemon/cbc.h \
    6367        lemon/circulation.h \
    … …  
    6670        lemon/concept_check.h \
    6771        lemon/connectivity.h \
     72        lemon/core.h \
     73        lemon/cost_scaling.h \
    6874        lemon/counter.h \
    69         lemon/core.h \
    7075        lemon/cplex.h \
     76        lemon/cycle_canceling.h \
    7177        lemon/dfs.h \
     78        lemon/dheap.h \
    7279        lemon/dijkstra.h \
    7380        lemon/dim2.h \
    … …  
    7784        lemon/error.h \
    7885        lemon/euler.h \
     86        lemon/fib_heap.h \
     87        lemon/fractional_matching.h \
    7988        lemon/full_graph.h \
    8089        lemon/glpk.h \
    … …  
    8291        lemon/graph_to_eps.h \
    8392        lemon/grid_graph.h \
     93        lemon/hartmann_orlin_mmc.h \
     94        lemon/howard_mmc.h \
    8495        lemon/hypercube_graph.h \
     96        lemon/karp_mmc.h \
    8597        lemon/kruskal.h \
    8698        lemon/hao_orlin.h \
    … …  
    91103        lemon/lp_base.h \
    92104        lemon/lp_skeleton.h \
    93         lemon/list_graph.h \
    94105        lemon/maps.h \
    95106        lemon/matching.h \
    … …  
    98109        lemon/nauty_reader.h \
    99110        lemon/network_simplex.h \
     111        lemon/pairing_heap.h \
    100112        lemon/path.h \
     113        lemon/planarity.h \
    101114        lemon/preflow.h \
     115        lemon/quad_heap.h \
     116        lemon/radix_heap.h \
    102117        lemon/radix_sort.h \
    103118        lemon/random.h \
    104119        lemon/smart_graph.h \
    105120        lemon/soplex.h \
     121        lemon/static_graph.h \
    106122        lemon/suurballe.h \
    107123        lemon/time_measure.h \

  • lemon/adaptors.h

    r703 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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  ///
    363366  /// \tparam DGR The type of the adapted digraph.
    364367  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    … …  
    419422      Parent::initialize(digraph);
    420423      _node_filter = &node_filter;
    421       _arc_filter = &arc_filter;     
     424      _arc_filter = &arc_filter;
    422425    }
    423426
    … …  
    506509
    507510    template <typename V>
    508     class NodeMap 
    509       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 
    510               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
     511    class NodeMap
     512      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     513              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    511514      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    512         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     515        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    513516
    514517    public:
    … …  
    533536
    534537    template <typename V>
    535     class ArcMap 
     538    class ArcMap
    536539      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    537               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     540              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    538541      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    539542        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
    … …  
    580583      Parent::initialize(digraph);
    581584      _node_filter = &node_filter;
    582       _arc_filter = &arc_filter;     
     585      _arc_filter = &arc_filter;
    583586    }
    584587
    … …  
    649652
    650653    template <typename V>
    651     class NodeMap 
     654    class NodeMap
    652655      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    653656          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    654       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 
     657      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    655658        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    656659
    … …  
    676679
    677680    template <typename V>
    678     class ArcMap 
     681    class ArcMap
    679682      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    680683          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    … …  
    719722  /// by adding or removing nodes or arcs, unless the \c GR template
    720723  /// parameter is set to be \c const.
     724  ///
     725  /// This class provides only linear time counting for nodes and arcs.
    721726  ///
    722727  /// \tparam DGR The type of the adapted digraph.
    … …  
    10171022
    10181023    template <typename V>
    1019     class NodeMap 
     1024    class NodeMap
    10201025      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10211026          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1022       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1027      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10231028        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    10241029
    … …  
    10441049
    10451050    template <typename V>
    1046     class ArcMap 
     1051    class ArcMap
    10471052      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10481053          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1049       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1054      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10501055        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    10511056
    … …  
    10711076
    10721077    template <typename V>
    1073     class EdgeMap 
     1078    class EdgeMap
    10741079      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10751080        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1076       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1081      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10771082        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    10781083
    … …  
    11131118    NF* _node_filter;
    11141119    EF* _edge_filter;
    1115     SubGraphBase() 
    1116           : Parent(), _node_filter(0), _edge_filter(0) { }
     1120    SubGraphBase()
     1121          : Parent(), _node_filter(0), _edge_filter(0) { }
    11171122
    11181123    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
    … …  
    12151220
    12161221    template <typename V>
    1217     class NodeMap 
     1222    class NodeMap
    12181223      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12191224          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1220       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
     1225      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12211226        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    12221227
    … …  
    12421247
    12431248    template <typename V>
    1244     class ArcMap 
     1249    class ArcMap
    12451250      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12461251          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1247       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
     1252      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12481253        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    12491254
    … …  
    12691274
    12701275    template <typename V>
    1271     class EdgeMap 
     1276    class EdgeMap
    12721277      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12731278        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1274       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
    1275         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1279      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1280        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    12761281
    12771282    public:
    … …  
    13141319  /// by adding or removing nodes or edges, unless the \c GR template
    13151320  /// parameter is set to be \c const.
     1321  ///
     1322  /// This class provides only linear time counting for nodes, edges and arcs.
    13161323  ///
    13171324  /// \tparam GR The type of the adapted graph.
    … …  
    14711478  /// by adding or removing nodes or arcs/edges, unless the \c GR template
    14721479  /// parameter is set to be \c const.
     1480  ///
     1481  /// This class provides only linear time item counting.
    14731482  ///
    14741483  /// \tparam GR The type of the adapted digraph or graph.
    … …  
    14961505#endif
    14971506    typedef DigraphAdaptorExtender<
    1498       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 
     1507      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
    14991508                     true> > Parent;
    15001509
    … …  
    15171526    /// Creates a subgraph for the given digraph or graph with the
    15181527    /// given node filter map.
    1519     FilterNodes(GR& graph, NF& node_filter) 
     1528    FilterNodes(GR& graph, NF& node_filter)
    15201529      : Parent(), const_true_map()
    15211530    {
    … …  
    15551564                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
    15561565    public GraphAdaptorExtender<
    1557       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
     1566      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15581567                   true> > {
    15591568
    15601569    typedef GraphAdaptorExtender<
    1561       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
     1570      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15621571                   true> > Parent;
    15631572
    … …  
    16191628  /// by adding or removing nodes or arcs, unless the \c GR template
    16201629  /// parameter is set to be \c const.
     1630  ///
     1631  /// This class provides only linear time counting for nodes and arcs.
    16211632  ///
    16221633  /// \tparam DGR The type of the adapted digraph.
    … …  
    16431654#endif
    16441655    typedef DigraphAdaptorExtender<
    1645       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 
     1656      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
    16461657                     AF, false> > Parent;
    16471658
    … …  
    17291740  /// by adding or removing nodes or edges, unless the \c GR template
    17301741  /// parameter is set to be \c const.
     1742  ///
     1743  /// This class provides only linear time counting for nodes, edges and arcs.
    17311744  ///
    17321745  /// \tparam GR The type of the adapted graph.
    … …  
    17491762  class FilterEdges :
    17501763    public GraphAdaptorExtender<
    1751       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
     1764      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
    17521765                   EF, false> > {
    17531766#endif
    17541767    typedef GraphAdaptorExtender<
    1755       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 
     1768      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
    17561769                   EF, false> > Parent;
    17571770
    … …  
    17781791    /// Creates a subgraph for the given graph with the given edge
    17791792    /// filter map.
    1780     FilterEdges(GR& graph, EF& edge_filter) 
     1793    FilterEdges(GR& graph, EF& edge_filter)
    17811794      : Parent(), const_true_map() {
    17821795      Parent::initialize(graph, const_true_map, edge_filter);
    … …  
    18461859      bool _forward;
    18471860
    1848       Arc(const Edge& edge, bool forward) 
     1861      Arc(const Edge& edge, bool forward)
    18491862        : _edge(edge), _forward(forward) {}
    18501863
    … …  
    20862099
    20872100      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
    2088         : _forward(*adaptor._digraph, value), 
     2101        : _forward(*adaptor._digraph, value),
    20892102          _backward(*adaptor._digraph, value) {}
    20902103
    … …  
    22042217    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
    22052218    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
    2206    
     2219
    22072220    typedef EdgeNotifier ArcNotifier;
    22082221    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
    … …  
    22322245  /// by adding or removing nodes or edges, unless the \c GR template
    22332246  /// parameter is set to be \c const.
     2247  ///
     2248  /// This class provides item counting in the same time as the adapted
     2249  /// digraph structure.
    22342250  ///
    22352251  /// \tparam DGR The type of the adapted digraph.
    … …  
    25352551  /// by adding or removing nodes or arcs, unless the \c GR template
    25362552  /// parameter is set to be \c const.
     2553  ///
     2554  /// This class provides item counting in the same time as the adapted
     2555  /// graph structure.
    25372556  ///
    25382557  /// \tparam GR The type of the adapted graph.
    … …  
    26792698  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
    26802699  ///
     2700  /// This class provides only linear time counting for nodes and arcs.
     2701  ///
    26812702  /// \tparam DGR The type of the adapted digraph.
    26822703  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    … …  
    27082729           typename FM = CM,
    27092730           typename TL = Tolerance<typename CM::Value> >
    2710   class ResidualDigraph 
     2731  class ResidualDigraph
    27112732    : public SubDigraph<
    27122733        Undirector<const DGR>,
    … …  
    27652786    ResidualDigraph(const DGR& digraph, const CM& capacity,
    27662787                    FM& flow, const TL& tolerance = Tolerance())
    2767       : Parent(), _capacity(&capacity), _flow(&flow), 
     2788      : Parent(), _capacity(&capacity), _flow(&flow),
    27682789        _graph(digraph), _node_filter(),
    27692790        _forward_filter(capacity, flow, tolerance),
    … …  
    28472868
    28482869      /// Constructor
    2849       ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 
     2870      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
    28502871        : _adaptor(&adaptor) {}
    28512872
    … …  
    33263347  /// in the adaptor.
    33273348  ///
     3349  /// This class provides item counting in the same time as the adapted
     3350  /// digraph structure.
     3351  ///
    33283352  /// \tparam DGR The type of the adapted digraph.
    33293353  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    … …  
    34243448    /// to get a node map of the split digraph.
    34253449    /// Its value type is inherited from the first node map type (\c IN).
    3426     /// \tparam IN The type of the node map for the in-nodes. 
     3450    /// \tparam IN The type of the node map for the in-nodes.
    34273451    /// \tparam OUT The type of the node map for the out-nodes.
    34283452    template <typename IN, typename OUT>

  • lemon/arg_parser.cc

    r463 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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
    2331  void ArgParser::_showHelp(void *p)
    2432  {
    2533    (static_cast<ArgParser*>(p))->showHelp();
    26     exit(1);
     34    (static_cast<ArgParser*>(p))->_terminate(ArgParserException::HELP);
    2735  }
    2836
    2937  ArgParser::ArgParser(int argc, const char * const *argv)
    30     :_argc(argc), _argv(argv), _command_name(argv[0]) {
     38    :_argc(argc), _argv(argv), _command_name(argv[0]),
     39    _exit_on_problems(true) {
    3140    funcOption("-help","Print a short help message",_showHelp,this);
    3241    synonym("help","-help");
    … …  
    343352        i!=_others_help.end();++i) showHelp(i);
    344353    for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i);
    345     exit(1);
     354    _terminate(ArgParserException::HELP);
    346355  }
    347356
    … …  
    352361    std::cerr << "\nType '" << _command_name <<
    353362      " --help' to obtain a short summary on the usage.\n\n";
    354     exit(1);
     363    _terminate(ArgParserException::UNKNOWN_OPT);
    355364  }
    356365
    … …  
    415424      std::cerr << "\nType '" << _command_name <<
    416425        " --help' to obtain a short summary on the usage.\n\n";
    417       exit(1);
     426      _terminate(ArgParserException::INVALID_OPT);
    418427    }
    419428  }

  • lemon/arg_parser.h

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

  • lemon/bfs.h

    r525 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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 meet the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must conform to 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 meet the \ref concepts::WriteMap "WriteMap" concept.
     65    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     66    ///By default, it is a NullMap.
    6667    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6768    ///Instantiates a \c ProcessedMap.
    … …  
    8283
    8384    ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to
     86    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8587    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8688    ///Instantiates a \c ReachedMap.
    … …  
    9799
    98100    ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     101    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    100102    typedef typename Digraph::template NodeMap<int> DistMap;
    101103    ///Instantiates a \c DistMap.
    … …  
    121123  ///\tparam GR The type of the digraph the algorithm runs on.
    122124  ///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.
    123130#ifdef DOXYGEN
    124131  template <typename GR,
    … …  
    226233    ///\ref named-templ-param "Named parameter" for setting
    227234    ///\c PredMap type.
    228     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     235    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    229236    template <class T>
    230237    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
    … …  
    246253    ///\ref named-templ-param "Named parameter" for setting
    247254    ///\c DistMap type.
    248     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     255    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    249256    template <class T>
    250257    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
    … …  
    266273    ///\ref named-templ-param "Named parameter" for setting
    267274    ///\c ReachedMap type.
    268     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     275    ///It must conform to
     276    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    269277    template <class T>
    270278    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    286294    ///\ref named-templ-param "Named parameter" for setting
    287295    ///\c ProcessedMap type.
    288     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     296    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    289297    template <class T>
    290298    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
    … …  
    414422    ///The simplest way to execute the BFS algorithm is to use one of the
    415423    ///member functions called \ref run(Node) "run()".\n
    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
     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
    418426    ///\ref addSource(). Finally the actual path computation can be
    419427    ///performed with one of the \ref start() functions.
    … …  
    701709    ///Runs the algorithm to visit all nodes in the digraph.
    702710
    703     ///This method runs the %BFS algorithm in order to
    704     ///compute the shortest path to each node.
    705     ///
    706     ///The algorithm computes
    707     ///- the shortest path tree (forest),
    708     ///- the distance of each node from the root(s).
     711    ///This method runs the %BFS algorithm in order to visit all nodes
     712    ///in the digraph.
    709713    ///
    710714    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
    … …  
    738742    ///@{
    739743
    740     ///The shortest path to a node.
    741 
    742     ///Returns the shortest path to a node.
     744    ///The shortest path to the given node.
     745
     746    ///Returns the shortest path to the given node from the root(s).
    743747    ///
    744748    ///\warning \c t should be reached from the root(s).
    … …  
    748752    Path path(Node t) const { return Path(*G, *_pred, t); }
    749753
    750     ///The distance of a node from the root(s).
    751 
    752     ///Returns the distance of a node from the root(s).
     754    ///The distance of the given node from the root(s).
     755
     756    ///Returns the distance of the given node from the root(s).
    753757    ///
    754758    ///\warning If node \c v is not reached from the root(s), then
    … …  
    759763    int dist(Node v) const { return (*_dist)[v]; }
    760764
    761     ///Returns the 'previous arc' of the shortest path tree for a node.
    762 
     765    ///\brief Returns the 'previous arc' of the shortest path tree for
     766    ///the given node.
     767    ///
    763768    ///This function returns the 'previous arc' of the shortest path
    764769    ///tree for the node \c v, i.e. it returns the last arc of a
    … …  
    767772    ///
    768773    ///The shortest path tree used here is equal to the shortest path
    769     ///tree used in \ref predNode().
     774    ///tree used in \ref predNode() and \ref predMap().
    770775    ///
    771776    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    773778    Arc predArc(Node v) const { return (*_pred)[v];}
    774779
    775     ///Returns the 'previous node' of the shortest path tree for a node.
    776 
     780    ///\brief Returns the 'previous node' of the shortest path tree for
     781    ///the given node.
     782    ///
    777783    ///This function returns the 'previous node' of the shortest path
    778784    ///tree for the node \c v, i.e. it returns the last but one node
    779     ///from a shortest path from a root to \c v. It is \c INVALID
     785    ///of a shortest path from a root to \c v. It is \c INVALID
    780786    ///if \c v is not reached from the root(s) or if \c v is a root.
    781787    ///
    782788    ///The shortest path tree used here is equal to the shortest path
    783     ///tree used in \ref predArc().
     789    ///tree used in \ref predArc() and \ref predMap().
    784790    ///
    785791    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    802808    ///
    803809    ///Returns a const reference to the node map that stores the predecessor
    804     ///arcs, which form the shortest path tree.
     810    ///arcs, which form the shortest path tree (forest).
    805811    ///
    806812    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    808814    const PredMap &predMap() const { return *_pred;}
    809815
    810     ///Checks if a node is reached from the root(s).
     816    ///Checks if the given node is reached from the root(s).
    811817
    812818    ///Returns \c true if \c v is reached from the root(s).
    … …  
    834840    ///The type of the map that stores the predecessor
    835841    ///arcs of the shortest paths.
    836     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     842    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    837843    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    838844    ///Instantiates a PredMap.
    … …  
    849855
    850856    ///The type of the map that indicates which nodes are processed.
    851     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    852     ///By default it is a NullMap.
     857    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     858    ///By default, it is a NullMap.
    853859    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    854860    ///Instantiates a ProcessedMap.
    … …  
    869875
    870876    ///The type of the map that indicates which nodes are reached.
    871     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     877    ///It must conform to
     878    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    872879    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    873880    ///Instantiates a ReachedMap.
    … …  
    884891
    885892    ///The type of the map that stores the distances of the nodes.
    886     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     893    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    887894    typedef typename Digraph::template NodeMap<int> DistMap;
    888895    ///Instantiates a DistMap.
    … …  
    899906
    900907    ///The type of the shortest paths.
    901     ///It must meet the \ref concepts::Path "Path" concept.
     908    ///It must conform to the \ref concepts::Path "Path" concept.
    902909    typedef lemon::Path<Digraph> Path;
    903910  };
    … …  
    905912  /// Default traits class used by BfsWizard
    906913
    907   /// To make it easier to use Bfs algorithm
    908   /// we have created a wizard class.
    909   /// This \ref BfsWizard class needs default traits,
    910   /// as well as the \ref Bfs class.
    911   /// The \ref BfsWizardBase is a class to be the default traits of the
    912   /// \ref BfsWizard class.
     914  /// Default traits class used by BfsWizard.
     915  /// \tparam GR The type of the digraph.
    913916  template<class GR>
    914917  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
    … …  
    938941    /// Constructor.
    939942
    940     /// This constructor does not require parameters, therefore it initiates
     943    /// This constructor does not require parameters, it initiates
    941944    /// all of the attributes to \c 0.
    942945    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    … …  
    963966  /// This class should only be used through the \ref bfs() function,
    964967  /// which makes it easier to use the algorithm.
     968  ///
     969  /// \tparam TR The traits class that defines various types used by the
     970  /// algorithm.
    965971  template<class TR>
    966972  class BfsWizard : public TR
    … …  
    968974    typedef TR Base;
    969975
    970     ///The type of the digraph the algorithm runs on.
    971976    typedef typename TR::Digraph Digraph;
    972977
    … …  
    976981    typedef typename Digraph::OutArcIt OutArcIt;
    977982
    978     ///\brief The type of the map that stores the predecessor
    979     ///arcs of the shortest paths.
    980983    typedef typename TR::PredMap PredMap;
    981     ///\brief The type of the map that stores the distances of the nodes.
    982984    typedef typename TR::DistMap DistMap;
    983     ///\brief The type of the map that indicates which nodes are reached.
    984985    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
    988987    typedef typename TR::Path Path;
    989988
    … …  
    10551054    ///Runs BFS algorithm to visit all nodes in the digraph.
    10561055
    1057     ///This method runs BFS algorithm in order to compute
    1058     ///the shortest path to each node.
     1056    ///This method runs BFS algorithm in order to visit all nodes
     1057    ///in the digraph.
    10591058    void run()
    10601059    {
    … …  
    10681067      SetPredMapBase(const TR &b) : TR(b) {}
    10691068    };
    1070     ///\brief \ref named-func-param "Named parameter"
    1071     ///for setting PredMap object.
    1072     ///
    1073     ///\ref named-func-param "Named parameter"
    1074     ///for setting PredMap object.
     1069
     1070    ///\brief \ref named-templ-param "Named parameter" for setting
     1071    ///the predecessor map.
     1072    ///
     1073    ///\ref named-templ-param "Named parameter" function for setting
     1074    ///the map that stores the predecessor arcs of the nodes.
    10751075    template<class T>
    10761076    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
    … …  
    10861086      SetReachedMapBase(const TR &b) : TR(b) {}
    10871087    };
    1088     ///\brief \ref named-func-param "Named parameter"
    1089     ///for setting ReachedMap object.
    1090     ///
    1091     /// \ref named-func-param "Named parameter"
    1092     ///for setting ReachedMap object.
     1088
     1089    ///\brief \ref named-templ-param "Named parameter" for setting
     1090    ///the reached map.
     1091    ///
     1092    ///\ref named-templ-param "Named parameter" function for setting
     1093    ///the map that indicates which nodes are reached.
    10931094    template<class T>
    10941095    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
    … …  
    11041105      SetDistMapBase(const TR &b) : TR(b) {}
    11051106    };
    1106     ///\brief \ref named-func-param "Named parameter"
    1107     ///for setting DistMap object.
    1108     ///
    1109     /// \ref named-func-param "Named parameter"
    1110     ///for setting DistMap object.
     1107
     1108    ///\brief \ref named-templ-param "Named parameter" for setting
     1109    ///the distance map.
     1110    ///
     1111    ///\ref named-templ-param "Named parameter" function for setting
     1112    ///the map that stores the distances of the nodes calculated
     1113    ///by the algorithm.
    11111114    template<class T>
    11121115    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
    … …  
    11221125      SetProcessedMapBase(const TR &b) : TR(b) {}
    11231126    };
    1124     ///\brief \ref named-func-param "Named parameter"
    1125     ///for setting ProcessedMap object.
    1126     ///
    1127     /// \ref named-func-param "Named parameter"
    1128     ///for setting ProcessedMap object.
     1127
     1128    ///\brief \ref named-func-param "Named parameter" for setting
     1129    ///the processed map.
     1130    ///
     1131    ///\ref named-templ-param "Named parameter" function for setting
     1132    ///the map that indicates which nodes are processed.
    11291133    template<class T>
    11301134    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
    … …  
    12651269    ///
    12661270    /// The type of the map that indicates which nodes are reached.
    1267     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1271    /// It must conform to
     1272    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12681273    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12691274
    … …  
    13031308  /// does not observe the BFS events. If you want to observe the BFS
    13041309  /// events, you should implement your own visitor class.
    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.
     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.
    13101315#ifdef DOXYGEN
    13111316  template <typename GR, typename VS, typename TR>
    … …  
    14261431    /// The simplest way to execute the BFS algorithm is to use one of the
    14271432    /// member functions called \ref run(Node) "run()".\n
    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
     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
    14301435    /// \ref addSource(). Finally the actual path computation can be
    14311436    /// performed with one of the \ref start() functions.
    … …  
    16991704    /// \brief Runs the algorithm to visit all nodes in the digraph.
    17001705    ///
    1701     /// This method runs the %BFS algorithm in order to
    1702     /// compute the shortest path to each node.
    1703     ///
    1704     /// The algorithm computes
    1705     /// - the shortest path tree (forest),
    1706     /// - the distance of each node from the root(s).
     1706    /// This method runs the %BFS algorithm in order to visit all nodes
     1707    /// in the digraph.
    17071708    ///
    17081709    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
    … …  
    17361737    ///@{
    17371738
    1738     /// \brief Checks if a node is reached from the root(s).
     1739    /// \brief Checks if the given node is reached from the root(s).
    17391740    ///
    17401741    /// Returns \c true if \c v is reached from the root(s).

  • lemon/bin_heap.h

    r631 r758  
    2020#define LEMON_BIN_HEAP_H
    2121
    22 ///\ingroup auxdat
     22///\ingroup heaps
    2323///\file
    24 ///\brief Binary Heap implementation.
     24///\brief Binary heap implementation.
    2525
    2626#include <vector>
    … …  
    3030namespace lemon {
    3131
    32   ///\ingroup auxdat
     32  /// \ingroup heaps
    3333  ///
    34   ///\brief A Binary Heap implementation.
     34  /// \brief Binary heap data structure.
    3535  ///
    36   ///This class implements the \e binary \e heap data structure.
    37   ///
    38   ///A \e heap is a data structure for storing items with specified values
    39   ///called \e priorities in such a way that finding the item with minimum
    40   ///priority is efficient. \c Comp specifies the ordering of the priorities.
    41   ///In a heap one can change the priority of an item, add or erase an
    42   ///item, etc.
     36  /// This class implements the \e binary \e heap data structure.
     37  /// It fully conforms to the \ref concepts::Heap "heap concept".
    4338  ///
    44   ///\tparam PR Type of the priority of the items.
    45   ///\tparam IM A read and writable item map with int values, used internally
    46   ///to handle the cross references.
    47   ///\tparam Comp A functor class for the ordering of the priorities.
    48   ///The default is \c std::less<PR>.
    49   ///
    50   ///\sa FibHeap
    51   ///\sa Dijkstra
    52   template <typename PR, typename IM, typename Comp = std::less<PR> >
     39  /// \tparam PR Type of the priorities of the items.
     40  /// \tparam IM A read-writable item map with \c int values, used
     41  /// internally to handle the cross references.
     42  /// \tparam CMP A functor class for comparing the priorities.
     43  /// The default is \c std::less<PR>.
     44#ifdef DOXYGEN
     45  template <typename PR, typename IM, typename CMP>
     46#else
     47  template <typename PR, typename IM, typename CMP = std::less<PR> >
     48#endif
    5349  class BinHeap {
    54 
    5550  public:
    56     ///\e
     51
     52    /// Type of the item-int map.
    5753    typedef IM ItemIntMap;
    58     ///\e
     54    /// Type of the priorities.
    5955    typedef PR Prio;
    60     ///\e
     56    /// Type of the items stored in the heap.
    6157    typedef typename ItemIntMap::Key Item;
    62     ///\e
     58    /// Type of the item-priority pairs.
    6359    typedef std::pair<Item,Prio> Pair;
    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
     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
    7167    /// heap's point of view, but may be useful to the user.
    7268    ///
    … …  
    8581
    8682  public:
    87     /// \brief The constructor.
    88     ///
    89     /// The constructor.
    90     /// \param map should be given to the constructor, since it is used
    91     /// internally to handle the cross references. The value of the map
    92     /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
     83
     84    /// \brief Constructor.
     85    ///
     86    /// Constructor.
     87    /// \param map A map that assigns \c int values to the items.
     88    /// It is used internally to handle the cross references.
     89    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    9390    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
    9491
    95     /// \brief The constructor.
    96     ///
    97     /// The constructor.
    98     /// \param map should be given to the constructor, since it is used
    99     /// internally to handle the cross references. The value of the map
    100     /// should be PRE_HEAP (-1) for each element.
    101     ///
    102     /// \param comp The comparator function object.
     92    /// \brief Constructor.
     93    ///
     94    /// Constructor.
     95    /// \param map A map that assigns \c int values to the items.
     96    /// It is used internally to handle the cross references.
     97    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     98    /// \param comp The function object used for comparing the priorities.
    10399    BinHeap(ItemIntMap &map, const Compare &comp)
    104100      : _iim(map), _comp(comp) {}
    105101
    106102
    107     /// The number of items stored in the heap.
    108     ///
    109     /// \brief Returns the number of items stored in the heap.
     103    /// \brief The number of items stored in the heap.
     104    ///
     105    /// This function returns the number of items stored in the heap.
    110106    int size() const { return _data.size(); }
    111107
    112     /// \brief Checks if the heap stores no items.
    113     ///
    114     /// Returns \c true if and only if the heap stores no items.
     108    /// \brief Check if the heap is empty.
     109    ///
     110    /// This function returns \c true if the heap is empty.
    115111    bool empty() const { return _data.empty(); }
    116112
    117     /// \brief Make empty this heap.
    118     ///
    119     /// Make empty this heap. It does not change the cross reference map.
    120     /// If you want to reuse what is not surely empty you should first clear
    121     /// the heap and after that you should set the cross reference map for
    122     /// each item to \c PRE_HEAP.
     113    /// \brief Make the heap empty.
     114    ///
     115    /// This functon makes the heap empty.
     116    /// It does not change the cross reference map. If you want to reuse
     117    /// a heap that is not surely empty, you should first clear it and
     118    /// then you should set the cross reference map to \c PRE_HEAP
     119    /// for each item.
    123120    void clear() {
    124121      _data.clear();
    … …  
    128125    static int parent(int i) { return (i-1)/2; }
    129126
    130     static int second_child(int i) { return 2*i+2; }
     127    static int secondChild(int i) { return 2*i+2; }
    131128    bool less(const Pair &p1, const Pair &p2) const {
    132129      return _comp(p1.second, p2.second);
    133130    }
    134131
    135     int bubble_up(int hole, Pair p) {
     132    int bubbleUp(int hole, Pair p) {
    136133      int par = parent(hole);
    137134      while( hole>0 && less(p,_data[par]) ) {
    … …  
    144141    }
    145142
    146     int bubble_down(int hole, Pair p, int length) {
    147       int child = second_child(hole);
     143    int bubbleDown(int hole, Pair p, int length) {
     144      int child = secondChild(hole);
    148145      while(child < length) {
    149146        if( less(_data[child-1], _data[child]) ) {
    … …  
    154151        move(_data[child], hole);
    155152        hole = child;
    156         child = second_child(hole);
     153        child = secondChild(hole);
    157154      }
    158155      child--;
    … …  
    172169
    173170  public:
     171
    174172    /// \brief Insert a pair of item and priority into the heap.
    175173    ///
    176     /// Adds \c p.first to the heap with priority \c p.second.
     174    /// This function inserts \c p.first to the heap with priority
     175    /// \c p.second.
    177176    /// \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       bubble_up(n, p);
    182     }
    183 
    184     /// \brief Insert an item into the heap with the given heap.
    185     ///
    186     /// Adds \c i to the heap with priority \c p.
     181      bubbleUp(n, p);
     182    }
     183
     184    /// \brief Insert an item into the heap with the given priority.
     185    ///
     186    /// This function inserts the given item into the heap with the
     187    /// given priority.
    187188    /// \param i The item to insert.
    188189    /// \param p The priority of the item.
     190    /// \pre \e i must not be stored in the heap.
    189191    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    190192
    191     /// \brief Returns the item with minimum priority relative to \c Compare.
    192     ///
    193     /// This method returns the item with minimum priority relative to \c
    194     /// Compare.
    195     /// \pre The heap must be nonempty.
     193    /// \brief Return the item having minimum priority.
     194    ///
     195    /// This function returns the item having minimum priority.
     196    /// \pre The heap must be non-empty.
    196197    Item top() const {
    197198      return _data[0].first;
    198199    }
    199200
    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.
     201    /// \brief The minimum priority.
     202    ///
     203    /// This function returns the minimum priority.
     204    /// \pre The heap must be non-empty.
    204205    Prio prio() const {
    205206      return _data[0].second;
    206207    }
    207208
    208     /// \brief Deletes the item with minimum priority relative to \c Compare.
    209     ///
    210     /// This method deletes the item with minimum priority relative to \c
    211     /// Compare from the heap.
     209    /// \brief Remove the item having minimum priority.
     210    ///
     211    /// This function removes the item having minimum priority.
    212212    /// \pre The heap must be non-empty.
    213213    void pop() {
    … …  
    215215      _iim.set(_data[0].first, POST_HEAP);
    216216      if (n > 0) {
    217         bubble_down(0, _data[n], n);
     217        bubbleDown(0, _data[n], n);
    218218      }
    219219      _data.pop_back();
    220220    }
    221221
    222     /// \brief Deletes \c i from the heap.
    223     ///
    224     /// This method deletes item \c i from the heap.
    225     /// \param i The item to erase.
    226     /// \pre The item should be in the heap.
     222    /// \brief Remove the given item from the heap.
     223    ///
     224    /// This function removes the given item from the heap if it is
     225    /// already stored.
     226    /// \param i The item to delete.
     227    /// \pre \e i must be in the heap.
    227228    void erase(const Item &i) {
    228229      int h = _iim[i];
    … …  
    230231      _iim.set(_data[h].first, POST_HEAP);
    231232      if( h < n ) {
    232         if ( bubble_up(h, _data[n]) == h) {
    233           bubble_down(h, _data[n], n);
     233        if ( bubbleUp(h, _data[n]) == h) {
     234          bubbleDown(h, _data[n], n);
    234235        }
    235236      }
    … …  
    237238    }
    238239
    239 
    240     /// \brief Returns the priority of \c i.
    241     ///
    242     /// This function returns the priority of item \c i.
    243     /// \param i The item.
    244     /// \pre \c i must be in the heap.
     240    /// \brief The priority of the given item.
     241    ///
     242    /// This function returns the priority of the given item.
     243    /// \param i The item.
     244    /// \pre \e i must be in the heap.
    245245    Prio operator[](const Item &i) const {
    246246      int idx = _iim[i];
    … …  
    248248    }
    249249
    250     /// \brief \c i gets to the heap with priority \c p independently
    251     /// if \c i was already there.
    252     ///
    253     /// This method calls \ref push(\c i, \c p) if \c i is not stored
    254     /// in the heap and sets the priority of \c i to \c p otherwise.
     250    /// \brief Set the priority of an item or insert it, if it is
     251    /// not stored in the heap.
     252    ///
     253    /// This method sets the priority of the given item if it is
     254    /// already stored in the heap. Otherwise it inserts the given
     255    /// item into the heap with the given priority.
    255256    /// \param i The item.
    256257    /// \param p The priority.
    … …  
    261262      }
    262263      else if( _comp(p, _data[idx].second) ) {
    263         bubble_up(idx, Pair(i,p));
     264        bubbleUp(idx, Pair(i,p));
    264265      }
    265266      else {
    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.
     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.
    273274    /// \param i The item.
    274275    /// \param p The priority.
    275     /// \pre \c i must be stored in the heap with priority at least \c
    276     /// p relative to \c Compare.
     276    /// \pre \e i must be stored in the heap with priority at least \e p.
    277277    void decrease(const Item &i, const Prio &p) {
    278278      int idx = _iim[i];
    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.
     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.
    285285    /// \param i The item.
    286286    /// \param p The priority.
    287     /// \pre \c i must be stored in the heap with priority at most \c
    288     /// p relative to \c Compare.
     287    /// \pre \e i must be stored in the heap with priority at most \e p.
    289288    void increase(const Item &i, const Prio &p) {
    290289      int idx = _iim[i];
    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.
     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.
    301300    /// \param i The item.
    302301    State state(const Item &i) const {
    … …  
    307306    }
    308307
    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.
     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.
    314313    /// \param i The item.
    315314    /// \param st The state. It should not be \c IN_HEAP.
    … …  
    328327    }
    329328
    330     /// \brief Replaces an item in the heap.
    331     ///
    332     /// The \c i item is replaced with \c j item. The \c i item should
    333     /// be in the heap, while the \c j should be out of the heap. The
    334     /// \c i item will out of the heap and \c j will be in the heap
    335     /// with the same prioriority as prevoiusly the \c i item.
     329    /// \brief Replace an item in the heap.
     330    ///
     331    /// This function replaces item \c i with item \c j.
     332    /// Item \c i must be in the heap, while \c j must be out of the heap.
     333    /// After calling this method, item \c i will be out of the
     334    /// heap and \c j will be in the heap with the same prioriority
     335    /// as item \c i had before.
    336336    void replace(const Item& i, const Item& j) {
    337337      int idx = _iim[i];

  • lemon/bits/array_map.h

    r664 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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

    r674 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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

    r664 r968  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    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-2008
     5 * Copyright (C) 2003-2010
    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
    283285    typedef typename Parent::Node Node;
    284286    typedef typename Parent::Arc Arc;
    … …  
    311313    Node oppositeNode(const Node &n, const Edge &e) const {
    312314      if( n == Parent::u(e))
    313         return Parent::v(e);
     315        return Parent::v(e);
    314316      else if( n == Parent::v(e))
    315         return Parent::u(e);
     317        return Parent::u(e);
    316318      else
    317         return INVALID;
     319        return INVALID;
    318320    }
    319321
    … …  
    339341
    340342    using Parent::notifier;
    341    
     343
    342344    ArcNotifier& notifier(Arc) const {
    343345      return arc_notifier;
    … …  
    349351
    350352
    351     class NodeIt : public Node { 
     353    class NodeIt : public Node {
    352354      const Graph* graph;
    353355    public:
    … …  
    358360
    359361      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
    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 { 
     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 {
    375377      const Graph* graph;
    376378    public:
    … …  
    381383
    382384      explicit ArcIt(const Graph& _graph) : graph(&_graph) {
    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 { 
     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 {
    398400      const Graph* graph;
    399401    public:
    … …  
    403405      OutArcIt(Invalid i) : Arc(i) { }
    404406
    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 { 
     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 {
    422424      const Graph* graph;
    423425    public:
    … …  
    427429      InArcIt(Invalid i) : Arc(i) { }
    428430
    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 { 
     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 {
    446448      const Graph* graph;
    447449    public:
    … …  
    452454
    453455      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
    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;
     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;
    463465      }
    464466
    … …  
    476478
    477479      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
    478         _graph.firstInc(*this, direction, n);
     480        _graph.firstInc(*this, direction, n);
    479481      }
    480482
    481483      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
    482         : graph(&_graph), Edge(ue) {
    483         direction = (_graph.source(ue) == n);
     484        : graph(&_graph), Edge(ue) {
     485        direction = (_graph.source(ue) == n);
    484486      }
    485487
    486488      IncEdgeIt& operator++() {
    487         graph->nextInc(*this, direction);
    488         return *this;
     489        graph->nextInc(*this, direction);
     490        return *this;
    489491      }
    490492    };
    … …  
    533535
    534536    template <typename _Value>
    535     class ArcMap 
     537    class ArcMap
    536538      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    537539      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    538540
    539541    public:
    540       ArcMap(const Graph& _g)
    541         : Parent(_g) {}
    542       ArcMap(const Graph& _g, const _Value& _v) 
    543         : Parent(_g, _v) {}
     542      explicit ArcMap(const Graph& _g)
     543        : Parent(_g) {}
     544      ArcMap(const Graph& _g, const _Value& _v)
     545        : Parent(_g, _v) {}
    544546
    545547      ArcMap& operator=(const ArcMap& cmap) {
    546         return operator=<ArcMap>(cmap);
     548        return operator=<ArcMap>(cmap);
    547549      }
    548550
    … …  
    550552      ArcMap& operator=(const CMap& cmap) {
    551553        Parent::operator=(cmap);
    552         return *this;
     554        return *this;
    553555      }
    554556
    … …  
    557559
    558560    template <typename _Value>
    559     class EdgeMap 
     561    class EdgeMap
    560562      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    561563      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    562564
    563565    public:
    564       EdgeMap(const Graph& _g)
    565         : Parent(_g) {}
    566 
    567       EdgeMap(const Graph& _g, const _Value& _v) 
    568         : Parent(_g, _v) {}
     566      explicit EdgeMap(const Graph& _g)
     567        : Parent(_g) {}
     568
     569      EdgeMap(const Graph& _g, const _Value& _v)
     570        : Parent(_g, _v) {}
    569571
    570572      EdgeMap& operator=(const EdgeMap& cmap) {
    571         return operator=<EdgeMap>(cmap);
     573        return operator=<EdgeMap>(cmap);
    572574      }
    573575
    … …  
    575577      EdgeMap& operator=(const CMap& cmap) {
    576578        Parent::operator=(cmap);
    577         return *this;
     579        return *this;
    578580      }
    579581
    … …  
    592594      return edge;
    593595    }
    594    
     596
    595597    void clear() {
    596598      notifier(Arc()).clear();
    … …  
    618620      arc_notifier.clear();
    619621    }
    620    
     622
    621623  };
    622624

  • lemon/bits/graph_adaptor_extender.h

    r664 r965  
    182182    typedef GraphAdaptorExtender Adaptor;
    183183
     184    typedef True UndirectedTag;
     185
    184186    typedef typename Parent::Node Node;
    185187    typedef typename Parent::Arc Arc;

  • lemon/bits/graph_extender.h

    r664 r825  
    5757    }
    5858
    59     Node fromId(int id, Node) const {
     59    static Node fromId(int id, Node) {
    6060      return Parent::nodeFromId(id);
    6161    }
    6262
    63     Arc fromId(int id, Arc) const {
     63    static Arc fromId(int id, Arc) {
    6464      return Parent::arcFromId(id);
    6565    }
    … …  
    356356    }
    357357
    358     Node fromId(int id, Node) const {
     358    static Node fromId(int id, Node) {
    359359      return Parent::nodeFromId(id);
    360360    }
    361361
    362     Arc fromId(int id, Arc) const {
     362    static Arc fromId(int id, Arc) {
    363363      return Parent::arcFromId(id);
    364364    }
    365365
    366     Edge fromId(int id, Edge) const {
     366    static Edge fromId(int id, Edge) {
    367367      return Parent::edgeFromId(id);
    368368    }
    … …  
    605605
    606606    public:
    607       NodeMap(const Graph& graph)
     607      explicit NodeMap(const Graph& graph)
    608608        : Parent(graph) {}
    609609      NodeMap(const Graph& graph, const _Value& value)
    … …  
    629629
    630630    public:
    631       ArcMap(const Graph& graph)
     631      explicit ArcMap(const Graph& graph)
    632632        : Parent(graph) {}
    633633      ArcMap(const Graph& graph, const _Value& value)
    … …  
    653653
    654654    public:
    655       EdgeMap(const Graph& graph)
     655      explicit EdgeMap(const Graph& graph)
    656656        : Parent(graph) {}
    657657

  • lemon/bits/map_extender.h

    r664 r867  
    5050    typedef typename Parent::ConstReference ConstReference;
    5151
     52    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
     53
    5254    class MapIt;
    5355    class ConstMapIt;
    … …  
    8385      typedef typename Map::Value Value;
    8486
    85       MapIt() {}
    86 
    87       MapIt(Invalid i) : Parent(i) { }
    88 
    89       explicit MapIt(Map& _map) : map(_map) {
    90         map.notifier()->first(*this);
     87      MapIt() : map(NULL) {}
     88
     89      MapIt(Invalid i) : Parent(i), map(NULL) {}
     90
     91      explicit MapIt(Map& _map) : map(&_map) {
     92        map->notifier()->first(*this);
    9193      }
    9294
    9395      MapIt(const Map& _map, const Item& item)
     96        : Parent(item), map(&_map) {}
     97
     98      MapIt& operator++() {
     99        map->notifier()->next(*this);
     100        return *this;
     101      }
     102
     103      typename MapTraits<Map>::ConstReturnValue operator*() const {
     104        return (*map)[*this];
     105      }
     106
     107      typename MapTraits<Map>::ReturnValue operator*() {
     108        return (*map)[*this];
     109      }
     110
     111      void set(const Value& value) {
     112        map->set(*this, value);
     113      }
     114
     115    protected:
     116      Map* map;
     117
     118    };
     119
     120    class ConstMapIt : public Item {
     121      typedef Item Parent;
     122
     123    public:
     124
     125      typedef typename Map::Value Value;
     126
     127      ConstMapIt() : map(NULL) {}
     128
     129      ConstMapIt(Invalid i) : Parent(i), map(NULL) {}
     130
     131      explicit ConstMapIt(Map& _map) : map(&_map) {
     132        map->notifier()->first(*this);
     133      }
     134
     135      ConstMapIt(const Map& _map, const Item& item)
    94136        : Parent(item), map(_map) {}
    95137
    96       MapIt& operator++() {
    97         map.notifier()->next(*this);
     138      ConstMapIt& operator++() {
     139        map->notifier()->next(*this);
    98140        return *this;
    99141      }
    … …  
    103145      }
    104146
    105       typename MapTraits<Map>::ReturnValue operator*() {
    106         return map[*this];
    107       }
    108 
    109       void set(const Value& value) {
    110         map.set(*this, value);
    111       }
    112 
    113     protected:
    114       Map& map;
    115 
    116     };
    117 
    118     class ConstMapIt : public Item {
    119       typedef Item Parent;
    120 
    121     public:
    122 
    123       typedef typename Map::Value Value;
    124 
    125       ConstMapIt() {}
    126 
    127       ConstMapIt(Invalid i) : Parent(i) { }
    128 
    129       explicit ConstMapIt(Map& _map) : map(_map) {
    130         map.notifier()->first(*this);
    131       }
    132 
    133       ConstMapIt(const Map& _map, const Item& item)
    134         : Parent(item), map(_map) {}
    135 
    136       ConstMapIt& operator++() {
    137         map.notifier()->next(*this);
    138         return *this;
    139       }
    140 
    141       typename MapTraits<Map>::ConstReturnValue operator*() const {
    142         return map[*this];
    143       }
    144 
    145     protected:
    146       const Map& map;
     147    protected:
     148      const Map* map;
    147149    };
    148150
    … …  
    151153
    152154    public:
    153 
    154       ItemIt() {}
    155 
    156       ItemIt(Invalid i) : Parent(i) { }
    157 
    158       explicit ItemIt(Map& _map) : map(_map) {
    159         map.notifier()->first(*this);
     155      ItemIt() : map(NULL) {}
     156
     157
     158      ItemIt(Invalid i) : Parent(i), map(NULL) {}
     159
     160      explicit ItemIt(Map& _map) : map(&_map) {
     161        map->notifier()->first(*this);
    160162      }
    161163
    162164      ItemIt(const Map& _map, const Item& item)
    163         : Parent(item), map(_map) {}
     165        : Parent(item), map(&_map) {}
    164166
    165167      ItemIt& operator++() {
    166         map.notifier()->next(*this);
    167         return *this;
    168       }
    169 
    170     protected:
    171       const Map& map;
     168        map->notifier()->next(*this);
     169        return *this;
     170      }
     171
     172    protected:
     173      const Map* map;
    172174
    173175    };
    … …  
    192194    typedef typename Parent::ConstReference ConstReference;
    193195
     196    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
     197
    194198    class MapIt;
    195199    class ConstMapIt;
    … …  
    228232      typedef typename Map::Value Value;
    229233
    230       MapIt() {}
    231 
    232       MapIt(Invalid i) : Parent(i) { }
    233 
    234       explicit MapIt(Map& _map) : map(_map) {
    235         map.graph.first(*this);
     234      MapIt() : map(NULL) {}
     235
     236      MapIt(Invalid i) : Parent(i), map(NULL) { }
     237
     238      explicit MapIt(Map& _map) : map(&_map) {
     239        map->graph.first(*this);
    236240      }
    237241
    238242      MapIt(const Map& _map, const Item& item)
    239         : Parent(item), map(_map) {}
     243        : Parent(item), map(&_map) {}
    240244
    241245      MapIt& operator++() {
    242         map.graph.next(*this);
     246        map->graph.next(*this);
    243247        return *this;
    244248      }
    245249
    246250      typename MapTraits<Map>::ConstReturnValue operator*() const {
    247         return map[*this];
     251        return (*map)[*this];
    248252      }
    249253
    250254      typename MapTraits<Map>::ReturnValue operator*() {
    251         return map[*this];
     255        return (*map)[*this];
    252256      }
    253257
    254258      void set(const Value& value) {
    255         map.set(*this, value);
    256       }
    257 
    258     protected:
    259       Map& map;
     259        map->set(*this, value);
     260      }
     261
     262    protected:
     263      Map* map;
    260264
    261265    };
    … …  
    268272      typedef typename Map::Value Value;
    269273
    270       ConstMapIt() {}
    271 
    272       ConstMapIt(Invalid i) : Parent(i) { }
    273 
    274       explicit ConstMapIt(Map& _map) : map(_map) {
    275         map.graph.first(*this);
     274      ConstMapIt() : map(NULL) {}
     275
     276      ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
     277
     278      explicit ConstMapIt(Map& _map) : map(&_map) {
     279        map->graph.first(*this);
    276280      }
    277281
    278282      ConstMapIt(const Map& _map, const Item& item)
    279         : Parent(item), map(_map) {}
     283        : Parent(item), map(&_map) {}
    280284
    281285      ConstMapIt& operator++() {
    282         map.graph.next(*this);
     286        map->graph.next(*this);
    283287        return *this;
    284288      }
    285289
    286290      typename MapTraits<Map>::ConstReturnValue operator*() const {
    287         return map[*this];
    288       }
    289 
    290     protected:
    291       const Map& map;
     291        return (*map)[*this];
     292      }
     293
     294    protected:
     295      const Map* map;
    292296    };
    293297
    … …  
    296300
    297301    public:
    298 
    299       ItemIt() {}
    300 
    301       ItemIt(Invalid i) : Parent(i) { }
    302 
    303       explicit ItemIt(Map& _map) : map(_map) {
    304         map.graph.first(*this);
     302      ItemIt() : map(NULL) {}
     303
     304
     305      ItemIt(Invalid i) : Parent(i), map(NULL) { }
     306
     307      explicit ItemIt(Map& _map) : map(&_map) {
     308        map->graph.first(*this);
    305309      }
    306310
    307311      ItemIt(const Map& _map, const Item& item)
    308         : Parent(item), map(_map) {}
     312        : Parent(item), map(&_map) {}
    309313
    310314      ItemIt& operator++() {
    311         map.graph.next(*this);
    312         return *this;
    313       }
    314 
    315     protected:
    316       const Map& map;
     315        map->graph.next(*this);
     316        return *this;
     317      }
     318
     319    protected:
     320      const Map* map;
    317321
    318322    };

  • lemon/bits/path_dump.h

    r576 r973  
    5050
    5151    bool empty() const {
    52       return predMap[target] != INVALID;
     52      return predMap[target] == INVALID;
    5353    }
    5454
    … …  
    124124
    125125    bool empty() const {
    126       return source != target;
     126      return predMatrixMap(source, target) == INVALID;
    127127    }
    128128

  • lemon/bits/solver_bits.h

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

  • lemon/bits/windows.cc

    r513 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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

    r623 r793  
    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  }
    97109
    98110  void CbcMip::_eraseCol(int i) {

  • lemon/cbc.h

    r623 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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);
    6566
    6667    virtual void _eraseCol(int i);
    … …  
    121122    int _message_level;
    122123
    123    
     124
    124125
    125126  };

  • lemon/circulation.h

    r735 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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
    7578    typedef typename Digraph::template ArcMap<Value> FlowMap;
     79#endif
    7680
    7781    /// \brief Instantiates a FlowMap.
    … …  
    8892    /// The elevator type used by the algorithm.
    8993    ///
    90     /// \sa Elevator
    91     /// \sa LinkedElevator
     94    /// \sa Elevator, LinkedElevator
     95#ifdef DOXYGEN
     96    typedef lemon::Elevator<GR, GR::Node> Elevator;
     97#else
    9298    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
     99#endif
    93100
    94101    /// \brief Instantiates an Elevator.
    … …  
    135142     \geq sup(u) \quad \forall u\in V, \f]
    136143     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
    137      
     144
    138145     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
    139146     zero or negative in order to have a feasible solution (since the sum
    … …  
    145152     constraints have to be satisfied with equality, i.e. all demands
    146153     have to be satisfied and all supplies have to be used.
    147      
     154
    148155     If you need the opposite inequalities in the supply/demand constraints
    149156     (i.e. the total demand is less than the total supply and all the demands
    … …  
    167174     \tparam SM The type of the supply map. The default map type is
    168175     \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.
    169181  */
    170182#ifdef DOXYGEN
    … …  
    300312    /// able to automatically created by the algorithm (i.e. the
    301313    /// digraph and the maximum level should be passed to it).
    302     /// However an external elevator object could also be passed to the
     314    /// However, an external elevator object could also be passed to the
    303315    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
    304316    /// before calling \ref run() or \ref init().
    … …  
    326338    /// \param graph The digraph the algorithm runs on.
    327339    /// \param lower The lower bounds for the flow values on the arcs.
    328     /// \param upper The upper bounds (capacities) for the flow values 
     340    /// \param upper The upper bounds (capacities) for the flow values
    329341    /// on the arcs.
    330342    /// \param supply The signed supply values of the nodes.
    … …  
    451463    }
    452464
    453     /// \brief Sets the tolerance used by algorithm.
    454     ///
    455     /// Sets the tolerance used by algorithm.
     465    /// \brief Sets the tolerance used by the algorithm.
     466    ///
     467    /// Sets the tolerance object used by the algorithm.
     468    /// \return <tt>(*this)</tt>
    456469    Circulation& tolerance(const Tolerance& tolerance) {
    457470      _tol = tolerance;
    … …  
    461474    /// \brief Returns a const reference to the tolerance.
    462475    ///
    463     /// Returns a const reference to the tolerance.
     476    /// Returns a const reference to the tolerance object used by
     477    /// the algorithm.
    464478    const Tolerance& tolerance() const {
    465479      return _tol;
    … …  
    468482    /// \name Execution Control
    469483    /// The simplest way to execute the algorithm is to call \ref run().\n
    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
     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
    472486    /// the \ref start() function.
    473487

  • lemon/clp.cc

    r623 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    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);
    7891    return _prob->numberRows() - 1;
    7992  }

  • lemon/clp.h

    r623 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    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);
    7879
    7980    virtual void _eraseCol(int i);
    … …  
    138139
    139140    virtual void _messageLevel(MessageLevel);
    140    
     141
    141142  public:
    142143

  • lemon/concepts/digraph.h

    r627 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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 \ref concept "concept" of the
    39     /// immutable directed digraphs.
     38    /// This class describes the common interface of all directed
     39    /// graphs (digraphs).
    4040    ///
    41     /// Note that actual digraph implementation like @ref ListDigraph or
    42     /// @ref SmartDigraph may have several additional functionality.
     41    /// Like all concept classes, it only provides an interface
     42    /// without any sensible implementation. So any general algorithm for
     43    /// directed graphs should compile with this class, but it will not
     44    /// run properly, of course.
     45    /// An actual digraph implementation like \ref ListDigraph or
     46    /// \ref SmartDigraph may have additional functionality.
    4347    ///
    44     /// \sa concept
     48    /// \sa Graph
    4549    class Digraph {
    4650    private:
    47       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    48 
    49       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    50       ///
    51       Digraph(const Digraph &) {};
    52       ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
    53       ///\e not allowed. Use DigraphCopy() instead.
    54 
    55       ///Assignment of \ref Digraph "Digraph"s to another ones are
    56       ///\e not allowed.  Use DigraphCopy() instead.
    57 
     51      /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
     52      Digraph(const Digraph &) {}
     53      /// \brief Assignment of a digraph to another one is \e not allowed.
     54      /// Use DigraphCopy instead.
    5855      void operator=(const Digraph &) {}
     56
    5957    public:
    60       ///\e
    61 
    62       /// Defalult constructor.
    63 
    64       /// Defalult constructor.
    65       ///
     58      /// Default constructor.
    6659      Digraph() { }
    67       /// Class for identifying a node of the digraph
     60
     61      /// The node type of the digraph
    6862
    6963      /// This class identifies a node of the digraph. It also serves
    7064      /// as a base class of the node iterators,
    71       /// thus they will convert to this type.
     65      /// thus they convert to this type.
    7266      class Node {
    7367      public:
    7468        /// Default constructor
    7569
    76         /// @warning The default constructor sets the iterator
    77         /// to an undefined value.
     70        /// Default constructor.
     71        /// \warning It sets the object to an undefined value.
    7872        Node() { }
    7973        /// Copy constructor.
    … …  
    8377        Node(const Node&) { }
    8478
    85         /// Invalid constructor \& conversion.
    86 
    87         /// This constructor initializes the iterator to be invalid.
     79        /// %Invalid constructor \& conversion.
     80
     81        /// Initializes the object to be invalid.
    8882        /// \sa Invalid for more details.
    8983        Node(Invalid) { }
    9084        /// Equality operator
    9185
     86        /// Equality operator.
     87        ///
    9288        /// Two iterators are equal if and only if they point to the
    93         /// same object or both are invalid.
     89        /// same object or both are \c INVALID.
    9490        bool operator==(Node) const { return true; }
    9591
    9692        /// Inequality operator
    9793
    98         /// \sa operator==(Node n)
    99         ///
     94        /// Inequality operator.
    10095        bool operator!=(Node) const { return true; }
    10196
    10297        /// Artificial ordering operator.
    10398
    104         /// To allow the use of digraph descriptors as key type in std::map or
    105         /// similar associative container we require this.
    106         ///
    107         /// \note This operator only have to define some strict ordering of
    108         /// the items; this order has nothing to do with the iteration
    109         /// ordering of the items.
     99        /// Artificial ordering operator.
     100        ///
     101        /// \note This operator only has to define some strict ordering of
     102        /// the nodes; this order has nothing to do with the iteration
     103        /// ordering of the nodes.
    110104        bool operator<(Node) const { return false; }
    111 
    112       };
    113 
    114       /// This iterator goes through each node.
    115 
    116       /// This iterator goes through each node.
    117       /// Its usage is quite simple, for example you can count the number
    118       /// of nodes in digraph \c g of type \c Digraph like this:
     105      };
     106
     107      /// Iterator class for the nodes.
     108
     109      /// This iterator goes through each node of the digraph.
     110      /// Its usage is quite simple, for example, you can count the number
     111      /// of nodes in a digraph \c g of type \c %Digraph like this:
    119112      ///\code
    120113      /// int count=0;
    … …  
    125118        /// Default constructor
    126119
    127         /// @warning The default constructor sets the iterator
    128         /// to an undefined value.
     120        /// Default constructor.
     121        /// \warning It sets the iterator to an undefined value.
    129122        NodeIt() { }
    130123        /// Copy constructor.
    … …  
    133126        ///
    134127        NodeIt(const NodeIt& n) : Node(n) { }
    135         /// Invalid constructor \& conversion.
    136 
    137         /// Initialize the iterator to be invalid.
     128        /// %Invalid constructor \& conversion.
     129
     130        /// Initializes the iterator to be invalid.
    138131        /// \sa Invalid for more details.
    139132        NodeIt(Invalid) { }
    140133        /// Sets the iterator to the first node.
    141134
    142         /// Sets the iterator to the first node of \c g.
    143         ///
    144         NodeIt(const Digraph&) { }
    145         /// Node -> NodeIt conversion.
    146 
    147         /// Sets the iterator to the node of \c the digraph pointed by
    148         /// the trivial iterator.
    149         /// This feature necessitates that each time we
    150         /// iterate the arc-set, the iteration order is the same.
     135        /// Sets the iterator to the first node of the given digraph.
     136        ///
     137        explicit NodeIt(const Digraph&) { }
     138        /// Sets the iterator to the given node.
     139
     140        /// Sets the iterator to the given node of the given digraph.
     141        ///
    151142        NodeIt(const Digraph&, const Node&) { }
    152143        /// Next node.
    … …  
    158149
    159150
    160       /// Class for identifying an arc of the digraph
     151      /// The arc type of the digraph
    161152
    162153      /// This class identifies an arc of the digraph. It also serves
    … …  
    167158        /// Default constructor
    168159
    169         /// @warning The default constructor sets the iterator
    170         /// to an undefined value.
     160        /// Default constructor.
     161        /// \warning It sets the object to an undefined value.
    171162        Arc() { }
    172163        /// Copy constructor.
    … …  
    175166        ///
    176167        Arc(const Arc&) { }
    177         /// Initialize the iterator to be invalid.
    178 
    179         /// Initialize the iterator to be invalid.
    180         ///
     168        /// %Invalid constructor \& conversion.
     169
     170        /// Initializes the object to be invalid.
     171        /// \sa Invalid for more details.
    181172        Arc(Invalid) { }
    182173        /// Equality operator
    183174
     175        /// Equality operator.
     176        ///
    184177        /// Two iterators are equal if and only if they point to the
    185         /// same object or both are invalid.
     178        /// same object or both are \c INVALID.
    186179        bool operator==(Arc) const { return true; }
    187180        /// Inequality operator
    188181
    189         /// \sa operator==(Arc n)
    190         ///
     182        /// Inequality operator.
    191183        bool operator!=(Arc) const { return true; }
    192184
    193185        /// Artificial ordering operator.
    194186
    195         /// To allow the use of digraph descriptors as key type in std::map or
    196         /// similar associative container we require this.
    197         ///
    198         /// \note This operator only have to define some strict ordering of
    199         /// the items; this order has nothing to do with the iteration
    200         /// ordering of the items.
     187        /// Artificial ordering operator.
     188        ///
     189        /// \note This operator only has to define some strict ordering of
     190        /// the arcs; this order has nothing to do with the iteration
     191        /// ordering of the arcs.
    201192        bool operator<(Arc) const { return false; }
    202193      };
    203194
    204       /// This iterator goes trough the outgoing arcs of a node.
     195      /// Iterator class for the outgoing arcs of a node.
    205196
    206197      /// This iterator goes trough the \e outgoing arcs of a certain node
    207198      /// of a digraph.
    208       /// Its usage is quite simple, for example you can count the number
     199      /// Its usage is quite simple, for example, you can count the number
    209200      /// of outgoing arcs of a node \c n
    210       /// in digraph \c g of type \c Digraph as follows.
     201      /// in a digraph \c g of type \c %Digraph as follows.
    211202      ///\code
    212203      /// int count=0;
    213       /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
     204      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
    214205      ///\endcode
    215 
    216206      class OutArcIt : public Arc {
    217207      public:
    218208        /// Default constructor
    219209
    220         /// @warning The default constructor sets the iterator
    221         /// to an undefined value.
     210        /// Default constructor.
     211        /// \warning It sets the iterator to an undefined value.
    222212        OutArcIt() { }
    223213        /// Copy constructor.
    … …  
    226216        ///
    227217        OutArcIt(const OutArcIt& e) : Arc(e) { }
    228         /// Initialize the iterator to be invalid.
    229 
    230         /// Initialize the iterator to be invalid.
    231         ///
     218        /// %Invalid constructor \& conversion.
     219
     220        /// Initializes the iterator to be invalid.
     221        /// \sa Invalid for more details.
    232222        OutArcIt(Invalid) { }
    233         /// This constructor sets the iterator to the first outgoing arc.
    234 
    235         /// This constructor sets the iterator to the first outgoing arc of
    236         /// the node.
     223        /// Sets the iterator to the first outgoing arc.
     224
     225        /// Sets the iterator to the first outgoing arc of the given node.
     226        ///
    237227        OutArcIt(const Digraph&, const Node&) { }
    238         /// Arc -> OutArcIt conversion
    239 
    240         /// Sets the iterator to the value of the trivial iterator.
    241         /// This feature necessitates that each time we
    242         /// iterate the arc-set, the iteration order is the same.
     228        /// Sets the iterator to the given arc.
     229
     230        /// Sets the iterator to the given arc of the given digraph.
     231        ///
    243232        OutArcIt(const Digraph&, const Arc&) { }
    244         ///Next outgoing arc
     233        /// Next outgoing arc
    245234
    246235        /// Assign the iterator to the next
    … …  
    249238      };
    250239
    251       /// This iterator goes trough the incoming arcs of a node.
     240      /// Iterator class for the incoming arcs of a node.
    252241
    253242      /// This iterator goes trough the \e incoming arcs of a certain node
    254243      /// of a digraph.
    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.
     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.
    258247      ///\code
    259248      /// int count=0;
    260       /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
     249      /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
    261250      ///\endcode
    262 
    263251      class InArcIt : public Arc {
    264252      public:
    265253        /// Default constructor
    266254
    267         /// @warning The default constructor sets the iterator
    268         /// to an undefined value.
     255        /// Default constructor.
     256        /// \warning It sets the iterator to an undefined value.
    269257        InArcIt() { }
    270258        /// Copy constructor.
    … …  
    273261        ///
    274262        InArcIt(const InArcIt& e) : Arc(e) { }
    275         /// Initialize the iterator to be invalid.
    276 
    277         /// Initialize the iterator to be invalid.
    278         ///
     263        /// %Invalid constructor \& conversion.
     264
     265        /// Initializes the iterator to be invalid.
     266        /// \sa Invalid for more details.
    279267        InArcIt(Invalid) { }
    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.
     268        /// Sets the iterator to the first incoming arc.
     269
     270        /// Sets the iterator to the first incoming arc of the given node.
     271        ///
    284272        InArcIt(const Digraph&, const Node&) { }
    285         /// Arc -> InArcIt conversion
    286 
    287         /// Sets the iterator to the value of the trivial iterator \c e.
    288         /// This feature necessitates that each time we
    289         /// iterate the arc-set, the iteration order is the same.
     273        /// Sets the iterator to the given arc.
     274
     275        /// Sets the iterator to the given arc of the given digraph.
     276        ///
    290277        InArcIt(const Digraph&, const Arc&) { }
    291278        /// Next incoming arc
    292279
    293         /// Assign the iterator to the next inarc of the corresponding node.
    294         ///
     280        /// Assign the iterator to the next
     281        /// incoming arc of the corresponding node.
    295282        InArcIt& operator++() { return *this; }
    296283      };
    297       /// This iterator goes through each arc.
    298 
    299       /// This iterator goes through each arc of a digraph.
    300       /// Its usage is quite simple, for example you can count the number
    301       /// of arcs in a digraph \c g of type \c Digraph as follows:
     284
     285      /// Iterator class for the arcs.
     286
     287      /// This iterator goes through each arc of the digraph.
     288      /// Its usage is quite simple, for example, you can count the number
     289      /// of arcs in a digraph \c g of type \c %Digraph as follows:
    302290      ///\code
    303291      /// int count=0;
    304       /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
     292      /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
    305293      ///\endcode
    306294      class ArcIt : public Arc {
    … …  
    308296        /// Default constructor
    309297
    310         /// @warning The default constructor sets the iterator
    311         /// to an undefined value.
     298        /// Default constructor.
     299        /// \warning It sets the iterator to an undefined value.
    312300        ArcIt() { }
    313301        /// Copy constructor.
    … …  
    316304        ///
    317305        ArcIt(const ArcIt& e) : Arc(e) { }
    318         /// Initialize the iterator to be invalid.
    319 
    320         /// Initialize the iterator to be invalid.
    321         ///
     306        /// %Invalid constructor \& conversion.
     307
     308        /// Initializes the iterator to be invalid.
     309        /// \sa Invalid for more details.
    322310        ArcIt(Invalid) { }
    323         /// This constructor sets the iterator to the first arc.
    324 
    325         /// This constructor sets the iterator to the first arc of \c g.
    326         ///@param g the digraph
    327         ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
    328         /// Arc -> ArcIt conversion
    329 
    330         /// Sets the iterator to the value of the trivial iterator \c e.
    331         /// This feature necessitates that each time we
    332         /// iterate the arc-set, the iteration order is the same.
     311        /// Sets the iterator to the first arc.
     312
     313        /// Sets the iterator to the first arc of the given digraph.
     314        ///
     315        explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
     316        /// Sets the iterator to the given arc.
     317
     318        /// Sets the iterator to the given arc of the given digraph.
     319        ///
    333320        ArcIt(const Digraph&, const Arc&) { }
    334         ///Next arc
     321        /// Next arc
    335322
    336323        /// Assign the iterator to the next arc.
     324        ///
    337325        ArcIt& operator++() { return *this; }
    338326      };
    339       ///Gives back the target node of an arc.
    340 
    341       ///Gives back the target node of an arc.
    342       ///
     327
     328      /// \brief The source node of the arc.
     329      ///
     330      /// Returns the source node of the given arc.
     331      Node source(Arc) const { return INVALID; }
     332
     333      /// \brief The target node of the arc.
     334      ///
     335      /// Returns the target node of the given arc.
    343336      Node target(Arc) const { return INVALID; }
    344       ///Gives back the source node of an arc.
    345 
    346       ///Gives back the source node of an arc.
    347       ///
    348       Node source(Arc) const { return INVALID; }
    349 
    350       /// \brief Returns the ID of the node.
     337
     338      /// \brief The ID of the node.
     339      ///
     340      /// Returns the ID of the given node.
    351341      int id(Node) const { return -1; }
    352342
    353       /// \brief Returns the ID of the arc.
     343      /// \brief The ID of the arc.
     344      ///
     345      /// Returns the ID of the given arc.
    354346      int id(Arc) const { return -1; }
    355347
    356       /// \brief Returns the node with the given ID.
    357       ///
    358       /// \pre The argument should be a valid node ID in the graph.
     348      /// \brief The node with the given ID.
     349      ///
     350      /// Returns the node with the given ID.
     351      /// \pre The argument should be a valid node ID in the digraph.
    359352      Node nodeFromId(int) const { return INVALID; }
    360353
    361       /// \brief Returns the arc with the given ID.
    362       ///
    363       /// \pre The argument should be a valid arc ID in the graph.
     354      /// \brief The arc with the given ID.
     355      ///
     356      /// Returns the arc with the given ID.
     357      /// \pre The argument should be a valid arc ID in the digraph.
    364358      Arc arcFromId(int) const { return INVALID; }
    365359
    366       /// \brief Returns an upper bound on the node IDs.
     360      /// \brief An upper bound on the node IDs.
     361      ///
     362      /// Returns an upper bound on the node IDs.
    367363      int maxNodeId() const { return -1; }
    368364
    369       /// \brief Returns an upper bound on the arc IDs.
     365      /// \brief An upper bound on the arc IDs.
     366      ///
     367      /// Returns an upper bound on the arc IDs.
    370368      int maxArcId() const { return -1; }
    371369
    … …  
    393391      int maxId(Arc) const { return -1; }
    394392
     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
    395398      /// \brief The base node of the iterator.
    396399      ///
    397       /// Gives back the base node of the iterator.
    398       /// It is always the target of the pointed arc.
    399       Node baseNode(const InArcIt&) const { return INVALID; }
     400      /// Returns the base node of the given outgoing arc iterator
     401      /// (i.e. the source node of the corresponding arc).
     402      Node baseNode(OutArcIt) const { return INVALID; }
    400403
    401404      /// \brief The running node of the iterator.
    402405      ///
    403       /// Gives back the running node of the iterator.
    404       /// It is always the source of the pointed arc.
    405       Node runningNode(const InArcIt&) const { return INVALID; }
     406      /// Returns the running node of the given outgoing arc iterator
     407      /// (i.e. the target node of the corresponding arc).
     408      Node runningNode(OutArcIt) const { return INVALID; }
    406409
    407410      /// \brief The base node of the iterator.
    408411      ///
    409       /// Gives back the base node of the iterator.
    410       /// It is always the source of the pointed arc.
    411       Node baseNode(const OutArcIt&) const { return INVALID; }
     412      /// Returns the base node of the given incomming arc iterator
     413      /// (i.e. the target node of the corresponding arc).
     414      Node baseNode(InArcIt) const { return INVALID; }
    412415
    413416      /// \brief The running node of the iterator.
    414417      ///
    415       /// Gives back the running node of the iterator.
    416       /// It is always the target of the pointed arc.
    417       Node runningNode(const OutArcIt&) const { return INVALID; }
    418 
    419       /// \brief The opposite node on the given arc.
    420       ///
    421       /// Gives back the opposite node on the given arc.
    422       Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
    423 
    424       /// \brief Reference map of the nodes to type \c T.
    425       ///
    426       /// Reference map of the nodes to type \c T.
     418      /// Returns the running node of the given incomming arc iterator
     419      /// (i.e. the source node of the corresponding arc).
     420      Node runningNode(InArcIt) const { return INVALID; }
     421
     422      /// \brief Standard graph map type for the nodes.
     423      ///
     424      /// Standard graph map type for the nodes.
     425      /// It conforms to the ReferenceMap concept.
    427426      template<class T>
    428427      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
    429428      public:
    430429
    431         ///\e
    432         NodeMap(const Digraph&) { }
    433         ///\e
     430        /// Constructor
     431        explicit NodeMap(const Digraph&) { }
     432        /// Constructor with given initial value
    434433        NodeMap(const Digraph&, T) { }
    435434
    436435      private:
    437436        ///Copy constructor
    438         NodeMap(const NodeMap& nm) : 
     437        NodeMap(const NodeMap& nm) :
    439438          ReferenceMap<Node, T, T&, const T&>(nm) { }
    440439        ///Assignment operator
    … …  
    446445      };
    447446
    448       /// \brief Reference map of the arcs to type \c T.
    449       ///
    450       /// Reference map of the arcs to type \c T.
     447      /// \brief Standard graph map type for the arcs.
     448      ///
     449      /// Standard graph map type for the arcs.
     450      /// It conforms to the ReferenceMap concept.
    451451      template<class T>
    452452      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
    453453      public:
    454454
    455         ///\e
    456         ArcMap(const Digraph&) { }
    457         ///\e
     455        /// Constructor
     456        explicit ArcMap(const Digraph&) { }
     457        /// Constructor with given initial value
    458458        ArcMap(const Digraph&, T) { }
     459
    459460      private:
    460461        ///Copy constructor

  • lemon/concepts/graph.h

    r704 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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>
    2729#include <lemon/core.h>
    2830
    … …  
    3234    /// \ingroup graph_concepts
    3335    ///
    34     /// \brief Class describing the concept of Undirected Graphs.
     36    /// \brief Class describing the concept of undirected graphs.
    3537    ///
    36     /// This class describes the common interface of all Undirected
    37     /// Graphs.
     38    /// This class describes the common interface of all undirected
     39    /// graphs.
    3840    ///
    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
     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
    4244    /// run properly, of course.
     45    /// An actual graph implementation like \ref ListGraph or
     46    /// \ref SmartGraph may have additional functionality.
    4347    ///
    44     /// The LEMON undirected graphs also fulfill the concept of
    45     /// directed graphs (\ref lemon::concepts::Digraph "Digraph
    46     /// Concept"). Each edges can be seen as two opposite
    47     /// directed arc and consequently the undirected graph can be
    48     /// seen as the direceted graph of these directed arcs. The
    49     /// Graph has the Edge inner class for the edges and
    50     /// the Arc type for the directed arcs. The Arc type is
    51     /// convertible to Edge or inherited from it so from a directed
    52     /// arc we can get the represented edge.
     48    /// The undirected graphs also fulfill the concept of \ref Digraph
     49    /// "directed graphs", since each edge can also be regarded as two
     50    /// oppositely directed arcs.
     51    /// Undirected graphs provide an Edge type for the undirected edges and
     52    /// an Arc type for the directed arcs. The Arc type is convertible to
     53    /// Edge or inherited from it, i.e. the corresponding edge can be
     54    /// obtained from an arc.
     55    /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
     56    /// and ArcMap classes can be used for the arcs (just like in digraphs).
     57    /// Both InArcIt and OutArcIt iterates on the same edges but with
     58    /// opposite direction. IncEdgeIt also iterates on the same edges
     59    /// as OutArcIt and InArcIt, but it is not convertible to Arc,
     60    /// only to Edge.
    5361    ///
    54     /// In the sense of the LEMON each edge has a default
    55     /// direction (it should be in every computer implementation,
    56     /// because the order of edge's nodes defines an
    57     /// orientation). With the default orientation we can define that
    58     /// the directed arc is forward or backward directed. With the \c
    59     /// direction() and \c direct() function we can get the direction
    60     /// of the directed arc and we can direct an edge.
     62    /// In LEMON, each undirected edge has an inherent orientation.
     63    /// Thus it can defined if an arc is forward or backward oriented in
     64    /// an undirected graph with respect to this default oriantation of
     65    /// the represented edge.
     66    /// With the direction() and direct() functions the direction
     67    /// of an arc can be obtained and set, respectively.
    6168    ///
    62     /// The EdgeIt is an iterator for the edges. We can use
    63     /// the EdgeMap to map values for the edges. The InArcIt and
    64     /// OutArcIt iterates on the same edges but with opposite
    65     /// direction. The IncEdgeIt iterates also on the same edges
    66     /// as the OutArcIt and InArcIt but it is not convertible to Arc just
    67     /// to Edge.
     69    /// Only nodes and edges can be added to or removed from an undirected
     70    /// graph and the corresponding arcs are added or removed automatically.
     71    ///
     72    /// \sa Digraph
    6873    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
    6981    public:
    70       /// \brief The undirected graph should be tagged by the
    71       /// UndirectedTag.
    72       ///
    73       /// The undirected graph should be tagged by the UndirectedTag. This
    74       /// tag helps the enable_if technics to make compile time
     82      /// Default constructor.
     83      Graph() {}
     84
     85      /// \brief Undirected graphs should be tagged with \c UndirectedTag.
     86      ///
     87      /// Undirected graphs should be tagged with \c UndirectedTag.
     88      ///
     89      /// This tag helps the \c enable_if technics to make compile time
    7590      /// specializations for undirected graphs.
    7691      typedef True UndirectedTag;
    7792
    78       /// \brief The base type of node iterators,
    79       /// or in other words, the trivial node iterator.
    80       ///
    81       /// This is the base type of each node iterator,
    82       /// thus each kind of node iterator converts to this.
    83       /// More precisely each kind of node iterator should be inherited
    84       /// from the trivial node iterator.
     93      /// The node type of the graph
     94
     95      /// This class identifies a node of the graph. It also serves
     96      /// as a base class of the node iterators,
     97      /// thus they convert to this type.
    8598      class Node {
    8699      public:
    87100        /// Default constructor
    88101
    89         /// @warning The default constructor sets the iterator
    90         /// to an undefined value.
     102        /// Default constructor.
     103        /// \warning It sets the object to an undefined value.
    91104        Node() { }
    92105        /// Copy constructor.
    … …  
    96109        Node(const Node&) { }
    97110
    98         /// Invalid constructor \& conversion.
    99 
    100         /// This constructor initializes the iterator to be invalid.
     111        /// %Invalid constructor \& conversion.
     112
     113        /// Initializes the object to be invalid.
    101114        /// \sa Invalid for more details.
    102115        Node(Invalid) { }
    103116        /// Equality operator
    104117
     118        /// Equality operator.
     119        ///
    105120        /// Two iterators are equal if and only if they point to the
    106         /// same object or both are invalid.
     121        /// same object or both are \c INVALID.
    107122        bool operator==(Node) const { return true; }
    108123
    109124        /// Inequality operator
    110125
    111         /// \sa operator==(Node n)
    112         ///
     126        /// Inequality operator.
    113127        bool operator!=(Node) const { return true; }
    114128
    115129        /// Artificial ordering operator.
    116130
    117         /// To allow the use of graph descriptors as key type in std::map or
    118         /// similar associative container we require this.
    119         ///
    120         /// \note This operator only have to define some strict ordering of
     131        /// Artificial ordering operator.
     132        ///
     133        /// \note This operator only has to define some strict ordering of
    121134        /// the items; this order has nothing to do with the iteration
    122135        /// ordering of the items.
    … …  
    125138      };
    126139
    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:
     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:
    132145      ///\code
    133146      /// int count=0;
    … …  
    138151        /// Default constructor
    139152
    140         /// @warning The default constructor sets the iterator
    141         /// to an undefined value.
     153        /// Default constructor.
     154        /// \warning It sets the iterator to an undefined value.
    142155        NodeIt() { }
    143156        /// Copy constructor.
    … …  
    146159        ///
    147160        NodeIt(const NodeIt& n) : Node(n) { }
    148         /// Invalid constructor \& conversion.
    149 
    150         /// Initialize the iterator to be invalid.
     161        /// %Invalid constructor \& conversion.
     162
     163        /// Initializes the iterator to be invalid.
    151164        /// \sa Invalid for more details.
    152165        NodeIt(Invalid) { }
    153166        /// Sets the iterator to the first node.
    154167
    155         /// Sets the iterator to the first node of \c g.
    156         ///
    157         NodeIt(const Graph&) { }
    158         /// Node -> NodeIt conversion.
    159 
    160         /// Sets the iterator to the node of \c the graph pointed by
    161         /// the trivial iterator.
    162         /// This feature necessitates that each time we
    163         /// iterate the arc-set, the iteration order is the same.
     168        /// Sets the iterator to the first node of the given digraph.
     169        ///
     170        explicit NodeIt(const Graph&) { }
     171        /// Sets the iterator to the given node.
     172
     173        /// Sets the iterator to the given node of the given digraph.
     174        ///
    164175        NodeIt(const Graph&, const Node&) { }
    165176        /// Next node.
    … …  
    171182
    172183
    173       /// The base type of the edge iterators.
    174 
    175       /// The base type of the edge iterators.
    176       ///
     184      /// The edge type of the graph
     185
     186      /// This class identifies an edge of the graph. It also serves
     187      /// as a base class of the edge iterators,
     188      /// thus they will convert to this type.
    177189      class Edge {
    178190      public:
    179191        /// Default constructor
    180192
    181         /// @warning The default constructor sets the iterator
    182         /// to an undefined value.
     193        /// Default constructor.
     194        /// \warning It sets the object to an undefined value.
    183195        Edge() { }
    184196        /// Copy constructor.
    … …  
    187199        ///
    188200        Edge(const Edge&) { }
    189         /// Initialize the iterator to be invalid.
    190 
    191         /// Initialize the iterator to be invalid.
    192         ///
     201        /// %Invalid constructor \& conversion.
     202
     203        /// Initializes the object to be invalid.
     204        /// \sa Invalid for more details.
    193205        Edge(Invalid) { }
    194206        /// Equality operator
    195207
     208        /// Equality operator.
     209        ///
    196210        /// Two iterators are equal if and only if they point to the
    197         /// same object or both are invalid.
     211        /// same object or both are \c INVALID.
    198212        bool operator==(Edge) const { return true; }
    199213        /// Inequality operator
    200214
    201         /// \sa operator==(Edge n)
    202         ///
     215        /// Inequality operator.
    203216        bool operator!=(Edge) const { return true; }
    204217
    205218        /// Artificial ordering operator.
    206219
    207         /// To allow the use of graph descriptors as key type in std::map or
    208         /// similar associative container we require this.
    209         ///
    210         /// \note This operator only have to define some strict ordering of
    211         /// the items; this order has nothing to do with the iteration
    212         /// ordering of the items.
     220        /// Artificial ordering operator.
     221        ///
     222        /// \note This operator only has to define some strict ordering of
     223        /// the edges; this order has nothing to do with the iteration
     224        /// ordering of the edges.
    213225        bool operator<(Edge) const { return false; }
    214226      };
    215227
    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:
     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:
    221233      ///\code
    222234      /// int count=0;
    … …  
    227239        /// Default constructor
    228240
    229         /// @warning The default constructor sets the iterator
    230         /// to an undefined value.
     241        /// Default constructor.
     242        /// \warning It sets the iterator to an undefined value.
    231243        EdgeIt() { }
    232244        /// Copy constructor.
    … …  
    235247        ///
    236248        EdgeIt(const EdgeIt& e) : Edge(e) { }
    237         /// Initialize the iterator to be invalid.
    238 
    239         /// Initialize the iterator to be invalid.
    240         ///
     249        /// %Invalid constructor \& conversion.
     250
     251        /// Initializes the iterator to be invalid.
     252        /// \sa Invalid for more details.
    241253        EdgeIt(Invalid) { }
    242         /// This constructor sets the iterator to the first edge.
    243 
    244         /// This constructor sets the iterator to the first edge.
    245         EdgeIt(const Graph&) { }
    246         /// Edge -> EdgeIt conversion
    247 
    248         /// Sets the iterator to the value of the trivial iterator.
    249         /// This feature necessitates that each time we
    250         /// iterate the edge-set, the iteration order is the
    251         /// same.
     254        /// Sets the iterator to the first edge.
     255
     256        /// Sets the iterator to the first edge of the given graph.
     257        ///
     258        explicit EdgeIt(const Graph&) { }
     259        /// Sets the iterator to the given edge.
     260
     261        /// Sets the iterator to the given edge of the given graph.
     262        ///
    252263        EdgeIt(const Graph&, const Edge&) { }
    253264        /// Next edge
    254265
    255266        /// Assign the iterator to the next edge.
     267        ///
    256268        EdgeIt& operator++() { return *this; }
    257269      };
    258270
    259       /// \brief This iterator goes trough the incident undirected
    260       /// arcs of a node.
    261       ///
    262       /// This iterator goes trough the incident edges
    263       /// of a certain node of a graph. You should assume that the
    264       /// loop arcs will be iterated twice.
    265       ///
    266       /// Its usage is quite simple, for example you can compute the
    267       /// degree (i.e. count the number of incident arcs of a node \c n
    268       /// in graph \c g of type \c Graph as follows.
     271      /// Iterator class for the incident edges of a node.
     272
     273      /// This iterator goes trough the incident undirected edges
     274      /// of a certain node of a graph.
     275      /// Its usage is quite simple, for example, you can compute the
     276      /// degree (i.e. the number of incident edges) of a node \c n
     277      /// in a graph \c g of type \c %Graph as follows.
    269278      ///
    270279      ///\code
    … …  
    272281      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    273282      ///\endcode
     283      ///
     284      /// \warning Loop edges will be iterated twice.
    274285      class IncEdgeIt : public Edge {
    275286      public:
    276287        /// Default constructor
    277288
    278         /// @warning The default constructor sets the iterator
    279         /// to an undefined value.
     289        /// Default constructor.
     290        /// \warning It sets the iterator to an undefined value.
    280291        IncEdgeIt() { }
    281292        /// Copy constructor.
    … …  
    284295        ///
    285296        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
    286         /// Initialize the iterator to be invalid.
    287 
    288         /// Initialize the iterator to be invalid.
    289         ///
     297        /// %Invalid constructor \& conversion.
     298
     299        /// Initializes the iterator to be invalid.
     300        /// \sa Invalid for more details.
    290301        IncEdgeIt(Invalid) { }
    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.
     302        /// Sets the iterator to the first incident edge.
     303
     304        /// Sets the iterator to the first incident edge of the given node.
     305        ///
    295306        IncEdgeIt(const Graph&, const Node&) { }
    296         /// Edge -> IncEdgeIt conversion
    297 
    298         /// Sets the iterator to the value of the trivial iterator \c e.
    299         /// This feature necessitates that each time we
    300         /// iterate the arc-set, the iteration order is the same.
     307        /// Sets the iterator to the given edge.
     308
     309        /// Sets the iterator to the given edge of the given graph.
     310        ///
    301311        IncEdgeIt(const Graph&, const Edge&) { }
    302         /// Next incident arc
    303 
    304         /// Assign the iterator to the next incident arc
     312        /// Next incident edge
     313
     314        /// Assign the iterator to the next incident edge
    305315        /// of the corresponding node.
    306316        IncEdgeIt& operator++() { return *this; }
    307317      };
    308318
    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.
     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.
    314324      class Arc {
    315325      public:
    316326        /// Default constructor
    317327
    318         /// @warning The default constructor sets the iterator
    319         /// to an undefined value.
     328        /// Default constructor.
     329        /// \warning It sets the object to an undefined value.
    320330        Arc() { }
    321331        /// Copy constructor.
    … …  
    324334        ///
    325335        Arc(const Arc&) { }
    326         /// Initialize the iterator to be invalid.
    327 
    328         /// Initialize the iterator to be invalid.
    329         ///
     336        /// %Invalid constructor \& conversion.
     337
     338        /// Initializes the object to be invalid.
     339        /// \sa Invalid for more details.
    330340        Arc(Invalid) { }
    331341        /// Equality operator
    332342
     343        /// Equality operator.
     344        ///
    333345        /// Two iterators are equal if and only if they point to the
    334         /// same object or both are invalid.
     346        /// same object or both are \c INVALID.
    335347        bool operator==(Arc) const { return true; }
    336348        /// Inequality operator
    337349
    338         /// \sa operator==(Arc n)
    339         ///
     350        /// Inequality operator.
    340351        bool operator!=(Arc) const { return true; }
    341352
    342353        /// Artificial ordering operator.
    343354
    344         /// To allow the use of graph descriptors as key type in std::map or
    345         /// similar associative container we require this.
    346         ///
    347         /// \note This operator only have to define some strict ordering of
    348         /// the items; this order has nothing to do with the iteration
    349         /// ordering of the items.
     355        /// Artificial ordering operator.
     356        ///
     357        /// \note This operator only has to define some strict ordering of
     358        /// the arcs; this order has nothing to do with the iteration
     359        /// ordering of the arcs.
    350360        bool operator<(Arc) const { return false; }
    351361
    352         /// Converison to Edge
     362        /// Converison to \c Edge
     363
     364        /// Converison to \c Edge.
     365        ///
    353366        operator Edge() const { return Edge(); }
    354367      };
    355       /// This iterator goes through each directed arc.
    356 
    357       /// This iterator goes through each arc of a graph.
    358       /// Its usage is quite simple, for example you can count the number
    359       /// of arcs in a graph \c g of type \c Graph as follows:
     368
     369      /// Iterator class for the arcs.
     370
     371      /// This iterator goes through each directed arc of the graph.
     372      /// Its usage is quite simple, for example, you can count the number
     373      /// of arcs in a graph \c g of type \c %Graph as follows:
    360374      ///\code
    361375      /// int count=0;
    362       /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
     376      /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
    363377      ///\endcode
    364378      class ArcIt : public Arc {
    … …  
    366380        /// Default constructor
    367381
    368         /// @warning The default constructor sets the iterator
    369         /// to an undefined value.
     382        /// Default constructor.
     383        /// \warning It sets the iterator to an undefined value.
    370384        ArcIt() { }
    371385        /// Copy constructor.
    … …  
    374388        ///
    375389        ArcIt(const ArcIt& e) : Arc(e) { }
    376         /// Initialize the iterator to be invalid.
    377 
    378         /// Initialize the iterator to be invalid.
    379         ///
     390        /// %Invalid constructor \& conversion.
     391
     392        /// Initializes the iterator to be invalid.
     393        /// \sa Invalid for more details.
    380394        ArcIt(Invalid) { }
    381         /// This constructor sets the iterator to the first arc.
    382 
    383         /// This constructor sets the iterator to the first arc of \c g.
    384         ///@param g the graph
    385         ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
    386         /// Arc -> ArcIt conversion
    387 
    388         /// Sets the iterator to the value of the trivial iterator \c e.
    389         /// This feature necessitates that each time we
    390         /// iterate the arc-set, the iteration order is the same.
     395        /// Sets the iterator to the first arc.
     396
     397        /// Sets the iterator to the first arc of the given graph.
     398        ///
     399        explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
     400        /// Sets the iterator to the given arc.
     401
     402        /// Sets the iterator to the given arc of the given graph.
     403        ///
    391404        ArcIt(const Graph&, const Arc&) { }
    392         ///Next arc
     405        /// Next arc
    393406
    394407        /// Assign the iterator to the next arc.
     408        ///
    395409        ArcIt& operator++() { return *this; }
    396410      };
    397411
    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
     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
    403417      /// of outgoing arcs of a node \c n
    404       /// in graph \c g of type \c Graph as follows.
     418      /// in a graph \c g of type \c %Graph as follows.
    405419      ///\code
    406420      /// int count=0;
    407       /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
     421      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
    408422      ///\endcode
    409 
    410423      class OutArcIt : public Arc {
    411424      public:
    412425        /// Default constructor
    413426
    414         /// @warning The default constructor sets the iterator
    415         /// to an undefined value.
     427        /// Default constructor.
     428        /// \warning It sets the iterator to an undefined value.
    416429        OutArcIt() { }
    417430        /// Copy constructor.
    … …  
    420433        ///
    421434        OutArcIt(const OutArcIt& e) : Arc(e) { }
    422         /// Initialize the iterator to be invalid.
    423 
    424         /// Initialize the iterator to be invalid.
    425         ///
     435        /// %Invalid constructor \& conversion.
     436
     437        /// Initializes the iterator to be invalid.
     438        /// \sa Invalid for more details.
    426439        OutArcIt(Invalid) { }
    427         /// This constructor sets the iterator to the first outgoing arc.
    428 
    429         /// This constructor sets the iterator to the first outgoing arc of
    430         /// the node.
    431         ///@param n the node
    432         ///@param g the graph
     440        /// Sets the iterator to the first outgoing arc.
     441
     442        /// Sets the iterator to the first outgoing arc of the given node.
     443        ///
    433444        OutArcIt(const Graph& n, const Node& g) {
    434445          ignore_unused_variable_warning(n);
    435446          ignore_unused_variable_warning(g);
    436447        }
    437         /// Arc -> OutArcIt conversion
    438 
    439         /// Sets the iterator to the value of the trivial iterator.
    440         /// This feature necessitates that each time we
    441         /// iterate the arc-set, the iteration order is the same.
     448        /// Sets the iterator to the given arc.
     449
     450        /// Sets the iterator to the given arc of the given graph.
     451        ///
    442452        OutArcIt(const Graph&, const Arc&) { }
    443         ///Next outgoing arc
     453        /// Next outgoing arc
    444454
    445455        /// Assign the iterator to the next
    … …  
    448458      };
    449459
    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.
     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.
    457467      ///\code
    458468      /// int count=0;
    459       /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
     469      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
    460470      ///\endcode
    461 
    462471      class InArcIt : public Arc {
    463472      public:
    464473        /// Default constructor
    465474
    466         /// @warning The default constructor sets the iterator
    467         /// to an undefined value.
     475        /// Default constructor.
     476        /// \warning It sets the iterator to an undefined value.
    468477        InArcIt() { }
    469478        /// Copy constructor.
    … …  
    472481        ///
    473482        InArcIt(const InArcIt& e) : Arc(e) { }
    474         /// Initialize the iterator to be invalid.
    475 
    476         /// Initialize the iterator to be invalid.
    477         ///
     483        /// %Invalid constructor \& conversion.
     484
     485        /// Initializes the iterator to be invalid.
     486        /// \sa Invalid for more details.
    478487        InArcIt(Invalid) { }
    479         /// This constructor sets the iterator to first incoming arc.
    480 
    481         /// This constructor set the iterator to the first incoming arc of
    482         /// the node.
    483         ///@param n the node
    484         ///@param g the graph
     488        /// Sets the iterator to the first incoming arc.
     489
     490        /// Sets the iterator to the first incoming arc of the given node.
     491        ///
    485492        InArcIt(const Graph& g, const Node& n) {
    486493          ignore_unused_variable_warning(n);
    487494          ignore_unused_variable_warning(g);
    488495        }
    489         /// Arc -> InArcIt conversion
    490 
    491         /// Sets the iterator to the value of the trivial iterator \c e.
    492         /// This feature necessitates that each time we
    493         /// iterate the arc-set, the iteration order is the same.
     496        /// Sets the iterator to the given arc.
     497
     498        /// Sets the iterator to the given arc of the given graph.
     499        ///
    494500        InArcIt(const Graph&, const Arc&) { }
    495501        /// Next incoming arc
    496502
    497         /// Assign the iterator to the next inarc of the corresponding node.
    498         ///
     503        /// Assign the iterator to the next
     504        /// incoming arc of the corresponding node.
    499505        InArcIt& operator++() { return *this; }
    500506      };
    501507
    502       /// \brief Reference map of the nodes to type \c T.
    503       ///
    504       /// Reference map of the nodes to type \c T.
     508      /// \brief Standard graph map type for the nodes.
     509      ///
     510      /// Standard graph map type for the nodes.
     511      /// It conforms to the ReferenceMap concept.
    505512      template<class T>
    506513      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
    … …  
    508515      public:
    509516
    510         ///\e
    511         NodeMap(const Graph&) { }
    512         ///\e
     517        /// Constructor
     518        explicit NodeMap(const Graph&) { }
     519        /// Constructor with given initial value
    513520        NodeMap(const Graph&, T) { }
    514521
    … …  
    525532      };
    526533
    527       /// \brief Reference map of the arcs to type \c T.
    528       ///
    529       /// Reference map of the arcs to type \c T.
     534      /// \brief Standard graph map type for the arcs.
     535      ///
     536      /// Standard graph map type for the arcs.
     537      /// It conforms to the ReferenceMap concept.
    530538      template<class T>
    531539      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
    … …  
    533541      public:
    534542
    535         ///\e
    536         ArcMap(const Graph&) { }
    537         ///\e
     543        /// Constructor
     544        explicit ArcMap(const Graph&) { }
     545        /// Constructor with given initial value
    538546        ArcMap(const Graph&, T) { }
     547
    539548      private:
    540549        ///Copy constructor
    … …  
    549558      };
    550559
    551       /// Reference map of the edges to type \c T.
    552 
    553       /// Reference map of the edges to type \c T.
     560      /// \brief Standard graph map type for the edges.
     561      ///
     562      /// Standard graph map type for the edges.
     563      /// It conforms to the ReferenceMap concept.
    554564      template<class T>
    555565      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
    … …  
    557567      public:
    558568
    559         ///\e
    560         EdgeMap(const Graph&) { }
    561         ///\e
     569        /// Constructor
     570        explicit EdgeMap(const Graph&) { }
     571        /// Constructor with given initial value
    562572        EdgeMap(const Graph&, T) { }
     573
    563574      private:
    564575        ///Copy constructor
    … …  
    573584      };
    574585
    575       /// \brief Direct the given edge.
    576       ///
    577       /// Direct the given edge. The returned arc source
    578       /// will be the given node.
    579       Arc direct(const Edge&, const Node&) const {
    580         return INVALID;
    581       }
    582 
    583       /// \brief Direct the given edge.
    584       ///
    585       /// Direct the given edge. The returned arc
    586       /// represents the given edge and the direction comes
    587       /// from the bool parameter. The source of the edge and
    588       /// the directed arc is the same when the given bool is true.
    589       Arc direct(const Edge&, bool) const {
    590         return INVALID;
    591       }
    592 
    593       /// \brief Returns true if the arc has default orientation.
    594       ///
    595       /// Returns whether the given directed arc is same orientation as
    596       /// the corresponding edge's default orientation.
    597       bool direction(Arc) const { return true; }
    598 
    599       /// \brief Returns the opposite directed arc.
    600       ///
    601       /// Returns the opposite directed arc.
    602       Arc oppositeArc(Arc) const { return INVALID; }
    603 
    604       /// \brief Opposite node on an arc
    605       ///
    606       /// \return The opposite of the given node on the given edge.
    607       Node oppositeNode(Node, Edge) const { return INVALID; }
    608 
    609       /// \brief First node of the edge.
    610       ///
    611       /// \return The first node of the given edge.
    612       ///
    613       /// Naturally edges don't have direction and thus
    614       /// don't have source and target node. However we use \c u() and \c v()
    615       /// methods to query the two nodes of the arc. The direction of the
    616       /// arc which arises this way is called the inherent direction of the
    617       /// edge, and is used to define the "default" direction
    618       /// of the directed versions of the arcs.
     586      /// \brief The first node of the edge.
     587      ///
     588      /// Returns the first node of the given edge.
     589      ///
     590      /// Edges don't have source and target nodes, however, methods
     591      /// u() and v() are used to query the two end-nodes of an edge.
     592      /// The orientation of an edge that arises this way is called
     593      /// the inherent direction, it is used to define the default
     594      /// direction for the corresponding arcs.
    619595      /// \sa v()
    620596      /// \sa direction()
    621597      Node u(Edge) const { return INVALID; }
    622598
    623       /// \brief Second node of the edge.
    624       ///
    625       /// \return The second node of the given edge.
    626       ///
    627       /// Naturally edges don't have direction and thus
    628       /// don't have source and target node. However we use \c u() and \c v()
    629       /// methods to query the two nodes of the arc. The direction of the
    630       /// arc which arises this way is called the inherent direction of the
    631       /// edge, and is used to define the "default" direction
    632       /// of the directed versions of the arcs.
     599      /// \brief The second node of the edge.
     600      ///
     601      /// Returns the second node of the given edge.
     602      ///
     603      /// Edges don't have source and target nodes, however, methods
     604      /// u() and v() are used to query the two end-nodes of an edge.
     605      /// The orientation of an edge that arises this way is called
     606      /// the inherent direction, it is used to define the default
     607      /// direction for the corresponding arcs.
    633608      /// \sa u()
    634609      /// \sa direction()
    635610      Node v(Edge) const { return INVALID; }
    636611
    637       /// \brief Source node of the directed arc.
     612      /// \brief The source node of the arc.
     613      ///
     614      /// Returns the source node of the given arc.
    638615      Node source(Arc) const { return INVALID; }
    639616
    640       /// \brief Target node of the directed arc.
     617      /// \brief The target node of the arc.
     618      ///
     619      /// Returns the target node of the given arc.
    641620      Node target(Arc) const { return INVALID; }
    642621
    643       /// \brief Returns the id of the node.
     622      /// \brief The ID of the node.
     623      ///
     624      /// Returns the ID of the given node.
    644625      int id(Node) const { return -1; }
    645626
    646       /// \brief Returns the id of the edge.
     627      /// \brief The ID of the edge.
     628      ///
     629      /// Returns the ID of the given edge.
    647630      int id(Edge) const { return -1; }
    648631
    649       /// \brief Returns the id of the arc.
     632      /// \brief The ID of the arc.
     633      ///
     634      /// Returns the ID of the given arc.
    650635      int id(Arc) const { return -1; }
    651636
    652       /// \brief Returns the node with the given id.
    653       ///
    654       /// \pre The argument should be a valid node id in the graph.
     637      /// \brief The node with the given ID.
     638      ///
     639      /// Returns the node with the given ID.
     640      /// \pre The argument should be a valid node ID in the graph.
    655641      Node nodeFromId(int) const { return INVALID; }
    656642
    657       /// \brief Returns the edge with the given id.
    658       ///
    659       /// \pre The argument should be a valid edge id in the graph.
     643      /// \brief The edge with the given ID.
     644      ///
     645      /// Returns the edge with the given ID.
     646      /// \pre The argument should be a valid edge ID in the graph.
    660647      Edge edgeFromId(int) const { return INVALID; }
    661648
    662       /// \brief Returns the arc with the given id.
    663       ///
    664       /// \pre The argument should be a valid arc id in the graph.
     649      /// \brief The arc with the given ID.
     650      ///
     651      /// Returns the arc with the given ID.
     652      /// \pre The argument should be a valid arc ID in the graph.
    665653      Arc arcFromId(int) const { return INVALID; }
    666654
    667       /// \brief Returns an upper bound on the node IDs.
     655      /// \brief An upper bound on the node IDs.
     656      ///
     657      /// Returns an upper bound on the node IDs.
    668658      int maxNodeId() const { return -1; }
    669659
    670       /// \brief Returns an upper bound on the edge IDs.
     660      /// \brief An upper bound on the edge IDs.
     661      ///
     662      /// Returns an upper bound on the edge IDs.
    671663      int maxEdgeId() const { return -1; }
    672664
    673       /// \brief Returns an upper bound on the arc IDs.
     665      /// \brief An upper bound on the arc IDs.
     666      ///
     667      /// Returns an upper bound on the arc IDs.
    674668      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; }
    675703
    676704      void first(Node&) const {}
    … …  
    706734      int maxId(Arc) const { return -1; }
    707735
    708       /// \brief Base node of the iterator
    709       ///
    710       /// Returns the base node (the source in this case) of the iterator
    711       Node baseNode(OutArcIt e) const {
    712         return source(e);
    713       }
    714       /// \brief Running node of the iterator
    715       ///
    716       /// Returns the running node (the target in this case) of the
    717       /// iterator
    718       Node runningNode(OutArcIt e) const {
    719         return target(e);
    720       }
    721 
    722       /// \brief Base node of the iterator
    723       ///
    724       /// Returns the base node (the target in this case) of the iterator
    725       Node baseNode(InArcIt e) const {
    726         return target(e);
    727       }
    728       /// \brief Running node of the iterator
    729       ///
    730       /// Returns the running node (the source in this case) of the
    731       /// iterator
    732       Node runningNode(InArcIt e) const {
    733         return source(e);
    734       }
    735 
    736       /// \brief Base node of the iterator
    737       ///
    738       /// Returns the base node of the iterator
    739       Node baseNode(IncEdgeIt) const {
    740         return INVALID;
    741       }
    742 
    743       /// \brief Running node of the iterator
    744       ///
    745       /// Returns the running node of the iterator
    746       Node runningNode(IncEdgeIt) const {
    747         return INVALID;
    748       }
     736      /// \brief The base node of the iterator.
     737      ///
     738      /// Returns the base node of the given incident edge iterator.
     739      Node baseNode(IncEdgeIt) const { return INVALID; }
     740
     741      /// \brief The running node of the iterator.
     742      ///
     743      /// Returns the running node of the given incident edge iterator.
     744      Node runningNode(IncEdgeIt) const { return INVALID; }
     745
     746      /// \brief The base node of the iterator.
     747      ///
     748      /// Returns the base node of the given outgoing arc iterator
     749      /// (i.e. the source node of the corresponding arc).
     750      Node baseNode(OutArcIt) const { return INVALID; }
     751
     752      /// \brief The running node of the iterator.
     753      ///
     754      /// Returns the running node of the given outgoing arc iterator
     755      /// (i.e. the target node of the corresponding arc).
     756      Node runningNode(OutArcIt) const { return INVALID; }
     757
     758      /// \brief The base node of the iterator.
     759      ///
     760      /// Returns the base node of the given incomming arc iterator
     761      /// (i.e. the target node of the corresponding arc).
     762      Node baseNode(InArcIt) const { return INVALID; }
     763
     764      /// \brief The running node of the iterator.
     765      ///
     766      /// Returns the running node of the given incomming arc iterator
     767      /// (i.e. the source node of the corresponding arc).
     768      Node runningNode(InArcIt) const { return INVALID; }
    749769
    750770      template <typename _Graph>

  • lemon/concepts/graph_components.h

    r713 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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 graph components.
     21///\brief The concepts 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 have to define some strict ordering of
     95      /// \note This operator only has 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.