# Changes in /[932:2eebc8f7dca5:933:140facbd1d7c] in lemon-1.2

Ignore:
Files:
112 edited

Unmodified
Removed
• ## .hgignore

 r563 lemon/stamp-h2 doc/Doxyfile doc/references.dox cmake/version.cmake .dirstamp
• ## AUTHORS

 r320 Again, please visit the history of the old LEMON repository for more details: http://lemon.cs.elte.hu/svn/lemon/trunk details: http://lemon.cs.elte.hu/hg/lemon-0.x

 r904 ELSE() IF(CMAKE_COMPILER_IS_GNUCXX) SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas") SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas") SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb") SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb") SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG}) INCLUDE(FindPythonInterp) ENABLE_TESTING() • ## INSTALL  r568 Disable COIN-OR support. Makefile Variables ================== Some Makefile variables are reserved by the GNU Coding Standards for the use of the "user" - the person building the package. For instance, CXX and CXXFLAGS are such variables, and have the same meaning as explained in the previous section. These variables can be set on the command line when invoking make' like this: make [VARIABLE=VALUE]...' WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us to hold several compiler flags related to warnings. Its default value can be overridden when invoking make'. For example to disable all warning flags use make WARNINGCXXFLAGS='. In order to turn off a single flag from the default set of warning flags, you can use the CXXFLAGS variable, since this is passed after WARNINGCXXFLAGS. For example to turn off -Wold-style-cast' (which is used by default when g++ is detected) you can use make CXXFLAGS="-g -O2 -Wno-old-style-cast"'. • ## LICENSE  r553 copyright/license. Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport (Egervary Combinatorial Optimization Research Group, EGRES). • ## Makefile.am  r752 include doc/Makefile.am include tools/Makefile.am include scripts/Makefile.am DIST_SUBDIRS = demo • ## NEWS  r665 2011-08-08 Version 1.2.2 released Bugfix release. #392: Bug fix in Dfs::start(s,t) #414: Fix wrong initialization in Preflow #404: Update Doxygen configuration #416: Support tests with valgrind #418: Better Win CodeBlock/MinGW support #419: Backport build environment improvements from the main branch - Build of mip_test and lp_test precede the running of the tests - Also search for coin libs under${COIN_ROOT_DIR}/lib/coin - Do not look for COIN_VOL libraries #382: Allow lgf file without Arc maps #417: Bug fix in CostScaling 2010-10-21 Version 1.2.1 released Bugfix release. #366: Fix Pred[Matrix]MapPath::empty() #371: Bug fix in (di)graphCopy() The target graph is cleared before adding nodes and arcs/edges. #364: Add missing UndirectedTags #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex #372: Fix a critical bug in preflow 2010-03-19 Version 1.2 released This is major feature release * New algorithms * Bellman-Ford algorithm (#51) * Minimum mean cycle algorithms (#179) * Karp, Hartman-Orlin and Howard algorithms * New minimum cost flow algorithms (#180) * Cost Scaling algorithms * Capacity Scaling algorithm * Cycle-Canceling algorithms * Planarity related algorithms (#62) * Planarity checking algorithm * Planar embedding algorithm * Schnyder's planar drawing algorithm * Coloring planar graphs with five or six colors * Fractional matching algorithms (#314) * New data structures * StaticDigraph structure (#68) * Several new priority queue structures (#50, #301) * Fibonacci, Radix, Bucket, Pairing, Binomial D-ary and fourary heaps (#301) * Iterable map structures (#73) * Other new tools and functionality * Map utility functions (#320) * Reserve functions are added to ListGraph and SmartGraph (#311) * A resize() function is added to HypercubeGraph (#311) * A count() function is added to CrossRefMap (#302) * Support for multiple targets in Suurballe using fullInit() (#181) * Traits class and named parameters for Suurballe (#323) * Separate reset() and resetParams() functions in NetworkSimplex to handle graph changes (#327) * tolerance() functions are added to HaoOrlin (#306) * Implementation improvements * Improvements in weighted matching algorithms (#314) * Jumpstart initialization * ArcIt iteration is based on out-arc lists instead of in-arc lists in ListDigraph (#311) * Faster add row operation in CbcMip (#203) * Better implementation for split() in ListDigraph (#311) * ArgParser can also throw exception instead of exit(1) (#332) * Miscellaneous * A simple interactive bootstrap script * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315, #316,#319) * BibTeX references in the doc (#184) * Optionally use valgrind when running tests * Also check ReferenceMapTag in concept checks (#312) * dimacs-solver uses long long type by default. * Several bugfixes (compared to release 1.1): #295: Suppress MSVC warnings using pragmas ----: Various CMAKE related improvements * Remove duplications from doc/CMakeLists.txt * Rename documentation install folder from 'docs' to 'html' * Add tools/CMakeLists.txt to the tarball * Generate and install LEMONConfig.cmake * Change the label of the html project in Visual Studio * Fix the check for the 'long long' type * Put the version string into config.h * Minor CMake improvements * Set the version to 'hg-tip' if everything fails #311: Add missing 'explicit' keywords #302: Fix the implementation and doc of CrossRefMap #308: Remove duplicate list_graph.h entry from source list #307: Bugfix in Preflow and Circulation #305: Bugfix and extension in the rename script #312: Also check ReferenceMapTag in concept checks #250: Bugfix in pathSource() and pathTarget() #321: Use pathCopy(from,to) instead of copyPath(to,from) #322: Distribure LEMONConfig.cmake.in #330: Bug fix in map_extender.h #336: Fix the date field comment of graphToEps() output #323: Bug fix in Suurballe #335: Fix clear() function in ExtendFindEnum #337: Use void* as the LPX object pointer #317: Fix (and improve) error message in mip_test.cc Remove unnecessary OsiCbc dependency #356: Allow multiple executions of weighted matching algorithms (#356) 2009-05-13 Version 1.1 released ----: Add missing unistd.h include to time_measure.h #204: Compilation bug fixed in graph_to_eps.h with VS2005 #214,#215: windows.h should never be included by lemon headers #214,#215: windows.h should never be included by LEMON headers #230: Build systems check the availability of 'long long' type #229: Default implementation of Tolerance<> is used for integer types 2008-10-13 Version 1.0 released This is the first stable release of LEMON. Compared to the 0.x release series, it features a considerably smaller but more matured set of tools. The API has also completely revised and changed in several places. * The major name changes compared to the 0.x series (see the This is the first stable release of LEMON. Compared to the 0.x release series, it features a considerably smaller but more matured set of tools. The API has also completely revised and changed in several places. * The major name changes compared to the 0.x series (see the Migration Guide in the doc for more details) * Graph -> Digraph, UGraph -> Graph * Edge -> Arc, UEdge -> Edge * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge) * Other improvements * Better documentation * Reviewed and cleaned up codebase * CMake based build system (along with the autotools based one) * Contents of the library (ported from 0.x) * Algorithms * breadth-first search (bfs.h) * depth-first search (dfs.h) * Dijkstra's algorithm (dijkstra.h) * Kruskal's algorithm (kruskal.h) * Data structures * graph data structures (list_graph.h, smart_graph.h) * path data structures (path.h) * binary heap data structure (bin_heap.h) * union-find data structures (unionfind.h) * miscellaneous property maps (maps.h) * two dimensional vector and bounding box (dim2.h) * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge) * Other improvements * Better documentation * Reviewed and cleaned up codebase * CMake based build system (along with the autotools based one) * Contents of the library (ported from 0.x) * Algorithms * breadth-first search (bfs.h) * depth-first search (dfs.h) * Dijkstra's algorithm (dijkstra.h) * Kruskal's algorithm (kruskal.h) * Data structures * graph data structures (list_graph.h, smart_graph.h) * path data structures (path.h) * binary heap data structure (bin_heap.h) * union-find data structures (unionfind.h) * miscellaneous property maps (maps.h) * two dimensional vector and bounding box (dim2.h) * Concepts * graph structure concepts (concepts/digraph.h, concepts/graph.h, * graph structure concepts (concepts/digraph.h, concepts/graph.h, concepts/graph_components.h) * concepts for other structures (concepts/heap.h, concepts/maps.h, concepts/path.h) * Tools * Mersenne twister random number generator (random.h) * tools for measuring cpu and wall clock time (time_measure.h) * tools for counting steps and events (counter.h) * tool for parsing command line arguments (arg_parser.h) * tool for visualizing graphs (graph_to_eps.h) * tools for reading and writing data in LEMON Graph Format * concepts for other structures (concepts/heap.h, concepts/maps.h, concepts/path.h) * Tools * Mersenne twister random number generator (random.h) * tools for measuring cpu and wall clock time (time_measure.h) * tools for counting steps and events (counter.h) * tool for parsing command line arguments (arg_parser.h) * tool for visualizing graphs (graph_to_eps.h) * tools for reading and writing data in LEMON Graph Format (lgf_reader.h, lgf_writer.h) * tools to handle the anomalies of calculations with floating point numbers (tolerance.h) floating point numbers (tolerance.h) * tools to manage RGB colors (color.h) * Infrastructure * extended assertion handling (assert.h) * exception classes and error handling (error.h) * concept checking (concept_check.h) * commonly used mathematical constants (math.h) * Infrastructure * extended assertion handling (assert.h) * exception classes and error handling (error.h) * concept checking (concept_check.h) * commonly used mathematical constants (math.h)

 r658 Copying, distribution and modification conditions and terms. NEWS News and version history. INSTALL Some example programs to make you easier to get familiar with LEMON. scripts/ Scripts that make it easier to develop LEMON. test/
• ## configure.ac

 r907 AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no]) AC_CHECK_PROG([python_found],[python],[yes],[no]) AC_CHECK_PROG([gs_found],[gs],[yes],[no]) fi AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"]) dnl Support for running test cases using valgrind. use_valgrind=no AC_ARG_ENABLE([valgrind], AS_HELP_STRING([--enable-valgrind], [use valgrind when running tests]), [use_valgrind=yes]) if [[ "$use_valgrind" = "yes" ]]; then AC_CHECK_PROG(HAVE_VALGRIND, valgrind, yes, no) if [[ "$HAVE_VALGRIND" = "no" ]]; then AC_MSG_ERROR([Valgrind not found in PATH.]) fi fi AM_CONDITIONAL(USE_VALGRIND, [test "$use_valgrind" = "yes"]) dnl Checks for header files. echo echo Build additional tools........ : $enable_tools echo Use valgrind for tests........ :$use_valgrind echo echo The packace will be installed in
• ## demo/arg_parser_demo.cc

 r440 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). .other("..."); // Throw an exception when problems occurs. The default behavior is to // exit(1) on these cases, but this makes Valgrind falsely warn // about memory leaks. ap.throwOnProblems(); // Perform the parsing process // (in case of any error it terminates the program) ap.parse(); // The try {} construct is necessary only if the ap.trowOnProblems() // setting is in use. try { ap.parse(); } catch (ArgParserException &) { return 1; } // Check each option if it has been given and print its value
• ## doc/CMakeLists.txt

 r907 ) IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE) IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE) FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/) SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha) COMMAND${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE}${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps COMMAND${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE}${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps COMMAND${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE}${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps COMMAND${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE}${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps COMMAND${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps COMMAND ${CMAKE_COMMAND} -E remove_directory html COMMAND${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile WORKING_DIRECTORY${CMAKE_CURRENT_BINARY_DIR}
• ## doc/Doxyfile.in

 r907 "@abs_top_srcdir@/tools" \ "@abs_top_srcdir@/test/test_tools.h" \ "@abs_top_builddir@/doc/mainpage.dox" "@abs_top_builddir@/doc/mainpage.dox" \ "@abs_top_builddir@/doc/references.dox" INPUT_ENCODING         = UTF-8 FILE_PATTERNS          = *.h \
• ## doc/Makefile.am

 r673 connected_components.eps \ edge_biconnected_components.eps \ matching.eps \ node_biconnected_components.eps \ planar.eps \ strongly_connected_components.eps fi html-local: $(DOC_PNG_IMAGES) references.dox: doc/references.bib if test${python_found} = yes; then \ cd doc; \ python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \ cd ..; \ else \ echo; \ echo "Python not found."; \ echo; \ exit 1; \ fi html-local: $(DOC_PNG_IMAGES) references.dox if test${doxygen_found} = yes; then \ cd doc; \
• ## doc/groups.dox

 r663 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /** @defgroup matrices Matrices @ingroup datas \brief Two dimensional data storages implemented in LEMON. This group contains two dimensional data storages implemented in LEMON. */ /** @defgroup paths Path Structures @ingroup datas any kind of path structure. \sa lemon::concepts::Path \sa \ref concepts::Path "Path concept" */ /** @defgroup heaps Heap Structures @ingroup datas \brief %Heap structures implemented in LEMON. This group contains the heap structures implemented in LEMON. LEMON provides several heap classes. They are efficient implementations of the abstract data type \e priority \e queue. They store items with specified values called \e priorities in such a way that finding and removing the item with minimum priority are efficient. The basic operations are adding and erasing items, changing the priority of an item, etc. Heaps are crucial in several algorithms, such as Dijkstra and Prim. The heap implementations have the same interface, thus any of them can be used easily in such algorithms. \sa \ref concepts::Heap "Heap concept" */ /** @defgroup geomdat Geometric Data Structures @ingroup auxdat \brief Geometric data structures implemented in LEMON. This group contains geometric data structures implemented in LEMON. - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional vector with the usual operations. - \ref lemon::dim2::Box "dim2::Box" can be used to determine the rectangular bounding box of a set of \ref lemon::dim2::Point "dim2::Point"'s. */ /** @defgroup algs Algorithms \brief This group contains the several algorithms This group contains the common graph search algorithms, namely \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) \ref clrs01algorithms. */ \brief Algorithms for finding shortest paths. This group contains the algorithms for finding shortest paths in digraphs. This group contains the algorithms for finding shortest paths in digraphs \ref clrs01algorithms. - \ref Dijkstra algorithm for finding shortest paths from a source node but the digraph should not contain directed cycles with negative total length. - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms for solving the \e all-pairs \e shortest \e paths \e problem when arc lenghts can be either positive or negative, but the digraph should not contain directed cycles with negative total length. - \ref Suurballe A successive shortest path algorithm for finding arc-disjoint paths between two nodes having minimum total length. /** @defgroup spantree Minimum Spanning Tree Algorithms @ingroup algs \brief Algorithms for finding minimum cost spanning trees and arborescences. This group contains the algorithms for finding minimum cost spanning trees and arborescences \ref clrs01algorithms. */ /** @defgroup max_flow Maximum Flow Algorithms @ingroup algs This group contains the algorithms for finding maximum flows and feasible circulations. feasible circulations \ref clrs01algorithms, \ref amo93networkflows. The \e maximum \e flow \e problem is to find a flow of maximum value between \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] LEMON contains several algorithms for solving maximum flow problems: - \ref EdmondsKarp Edmonds-Karp algorithm. - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. In most cases the \ref Preflow "Preflow" algorithm provides the fastest method for computing a maximum flow. All implementations also provide functions to query the minimum cut, which is the dual problem of maximum flow. \ref Circulation is a preflow push-relabel algorithm implemented directly \ref Preflow is an efficient implementation of Goldberg-Tarjan's preflow push-relabel algorithm \ref goldberg88newapproach for finding maximum flows. It also provides functions to query the minimum cut, which is the dual problem of maximum flow. \ref Circulation is a preflow push-relabel algorithm implemented directly for finding feasible circulations, which is a somewhat different problem, but it is strongly related to maximum flow. This group contains the algorithms for finding minimum cost flows and circulations. For more information about this problem and its dual solution see \ref min_cost_flow "Minimum Cost Flow Problem". circulations \ref amo93networkflows. For more information about this problem and its dual solution, see \ref min_cost_flow "Minimum Cost Flow Problem". LEMON contains several algorithms for this problem. - \ref NetworkSimplex Primal Network Simplex algorithm with various pivot strategies. - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on cost scaling. - \ref CapacityScaling Successive Shortest %Path algorithm with optional capacity scaling. - \ref CancelAndTighten The Cancel and Tighten algorithm. - \ref CycleCanceling Cycle-Canceling algorithms. pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. - \ref CostScaling Cost Scaling algorithm based on push/augment and relabel operations \ref goldberg90approximation, \ref goldberg97efficient, \ref bunnagel98efficient. - \ref CapacityScaling Capacity Scaling algorithm based on the successive shortest path method \ref edmondskarp72theoretical. - \ref CycleCanceling Cycle-Canceling algorithms, two of which are strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. In general NetworkSimplex is the most efficient implementation, \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f] \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f] LEMON contains several algorithms related to minimum cut problems: - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut in directed graphs. - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for calculating minimum cut in undirected graphs. - \ref GomoryHu "Gomory-Hu tree computation" for calculating all-pairs minimum cut in undirected graphs. /** @defgroup graph_properties Connectivity and Other Graph Properties @ingroup algs \brief Algorithms for discovering the graph properties This group contains the algorithms for discovering the graph properties like connectivity, bipartiteness, euler property, simplicity etc. \image html edge_biconnected_components.png \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth */ /** @defgroup planar Planarity Embedding and Drawing @ingroup algs \brief Algorithms for planarity checking, embedding and drawing This group contains the algorithms for planarity checking, embedding and drawing. \image html planar.png \image latex planar.eps "Plane graph" width=\textwidth @defgroup min_mean_cycle Minimum Mean Cycle Algorithms @ingroup algs \brief Algorithms for finding minimum mean cycles. This group contains the algorithms for finding minimum mean cycles \ref clrs01algorithms, \ref amo93networkflows. The \e minimum \e mean \e cycle \e problem is to find a directed cycle of minimum mean length (cost) in a digraph. The mean length of a cycle is the average length of its arcs, i.e. the ratio between the total length of the cycle and the number of arcs on it. This problem has an important connection to \e conservative \e length \e functions, too. A length function on the arcs of a digraph is called conservative if and only if there is no directed cycle of negative total length. For an arbitrary length function, the negative of the minimum cycle mean is the smallest \f$\epsilon\f$ value so that increasing the arc lengths uniformly by \f$\epsilon\f$ results in a conservative length function. LEMON contains three algorithms for solving the minimum mean cycle problem: - \ref KarpMmc Karp's original algorithm \ref amo93networkflows, \ref dasdan98minmeancycle. - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved version of Karp's algorithm \ref dasdan98minmeancycle. - \ref HowardMmc Howard's policy iteration algorithm \ref dasdan98minmeancycle. In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the most efficient one, though the best known theoretical bound on its running time is exponential. Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms run in time O(ne) and use space O(n2+e), but the latter one is typically faster due to the applied early termination scheme. */ The matching algorithms implemented in LEMON: - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm for calculating maximum cardinality matching in bipartite graphs. - \ref PrBipartiteMatching Push-relabel algorithm for calculating maximum cardinality matching in bipartite graphs. - \ref MaxWeightedBipartiteMatching Successive shortest path algorithm for calculating maximum weighted matching and maximum weighted bipartite matching in bipartite graphs. - \ref MinCostMaxBipartiteMatching Successive shortest path algorithm for calculating minimum cost maximum matching in bipartite graphs. - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating maximum cardinality matching in general graphs. Edmond's blossom shrinking algorithm for calculating maximum weighted perfect matching in general graphs. \image html bipartite_matching.png \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth */ /** @defgroup spantree Minimum Spanning Tree Algorithms @ingroup algs \brief Algorithms for finding minimum cost spanning trees and arborescences. This group contains the algorithms for finding minimum cost spanning trees and arborescences. - \ref MaxFractionalMatching Push-relabel algorithm for calculating maximum cardinality fractional matching in general graphs. - \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating maximum weighted fractional matching in general graphs. - \ref MaxWeightedPerfectFractionalMatching Augmenting path algorithm for calculating maximum weighted perfect fractional matching in general graphs. \image html matching.png \image latex matching.eps "Min Cost Perfect Matching" width=\textwidth */ /** @defgroup graph_properties Connectivity and Other Graph Properties @ingroup algs \brief Algorithms for discovering the graph properties This group contains the algorithms for discovering the graph properties like connectivity, bipartiteness, euler property, simplicity etc. \image html connected_components.png \image latex connected_components.eps "Connected components" width=\textwidth */ /** @defgroup planar Planarity Embedding and Drawing @ingroup algs \brief Algorithms for planarity checking, embedding and drawing This group contains the algorithms for planarity checking, embedding and drawing. \image html planar.png \image latex planar.eps "Plane graph" width=\textwidth */ This group contains some algorithms implemented in LEMON in order to make it easier to implement complex algorithms. */ /** @defgroup approx Approximation Algorithms @ingroup algs \brief Approximation algorithms. This group contains the approximation and heuristic algorithms implemented in LEMON. */ /** @defgroup lp_group Lp and Mip Solvers @defgroup lp_group LP and MIP Solvers @ingroup gen_opt_group \brief Lp and Mip solver interfaces for LEMON. This group contains Lp and Mip solver interfaces for LEMON. The various LP solvers could be used in the same manner with this interface. */ /** @defgroup lp_utils Tools for Lp and Mip Solvers @ingroup lp_group \brief Helper tools to the Lp and Mip solvers. This group adds some helper tools to general optimization framework implemented in LEMON. */ /** @defgroup metah Metaheuristics @ingroup gen_opt_group \brief Metaheuristics for LEMON library. This group contains some metaheuristic optimization tools. \brief LP and MIP solver interfaces for LEMON. This group contains LP and MIP solver interfaces for LEMON. Various LP solvers could be used in the same manner with this high-level interface. The currently supported solvers are \ref glpk, \ref clp, \ref cbc, \ref cplex, \ref soplex. */ /** @defgroup dimacs_group DIMACS format @defgroup dimacs_group DIMACS Format @ingroup io_group \brief Read and write files in DIMACS format \brief Skeleton and concept checking classes for graph structures This group contains the skeletons and concept checking classes of LEMON's graph structures and helper classes used to implement these. This group contains the skeletons and concept checking classes of graph structures. */ /** @defgroup tools Standalone Utility Applications Some utility applications are listed here. The standard compilation procedure (./configure;make) will compile them, as well. */ /** \anchor demoprograms */ /** @defgroup tools Standalone Utility Applications Some utility applications are listed here. The standard compilation procedure (./configure;make) will compile them, as well. */ }
• ## doc/lgf.dox

 r440 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). \endcode The \c \@arcs section is very similar to the \c \@nodes section, it again starts with a header line describing the names of the maps, but the \c "label" map is not obligatory here. The following lines describe the arcs. The first two tokens of each line are the source and the target node of the arc, respectively, then come the map The \c \@arcs section is very similar to the \c \@nodes section, it again starts with a header line describing the names of the maps, but the \c "label" map is not obligatory here. The following lines describe the arcs. The first two tokens of each line are the source and the target node of the arc, respectively, then come the map values. The source and target tokens must be node labels. \endcode If there is no map in the \c \@arcs section at all, then it must be indicated by a sole '-' sign in the first line. \code @arcs - 1   2 1   3 2   3 \endcode The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can also store the edge set of an undirected graph. In such case there is a conventional method for store arc maps in the file, if two columns has the same caption with \c '+' and \c '-' prefix, then these columns have the same caption with \c '+' and \c '-' prefix, then these columns can be regarded as the values of an arc map.
• ## doc/mainpage.dox.in

 r907 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). \section intro Introduction \subsection whatis What is LEMON LEMON stands for Library for Efficient Modeling and Optimization in Networks. It is a C++ template library aimed at combinatorial optimization tasks which often involve in working with graphs. LEMON stands for Library for Efficient Modeling and Optimization in Networks. It is a C++ template library providing efficient implementations of common data structures and algorithms with focus on combinatorial optimization tasks connected mainly with graphs and networks. \subsection howtoread How to read the documentation The project is maintained by the Egerváry Research Group on Combinatorial Optimization \ref egres at the Operations Research Department of the Eötvös Loránd University, Budapest, Hungary. LEMON is also a member of the COIN-OR initiative \ref coinor. \section howtoread How to Read the Documentation If you would like to get to know the library, see LEMON Tutorial. If you are interested in starting to use the library, see the Installation Guide. If you know what you are looking for, then try to find it under the
• ## doc/min_cost_flow.dox

 r663 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). minimum total cost from a set of supply nodes to a set of demand nodes in a network with capacity constraints (lower and upper bounds) and arc costs. and arc costs \ref amo93networkflows. Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$, - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. - For all \f$u\in V\f$ nodes: - \f$\pi(u)<=0\f$; - \f$\pi(u)\leq 0\f$; - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, then \f$\pi(u)=0\f$. Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e. \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] It means that the total demand must be less or equal to the It means that the total demand must be less or equal to the total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or positive) and all the demands have to be satisfied, but there - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. - For all \f$u\in V\f$ nodes: - \f$\pi(u)>=0\f$; - \f$\pi(u)\geq 0\f$; - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, then \f$\pi(u)=0\f$.
• ## lemon/Makefile.am

 r681 EXTRA_DIST += \ lemon/lemon.pc.in \ lemon/lemon.pc.cmake \ lemon/CMakeLists.txt \ lemon/config.h.cmake lemon/arg_parser.h \ lemon/assert.h \ lemon/bellman_ford.h \ lemon/bfs.h \ lemon/bin_heap.h \ lemon/binomial_heap.h \ lemon/bucket_heap.h \ lemon/capacity_scaling.h \ lemon/cbc.h \ lemon/circulation.h \ lemon/concept_check.h \ lemon/connectivity.h \ lemon/core.h \ lemon/cost_scaling.h \ lemon/counter.h \ lemon/core.h \ lemon/cplex.h \ lemon/cycle_canceling.h \ lemon/dfs.h \ lemon/dheap.h \ lemon/dijkstra.h \ lemon/dim2.h \ lemon/euler.h \ lemon/fib_heap.h \ lemon/fractional_matching.h \ lemon/full_graph.h \ lemon/glpk.h \ lemon/graph_to_eps.h \ lemon/grid_graph.h \ lemon/hartmann_orlin_mmc.h \ lemon/howard_mmc.h \ lemon/hypercube_graph.h \ lemon/karp_mmc.h \ lemon/kruskal.h \ lemon/hao_orlin.h \ lemon/lp_base.h \ lemon/lp_skeleton.h \ lemon/list_graph.h \ lemon/maps.h \ lemon/matching.h \ lemon/nauty_reader.h \ lemon/network_simplex.h \ lemon/pairing_heap.h \ lemon/path.h \ lemon/planarity.h \ lemon/preflow.h \ lemon/quad_heap.h \ lemon/radix_heap.h \ lemon/radix_sort.h \ lemon/smart_graph.h \ lemon/soplex.h \ lemon/static_graph.h \ lemon/suurballe.h \ lemon/time_measure.h \

• ## lemon/arg_parser.cc

 r440 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). namespace lemon { void ArgParser::_terminate(ArgParserException::Reason reason) const { if(_exit_on_problems) exit(1); else throw(ArgParserException(reason)); } void ArgParser::_showHelp(void *p) { (static_cast(p))->showHelp(); exit(1); (static_cast(p))->_terminate(ArgParserException::HELP); } ArgParser::ArgParser(int argc, const char * const *argv) :_argc(argc), _argv(argv), _command_name(argv[0]) { :_argc(argc), _argv(argv), _command_name(argv[0]), _exit_on_problems(true) { funcOption("-help","Print a short help message",_showHelp,this); synonym("help","-help"); i!=_others_help.end();++i) showHelp(i); for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i); exit(1); _terminate(ArgParserException::HELP); } std::cerr << "\nType '" << _command_name << " --help' to obtain a short summary on the usage.\n\n"; exit(1); _terminate(ArgParserException::UNKNOWN_OPT); } std::cerr << "\nType '" << _command_name << " --help' to obtain a short summary on the usage.\n\n"; exit(1); _terminate(ArgParserException::INVALID_OPT); } }
• ## lemon/arg_parser.h

 r440 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). namespace lemon { ///Exception used by ArgParser ///Exception used by ArgParser. /// class ArgParserException : public Exception { public: /// Reasons for failure /// Reasons for failure. /// enum Reason { HELP,         ///< --help option was given. UNKNOWN_OPT,  ///< Unknown option was given. INVALID_OPT   ///< Invalid combination of options. }; private: Reason _reason; public: ///Constructor ArgParserException(Reason r) throw() : _reason(r) {} ///Virtual destructor virtual ~ArgParserException() throw() {} ///A short description of the exception virtual const char* what() const throw() { switch(_reason) { case HELP: return "lemon::ArgParseException: ask for help"; break; case UNKNOWN_OPT: return "lemon::ArgParseException: unknown option"; break; case INVALID_OPT: return "lemon::ArgParseException: invalid combination of options"; break; } return ""; } ///Return the reason for the failure Reason reason() const {return _reason; } }; ///Command line arguments parser const std::string &help, void (*func)(void *),void *data); bool _exit_on_problems; void _terminate(ArgParserException::Reason reason) const; public: const std::vector &files() const { return _file_args; } ///Throw instead of exit in case of problems void throwOnProblems() { _exit_on_problems=false; } }; }

• ## lemon/bin_heap.h

 r683 #define LEMON_BIN_HEAP_H ///\ingroup auxdat ///\ingroup heaps ///\file ///\brief Binary Heap implementation. ///\brief Binary heap implementation. #include namespace lemon { ///\ingroup auxdat /// \ingroup heaps /// ///\brief A Binary Heap implementation. /// \brief Binary heap data structure. /// ///This class implements the \e binary \e heap data structure. /// This class implements the \e binary \e heap data structure. /// It fully conforms to the \ref concepts::Heap "heap concept". /// ///A \e heap is a data structure for storing items with specified values ///called \e priorities in such a way that finding the item with minimum ///priority is efficient. \c CMP specifies the ordering of the priorities. ///In a heap one can change the priority of an item, add or erase an ///item, etc. /// ///\tparam PR Type of the priority of the items. ///\tparam IM A read and writable item map with int values, used internally ///to handle the cross references. ///\tparam CMP A functor class for the ordering of the priorities. ///The default is \c std::less. /// ///\sa FibHeap ///\sa Dijkstra /// \tparam PR Type of the priorities of the items. /// \tparam IM A read-writable item map with \c int values, used /// internally to handle the cross references. /// \tparam CMP A functor class for comparing the priorities. /// The default is \c std::less. #ifdef DOXYGEN template #else template > #endif class BinHeap { public: ///\e /// Type of the item-int map. typedef IM ItemIntMap; ///\e /// Type of the priorities. typedef PR Prio; ///\e /// Type of the items stored in the heap. typedef typename ItemIntMap::Key Item; ///\e /// Type of the item-priority pairs. typedef std::pair Pair; ///\e /// Functor type for comparing the priorities. typedef CMP Compare; /// \brief Type to represent the items states. /// /// Each Item element have a state associated to it. It may be "in heap", /// "pre heap" or "post heap". The latter two are indifferent from the /// \brief Type to represent the states of the items. /// /// Each item has a state associated to it. It can be "in heap", /// "pre-heap" or "post-heap". The latter two are indifferent from the /// heap's point of view, but may be useful to the user. /// public: /// \brief The constructor. /// /// The constructor. /// \param map should be given to the constructor, since it is used /// internally to handle the cross references. The value of the map /// must be \c PRE_HEAP (-1) for every item. /// \brief Constructor. /// /// Constructor. /// \param map A map that assigns \c int values to the items. /// It is used internally to handle the cross references. /// The assigned value must be \c PRE_HEAP (-1) for each item. explicit BinHeap(ItemIntMap &map) : _iim(map) {} /// \brief The constructor. /// /// The constructor. /// \param map should be given to the constructor, since it is used /// internally to handle the cross references. The value of the map /// should be PRE_HEAP (-1) for each element. /// /// \param comp The comparator function object. /// \brief Constructor. /// /// Constructor. /// \param map A map that assigns \c int values to the items. /// It is used internally to handle the cross references. /// The assigned value must be \c PRE_HEAP (-1) for each item. /// \param comp The function object used for comparing the priorities. BinHeap(ItemIntMap &map, const Compare &comp) : _iim(map), _comp(comp) {} /// The number of items stored in the heap. /// /// \brief Returns the number of items stored in the heap. /// \brief The number of items stored in the heap. /// /// This function returns the number of items stored in the heap. int size() const { return _data.size(); } /// \brief Checks if the heap stores no items. /// /// Returns \c true if and only if the heap stores no items. /// \brief Check if the heap is empty. /// /// This function returns \c true if the heap is empty. bool empty() const { return _data.empty(); } /// \brief Make empty this heap. /// /// Make empty this heap. It does not change the cross reference map. /// If you want to reuse what is not surely empty you should first clear /// the heap and after that you should set the cross reference map for /// each item to \c PRE_HEAP. /// \brief Make the heap empty. /// /// This functon makes the heap empty. /// It does not change the cross reference map. If you want to reuse /// a heap that is not surely empty, you should first clear it and /// then you should set the cross reference map to \c PRE_HEAP /// for each item. void clear() { _data.clear(); static int parent(int i) { return (i-1)/2; } static int second_child(int i) { return 2*i+2; } static int secondChild(int i) { return 2*i+2; } bool less(const Pair &p1, const Pair &p2) const { return _comp(p1.second, p2.second); } int bubble_up(int hole, Pair p) { int bubbleUp(int hole, Pair p) { int par = parent(hole); while( hole>0 && less(p,_data[par]) ) { } int bubble_down(int hole, Pair p, int length) { int child = second_child(hole); int bubbleDown(int hole, Pair p, int length) { int child = secondChild(hole); while(child < length) { if( less(_data[child-1], _data[child]) ) { move(_data[child], hole); hole = child; child = second_child(hole); child = secondChild(hole); } child--; public: /// \brief Insert a pair of item and priority into the heap. /// /// Adds \c p.first to the heap with priority \c p.second. /// This function inserts \c p.first to the heap with priority /// \c p.second. /// \param p The pair to insert. /// \pre \c p.first must not be stored in the heap. void push(const Pair &p) { int n = _data.size(); _data.resize(n+1); bubble_up(n, p); } /// \brief Insert an item into the heap with the given heap. /// /// Adds \c i to the heap with priority \c p. bubbleUp(n, p); } /// \brief Insert an item into the heap with the given priority. /// /// This function inserts the given item into the heap with the /// given priority. /// \param i The item to insert. /// \param p The priority of the item. /// \pre \e i must not be stored in the heap. void push(const Item &i, const Prio &p) { push(Pair(i,p)); } /// \brief Returns the item with minimum priority relative to \c Compare. /// /// This method returns the item with minimum priority relative to \c /// Compare. /// \pre The heap must be nonempty. /// \brief Return the item having minimum priority. /// /// This function returns the item having minimum priority. /// \pre The heap must be non-empty. Item top() const { return _data[0].first; } /// \brief Returns the minimum priority relative to \c Compare. /// /// It returns the minimum priority relative to \c Compare. /// \pre The heap must be nonempty. /// \brief The minimum priority. /// /// This function returns the minimum priority. /// \pre The heap must be non-empty. Prio prio() const { return _data[0].second; } /// \brief Deletes the item with minimum priority relative to \c Compare. /// /// This method deletes the item with minimum priority relative to \c /// Compare from the heap. /// \brief Remove the item having minimum priority. /// /// This function removes the item having minimum priority. /// \pre The heap must be non-empty. void pop() { _iim.set(_data[0].first, POST_HEAP); if (n > 0) { bubble_down(0, _data[n], n); bubbleDown(0, _data[n], n); } _data.pop_back(); } /// \brief Deletes \c i from the heap. /// /// This method deletes item \c i from the heap. /// \param i The item to erase. /// \pre The item should be in the heap. /// \brief Remove the given item from the heap. /// /// This function removes the given item from the heap if it is /// already stored. /// \param i The item to delete. /// \pre \e i must be in the heap. void erase(const Item &i) { int h = _iim[i]; _iim.set(_data[h].first, POST_HEAP); if( h < n ) { if ( bubble_up(h, _data[n]) == h) { bubble_down(h, _data[n], n); if ( bubbleUp(h, _data[n]) == h) { bubbleDown(h, _data[n], n); } } } /// \brief Returns the priority of \c i. /// /// This function returns the priority of item \c i. /// \param i The item. /// \pre \c i must be in the heap. /// \brief The priority of the given item. /// /// This function returns the priority of the given item. /// \param i The item. /// \pre \e i must be in the heap. Prio operator[](const Item &i) const { int idx = _iim[i]; } /// \brief \c i gets to the heap with priority \c p independently /// if \c i was already there. /// /// This method calls \ref push(\c i, \c p) if \c i is not stored /// in the heap and sets the priority of \c i to \c p otherwise. /// \brief Set the priority of an item or insert it, if it is /// not stored in the heap. /// /// This method sets the priority of the given item if it is /// already stored in the heap. Otherwise it inserts the given /// item into the heap with the given priority. /// \param i The item. /// \param p The priority. } else if( _comp(p, _data[idx].second) ) { bubble_up(idx, Pair(i,p)); bubbleUp(idx, Pair(i,p)); } else { bubble_down(idx, Pair(i,p), _data.size()); } } /// \brief Decreases the priority of \c i to \c p. /// /// This method decreases the priority of item \c i to \c p. bubbleDown(idx, Pair(i,p), _data.size()); } } /// \brief Decrease the priority of an item to the given value. /// /// This function decreases the priority of an item to the given value. /// \param i The item. /// \param p The priority. /// \pre \c i must be stored in the heap with priority at least \c /// p relative to \c Compare. /// \pre \e i must be stored in the heap with priority at least \e p. void decrease(const Item &i, const Prio &p) { int idx = _iim[i]; bubble_up(idx, Pair(i,p)); } /// \brief Increases the priority of \c i to \c p. /// /// This method sets the priority of item \c i to \c p. bubbleUp(idx, Pair(i,p)); } /// \brief Increase the priority of an item to the given value. /// /// This function increases the priority of an item to the given value. /// \param i The item. /// \param p The priority. /// \pre \c i must be stored in the heap with priority at most \c /// p relative to \c Compare. /// \pre \e i must be stored in the heap with priority at most \e p. void increase(const Item &i, const Prio &p) { int idx = _iim[i]; bubble_down(idx, Pair(i,p), _data.size()); } /// \brief Returns if \c item is in, has already been in, or has /// never been in the heap. /// /// This method returns PRE_HEAP if \c item has never been in the /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP /// otherwise. In the latter case it is possible that \c item will /// get back to the heap again. bubbleDown(idx, Pair(i,p), _data.size()); } /// \brief Return the state of an item. /// /// This method returns \c PRE_HEAP if the given item has never /// been in the heap, \c IN_HEAP if it is in the heap at the moment, /// and \c POST_HEAP otherwise. /// In the latter case it is possible that the item will get back /// to the heap again. /// \param i The item. State state(const Item &i) const { } /// \brief Sets the state of the \c item in the heap. /// /// Sets the state of the \c item in the heap. It can be used to /// manually clear the heap when it is important to achive the /// better time complexity. /// \brief Set the state of an item in the heap. /// /// This function sets the state of the given item in the heap. /// It can be used to manually clear the heap when it is important /// to achive better time complexity. /// \param i The item. /// \param st The state. It should not be \c IN_HEAP. } /// \brief Replaces an item in the heap. /// /// The \c i item is replaced with \c j item. The \c i item should /// be in the heap, while the \c j should be out of the heap. The /// \c i item will out of the heap and \c j will be in the heap /// with the same prioriority as prevoiusly the \c i item. /// \brief Replace an item in the heap. /// /// This function replaces item \c i with item \c j. /// Item \c i must be in the heap, while \c j must be out of the heap. /// After calling this method, item \c i will be out of the /// heap and \c j will be in the heap with the same prioriority /// as item \c i had before. void replace(const Item& i, const Item& j) { int idx = _iim[i];
• ## lemon/bits/array_map.h

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

 r627 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). public: typedef DefaultMap<_Graph, _Item, _Value> Map; typedef typename Parent::GraphType GraphType; typedef typename Parent::Value Value;
• ## lemon/bits/edge_set_extender.h

 r617 /* -*- C++ -*- /* -*- mode: C++; indent-tabs-mode: nil; -*- * * This file is a part of LEMON, a generic C++ optimization library * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2008 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Node oppositeNode(const Node &n, const Arc &e) const { if (n == Parent::source(e)) return Parent::target(e); return Parent::target(e); else if(n==Parent::target(e)) return Parent::source(e); return Parent::source(e); else return INVALID; return INVALID; } // Iterable extensions class NodeIt : public Node { class NodeIt : public Node { const Digraph* digraph; public: explicit NodeIt(const Digraph& _graph) : digraph(&_graph) { _graph.first(static_cast(*this)); } NodeIt(const Digraph& _graph, const Node& node) : Node(node), digraph(&_graph) {} NodeIt& operator++() { digraph->next(*this); return *this; } }; class ArcIt : public Arc { _graph.first(static_cast(*this)); } NodeIt(const Digraph& _graph, const Node& node) : Node(node), digraph(&_graph) {} NodeIt& operator++() { digraph->next(*this); return *this; } }; class ArcIt : public Arc { const Digraph* digraph; public: explicit ArcIt(const Digraph& _graph) : digraph(&_graph) { _graph.first(static_cast(*this)); } ArcIt(const Digraph& _graph, const Arc& e) : Arc(e), digraph(&_graph) { } ArcIt& operator++() { digraph->next(*this); return *this; } }; class OutArcIt : public Arc { _graph.first(static_cast(*this)); } ArcIt(const Digraph& _graph, const Arc& e) : Arc(e), digraph(&_graph) { } ArcIt& operator++() { digraph->next(*this); return *this; } }; class OutArcIt : public Arc { const Digraph* digraph; public: OutArcIt(Invalid i) : Arc(i) { } OutArcIt(const Digraph& _graph, const Node& node) : digraph(&_graph) { _graph.firstOut(*this, node); } OutArcIt(const Digraph& _graph, const Arc& arc) : Arc(arc), digraph(&_graph) {} OutArcIt& operator++() { digraph->nextOut(*this); return *this; } }; class InArcIt : public Arc { OutArcIt(const Digraph& _graph, const Node& node) : digraph(&_graph) { _graph.firstOut(*this, node); } OutArcIt(const Digraph& _graph, const Arc& arc) : Arc(arc), digraph(&_graph) {} OutArcIt& operator++() { digraph->nextOut(*this); return *this; } }; class InArcIt : public Arc { const Digraph* digraph; public: InArcIt(Invalid i) : Arc(i) { } InArcIt(const Digraph& _graph, const Node& node) : digraph(&_graph) { _graph.firstIn(*this, node); } InArcIt(const Digraph& _graph, const Arc& arc) : Arc(arc), digraph(&_graph) {} InArcIt& operator++() { digraph->nextIn(*this); return *this; InArcIt(const Digraph& _graph, const Node& node) : digraph(&_graph) { _graph.firstIn(*this, node); } InArcIt(const Digraph& _graph, const Arc& arc) : Arc(arc), digraph(&_graph) {} InArcIt& operator++() { digraph->nextIn(*this); return *this; } // Mappable extension template class ArcMap class ArcMap : public MapExtender > { typedef MapExtender > Parent; public: explicit ArcMap(const Digraph& _g) : Parent(_g) {} ArcMap(const Digraph& _g, const _Value& _v) : Parent(_g, _v) {} explicit ArcMap(const Digraph& _g) : Parent(_g) {} ArcMap(const Digraph& _g, const _Value& _v) : Parent(_g, _v) {} ArcMap& operator=(const ArcMap& cmap) { return operator=(cmap); return operator=(cmap); } ArcMap& operator=(const CMap& cmap) { Parent::operator=(cmap); return *this; return *this; } return arc; } void clear() { notifier(Arc()).clear(); typedef EdgeSetExtender Graph; typedef True UndirectedTag; typedef typename Parent::Node Node; typedef typename Parent::Arc Arc; Node oppositeNode(const Node &n, const Edge &e) const { if( n == Parent::u(e)) return Parent::v(e); return Parent::v(e); else if( n == Parent::v(e)) return Parent::u(e); return Parent::u(e); else return INVALID; return INVALID; } using Parent::notifier; ArcNotifier& notifier(Arc) const { return arc_notifier; class NodeIt : public Node { class NodeIt : public Node { const Graph* graph; public: explicit NodeIt(const Graph& _graph) : graph(&_graph) { _graph.first(static_cast(*this)); } NodeIt(const Graph& _graph, const Node& node) : Node(node), graph(&_graph) {} NodeIt& operator++() { graph->next(*this); return *this; } }; class ArcIt : public Arc { _graph.first(static_cast(*this)); } NodeIt(const Graph& _graph, const Node& node) : Node(node), graph(&_graph) {} NodeIt& operator++() { graph->next(*this); return *this; } }; class ArcIt : public Arc { const Graph* graph; public: explicit ArcIt(const Graph& _graph) : graph(&_graph) { _graph.first(static_cast(*this)); } ArcIt(const Graph& _graph, const Arc& e) : Arc(e), graph(&_graph) { } ArcIt& operator++() { graph->next(*this); return *this; } }; class OutArcIt : public Arc { _graph.first(static_cast(*this)); } ArcIt(const Graph& _graph, const Arc& e) : Arc(e), graph(&_graph) { } ArcIt& operator++() { graph->next(*this); return *this; } }; class OutArcIt : public Arc { const Graph* graph; public: OutArcIt(Invalid i) : Arc(i) { } OutArcIt(const Graph& _graph, const Node& node) : graph(&_graph) { _graph.firstOut(*this, node); } OutArcIt(const Graph& _graph, const Arc& arc) : Arc(arc), graph(&_graph) {} OutArcIt& operator++() { graph->nextOut(*this); return *this; } }; class InArcIt : public Arc { OutArcIt(const Graph& _graph, const Node& node) : graph(&_graph) { _graph.firstOut(*this, node); } OutArcIt(const Graph& _graph, const Arc& arc) : Arc(arc), graph(&_graph) {} OutArcIt& operator++() { graph->nextOut(*this); return *this; } }; class InArcIt : public Arc { const Graph* graph; public: InArcIt(Invalid i) : Arc(i) { } InArcIt(const Graph& _graph, const Node& node) : graph(&_graph) { _graph.firstIn(*this, node); } InArcIt(const Graph& _graph, const Arc& arc) : Arc(arc), graph(&_graph) {} InArcIt& operator++() { graph->nextIn(*this); return *this; } }; class EdgeIt : public Parent::Edge { InArcIt(const Graph& _graph, const Node& node) : graph(&_graph) { _graph.firstIn(*this, node); } InArcIt(const Graph& _graph, const Arc& arc) : Arc(arc), graph(&_graph) {} InArcIt& operator++() { graph->nextIn(*this); return *this; } }; class EdgeIt : public Parent::Edge { const Graph* graph; public: explicit EdgeIt(const Graph& _graph) : graph(&_graph) { _graph.first(static_cast(*this)); } EdgeIt(const Graph& _graph, const Edge& e) : Edge(e), graph(&_graph) { } EdgeIt& operator++() { graph->next(*this); return *this; _graph.first(static_cast(*this)); } EdgeIt(const Graph& _graph, const Edge& e) : Edge(e), graph(&_graph) { } EdgeIt& operator++() { graph->next(*this); return *this; } IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { _graph.firstInc(*this, direction, n); _graph.firstInc(*this, direction, n); } IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n) : graph(&_graph), Edge(ue) { direction = (_graph.source(ue) == n); : graph(&_graph), Edge(ue) { direction = (_graph.source(ue) == n); } IncEdgeIt& operator++() { graph->nextInc(*this, direction); return *this; graph->nextInc(*this, direction); return *this; } }; template class ArcMap class ArcMap : public MapExtender > { typedef MapExtender > Parent; public: ArcMap(const Graph& _g) : Parent(_g) {} ArcMap(const Graph& _g, const _Value& _v) : Parent(_g, _v) {} explicit ArcMap(const Graph& _g) : Parent(_g) {} ArcMap(const Graph& _g, const _Value& _v) : Parent(_g, _v) {} ArcMap& operator=(const ArcMap& cmap) { return operator=(cmap); return operator=(cmap); } ArcMap& operator=(const CMap& cmap) { Parent::operator=(cmap); return *this; return *this; } template class EdgeMap class EdgeMap : public MapExtender > { typedef MapExtender > Parent; public: EdgeMap(const Graph& _g) : Parent(_g) {} EdgeMap(const Graph& _g, const _Value& _v) : Parent(_g, _v) {} explicit EdgeMap(const Graph& _g) : Parent(_g) {} EdgeMap(const Graph& _g, const _Value& _v) : Parent(_g, _v) {} EdgeMap& operator=(const EdgeMap& cmap) { return operator=(cmap); return operator=(cmap); } EdgeMap& operator=(const CMap& cmap) { Parent::operator=(cmap); return *this; return *this; } return edge; } void clear() { notifier(Arc()).clear(); arc_notifier.clear(); } };

 r617 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). typedef GraphAdaptorExtender Adaptor; typedef True UndirectedTag; typedef typename Parent::Node Node; typedef typename Parent::Arc Arc;
• ## lemon/bits/graph_extender.h

 r617 } Node fromId(int id, Node) const { static Node fromId(int id, Node) { return Parent::nodeFromId(id); } Arc fromId(int id, Arc) const { static Arc fromId(int id, Arc) { return Parent::arcFromId(id); } } Node fromId(int id, Node) const { static Node fromId(int id, Node) { return Parent::nodeFromId(id); } Arc fromId(int id, Arc) const { static Arc fromId(int id, Arc) { return Parent::arcFromId(id); } Edge fromId(int id, Edge) const { static Edge fromId(int id, Edge) { return Parent::edgeFromId(id); } public: NodeMap(const Graph& graph) explicit NodeMap(const Graph& graph) : Parent(graph) {} NodeMap(const Graph& graph, const _Value& value) public: ArcMap(const Graph& graph) explicit ArcMap(const Graph& graph) : Parent(graph) {} ArcMap(const Graph& graph, const _Value& value) public: EdgeMap(const Graph& graph) explicit EdgeMap(const Graph& graph) : Parent(graph) {}
• ## lemon/bits/path_dump.h

 r529 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). bool empty() const { return predMap[target] != INVALID; return predMap[target] == INVALID; } bool empty() const { return source != target; return predMatrixMap(source, target) == INVALID; }
• ## lemon/bits/solver_bits.h

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

 r483 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2011 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). #include #include #ifndef WIN32 #include #endif #include #endif GetSystemTime(&time); char buf1[11], buf2[9], buf3[5]; if (GetDateFormat(MY_LOCALE, 0, &time, if (GetDateFormat(MY_LOCALE, 0, &time, ("ddd MMM dd"), buf1, 11) && GetTimeFormat(MY_LOCALE, 0, &time,
• ## lemon/bucket_heap.h

 r683 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). #define LEMON_BUCKET_HEAP_H ///\ingroup auxdat ///\ingroup heaps ///\file ///\brief Bucket Heap implementation. ///\brief Bucket heap implementation. #include } /// \ingroup auxdat /// /// \brief A Bucket Heap implementation. /// /// This class implements the \e bucket \e heap data structure. A \e heap /// is a data structure for storing items with specified values called \e /// priorities in such a way that finding the item with minimum priority is /// efficient. The bucket heap is very simple implementation, it can store /// only integer priorities and it stores for each priority in the /// \f$[0..C) \f$ range a list of items. So it should be used only when /// the priorities are small. It is not intended to use as dijkstra heap. /// /// \param IM A read and write Item int map, used internally /// to handle the cross references. /// \param MIN If the given parameter is false then instead of the /// minimum value the maximum can be retrivied with the top() and /// prio() member functions. /// \ingroup heaps /// /// \brief Bucket heap data structure. /// /// This class implements the \e bucket \e heap data structure. /// It practically conforms to the \ref concepts::Heap "heap concept", /// but it has some limitations. /// /// The bucket heap is a very simple structure. It can store only /// \c int priorities and it maintains a list of items for each priority /// in the range [0..C). So it should only be used when the /// priorities are small. It is not intended to use as a Dijkstra heap. /// /// \tparam IM A read-writable item map with \c int values, used /// internally to handle the cross references. /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap. /// The default is \e min-heap. If this parameter is set to \c false, /// then the comparison is reversed, so the top(), prio() and pop() /// functions deal with the item having maximum priority instead of the /// minimum. /// /// \sa SimpleBucketHeap template class BucketHeap { public: /// \e typedef typename IM::Key Item; /// \e /// Type of the item-int map. typedef IM ItemIntMap; /// Type of the priorities. typedef int Prio; /// \e typedef std::pair Pair; /// \e typedef IM ItemIntMap; /// Type of the items stored in the heap. typedef typename ItemIntMap::Key Item; /// Type of the item-priority pairs. typedef std::pair Pair; private: public: /// \brief Type to represent the items states. /// /// Each Item element have a state associated to it. It may be "in heap", /// "pre heap" or "post heap". The latter two are indifferent from the /// \brief Type to represent the states of the items. /// /// Each item has a state associated to it. It can be "in heap", /// "pre-heap" or "post-heap". The latter two are indifferent from the /// heap's point of view, but may be useful to the user. /// public: /// \brief The constructor. /// /// The constructor. /// \param map should be given to the constructor, since it is used /// internally to handle the cross references. The value of the map /// should be PRE_HEAP (-1) for each element. /// \brief Constructor. /// /// Constructor. /// \param map A map that assigns \c int values to the items. /// It is used internally to handle the cross references. /// The assigned value must be \c PRE_HEAP (-1) for each item. explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {} /// The number of items stored in the heap. /// /// \brief Returns the number of items stored in the heap. /// \brief The number of items stored in the heap. /// /// This function returns the number of items stored in the heap. int size() const { return _data.size(); } /// \brief Checks if the heap stores no items. /// /// Returns \c true if and only if the heap stores no items. /// \brief Check if the heap is empty. /// /// This function returns \c true if the heap is empty. bool empty() const { return _data.empty(); } /// \brief Make empty this heap. /// /// Make empty this heap. It does not change the cross reference /// map.  If you want to reuse a heap what is not surely empty you /// should first clear the heap and after that you should set the /// cross reference map for each item to \c PRE_HEAP. /// \brief Make the heap empty. /// /// This functon makes the heap empty. /// It does not change the cross reference map. If you want to reuse /// a heap that is not surely empty, you should first clear it and /// then you should set the cross reference map to \c PRE_HEAP /// for each item. void clear() { _data.clear(); _first.clear(); _minimum = 0; private: void relocate_last(int idx) { void relocateLast(int idx) { if (idx + 1 < int(_data.size())) { _data[idx] = _data.back(); public: /// \brief Insert a pair of item and priority into the heap. /// /// Adds \c p.first to the heap with priority \c p.second. /// This function inserts \c p.first to the heap with priority /// \c p.second. /// \param p The pair to insert. /// \pre \c p.first must not be stored in the heap. void push(const Pair& p) { push(p.first, p.second); /// \brief Insert an item into the heap with the given priority. /// /// Adds \c i to the heap with priority \c p. /// This function inserts the given item into the heap with the /// given priority. /// \param i The item to insert. /// \param p The priority of the item. /// \pre \e i must not be stored in the heap. void push(const Item &i, const Prio &p) { int idx = _data.size(); } /// \brief Returns the item with minimum priority. /// /// This method returns the item with minimum priority. /// \pre The heap must be nonempty. /// \brief Return the item having minimum priority. /// /// This function returns the item having minimum priority. /// \pre The heap must be non-empty. Item top() const { while (_first[_minimum] == -1) { } /// \brief Returns the minimum priority. /// /// It returns the minimum priority. /// \pre The heap must be nonempty. /// \brief The minimum priority. /// /// This function returns the minimum priority. /// \pre The heap must be non-empty. Prio prio() const { while (_first[_minimum] == -1) { } /// \brief Deletes the item with minimum priority. /// /// This method deletes the item with minimum priority from the heap. /// \brief Remove the item having minimum priority. /// /// This function removes the item having minimum priority. /// \pre The heap must be non-empty. void pop() { _iim[_data[idx].item] = -2; unlace(idx); relocate_last(idx); } /// \brief Deletes \c i from the heap. /// /// This method deletes item \c i from the heap, if \c i was /// already stored in the heap. /// \param i The item to erase. relocateLast(idx); } /// \brief Remove the given item from the heap. /// /// This function removes the given item from the heap if it is /// already stored. /// \param i The item to delete. /// \pre \e i must be in the heap. void erase(const Item &i) { int idx = _iim[i]; _iim[_data[idx].item] = -2; unlace(idx); relocate_last(idx); } /// \brief Returns the priority of \c i. /// /// This function returns the priority of item \c i. /// \pre \c i must be in the heap. /// \param i The item. relocateLast(idx); } /// \brief The priority of the given item. /// /// This function returns the priority of the given item. /// \param i The item. /// \pre \e i must be in the heap. Prio operator[](const Item &i) const { int idx = _iim[i]; } /// \brief \c i gets to the heap with priority \c p independently /// if \c i was already there. /// /// This method calls \ref push(\c i, \c p) if \c i is not stored /// in the heap and sets the priority of \c i to \c p otherwise. /// \brief Set the priority of an item or insert it, if it is /// not stored in the heap. /// /// This method sets the priority of the given item if it is /// already stored in the heap. Otherwise it inserts the given /// item into the heap with the given priority. /// \param i The item. /// \param p The priority. } /// \brief Decreases the priority of \c i to \c p. /// /// This method decreases the priority of item \c i to \c p. /// \pre \c i must be stored in the heap with priority at least \c /// p relative to \c Compare. /// \brief Decrease the priority of an item to the given value. /// /// This function decreases the priority of an item to the given value. /// \param i The item. /// \param p The priority. /// \pre \e i must be stored in the heap with priority at least \e p. void decrease(const Item &i, const Prio &p) { int idx = _iim[i]; } /// \brief Increases the priority of \c i to \c p. /// /// This method sets the priority of item \c i to \c p. /// \pre \c i must be stored in the heap with priority at most \c /// p relative to \c Compare. /// \brief Increase the priority of an item to the given value. /// /// This function increases the priority of an item to the given value. /// \param i The item. /// \param p The priority. /// \pre \e i must be stored in the heap with priority at most \e p. void increase(const Item &i, const Prio &p) { int idx = _iim[i]; } /// \brief Returns if \c item is in, has already been in, or has /// never been in the heap. /// /// This method returns PRE_HEAP if \c item has never been in the /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP /// otherwise. In the latter case it is possible that \c item will /// get back to the heap again. /// \brief Return the state of an item. /// /// This method returns \c PRE_HEAP if the given item has never /// been in the heap, \c IN_HEAP if it is in the heap at the moment, /// and \c POST_HEAP otherwise. /// In the latter case it is possible that the item will get back /// to the heap again. /// \param i The item. State state(const Item &i) const { } /// \brief Sets the state of the \c item in the heap. /// /// Sets the state of the \c item in the heap. It can be used to /// manually clear the heap when it is important to achive the /// better time complexity. /// \brief Set the state of an item in the heap. /// /// This function sets the state of the given item in the heap. /// It can be used to manually clear the heap when it is important /// to achive better time complexity. /// \param i The item. /// \param st The state. It should not be \c IN_HEAP. }; // class BucketHeap /// \ingroup auxdat /// /// \brief A Simplified Bucket Heap implementation. /// \ingroup heaps /// /// \brief Simplified bucket heap data structure. /// /// This class implements a simplified \e bucket \e heap data /// structure.  It does not provide some functionality but it faster /// and simplier data structure than the BucketHeap. The main /// difference is that the BucketHeap stores for every key a double /// linked list while this class stores just simple lists. In the /// other way it does not support erasing each elements just the /// minimal and it does not supports key increasing, decreasing. /// /// \param IM A read and write Item int map, used internally /// to handle the cross references. /// \param MIN If the given parameter is false then instead of the /// minimum value the maximum can be retrivied with the top() and /// prio() member functions. /// structure. It does not provide some functionality, but it is /// faster and simpler than BucketHeap. The main difference is /// that BucketHeap stores a doubly-linked list for each key while /// this class stores only simply-linked lists. It supports erasing /// only for the item having minimum priority and it does not support /// key increasing and decreasing. /// /// Note that this implementation does not conform to the /// \ref concepts::Heap "heap concept" due to the lack of some /// functionality. /// /// \tparam IM A read-writable item map with \c int values, used /// internally to handle the cross references. /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap. /// The default is \e min-heap. If this parameter is set to \c false, /// then the comparison is reversed, so the top(), prio() and pop() /// functions deal with the item having maximum priority instead of the /// minimum. /// /// \sa BucketHeap public: typedef typename IM::Key Item; /// Type of the item-int map. typedef IM ItemIntMap; /// Type of the priorities. typedef int Prio; typedef std::pair Pair; typedef IM ItemIntMap; /// Type of the items stored in the heap. typedef typename ItemIntMap::Key Item; /// Type of the item-priority pairs. typedef std::pair Pair; private: public: /// \brief Type to represent the items states. /// /// Each Item element have a state associated to it. It may be "in heap", /// "pre heap" or "post heap". The latter two are indifferent from the /// \brief Type to represent the states of the items. /// /// Each item has a state associated to it. It can be "in heap", /// "pre-heap" or "post-heap". The latter two are indifferent from the /// heap's point of view, but may be useful to the user. /// public: /// \brief The constructor. /// /// The constructor. /// \param map should be given to the constructor, since it is used /// internally to handle the cross references. The value of the map /// should be PRE_HEAP (-1) for each element. /// \brief Constructor. /// /// Constructor. /// \param map A map that assigns \c int values to the items. /// It is used internally to handle the cross references. /// The assigned value must be \c PRE_HEAP (-1) for each item. explicit SimpleBucketHeap(ItemIntMap &map) : _iim(map), _free(-1), _num(0), _minimum(0) {} /// \brief Returns the number of items stored in the heap. /// /// The number of items stored in the heap. /// \brief The number of items stored in the heap. /// /// This function returns the number of items stored in the heap. int size() const { return _num; } /// \brief Checks if the heap stores no items. /// /// Returns \c true if and only if the heap stores no items. /// \brief Check if the heap is empty. /// /// This function returns \c true if the heap is empty. bool empty() const { return _num == 0; } /// \brief Make empty this heap. /// /// Make empty this heap. It does not change the cross reference /// map.  If you want to reuse a heap what is not surely empty you /// should first clear the heap and after that you should set the /// cross reference map for each item to \c PRE_HEAP. /// \brief Make the heap empty. /// /// This functon makes the heap empty. /// It does not change the cross reference map. If you want to reuse /// a heap that is not surely empty, you should first clear it and /// then you should set the cross reference map to \c PRE_HEAP /// for each item. void clear() { _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0; /// \brief Insert a pair of item and priority into the heap. /// /// Adds \c p.first to the heap with priority \c p.second. /// This function inserts \c p.first to the heap with priority /// \c p.second. /// \param p The pair to insert. /// \pre \c p.first must not be stored in the heap. void push(const Pair& p) { push(p.first, p.second); /// \brief Insert an item into the heap with the given priority. /// /// Adds \c i to the heap with priority \c p. /// This function inserts the given item into the heap with the /// given priority. /// \param i The item to insert. /// \param p The priority of the item. /// \pre \e i must not be stored in the heap. void push(const Item &i, const Prio &p) { int idx; } /// \brief Returns the item with minimum priority. /// /// This method returns the item with minimum priority. /// \pre The heap must be nonempty. /// \brief Return the item having minimum priority. /// /// This function returns the item having minimum priority. /// \pre The heap must be non-empty. Item top() const { while (_first[_minimum] == -1) { } /// \brief Returns the minimum priority. /// /// It returns the minimum priority. /// \pre The heap must be nonempty. /// \brief The minimum priority. /// /// This function returns the minimum priority. /// \pre The heap must be non-empty. Prio prio() const { while (_first[_minimum] == -1) { } /// \brief Deletes the item with minimum priority. /// /// This method deletes the item with minimum priority from the heap. /// \brief Remove the item having minimum priority. /// /// This function removes the item having minimum priority. /// \pre The heap must be non-empty. void pop() { } /// \brief Returns the priority of \c i. /// /// This function returns the priority of item \c i. /// \warning This operator is not a constant time function /// because it scans the whole data structure to find the proper /// value. /// \pre \c i must be in the heap. /// \param i The item. /// \brief The priority of the given item. /// /// This function returns the priority of the given item. /// \param i The item. /// \pre \e i must be in the heap. /// \warning This operator is not a constant time function because /// it scans the whole data structure to find the proper value. Prio operator[](const Item &i) const { for (int k = 0; k < _first.size(); ++k) { for (int k = 0; k < int(_first.size()); ++k) { int idx = _first[k]; while (idx != -1) { } /// \brief Returns if \c item is in, has already been in, or has /// never been in the heap. /// /// This method returns PRE_HEAP if \c item has never been in the /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP /// otherwise. In the latter case it is possible that \c item will /// get back to the heap again. /// \brief Return the state of an item. /// /// This method returns \c PRE_HEAP if the given item has never /// been in the heap, \c IN_HEAP if it is in the heap at the moment, /// and \c POST_HEAP otherwise. /// In the latter case it is possible that the item will get back /// to the heap again. /// \param i The item. State state(const Item &i) const {
• ## lemon/cbc.cc

 r576 } int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) { std::vector indexes; std::vector values; for(ExprIterator it = b; it != e; ++it) { indexes.push_back(it->first); values.push_back(it->second); } _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u); return _prob->numberRows() - 1; } void CbcMip::_eraseCol(int i) {
• ## lemon/cbc.h

 r576 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). virtual int _addCol(); virtual int _addRow(); virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); virtual void _eraseCol(int i); int _message_level; };
• ## lemon/circulation.h

 r688 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /// \brief The type of supply map. /// /// The type of the map that stores the signed supply values of the /// nodes. /// The type of the map that stores the signed supply values of the /// nodes. /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. typedef SM SupplyMap; /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" /// concept. #ifdef DOXYGEN typedef GR::ArcMap FlowMap; #else typedef typename Digraph::template ArcMap FlowMap; #endif /// \brief Instantiates a FlowMap. /// The elevator type used by the algorithm. /// /// \sa Elevator /// \sa LinkedElevator /// \sa Elevator, LinkedElevator #ifdef DOXYGEN typedef lemon::Elevator Elevator; #else typedef lemon::Elevator Elevator; #endif /// \brief Instantiates an Elevator. \geq sup(u) \quad \forall u\in V, \f] \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f] The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or negative in order to have a feasible solution (since the sum constraints have to be satisfied with equality, i.e. all demands have to be satisfied and all supplies have to be used. If you need the opposite inequalities in the supply/demand constraints (i.e. the total demand is less than the total supply and all the demands \tparam SM The type of the supply map. The default map type is \ref concepts::Digraph::NodeMap "GR::NodeMap". \tparam TR The traits class that defines various types used by the algorithm. By default, it is \ref CirculationDefaultTraits "CirculationDefaultTraits". In most cases, this parameter should not be set directly, consider to use the named template parameters instead. */ #ifdef DOXYGEN /// able to automatically created by the algorithm (i.e. the /// digraph and the maximum level should be passed to it). /// However an external elevator object could also be passed to the /// However, an external elevator object could also be passed to the /// algorithm with the \ref elevator(Elevator&) "elevator()" function /// before calling \ref run() or \ref init(). /// \param graph The digraph the algorithm runs on. /// \param lower The lower bounds for the flow values on the arcs. /// \param upper The upper bounds (capacities) for the flow values /// \param upper The upper bounds (capacities) for the flow values /// on the arcs. /// \param supply The signed supply values of the nodes. } /// \brief Sets the tolerance used by algorithm. /// /// Sets the tolerance used by algorithm. /// \brief Sets the tolerance used by the algorithm. /// /// Sets the tolerance object used by the algorithm. /// \return (*this) Circulation& tolerance(const Tolerance& tolerance) { _tol = tolerance; /// \brief Returns a const reference to the tolerance. /// /// Returns a const reference to the tolerance. /// Returns a const reference to the tolerance object used by /// the algorithm. const Tolerance& tolerance() const { return _tol; /// \name Execution Control /// The simplest way to execute the algorithm is to call \ref run().\n /// If you need more control on the initial solution or the execution, /// first you have to call one of the \ref init() functions, then /// If you need better control on the initial solution or the execution, /// you have to call one of the \ref init() functions first, then /// the \ref start() function.
• ## lemon/clp.cc

 r576 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2008 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). int ClpLp::_addRow() { _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX); return _prob->numberRows() - 1; } int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) { std::vector indexes; std::vector values; for(ExprIterator it = b; it != e; ++it) { indexes.push_back(it->first); values.push_back(it->second); } _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u); return _prob->numberRows() - 1; }
• ## lemon/clp.h

 r576 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2008 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). virtual int _addCol(); virtual int _addRow(); virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); virtual void _eraseCol(int i); virtual void _messageLevel(MessageLevel); public:
• ## lemon/concepts/digraph.h

 r580 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /// \brief Class describing the concept of directed graphs. /// /// This class describes the \ref concept "concept" of the /// immutable directed digraphs. /// This class describes the common interface of all directed /// graphs (digraphs). /// /// Note that actual digraph implementation like @ref ListDigraph or /// @ref SmartDigraph may have several additional functionality. /// Like all concept classes, it only provides an interface /// without any sensible implementation. So any general algorithm for /// directed graphs should compile with this class, but it will not /// run properly, of course. /// An actual digraph implementation like \ref ListDigraph or /// \ref SmartDigraph may have additional functionality. /// /// \sa concept /// \sa Graph class Digraph { private: ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. /// Digraph(const Digraph &) {}; ///\brief Assignment of \ref Digraph "Digraph"s to another ones are ///\e not allowed. Use DigraphCopy() instead. ///Assignment of \ref Digraph "Digraph"s to another ones are ///\e not allowed.  Use DigraphCopy() instead. /// Diraphs are \e not copy constructible. Use DigraphCopy instead. Digraph(const Digraph &) {} /// \brief Assignment of a digraph to another one is \e not allowed. /// Use DigraphCopy instead. void operator=(const Digraph &) {} public: ///\e /// Defalult constructor. /// Defalult constructor. /// /// Default constructor. Digraph() { } /// Class for identifying a node of the digraph /// The node type of the digraph /// This class identifies a node of the digraph. It also serves /// as a base class of the node iterators, /// thus they will convert to this type. /// thus they convert to this type. class Node { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the object to an undefined value. Node() { } /// Copy constructor. Node(const Node&) { } /// Invalid constructor \& conversion. /// This constructor initializes the iterator to be invalid. /// %Invalid constructor \& conversion. /// Initializes the object to be invalid. /// \sa Invalid for more details. Node(Invalid) { } /// Equality operator /// Equality operator. /// /// Two iterators are equal if and only if they point to the /// same object or both are invalid. /// same object or both are \c INVALID. bool operator==(Node) const { return true; } /// Inequality operator /// \sa operator==(Node n) /// /// Inequality operator. bool operator!=(Node) const { return true; } /// Artificial ordering operator. /// To allow the use of digraph descriptors as key type in std::map or /// similar associative container we require this. /// /// \note This operator only have to define some strict ordering of /// the items; this order has nothing to do with the iteration /// ordering of the items. /// Artificial ordering operator. /// /// \note This operator only has to define some strict ordering of /// the nodes; this order has nothing to do with the iteration /// ordering of the nodes. bool operator<(Node) const { return false; } }; /// This iterator goes through each node. /// This iterator goes through each node. /// Its usage is quite simple, for example you can count the number /// of nodes in digraph \c g of type \c Digraph like this: }; /// Iterator class for the nodes. /// This iterator goes through each node of the digraph. /// Its usage is quite simple, for example, you can count the number /// of nodes in a digraph \c g of type \c %Digraph like this: ///\code /// int count=0; /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. NodeIt() { } /// Copy constructor. /// NodeIt(const NodeIt& n) : Node(n) { } /// Invalid constructor \& conversion. /// Initialize the iterator to be invalid. /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. NodeIt(Invalid) { } /// Sets the iterator to the first node. /// Sets the iterator to the first node of \c g. /// NodeIt(const Digraph&) { } /// Node -> NodeIt conversion. /// Sets the iterator to the node of \c the digraph pointed by /// the trivial iterator. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the first node of the given digraph. /// explicit NodeIt(const Digraph&) { } /// Sets the iterator to the given node. /// Sets the iterator to the given node of the given digraph. /// NodeIt(const Digraph&, const Node&) { } /// Next node. /// Class for identifying an arc of the digraph /// The arc type of the digraph /// This class identifies an arc of the digraph. It also serves /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the object to an undefined value. Arc() { } /// Copy constructor. /// Arc(const Arc&) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the object to be invalid. /// \sa Invalid for more details. Arc(Invalid) { } /// Equality operator /// Equality operator. /// /// Two iterators are equal if and only if they point to the /// same object or both are invalid. /// same object or both are \c INVALID. bool operator==(Arc) const { return true; } /// Inequality operator /// \sa operator==(Arc n) /// /// Inequality operator. bool operator!=(Arc) const { return true; } /// Artificial ordering operator. /// To allow the use of digraph descriptors as key type in std::map or /// similar associative container we require this. /// /// \note This operator only have to define some strict ordering of /// the items; this order has nothing to do with the iteration /// ordering of the items. /// Artificial ordering operator. /// /// \note This operator only has to define some strict ordering of /// the arcs; this order has nothing to do with the iteration /// ordering of the arcs. bool operator<(Arc) const { return false; } }; /// This iterator goes trough the outgoing arcs of a node. /// Iterator class for the outgoing arcs of a node. /// This iterator goes trough the \e outgoing arcs of a certain node /// of a digraph. /// Its usage is quite simple, for example you can count the number /// Its usage is quite simple, for example, you can count the number /// of outgoing arcs of a node \c n /// in digraph \c g of type \c Digraph as follows. /// in a digraph \c g of type \c %Digraph as follows. ///\code /// int count=0; /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; ///\endcode class OutArcIt : public Arc { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. OutArcIt() { } /// Copy constructor. /// OutArcIt(const OutArcIt& e) : Arc(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. OutArcIt(Invalid) { } /// This constructor sets the iterator to the first outgoing arc. /// This constructor sets the iterator to the first outgoing arc of /// the node. /// Sets the iterator to the first outgoing arc. /// Sets the iterator to the first outgoing arc of the given node. /// OutArcIt(const Digraph&, const Node&) { } /// Arc -> OutArcIt conversion /// Sets the iterator to the value of the trivial iterator. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the given arc. /// Sets the iterator to the given arc of the given digraph. /// OutArcIt(const Digraph&, const Arc&) { } ///Next outgoing arc /// Next outgoing arc /// Assign the iterator to the next }; /// This iterator goes trough the incoming arcs of a node. /// Iterator class for the incoming arcs of a node. /// This iterator goes trough the \e incoming arcs of a certain node /// of a digraph. /// Its usage is quite simple, for example you can count the number /// of outgoing arcs of a node \c n /// in digraph \c g of type \c Digraph as follows. /// Its usage is quite simple, for example, you can count the number /// of incoming arcs of a node \c n /// in a digraph \c g of type \c %Digraph as follows. ///\code /// int count=0; /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count; /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; ///\endcode class InArcIt : public Arc { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. InArcIt() { } /// Copy constructor. /// InArcIt(const InArcIt& e) : Arc(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. InArcIt(Invalid) { } /// This constructor sets the iterator to first incoming arc. /// This constructor set the iterator to the first incoming arc of /// the node. /// Sets the iterator to the first incoming arc. /// Sets the iterator to the first incoming arc of the given node. /// InArcIt(const Digraph&, const Node&) { } /// Arc -> InArcIt conversion /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the given arc. /// Sets the iterator to the given arc of the given digraph. /// InArcIt(const Digraph&, const Arc&) { } /// Next incoming arc /// Assign the iterator to the next inarc of the corresponding node. /// /// Assign the iterator to the next /// incoming arc of the corresponding node. InArcIt& operator++() { return *this; } }; /// This iterator goes through each arc. /// This iterator goes through each arc of a digraph. /// Its usage is quite simple, for example you can count the number /// of arcs in a digraph \c g of type \c Digraph as follows: /// Iterator class for the arcs. /// This iterator goes through each arc of the digraph. /// Its usage is quite simple, for example, you can count the number /// of arcs in a digraph \c g of type \c %Digraph as follows: ///\code /// int count=0; /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count; /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count; ///\endcode class ArcIt : public Arc { /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. ArcIt() { } /// Copy constructor. /// ArcIt(const ArcIt& e) : Arc(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. ArcIt(Invalid) { } /// This constructor sets the iterator to the first arc. /// This constructor sets the iterator to the first arc of \c g. ///@param g the digraph ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); } /// Arc -> ArcIt conversion /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the first arc. /// Sets the iterator to the first arc of the given digraph. /// explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); } /// Sets the iterator to the given arc. /// Sets the iterator to the given arc of the given digraph. /// ArcIt(const Digraph&, const Arc&) { } ///Next arc /// Next arc /// Assign the iterator to the next arc. /// ArcIt& operator++() { return *this; } }; ///Gives back the target node of an arc. ///Gives back the target node of an arc. /// /// \brief The source node of the arc. /// /// Returns the source node of the given arc. Node source(Arc) const { return INVALID; } /// \brief The target node of the arc. /// /// Returns the target node of the given arc. Node target(Arc) const { return INVALID; } ///Gives back the source node of an arc. ///Gives back the source node of an arc. /// Node source(Arc) const { return INVALID; } /// \brief Returns the ID of the node. /// \brief The ID of the node. /// /// Returns the ID of the given node. int id(Node) const { return -1; } /// \brief Returns the ID of the arc. /// \brief The ID of the arc. /// /// Returns the ID of the given arc. int id(Arc) const { return -1; } /// \brief Returns the node with the given ID. /// /// \pre The argument should be a valid node ID in the graph. /// \brief The node with the given ID. /// /// Returns the node with the given ID. /// \pre The argument should be a valid node ID in the digraph. Node nodeFromId(int) const { return INVALID; } /// \brief Returns the arc with the given ID. /// /// \pre The argument should be a valid arc ID in the graph. /// \brief The arc with the given ID. /// /// Returns the arc with the given ID. /// \pre The argument should be a valid arc ID in the digraph. Arc arcFromId(int) const { return INVALID; } /// \brief Returns an upper bound on the node IDs. /// \brief An upper bound on the node IDs. /// /// Returns an upper bound on the node IDs. int maxNodeId() const { return -1; } /// \brief Returns an upper bound on the arc IDs. /// \brief An upper bound on the arc IDs. /// /// Returns an upper bound on the arc IDs. int maxArcId() const { return -1; } int maxId(Arc) const { return -1; } /// \brief The opposite node on the arc. /// /// Returns the opposite node on the given arc. Node oppositeNode(Node, Arc) const { return INVALID; } /// \brief The base node of the iterator. /// /// Gives back the base node of the iterator. /// It is always the target of the pointed arc. Node baseNode(const InArcIt&) const { return INVALID; } /// Returns the base node of the given outgoing arc iterator /// (i.e. the source node of the corresponding arc). Node baseNode(OutArcIt) const { return INVALID; } /// \brief The running node of the iterator. /// /// Gives back the running node of the iterator. /// It is always the source of the pointed arc. Node runningNode(const InArcIt&) const { return INVALID; } /// Returns the running node of the given outgoing arc iterator /// (i.e. the target node of the corresponding arc). Node runningNode(OutArcIt) const { return INVALID; } /// \brief The base node of the iterator. /// /// Gives back the base node of the iterator. /// It is always the source of the pointed arc. Node baseNode(const OutArcIt&) const { return INVALID; } /// Returns the base node of the given incomming arc iterator /// (i.e. the target node of the corresponding arc). Node baseNode(InArcIt) const { return INVALID; } /// \brief The running node of the iterator. /// /// Gives back the running node of the iterator. /// It is always the target of the pointed arc. Node runningNode(const OutArcIt&) const { return INVALID; } /// \brief The opposite node on the given arc. /// /// Gives back the opposite node on the given arc. Node oppositeNode(const Node&, const Arc&) const { return INVALID; } /// \brief Reference map of the nodes to type \c T. /// /// Reference map of the nodes to type \c T. /// Returns the running node of the given incomming arc iterator /// (i.e. the source node of the corresponding arc). Node runningNode(InArcIt) const { return INVALID; } /// \brief Standard graph map type for the nodes. /// /// Standard graph map type for the nodes. /// It conforms to the ReferenceMap concept. template class NodeMap : public ReferenceMap { public: ///\e NodeMap(const Digraph&) { } ///\e /// Constructor explicit NodeMap(const Digraph&) { } /// Constructor with given initial value NodeMap(const Digraph&, T) { } private: ///Copy constructor NodeMap(const NodeMap& nm) : NodeMap(const NodeMap& nm) : ReferenceMap(nm) { } ///Assignment operator }; /// \brief Reference map of the arcs to type \c T. /// /// Reference map of the arcs to type \c T. /// \brief Standard graph map type for the arcs. /// /// Standard graph map type for the arcs. /// It conforms to the ReferenceMap concept. template class ArcMap : public ReferenceMap { public: ///\e ArcMap(const Digraph&) { } ///\e /// Constructor explicit ArcMap(const Digraph&) { } /// Constructor with given initial value ArcMap(const Digraph&, T) { } private: ///Copy constructor
• ## lemon/concepts/graph.h

 r657 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). ///\ingroup graph_concepts ///\file ///\brief The concept of Undirected Graphs. ///\brief The concept of undirected graphs. #ifndef LEMON_CONCEPTS_GRAPH_H #include #include #include #include /// \ingroup graph_concepts /// /// \brief Class describing the concept of Undirected Graphs. /// \brief Class describing the concept of undirected graphs. /// /// This class describes the common interface of all Undirected /// Graphs. /// This class describes the common interface of all undirected /// graphs. /// /// As all concept describing classes it provides only interface /// without any sensible implementation. So any algorithm for /// undirected graph should compile with this class, but it will not /// Like all concept classes, it only provides an interface /// without any sensible implementation. So any general algorithm for /// undirected graphs should compile with this class, but it will not /// run properly, of course. /// An actual graph implementation like \ref ListGraph or /// \ref SmartGraph may have additional functionality. /// /// The LEMON undirected graphs also fulfill the concept of /// directed graphs (\ref lemon::concepts::Digraph "Digraph /// Concept"). Each edges can be seen as two opposite /// directed arc and consequently the undirected graph can be /// seen as the direceted graph of these directed arcs. The /// Graph has the Edge inner class for the edges and /// the Arc type for the directed arcs. The Arc type is /// convertible to Edge or inherited from it so from a directed /// arc we can get the represented edge. /// The undirected graphs also fulfill the concept of \ref Digraph /// "directed graphs", since each edge can also be regarded as two /// oppositely directed arcs. /// Undirected graphs provide an Edge type for the undirected edges and /// an Arc type for the directed arcs. The Arc type is convertible to /// Edge or inherited from it, i.e. the corresponding edge can be /// obtained from an arc. /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt /// and ArcMap classes can be used for the arcs (just like in digraphs). /// Both InArcIt and OutArcIt iterates on the same edges but with /// opposite direction. IncEdgeIt also iterates on the same edges /// as OutArcIt and InArcIt, but it is not convertible to Arc, /// only to Edge. /// /// In the sense of the LEMON each edge has a default /// direction (it should be in every computer implementation, /// because the order of edge's nodes defines an /// orientation). With the default orientation we can define that /// the directed arc is forward or backward directed. With the \c /// direction() and \c direct() function we can get the direction /// of the directed arc and we can direct an edge. /// In LEMON, each undirected edge has an inherent orientation. /// Thus it can defined if an arc is forward or backward oriented in /// an undirected graph with respect to this default oriantation of /// the represented edge. /// With the direction() and direct() functions the direction /// of an arc can be obtained and set, respectively. /// /// The EdgeIt is an iterator for the edges. We can use /// the EdgeMap to map values for the edges. The InArcIt and /// OutArcIt iterates on the same edges but with opposite /// direction. The IncEdgeIt iterates also on the same edges /// as the OutArcIt and InArcIt but it is not convertible to Arc just /// to Edge. /// Only nodes and edges can be added to or removed from an undirected /// graph and the corresponding arcs are added or removed automatically. /// /// \sa Digraph class Graph { private: /// Graphs are \e not copy constructible. Use DigraphCopy instead. Graph(const Graph&) {} /// \brief Assignment of a graph to another one is \e not allowed. /// Use DigraphCopy instead. void operator=(const Graph&) {} public: /// \brief The undirected graph should be tagged by the /// UndirectedTag. /// /// The undirected graph should be tagged by the UndirectedTag. This /// tag helps the enable_if technics to make compile time /// Default constructor. Graph() {} /// \brief Undirected graphs should be tagged with \c UndirectedTag. /// /// Undirected graphs should be tagged with \c UndirectedTag. /// /// This tag helps the \c enable_if technics to make compile time /// specializations for undirected graphs. typedef True UndirectedTag; /// \brief The base type of node iterators, /// or in other words, the trivial node iterator. /// /// This is the base type of each node iterator, /// thus each kind of node iterator converts to this. /// More precisely each kind of node iterator should be inherited /// from the trivial node iterator. /// The node type of the graph /// This class identifies a node of the graph. It also serves /// as a base class of the node iterators, /// thus they convert to this type. class Node { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the object to an undefined value. Node() { } /// Copy constructor. Node(const Node&) { } /// Invalid constructor \& conversion. /// This constructor initializes the iterator to be invalid. /// %Invalid constructor \& conversion. /// Initializes the object to be invalid. /// \sa Invalid for more details. Node(Invalid) { } /// Equality operator /// Equality operator. /// /// Two iterators are equal if and only if they point to the /// same object or both are invalid. /// same object or both are \c INVALID. bool operator==(Node) const { return true; } /// Inequality operator /// \sa operator==(Node n) /// /// Inequality operator. bool operator!=(Node) const { return true; } /// Artificial ordering operator. /// To allow the use of graph descriptors as key type in std::map or /// similar associative container we require this. /// /// \note This operator only have to define some strict ordering of /// Artificial ordering operator. /// /// \note This operator only has to define some strict ordering of /// the items; this order has nothing to do with the iteration /// ordering of the items. }; /// This iterator goes through each node. /// This iterator goes through each node. /// Its usage is quite simple, for example you can count the number /// of nodes in graph \c g of type \c Graph like this: /// Iterator class for the nodes. /// This iterator goes through each node of the graph. /// Its usage is quite simple, for example, you can count the number /// of nodes in a graph \c g of type \c %Graph like this: ///\code /// int count=0; /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. NodeIt() { } /// Copy constructor. /// NodeIt(const NodeIt& n) : Node(n) { } /// Invalid constructor \& conversion. /// Initialize the iterator to be invalid. /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. NodeIt(Invalid) { } /// Sets the iterator to the first node. /// Sets the iterator to the first node of \c g. /// NodeIt(const Graph&) { } /// Node -> NodeIt conversion. /// Sets the iterator to the node of \c the graph pointed by /// the trivial iterator. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the first node of the given digraph. /// explicit NodeIt(const Graph&) { } /// Sets the iterator to the given node. /// Sets the iterator to the given node of the given digraph. /// NodeIt(const Graph&, const Node&) { } /// Next node. /// The base type of the edge iterators. /// The base type of the edge iterators. /// /// The edge type of the graph /// This class identifies an edge of the graph. It also serves /// as a base class of the edge iterators, /// thus they will convert to this type. class Edge { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the object to an undefined value. Edge() { } /// Copy constructor. /// Edge(const Edge&) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the object to be invalid. /// \sa Invalid for more details. Edge(Invalid) { } /// Equality operator /// Equality operator. /// /// Two iterators are equal if and only if they point to the /// same object or both are invalid. /// same object or both are \c INVALID. bool operator==(Edge) const { return true; } /// Inequality operator /// \sa operator==(Edge n) /// /// Inequality operator. bool operator!=(Edge) const { return true; } /// Artificial ordering operator. /// To allow the use of graph descriptors as key type in std::map or /// similar associative container we require this. /// /// \note This operator only have to define some strict ordering of /// the items; this order has nothing to do with the iteration /// ordering of the items. /// Artificial ordering operator. /// /// \note This operator only has to define some strict ordering of /// the edges; this order has nothing to do with the iteration /// ordering of the edges. bool operator<(Edge) const { return false; } }; /// This iterator goes through each edge. /// This iterator goes through each edge of a graph. /// Its usage is quite simple, for example you can count the number /// of edges in a graph \c g of type \c Graph as follows: /// Iterator class for the edges. /// This iterator goes through each edge of the graph. /// Its usage is quite simple, for example, you can count the number /// of edges in a graph \c g of type \c %Graph as follows: ///\code /// int count=0; /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. EdgeIt() { } /// Copy constructor. /// EdgeIt(const EdgeIt& e) : Edge(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. EdgeIt(Invalid) { } /// This constructor sets the iterator to the first edge. /// This constructor sets the iterator to the first edge. EdgeIt(const Graph&) { } /// Edge -> EdgeIt conversion /// Sets the iterator to the value of the trivial iterator. /// This feature necessitates that each time we /// iterate the edge-set, the iteration order is the /// same. /// Sets the iterator to the first edge. /// Sets the iterator to the first edge of the given graph. /// explicit EdgeIt(const Graph&) { } /// Sets the iterator to the given edge. /// Sets the iterator to the given edge of the given graph. /// EdgeIt(const Graph&, const Edge&) { } /// Next edge /// Assign the iterator to the next edge. /// EdgeIt& operator++() { return *this; } }; /// \brief This iterator goes trough the incident undirected /// arcs of a node. /// /// This iterator goes trough the incident edges /// of a certain node of a graph. You should assume that the /// loop arcs will be iterated twice. /// /// Its usage is quite simple, for example you can compute the /// degree (i.e. count the number of incident arcs of a node \c n /// in graph \c g of type \c Graph as follows. /// Iterator class for the incident edges of a node. /// This iterator goes trough the incident undirected edges /// of a certain node of a graph. /// Its usage is quite simple, for example, you can compute the /// degree (i.e. the number of incident edges) of a node \c n /// in a graph \c g of type \c %Graph as follows. /// ///\code /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; ///\endcode /// /// \warning Loop edges will be iterated twice. class IncEdgeIt : public Edge { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. IncEdgeIt() { } /// Copy constructor. /// IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. IncEdgeIt(Invalid) { } /// This constructor sets the iterator to first incident arc. /// This constructor set the iterator to the first incident arc of /// the node. /// Sets the iterator to the first incident edge. /// Sets the iterator to the first incident edge of the given node. /// IncEdgeIt(const Graph&, const Node&) { } /// Edge -> IncEdgeIt conversion /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the given edge. /// Sets the iterator to the given edge of the given graph. /// IncEdgeIt(const Graph&, const Edge&) { } /// Next incident arc /// Assign the iterator to the next incident arc /// Next incident edge /// Assign the iterator to the next incident edge /// of the corresponding node. IncEdgeIt& operator++() { return *this; } }; /// The directed arc type. /// The directed arc type. It can be converted to the /// edge or it should be inherited from the undirected /// edge. /// The arc type of the graph /// This class identifies a directed arc of the graph. It also serves /// as a base class of the arc iterators, /// thus they will convert to this type. class Arc { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the object to an undefined value. Arc() { } /// Copy constructor. /// Arc(const Arc&) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the object to be invalid. /// \sa Invalid for more details. Arc(Invalid) { } /// Equality operator /// Equality operator. /// /// Two iterators are equal if and only if they point to the /// same object or both are invalid. /// same object or both are \c INVALID. bool operator==(Arc) const { return true; } /// Inequality operator /// \sa operator==(Arc n) /// /// Inequality operator. bool operator!=(Arc) const { return true; } /// Artificial ordering operator. /// To allow the use of graph descriptors as key type in std::map or /// similar associative container we require this. /// /// \note This operator only have to define some strict ordering of /// the items; this order has nothing to do with the iteration /// ordering of the items. /// Artificial ordering operator. /// /// \note This operator only has to define some strict ordering of /// the arcs; this order has nothing to do with the iteration /// ordering of the arcs. bool operator<(Arc) const { return false; } /// Converison to Edge /// Converison to \c Edge /// Converison to \c Edge. /// operator Edge() const { return Edge(); } }; /// This iterator goes through each directed arc. /// This iterator goes through each arc of a graph. /// Its usage is quite simple, for example you can count the number /// of arcs in a graph \c g of type \c Graph as follows: /// Iterator class for the arcs. /// This iterator goes through each directed arc of the graph. /// Its usage is quite simple, for example, you can count the number /// of arcs in a graph \c g of type \c %Graph as follows: ///\code /// int count=0; /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count; /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count; ///\endcode class ArcIt : public Arc { /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. ArcIt() { } /// Copy constructor. /// ArcIt(const ArcIt& e) : Arc(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. ArcIt(Invalid) { } /// This constructor sets the iterator to the first arc. /// This constructor sets the iterator to the first arc of \c g. ///@param g the graph ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } /// Arc -> ArcIt conversion /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the first arc. /// Sets the iterator to the first arc of the given graph. /// explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } /// Sets the iterator to the given arc. /// Sets the iterator to the given arc of the given graph. /// ArcIt(const Graph&, const Arc&) { } ///Next arc /// Next arc /// Assign the iterator to the next arc. /// ArcIt& operator++() { return *this; } }; /// This iterator goes trough the outgoing directed arcs of a node. /// This iterator goes trough the \e outgoing arcs of a certain node /// of a graph. /// Its usage is quite simple, for example you can count the number /// Iterator class for the outgoing arcs of a node. /// This iterator goes trough the \e outgoing directed arcs of a /// certain node of a graph. /// Its usage is quite simple, for example, you can count the number /// of outgoing arcs of a node \c n /// in graph \c g of type \c Graph as follows. /// in a graph \c g of type \c %Graph as follows. ///\code /// int count=0; /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; ///\endcode class OutArcIt : public Arc { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. OutArcIt() { } /// Copy constructor. /// OutArcIt(const OutArcIt& e) : Arc(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. OutArcIt(Invalid) { } /// This constructor sets the iterator to the first outgoing arc. /// This constructor sets the iterator to the first outgoing arc of /// the node. ///@param n the node ///@param g the graph /// Sets the iterator to the first outgoing arc. /// Sets the iterator to the first outgoing arc of the given node. /// OutArcIt(const Graph& n, const Node& g) { ignore_unused_variable_warning(n); ignore_unused_variable_warning(g); } /// Arc -> OutArcIt conversion /// Sets the iterator to the value of the trivial iterator. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the given arc. /// Sets the iterator to the given arc of the given graph. /// OutArcIt(const Graph&, const Arc&) { } ///Next outgoing arc /// Next outgoing arc /// Assign the iterator to the next }; /// This iterator goes trough the incoming directed arcs of a node. /// This iterator goes trough the \e incoming arcs of a certain node /// of a graph. /// Its usage is quite simple, for example you can count the number /// of outgoing arcs of a node \c n /// in graph \c g of type \c Graph as follows. /// Iterator class for the incoming arcs of a node. /// This iterator goes trough the \e incoming directed arcs of a /// certain node of a graph. /// Its usage is quite simple, for example, you can count the number /// of incoming arcs of a node \c n /// in a graph \c g of type \c %Graph as follows. ///\code /// int count=0; /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count; /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; ///\endcode class InArcIt : public Arc { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. InArcIt() { } /// Copy constructor. /// InArcIt(const InArcIt& e) : Arc(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. InArcIt(Invalid) { } /// This constructor sets the iterator to first incoming arc. /// This constructor set the iterator to the first incoming arc of /// the node. ///@param n the node ///@param g the graph /// Sets the iterator to the first incoming arc. /// Sets the iterator to the first incoming arc of the given node. /// InArcIt(const Graph& g, const Node& n) { ignore_unused_variable_warning(n); ignore_unused_variable_warning(g); } /// Arc -> InArcIt conversion /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the given arc. /// Sets the iterator to the given arc of the given graph. /// InArcIt(const Graph&, const Arc&) { } /// Next incoming arc /// Assign the iterator to the next inarc of the corresponding node. /// /// Assign the iterator to the next /// incoming arc of the corresponding node. InArcIt& operator++() { return *this; } }; /// \brief Reference map of the nodes to type \c T. /// /// Reference map of the nodes to type \c T. /// \brief Standard graph map type for the nodes. /// /// Standard graph map type for the nodes. /// It conforms to the ReferenceMap concept. template class NodeMap : public ReferenceMap public: ///\e NodeMap(const Graph&) { } ///\e /// Constructor explicit NodeMap(const Graph&) { } /// Constructor with given initial value NodeMap(const Graph&, T) { } }; /// \brief Reference map of the arcs to type \c T. /// /// Reference map of the arcs to type \c T. /// \brief Standard graph map type for the arcs. /// /// Standard graph map type for the arcs. /// It conforms to the ReferenceMap concept. template class ArcMap : public ReferenceMap public: ///\e ArcMap(const Graph&) { } ///\e /// Constructor explicit ArcMap(const Graph&) { } /// Constructor with given initial value ArcMap(const Graph&, T) { } private: ///Copy constructor }; /// Reference map of the edges to type \c T. /// Reference map of the edges to type \c T. /// \brief Standard graph map type for the edges. ///