diff --git a/.hgignore b/.hgignore
--- a/.hgignore
+++ b/.hgignore
@@ -22,6 +22,7 @@
lemon/libemon.la
lemon/stamp-h2
doc/Doxyfile
+doc/references.dox
cmake/version.cmake
.dirstamp
.libs/*
diff --git a/CMakeLists.txt b/CMakeLists.txt
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -114,6 +114,8 @@
CHECK_TYPE_SIZE("long long" LONG_LONG)
SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
+INCLUDE(FindPythonInterp)
+
ENABLE_TESTING()
IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
diff --git a/INSTALL b/INSTALL
--- a/INSTALL
+++ b/INSTALL
@@ -173,3 +173,25 @@
--without-coin
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"'.
diff --git a/Makefile.am b/Makefile.am
--- a/Makefile.am
+++ b/Makefile.am
@@ -44,6 +44,7 @@
include test/Makefile.am
include doc/Makefile.am
include tools/Makefile.am
+include scripts/Makefile.am
DIST_SUBDIRS = demo
diff --git a/README b/README
--- a/README
+++ b/README
@@ -17,6 +17,10 @@
Copying, distribution and modification conditions and terms.
+NEWS
+
+ News and version history.
+
INSTALL
General building and installation instructions.
@@ -33,6 +37,10 @@
Some example programs to make you easier to get familiar with LEMON.
+scripts/
+
+ Scripts that make it easier to develop LEMON.
+
test/
Programs to check the integrity and correctness of LEMON.
diff --git a/configure.ac b/configure.ac
--- a/configure.ac
+++ b/configure.ac
@@ -41,6 +41,7 @@
AC_PROG_LIBTOOL
AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
+AC_CHECK_PROG([python_found],[python],[yes],[no])
AC_CHECK_PROG([gs_found],[gs],[yes],[no])
dnl Detect Intel compiler.
@@ -82,6 +83,21 @@
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.
AC_CHECK_HEADERS(limits.h sys/time.h sys/times.h unistd.h)
@@ -128,6 +144,7 @@
echo CBC support................... : $lx_cbc_found
echo
echo Build additional tools........ : $enable_tools
+echo Use valgrind for tests........ : $use_valgrind
echo
echo The packace will be installed in
echo -n ' '
diff --git a/demo/arg_parser_demo.cc b/demo/arg_parser_demo.cc
--- a/demo/arg_parser_demo.cc
+++ b/demo/arg_parser_demo.cc
@@ -2,7 +2,7 @@
*
* 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).
*
@@ -65,9 +65,18 @@
ap.other("infile", "The input file.")
.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
std::cout << "Parameters of '" << ap.commandName() << "':\n";
diff --git a/doc/CMakeLists.txt b/doc/CMakeLists.txt
--- a/doc/CMakeLists.txt
+++ b/doc/CMakeLists.txt
@@ -17,7 +17,7 @@
@ONLY
)
-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)
ADD_CUSTOM_TARGET(html
@@ -28,14 +28,17 @@
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
COMMAND ${CMAKE_COMMAND} -E remove_directory html
+ COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
)
diff --git a/doc/Doxyfile.in b/doc/Doxyfile.in
--- a/doc/Doxyfile.in
+++ b/doc/Doxyfile.in
@@ -97,7 +97,8 @@
"@abs_top_srcdir@/demo" \
"@abs_top_srcdir@/tools" \
"@abs_top_srcdir@/test/test_tools.h" \
- "@abs_top_builddir@/doc/mainpage.dox"
+ "@abs_top_builddir@/doc/mainpage.dox" \
+ "@abs_top_builddir@/doc/references.dox"
INPUT_ENCODING = UTF-8
FILE_PATTERNS = *.h \
*.cc \
diff --git a/doc/Makefile.am b/doc/Makefile.am
--- a/doc/Makefile.am
+++ b/doc/Makefile.am
@@ -27,7 +27,9 @@
bipartite_partitions.eps \
connected_components.eps \
edge_biconnected_components.eps \
+ matching.eps \
node_biconnected_components.eps \
+ planar.eps \
strongly_connected_components.eps
DOC_EPS_IMAGES = \
@@ -66,7 +68,19 @@
exit 1; \
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; \
doxygen Doxyfile; \
diff --git a/doc/groups.dox b/doc/groups.dox
--- a/doc/groups.dox
+++ b/doc/groups.dox
@@ -2,7 +2,7 @@
*
* 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).
*
@@ -226,14 +226,6 @@
*/
/**
-@defgroup matrices Matrices
-@ingroup datas
-\brief Two dimensional data storages implemented in LEMON.
-
-This group contains two dimensional data storages implemented in LEMON.
-*/
-
-/**
@defgroup paths Path Structures
@ingroup datas
\brief %Path structures implemented in LEMON.
@@ -246,7 +238,36 @@
efficient to have e.g. the Dijkstra algorithm to store its result in
any kind of path structure.
-\sa lemon::concepts::Path
+\sa \ref concepts::Path "Path concept"
+*/
+
+/**
+@defgroup heaps Heap Structures
+@ingroup datas
+\brief %Heap structures implemented in LEMON.
+
+This group contains the heap structures implemented in LEMON.
+
+LEMON provides several heap classes. They are efficient implementations
+of the abstract data type \e priority \e queue. They store items with
+specified values called \e priorities in such a way that finding and
+removing the item with minimum priority are efficient.
+The basic operations are adding and erasing items, changing the priority
+of an item, etc.
+
+Heaps are crucial in several algorithms, such as Dijkstra and Prim.
+The heap implementations have the same interface, thus any of them can be
+used easily in such algorithms.
+
+\sa \ref concepts::Heap "Heap concept"
+*/
+
+/**
+@defgroup matrices Matrices
+@ingroup datas
+\brief Two dimensional data storages implemented in LEMON.
+
+This group contains two dimensional data storages implemented in LEMON.
*/
/**
@@ -259,6 +280,28 @@
*/
/**
+@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 matrices Matrices
+@ingroup auxdat
+\brief Two dimensional data storages implemented in LEMON.
+
+This group contains two dimensional data storages implemented in LEMON.
+*/
+
+/**
@defgroup algs Algorithms
\brief This group contains the several algorithms
implemented in LEMON.
@@ -273,7 +316,8 @@
\brief Common graph search algorithms.
This group contains the common graph search algorithms, namely
-\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
+\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
+\ref clrs01algorithms.
*/
/**
@@ -281,7 +325,8 @@
@ingroup algs
\brief Algorithms for finding shortest paths.
-This group contains the algorithms for finding shortest paths in digraphs.
+This group contains the algorithms for finding shortest paths in digraphs
+\ref clrs01algorithms.
- \ref Dijkstra algorithm for finding shortest paths from a source node
when all arc lengths are non-negative.
@@ -298,12 +343,21 @@
*/
/**
+@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
\brief Algorithms for finding maximum flows.
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
a single source and a single target. Formally, there is a \f$G=(V,A)\f$
@@ -318,17 +372,21 @@
\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
LEMON contains several algorithms for solving maximum flow problems:
-- \ref EdmondsKarp Edmonds-Karp algorithm.
-- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
-- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
-- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
+- \ref EdmondsKarp Edmonds-Karp algorithm
+ \ref edmondskarp72theoretical.
+- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
+ \ref goldberg88newapproach.
+- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
+ \ref dinic70algorithm, \ref sleator83dynamic.
+- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
+ \ref goldberg88newapproach, \ref sleator83dynamic.
-In most cases the \ref Preflow "Preflow" algorithm provides the
+In most cases the \ref Preflow algorithm provides the
fastest method for computing a maximum flow. All implementations
also provide functions to query the minimum cut, which is the dual
problem of maximum flow.
-\ref Circulation is a preflow push-relabel algorithm implemented directly
+\ref 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.
For more information, see \ref Circulation.
@@ -341,18 +399,20 @@
\brief Algorithms for finding minimum cost flows and circulations.
This group contains the algorithms for finding minimum cost flows and
-circulations. For more information about this problem and its dual
-solution see \ref min_cost_flow "Minimum Cost Flow Problem".
+circulations \ref amo93networkflows. For more information about this
+problem and its dual solution, see \ref min_cost_flow
+"Minimum Cost Flow Problem".
LEMON contains several algorithms for this problem.
- \ref NetworkSimplex Primal Network Simplex algorithm with various
- pivot strategies.
- - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
- cost scaling.
- - \ref CapacityScaling Successive Shortest %Path algorithm with optional
- capacity scaling.
- - \ref CancelAndTighten The Cancel and Tighten algorithm.
- - \ref CycleCanceling Cycle-Canceling algorithms.
+ pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
+ - \ref CostScaling Cost Scaling algorithm based on push/augment and
+ relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
+ \ref bunnagel98efficient.
+ - \ref CapacityScaling Capacity Scaling algorithm based on the successive
+ shortest path method \ref edmondskarp72theoretical.
+ - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
+ strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
In general NetworkSimplex is the most efficient implementation,
but in special cases other algorithms could be faster.
@@ -375,7 +435,7 @@
cut is the \f$X\f$ solution of the next optimization problem:
\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:
@@ -391,27 +451,40 @@
*/
/**
-@defgroup graph_properties Connectivity and Other Graph Properties
+@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
@ingroup algs
-\brief Algorithms for discovering the graph properties
+\brief Algorithms for finding minimum mean cycles.
-This group contains the algorithms for discovering the graph properties
-like connectivity, bipartiteness, euler property, simplicity etc.
+This group contains the algorithms for finding minimum mean cycles
+\ref clrs01algorithms, \ref amo93networkflows.
-\image html edge_biconnected_components.png
-\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
-*/
+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.
-/**
-@defgroup planar Planarity Embedding and Drawing
-@ingroup algs
-\brief Algorithms for planarity checking, embedding and drawing
+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.
-This group contains the algorithms for planarity checking,
-embedding and drawing.
+LEMON contains three algorithms for solving the minimum mean cycle problem:
+- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
+ \ref dasdan98minmeancycle.
+- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
+ version of Karp's algorithm \ref dasdan98minmeancycle.
+- \ref Howard "Howard"'s policy iteration algorithm
+ \ref dasdan98minmeancycle.
-\image html planar.png
-\image latex planar.eps "Plane graph" width=\textwidth
+In practice, the Howard algorithm proved to be by far the most efficient
+one, though the best known theoretical bound on its running time is
+exponential.
+Both Karp and HartmannOrlin 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.
*/
/**
@@ -449,18 +522,49 @@
- \ref MaxWeightedPerfectMatching
Edmond's blossom shrinking algorithm for calculating maximum weighted
perfect matching in general graphs.
+- \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 bipartite_matching.png
-\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
+\image html matching.png
+\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
*/
/**
-@defgroup spantree Minimum Spanning Tree Algorithms
+@defgroup graph_properties Connectivity and Other Graph Properties
@ingroup algs
-\brief Algorithms for finding minimum cost spanning trees and arborescences.
+\brief Algorithms for discovering the graph properties
-This group contains the algorithms for finding minimum cost spanning
-trees and arborescences.
+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
+*/
+
+/**
+@defgroup approx Approximation Algorithms
+@ingroup algs
+\brief Approximation algorithms.
+
+This group contains the approximation and heuristic algorithms
+implemented in LEMON.
*/
/**
@@ -473,15 +577,6 @@
*/
/**
-@defgroup approx Approximation Algorithms
-@ingroup algs
-\brief Approximation algorithms.
-
-This group contains the approximation and heuristic algorithms
-implemented in LEMON.
-*/
-
-/**
@defgroup gen_opt_group General Optimization Tools
\brief This group contains some general optimization frameworks
implemented in LEMON.
@@ -491,13 +586,16 @@
*/
/**
-@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.
+\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.
+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.
*/
/**
@@ -587,7 +685,7 @@
*/
/**
-@defgroup dimacs_group DIMACS format
+@defgroup dimacs_group DIMACS Format
@ingroup io_group
\brief Read and write files in DIMACS format
@@ -636,8 +734,8 @@
@ingroup concept
\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.
*/
/**
@@ -649,6 +747,15 @@
*/
/**
+@defgroup tools Standalone Utility Applications
+
+Some utility applications are listed here.
+
+The standard compilation procedure (./configure;make) will compile
+them, as well.
+*/
+
+/**
\anchor demoprograms
@defgroup demos Demo Programs
@@ -660,13 +767,4 @@
make check commands.
*/
-/**
-@defgroup tools Standalone Utility Applications
-
-Some utility applications are listed here.
-
-The standard compilation procedure (./configure;make) will compile
-them, as well.
-*/
-
}
diff --git a/doc/images/matching.eps b/doc/images/matching.eps
new file mode 100644
--- /dev/null
+++ b/doc/images/matching.eps
@@ -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
diff --git a/doc/images/planar.eps b/doc/images/planar.eps
new file mode 100644
--- /dev/null
+++ b/doc/images/planar.eps
@@ -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
diff --git a/doc/mainpage.dox.in b/doc/mainpage.dox.in
--- a/doc/mainpage.dox.in
+++ b/doc/mainpage.dox.in
@@ -2,7 +2,7 @@
*
* 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,14 +21,11 @@
\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.
LEMON is an open source
@@ -38,11 +35,24 @@
\ref license "license terms".
-\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
Modules section.
diff --git a/doc/min_cost_flow.dox b/doc/min_cost_flow.dox
--- a/doc/min_cost_flow.dox
+++ b/doc/min_cost_flow.dox
@@ -2,7 +2,7 @@
*
* 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).
*
@@ -26,7 +26,7 @@
The \e minimum \e cost \e flow \e problem is to find a feasible flow of
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$,
\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
@@ -78,10 +78,10 @@
- if \f$lower(uv)=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$.
diff --git a/doc/references.bib b/doc/references.bib
new file mode 100644
--- /dev/null
+++ b/doc/references.bib
@@ -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,
+}
diff --git a/lemon/Makefile.am b/lemon/Makefile.am
--- a/lemon/Makefile.am
+++ b/lemon/Makefile.am
@@ -58,19 +58,25 @@
lemon/adaptors.h \
lemon/arg_parser.h \
lemon/assert.h \
+ lemon/bellman_ford.h \
lemon/bfs.h \
lemon/bin_heap.h \
+ lemon/binomial_heap.h \
lemon/bucket_heap.h \
+ lemon/capacity_scaling.h \
lemon/cbc.h \
lemon/circulation.h \
lemon/clp.h \
lemon/color.h \
lemon/concept_check.h \
lemon/connectivity.h \
+ lemon/core.h \
+ lemon/cost_scaling.h \
lemon/counter.h \
- lemon/core.h \
lemon/cplex.h \
+ lemon/cycle_canceling.h \
lemon/dfs.h \
+ lemon/dheap.h \
lemon/dijkstra.h \
lemon/dim2.h \
lemon/dimacs.h \
@@ -79,12 +85,16 @@
lemon/error.h \
lemon/euler.h \
lemon/fib_heap.h \
+ lemon/fractional_matching.h \
lemon/full_graph.h \
lemon/glpk.h \
lemon/gomory_hu.h \
lemon/graph_to_eps.h \
lemon/grid_graph.h \
+ lemon/hartmann_orlin_mmc.h \
+ lemon/howard_mmc.h \
lemon/hypercube_graph.h \
+ lemon/karp_mmc.h \
lemon/kruskal.h \
lemon/hao_orlin.h \
lemon/lgf_reader.h \
@@ -99,13 +109,17 @@
lemon/min_cost_arborescence.h \
lemon/nauty_reader.h \
lemon/network_simplex.h \
+ lemon/pairing_heap.h \
lemon/path.h \
+ lemon/planarity.h \
lemon/preflow.h \
+ lemon/quad_heap.h \
lemon/radix_heap.h \
lemon/radix_sort.h \
lemon/random.h \
lemon/smart_graph.h \
lemon/soplex.h \
+ lemon/static_graph.h \
lemon/suurballe.h \
lemon/time_measure.h \
lemon/tolerance.h \
diff --git a/lemon/adaptors.h b/lemon/adaptors.h
--- a/lemon/adaptors.h
+++ b/lemon/adaptors.h
@@ -2,7 +2,7 @@
*
* 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).
*
@@ -360,6 +360,9 @@
/// 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
+ /// digraph structure.
+ ///
/// \tparam DGR The type of the adapted digraph.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
/// It can also be specified to be \c const.
@@ -418,7 +421,7 @@
void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
Parent::initialize(digraph);
_node_filter = &node_filter;
- _arc_filter = &arc_filter;
+ _arc_filter = &arc_filter;
}
public:
@@ -505,11 +508,11 @@
public:
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:
typedef V Value;
@@ -532,9 +535,9 @@
};
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;
@@ -579,7 +582,7 @@
void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
Parent::initialize(digraph);
_node_filter = &node_filter;
- _arc_filter = &arc_filter;
+ _arc_filter = &arc_filter;
}
public:
@@ -648,10 +651,10 @@
}
template
- class NodeMap
+ class NodeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent;
public:
@@ -675,7 +678,7 @@
};
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> {
typedef SubMapExtender,
@@ -719,6 +722,8 @@
/// 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.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
/// It can also be specified to be \c const.
@@ -1016,10 +1021,10 @@
}
template
- class NodeMap
+ class NodeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent;
public:
@@ -1043,10 +1048,10 @@
};
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent;
public:
@@ -1070,10 +1075,10 @@
};
template
- class EdgeMap
+ class EdgeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent;
public:
@@ -1112,8 +1117,8 @@
protected:
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) {
Parent::initialize(graph);
@@ -1214,10 +1219,10 @@
}
template
- class NodeMap
+ class NodeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent;
public:
@@ -1241,10 +1246,10 @@
};
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent;
public:
@@ -1268,11 +1273,11 @@
};
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:
typedef V Value;
@@ -1314,6 +1319,8 @@
/// 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.
/// It must conform to the \ref concepts::Graph "Graph" concept.
/// It can also be specified to be \c const.
@@ -1471,6 +1478,8 @@
/// 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.
/// It must conform to the \ref concepts::Digraph "Digraph" concept
/// or the \ref concepts::Graph "Graph" concept.
@@ -1495,7 +1504,7 @@
true> > {
#endif
typedef DigraphAdaptorExtender<
- SubDigraphBase >,
+ SubDigraphBase >,
true> > Parent;
public:
@@ -1516,7 +1525,7 @@
///
/// 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()
{
Parent::initialize(graph, node_filter, const_true_map);
@@ -1554,11 +1563,11 @@
class FilterNodes >::type> :
public GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
true> > {
typedef GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
true> > Parent;
public:
@@ -1619,6 +1628,8 @@
/// 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.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
/// It can also be specified to be \c const.
@@ -1642,7 +1653,7 @@
AF, false> > {
#endif
typedef DigraphAdaptorExtender<
- SubDigraphBase >,
+ SubDigraphBase >,
AF, false> > Parent;
public:
@@ -1729,6 +1740,8 @@
/// 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.
/// It must conform to the \ref concepts::Graph "Graph" concept.
/// It can also be specified to be \c const.
@@ -1748,11 +1761,11 @@
typename EF = typename GR::template EdgeMap >
class FilterEdges :
public GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
EF, false> > {
#endif
typedef GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
EF, false> > Parent;
public:
@@ -1777,7 +1790,7 @@
///
/// 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);
}
@@ -1845,7 +1858,7 @@
Edge _edge;
bool _forward;
- Arc(const Edge& edge, bool forward)
+ Arc(const Edge& edge, bool forward)
: _edge(edge), _forward(forward) {}
public:
@@ -2085,7 +2098,7 @@
_forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
ArcMapBase(const UndirectorBase& adaptor, const V& value)
- : _forward(*adaptor._digraph, value),
+ : _forward(*adaptor._digraph, value),
_backward(*adaptor._digraph, value) {}
void set(const Arc& a, const V& value) {
@@ -2203,7 +2216,7 @@
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,6 +2245,9 @@
/// 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.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
/// It can also be specified to be \c const.
@@ -2535,6 +2551,9 @@
/// 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.
/// It must conform to the \ref concepts::Graph "Graph" concept.
/// It can also be specified to be \c const.
@@ -2678,6 +2697,8 @@
/// arcs).
/// 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.
/// It is implicitly \c const.
@@ -2707,7 +2728,7 @@
typename CM = typename DGR::template ArcMap,
typename FM = CM,
typename TL = Tolerance >
- class ResidualDigraph
+ class ResidualDigraph
: public SubDigraph<
Undirector,
ConstMap >,
@@ -2764,7 +2785,7 @@
/// digraph, the capacity map, the flow map, and a tolerance object.
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),
_backward_filter(capacity, flow, tolerance),
@@ -2846,7 +2867,7 @@
typedef typename CapacityMap::Value Value;
/// Constructor
- ResidualCapacity(const ResidualDigraph& adaptor)
+ ResidualCapacity(const ResidualDigraph& adaptor)
: _adaptor(&adaptor) {}
/// Returns the value associated with the given residual arc
@@ -3325,6 +3346,9 @@
/// costs/capacities of the original digraph to the \e bind \e arcs
/// 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.
/// It is implicitly \c const.
@@ -3423,7 +3447,7 @@
/// This map adaptor class adapts two node maps of the original digraph
/// 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
class CombinedNodeMap {
diff --git a/lemon/arg_parser.cc b/lemon/arg_parser.cc
--- a/lemon/arg_parser.cc
+++ b/lemon/arg_parser.cc
@@ -2,7 +2,7 @@
*
* 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).
*
@@ -20,14 +20,23 @@
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");
synonym("h","-help");
@@ -342,7 +351,7 @@
for(std::vector::const_iterator i=_others_help.begin();
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);
}
@@ -351,7 +360,7 @@
std::cerr << "\nUnknown option: " << arg << "\n";
std::cerr << "\nType '" << _command_name <<
" --help' to obtain a short summary on the usage.\n\n";
- exit(1);
+ _terminate(ArgParserException::UNKNOWN_OPT);
}
void ArgParser::requiresValue(std::string arg, OptType t) const
@@ -414,7 +423,7 @@
if(!ok) {
std::cerr << "\nType '" << _command_name <<
" --help' to obtain a short summary on the usage.\n\n";
- exit(1);
+ _terminate(ArgParserException::INVALID_OPT);
}
}
diff --git a/lemon/arg_parser.h b/lemon/arg_parser.h
--- a/lemon/arg_parser.h
+++ b/lemon/arg_parser.h
@@ -2,7 +2,7 @@
*
* 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).
*
@@ -34,6 +34,44 @@
namespace lemon {
+ ///Exception used by ArgParser
+ class ArgParserException : public Exception {
+ public:
+ 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
///\ingroup misc
@@ -116,6 +154,10 @@
const std::string &help,
void (*func)(void *),void *data);
+ bool _exit_on_problems;
+
+ void _terminate(ArgParserException::Reason reason) const;
+
public:
///Constructor
@@ -380,6 +422,11 @@
///not starting with a '-' character.
const std::vector &files() const { return _file_args; }
+ ///Throw instead of exit in case of problems
+ void throwOnProblems()
+ {
+ _exit_on_problems=false;
+ }
};
}
diff --git a/lemon/bellman_ford.h b/lemon/bellman_ford.h
new file mode 100644
--- /dev/null
+++ b/lemon/bellman_ford.h
@@ -0,0 +1,1165 @@
+/* -*- 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
+
+#include
+
+namespace lemon {
+
+ /// \brief Default operation traits 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.
+ ///
+ /// \see BellmanFordToleranceOperationTraits
+ template <
+ typename V,
+ bool has_inf = std::numeric_limits::has_infinity>
+ struct BellmanFordDefaultOperationTraits {
+ /// \brief Value type for the algorithm.
+ 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 Operation traits for the BellmanFord algorithm class
+ /// using tolerance.
+ ///
+ /// This operation traits class defines all computational operations
+ /// and constants that are used in the Bellman-Ford algorithm.
+ /// The only difference between this implementation and
+ /// \ref BellmanFordDefaultOperationTraits is that this class uses
+ /// the \ref Tolerance "tolerance technique" in its \ref less()
+ /// function.
+ ///
+ /// \tparam V The value type.
+ /// \tparam eps The epsilon value for the \ref less() function.
+ /// By default, it is the epsilon value used by \ref Tolerance
+ /// "Tolerance".
+ ///
+ /// \see BellmanFordDefaultOperationTraits
+#ifdef DOXYGEN
+ template
+#else
+ template <
+ typename V,
+ V eps = Tolerance::def_epsilon>
+#endif
+ struct BellmanFordToleranceOperationTraits {
+ /// \brief Value type for the algorithm.
+ 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 + eps < 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,
+ /// BellmanFordToleranceOperationTraits
+ 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,
+ /// BellmanFordToleranceOperationTraits
+ 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
+
diff --git a/lemon/bfs.h b/lemon/bfs.h
--- a/lemon/bfs.h
+++ b/lemon/bfs.h
@@ -2,7 +2,7 @@
*
* 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).
*
@@ -47,7 +47,7 @@
///
///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.
@@ -62,7 +62,8 @@
///The type of the map that indicates which nodes are processed.
///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.
@@ -81,7 +82,8 @@
///The type of the map that indicates which nodes are reached.
///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.
@@ -96,7 +98,7 @@
///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 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.
@@ -120,6 +122,11 @@
///
///\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
@@ -225,7 +232,7 @@
///
///\ref named-templ-param "Named parameter" for setting
///\c PredMap type.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetPredMap : public Bfs< Digraph, SetPredMapTraits > {
typedef Bfs< Digraph, SetPredMapTraits > Create;
@@ -245,7 +252,7 @@
///
///\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 > {
typedef Bfs< Digraph, SetDistMapTraits > Create;
@@ -265,7 +272,8 @@
///
///\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 > {
typedef Bfs< Digraph, SetReachedMapTraits > Create;
@@ -285,7 +293,7 @@
///
///\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 > {
typedef Bfs< Digraph, SetProcessedMapTraits > Create;
@@ -413,8 +421,8 @@
///\name Execution Control
///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.
@@ -700,12 +708,8 @@
///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.
///\code
@@ -737,9 +741,9 @@
///@{
- ///The shortest path to a node.
+ ///The shortest path to the given node.
- ///Returns the shortest path to a node.
+ ///Returns the shortest path to the given node from the root(s).
///
///\warning \c t should be reached from the root(s).
///
@@ -747,9 +751,9 @@
///must be called before using this function.
Path path(Node t) const { return Path(*G, *_pred, t); }
- ///The distance of a node from the root(s).
+ ///The distance of the given node from the root(s).
- ///Returns the distance of a 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.
@@ -758,29 +762,31 @@
///must be called before using this function.
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
///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().
+ ///tree used in \ref predNode() and \ref predMap().
///
///\pre Either \ref run(Node) "run()" or \ref init()
///must be called before using this function.
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()
///must be called before using this function.
@@ -801,13 +807,13 @@
///predecessor arcs.
///
///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()
///must be called before using this function.
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).
///
@@ -833,7 +839,7 @@
///
///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.
@@ -848,8 +854,8 @@
///The type of the map that indicates which nodes are processed.
///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.
@@ -868,7 +874,8 @@
///The type of the map that indicates which nodes are reached.
///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.
@@ -883,7 +890,7 @@
///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 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.
@@ -898,18 +905,14 @@
///The type of the shortest paths.
///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;
};
/// 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
{
@@ -937,7 +940,7 @@
public:
/// 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),
_dist(0), _path(0), _di(0) {}
@@ -962,12 +965,14 @@
///
/// 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
{
typedef TR Base;
- ///The type of the digraph the algorithm runs on.
typedef typename TR::Digraph Digraph;
typedef typename Digraph::Node Node;
@@ -975,16 +980,10 @@
typedef typename Digraph::Arc Arc;
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;
public:
@@ -1054,8 +1053,8 @@
///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()
{
run(INVALID);
@@ -1067,11 +1066,12 @@
static PredMap *createPredMap(const Digraph &) { return 0; };
SetPredMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting PredMap object.
+
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///the predecessor map.
///
- ///\ref named-func-param "Named parameter"
- ///for setting PredMap object.
+ ///\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)
{
@@ -1085,11 +1085,12 @@
static ReachedMap *createReachedMap(const Digraph &) { return 0; };
SetReachedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting ReachedMap object.
+
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///the reached map.
///
- /// \ref named-func-param "Named parameter"
- ///for setting ReachedMap object.
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that indicates which nodes are reached.
template
BfsWizard > reachedMap(const T &t)
{
@@ -1103,11 +1104,13 @@
static DistMap *createDistMap(const Digraph &) { return 0; };
SetDistMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting DistMap object.
+
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///the distance map.
///
- /// \ref named-func-param "Named parameter"
- ///for setting DistMap object.
+ ///\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)
{
@@ -1121,11 +1124,12 @@
static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
SetProcessedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting ProcessedMap object.
+
+ ///\brief \ref named-func-param "Named parameter" for setting
+ ///the processed map.
///
- /// \ref named-func-param "Named parameter"
- ///for setting ProcessedMap object.
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that indicates which nodes are processed.
template
BfsWizard > processedMap(const T &t)
{
@@ -1264,7 +1268,8 @@
/// \brief The type of the map that indicates which nodes are reached.
///
/// 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;
/// \brief Instantiates a ReachedMap.
@@ -1302,11 +1307,11 @@
/// \ref BfsVisitor "BfsVisitor" is an empty visitor, which
/// 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