Index: .hgignore
===================================================================
--- .hgignore (revision 610)
+++ .hgignore (revision 944)
@@ -23,4 +23,5 @@
lemon/stamp-h2
doc/Doxyfile
+doc/references.dox
cmake/version.cmake
.dirstamp
Index: .hgtags
===================================================================
--- .hgtags (revision 1004)
+++ .hgtags (revision 1006)
@@ -1,4 +1,2 @@
-06f816565bef381024acd7c15beb74ba407e3546 r1.1
-78b7231f0b2e786f74a9b0dbb345fe8b17fa35f9 r1.1.1
-86a880ba752dd02bfa084223b3cdf1698e5c0830 r1.1.2
-dfdb58f52f0220ccfb6dbedfe2a0be7d99995e0a r1.1.3
+3ed8f7c8bed8f51aecdc8395aa11af2f1fa12d9f r1.2
+ffc2d2559fc916e90c3f000582a2d4761d229d44 r1.2.1
Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt (revision 727)
+++ CMakeLists.txt (revision 791)
@@ -35,4 +35,6 @@
CHECK_TYPE_SIZE("long long" LONG_LONG)
SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
+
+INCLUDE(FindPythonInterp)
ENABLE_TESTING()
Index: INSTALL
===================================================================
--- INSTALL (revision 615)
+++ INSTALL (revision 890)
@@ -174,2 +174,24 @@
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"'.
Index: LICENSE
===================================================================
--- LICENSE (revision 600)
+++ LICENSE (revision 959)
@@ -2,5 +2,5 @@
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).
Index: Makefile.am
===================================================================
--- Makefile.am (revision 799)
+++ Makefile.am (revision 840)
@@ -45,4 +45,5 @@
include doc/Makefile.am
include tools/Makefile.am
+include scripts/Makefile.am
DIST_SUBDIRS = demo
Index: NEWS
===================================================================
--- NEWS (revision 1003)
+++ NEWS (revision 1005)
@@ -1,3 +1,3 @@
-2010-10-21 Version 1.1.3 released
+2010-10-21 Version 1.2.1 released
Bugfix release.
@@ -7,43 +7,87 @@
The target graph is cleared before adding nodes and arcs/edges.
- #356: Fix multiple execution bug in weighted matchings
#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-08 Version 1.1.2 released
-
- Bugfix release.
-
- #317: Fix (and improve) error message in mip_test.cc
- Remove unnecessary OsiCbc dependency
- #250: Fix in pathSource() and pathTarget()
- #322: Distribute LEMONConfig.cmake.in
- #321: Use pathCopy(from,to) instead of copyPath(to,from)
- #330: Bug fix in map_extender.h
- #335: Fix clear() function in ExtendFindEnum
- #337: Use void* as LPX object pointer
- #336: Fix the date field comment of graphToEps() output
- #323: Bug fix in Suurballe
-
-2009-10-03 Version 1.1.1 released
-
- Bugfix release.
-
- #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: Bug fix in Preflow and Circulation
+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
@@ -121,5 +165,5 @@
----: 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
@@ -143,50 +187,50 @@
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)
Index: README
===================================================================
--- README (revision 705)
+++ README (revision 921)
@@ -18,4 +18,8 @@
Copying, distribution and modification conditions and terms.
+NEWS
+
+ News and version history.
+
INSTALL
@@ -34,4 +38,8 @@
Some example programs to make you easier to get familiar with LEMON.
+scripts/
+
+ Scripts that make it easier to develop LEMON.
+
test/
Index: configure.ac
===================================================================
--- configure.ac (revision 727)
+++ configure.ac (revision 840)
@@ -42,4 +42,5 @@
AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
+AC_CHECK_PROG([python_found],[python],[yes],[no])
AC_CHECK_PROG([gs_found],[gs],[yes],[no])
@@ -82,4 +83,19 @@
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.
@@ -128,4 +144,5 @@
echo
echo Build additional tools........ : $enable_tools
+echo Use valgrind for tests........ : $use_valgrind
echo
echo The packace will be installed in
Index: demo/arg_parser_demo.cc
===================================================================
--- demo/arg_parser_demo.cc (revision 463)
+++ demo/arg_parser_demo.cc (revision 956)
@@ -3,5 +3,5 @@
* 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).
@@ -66,7 +66,16 @@
.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
Index: doc/CMakeLists.txt
===================================================================
--- doc/CMakeLists.txt (revision 726)
+++ doc/CMakeLists.txt (revision 943)
@@ -10,5 +10,5 @@
)
-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)
@@ -21,4 +21,5 @@
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
@@ -27,6 +28,8 @@
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}
Index: doc/Doxyfile.in
===================================================================
--- doc/Doxyfile.in (revision 379)
+++ doc/Doxyfile.in (revision 803)
@@ -1,3 +1,3 @@
-# Doxyfile 1.5.7.1
+# Doxyfile 1.5.9
#---------------------------------------------------------------------------
@@ -22,5 +22,4 @@
QT_AUTOBRIEF = NO
MULTILINE_CPP_IS_BRIEF = NO
-DETAILS_AT_TOP = YES
INHERIT_DOCS = NO
SEPARATE_MEMBER_PAGES = NO
@@ -92,5 +91,6 @@
"@abs_top_srcdir@/demo" \
"@abs_top_srcdir@/tools" \
- "@abs_top_srcdir@/test/test_tools.h"
+ "@abs_top_srcdir@/test/test_tools.h" \
+ "@abs_top_builddir@/doc/references.dox"
INPUT_ENCODING = UTF-8
FILE_PATTERNS = *.h \
@@ -224,5 +224,5 @@
SKIP_FUNCTION_MACROS = YES
#---------------------------------------------------------------------------
-# Configuration::additions related to external references
+# Options related to the search engine
#---------------------------------------------------------------------------
TAGFILES = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ "
Index: doc/Makefile.am
===================================================================
--- doc/Makefile.am (revision 720)
+++ doc/Makefile.am (revision 943)
@@ -28,5 +28,7 @@
connected_components.eps \
edge_biconnected_components.eps \
+ matching.eps \
node_biconnected_components.eps \
+ planar.eps \
strongly_connected_components.eps
@@ -67,5 +69,17 @@
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; \
Index: doc/groups.dox
===================================================================
--- doc/groups.dox (revision 844)
+++ doc/groups.dox (revision 963)
@@ -3,5 +3,5 @@
* 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).
@@ -239,5 +239,26 @@
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"
*/
@@ -252,4 +273,18 @@
/**
+@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
@@ -266,5 +301,6 @@
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.
*/
@@ -274,8 +310,13 @@
\brief Algorithms for finding shortest paths.
-This group contains the algorithms for finding shortest paths in digraphs.
-
- - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
- source node when all arc lengths are non-negative.
+This group contains the algorithms for finding shortest paths in digraphs
+\ref clrs01algorithms.
+
+ - \ref Dijkstra algorithm for finding shortest paths from a source node
+ when all arc lengths are non-negative.
+ - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
+ from a source node 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.
@@ -283,4 +324,13 @@
/**
+@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
@@ -288,5 +338,5 @@
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
@@ -302,10 +352,10 @@
\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
-\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
-Tarjan for solving this problem. 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
+\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.
@@ -320,10 +370,23 @@
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".
-
-\ref NetworkSimplex is an efficient implementation of the primal Network
-Simplex algorithm for finding minimum cost flows. It also provides dual
-solution (node potentials), if an optimal flow is found.
+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 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,
+but in special cases other algorithms could be faster.
+For example, if the total supply and/or capacities are rather small,
+CapacityScaling is usually the fastest algorithm (without effective scaling).
*/
@@ -343,5 +406,5 @@
\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:
@@ -357,13 +420,38 @@
/**
-@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 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.
*/
@@ -373,10 +461,12 @@
\brief Algorithms for finding matchings in graphs and bipartite graphs.
-This group contains the algorithms for calculating matchings in graphs.
-The general matching problem is finding a subset of the edges for which
-each node has at most one incident edge.
+This group contains the algorithms for calculating
+matchings in graphs and bipartite graphs. The general matching problem is
+finding a subset of the edges for which each node has at most one incident
+edge.
There are several different algorithms for calculate matchings in
-graphs. The goal of the matching optimization
+graphs. The matching problems in bipartite graphs are generally
+easier than in general graphs. The goal of the matching optimization
can be finding maximum cardinality, maximum weight or minimum cost
matching. The search can be constrained to find perfect or
@@ -391,16 +481,38 @@
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
*/
@@ -424,11 +536,14 @@
/**
-@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.
+\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.
*/
@@ -503,5 +618,5 @@
/**
-@defgroup dimacs_group DIMACS format
+@defgroup dimacs_group DIMACS Format
@ingroup io_group
\brief Read and write files in DIMACS format
@@ -552,6 +667,6 @@
\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.
*/
@@ -565,4 +680,13 @@
/**
+@defgroup tools Standalone Utility Applications
+
+Some utility applications are listed here.
+
+The standard compilation procedure (./configure;make) will compile
+them, as well.
+*/
+
+/**
\anchor demoprograms
@@ -576,12 +700,3 @@
*/
-/**
-@defgroup tools Standalone Utility Applications
-
-Some utility applications are listed here.
-
-The standard compilation procedure (./configure;make) will compile
-them, as well.
-*/
-
}
Index: doc/images/matching.eps
===================================================================
--- doc/images/matching.eps (revision 943)
+++ doc/images/matching.eps (revision 943)
@@ -0,0 +1,130 @@
+%!PS-Adobe-2.0 EPSF-2.0
+%%Creator: LEMON, graphToEps()
+%%CreationDate: Sun Mar 14 09:08:34 2010
+%%BoundingBox: -353 -264 559 292
+%%EndComments
+/lb { setlinewidth setrgbcolor newpath moveto
+ 4 2 roll 1 index 1 index curveto stroke } bind def
+/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
+/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
+/sq { newpath 2 index 1 index add 2 index 2 index add moveto
+ 2 index 1 index sub 2 index 2 index add lineto
+ 2 index 1 index sub 2 index 2 index sub lineto
+ 2 index 1 index add 2 index 2 index sub lineto
+ closepath pop pop pop} bind def
+/di { newpath 2 index 1 index add 2 index moveto
+ 2 index 2 index 2 index add lineto
+ 2 index 1 index sub 2 index lineto
+ 2 index 2 index 2 index sub lineto
+ closepath pop pop pop} bind def
+/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
+ setrgbcolor 1.1 div sq fill
+ } bind def
+/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
+ setrgbcolor 1.1 div di fill
+ } bind def
+/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+ newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
+ lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
+ 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
+ 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/nmale {
+ 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+ newpath 5 index 5 index moveto
+ 5 index 4 index 1 mul 1.5 mul add
+ 5 index 5 index 3 sqrt 1.5 mul mul add
+ 1 index 1 index lineto
+ 1 index 1 index 7 index sub moveto
+ 1 index 1 index lineto
+ exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
+ stroke
+ 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/arrl 1 def
+/arrw 0.3 def
+/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
+/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
+ /w exch def /len exch def
+ newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
+ len w sub arrl sub dx dy lrl
+ arrw dy dx neg lrl
+ dx arrl w add mul dy w 2 div arrw add mul sub
+ dy arrl w add mul dx w 2 div arrw add mul add rlineto
+ dx arrl w add mul neg dy w 2 div arrw add mul sub
+ dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
+ arrw dy dx neg lrl
+ len w sub arrl sub neg dx dy lrl
+ closepath fill } bind def
+/cshow { 2 index 2 index moveto dup stringwidth pop
+ neg 2 div fosi .35 mul neg rmoveto show pop pop} def
+
+gsave
+%Arcs:
+gsave
+140.321 266.249 -327.729 150.06 0 0 0 4.99223 l
+82.1207 -238.726 -245.288 -110.743 0 0 0 4.99223 l
+336.635 -229.036 533.603 13.109 0 0 0 4.99223 l
+53.8598 -45.8071 -245.288 -110.743 0 0 0 4.99223 l
+-75.5617 118.579 -327.729 150.06 0 0 0 4.99223 l
+-327.729 150.06 -245.288 -110.743 1 0 0 11.9813 l
+533.603 13.109 218.184 -84.2955 0 0 0 4.99223 l
+39.87 175.035 141.163 67.2575 0 0 0 4.99223 l
+53.8598 -45.8071 -75.5617 118.579 0 0 0 4.99223 l
+-102.406 -141.267 82.1207 -238.726 0 0 0 4.99223 l
+399.144 166.894 533.603 13.109 1 0 0 11.9813 l
+39.87 175.035 140.321 266.249 1 0 0 11.9813 l
+399.144 166.894 140.321 266.249 0 0 0 4.99223 l
+399.144 166.894 141.163 67.2575 0 0 0 4.99223 l
+53.8598 -45.8071 204.765 -173.77 0 0 0 4.99223 l
+82.1207 -238.726 204.765 -173.77 0 0 0 4.99223 l
+258.227 61.658 399.144 166.894 0 0 0 4.99223 l
+53.8598 -45.8071 -102.406 -141.267 1 0 0 11.9813 l
+175.073 -37.4477 141.163 67.2575 0 0 0 4.99223 l
+258.227 61.658 380 0 0 0 0 4.99223 l
+34.6739 40.8267 -75.5617 118.579 1 0 0 11.9813 l
+380 0 533.603 13.109 0 0 0 4.99223 l
+175.073 -37.4477 380 0 0 0 0 4.99223 l
+218.184 -84.2955 204.765 -173.77 0 0 0 4.99223 l
+53.8598 -45.8071 34.6739 40.8267 0 0 0 4.99223 l
+167.905 -213.988 82.1207 -238.726 1 0 0 11.9813 l
+336.635 -229.036 204.765 -173.77 1 0 0 11.9813 l
+336.635 -229.036 167.905 -213.988 0 0 0 4.99223 l
+329.08 -26.3098 218.184 -84.2955 0 0 0 4.99223 l
+39.87 175.035 -75.5617 118.579 0 0 0 4.99223 l
+53.8598 -45.8071 175.073 -37.4477 0 0 0 4.99223 l
+34.6739 40.8267 141.163 67.2575 0 0 0 4.99223 l
+258.227 61.658 141.163 67.2575 1 0 0 11.9813 l
+175.073 -37.4477 218.184 -84.2955 1 0 0 11.9813 l
+380 0 329.08 -26.3098 1 0 0 11.9813 l
+grestore
+%Nodes:
+gsave
+-245.288 -110.743 14.9767 1 1 1 nc
+204.765 -173.77 14.9767 1 1 1 nc
+-327.729 150.06 14.9767 1 1 1 nc
+-75.5617 118.579 14.9767 1 1 1 nc
+218.184 -84.2955 14.9767 1 1 1 nc
+140.321 266.249 14.9767 1 1 1 nc
+141.163 67.2575 14.9767 1 1 1 nc
+82.1207 -238.726 14.9767 1 1 1 nc
+329.08 -26.3098 14.9767 1 1 1 nc
+-102.406 -141.267 14.9767 1 1 1 nc
+533.603 13.109 14.9767 1 1 1 nc
+167.905 -213.988 14.9767 1 1 1 nc
+336.635 -229.036 14.9767 1 1 1 nc
+380 0 14.9767 1 1 1 nc
+399.144 166.894 14.9767 1 1 1 nc
+34.6739 40.8267 14.9767 1 1 1 nc
+39.87 175.035 14.9767 1 1 1 nc
+175.073 -37.4477 14.9767 1 1 1 nc
+53.8598 -45.8071 14.9767 1 1 1 nc
+258.227 61.658 14.9767 1 1 1 nc
+grestore
+grestore
+showpage
Index: doc/images/planar.eps
===================================================================
--- doc/images/planar.eps (revision 895)
+++ doc/images/planar.eps (revision 895)
@@ -0,0 +1,181 @@
+%!PS-Adobe-2.0 EPSF-2.0
+%%Creator: LEMON, graphToEps()
+%%CreationDate: Fri Oct 19 18:32:32 2007
+%%BoundingBox: 0 0 596 842
+%%DocumentPaperSizes: a4
+%%EndComments
+/lb { setlinewidth setrgbcolor newpath moveto
+ 4 2 roll 1 index 1 index curveto stroke } bind def
+/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
+/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
+/sq { newpath 2 index 1 index add 2 index 2 index add moveto
+ 2 index 1 index sub 2 index 2 index add lineto
+ 2 index 1 index sub 2 index 2 index sub lineto
+ 2 index 1 index add 2 index 2 index sub lineto
+ closepath pop pop pop} bind def
+/di { newpath 2 index 1 index add 2 index moveto
+ 2 index 2 index 2 index add lineto
+ 2 index 1 index sub 2 index lineto
+ 2 index 2 index 2 index sub lineto
+ closepath pop pop pop} bind def
+/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
+ setrgbcolor 1.1 div sq fill
+ } bind def
+/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
+ setrgbcolor 1.1 div di fill
+ } bind def
+/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+ newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
+ lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
+ 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
+ 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/nmale {
+ 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+ newpath 5 index 5 index moveto
+ 5 index 4 index 1 mul 1.5 mul add
+ 5 index 5 index 3 sqrt 1.5 mul mul add
+ 1 index 1 index lineto
+ 1 index 1 index 7 index sub moveto
+ 1 index 1 index lineto
+ exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
+ stroke
+ 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/arrl 1 def
+/arrw 0.3 def
+/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
+/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
+ /w exch def /len exch def
+ newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
+ len w sub arrl sub dx dy lrl
+ arrw dy dx neg lrl
+ dx arrl w add mul dy w 2 div arrw add mul sub
+ dy arrl w add mul dx w 2 div arrw add mul add rlineto
+ dx arrl w add mul neg dy w 2 div arrw add mul sub
+ dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
+ arrw dy dx neg lrl
+ len w sub arrl sub neg dx dy lrl
+ closepath fill } bind def
+/cshow { 2 index 2 index moveto dup stringwidth pop
+ neg 2 div fosi .35 mul neg rmoveto show pop pop} def
+
+gsave
+15 138.307 translate
+12.7843 dup scale
+90 rotate
+0.608112 -43.6081 translate
+%Edges:
+gsave
+9 31 9.5 30.5 10 30 0 0 0 0.091217 lb
+9 31 5.5 34.5 2 38 0 0 0 0.091217 lb
+9 31 25.5 16 42 1 0 0 0 0.091217 lb
+3 40 23 20.5 43 1 0 0 0 0.091217 lb
+3 40 22.5 20.5 42 1 0 0 0 0.091217 lb
+3 40 2.5 40.5 2 41 0 0 0 0.091217 lb
+13 25 10.5 24.5 8 24 0 0 0 0.091217 lb
+13 25 12 27 11 29 0 0 0 0.091217 lb
+3 4 2.5 3 2 2 0 0 0 0.091217 lb
+3 4 4.5 3 6 2 0 0 0 0.091217 lb
+6 25 7 24.5 8 24 0 0 0 0.091217 lb
+6 25 6 24.5 6 24 0 0 0 0.091217 lb
+34 2 33.5 2 33 2 0 0 0 0.091217 lb
+34 2 35 2 36 2 0 0 0 0.091217 lb
+6 8 16 9 26 10 0 0 0 0.091217 lb
+6 8 6 10.5 6 13 0 0 0 0.091217 lb
+6 8 6 7.5 6 7 0 0 0 0.091217 lb
+26 10 27.5 8.5 29 7 0 0 0 0.091217 lb
+26 10 27.5 9 29 8 0 0 0 0.091217 lb
+10 30 10.5 29.5 11 29 0 0 0 0.091217 lb
+8 24 7 23.5 6 23 0 0 0 0.091217 lb
+8 24 8 24.5 8 25 0 0 0 0.091217 lb
+33 2 32.5 2 32 2 0 0 0 0.091217 lb
+29 7 17.5 7 6 7 0 0 0 0.091217 lb
+2 2 1.5 22 1 42 0 0 0 0.091217 lb
+2 2 3.5 2 5 2 0 0 0 0.091217 lb
+21 15 13.5 14.5 6 14 0 0 0 0.091217 lb
+21 15 21 15.5 21 16 0 0 0 0.091217 lb
+1 42 0.5 42.5 0 43 0 0 0 0.091217 lb
+1 42 1.5 41.5 2 41 0 0 0 0.091217 lb
+6 15 6 15.5 6 16 0 0 0 0.091217 lb
+6 15 6 14.5 6 14 0 0 0 0.091217 lb
+43 1 22 0.5 1 0 0 0 0 0.091217 lb
+31 2 18.5 2 6 2 0 0 0 0.091217 lb
+31 2 31.5 2 32 2 0 0 0 0.091217 lb
+6 24 6 23.5 6 23 0 0 0 0.091217 lb
+6 16 6 16.5 6 17 0 0 0 0.091217 lb
+6 23 6 20 6 17 0 0 0 0.091217 lb
+6 2 5.5 2 5 2 0 0 0 0.091217 lb
+6 2 6 4.5 6 7 0 0 0 0.091217 lb
+0 43 0.5 21.5 1 0 0 0 0 0.091217 lb
+1 1 19.5 1.5 38 2 0 0 0 0.091217 lb
+1 1 1 0.5 1 0 0 0 0 0.091217 lb
+2 38 5.5 31.5 9 25 0 0 0 0.091217 lb
+25 13 15.5 13 6 13 0 0 0 0.091217 lb
+25 13 15.5 13.5 6 14 0 0 0 0.091217 lb
+8 25 8.5 25 9 25 0 0 0 0.091217 lb
+11 29 24.5 15.5 38 2 0 0 0 0.091217 lb
+6 17 11.5 18 17 19 0 0 0 0.091217 lb
+16 23 26.5 12.5 37 2 0 0 0 0.091217 lb
+16 23 18.5 19.5 21 16 0 0 0 0.091217 lb
+36 2 36.5 2 37 2 0 0 0 0.091217 lb
+36 2 32.5 5 29 8 0 0 0 0.091217 lb
+6 13 6 13.5 6 14 0 0 0 0.091217 lb
+37 2 37.5 2 38 2 0 0 0 0.091217 lb
+21 16 19 17.5 17 19 0 0 0 0.091217 lb
+grestore
+%Nodes:
+gsave
+29 8 0.304556 1 1 1 nc
+2 41 0.304556 1 1 1 nc
+6 7 0.304556 1 1 1 nc
+5 2 0.304556 1 1 1 nc
+17 19 0.304556 1 1 1 nc
+21 16 0.304556 1 1 1 nc
+1 0 0.304556 1 1 1 nc
+9 25 0.304556 1 1 1 nc
+6 14 0.304556 1 1 1 nc
+42 1 0.304556 1 1 1 nc
+38 2 0.304556 1 1 1 nc
+37 2 0.304556 1 1 1 nc
+6 13 0.304556 1 1 1 nc
+36 2 0.304556 1 1 1 nc
+16 23 0.304556 1 1 1 nc
+6 17 0.304556 1 1 1 nc
+11 29 0.304556 1 1 1 nc
+8 25 0.304556 1 1 1 nc
+32 2 0.304556 1 1 1 nc
+25 13 0.304556 1 1 1 nc
+2 38 0.304556 1 1 1 nc
+1 1 0.304556 1 1 1 nc
+0 43 0.304556 1 1 1 nc
+6 2 0.304556 1 1 1 nc
+6 23 0.304556 1 1 1 nc
+6 16 0.304556 1 1 1 nc
+6 24 0.304556 1 1 1 nc
+31 2 0.304556 1 1 1 nc
+43 1 0.304556 1 1 1 nc
+6 15 0.304556 1 1 1 nc
+1 42 0.304556 1 1 1 nc
+21 15 0.304556 1 1 1 nc
+2 2 0.304556 1 1 1 nc
+29 7 0.304556 1 1 1 nc
+33 2 0.304556 1 1 1 nc
+8 24 0.304556 1 1 1 nc
+10 30 0.304556 1 1 1 nc
+26 10 0.304556 1 1 1 nc
+6 8 0.304556 1 1 1 nc
+34 2 0.304556 1 1 1 nc
+6 25 0.304556 1 1 1 nc
+3 4 0.304556 1 1 1 nc
+13 25 0.304556 1 1 1 nc
+3 40 0.304556 1 1 1 nc
+9 31 0.304556 1 1 1 nc
+grestore
+grestore
+showpage
Index: doc/mainpage.dox
===================================================================
--- doc/mainpage.dox (revision 705)
+++ doc/mainpage.dox (revision 956)
@@ -3,5 +3,5 @@
* 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).
@@ -22,12 +22,9 @@
\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.
@@ -39,8 +36,21 @@
-\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
Index: doc/min_cost_flow.dox
===================================================================
--- doc/min_cost_flow.dox (revision 710)
+++ doc/min_cost_flow.dox (revision 956)
@@ -3,5 +3,5 @@
* 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).
@@ -27,5 +27,5 @@
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$,
@@ -79,8 +79,8 @@
- 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.
@@ -120,5 +120,5 @@
\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
@@ -146,5 +146,5 @@
- 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$.
Index: doc/references.bib
===================================================================
--- doc/references.bib (revision 802)
+++ doc/references.bib (revision 802)
@@ -0,0 +1,301 @@
+%%%%% Defining LEMON %%%%%
+
+@misc{lemon,
+ key = {LEMON},
+ title = {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and
+ {O}ptimization in {N}etworks},
+ howpublished = {\url{http://lemon.cs.elte.hu/}},
+ year = 2009
+}
+
+@misc{egres,
+ key = {EGRES},
+ title = {{EGRES} -- {E}gerv{\'a}ry {R}esearch {G}roup on
+ {C}ombinatorial {O}ptimization},
+ url = {http://www.cs.elte.hu/egres/}
+}
+
+@misc{coinor,
+ key = {COIN-OR},
+ title = {{COIN-OR} -- {C}omputational {I}nfrastructure for
+ {O}perations {R}esearch},
+ url = {http://www.coin-or.org/}
+}
+
+
+%%%%% Other libraries %%%%%%
+
+@misc{boost,
+ key = {Boost},
+ title = {{B}oost {C++} {L}ibraries},
+ url = {http://www.boost.org/}
+}
+
+@book{bglbook,
+ author = {Jeremy G. Siek and Lee-Quan Lee and Andrew
+ Lumsdaine},
+ title = {The Boost Graph Library: User Guide and Reference
+ Manual},
+ publisher = {Addison-Wesley},
+ year = 2002
+}
+
+@misc{leda,
+ key = {LEDA},
+ title = {{LEDA} -- {L}ibrary of {E}fficient {D}ata {T}ypes and
+ {A}lgorithms},
+ url = {http://www.algorithmic-solutions.com/}
+}
+
+@book{ledabook,
+ author = {Kurt Mehlhorn and Stefan N{\"a}her},
+ title = {{LEDA}: {A} platform for combinatorial and geometric
+ computing},
+ isbn = {0-521-56329-1},
+ publisher = {Cambridge University Press},
+ address = {New York, NY, USA},
+ year = 1999
+}
+
+
+%%%%% Tools that LEMON depends on %%%%%
+
+@misc{cmake,
+ key = {CMake},
+ title = {{CMake} -- {C}ross {P}latform {M}ake},
+ url = {http://www.cmake.org/}
+}
+
+@misc{doxygen,
+ key = {Doxygen},
+ title = {{Doxygen} -- {S}ource code documentation generator
+ tool},
+ url = {http://www.doxygen.org/}
+}
+
+
+%%%%% LP/MIP libraries %%%%%
+
+@misc{glpk,
+ key = {GLPK},
+ title = {{GLPK} -- {GNU} {L}inear {P}rogramming {K}it},
+ url = {http://www.gnu.org/software/glpk/}
+}
+
+@misc{clp,
+ key = {Clp},
+ title = {{Clp} -- {Coin-Or} {L}inear {P}rogramming},
+ url = {http://projects.coin-or.org/Clp/}
+}
+
+@misc{cbc,
+ key = {Cbc},
+ title = {{Cbc} -- {Coin-Or} {B}ranch and {C}ut},
+ url = {http://projects.coin-or.org/Cbc/}
+}
+
+@misc{cplex,
+ key = {CPLEX},
+ title = {{ILOG} {CPLEX}},
+ url = {http://www.ilog.com/}
+}
+
+@misc{soplex,
+ key = {SoPlex},
+ title = {{SoPlex} -- {T}he {S}equential {O}bject-{O}riented
+ {S}implex},
+ url = {http://soplex.zib.de/}
+}
+
+
+%%%%% General books %%%%%
+
+@book{amo93networkflows,
+ author = {Ravindra K. Ahuja and Thomas L. Magnanti and James
+ B. Orlin},
+ title = {Network Flows: Theory, Algorithms, and Applications},
+ publisher = {Prentice-Hall, Inc.},
+ year = 1993,
+ month = feb,
+ isbn = {978-0136175490}
+}
+
+@book{schrijver03combinatorial,
+ author = {Alexander Schrijver},
+ title = {Combinatorial Optimization: Polyhedra and Efficiency},
+ publisher = {Springer-Verlag},
+ year = 2003,
+ isbn = {978-3540443896}
+}
+
+@book{clrs01algorithms,
+ author = {Thomas H. Cormen and Charles E. Leiserson and Ronald
+ L. Rivest and Clifford Stein},
+ title = {Introduction to Algorithms},
+ publisher = {The MIT Press},
+ year = 2001,
+ edition = {2nd}
+}
+
+@book{stroustrup00cpp,
+ author = {Bjarne Stroustrup},
+ title = {The C++ Programming Language},
+ edition = {3rd},
+ publisher = {Addison-Wesley Professional},
+ isbn = 0201700735,
+ month = {February},
+ year = 2000
+}
+
+
+%%%%% Maximum flow algorithms %%%%%
+
+@article{edmondskarp72theoretical,
+ author = {Jack Edmonds and Richard M. Karp},
+ title = {Theoretical improvements in algorithmic efficiency
+ for network flow problems},
+ journal = {Journal of the ACM},
+ year = 1972,
+ volume = 19,
+ number = 2,
+ pages = {248-264}
+}
+
+@article{goldberg88newapproach,
+ author = {Andrew V. Goldberg and Robert E. Tarjan},
+ title = {A new approach to the maximum flow problem},
+ journal = {Journal of the ACM},
+ year = 1988,
+ volume = 35,
+ number = 4,
+ pages = {921-940}
+}
+
+@article{dinic70algorithm,
+ author = {E. A. Dinic},
+ title = {Algorithm for solution of a problem of maximum flow
+ in a network with power estimation},
+ journal = {Soviet Math. Doklady},
+ year = 1970,
+ volume = 11,
+ pages = {1277-1280}
+}
+
+@article{goldberg08partial,
+ author = {Andrew V. Goldberg},
+ title = {The Partial Augment-Relabel Algorithm for the
+ Maximum Flow Problem},
+ journal = {16th Annual European Symposium on Algorithms},
+ year = 2008,
+ pages = {466-477}
+}
+
+@article{sleator83dynamic,
+ author = {Daniel D. Sleator and Robert E. Tarjan},
+ title = {A data structure for dynamic trees},
+ journal = {Journal of Computer and System Sciences},
+ year = 1983,
+ volume = 26,
+ number = 3,
+ pages = {362-391}
+}
+
+
+%%%%% Minimum mean cycle algorithms %%%%%
+
+@article{karp78characterization,
+ author = {Richard M. Karp},
+ title = {A characterization of the minimum cycle mean in a
+ digraph},
+ journal = {Discrete Math.},
+ year = 1978,
+ volume = 23,
+ pages = {309-311}
+}
+
+@article{dasdan98minmeancycle,
+ author = {Ali Dasdan and Rajesh K. Gupta},
+ title = {Faster Maximum and Minimum Mean Cycle Alogrithms for
+ System Performance Analysis},
+ journal = {IEEE Transactions on Computer-Aided Design of
+ Integrated Circuits and Systems},
+ year = 1998,
+ volume = 17,
+ number = 10,
+ pages = {889-899}
+}
+
+
+%%%%% Minimum cost flow algorithms %%%%%
+
+@article{klein67primal,
+ author = {Morton Klein},
+ title = {A primal method for minimal cost flows with
+ applications to the assignment and transportation
+ problems},
+ journal = {Management Science},
+ year = 1967,
+ volume = 14,
+ pages = {205-220}
+}
+
+@article{goldberg89cyclecanceling,
+ author = {Andrew V. Goldberg and Robert E. Tarjan},
+ title = {Finding minimum-cost circulations by canceling
+ negative cycles},
+ journal = {Journal of the ACM},
+ year = 1989,
+ volume = 36,
+ number = 4,
+ pages = {873-886}
+}
+
+@article{goldberg90approximation,
+ author = {Andrew V. Goldberg and Robert E. Tarjan},
+ title = {Finding Minimum-Cost Circulations by Successive
+ Approximation},
+ journal = {Mathematics of Operations Research},
+ year = 1990,
+ volume = 15,
+ number = 3,
+ pages = {430-466}
+}
+
+@article{goldberg97efficient,
+ author = {Andrew V. Goldberg},
+ title = {An Efficient Implementation of a Scaling
+ Minimum-Cost Flow Algorithm},
+ journal = {Journal of Algorithms},
+ year = 1997,
+ volume = 22,
+ number = 1,
+ pages = {1-29}
+}
+
+@article{bunnagel98efficient,
+ author = {Ursula B{\"u}nnagel and Bernhard Korte and Jens
+ Vygen},
+ title = {Efficient implementation of the {G}oldberg-{T}arjan
+ minimum-cost flow algorithm},
+ journal = {Optimization Methods and Software},
+ year = 1998,
+ volume = 10,
+ pages = {157-174}
+}
+
+@book{dantzig63linearprog,
+ author = {George B. Dantzig},
+ title = {Linear Programming and Extensions},
+ publisher = {Princeton University Press},
+ year = 1963
+}
+
+@mastersthesis{kellyoneill91netsimplex,
+ author = {Damian J. Kelly and Garrett M. O'Neill},
+ title = {The Minimum Cost Flow Problem and The Network
+ Simplex Method},
+ school = {University College},
+ address = {Dublin, Ireland},
+ year = 1991,
+ month = sep,
+}
Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am (revision 913)
+++ lemon/Makefile.am (revision 953)
@@ -58,6 +58,10 @@
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 \
@@ -66,8 +70,11 @@
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 \
@@ -77,4 +84,6 @@
lemon/error.h \
lemon/euler.h \
+ lemon/fib_heap.h \
+ lemon/fractional_matching.h \
lemon/full_graph.h \
lemon/glpk.h \
@@ -82,5 +91,8 @@
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 \
@@ -97,10 +109,15 @@
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/random.h \
lemon/smart_graph.h \
lemon/soplex.h \
+ lemon/static_graph.h \
lemon/suurballe.h \
lemon/time_measure.h \
Index: lemon/adaptors.h
===================================================================
--- lemon/adaptors.h (revision 703)
+++ lemon/adaptors.h (revision 956)
@@ -3,5 +3,5 @@
* 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).
@@ -361,4 +361,7 @@
/// parameter is set to be \c const.
///
+ /// This class provides item counting in the same time as the adapted
+ /// digraph structure.
+ ///
/// \tparam DGR The type of the adapted digraph.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -419,5 +422,5 @@
Parent::initialize(digraph);
_node_filter = &node_filter;
- _arc_filter = &arc_filter;
+ _arc_filter = &arc_filter;
}
@@ -506,9 +509,9 @@
template
- class NodeMap
- : public SubMapExtender,
- LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> {
+ class NodeMap
+ : public SubMapExtender,
+ LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> {
typedef SubMapExtender,
- LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent;
+ LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent;
public:
@@ -533,7 +536,7 @@
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
- LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> {
+ LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> {
typedef SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> Parent;
@@ -580,5 +583,5 @@
Parent::initialize(digraph);
_node_filter = &node_filter;
- _arc_filter = &arc_filter;
+ _arc_filter = &arc_filter;
}
@@ -649,8 +652,8 @@
template
- class NodeMap
+ class NodeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent;
@@ -676,5 +679,5 @@
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> {
@@ -719,4 +722,6 @@
/// by adding or removing nodes or arcs, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides only linear time counting for nodes and arcs.
///
/// \tparam DGR The type of the adapted digraph.
@@ -1017,8 +1022,8 @@
template
- class NodeMap
+ class NodeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent;
@@ -1044,8 +1049,8 @@
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent;
@@ -1071,8 +1076,8 @@
template
- class EdgeMap
+ class EdgeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent;
@@ -1113,6 +1118,6 @@
NF* _node_filter;
EF* _edge_filter;
- SubGraphBase()
- : Parent(), _node_filter(0), _edge_filter(0) { }
+ SubGraphBase()
+ : Parent(), _node_filter(0), _edge_filter(0) { }
void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
@@ -1215,8 +1220,8 @@
template
- class NodeMap
+ class NodeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent;
@@ -1242,8 +1247,8 @@
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent;
@@ -1269,9 +1274,9 @@
template
- class EdgeMap
+ class EdgeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> {
- typedef SubMapExtender,
- LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent;
+ typedef SubMapExtender,
+ LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent;
public:
@@ -1314,4 +1319,6 @@
/// by adding or removing nodes or edges, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides only linear time counting for nodes, edges and arcs.
///
/// \tparam GR The type of the adapted graph.
@@ -1471,4 +1478,6 @@
/// by adding or removing nodes or arcs/edges, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides only linear time item counting.
///
/// \tparam GR The type of the adapted digraph or graph.
@@ -1496,5 +1505,5 @@
#endif
typedef DigraphAdaptorExtender<
- SubDigraphBase >,
+ SubDigraphBase >,
true> > Parent;
@@ -1517,5 +1526,5 @@
/// Creates a subgraph for the given digraph or graph with the
/// given node filter map.
- FilterNodes(GR& graph, NF& node_filter)
+ FilterNodes(GR& graph, NF& node_filter)
: Parent(), const_true_map()
{
@@ -1555,9 +1564,9 @@
typename enable_if >::type> :
public GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
true> > {
typedef GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
true> > Parent;
@@ -1619,4 +1628,6 @@
/// by adding or removing nodes or arcs, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides only linear time counting for nodes and arcs.
///
/// \tparam DGR The type of the adapted digraph.
@@ -1643,5 +1654,5 @@
#endif
typedef DigraphAdaptorExtender<
- SubDigraphBase >,
+ SubDigraphBase >,
AF, false> > Parent;
@@ -1729,4 +1740,6 @@
/// by adding or removing nodes or edges, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides only linear time counting for nodes, edges and arcs.
///
/// \tparam GR The type of the adapted graph.
@@ -1749,9 +1762,9 @@
class FilterEdges :
public GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
EF, false> > {
#endif
typedef GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
EF, false> > Parent;
@@ -1778,5 +1791,5 @@
/// Creates a subgraph for the given graph with the given edge
/// filter map.
- FilterEdges(GR& graph, EF& edge_filter)
+ FilterEdges(GR& graph, EF& edge_filter)
: Parent(), const_true_map() {
Parent::initialize(graph, const_true_map, edge_filter);
@@ -1846,5 +1859,5 @@
bool _forward;
- Arc(const Edge& edge, bool forward)
+ Arc(const Edge& edge, bool forward)
: _edge(edge), _forward(forward) {}
@@ -2086,5 +2099,5 @@
ArcMapBase(const UndirectorBase& adaptor, const V& value)
- : _forward(*adaptor._digraph, value),
+ : _forward(*adaptor._digraph, value),
_backward(*adaptor._digraph, value) {}
@@ -2204,5 +2217,5 @@
typedef typename ItemSetTraits::ItemNotifier EdgeNotifier;
EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
-
+
typedef EdgeNotifier ArcNotifier;
ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
@@ -2232,4 +2245,7 @@
/// by adding or removing nodes or edges, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides item counting in the same time as the adapted
+ /// digraph structure.
///
/// \tparam DGR The type of the adapted digraph.
@@ -2535,4 +2551,7 @@
/// by adding or removing nodes or arcs, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides item counting in the same time as the adapted
+ /// graph structure.
///
/// \tparam GR The type of the adapted graph.
@@ -2679,4 +2698,6 @@
/// This class conforms to the \ref concepts::Digraph "Digraph" concept.
///
+ /// This class provides only linear time counting for nodes and arcs.
+ ///
/// \tparam DGR The type of the adapted digraph.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -2708,5 +2729,5 @@
typename FM = CM,
typename TL = Tolerance >
- class ResidualDigraph
+ class ResidualDigraph
: public SubDigraph<
Undirector,
@@ -2765,5 +2786,5 @@
ResidualDigraph(const DGR& digraph, const CM& capacity,
FM& flow, const TL& tolerance = Tolerance())
- : Parent(), _capacity(&capacity), _flow(&flow),
+ : Parent(), _capacity(&capacity), _flow(&flow),
_graph(digraph), _node_filter(),
_forward_filter(capacity, flow, tolerance),
@@ -2847,5 +2868,5 @@
/// Constructor
- ResidualCapacity(const ResidualDigraph& adaptor)
+ ResidualCapacity(const ResidualDigraph& adaptor)
: _adaptor(&adaptor) {}
@@ -3326,4 +3347,7 @@
/// in the adaptor.
///
+ /// This class provides item counting in the same time as the adapted
+ /// digraph structure.
+ ///
/// \tparam DGR The type of the adapted digraph.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -3424,5 +3448,5 @@
/// to get a node map of the split digraph.
/// Its value type is inherited from the first node map type (\c IN).
- /// \tparam IN The type of the node map for the in-nodes.
+ /// \tparam IN The type of the node map for the in-nodes.
/// \tparam OUT The type of the node map for the out-nodes.
template
Index: lemon/arg_parser.cc
===================================================================
--- lemon/arg_parser.cc (revision 463)
+++ lemon/arg_parser.cc (revision 956)
@@ -3,5 +3,5 @@
* 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).
@@ -21,12 +21,21 @@
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");
@@ -343,5 +352,5 @@
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);
}
@@ -352,5 +361,5 @@
std::cerr << "\nType '" << _command_name <<
" --help' to obtain a short summary on the usage.\n\n";
- exit(1);
+ _terminate(ArgParserException::UNKNOWN_OPT);
}
@@ -415,5 +424,5 @@
std::cerr << "\nType '" << _command_name <<
" --help' to obtain a short summary on the usage.\n\n";
- exit(1);
+ _terminate(ArgParserException::INVALID_OPT);
}
}
Index: lemon/arg_parser.h
===================================================================
--- lemon/arg_parser.h (revision 463)
+++ lemon/arg_parser.h (revision 959)
@@ -3,5 +3,5 @@
* 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).
@@ -35,4 +35,49 @@
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
@@ -116,4 +161,8 @@
const std::string &help,
void (*func)(void *),void *data);
+
+ bool _exit_on_problems;
+
+ void _terminate(ArgParserException::Reason reason) const;
public:
@@ -381,4 +430,9 @@
const std::vector &files() const { return _file_args; }
+ ///Throw instead of exit in case of problems
+ void throwOnProblems()
+ {
+ _exit_on_problems=false;
+ }
};
}
Index: lemon/bellman_ford.h
===================================================================
--- lemon/bellman_ford.h (revision 960)
+++ lemon/bellman_ford.h (revision 960)
@@ -0,0 +1,1115 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_BELLMAN_FORD_H
+#define LEMON_BELLMAN_FORD_H
+
+/// \ingroup shortest_path
+/// \file
+/// \brief Bellman-Ford algorithm.
+
+#include
+#include
+#include
+#include
+#include
+#include
+
+#include
+
+namespace lemon {
+
+ /// \brief Default OperationTraits for the BellmanFord algorithm class.
+ ///
+ /// This operation traits class defines all computational operations
+ /// and constants that are used in the Bellman-Ford algorithm.
+ /// The default implementation is based on the \c numeric_limits class.
+ /// If the numeric type does not have infinity value, then the maximum
+ /// value is used as extremal infinity value.
+ template <
+ typename V,
+ bool has_inf = std::numeric_limits::has_infinity>
+ struct BellmanFordDefaultOperationTraits {
+ /// \e
+ typedef V Value;
+ /// \brief Gives back the zero value of the type.
+ static Value zero() {
+ return static_cast(0);
+ }
+ /// \brief Gives back the positive infinity value of the type.
+ static Value infinity() {
+ return std::numeric_limits::infinity();
+ }
+ /// \brief Gives back the sum of the given two elements.
+ static Value plus(const Value& left, const Value& right) {
+ return left + right;
+ }
+ /// \brief Gives back \c true only if the first value is less than
+ /// the second.
+ static bool less(const Value& left, const Value& right) {
+ return left < right;
+ }
+ };
+
+ template
+ struct BellmanFordDefaultOperationTraits {
+ typedef V Value;
+ static Value zero() {
+ return static_cast(0);
+ }
+ static Value infinity() {
+ return std::numeric_limits::max();
+ }
+ static Value plus(const Value& left, const Value& right) {
+ if (left == infinity() || right == infinity()) return infinity();
+ return left + right;
+ }
+ static bool less(const Value& left, const Value& right) {
+ return left < right;
+ }
+ };
+
+ /// \brief Default traits class of BellmanFord class.
+ ///
+ /// Default traits class of BellmanFord class.
+ /// \param GR The type of the digraph.
+ /// \param LEN The type of the length map.
+ template
+ struct BellmanFordDefaultTraits {
+ /// The type of the digraph the algorithm runs on.
+ typedef GR Digraph;
+
+ /// \brief The type of the map that stores the arc lengths.
+ ///
+ /// The type of the map that stores the arc lengths.
+ /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+ typedef LEN LengthMap;
+
+ /// The type of the arc lengths.
+ typedef typename LEN::Value Value;
+
+ /// \brief Operation traits for Bellman-Ford algorithm.
+ ///
+ /// It defines the used operations and the infinity value for the
+ /// given \c Value type.
+ /// \see BellmanFordDefaultOperationTraits
+ typedef BellmanFordDefaultOperationTraits OperationTraits;
+
+ /// \brief The type of the map that stores the last arcs of the
+ /// shortest paths.
+ ///
+ /// The type of the map that stores the last
+ /// arcs of the shortest paths.
+ /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ typedef typename GR::template NodeMap PredMap;
+
+ /// \brief Instantiates a \c PredMap.
+ ///
+ /// This function instantiates a \ref PredMap.
+ /// \param g is the digraph to which we would like to define the
+ /// \ref PredMap.
+ static PredMap *createPredMap(const GR& g) {
+ return new PredMap(g);
+ }
+
+ /// \brief The type of the map that stores the distances of the nodes.
+ ///
+ /// The type of the map that stores the distances of the nodes.
+ /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ typedef typename GR::template NodeMap DistMap;
+
+ /// \brief Instantiates a \c DistMap.
+ ///
+ /// This function instantiates a \ref DistMap.
+ /// \param g is the digraph to which we would like to define the
+ /// \ref DistMap.
+ static DistMap *createDistMap(const GR& g) {
+ return new DistMap(g);
+ }
+
+ };
+
+ /// \brief %BellmanFord algorithm class.
+ ///
+ /// \ingroup shortest_path
+ /// This class provides an efficient implementation of the Bellman-Ford
+ /// algorithm. The maximum time complexity of the algorithm is
+ /// O(ne).
+ ///
+ /// The Bellman-Ford algorithm solves the single-source shortest path
+ /// problem when the arcs can have negative lengths, but the digraph
+ /// should not contain directed cycles with negative total length.
+ /// If all arc costs are non-negative, consider to use the Dijkstra
+ /// algorithm instead, since it is more efficient.
+ ///
+ /// The arc lengths are passed to the algorithm using a
+ /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
+ /// kind of length. The type of the length values is determined by the
+ /// \ref concepts::ReadMap::Value "Value" type of the length map.
+ ///
+ /// There is also a \ref bellmanFord() "function-type interface" for the
+ /// Bellman-Ford algorithm, which is convenient in the simplier cases and
+ /// it can be used easier.
+ ///
+ /// \tparam GR The type of the digraph the algorithm runs on.
+ /// The default type is \ref ListDigraph.
+ /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
+ /// the lengths of the arcs. The default map type is
+ /// \ref concepts::Digraph::ArcMap "GR::ArcMap".
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm. By default, it is \ref BellmanFordDefaultTraits
+ /// "BellmanFordDefaultTraits".
+ /// In most cases, this parameter should not be set directly,
+ /// consider to use the named template parameters instead.
+#ifdef DOXYGEN
+ template
+#else
+ template ,
+ typename TR=BellmanFordDefaultTraits >
+#endif
+ class BellmanFord {
+ public:
+
+ ///The type of the underlying digraph.
+ typedef typename TR::Digraph Digraph;
+
+ /// \brief The type of the arc lengths.
+ typedef typename TR::LengthMap::Value Value;
+ /// \brief The type of the map that stores the arc lengths.
+ typedef typename TR::LengthMap LengthMap;
+ /// \brief The type of the map that stores the last
+ /// arcs of the shortest paths.
+ typedef typename TR::PredMap PredMap;
+ /// \brief The type of the map that stores the distances of the nodes.
+ typedef typename TR::DistMap DistMap;
+ /// The type of the paths.
+ typedef PredMapPath Path;
+ ///\brief The \ref BellmanFordDefaultOperationTraits
+ /// "operation traits class" of the algorithm.
+ typedef typename TR::OperationTraits OperationTraits;
+
+ ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
+ typedef TR Traits;
+
+ private:
+
+ typedef typename Digraph::Node Node;
+ typedef typename Digraph::NodeIt NodeIt;
+ typedef typename Digraph::Arc Arc;
+ typedef typename Digraph::OutArcIt OutArcIt;
+
+ // Pointer to the underlying digraph.
+ const Digraph *_gr;
+ // Pointer to the length map
+ const LengthMap *_length;
+ // Pointer to the map of predecessors arcs.
+ PredMap *_pred;
+ // Indicates if _pred is locally allocated (true) or not.
+ bool _local_pred;
+ // Pointer to the map of distances.
+ DistMap *_dist;
+ // Indicates if _dist is locally allocated (true) or not.
+ bool _local_dist;
+
+ typedef typename Digraph::template NodeMap MaskMap;
+ MaskMap *_mask;
+
+ std::vector _process;
+
+ // Creates the maps if necessary.
+ void create_maps() {
+ if(!_pred) {
+ _local_pred = true;
+ _pred = Traits::createPredMap(*_gr);
+ }
+ if(!_dist) {
+ _local_dist = true;
+ _dist = Traits::createDistMap(*_gr);
+ }
+ if(!_mask) {
+ _mask = new MaskMap(*_gr);
+ }
+ }
+
+ public :
+
+ typedef BellmanFord Create;
+
+ /// \name Named Template Parameters
+
+ ///@{
+
+ template
+ struct SetPredMapTraits : public Traits {
+ typedef T PredMap;
+ static PredMap *createPredMap(const Digraph&) {
+ LEMON_ASSERT(false, "PredMap is not initialized");
+ return 0; // ignore warnings
+ }
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// \c PredMap type.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting
+ /// \c PredMap type.
+ /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ template
+ struct SetPredMap
+ : public BellmanFord< Digraph, LengthMap, SetPredMapTraits > {
+ typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits > Create;
+ };
+
+ template
+ struct SetDistMapTraits : public Traits {
+ typedef T DistMap;
+ static DistMap *createDistMap(const Digraph&) {
+ LEMON_ASSERT(false, "DistMap is not initialized");
+ return 0; // ignore warnings
+ }
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// \c DistMap type.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting
+ /// \c DistMap type.
+ /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ template
+ struct SetDistMap
+ : public BellmanFord< Digraph, LengthMap, SetDistMapTraits > {
+ typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits > Create;
+ };
+
+ template
+ struct SetOperationTraitsTraits : public Traits {
+ typedef T OperationTraits;
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// \c OperationTraits type.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting
+ /// \c OperationTraits type.
+ /// For more information, see \ref BellmanFordDefaultOperationTraits.
+ template
+ struct SetOperationTraits
+ : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits > {
+ typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits >
+ Create;
+ };
+
+ ///@}
+
+ protected:
+
+ BellmanFord() {}
+
+ public:
+
+ /// \brief Constructor.
+ ///
+ /// Constructor.
+ /// \param g The digraph the algorithm runs on.
+ /// \param length The length map used by the algorithm.
+ BellmanFord(const Digraph& g, const LengthMap& length) :
+ _gr(&g), _length(&length),
+ _pred(0), _local_pred(false),
+ _dist(0), _local_dist(false), _mask(0) {}
+
+ ///Destructor.
+ ~BellmanFord() {
+ if(_local_pred) delete _pred;
+ if(_local_dist) delete _dist;
+ if(_mask) delete _mask;
+ }
+
+ /// \brief Sets the length map.
+ ///
+ /// Sets the length map.
+ /// \return (*this)
+ BellmanFord &lengthMap(const LengthMap &map) {
+ _length = ↦
+ return *this;
+ }
+
+ /// \brief Sets the map that stores the predecessor arcs.
+ ///
+ /// Sets the map that stores the predecessor arcs.
+ /// If you don't use this function before calling \ref run()
+ /// or \ref init(), an instance will be allocated automatically.
+ /// The destructor deallocates this automatically allocated map,
+ /// of course.
+ /// \return (*this)
+ BellmanFord &predMap(PredMap &map) {
+ if(_local_pred) {
+ delete _pred;
+ _local_pred=false;
+ }
+ _pred = ↦
+ return *this;
+ }
+
+ /// \brief Sets the map that stores the distances of the nodes.
+ ///
+ /// Sets the map that stores the distances of the nodes calculated
+ /// by the algorithm.
+ /// If you don't use this function before calling \ref run()
+ /// or \ref init(), an instance will be allocated automatically.
+ /// The destructor deallocates this automatically allocated map,
+ /// of course.
+ /// \return (*this)
+ BellmanFord &distMap(DistMap &map) {
+ if(_local_dist) {
+ delete _dist;
+ _local_dist=false;
+ }
+ _dist = ↦
+ return *this;
+ }
+
+ /// \name Execution Control
+ /// The simplest way to execute the Bellman-Ford algorithm is to use
+ /// one of the member functions called \ref run().\n
+ /// If you need better control on the execution, you have to call
+ /// \ref init() first, then you can add several source nodes
+ /// with \ref addSource(). Finally the actual path computation can be
+ /// performed with \ref start(), \ref checkedStart() or
+ /// \ref limitedStart().
+
+ ///@{
+
+ /// \brief Initializes the internal data structures.
+ ///
+ /// Initializes the internal data structures. The optional parameter
+ /// is the initial distance of each node.
+ void init(const Value value = OperationTraits::infinity()) {
+ create_maps();
+ for (NodeIt it(*_gr); it != INVALID; ++it) {
+ _pred->set(it, INVALID);
+ _dist->set(it, value);
+ }
+ _process.clear();
+ if (OperationTraits::less(value, OperationTraits::infinity())) {
+ for (NodeIt it(*_gr); it != INVALID; ++it) {
+ _process.push_back(it);
+ _mask->set(it, true);
+ }
+ } else {
+ for (NodeIt it(*_gr); it != INVALID; ++it) {
+ _mask->set(it, false);
+ }
+ }
+ }
+
+ /// \brief Adds a new source node.
+ ///
+ /// This function adds a new source node. The optional second parameter
+ /// is the initial distance of the node.
+ void addSource(Node source, Value dst = OperationTraits::zero()) {
+ _dist->set(source, dst);
+ if (!(*_mask)[source]) {
+ _process.push_back(source);
+ _mask->set(source, true);
+ }
+ }
+
+ /// \brief Executes one round from the Bellman-Ford algorithm.
+ ///
+ /// If the algoritm calculated the distances in the previous round
+ /// exactly for the paths of at most \c k arcs, then this function
+ /// will calculate the distances exactly for the paths of at most
+ /// k+1 arcs. Performing \c k iterations using this function
+ /// calculates the shortest path distances exactly for the paths
+ /// consisting of at most \c k arcs.
+ ///
+ /// \warning The paths with limited arc number cannot be retrieved
+ /// easily with \ref path() or \ref predArc() functions. If you also
+ /// need the shortest paths and not only the distances, you should
+ /// store the \ref predMap() "predecessor map" after each iteration
+ /// and build the path manually.
+ ///
+ /// \return \c true when the algorithm have not found more shorter
+ /// paths.
+ ///
+ /// \see ActiveIt
+ bool processNextRound() {
+ for (int i = 0; i < int(_process.size()); ++i) {
+ _mask->set(_process[i], false);
+ }
+ std::vector nextProcess;
+ std::vector values(_process.size());
+ for (int i = 0; i < int(_process.size()); ++i) {
+ values[i] = (*_dist)[_process[i]];
+ }
+ for (int i = 0; i < int(_process.size()); ++i) {
+ for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
+ Node target = _gr->target(it);
+ Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
+ if (OperationTraits::less(relaxed, (*_dist)[target])) {
+ _pred->set(target, it);
+ _dist->set(target, relaxed);
+ if (!(*_mask)[target]) {
+ _mask->set(target, true);
+ nextProcess.push_back(target);
+ }
+ }
+ }
+ }
+ _process.swap(nextProcess);
+ return _process.empty();
+ }
+
+ /// \brief Executes one weak round from the Bellman-Ford algorithm.
+ ///
+ /// If the algorithm calculated the distances in the previous round
+ /// at least for the paths of at most \c k arcs, then this function
+ /// will calculate the distances at least for the paths of at most
+ /// k+1 arcs.
+ /// This function does not make it possible to calculate the shortest
+ /// path distances exactly for paths consisting of at most \c k arcs,
+ /// this is why it is called weak round.
+ ///
+ /// \return \c true when the algorithm have not found more shorter
+ /// paths.
+ ///
+ /// \see ActiveIt
+ bool processNextWeakRound() {
+ for (int i = 0; i < int(_process.size()); ++i) {
+ _mask->set(_process[i], false);
+ }
+ std::vector nextProcess;
+ for (int i = 0; i < int(_process.size()); ++i) {
+ for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
+ Node target = _gr->target(it);
+ Value relaxed =
+ OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
+ if (OperationTraits::less(relaxed, (*_dist)[target])) {
+ _pred->set(target, it);
+ _dist->set(target, relaxed);
+ if (!(*_mask)[target]) {
+ _mask->set(target, true);
+ nextProcess.push_back(target);
+ }
+ }
+ }
+ }
+ _process.swap(nextProcess);
+ return _process.empty();
+ }
+
+ /// \brief Executes the algorithm.
+ ///
+ /// Executes the algorithm.
+ ///
+ /// This method runs the Bellman-Ford algorithm from the root node(s)
+ /// in order to compute the shortest path to each node.
+ ///
+ /// The algorithm computes
+ /// - the shortest path tree (forest),
+ /// - the distance of each node from the root(s).
+ ///
+ /// \pre init() must be called and at least one root node should be
+ /// added with addSource() before using this function.
+ void start() {
+ int num = countNodes(*_gr) - 1;
+ for (int i = 0; i < num; ++i) {
+ if (processNextWeakRound()) break;
+ }
+ }
+
+ /// \brief Executes the algorithm and checks the negative cycles.
+ ///
+ /// Executes the algorithm and checks the negative cycles.
+ ///
+ /// This method runs the Bellman-Ford algorithm from the root node(s)
+ /// in order to compute the shortest path to each node and also checks
+ /// if the digraph contains cycles with negative total length.
+ ///
+ /// The algorithm computes
+ /// - the shortest path tree (forest),
+ /// - the distance of each node from the root(s).
+ ///
+ /// \return \c false if there is a negative cycle in the digraph.
+ ///
+ /// \pre init() must be called and at least one root node should be
+ /// added with addSource() before using this function.
+ bool checkedStart() {
+ int num = countNodes(*_gr);
+ for (int i = 0; i < num; ++i) {
+ if (processNextWeakRound()) return true;
+ }
+ return _process.empty();
+ }
+
+ /// \brief Executes the algorithm with arc number limit.
+ ///
+ /// Executes the algorithm with arc number limit.
+ ///
+ /// This method runs the Bellman-Ford algorithm from the root node(s)
+ /// in order to compute the shortest path distance for each node
+ /// using only the paths consisting of at most \c num arcs.
+ ///
+ /// The algorithm computes
+ /// - the limited distance of each node from the root(s),
+ /// - the predecessor arc for each node.
+ ///
+ /// \warning The paths with limited arc number cannot be retrieved
+ /// easily with \ref path() or \ref predArc() functions. If you also
+ /// need the shortest paths and not only the distances, you should
+ /// store the \ref predMap() "predecessor map" after each iteration
+ /// and build the path manually.
+ ///
+ /// \pre init() must be called and at least one root node should be
+ /// added with addSource() before using this function.
+ void limitedStart(int num) {
+ for (int i = 0; i < num; ++i) {
+ if (processNextRound()) break;
+ }
+ }
+
+ /// \brief Runs the algorithm from the given root node.
+ ///
+ /// This method runs the Bellman-Ford algorithm from the given root
+ /// node \c s in order to compute the shortest path to each node.
+ ///
+ /// The algorithm computes
+ /// - the shortest path tree (forest),
+ /// - the distance of each node from the root(s).
+ ///
+ /// \note bf.run(s) is just a shortcut of the following code.
+ /// \code
+ /// bf.init();
+ /// bf.addSource(s);
+ /// bf.start();
+ /// \endcode
+ void run(Node s) {
+ init();
+ addSource(s);
+ start();
+ }
+
+ /// \brief Runs the algorithm from the given root node with arc
+ /// number limit.
+ ///
+ /// This method runs the Bellman-Ford algorithm from the given root
+ /// node \c s in order to compute the shortest path distance for each
+ /// node using only the paths consisting of at most \c num arcs.
+ ///
+ /// The algorithm computes
+ /// - the limited distance of each node from the root(s),
+ /// - the predecessor arc for each node.
+ ///
+ /// \warning The paths with limited arc number cannot be retrieved
+ /// easily with \ref path() or \ref predArc() functions. If you also
+ /// need the shortest paths and not only the distances, you should
+ /// store the \ref predMap() "predecessor map" after each iteration
+ /// and build the path manually.
+ ///
+ /// \note bf.run(s, num) is just a shortcut of the following code.
+ /// \code
+ /// bf.init();
+ /// bf.addSource(s);
+ /// bf.limitedStart(num);
+ /// \endcode
+ void run(Node s, int num) {
+ init();
+ addSource(s);
+ limitedStart(num);
+ }
+
+ ///@}
+
+ /// \brief LEMON iterator for getting the active nodes.
+ ///
+ /// This class provides a common style LEMON iterator that traverses
+ /// the active nodes of the Bellman-Ford algorithm after the last
+ /// phase. These nodes should be checked in the next phase to
+ /// find augmenting arcs outgoing from them.
+ class ActiveIt {
+ public:
+
+ /// \brief Constructor.
+ ///
+ /// Constructor for getting the active nodes of the given BellmanFord
+ /// instance.
+ ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
+ {
+ _index = _algorithm->_process.size() - 1;
+ }
+
+ /// \brief Invalid constructor.
+ ///
+ /// Invalid constructor.
+ ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
+
+ /// \brief Conversion to \c Node.
+ ///
+ /// Conversion to \c Node.
+ operator Node() const {
+ return _index >= 0 ? _algorithm->_process[_index] : INVALID;
+ }
+
+ /// \brief Increment operator.
+ ///
+ /// Increment operator.
+ ActiveIt& operator++() {
+ --_index;
+ return *this;
+ }
+
+ bool operator==(const ActiveIt& it) const {
+ return static_cast(*this) == static_cast(it);
+ }
+ bool operator!=(const ActiveIt& it) const {
+ return static_cast(*this) != static_cast(it);
+ }
+ bool operator<(const ActiveIt& it) const {
+ return static_cast(*this) < static_cast(it);
+ }
+
+ private:
+ const BellmanFord* _algorithm;
+ int _index;
+ };
+
+ /// \name Query Functions
+ /// The result of the Bellman-Ford algorithm can be obtained using these
+ /// functions.\n
+ /// Either \ref run() or \ref init() should be called before using them.
+
+ ///@{
+
+ /// \brief The shortest path to the given node.
+ ///
+ /// Gives back the shortest path to the given node from the root(s).
+ ///
+ /// \warning \c t should be reached from the root(s).
+ ///
+ /// \pre Either \ref run() or \ref init() must be called before
+ /// using this function.
+ Path path(Node t) const
+ {
+ return Path(*_gr, *_pred, t);
+ }
+
+ /// \brief The distance of the given node from the root(s).
+ ///
+ /// Returns the distance of the given node from the root(s).
+ ///
+ /// \warning If node \c v is not reached from the root(s), then
+ /// the return value of this function is undefined.
+ ///
+ /// \pre Either \ref run() or \ref init() must be called before
+ /// using this function.
+ Value dist(Node v) const { return (*_dist)[v]; }
+
+ /// \brief Returns the 'previous arc' of the shortest path tree for
+ /// the given node.
+ ///
+ /// This function returns the 'previous arc' of the shortest path
+ /// tree for node \c v, i.e. it returns the last arc of a
+ /// shortest path from a root to \c v. It is \c INVALID if \c v
+ /// is not reached from the root(s) or if \c v is a root.
+ ///
+ /// The shortest path tree used here is equal to the shortest path
+ /// tree used in \ref predNode() and \ref predMap().
+ ///
+ /// \pre Either \ref run() or \ref init() must be called before
+ /// using this function.
+ Arc predArc(Node v) const { return (*_pred)[v]; }
+
+ /// \brief Returns the 'previous node' of the shortest path tree for
+ /// the given node.
+ ///
+ /// This function returns the 'previous node' of the shortest path
+ /// tree for node \c v, i.e. it returns the last but one node of
+ /// a shortest path from a root to \c v. It is \c INVALID if \c v
+ /// is not reached from the root(s) or if \c v is a root.
+ ///
+ /// The shortest path tree used here is equal to the shortest path
+ /// tree used in \ref predArc() and \ref predMap().
+ ///
+ /// \pre Either \ref run() or \ref init() must be called before
+ /// using this function.
+ Node predNode(Node v) const {
+ return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
+ }
+
+ /// \brief Returns a const reference to the node map that stores the
+ /// distances of the nodes.
+ ///
+ /// Returns a const reference to the node map that stores the distances
+ /// of the nodes calculated by the algorithm.
+ ///
+ /// \pre Either \ref run() or \ref init() must be called before
+ /// using this function.
+ const DistMap &distMap() const { return *_dist;}
+
+ /// \brief Returns a const reference to the node map that stores the
+ /// predecessor arcs.
+ ///
+ /// Returns a const reference to the node map that stores the predecessor
+ /// arcs, which form the shortest path tree (forest).
+ ///
+ /// \pre Either \ref run() or \ref init() must be called before
+ /// using this function.
+ const PredMap &predMap() const { return *_pred; }
+
+ /// \brief Checks if a node is reached from the root(s).
+ ///
+ /// Returns \c true if \c v is reached from the root(s).
+ ///
+ /// \pre Either \ref run() or \ref init() must be called before
+ /// using this function.
+ bool reached(Node v) const {
+ return (*_dist)[v] != OperationTraits::infinity();
+ }
+
+ /// \brief Gives back a negative cycle.
+ ///
+ /// This function gives back a directed cycle with negative total
+ /// length if the algorithm has already found one.
+ /// Otherwise it gives back an empty path.
+ lemon::Path negativeCycle() const {
+ typename Digraph::template NodeMap state(*_gr, -1);
+ lemon::Path cycle;
+ for (int i = 0; i < int(_process.size()); ++i) {
+ if (state[_process[i]] != -1) continue;
+ for (Node v = _process[i]; (*_pred)[v] != INVALID;
+ v = _gr->source((*_pred)[v])) {
+ if (state[v] == i) {
+ cycle.addFront((*_pred)[v]);
+ for (Node u = _gr->source((*_pred)[v]); u != v;
+ u = _gr->source((*_pred)[u])) {
+ cycle.addFront((*_pred)[u]);
+ }
+ return cycle;
+ }
+ else if (state[v] >= 0) {
+ break;
+ }
+ state[v] = i;
+ }
+ }
+ return cycle;
+ }
+
+ ///@}
+ };
+
+ /// \brief Default traits class of bellmanFord() function.
+ ///
+ /// Default traits class of bellmanFord() function.
+ /// \tparam GR The type of the digraph.
+ /// \tparam LEN The type of the length map.
+ template
+ struct BellmanFordWizardDefaultTraits {
+ /// The type of the digraph the algorithm runs on.
+ typedef GR Digraph;
+
+ /// \brief The type of the map that stores the arc lengths.
+ ///
+ /// The type of the map that stores the arc lengths.
+ /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
+ typedef LEN LengthMap;
+
+ /// The type of the arc lengths.
+ typedef typename LEN::Value Value;
+
+ /// \brief Operation traits for Bellman-Ford algorithm.
+ ///
+ /// It defines the used operations and the infinity value for the
+ /// given \c Value type.
+ /// \see BellmanFordDefaultOperationTraits
+ typedef BellmanFordDefaultOperationTraits OperationTraits;
+
+ /// \brief The type of the map that stores the last
+ /// arcs of the shortest paths.
+ ///
+ /// The type of the map that stores the last arcs of the shortest paths.
+ /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ typedef typename GR::template NodeMap PredMap;
+
+ /// \brief Instantiates a \c PredMap.
+ ///
+ /// This function instantiates a \ref PredMap.
+ /// \param g is the digraph to which we would like to define the
+ /// \ref PredMap.
+ static PredMap *createPredMap(const GR &g) {
+ return new PredMap(g);
+ }
+
+ /// \brief The type of the map that stores the distances of the nodes.
+ ///
+ /// The type of the map that stores the distances of the nodes.
+ /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ typedef typename GR::template NodeMap DistMap;
+
+ /// \brief Instantiates a \c DistMap.
+ ///
+ /// This function instantiates a \ref DistMap.
+ /// \param g is the digraph to which we would like to define the
+ /// \ref DistMap.
+ static DistMap *createDistMap(const GR &g) {
+ return new DistMap(g);
+ }
+
+ ///The type of the shortest paths.
+
+ ///The type of the shortest paths.
+ ///It must meet the \ref concepts::Path "Path" concept.
+ typedef lemon::Path Path;
+ };
+
+ /// \brief Default traits class used by BellmanFordWizard.
+ ///
+ /// Default traits class used by BellmanFordWizard.
+ /// \tparam GR The type of the digraph.
+ /// \tparam LEN The type of the length map.
+ template
+ class BellmanFordWizardBase
+ : public BellmanFordWizardDefaultTraits {
+
+ typedef BellmanFordWizardDefaultTraits Base;
+ protected:
+ // Type of the nodes in the digraph.
+ typedef typename Base::Digraph::Node Node;
+
+ // Pointer to the underlying digraph.
+ void *_graph;
+ // Pointer to the length map
+ void *_length;
+ // Pointer to the map of predecessors arcs.
+ void *_pred;
+ // Pointer to the map of distances.
+ void *_dist;
+ //Pointer to the shortest path to the target node.
+ void *_path;
+ //Pointer to the distance of the target node.
+ void *_di;
+
+ public:
+ /// Constructor.
+
+ /// This constructor does not require parameters, it initiates
+ /// all of the attributes to default values \c 0.
+ BellmanFordWizardBase() :
+ _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
+
+ /// Constructor.
+
+ /// This constructor requires two parameters,
+ /// others are initiated to \c 0.
+ /// \param gr The digraph the algorithm runs on.
+ /// \param len The length map.
+ BellmanFordWizardBase(const GR& gr,
+ const LEN& len) :
+ _graph(reinterpret_cast(const_cast(&gr))),
+ _length(reinterpret_cast(const_cast(&len))),
+ _pred(0), _dist(0), _path(0), _di(0) {}
+
+ };
+
+ /// \brief Auxiliary class for the function-type interface of the
+ /// \ref BellmanFord "Bellman-Ford" algorithm.
+ ///
+ /// This auxiliary class is created to implement the
+ /// \ref bellmanFord() "function-type interface" of the
+ /// \ref BellmanFord "Bellman-Ford" algorithm.
+ /// It does not have own \ref run() method, it uses the
+ /// functions and features of the plain \ref BellmanFord.
+ ///
+ /// This class should only be used through the \ref bellmanFord()
+ /// function, which makes it easier to use the algorithm.
+ ///
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm.
+ template
+ class BellmanFordWizard : public TR {
+ typedef TR Base;
+
+ typedef typename TR::Digraph Digraph;
+
+ typedef typename Digraph::Node Node;
+ typedef typename Digraph::NodeIt NodeIt;
+ typedef typename Digraph::Arc Arc;
+ typedef typename Digraph::OutArcIt ArcIt;
+
+ typedef typename TR::LengthMap LengthMap;
+ typedef typename LengthMap::Value Value;
+ typedef typename TR::PredMap PredMap;
+ typedef typename TR::DistMap DistMap;
+ typedef typename TR::Path Path;
+
+ public:
+ /// Constructor.
+ BellmanFordWizard() : TR() {}
+
+ /// \brief Constructor that requires parameters.
+ ///
+ /// Constructor that requires parameters.
+ /// These parameters will be the default values for the traits class.
+ /// \param gr The digraph the algorithm runs on.
+ /// \param len The length map.
+ BellmanFordWizard(const Digraph& gr, const LengthMap& len)
+ : TR(gr, len) {}
+
+ /// \brief Copy constructor
+ BellmanFordWizard(const TR &b) : TR(b) {}
+
+ ~BellmanFordWizard() {}
+
+ /// \brief Runs the Bellman-Ford algorithm from the given source node.
+ ///
+ /// This method runs the Bellman-Ford algorithm from the given source
+ /// node in order to compute the shortest path to each node.
+ void run(Node s) {
+ BellmanFord
+ bf(*reinterpret_cast(Base::_graph),
+ *reinterpret_cast(Base::_length));
+ if (Base::_pred) bf.predMap(*reinterpret_cast(Base::_pred));
+ if (Base::_dist) bf.distMap(*reinterpret_cast(Base::_dist));
+ bf.run(s);
+ }
+
+ /// \brief Runs the Bellman-Ford algorithm to find the shortest path
+ /// between \c s and \c t.
+ ///
+ /// This method runs the Bellman-Ford algorithm from node \c s
+ /// in order to compute the shortest path to node \c t.
+ /// Actually, it computes the shortest path to each node, but using
+ /// this function you can retrieve the distance and the shortest path
+ /// for a single target node easier.
+ ///
+ /// \return \c true if \c t is reachable form \c s.
+ bool run(Node s, Node t) {
+ BellmanFord
+ bf(*reinterpret_cast(Base::_graph),
+ *reinterpret_cast(Base::_length));
+ if (Base::_pred) bf.predMap(*reinterpret_cast(Base::_pred));
+ if (Base::_dist) bf.distMap(*reinterpret_cast(Base::_dist));
+ bf.run(s);
+ if (Base::_path) *reinterpret_cast(Base::_path) = bf.path(t);
+ if (Base::_di) *reinterpret_cast(Base::_di) = bf.dist(t);
+ return bf.reached(t);
+ }
+
+ template
+ struct SetPredMapBase : public Base {
+ typedef T PredMap;
+ static PredMap *createPredMap(const Digraph &) { return 0; };
+ SetPredMapBase(const TR &b) : TR(b) {}
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// the predecessor map.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting
+ /// the map that stores the predecessor arcs of the nodes.
+ template
+ BellmanFordWizard > predMap(const T &t) {
+ Base::_pred=reinterpret_cast(const_cast(&t));
+ return BellmanFordWizard >(*this);
+ }
+
+ template
+ struct SetDistMapBase : public Base {
+ typedef T DistMap;
+ static DistMap *createDistMap(const Digraph &) { return 0; };
+ SetDistMapBase(const TR &b) : TR(b) {}
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// the distance map.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting
+ /// the map that stores the distances of the nodes calculated
+ /// by the algorithm.
+ template
+ BellmanFordWizard > distMap(const T &t) {
+ Base::_dist=reinterpret_cast(const_cast(&t));
+ return BellmanFordWizard >(*this);
+ }
+
+ template
+ struct SetPathBase : public Base {
+ typedef T Path;
+ SetPathBase(const TR &b) : TR(b) {}
+ };
+
+ /// \brief \ref named-func-param "Named parameter" for getting
+ /// the shortest path to the target node.
+ ///
+ /// \ref named-func-param "Named parameter" for getting
+ /// the shortest path to the target node.
+ template
+ BellmanFordWizard > path(const T &t)
+ {
+ Base::_path=reinterpret_cast(const_cast(&t));
+ return BellmanFordWizard >(*this);
+ }
+
+ /// \brief \ref named-func-param "Named parameter" for getting
+ /// the distance of the target node.
+ ///
+ /// \ref named-func-param "Named parameter" for getting
+ /// the distance of the target node.
+ BellmanFordWizard dist(const Value &d)
+ {
+ Base::_di=reinterpret_cast(const_cast(&d));
+ return *this;
+ }
+
+ };
+
+ /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
+ /// algorithm.
+ ///
+ /// \ingroup shortest_path
+ /// Function type interface for the \ref BellmanFord "Bellman-Ford"
+ /// algorithm.
+ ///
+ /// This function also has several \ref named-templ-func-param
+ /// "named parameters", they are declared as the members of class
+ /// \ref BellmanFordWizard.
+ /// The following examples show how to use these parameters.
+ /// \code
+ /// // Compute shortest path from node s to each node
+ /// bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
+ ///
+ /// // Compute shortest path from s to t
+ /// bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
+ /// \endcode
+ /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
+ /// to the end of the parameter list.
+ /// \sa BellmanFordWizard
+ /// \sa BellmanFord
+ template
+ BellmanFordWizard >
+ bellmanFord(const GR& digraph,
+ const LEN& length)
+ {
+ return BellmanFordWizard >(digraph, length);
+ }
+
+} //END OF NAMESPACE LEMON
+
+#endif
+
Index: lemon/bfs.h
===================================================================
--- lemon/bfs.h (revision 525)
+++ lemon/bfs.h (revision 956)
@@ -3,5 +3,5 @@
* 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).
@@ -48,5 +48,5 @@
///The type of the map that stores the predecessor
///arcs of the shortest paths.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap PredMap;
///Instantiates a \c PredMap.
@@ -63,5 +63,6 @@
///The type of the map that indicates which nodes are processed.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ ///By default, it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a \c ProcessedMap.
@@ -82,5 +83,6 @@
///The type of the map that indicates which nodes are reached.
- ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///It must conform to
+ ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
///Instantiates a \c ReachedMap.
@@ -97,5 +99,5 @@
///The type of the map that stores the distances of the nodes.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap DistMap;
///Instantiates a \c DistMap.
@@ -121,4 +123,9 @@
///\tparam GR The type of the digraph the algorithm runs on.
///The default type is \ref ListDigraph.
+ ///\tparam TR The traits class that defines various types used by the
+ ///algorithm. By default, it is \ref BfsDefaultTraits
+ ///"BfsDefaultTraits".
+ ///In most cases, this parameter should not be set directly,
+ ///consider to use the named template parameters instead.
#ifdef DOXYGEN
template
struct SetPredMap : public Bfs< Digraph, SetPredMapTraits > {
@@ -246,5 +253,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c DistMap type.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetDistMap : public Bfs< Digraph, SetDistMapTraits > {
@@ -266,5 +273,6 @@
///\ref named-templ-param "Named parameter" for setting
///\c ReachedMap type.
- ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///It must conform to
+ ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
template
struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits > {
@@ -286,5 +294,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c ProcessedMap type.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits > {
@@ -414,6 +422,6 @@
///The simplest way to execute the BFS algorithm is to use one of the
///member functions called \ref run(Node) "run()".\n
- ///If you need more control on the execution, first you have to call
- ///\ref init(), then you can add several source nodes with
+ ///If you need better control on the execution, you have to call
+ ///\ref init() first, then you can add several source nodes with
///\ref addSource(). Finally the actual path computation can be
///performed with one of the \ref start() functions.
@@ -701,10 +709,6 @@
///Runs the algorithm to visit all nodes in the digraph.
- ///This method runs the %BFS algorithm in order to
- ///compute the shortest path to each node.
- ///
- ///The algorithm computes
- ///- the shortest path tree (forest),
- ///- the distance of each node from the root(s).
+ ///This method runs the %BFS algorithm in order to visit all nodes
+ ///in the digraph.
///
///\note b.run(s) is just a shortcut of the following code.
@@ -738,7 +742,7 @@
///@{
- ///The shortest path to a node.
-
- ///Returns the shortest path to a node.
+ ///The shortest path to the given node.
+
+ ///Returns the shortest path to the given node from the root(s).
///
///\warning \c t should be reached from the root(s).
@@ -748,7 +752,7 @@
Path path(Node t) const { return Path(*G, *_pred, t); }
- ///The distance of a node from the root(s).
-
- ///Returns the distance of a node from the root(s).
+ ///The distance of the given node from the root(s).
+
+ ///Returns the distance of the given node from the root(s).
///
///\warning If node \c v is not reached from the root(s), then
@@ -759,6 +763,7 @@
int dist(Node v) const { return (*_dist)[v]; }
- ///Returns the 'previous arc' of the shortest path tree for a node.
-
+ ///\brief Returns the 'previous arc' of the shortest path tree for
+ ///the given node.
+ ///
///This function returns the 'previous arc' of the shortest path
///tree for the node \c v, i.e. it returns the last arc of a
@@ -767,5 +772,5 @@
///
///The shortest path tree used here is equal to the shortest path
- ///tree used in \ref predNode().
+ ///tree used in \ref predNode() and \ref predMap().
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -773,13 +778,14 @@
Arc predArc(Node v) const { return (*_pred)[v];}
- ///Returns the 'previous node' of the shortest path tree for a node.
-
+ ///\brief Returns the 'previous node' of the shortest path tree for
+ ///the given node.
+ ///
///This function returns the 'previous node' of the shortest path
///tree for the node \c v, i.e. it returns the last but one node
- ///from a shortest path from a root to \c v. It is \c INVALID
+ ///of a shortest path from a root to \c v. It is \c INVALID
///if \c v is not reached from the root(s) or if \c v is a root.
///
///The shortest path tree used here is equal to the shortest path
- ///tree used in \ref predArc().
+ ///tree used in \ref predArc() and \ref predMap().
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -802,5 +808,5 @@
///
///Returns a const reference to the node map that stores the predecessor
- ///arcs, which form the shortest path tree.
+ ///arcs, which form the shortest path tree (forest).
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -808,5 +814,5 @@
const PredMap &predMap() const { return *_pred;}
- ///Checks if a node is reached from the root(s).
+ ///Checks if the given node is reached from the root(s).
///Returns \c true if \c v is reached from the root(s).
@@ -834,5 +840,5 @@
///The type of the map that stores the predecessor
///arcs of the shortest paths.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap PredMap;
///Instantiates a PredMap.
@@ -849,6 +855,6 @@
///The type of the map that indicates which nodes are processed.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///By default it is a NullMap.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ ///By default, it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a ProcessedMap.
@@ -869,5 +875,6 @@
///The type of the map that indicates which nodes are reached.
- ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///It must conform to
+ ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
///Instantiates a ReachedMap.
@@ -884,5 +891,5 @@
///The type of the map that stores the distances of the nodes.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap DistMap;
///Instantiates a DistMap.
@@ -899,5 +906,5 @@
///The type of the shortest paths.
- ///It must meet the \ref concepts::Path "Path" concept.
+ ///It must conform to the \ref concepts::Path "Path" concept.
typedef lemon::Path Path;
};
@@ -905,10 +912,6 @@
/// Default traits class used by BfsWizard
- /// To make it easier to use Bfs algorithm
- /// we have created a wizard class.
- /// This \ref BfsWizard class needs default traits,
- /// as well as the \ref Bfs class.
- /// The \ref BfsWizardBase is a class to be the default traits of the
- /// \ref BfsWizard class.
+ /// Default traits class used by BfsWizard.
+ /// \tparam GR The type of the digraph.
template
class BfsWizardBase : public BfsWizardDefaultTraits
@@ -938,5 +941,5 @@
/// Constructor.
- /// This constructor does not require parameters, therefore it initiates
+ /// This constructor does not require parameters, it initiates
/// all of the attributes to \c 0.
BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
@@ -963,4 +966,7 @@
/// This class should only be used through the \ref bfs() function,
/// which makes it easier to use the algorithm.
+ ///
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm.
template
class BfsWizard : public TR
@@ -968,5 +974,4 @@
typedef TR Base;
- ///The type of the digraph the algorithm runs on.
typedef typename TR::Digraph Digraph;
@@ -976,14 +981,8 @@
typedef typename Digraph::OutArcIt OutArcIt;
- ///\brief The type of the map that stores the predecessor
- ///arcs of the shortest paths.
typedef typename TR::PredMap PredMap;
- ///\brief The type of the map that stores the distances of the nodes.
typedef typename TR::DistMap DistMap;
- ///\brief The type of the map that indicates which nodes are reached.
typedef typename TR::ReachedMap ReachedMap;
- ///\brief The type of the map that indicates which nodes are processed.
typedef typename TR::ProcessedMap ProcessedMap;
- ///The type of the shortest paths
typedef typename TR::Path Path;
@@ -1055,6 +1054,6 @@
///Runs BFS algorithm to visit all nodes in the digraph.
- ///This method runs BFS algorithm in order to compute
- ///the shortest path to each node.
+ ///This method runs BFS algorithm in order to visit all nodes
+ ///in the digraph.
void run()
{
@@ -1068,9 +1067,10 @@
SetPredMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting PredMap object.
- ///
- ///\ref named-func-param "Named parameter"
- ///for setting PredMap object.
+
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///the predecessor map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that stores the predecessor arcs of the nodes.
template
BfsWizard > predMap(const T &t)
@@ -1086,9 +1086,10 @@
SetReachedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting ReachedMap object.
- ///
- /// \ref named-func-param "Named parameter"
- ///for setting ReachedMap object.
+
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///the reached map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that indicates which nodes are reached.
template
BfsWizard > reachedMap(const T &t)
@@ -1104,9 +1105,11 @@
SetDistMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting DistMap object.
- ///
- /// \ref named-func-param "Named parameter"
- ///for setting DistMap object.
+
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///the distance map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that stores the distances of the nodes calculated
+ ///by the algorithm.
template
BfsWizard > distMap(const T &t)
@@ -1122,9 +1125,10 @@
SetProcessedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting ProcessedMap object.
- ///
- /// \ref named-func-param "Named parameter"
- ///for setting ProcessedMap object.
+
+ ///\brief \ref named-func-param "Named parameter" for setting
+ ///the processed map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that indicates which nodes are processed.
template
BfsWizard > processedMap(const T &t)
@@ -1265,5 +1269,6 @@
///
/// The type of the map that indicates which nodes are reached.
- /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ /// It must conform to
+ ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
@@ -1303,9 +1308,9 @@
/// does not observe the BFS events. If you want to observe the BFS
/// events, you should implement your own visitor class.
- /// \tparam TR Traits class to set various data types used by the
- /// algorithm. The default traits class is
- /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits".
- /// See \ref BfsVisitDefaultTraits for the documentation of
- /// a BFS visit traits class.
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm. By default, it is \ref BfsVisitDefaultTraits
+ /// "BfsVisitDefaultTraits".
+ /// In most cases, this parameter should not be set directly,
+ /// consider to use the named template parameters instead.
#ifdef DOXYGEN
template
@@ -1426,6 +1431,6 @@
/// The simplest way to execute the BFS algorithm is to use one of the
/// member functions called \ref run(Node) "run()".\n
- /// If you need more control on the execution, first you have to call
- /// \ref init(), then you can add several source nodes with
+ /// If you need better control on the execution, you have to call
+ /// \ref init() first, then you can add several source nodes with
/// \ref addSource(). Finally the actual path computation can be
/// performed with one of the \ref start() functions.
@@ -1699,10 +1704,6 @@
/// \brief Runs the algorithm to visit all nodes in the digraph.
///
- /// This method runs the %BFS algorithm in order to
- /// compute the shortest path to each node.
- ///
- /// The algorithm computes
- /// - the shortest path tree (forest),
- /// - the distance of each node from the root(s).
+ /// This method runs the %BFS algorithm in order to visit all nodes
+ /// in the digraph.
///
/// \note b.run(s) is just a shortcut of the following code.
@@ -1736,5 +1737,5 @@
///@{
- /// \brief Checks if a node is reached from the root(s).
+ /// \brief Checks if the given node is reached from the root(s).
///
/// Returns \c true if \c v is reached from the root(s).
Index: lemon/bin_heap.h
===================================================================
--- lemon/bin_heap.h (revision 912)
+++ lemon/bin_heap.h (revision 758)
@@ -20,7 +20,7 @@
#define LEMON_BIN_HEAP_H
-///\ingroup auxdat
+///\ingroup heaps
///\file
-///\brief Binary Heap implementation.
+///\brief Binary heap implementation.
#include
@@ -30,43 +30,39 @@
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.
- ///
- ///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 Comp specifies the ordering of the priorities.
- ///In a heap one can change the priority of an item, add or erase an
- ///item, etc.
+ /// This class implements the \e binary \e heap data structure.
+ /// It fully conforms to the \ref concepts::Heap "heap concept".
///
- ///\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 Comp A functor class for the ordering of the priorities.
- ///The default is \c std::less.
- ///
- ///\sa FibHeap
- ///\sa Dijkstra
- template >
+ /// \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
- typedef Comp 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
+ /// Functor type for comparing the priorities.
+ typedef CMP Compare;
+
+ /// \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.
///
@@ -85,40 +81,41 @@
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();
@@ -128,10 +125,10 @@
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]) ) {
@@ -144,6 +141,6 @@
}
- 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]) ) {
@@ -154,5 +151,5 @@
move(_data[child], hole);
hole = child;
- child = second_child(hole);
+ child = secondChild(hole);
}
child--;
@@ -172,42 +169,45 @@
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() {
@@ -215,14 +215,15 @@
_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];
@@ -230,6 +231,6 @@
_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);
}
}
@@ -237,10 +238,9 @@
}
-
- /// \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];
@@ -248,9 +248,10 @@
}
- /// \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.
@@ -261,42 +262,40 @@
}
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 {
@@ -307,9 +306,9 @@
}
- /// \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.
@@ -328,10 +327,11 @@
}
- /// \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];
Index: lemon/binomial_heap.h
===================================================================
--- lemon/binomial_heap.h (revision 956)
+++ lemon/binomial_heap.h (revision 956)
@@ -0,0 +1,445 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_BINOMIAL_HEAP_H
+#define LEMON_BINOMIAL_HEAP_H
+
+///\file
+///\ingroup heaps
+///\brief Binomial Heap implementation.
+
+#include
+#include
+#include
+#include
+#include
+
+namespace lemon {
+
+ /// \ingroup heaps
+ ///
+ ///\brief Binomial heap data structure.
+ ///
+ /// This class implements the \e binomial \e heap data structure.
+ /// It fully conforms to the \ref concepts::Heap "heap concept".
+ ///
+ /// The methods \ref increase() and \ref erase() are not efficient
+ /// in a binomial heap. In case of many calls of these operations,
+ /// it is better to use other heap structure, e.g. \ref BinHeap
+ /// "binary heap".
+ ///
+ /// \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 BinomialHeap {
+ public:
+ /// Type of the item-int map.
+ typedef IM ItemIntMap;
+ /// Type of the priorities.
+ typedef PR Prio;
+ /// Type of the items stored in the heap.
+ typedef typename ItemIntMap::Key Item;
+ /// Functor type for comparing the priorities.
+ typedef CMP Compare;
+
+ /// \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.
+ ///
+ /// The item-int map must be initialized in such way that it assigns
+ /// \c PRE_HEAP (-1) to any element to be put in the heap.
+ enum State {
+ IN_HEAP = 0, ///< = 0.
+ PRE_HEAP = -1, ///< = -1.
+ POST_HEAP = -2 ///< = -2.
+ };
+
+ private:
+ class Store;
+
+ std::vector _data;
+ int _min, _head;
+ ItemIntMap &_iim;
+ Compare _comp;
+ int _num_items;
+
+ public:
+ /// \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 BinomialHeap(ItemIntMap &map)
+ : _min(0), _head(-1), _iim(map), _num_items(0) {}
+
+ /// \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.
+ BinomialHeap(ItemIntMap &map, const Compare &comp)
+ : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
+
+ /// \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_items; }
+
+ /// \brief Check if the heap is empty.
+ ///
+ /// This function returns \c true if the heap is empty.
+ bool empty() const { return _num_items==0; }
+
+ /// \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(); _min=0; _num_items=0; _head=-1;
+ }
+
+ /// \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 item The item.
+ /// \param value The priority.
+ void set (const Item& item, const Prio& value) {
+ int i=_iim[item];
+ if ( i >= 0 && _data[i].in ) {
+ if ( _comp(value, _data[i].prio) ) decrease(item, value);
+ if ( _comp(_data[i].prio, value) ) increase(item, value);
+ } else push(item, value);
+ }
+
+ /// \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 item The item to insert.
+ /// \param value The priority of the item.
+ /// \pre \e item must not be stored in the heap.
+ void push (const Item& item, const Prio& value) {
+ int i=_iim[item];
+ if ( i<0 ) {
+ int s=_data.size();
+ _iim.set( item,s );
+ Store st;
+ st.name=item;
+ st.prio=value;
+ _data.push_back(st);
+ i=s;
+ }
+ else {
+ _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
+ _data[i].degree=0;
+ _data[i].in=true;
+ _data[i].prio=value;
+ }
+
+ if( 0==_num_items ) {
+ _head=i;
+ _min=i;
+ } else {
+ merge(i);
+ if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
+ }
+ ++_num_items;
+ }
+
+ /// \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[_min].name; }
+
+ /// \brief The minimum priority.
+ ///
+ /// This function returns the minimum priority.
+ /// \pre The heap must be non-empty.
+ Prio prio() const { return _data[_min].prio; }
+
+ /// \brief The priority of the given item.
+ ///
+ /// This function returns the priority of the given item.
+ /// \param item The item.
+ /// \pre \e item must be in the heap.
+ const Prio& operator[](const Item& item) const {
+ return _data[_iim[item]].prio;
+ }
+
+ /// \brief Remove the item having minimum priority.
+ ///
+ /// This function removes the item having minimum priority.
+ /// \pre The heap must be non-empty.
+ void pop() {
+ _data[_min].in=false;
+
+ int head_child=-1;
+ if ( _data[_min].child!=-1 ) {
+ int child=_data[_min].child;
+ int neighb;
+ while( child!=-1 ) {
+ neighb=_data[child].right_neighbor;
+ _data[child].parent=-1;
+ _data[child].right_neighbor=head_child;
+ head_child=child;
+ child=neighb;
+ }
+ }
+
+ if ( _data[_head].right_neighbor==-1 ) {
+ // there was only one root
+ _head=head_child;
+ }
+ else {
+ // there were more roots
+ if( _head!=_min ) { unlace(_min); }
+ else { _head=_data[_head].right_neighbor; }
+ merge(head_child);
+ }
+ _min=findMin();
+ --_num_items;
+ }
+
+ /// \brief Remove the given item from the heap.
+ ///
+ /// This function removes the given item from the heap if it is
+ /// already stored.
+ /// \param item The item to delete.
+ /// \pre \e item must be in the heap.
+ void erase (const Item& item) {
+ int i=_iim[item];
+ if ( i >= 0 && _data[i].in ) {
+ decrease( item, _data[_min].prio-1 );
+ pop();
+ }
+ }
+
+ /// \brief Decrease the priority of an item to the given value.
+ ///
+ /// This function decreases the priority of an item to the given value.
+ /// \param item The item.
+ /// \param value The priority.
+ /// \pre \e item must be stored in the heap with priority at least \e value.
+ void decrease (Item item, const Prio& value) {
+ int i=_iim[item];
+ int p=_data[i].parent;
+ _data[i].prio=value;
+
+ while( p!=-1 && _comp(value, _data[p].prio) ) {
+ _data[i].name=_data[p].name;
+ _data[i].prio=_data[p].prio;
+ _data[p].name=item;
+ _data[p].prio=value;
+ _iim[_data[i].name]=i;
+ i=p;
+ p=_data[p].parent;
+ }
+ _iim[item]=i;
+ if ( _comp(value, _data[_min].prio) ) _min=i;
+ }
+
+ /// \brief Increase the priority of an item to the given value.
+ ///
+ /// This function increases the priority of an item to the given value.
+ /// \param item The item.
+ /// \param value The priority.
+ /// \pre \e item must be stored in the heap with priority at most \e value.
+ void increase (Item item, const Prio& value) {
+ erase(item);
+ push(item, value);
+ }
+
+ /// \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 item The item.
+ State state(const Item &item) const {
+ int i=_iim[item];
+ if( i>=0 ) {
+ if ( _data[i].in ) i=0;
+ else i=-2;
+ }
+ return State(i);
+ }
+
+ /// \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.
+ void state(const Item& i, State st) {
+ switch (st) {
+ case POST_HEAP:
+ case PRE_HEAP:
+ if (state(i) == IN_HEAP) {
+ erase(i);
+ }
+ _iim[i] = st;
+ break;
+ case IN_HEAP:
+ break;
+ }
+ }
+
+ private:
+
+ // Find the minimum of the roots
+ int findMin() {
+ if( _head!=-1 ) {
+ int min_loc=_head, min_val=_data[_head].prio;
+ for( int x=_data[_head].right_neighbor; x!=-1;
+ x=_data[x].right_neighbor ) {
+ if( _comp( _data[x].prio,min_val ) ) {
+ min_val=_data[x].prio;
+ min_loc=x;
+ }
+ }
+ return min_loc;
+ }
+ else return -1;
+ }
+
+ // Merge the heap with another heap starting at the given position
+ void merge(int a) {
+ if( _head==-1 || a==-1 ) return;
+ if( _data[a].right_neighbor==-1 &&
+ _data[a].degree<=_data[_head].degree ) {
+ _data[a].right_neighbor=_head;
+ _head=a;
+ } else {
+ interleave(a);
+ }
+ if( _data[_head].right_neighbor==-1 ) return;
+
+ int x=_head;
+ int x_prev=-1, x_next=_data[x].right_neighbor;
+ while( x_next!=-1 ) {
+ if( _data[x].degree!=_data[x_next].degree ||
+ ( _data[x_next].right_neighbor!=-1 &&
+ _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
+ x_prev=x;
+ x=x_next;
+ }
+ else {
+ if( _comp(_data[x_next].prio,_data[x].prio) ) {
+ if( x_prev==-1 ) {
+ _head=x_next;
+ } else {
+ _data[x_prev].right_neighbor=x_next;
+ }
+ fuse(x,x_next);
+ x=x_next;
+ }
+ else {
+ _data[x].right_neighbor=_data[x_next].right_neighbor;
+ fuse(x_next,x);
+ }
+ }
+ x_next=_data[x].right_neighbor;
+ }
+ }
+
+ // Interleave the elements of the given list into the list of the roots
+ void interleave(int a) {
+ int p=_head, q=a;
+ int curr=_data.size();
+ _data.push_back(Store());
+
+ while( p!=-1 || q!=-1 ) {
+ if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
+ _data[curr].right_neighbor=p;
+ curr=p;
+ p=_data[p].right_neighbor;
+ }
+ else {
+ _data[curr].right_neighbor=q;
+ curr=q;
+ q=_data[q].right_neighbor;
+ }
+ }
+
+ _head=_data.back().right_neighbor;
+ _data.pop_back();
+ }
+
+ // Lace node a under node b
+ void fuse(int a, int b) {
+ _data[a].parent=b;
+ _data[a].right_neighbor=_data[b].child;
+ _data[b].child=a;
+
+ ++_data[b].degree;
+ }
+
+ // Unlace node a (if it has siblings)
+ void unlace(int a) {
+ int neighb=_data[a].right_neighbor;
+ int other=_head;
+
+ while( _data[other].right_neighbor!=a )
+ other=_data[other].right_neighbor;
+ _data[other].right_neighbor=neighb;
+ }
+
+ private:
+
+ class Store {
+ friend class BinomialHeap;
+
+ Item name;
+ int parent;
+ int right_neighbor;
+ int child;
+ int degree;
+ bool in;
+ Prio prio;
+
+ Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
+ in(true) {}
+ };
+ };
+
+} //namespace lemon
+
+#endif //LEMON_BINOMIAL_HEAP_H
+
Index: lemon/bits/array_map.h
===================================================================
--- lemon/bits/array_map.h (revision 664)
+++ lemon/bits/array_map.h (revision 956)
@@ -3,5 +3,5 @@
* 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).
@@ -71,5 +71,5 @@
private:
-
+
// The MapBase of the Map which imlements the core regisitry function.
typedef typename Notifier::ObserverBase Parent;
Index: lemon/bits/default_map.h
===================================================================
--- lemon/bits/default_map.h (revision 674)
+++ lemon/bits/default_map.h (revision 956)
@@ -3,5 +3,5 @@
* 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).
@@ -158,5 +158,5 @@
public:
typedef DefaultMap<_Graph, _Item, _Value> Map;
-
+
typedef typename Parent::GraphType GraphType;
typedef typename Parent::Value Value;
Index: lemon/bits/edge_set_extender.h
===================================================================
--- lemon/bits/edge_set_extender.h (revision 967)
+++ lemon/bits/edge_set_extender.h (revision 968)
@@ -1,7 +1,7 @@
-/* -*- 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).
@@ -64,9 +64,9 @@
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;
}
@@ -92,5 +92,5 @@
// Iterable extensions
- class NodeIt : public Node {
+ class NodeIt : public Node {
const Digraph* digraph;
public:
@@ -101,19 +101,19 @@
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