Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt (revision 680)
+++ CMakeLists.txt (revision 744)
@@ -35,4 +35,6 @@
CHECK_TYPE_SIZE("long long" LONG_LONG)
SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
+
+INCLUDE(FindPythonInterp)
ENABLE_TESTING()
Index: Makefile.am
===================================================================
--- Makefile.am (revision 629)
+++ Makefile.am (revision 793)
@@ -18,4 +18,5 @@
cmake/FindGLPK.cmake \
cmake/FindCOIN.cmake \
+ cmake/LEMONConfig.cmake.in \
cmake/version.cmake.in \
cmake/version.cmake \
@@ -44,4 +45,5 @@
include doc/Makefile.am
include tools/Makefile.am
+include scripts/Makefile.am
DIST_SUBDIRS = demo
Index: configure.ac
===================================================================
--- configure.ac (revision 680)
+++ configure.ac (revision 793)
@@ -42,4 +42,5 @@
AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
+AC_CHECK_PROG([python_found],[python],[yes],[no])
AC_CHECK_PROG([gs_found],[gs],[yes],[no])
@@ -82,4 +83,19 @@
fi
AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
+
+dnl Support for running test cases using valgrind.
+use_valgrind=no
+AC_ARG_ENABLE([valgrind],
+AS_HELP_STRING([--enable-valgrind], [use valgrind when running tests]),
+ [use_valgrind=yes])
+
+if [[ "$use_valgrind" = "yes" ]]; then
+ AC_CHECK_PROG(HAVE_VALGRIND, valgrind, yes, no)
+
+ if [[ "$HAVE_VALGRIND" = "no" ]]; then
+ AC_MSG_ERROR([Valgrind not found in PATH.])
+ fi
+fi
+AM_CONDITIONAL(USE_VALGRIND, [test "$use_valgrind" = "yes"])
dnl Checks for header files.
@@ -128,4 +144,5 @@
echo
echo Build additional tools........ : $enable_tools
+echo Use valgrind for tests........ : $use_valgrind
echo
echo The packace will be installed in
Index: doc/CMakeLists.txt
===================================================================
--- doc/CMakeLists.txt (revision 679)
+++ doc/CMakeLists.txt (revision 744)
@@ -10,5 +10,5 @@
)
-IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
+IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
@@ -29,4 +29,5 @@
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
COMMAND ${CMAKE_COMMAND} -E remove_directory html
+ COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
Index: doc/Doxyfile.in
===================================================================
--- doc/Doxyfile.in (revision 367)
+++ doc/Doxyfile.in (revision 756)
@@ -1,3 +1,3 @@
-# Doxyfile 1.5.7.1
+# Doxyfile 1.5.9
#---------------------------------------------------------------------------
@@ -22,5 +22,4 @@
QT_AUTOBRIEF = NO
MULTILINE_CPP_IS_BRIEF = NO
-DETAILS_AT_TOP = YES
INHERIT_DOCS = NO
SEPARATE_MEMBER_PAGES = NO
@@ -92,5 +91,6 @@
"@abs_top_srcdir@/demo" \
"@abs_top_srcdir@/tools" \
- "@abs_top_srcdir@/test/test_tools.h"
+ "@abs_top_srcdir@/test/test_tools.h" \
+ "@abs_top_builddir@/doc/references.dox"
INPUT_ENCODING = UTF-8
FILE_PATTERNS = *.h \
@@ -224,5 +224,5 @@
SKIP_FUNCTION_MACROS = YES
#---------------------------------------------------------------------------
-# Configuration::additions related to external references
+# Options related to the search engine
#---------------------------------------------------------------------------
TAGFILES = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ "
Index: doc/Makefile.am
===================================================================
--- doc/Makefile.am (revision 673)
+++ doc/Makefile.am (revision 744)
@@ -67,5 +67,17 @@
fi
-html-local: $(DOC_PNG_IMAGES)
+references.dox: doc/references.bib
+ if test ${python_found} = yes; then \
+ cd doc; \
+ python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \
+ cd ..; \
+ else \
+ echo; \
+ echo "Python not found."; \
+ echo; \
+ exit 1; \
+ fi
+
+html-local: $(DOC_PNG_IMAGES) references.dox
if test ${doxygen_found} = yes; then \
cd doc; \
Index: doc/groups.dox
===================================================================
--- doc/groups.dox (revision 710)
+++ doc/groups.dox (revision 771)
@@ -281,4 +281,26 @@
/**
+@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
@@ -295,5 +317,6 @@
This group contains the common graph search algorithms, namely
-\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
+\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
+\ref clrs01algorithms.
*/
@@ -303,5 +326,6 @@
\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
@@ -320,4 +344,13 @@
/**
+@defgroup spantree Minimum Spanning Tree Algorithms
+@ingroup algs
+\brief Algorithms for finding minimum cost spanning trees and arborescences.
+
+This group contains the algorithms for finding minimum cost spanning
+trees and arborescences \ref clrs01algorithms.
+*/
+
+/**
@defgroup max_flow Maximum Flow Algorithms
@ingroup algs
@@ -325,5 +358,5 @@
This group contains the algorithms for finding maximum flows and
-feasible circulations.
+feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
The \e maximum \e flow \e problem is to find a flow of maximum value between
@@ -340,10 +373,14 @@
LEMON contains several algorithms for solving maximum flow problems:
-- \ref EdmondsKarp Edmonds-Karp algorithm.
-- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
-- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
-- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
-
-In most cases the \ref Preflow "Preflow" algorithm provides the
+- \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 algorithm provides the
fastest method for computing a maximum flow. All implementations
also provide functions to query the minimum cut, which is the dual
@@ -363,16 +400,20 @@
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.
+ pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
- \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
- cost scaling.
+ cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
+ \ref bunnagel98efficient.
- \ref CapacityScaling Successive Shortest %Path algorithm with optional
- capacity scaling.
- - \ref CancelAndTighten The Cancel and Tighten algorithm.
- - \ref CycleCanceling Cycle-Canceling algorithms.
+ capacity scaling \ref edmondskarp72theoretical.
+ - \ref CancelAndTighten The Cancel and Tighten algorithm
+ \ref goldberg89cyclecanceling.
+ - \ref CycleCanceling Cycle-Canceling algorithms
+ \ref klein67primal, \ref goldberg89cyclecanceling.
In general NetworkSimplex is the most efficient implementation,
@@ -397,5 +438,5 @@
\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
- \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
+ \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
LEMON contains several algorithms related to minimum cut problems:
@@ -413,25 +454,38 @@
/**
-@defgroup graph_properties Connectivity and Other Graph Properties
-@ingroup algs
-\brief Algorithms for discovering the graph properties
-
-This group contains the algorithms for discovering the graph properties
-like connectivity, bipartiteness, euler property, simplicity etc.
-
-\image html edge_biconnected_components.png
-\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
-*/
-
-/**
-@defgroup planar Planarity Embedding and Drawing
-@ingroup algs
-\brief Algorithms for planarity checking, embedding and drawing
-
-This group contains the algorithms for planarity checking,
-embedding and drawing.
-
-\image html planar.png
-\image latex planar.eps "Plane graph" width=\textwidth
+@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
+@ingroup algs
+\brief Algorithms for finding minimum mean cycles.
+
+This group contains the algorithms for finding minimum mean cycles
+\ref clrs01algorithms, \ref amo93networkflows.
+
+The \e minimum \e mean \e cycle \e problem is to find a directed cycle
+of minimum mean length (cost) in a digraph.
+The mean length of a cycle is the average length of its arcs, i.e. the
+ratio between the total length of the cycle and the number of arcs on it.
+
+This problem has an important connection to \e conservative \e length
+\e functions, too. A length function on the arcs of a digraph is called
+conservative if and only if there is no directed cycle of negative total
+length. For an arbitrary length function, the negative of the minimum
+cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
+arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
+function.
+
+LEMON contains three algorithms for solving the minimum mean cycle problem:
+- \ref 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.
+
+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.
*/
@@ -477,10 +531,34 @@
/**
-@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.
+@defgroup graph_properties Connectivity and Other Graph Properties
+@ingroup algs
+\brief Algorithms for discovering the graph properties
+
+This group contains the algorithms for discovering the graph properties
+like connectivity, bipartiteness, euler property, simplicity etc.
+
+\image html connected_components.png
+\image latex connected_components.eps "Connected components" width=\textwidth
+*/
+
+/**
+@defgroup planar Planarity Embedding and Drawing
+@ingroup algs
+\brief Algorithms for planarity checking, embedding and drawing
+
+This group contains the algorithms for planarity checking,
+embedding and drawing.
+
+\image html planar.png
+\image latex planar.eps "Plane graph" width=\textwidth
+*/
+
+/**
+@defgroup approx Approximation Algorithms
+@ingroup algs
+\brief Approximation algorithms.
+
+This group contains the approximation and heuristic algorithms
+implemented in LEMON.
*/
@@ -492,13 +570,4 @@
This group contains some algorithms implemented in LEMON
in order to make it easier to implement complex algorithms.
-*/
-
-/**
-@defgroup approx Approximation Algorithms
-@ingroup algs
-\brief Approximation algorithms.
-
-This group contains the approximation and heuristic algorithms
-implemented in LEMON.
*/
@@ -513,11 +582,14 @@
/**
-@defgroup lp_group Lp and Mip Solvers
+@defgroup lp_group LP and MIP Solvers
@ingroup gen_opt_group
-\brief Lp and Mip solver interfaces for LEMON.
-
-This group contains Lp and Mip solver interfaces for LEMON. The
-various LP solvers could be used in the same manner with this
-interface.
+\brief LP and MIP solver interfaces for LEMON.
+
+This group contains LP and MIP solver interfaces for LEMON.
+Various LP solvers could be used in the same manner with this
+high-level interface.
+
+The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
+\ref cplex, \ref soplex.
*/
@@ -609,5 +681,5 @@
/**
-@defgroup dimacs_group DIMACS format
+@defgroup dimacs_group DIMACS Format
@ingroup io_group
\brief Read and write files in DIMACS format
@@ -658,6 +730,6 @@
\brief Skeleton and concept checking classes for graph structures
-This group contains the skeletons and concept checking classes of LEMON's
-graph structures and helper classes used to implement these.
+This group contains the skeletons and concept checking classes of
+graph structures.
*/
@@ -671,4 +743,13 @@
/**
+@defgroup tools Standalone Utility Applications
+
+Some utility applications are listed here.
+
+The standard compilation procedure (./configure;make) will compile
+them, as well.
+*/
+
+/**
\anchor demoprograms
@@ -682,12 +763,3 @@
*/
-/**
-@defgroup tools Standalone Utility Applications
-
-Some utility applications are listed here.
-
-The standard compilation procedure (./configure;make) will compile
-them, as well.
-*/
-
}
Index: doc/mainpage.dox
===================================================================
--- doc/mainpage.dox (revision 658)
+++ doc/mainpage.dox (revision 755)
@@ -22,12 +22,9 @@
\section intro Introduction
-\subsection whatis What is LEMON
-
-LEMON stands for Library for Efficient Modeling
-and Optimization in Networks.
-It is a C++ template
-library aimed at combinatorial optimization tasks which
-often involve in working
-with graphs.
+LEMON stands for Library for Efficient Modeling
+and Optimization in Networks.
+It is a C++ template library providing efficient implementation of common
+data structures and algorithms with focus on combinatorial optimization
+problems in graphs and networks.
@@ -39,5 +36,14 @@
-\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
Index: doc/min_cost_flow.dox
===================================================================
--- doc/min_cost_flow.dox (revision 663)
+++ doc/min_cost_flow.dox (revision 788)
@@ -27,5 +27,5 @@
minimum total cost from a set of supply nodes to a set of demand nodes
in a network with capacity constraints (lower and upper bounds)
-and arc costs.
+and arc costs \ref amo93networkflows.
Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
@@ -79,5 +79,5 @@
- if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
- For all \f$u\in V\f$ nodes:
- - \f$\pi(u)<=0\f$;
+ - \f$\pi(u)\leq 0\f$;
- if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
then \f$\pi(u)=0\f$.
@@ -146,5 +146,5 @@
- if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
- For all \f$u\in V\f$ nodes:
- - \f$\pi(u)>=0\f$;
+ - \f$\pi(u)\geq 0\f$;
- if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
then \f$\pi(u)=0\f$.
Index: doc/references.bib
===================================================================
--- doc/references.bib (revision 755)
+++ doc/references.bib (revision 755)
@@ -0,0 +1,301 @@
+%%%%% Defining LEMON %%%%%
+
+@misc{lemon,
+ key = {LEMON},
+ title = {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and
+ {O}ptimization in {N}etworks},
+ howpublished = {\url{http://lemon.cs.elte.hu/}},
+ year = 2009
+}
+
+@misc{egres,
+ key = {EGRES},
+ title = {{EGRES} -- {E}gerv{\'a}ry {R}esearch {G}roup on
+ {C}ombinatorial {O}ptimization},
+ url = {http://www.cs.elte.hu/egres/}
+}
+
+@misc{coinor,
+ key = {COIN-OR},
+ title = {{COIN-OR} -- {C}omputational {I}nfrastructure for
+ {O}perations {R}esearch},
+ url = {http://www.coin-or.org/}
+}
+
+
+%%%%% Other libraries %%%%%%
+
+@misc{boost,
+ key = {Boost},
+ title = {{B}oost {C++} {L}ibraries},
+ url = {http://www.boost.org/}
+}
+
+@book{bglbook,
+ author = {Jeremy G. Siek and Lee-Quan Lee and Andrew
+ Lumsdaine},
+ title = {The Boost Graph Library: User Guide and Reference
+ Manual},
+ publisher = {Addison-Wesley},
+ year = 2002
+}
+
+@misc{leda,
+ key = {LEDA},
+ title = {{LEDA} -- {L}ibrary of {E}fficient {D}ata {T}ypes and
+ {A}lgorithms},
+ url = {http://www.algorithmic-solutions.com/}
+}
+
+@book{ledabook,
+ author = {Kurt Mehlhorn and Stefan N{\"a}her},
+ title = {{LEDA}: {A} platform for combinatorial and geometric
+ computing},
+ isbn = {0-521-56329-1},
+ publisher = {Cambridge University Press},
+ address = {New York, NY, USA},
+ year = 1999
+}
+
+
+%%%%% Tools that LEMON depends on %%%%%
+
+@misc{cmake,
+ key = {CMake},
+ title = {{CMake} -- {C}ross {P}latform {M}ake},
+ url = {http://www.cmake.org/}
+}
+
+@misc{doxygen,
+ key = {Doxygen},
+ title = {{Doxygen} -- {S}ource code documentation generator
+ tool},
+ url = {http://www.doxygen.org/}
+}
+
+
+%%%%% LP/MIP libraries %%%%%
+
+@misc{glpk,
+ key = {GLPK},
+ title = {{GLPK} -- {GNU} {L}inear {P}rogramming {K}it},
+ url = {http://www.gnu.org/software/glpk/}
+}
+
+@misc{clp,
+ key = {Clp},
+ title = {{Clp} -- {Coin-Or} {L}inear {P}rogramming},
+ url = {http://projects.coin-or.org/Clp/}
+}
+
+@misc{cbc,
+ key = {Cbc},
+ title = {{Cbc} -- {Coin-Or} {B}ranch and {C}ut},
+ url = {http://projects.coin-or.org/Cbc/}
+}
+
+@misc{cplex,
+ key = {CPLEX},
+ title = {{ILOG} {CPLEX}},
+ url = {http://www.ilog.com/}
+}
+
+@misc{soplex,
+ key = {SoPlex},
+ title = {{SoPlex} -- {T}he {S}equential {O}bject-{O}riented
+ {S}implex},
+ url = {http://soplex.zib.de/}
+}
+
+
+%%%%% General books %%%%%
+
+@book{amo93networkflows,
+ author = {Ravindra K. Ahuja and Thomas L. Magnanti and James
+ B. Orlin},
+ title = {Network Flows: Theory, Algorithms, and Applications},
+ publisher = {Prentice-Hall, Inc.},
+ year = 1993,
+ month = feb,
+ isbn = {978-0136175490}
+}
+
+@book{schrijver03combinatorial,
+ author = {Alexander Schrijver},
+ title = {Combinatorial Optimization: Polyhedra and Efficiency},
+ publisher = {Springer-Verlag},
+ year = 2003,
+ isbn = {978-3540443896}
+}
+
+@book{clrs01algorithms,
+ author = {Thomas H. Cormen and Charles E. Leiserson and Ronald
+ L. Rivest and Clifford Stein},
+ title = {Introduction to Algorithms},
+ publisher = {The MIT Press},
+ year = 2001,
+ edition = {2nd}
+}
+
+@book{stroustrup00cpp,
+ author = {Bjarne Stroustrup},
+ title = {The C++ Programming Language},
+ edition = {3rd},
+ publisher = {Addison-Wesley Professional},
+ isbn = 0201700735,
+ month = {February},
+ year = 2000
+}
+
+
+%%%%% Maximum flow algorithms %%%%%
+
+@article{edmondskarp72theoretical,
+ author = {Jack Edmonds and Richard M. Karp},
+ title = {Theoretical improvements in algorithmic efficiency
+ for network flow problems},
+ journal = {Journal of the ACM},
+ year = 1972,
+ volume = 19,
+ number = 2,
+ pages = {248-264}
+}
+
+@article{goldberg88newapproach,
+ author = {Andrew V. Goldberg and Robert E. Tarjan},
+ title = {A new approach to the maximum flow problem},
+ journal = {Journal of the ACM},
+ year = 1988,
+ volume = 35,
+ number = 4,
+ pages = {921-940}
+}
+
+@article{dinic70algorithm,
+ author = {E. A. Dinic},
+ title = {Algorithm for solution of a problem of maximum flow
+ in a network with power estimation},
+ journal = {Soviet Math. Doklady},
+ year = 1970,
+ volume = 11,
+ pages = {1277-1280}
+}
+
+@article{goldberg08partial,
+ author = {Andrew V. Goldberg},
+ title = {The Partial Augment-Relabel Algorithm for the
+ Maximum Flow Problem},
+ journal = {16th Annual European Symposium on Algorithms},
+ year = 2008,
+ pages = {466-477}
+}
+
+@article{sleator83dynamic,
+ author = {Daniel D. Sleator and Robert E. Tarjan},
+ title = {A data structure for dynamic trees},
+ journal = {Journal of Computer and System Sciences},
+ year = 1983,
+ volume = 26,
+ number = 3,
+ pages = {362-391}
+}
+
+
+%%%%% Minimum mean cycle algorithms %%%%%
+
+@article{karp78characterization,
+ author = {Richard M. Karp},
+ title = {A characterization of the minimum cycle mean in a
+ digraph},
+ journal = {Discrete Math.},
+ year = 1978,
+ volume = 23,
+ pages = {309-311}
+}
+
+@article{dasdan98minmeancycle,
+ author = {Ali Dasdan and Rajesh K. Gupta},
+ title = {Faster Maximum and Minimum Mean Cycle Alogrithms for
+ System Performance Analysis},
+ journal = {IEEE Transactions on Computer-Aided Design of
+ Integrated Circuits and Systems},
+ year = 1998,
+ volume = 17,
+ number = 10,
+ pages = {889-899}
+}
+
+
+%%%%% Minimum cost flow algorithms %%%%%
+
+@article{klein67primal,
+ author = {Morton Klein},
+ title = {A primal method for minimal cost flows with
+ applications to the assignment and transportation
+ problems},
+ journal = {Management Science},
+ year = 1967,
+ volume = 14,
+ pages = {205-220}
+}
+
+@article{goldberg89cyclecanceling,
+ author = {Andrew V. Goldberg and Robert E. Tarjan},
+ title = {Finding minimum-cost circulations by canceling
+ negative cycles},
+ journal = {Journal of the ACM},
+ year = 1989,
+ volume = 36,
+ number = 4,
+ pages = {873-886}
+}
+
+@article{goldberg90approximation,
+ author = {Andrew V. Goldberg and Robert E. Tarjan},
+ title = {Finding Minimum-Cost Circulations by Successive
+ Approximation},
+ journal = {Mathematics of Operations Research},
+ year = 1990,
+ volume = 15,
+ number = 3,
+ pages = {430-466}
+}
+
+@article{goldberg97efficient,
+ author = {Andrew V. Goldberg},
+ title = {An Efficient Implementation of a Scaling
+ Minimum-Cost Flow Algorithm},
+ journal = {Journal of Algorithms},
+ year = 1997,
+ volume = 22,
+ number = 1,
+ pages = {1-29}
+}
+
+@article{bunnagel98efficient,
+ author = {Ursula B{\"u}nnagel and Bernhard Korte and Jens
+ Vygen},
+ title = {Efficient implementation of the {G}oldberg-{T}arjan
+ minimum-cost flow algorithm},
+ journal = {Optimization Methods and Software},
+ year = 1998,
+ volume = 10,
+ pages = {157-174}
+}
+
+@book{dantzig63linearprog,
+ author = {George B. Dantzig},
+ title = {Linear Programming and Extensions},
+ publisher = {Princeton University Press},
+ year = 1963
+}
+
+@mastersthesis{kellyoneill91netsimplex,
+ author = {Damian J. Kelly and Garrett M. O'Neill},
+ title = {The Minimum Cost Flow Problem and The Network
+ Simplex Method},
+ school = {University College},
+ address = {Dublin, Ireland},
+ year = 1991,
+ month = sep,
+}
Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am (revision 797)
+++ lemon/Makefile.am (revision 799)
@@ -87,5 +87,8 @@
lemon/graph_to_eps.h \
lemon/grid_graph.h \
+ lemon/hartmann_orlin.h \
+ lemon/howard.h \
lemon/hypercube_graph.h \
+ lemon/karp.h \
lemon/kary_heap.h \
lemon/kruskal.h \
@@ -112,4 +115,5 @@
lemon/smart_graph.h \
lemon/soplex.h \
+ lemon/static_graph.h \
lemon/suurballe.h \
lemon/time_measure.h \
Index: lemon/adaptors.h
===================================================================
--- lemon/adaptors.h (revision 656)
+++ lemon/adaptors.h (revision 787)
@@ -361,4 +361,7 @@
/// parameter is set to be \c const.
///
+ /// This class provides item counting in the same time as the adapted
+ /// digraph structure.
+ ///
/// \tparam DGR The type of the adapted digraph.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -719,4 +722,6 @@
/// by adding or removing nodes or arcs, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides only linear time counting for nodes and arcs.
///
/// \tparam DGR The type of the adapted digraph.
@@ -1315,4 +1320,6 @@
/// 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.
@@ -1471,4 +1478,6 @@
/// by adding or removing nodes or arcs/edges, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides only linear time item counting.
///
/// \tparam GR The type of the adapted digraph or graph.
@@ -1620,4 +1629,6 @@
/// 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.
@@ -1729,4 +1740,6 @@
/// by adding or removing nodes or edges, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides only linear time counting for nodes, edges and arcs.
///
/// \tparam GR The type of the adapted graph.
@@ -2233,4 +2246,7 @@
/// parameter is set to be \c const.
///
+ /// This class provides item counting in the same time as the adapted
+ /// digraph structure.
+ ///
/// \tparam DGR The type of the adapted digraph.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -2535,4 +2551,7 @@
/// by adding or removing nodes or arcs, unless the \c GR template
/// parameter is set to be \c const.
+ ///
+ /// This class provides item counting in the same time as the adapted
+ /// graph structure.
///
/// \tparam GR The type of the adapted graph.
@@ -2678,4 +2697,6 @@
/// 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.
@@ -3326,4 +3347,7 @@
/// in the adaptor.
///
+ /// This class provides item counting in the same time as the adapted
+ /// digraph structure.
+ ///
/// \tparam DGR The type of the adapted digraph.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
Index: lemon/bellman_ford.h
===================================================================
--- lemon/bellman_ford.h (revision 699)
+++ lemon/bellman_ford.h (revision 788)
@@ -24,4 +24,5 @@
/// \brief Bellman-Ford algorithm.
+#include
#include
#include
@@ -300,5 +301,5 @@
/// \ref named-templ-param "Named parameter" for setting
/// \c OperationTraits type.
- /// For more information see \ref BellmanFordDefaultOperationTraits.
+ /// For more information, see \ref BellmanFordDefaultOperationTraits.
template
struct SetOperationTraits
@@ -718,5 +719,5 @@
///
/// The shortest path tree used here is equal to the shortest path
- /// tree used in \ref predNode() and \predMap().
+ /// tree used in \ref predNode() and \ref predMap().
///
/// \pre Either \ref run() or \ref init() must be called before
@@ -733,5 +734,5 @@
///
/// The shortest path tree used here is equal to the shortest path
- /// tree used in \ref predArc() and \predMap().
+ /// tree used in \ref predArc() and \ref predMap().
///
/// \pre Either \ref run() or \ref init() must be called before
@@ -776,5 +777,5 @@
/// length if the algorithm has already found one.
/// Otherwise it gives back an empty path.
- lemon::Path negativeCycle() {
+ lemon::Path negativeCycle() const {
typename Digraph::template NodeMap state(*_gr, -1);
lemon::Path cycle;
Index: lemon/bfs.h
===================================================================
--- lemon/bfs.h (revision 492)
+++ lemon/bfs.h (revision 788)
@@ -48,5 +48,5 @@
///The type of the map that stores the predecessor
///arcs of the shortest paths.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap PredMap;
///Instantiates a \c PredMap.
@@ -63,5 +63,6 @@
///The type of the map that indicates which nodes are processed.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ ///By default, it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a \c ProcessedMap.
@@ -82,5 +83,5 @@
///The type of the map that indicates which nodes are reached.
- ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
///Instantiates a \c ReachedMap.
@@ -97,5 +98,5 @@
///The type of the map that stores the distances of the nodes.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap DistMap;
///Instantiates a \c DistMap.
@@ -226,5 +227,5 @@
///\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 > {
@@ -246,5 +247,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c DistMap type.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetDistMap : public Bfs< Digraph, SetDistMapTraits > {
@@ -266,5 +267,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c ReachedMap type.
- ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
template
struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits > {
@@ -286,5 +287,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c ProcessedMap type.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits > {
@@ -414,6 +415,6 @@
///The simplest way to execute the BFS algorithm is to use one of the
///member functions called \ref run(Node) "run()".\n
- ///If you need more control on the execution, first you have to call
- ///\ref init(), then you can add several source nodes with
+ ///If you need better control on the execution, you have to call
+ ///\ref init() first, then you can add several source nodes with
///\ref addSource(). Finally the actual path computation can be
///performed with one of the \ref start() functions.
@@ -701,10 +702,6 @@
///Runs the algorithm to visit all nodes in the digraph.
- ///This method runs the %BFS algorithm in order to
- ///compute the shortest path to each node.
- ///
- ///The algorithm computes
- ///- the shortest path tree (forest),
- ///- the distance of each node from the root(s).
+ ///This method runs the %BFS algorithm in order to visit all nodes
+ ///in the digraph.
///
///\note b.run(s) is just a shortcut of the following code.
@@ -738,7 +735,7 @@
///@{
- ///The shortest path to a node.
-
- ///Returns the shortest path to a node.
+ ///The shortest path to the given node.
+
+ ///Returns the shortest path to the given node from the root(s).
///
///\warning \c t should be reached from the root(s).
@@ -748,7 +745,7 @@
Path path(Node t) const { return Path(*G, *_pred, t); }
- ///The distance of a node from the root(s).
-
- ///Returns the distance of a node from the root(s).
+ ///The distance of the given node from the root(s).
+
+ ///Returns the distance of the given node from the root(s).
///
///\warning If node \c v is not reached from the root(s), then
@@ -759,6 +756,7 @@
int dist(Node v) const { return (*_dist)[v]; }
- ///Returns the 'previous arc' of the shortest path tree for a node.
-
+ ///\brief Returns the 'previous arc' of the shortest path tree for
+ ///the given node.
+ ///
///This function returns the 'previous arc' of the shortest path
///tree for the node \c v, i.e. it returns the last arc of a
@@ -767,5 +765,5 @@
///
///The shortest path tree used here is equal to the shortest path
- ///tree used in \ref predNode().
+ ///tree used in \ref predNode() and \ref predMap().
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -773,13 +771,14 @@
Arc predArc(Node v) const { return (*_pred)[v];}
- ///Returns the 'previous node' of the shortest path tree for a node.
-
+ ///\brief Returns the 'previous node' of the shortest path tree for
+ ///the given node.
+ ///
///This function returns the 'previous node' of the shortest path
///tree for the node \c v, i.e. it returns the last but one node
- ///from a shortest path from a root to \c v. It is \c INVALID
+ ///of a shortest path from a root to \c v. It is \c INVALID
///if \c v is not reached from the root(s) or if \c v is a root.
///
///The shortest path tree used here is equal to the shortest path
- ///tree used in \ref predArc().
+ ///tree used in \ref predArc() and \ref predMap().
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -802,5 +801,5 @@
///
///Returns a const reference to the node map that stores the predecessor
- ///arcs, which form the shortest path tree.
+ ///arcs, which form the shortest path tree (forest).
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -808,5 +807,5 @@
const PredMap &predMap() const { return *_pred;}
- ///Checks if a node is reached from the root(s).
+ ///Checks if the given node is reached from the root(s).
///Returns \c true if \c v is reached from the root(s).
@@ -834,5 +833,5 @@
///The type of the map that stores the predecessor
///arcs of the shortest paths.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap PredMap;
///Instantiates a PredMap.
@@ -849,6 +848,6 @@
///The type of the map that indicates which nodes are processed.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///By default it is a NullMap.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ ///By default, it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a ProcessedMap.
@@ -869,5 +868,5 @@
///The type of the map that indicates which nodes are reached.
- ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
///Instantiates a ReachedMap.
@@ -884,5 +883,5 @@
///The type of the map that stores the distances of the nodes.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap DistMap;
///Instantiates a DistMap.
@@ -899,5 +898,5 @@
///The type of the shortest paths.
- ///It must meet the \ref concepts::Path "Path" concept.
+ ///It must conform to the \ref concepts::Path "Path" concept.
typedef lemon::Path Path;
};
@@ -905,10 +904,6 @@
/// Default traits class used by BfsWizard
- /// To make it easier to use Bfs algorithm
- /// we have created a wizard class.
- /// This \ref BfsWizard class needs default traits,
- /// as well as the \ref Bfs class.
- /// The \ref BfsWizardBase is a class to be the default traits of the
- /// \ref BfsWizard class.
+ /// Default traits class used by BfsWizard.
+ /// \tparam GR The type of the digraph.
template
class BfsWizardBase : public BfsWizardDefaultTraits
@@ -938,5 +933,5 @@
/// Constructor.
- /// This constructor does not require parameters, therefore it initiates
+ /// This constructor does not require parameters, it initiates
/// all of the attributes to \c 0.
BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
@@ -968,5 +963,4 @@
typedef TR Base;
- ///The type of the digraph the algorithm runs on.
typedef typename TR::Digraph Digraph;
@@ -976,14 +970,8 @@
typedef typename Digraph::OutArcIt OutArcIt;
- ///\brief The type of the map that stores the predecessor
- ///arcs of the shortest paths.
typedef typename TR::PredMap PredMap;
- ///\brief The type of the map that stores the distances of the nodes.
typedef typename TR::DistMap DistMap;
- ///\brief The type of the map that indicates which nodes are reached.
typedef typename TR::ReachedMap ReachedMap;
- ///\brief The type of the map that indicates which nodes are processed.
typedef typename TR::ProcessedMap ProcessedMap;
- ///The type of the shortest paths
typedef typename TR::Path Path;
@@ -1055,6 +1043,6 @@
///Runs BFS algorithm to visit all nodes in the digraph.
- ///This method runs BFS algorithm in order to compute
- ///the shortest path to each node.
+ ///This method runs BFS algorithm in order to visit all nodes
+ ///in the digraph.
void run()
{
@@ -1068,9 +1056,10 @@
SetPredMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting PredMap object.
- ///
- ///\ref named-func-param "Named parameter"
- ///for setting PredMap object.
+
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///the predecessor map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that stores the predecessor arcs of the nodes.
template
BfsWizard > predMap(const T &t)
@@ -1086,9 +1075,10 @@
SetReachedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting ReachedMap object.
- ///
- /// \ref named-func-param "Named parameter"
- ///for setting ReachedMap object.
+
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///the reached map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that indicates which nodes are reached.
template
BfsWizard > reachedMap(const T &t)
@@ -1104,9 +1094,11 @@
SetDistMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting DistMap object.
- ///
- /// \ref named-func-param "Named parameter"
- ///for setting DistMap object.
+
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///the distance map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that stores the distances of the nodes calculated
+ ///by the algorithm.
template
BfsWizard > distMap(const T &t)
@@ -1122,9 +1114,10 @@
SetProcessedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting ProcessedMap object.
- ///
- /// \ref named-func-param "Named parameter"
- ///for setting ProcessedMap object.
+
+ ///\brief \ref named-func-param "Named parameter" for setting
+ ///the processed map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that indicates which nodes are processed.
template
BfsWizard > processedMap(const T &t)
@@ -1265,5 +1258,5 @@
///
/// 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;
@@ -1426,6 +1419,6 @@
/// The simplest way to execute the BFS algorithm is to use one of the
/// member functions called \ref run(Node) "run()".\n
- /// If you need more control on the execution, first you have to call
- /// \ref init(), then you can add several source nodes with
+ /// If you need better control on the execution, you have to call
+ /// \ref init() first, then you can add several source nodes with
/// \ref addSource(). Finally the actual path computation can be
/// performed with one of the \ref start() functions.
@@ -1699,10 +1692,6 @@
/// \brief Runs the algorithm to visit all nodes in the digraph.
///
- /// This method runs the %BFS algorithm in order to
- /// compute the shortest path to each node.
- ///
- /// The algorithm computes
- /// - the shortest path tree (forest),
- /// - the distance of each node from the root(s).
+ /// This method runs the %BFS algorithm in order to visit all nodes
+ /// in the digraph.
///
/// \note b.run(s) is just a shortcut of the following code.
@@ -1736,5 +1725,5 @@
///@{
- /// \brief Checks if a node is reached from the root(s).
+ /// \brief Checks if the given node is reached from the root(s).
///
/// Returns \c true if \c v is reached from the root(s).
Index: lemon/bits/graph_extender.h
===================================================================
--- lemon/bits/graph_extender.h (revision 685)
+++ lemon/bits/graph_extender.h (revision 778)
@@ -57,9 +57,9 @@
}
- Node fromId(int id, Node) const {
+ static Node fromId(int id, Node) {
return Parent::nodeFromId(id);
}
- Arc fromId(int id, Arc) const {
+ static Arc fromId(int id, Arc) {
return Parent::arcFromId(id);
}
@@ -356,13 +356,13 @@
}
- Node fromId(int id, Node) const {
+ static Node fromId(int id, Node) {
return Parent::nodeFromId(id);
}
- Arc fromId(int id, Arc) const {
+ static Arc fromId(int id, Arc) {
return Parent::arcFromId(id);
}
- Edge fromId(int id, Edge) const {
+ static Edge fromId(int id, Edge) {
return Parent::edgeFromId(id);
}
Index: lemon/bits/map_extender.h
===================================================================
--- lemon/bits/map_extender.h (revision 617)
+++ lemon/bits/map_extender.h (revision 718)
@@ -50,4 +50,6 @@
typedef typename Parent::ConstReference ConstReference;
+ typedef typename Parent::ReferenceMapTag ReferenceMapTag;
+
class MapIt;
class ConstMapIt;
@@ -192,4 +194,6 @@
typedef typename Parent::ConstReference ConstReference;
+ typedef typename Parent::ReferenceMapTag ReferenceMapTag;
+
class MapIt;
class ConstMapIt;
Index: lemon/cbc.cc
===================================================================
--- lemon/cbc.cc (revision 576)
+++ lemon/cbc.cc (revision 746)
@@ -95,4 +95,16 @@
}
+ int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
+ std::vector indexes;
+ std::vector values;
+
+ for(ExprIterator it = b; it != e; ++it) {
+ indexes.push_back(it->first);
+ values.push_back(it->second);
+ }
+
+ _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
+ return _prob->numberRows() - 1;
+ }
void CbcMip::_eraseCol(int i) {
Index: lemon/cbc.h
===================================================================
--- lemon/cbc.h (revision 576)
+++ lemon/cbc.h (revision 746)
@@ -63,4 +63,5 @@
virtual int _addCol();
virtual int _addRow();
+ virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
virtual void _eraseCol(int i);
Index: lemon/circulation.h
===================================================================
--- lemon/circulation.h (revision 689)
+++ lemon/circulation.h (revision 786)
@@ -73,5 +73,9 @@
/// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
/// concept.
+#ifdef DOXYGEN
+ typedef GR::ArcMap FlowMap;
+#else
typedef typename Digraph::template ArcMap FlowMap;
+#endif
/// \brief Instantiates a FlowMap.
@@ -88,7 +92,10 @@
/// The elevator type used by the algorithm.
///
- /// \sa Elevator
- /// \sa LinkedElevator
+ /// \sa Elevator, LinkedElevator
+#ifdef DOXYGEN
+ typedef lemon::Elevator Elevator;
+#else
typedef lemon::Elevator Elevator;
+#endif
/// \brief Instantiates an Elevator.
@@ -300,5 +307,5 @@
/// able to automatically created by the algorithm (i.e. the
/// digraph and the maximum level should be passed to it).
- /// However an external elevator object could also be passed to the
+ /// However, an external elevator object could also be passed to the
/// algorithm with the \ref elevator(Elevator&) "elevator()" function
/// before calling \ref run() or \ref init().
@@ -470,6 +477,6 @@
/// \name Execution Control
/// The simplest way to execute the algorithm is to call \ref run().\n
- /// If you need more control on the initial solution or the execution,
- /// first you have to call one of the \ref init() functions, then
+ /// If you need better control on the initial solution or the execution,
+ /// you have to call one of the \ref init() functions first, then
/// the \ref start() function.
Index: lemon/clp.cc
===================================================================
--- lemon/clp.cc (revision 576)
+++ lemon/clp.cc (revision 746)
@@ -79,4 +79,17 @@
}
+ int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
+ std::vector indexes;
+ std::vector values;
+
+ for(ExprIterator it = b; it != e; ++it) {
+ indexes.push_back(it->first);
+ values.push_back(it->second);
+ }
+
+ _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
+ return _prob->numberRows() - 1;
+ }
+
void ClpLp::_eraseCol(int c) {
Index: lemon/clp.h
===================================================================
--- lemon/clp.h (revision 576)
+++ lemon/clp.h (revision 746)
@@ -76,4 +76,5 @@
virtual int _addCol();
virtual int _addRow();
+ virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
virtual void _eraseCol(int i);
Index: lemon/concepts/digraph.h
===================================================================
--- lemon/concepts/digraph.h (revision 580)
+++ lemon/concepts/digraph.h (revision 786)
@@ -36,44 +36,38 @@
/// \brief Class describing the concept of directed graphs.
///
- /// This class describes the \ref concept "concept" of the
- /// immutable directed digraphs.
+ /// This class describes the common interface of all directed
+ /// graphs (digraphs).
///
- /// Note that actual digraph implementation like @ref ListDigraph or
- /// @ref SmartDigraph may have several additional functionality.
+ /// Like all concept classes, it only provides an interface
+ /// without any sensible implementation. So any general algorithm for
+ /// directed graphs should compile with this class, but it will not
+ /// run properly, of course.
+ /// An actual digraph implementation like \ref ListDigraph or
+ /// \ref SmartDigraph may have additional functionality.
///
- /// \sa concept
+ /// \sa Graph
class Digraph {
private:
- ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
-
- ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
- ///
- Digraph(const Digraph &) {};
- ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
- ///\e not allowed. Use DigraphCopy() instead.
-
- ///Assignment of \ref Digraph "Digraph"s to another ones are
- ///\e not allowed. Use DigraphCopy() instead.
-
+ /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
+ Digraph(const Digraph &) {}
+ /// \brief Assignment of a digraph to another one is \e not allowed.
+ /// Use DigraphCopy instead.
void operator=(const Digraph &) {}
+
public:
- ///\e
-
- /// Defalult constructor.
-
- /// Defalult constructor.
- ///
+ /// Default constructor.
Digraph() { }
- /// Class for identifying a node of the digraph
+
+ /// The node type of the digraph
/// This class identifies a node of the digraph. It also serves
/// as a base class of the node iterators,
- /// thus they will convert to this type.
+ /// thus they convert to this type.
class Node {
public:
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the object to an undefined value.
Node() { }
/// Copy constructor.
@@ -83,38 +77,37 @@
Node(const Node&) { }
- /// Invalid constructor \& conversion.
-
- /// This constructor initializes the iterator to be invalid.
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the object to be invalid.
/// \sa Invalid for more details.
Node(Invalid) { }
/// Equality operator
+ /// Equality operator.
+ ///
/// Two iterators are equal if and only if they point to the
- /// same object or both are invalid.
+ /// same object or both are \c INVALID.
bool operator==(Node) const { return true; }
/// Inequality operator
- /// \sa operator==(Node n)
- ///
+ /// Inequality operator.
bool operator!=(Node) const { return true; }
/// Artificial ordering operator.
- /// To allow the use of digraph descriptors as key type in std::map or
- /// similar associative container we require this.
- ///
- /// \note This operator only have to define some strict ordering of
- /// the items; this order has nothing to do with the iteration
- /// ordering of the items.
+ /// Artificial ordering operator.
+ ///
+ /// \note This operator only has to define some strict ordering of
+ /// the nodes; this order has nothing to do with the iteration
+ /// ordering of the nodes.
bool operator<(Node) const { return false; }
-
- };
-
- /// This iterator goes through each node.
-
- /// This iterator goes through each node.
- /// Its usage is quite simple, for example you can count the number
- /// of nodes in digraph \c g of type \c Digraph like this:
+ };
+
+ /// Iterator class for the nodes.
+
+ /// This iterator goes through each node of the digraph.
+ /// Its usage is quite simple, for example, you can count the number
+ /// of nodes in a digraph \c g of type \c %Digraph like this:
///\code
/// int count=0;
@@ -125,6 +118,6 @@
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the iterator to an undefined value.
NodeIt() { }
/// Copy constructor.
@@ -133,20 +126,18 @@
///
NodeIt(const NodeIt& n) : Node(n) { }
- /// Invalid constructor \& conversion.
-
- /// Initialize the iterator to be invalid.
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the iterator to be invalid.
/// \sa Invalid for more details.
NodeIt(Invalid) { }
/// Sets the iterator to the first node.
- /// Sets the iterator to the first node of \c g.
- ///
- NodeIt(const Digraph&) { }
- /// Node -> NodeIt conversion.
-
- /// Sets the iterator to the node of \c the digraph pointed by
- /// the trivial iterator.
- /// This feature necessitates that each time we
- /// iterate the arc-set, the iteration order is the same.
+ /// Sets the iterator to the first node of the given digraph.
+ ///
+ explicit NodeIt(const Digraph&) { }
+ /// Sets the iterator to the given node.
+
+ /// Sets the iterator to the given node of the given digraph.
+ ///
NodeIt(const Digraph&, const Node&) { }
/// Next node.
@@ -158,5 +149,5 @@
- /// Class for identifying an arc of the digraph
+ /// The arc type of the digraph
/// This class identifies an arc of the digraph. It also serves
@@ -167,6 +158,6 @@
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the object to an undefined value.
Arc() { }
/// Copy constructor.
@@ -175,49 +166,48 @@
///
Arc(const Arc&) { }
- /// Initialize the iterator to be invalid.
-
- /// Initialize the iterator to be invalid.
- ///
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the object to be invalid.
+ /// \sa Invalid for more details.
Arc(Invalid) { }
/// Equality operator
+ /// Equality operator.
+ ///
/// Two iterators are equal if and only if they point to the
- /// same object or both are invalid.
+ /// same object or both are \c INVALID.
bool operator==(Arc) const { return true; }
/// Inequality operator
- /// \sa operator==(Arc n)
- ///
+ /// Inequality operator.
bool operator!=(Arc) const { return true; }
/// Artificial ordering operator.
- /// To allow the use of digraph descriptors as key type in std::map or
- /// similar associative container we require this.
- ///
- /// \note This operator only have to define some strict ordering of
- /// the items; this order has nothing to do with the iteration
- /// ordering of the items.
+ /// Artificial ordering operator.
+ ///
+ /// \note This operator only has to define some strict ordering of
+ /// the arcs; this order has nothing to do with the iteration
+ /// ordering of the arcs.
bool operator<(Arc) const { return false; }
};
- /// This iterator goes trough the outgoing arcs of a node.
+ /// Iterator class for the outgoing arcs of a node.
/// This iterator goes trough the \e outgoing arcs of a certain node
/// of a digraph.
- /// Its usage is quite simple, for example you can count the number
+ /// Its usage is quite simple, for example, you can count the number
/// of outgoing arcs of a node \c n
- /// in digraph \c g of type \c Digraph as follows.
+ /// in a digraph \c g of type \c %Digraph as follows.
///\code
/// int count=0;
- /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
+ /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
///\endcode
-
class OutArcIt : public Arc {
public:
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the iterator to an undefined value.
OutArcIt() { }
/// Copy constructor.
@@ -226,21 +216,20 @@
///
OutArcIt(const OutArcIt& e) : Arc(e) { }
- /// Initialize the iterator to be invalid.
-
- /// Initialize the iterator to be invalid.
- ///
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the iterator to be invalid.
+ /// \sa Invalid for more details.
OutArcIt(Invalid) { }
- /// This constructor sets the iterator to the first outgoing arc.
-
- /// This constructor sets the iterator to the first outgoing arc of
- /// the node.
+ /// Sets the iterator to the first outgoing arc.
+
+ /// Sets the iterator to the first outgoing arc of the given node.
+ ///
OutArcIt(const Digraph&, const Node&) { }
- /// Arc -> OutArcIt conversion
-
- /// Sets the iterator to the value of the trivial iterator.
- /// This feature necessitates that each time we
- /// iterate the arc-set, the iteration order is the same.
+ /// Sets the iterator to the given arc.
+
+ /// Sets the iterator to the given arc of the given digraph.
+ ///
OutArcIt(const Digraph&, const Arc&) { }
- ///Next outgoing arc
+ /// Next outgoing arc
/// Assign the iterator to the next
@@ -249,22 +238,21 @@
};
- /// This iterator goes trough the incoming arcs of a node.
+ /// Iterator class for the incoming arcs of a node.
/// This iterator goes trough the \e incoming arcs of a certain node
/// of a digraph.
- /// Its usage is quite simple, for example you can count the number
- /// of outgoing arcs of a node \c n
- /// in digraph \c g of type \c Digraph as follows.
+ /// Its usage is quite simple, for example, you can count the number
+ /// of incoming arcs of a node \c n
+ /// in a digraph \c g of type \c %Digraph as follows.
///\code
/// int count=0;
- /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
+ /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
///\endcode
-
class InArcIt : public Arc {
public:
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the iterator to an undefined value.
InArcIt() { }
/// Copy constructor.
@@ -273,34 +261,34 @@
///
InArcIt(const InArcIt& e) : Arc(e) { }
- /// Initialize the iterator to be invalid.
-
- /// Initialize the iterator to be invalid.
- ///
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the iterator to be invalid.
+ /// \sa Invalid for more details.
InArcIt(Invalid) { }
- /// This constructor sets the iterator to first incoming arc.
-
- /// This constructor set the iterator to the first incoming arc of
- /// the node.
+ /// Sets the iterator to the first incoming arc.
+
+ /// Sets the iterator to the first incoming arc of the given node.
+ ///
InArcIt(const Digraph&, const Node&) { }
- /// Arc -> InArcIt conversion
-
- /// Sets the iterator to the value of the trivial iterator \c e.
- /// This feature necessitates that each time we
- /// iterate the arc-set, the iteration order is the same.
+ /// Sets the iterator to the given arc.
+
+ /// Sets the iterator to the given arc of the given digraph.
+ ///
InArcIt(const Digraph&, const Arc&) { }
/// Next incoming arc
- /// Assign the iterator to the next inarc of the corresponding node.
- ///
+ /// Assign the iterator to the next
+ /// incoming arc of the corresponding node.
InArcIt& operator++() { return *this; }
};
- /// This iterator goes through each arc.
-
- /// This iterator goes through each arc of a digraph.
- /// Its usage is quite simple, for example you can count the number
- /// of arcs in a digraph \c g of type \c Digraph as follows:
+
+ /// Iterator class for the arcs.
+
+ /// This iterator goes through each arc of the digraph.
+ /// Its usage is quite simple, for example, you can count the number
+ /// of arcs in a digraph \c g of type \c %Digraph as follows:
///\code
/// int count=0;
- /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
+ /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
///\endcode
class ArcIt : public Arc {
@@ -308,6 +296,6 @@
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the iterator to an undefined value.
ArcIt() { }
/// Copy constructor.
@@ -316,56 +304,66 @@
///
ArcIt(const ArcIt& e) : Arc(e) { }
- /// Initialize the iterator to be invalid.
-
- /// Initialize the iterator to be invalid.
- ///
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the iterator to be invalid.
+ /// \sa Invalid for more details.
ArcIt(Invalid) { }
- /// This constructor sets the iterator to the first arc.
-
- /// This constructor sets the iterator to the first arc of \c g.
- ///@param g the digraph
- ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
- /// Arc -> ArcIt conversion
-
- /// Sets the iterator to the value of the trivial iterator \c e.
- /// This feature necessitates that each time we
- /// iterate the arc-set, the iteration order is the same.
+ /// Sets the iterator to the first arc.
+
+ /// Sets the iterator to the first arc of the given digraph.
+ ///
+ explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
+ /// Sets the iterator to the given arc.
+
+ /// Sets the iterator to the given arc of the given digraph.
+ ///
ArcIt(const Digraph&, const Arc&) { }
- ///Next arc
+ /// Next arc
/// Assign the iterator to the next arc.
+ ///
ArcIt& operator++() { return *this; }
};
- ///Gives back the target node of an arc.
-
- ///Gives back the target node of an arc.
- ///
+
+ /// \brief The source node of the arc.
+ ///
+ /// Returns the source node of the given arc.
+ Node source(Arc) const { return INVALID; }
+
+ /// \brief The target node of the arc.
+ ///
+ /// Returns the target node of the given arc.
Node target(Arc) const { return INVALID; }
- ///Gives back the source node of an arc.
-
- ///Gives back the source node of an arc.
- ///
- Node source(Arc) const { return INVALID; }
-
- /// \brief Returns the ID of the node.
+
+ /// \brief The ID of the node.
+ ///
+ /// Returns the ID of the given node.
int id(Node) const { return -1; }
- /// \brief Returns the ID of the arc.
+ /// \brief The ID of the arc.
+ ///
+ /// Returns the ID of the given arc.
int id(Arc) const { return -1; }
- /// \brief Returns the node with the given ID.
- ///
- /// \pre The argument should be a valid node ID in the graph.
+ /// \brief The node with the given ID.
+ ///
+ /// Returns the node with the given ID.
+ /// \pre The argument should be a valid node ID in the digraph.
Node nodeFromId(int) const { return INVALID; }
- /// \brief Returns the arc with the given ID.
- ///
- /// \pre The argument should be a valid arc ID in the graph.
+ /// \brief The arc with the given ID.
+ ///
+ /// Returns the arc with the given ID.
+ /// \pre The argument should be a valid arc ID in the digraph.
Arc arcFromId(int) const { return INVALID; }
- /// \brief Returns an upper bound on the node IDs.
+ /// \brief An upper bound on the node IDs.
+ ///
+ /// Returns an upper bound on the node IDs.
int maxNodeId() const { return -1; }
- /// \brief Returns an upper bound on the arc IDs.
+ /// \brief An upper bound on the arc IDs.
+ ///
+ /// Returns an upper bound on the arc IDs.
int maxArcId() const { return -1; }
@@ -393,43 +391,44 @@
int maxId(Arc) const { return -1; }
+ /// \brief The opposite node on the arc.
+ ///
+ /// Returns the opposite node on the given arc.
+ Node oppositeNode(Node, Arc) const { return INVALID; }
+
/// \brief The base node of the iterator.
///
- /// Gives back the base node of the iterator.
- /// It is always the target of the pointed arc.
- Node baseNode(const InArcIt&) const { return INVALID; }
+ /// Returns the base node of the given outgoing arc iterator
+ /// (i.e. the source node of the corresponding arc).
+ Node baseNode(OutArcIt) const { return INVALID; }
/// \brief The running node of the iterator.
///
- /// Gives back the running node of the iterator.
- /// It is always the source of the pointed arc.
- Node runningNode(const InArcIt&) const { return INVALID; }
+ /// Returns the running node of the given outgoing arc iterator
+ /// (i.e. the target node of the corresponding arc).
+ Node runningNode(OutArcIt) const { return INVALID; }
/// \brief The base node of the iterator.
///
- /// Gives back the base node of the iterator.
- /// It is always the source of the pointed arc.
- Node baseNode(const OutArcIt&) const { return INVALID; }
+ /// Returns the base node of the given incomming arc iterator
+ /// (i.e. the target node of the corresponding arc).
+ Node baseNode(InArcIt) const { return INVALID; }
/// \brief The running node of the iterator.
///
- /// Gives back the running node of the iterator.
- /// It is always the target of the pointed arc.
- Node runningNode(const OutArcIt&) const { return INVALID; }
-
- /// \brief The opposite node on the given arc.
- ///
- /// Gives back the opposite node on the given arc.
- Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
-
- /// \brief Reference map of the nodes to type \c T.
- ///
- /// Reference map of the nodes to type \c T.
+ /// Returns the running node of the given incomming arc iterator
+ /// (i.e. the source node of the corresponding arc).
+ Node runningNode(InArcIt) const { return INVALID; }
+
+ /// \brief Standard graph map type for the nodes.
+ ///
+ /// Standard graph map type for the nodes.
+ /// It conforms to the ReferenceMap concept.
template
class NodeMap : public ReferenceMap {
public:
- ///\e
- NodeMap(const Digraph&) { }
- ///\e
+ /// Constructor
+ explicit NodeMap(const Digraph&) { }
+ /// Constructor with given initial value
NodeMap(const Digraph&, T) { }
@@ -446,15 +445,17 @@
};
- /// \brief Reference map of the arcs to type \c T.
- ///
- /// Reference map of the arcs to type \c T.
+ /// \brief Standard graph map type for the arcs.
+ ///
+ /// Standard graph map type for the arcs.
+ /// It conforms to the ReferenceMap concept.
template
class ArcMap : public ReferenceMap {
public:
- ///\e
- ArcMap(const Digraph&) { }
- ///\e
+ /// Constructor
+ explicit ArcMap(const Digraph&) { }
+ /// Constructor with given initial value
ArcMap(const Digraph&, T) { }
+
private:
///Copy constructor
Index: lemon/concepts/graph.h
===================================================================
--- lemon/concepts/graph.h (revision 657)
+++ lemon/concepts/graph.h (revision 786)
@@ -19,5 +19,5 @@
///\ingroup graph_concepts
///\file
-///\brief The concept of Undirected Graphs.
+///\brief The concept of undirected graphs.
#ifndef LEMON_CONCEPTS_GRAPH_H
@@ -25,4 +25,6 @@
#include
+#include
+#include
#include
@@ -32,61 +34,72 @@
/// \ingroup graph_concepts
///
- /// \brief Class describing the concept of Undirected Graphs.
+ /// \brief Class describing the concept of undirected graphs.
///
- /// This class describes the common interface of all Undirected
- /// Graphs.
+ /// This class describes the common interface of all undirected
+ /// graphs.
///
- /// As all concept describing classes it provides only interface
- /// without any sensible implementation. So any algorithm for
- /// undirected graph should compile with this class, but it will not
+ /// Like all concept classes, it only provides an interface
+ /// without any sensible implementation. So any general algorithm for
+ /// undirected graphs should compile with this class, but it will not
/// run properly, of course.
+ /// An actual graph implementation like \ref ListGraph or
+ /// \ref SmartGraph may have additional functionality.
///
- /// The LEMON undirected graphs also fulfill the concept of
- /// directed graphs (\ref lemon::concepts::Digraph "Digraph
- /// Concept"). Each edges can be seen as two opposite
- /// directed arc and consequently the undirected graph can be
- /// seen as the direceted graph of these directed arcs. The
- /// Graph has the Edge inner class for the edges and
- /// the Arc type for the directed arcs. The Arc type is
- /// convertible to Edge or inherited from it so from a directed
- /// arc we can get the represented edge.
+ /// The undirected graphs also fulfill the concept of \ref Digraph
+ /// "directed graphs", since each edge can also be regarded as two
+ /// oppositely directed arcs.
+ /// Undirected graphs provide an Edge type for the undirected edges and
+ /// an Arc type for the directed arcs. The Arc type is convertible to
+ /// Edge or inherited from it, i.e. the corresponding edge can be
+ /// obtained from an arc.
+ /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
+ /// and ArcMap classes can be used for the arcs (just like in digraphs).
+ /// Both InArcIt and OutArcIt iterates on the same edges but with
+ /// opposite direction. IncEdgeIt also iterates on the same edges
+ /// as OutArcIt and InArcIt, but it is not convertible to Arc,
+ /// only to Edge.
///
- /// In the sense of the LEMON each edge has a default
- /// direction (it should be in every computer implementation,
- /// because the order of edge's nodes defines an
- /// orientation). With the default orientation we can define that
- /// the directed arc is forward or backward directed. With the \c
- /// direction() and \c direct() function we can get the direction
- /// of the directed arc and we can direct an edge.
+ /// In LEMON, each undirected edge has an inherent orientation.
+ /// Thus it can defined if an arc is forward or backward oriented in
+ /// an undirected graph with respect to this default oriantation of
+ /// the represented edge.
+ /// With the direction() and direct() functions the direction
+ /// of an arc can be obtained and set, respectively.
///
- /// The EdgeIt is an iterator for the edges. We can use
- /// the EdgeMap to map values for the edges. The InArcIt and
- /// OutArcIt iterates on the same edges but with opposite
- /// direction. The IncEdgeIt iterates also on the same edges
- /// as the OutArcIt and InArcIt but it is not convertible to Arc just
- /// to Edge.
+ /// Only nodes and edges can be added to or removed from an undirected
+ /// graph and the corresponding arcs are added or removed automatically.
+ ///
+ /// \sa Digraph
class Graph {
+ private:
+ /// Graphs are \e not copy constructible. Use DigraphCopy instead.
+ Graph(const Graph&) {}
+ /// \brief Assignment of a graph to another one is \e not allowed.
+ /// Use DigraphCopy instead.
+ void operator=(const Graph&) {}
+
public:
- /// \brief The undirected graph should be tagged by the
- /// UndirectedTag.
- ///
- /// The undirected graph should be tagged by the UndirectedTag. This
- /// tag helps the enable_if technics to make compile time
+ /// Default constructor.
+ Graph() {}
+
+ /// \brief Undirected graphs should be tagged with \c UndirectedTag.
+ ///
+ /// Undirected graphs should be tagged with \c UndirectedTag.
+ ///
+ /// This tag helps the \c enable_if technics to make compile time
/// specializations for undirected graphs.
typedef True UndirectedTag;
- /// \brief The base type of node iterators,
- /// or in other words, the trivial node iterator.
- ///
- /// This is the base type of each node iterator,
- /// thus each kind of node iterator converts to this.
- /// More precisely each kind of node iterator should be inherited
- /// from the trivial node iterator.
+ /// The node type of the graph
+
+ /// This class identifies a node of the graph. It also serves
+ /// as a base class of the node iterators,
+ /// thus they convert to this type.
class Node {
public:
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the object to an undefined value.
Node() { }
/// Copy constructor.
@@ -96,27 +109,27 @@
Node(const Node&) { }
- /// Invalid constructor \& conversion.
-
- /// This constructor initializes the iterator to be invalid.
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the object to be invalid.
/// \sa Invalid for more details.
Node(Invalid) { }
/// Equality operator
+ /// Equality operator.
+ ///
/// Two iterators are equal if and only if they point to the
- /// same object or both are invalid.
+ /// same object or both are \c INVALID.
bool operator==(Node) const { return true; }
/// Inequality operator
- /// \sa operator==(Node n)
- ///
+ /// Inequality operator.
bool operator!=(Node) const { return true; }
/// Artificial ordering operator.
- /// To allow the use of graph descriptors as key type in std::map or
- /// similar associative container we require this.
- ///
- /// \note This operator only have to define some strict ordering of
+ /// Artificial ordering operator.
+ ///
+ /// \note This operator only has to define some strict ordering of
/// the items; this order has nothing to do with the iteration
/// ordering of the items.
@@ -125,9 +138,9 @@
};
- /// This iterator goes through each node.
-
- /// This iterator goes through each node.
- /// Its usage is quite simple, for example you can count the number
- /// of nodes in graph \c g of type \c Graph like this:
+ /// Iterator class for the nodes.
+
+ /// This iterator goes through each node of the graph.
+ /// Its usage is quite simple, for example, you can count the number
+ /// of nodes in a graph \c g of type \c %Graph like this:
///\code
/// int count=0;
@@ -138,6 +151,6 @@
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the iterator to an undefined value.
NodeIt() { }
/// Copy constructor.
@@ -146,20 +159,18 @@
///
NodeIt(const NodeIt& n) : Node(n) { }
- /// Invalid constructor \& conversion.
-
- /// Initialize the iterator to be invalid.
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the iterator to be invalid.
/// \sa Invalid for more details.
NodeIt(Invalid) { }
/// Sets the iterator to the first node.
- /// Sets the iterator to the first node of \c g.
- ///
- NodeIt(const Graph&) { }
- /// Node -> NodeIt conversion.
-
- /// Sets the iterator to the node of \c the graph pointed by
- /// the trivial iterator.
- /// This feature necessitates that each time we
- /// iterate the arc-set, the iteration order is the same.
+ /// Sets the iterator to the first node of the given digraph.
+ ///
+ explicit NodeIt(const Graph&) { }
+ /// Sets the iterator to the given node.
+
+ /// Sets the iterator to the given node of the given digraph.
+ ///
NodeIt(const Graph&, const Node&) { }
/// Next node.
@@ -171,14 +182,15 @@
- /// The base type of the edge iterators.
-
- /// The base type of the edge iterators.
- ///
+ /// The edge type of the graph
+
+ /// This class identifies an edge of the graph. It also serves
+ /// as a base class of the edge iterators,
+ /// thus they will convert to this type.
class Edge {
public:
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the object to an undefined value.
Edge() { }
/// Copy constructor.
@@ -187,36 +199,36 @@
///
Edge(const Edge&) { }
- /// Initialize the iterator to be invalid.
-
- /// Initialize the iterator to be invalid.
- ///
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the object to be invalid.
+ /// \sa Invalid for more details.
Edge(Invalid) { }
/// Equality operator
+ /// Equality operator.
+ ///
/// Two iterators are equal if and only if they point to the
- /// same object or both are invalid.
+ /// same object or both are \c INVALID.
bool operator==(Edge) const { return true; }
/// Inequality operator
- /// \sa operator==(Edge n)
- ///
+ /// Inequality operator.
bool operator!=(Edge) const { return true; }
/// Artificial ordering operator.
- /// To allow the use of graph descriptors as key type in std::map or
- /// similar associative container we require this.
- ///
- /// \note This operator only have to define some strict ordering of
- /// the items; this order has nothing to do with the iteration
- /// ordering of the items.
+ /// Artificial ordering operator.
+ ///
+ /// \note This operator only has to define some strict ordering of
+ /// the edges; this order has nothing to do with the iteration
+ /// ordering of the edges.
bool operator<(Edge) const { return false; }
};
- /// This iterator goes through each edge.
-
- /// This iterator goes through each edge of a graph.
- /// Its usage is quite simple, for example you can count the number
- /// of edges in a graph \c g of type \c Graph as follows:
+ /// Iterator class for the edges.
+
+ /// This iterator goes through each edge of the graph.
+ /// Its usage is quite simple, for example, you can count the number
+ /// of edges in a graph \c g of type \c %Graph as follows:
///\code
/// int count=0;
@@ -227,6 +239,6 @@
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the iterator to an undefined value.
EdgeIt() { }
/// Copy constructor.
@@ -235,36 +247,33 @@
///
EdgeIt(const EdgeIt& e) : Edge(e) { }
- /// Initialize the iterator to be invalid.
-
- /// Initialize the iterator to be invalid.
- ///
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the iterator to be invalid.
+ /// \sa Invalid for more details.
EdgeIt(Invalid) { }
- /// This constructor sets the iterator to the first edge.
-
- /// This constructor sets the iterator to the first edge.
- EdgeIt(const Graph&) { }
- /// Edge -> EdgeIt conversion
-
- /// Sets the iterator to the value of the trivial iterator.
- /// This feature necessitates that each time we
- /// iterate the edge-set, the iteration order is the
- /// same.
+ /// Sets the iterator to the first edge.
+
+ /// Sets the iterator to the first edge of the given graph.
+ ///
+ explicit EdgeIt(const Graph&) { }
+ /// Sets the iterator to the given edge.
+
+ /// Sets the iterator to the given edge of the given graph.
+ ///
EdgeIt(const Graph&, const Edge&) { }
/// Next edge
/// Assign the iterator to the next edge.
+ ///
EdgeIt& operator++() { return *this; }
};
- /// \brief This iterator goes trough the incident undirected
- /// arcs of a node.
- ///
- /// This iterator goes trough the incident edges
- /// of a certain node of a graph. You should assume that the
- /// loop arcs will be iterated twice.
- ///
- /// Its usage is quite simple, for example you can compute the
- /// degree (i.e. count the number of incident arcs of a node \c n
- /// in graph \c g of type \c Graph as follows.
+ /// Iterator class for the incident edges of a node.
+
+ /// This iterator goes trough the incident undirected edges
+ /// of a certain node of a graph.
+ /// Its usage is quite simple, for example, you can compute the
+ /// degree (i.e. the number of incident edges) of a node \c n
+ /// in a graph \c g of type \c %Graph as follows.
///
///\code
@@ -272,10 +281,12 @@
/// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
///\endcode
+ ///
+ /// \warning Loop edges will be iterated twice.
class IncEdgeIt : public Edge {
public:
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the iterator to an undefined value.
IncEdgeIt() { }
/// Copy constructor.
@@ -284,38 +295,37 @@
///
IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
- /// Initialize the iterator to be invalid.
-
- /// Initialize the iterator to be invalid.
- ///
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the iterator to be invalid.
+ /// \sa Invalid for more details.
IncEdgeIt(Invalid) { }
- /// This constructor sets the iterator to first incident arc.
-
- /// This constructor set the iterator to the first incident arc of
- /// the node.
+ /// Sets the iterator to the first incident edge.
+
+ /// Sets the iterator to the first incident edge of the given node.
+ ///
IncEdgeIt(const Graph&, const Node&) { }
- /// Edge -> IncEdgeIt conversion
-
- /// Sets the iterator to the value of the trivial iterator \c e.
- /// This feature necessitates that each time we
- /// iterate the arc-set, the iteration order is the same.
+ /// Sets the iterator to the given edge.
+
+ /// Sets the iterator to the given edge of the given graph.
+ ///
IncEdgeIt(const Graph&, const Edge&) { }
- /// Next incident arc
-
- /// Assign the iterator to the next incident arc
+ /// Next incident edge
+
+ /// Assign the iterator to the next incident edge
/// of the corresponding node.
IncEdgeIt& operator++() { return *this; }
};
- /// The directed arc type.
-
- /// The directed arc type. It can be converted to the
- /// edge or it should be inherited from the undirected
- /// edge.
+ /// The arc type of the graph
+
+ /// This class identifies a directed arc of the graph. It also serves
+ /// as a base class of the arc iterators,
+ /// thus they will convert to this type.
class Arc {
public:
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the object to an undefined value.
Arc() { }
/// Copy constructor.
@@ -324,41 +334,45 @@
///
Arc(const Arc&) { }
- /// Initialize the iterator to be invalid.
-
- /// Initialize the iterator to be invalid.
- ///
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the object to be invalid.
+ /// \sa Invalid for more details.
Arc(Invalid) { }
/// Equality operator
+ /// Equality operator.
+ ///
/// Two iterators are equal if and only if they point to the
- /// same object or both are invalid.
+ /// same object or both are \c INVALID.
bool operator==(Arc) const { return true; }
/// Inequality operator
- /// \sa operator==(Arc n)
- ///
+ /// Inequality operator.
bool operator!=(Arc) const { return true; }
/// Artificial ordering operator.
- /// To allow the use of graph descriptors as key type in std::map or
- /// similar associative container we require this.
- ///
- /// \note This operator only have to define some strict ordering of
- /// the items; this order has nothing to do with the iteration
- /// ordering of the items.
+ /// Artificial ordering operator.
+ ///
+ /// \note This operator only has to define some strict ordering of
+ /// the arcs; this order has nothing to do with the iteration
+ /// ordering of the arcs.
bool operator<(Arc) const { return false; }
- /// Converison to Edge
+ /// Converison to \c Edge
+
+ /// Converison to \c Edge.
+ ///
operator Edge() const { return Edge(); }
};
- /// This iterator goes through each directed arc.
-
- /// This iterator goes through each arc of a graph.
- /// Its usage is quite simple, for example you can count the number
- /// of arcs in a graph \c g of type \c Graph as follows:
+
+ /// Iterator class for the arcs.
+
+ /// This iterator goes through each directed arc of the graph.
+ /// Its usage is quite simple, for example, you can count the number
+ /// of arcs in a graph \c g of type \c %Graph as follows:
///\code
/// int count=0;
- /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
+ /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
///\endcode
class ArcIt : public Arc {
@@ -366,6 +380,6 @@
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the iterator to an undefined value.
ArcIt() { }
/// Copy constructor.
@@ -374,44 +388,43 @@
///
ArcIt(const ArcIt& e) : Arc(e) { }
- /// Initialize the iterator to be invalid.
-
- /// Initialize the iterator to be invalid.
- ///
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the iterator to be invalid.
+ /// \sa Invalid for more details.
ArcIt(Invalid) { }
- /// This constructor sets the iterator to the first arc.
-
- /// This constructor sets the iterator to the first arc of \c g.
- ///@param g the graph
- ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
- /// Arc -> ArcIt conversion
-
- /// Sets the iterator to the value of the trivial iterator \c e.
- /// This feature necessitates that each time we
- /// iterate the arc-set, the iteration order is the same.
+ /// Sets the iterator to the first arc.
+
+ /// Sets the iterator to the first arc of the given graph.
+ ///
+ explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
+ /// Sets the iterator to the given arc.
+
+ /// Sets the iterator to the given arc of the given graph.
+ ///
ArcIt(const Graph&, const Arc&) { }
- ///Next arc
+ /// Next arc
/// Assign the iterator to the next arc.
+ ///
ArcIt& operator++() { return *this; }
};
- /// This iterator goes trough the outgoing directed arcs of a node.
-
- /// This iterator goes trough the \e outgoing arcs of a certain node
- /// of a graph.
- /// Its usage is quite simple, for example you can count the number
+ /// Iterator class for the outgoing arcs of a node.
+
+ /// This iterator goes trough the \e outgoing directed arcs of a
+ /// certain node of a graph.
+ /// Its usage is quite simple, for example, you can count the number
/// of outgoing arcs of a node \c n
- /// in graph \c g of type \c Graph as follows.
+ /// in a graph \c g of type \c %Graph as follows.
///\code
/// int count=0;
- /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
+ /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
///\endcode
-
class OutArcIt : public Arc {
public:
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the iterator to an undefined value.
OutArcIt() { }
/// Copy constructor.
@@ -420,26 +433,23 @@
///
OutArcIt(const OutArcIt& e) : Arc(e) { }
- /// Initialize the iterator to be invalid.
-
- /// Initialize the iterator to be invalid.
- ///
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the iterator to be invalid.
+ /// \sa Invalid for more details.
OutArcIt(Invalid) { }
- /// This constructor sets the iterator to the first outgoing arc.
-
- /// This constructor sets the iterator to the first outgoing arc of
- /// the node.
- ///@param n the node
- ///@param g the graph
+ /// Sets the iterator to the first outgoing arc.
+
+ /// Sets the iterator to the first outgoing arc of the given node.
+ ///
OutArcIt(const Graph& n, const Node& g) {
ignore_unused_variable_warning(n);
ignore_unused_variable_warning(g);
}
- /// Arc -> OutArcIt conversion
-
- /// Sets the iterator to the value of the trivial iterator.
- /// This feature necessitates that each time we
- /// iterate the arc-set, the iteration order is the same.
+ /// Sets the iterator to the given arc.
+
+ /// Sets the iterator to the given arc of the given graph.
+ ///
OutArcIt(const Graph&, const Arc&) { }
- ///Next outgoing arc
+ /// Next outgoing arc
/// Assign the iterator to the next
@@ -448,22 +458,21 @@
};
- /// This iterator goes trough the incoming directed arcs of a node.
-
- /// This iterator goes trough the \e incoming arcs of a certain node
- /// of a graph.
- /// Its usage is quite simple, for example you can count the number
- /// of outgoing arcs of a node \c n
- /// in graph \c g of type \c Graph as follows.
+ /// Iterator class for the incoming arcs of a node.
+
+ /// This iterator goes trough the \e incoming directed arcs of a
+ /// certain node of a graph.
+ /// Its usage is quite simple, for example, you can count the number
+ /// of incoming arcs of a node \c n
+ /// in a graph \c g of type \c %Graph as follows.
///\code
/// int count=0;
- /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
+ /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
///\endcode
-
class InArcIt : public Arc {
public:
/// Default constructor
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning It sets the iterator to an undefined value.
InArcIt() { }
/// Copy constructor.
@@ -472,35 +481,33 @@
///
InArcIt(const InArcIt& e) : Arc(e) { }
- /// Initialize the iterator to be invalid.
-
- /// Initialize the iterator to be invalid.
- ///
+ /// %Invalid constructor \& conversion.
+
+ /// Initializes the iterator to be invalid.
+ /// \sa Invalid for more details.
InArcIt(Invalid) { }
- /// This constructor sets the iterator to first incoming arc.
-
- /// This constructor set the iterator to the first incoming arc of
- /// the node.
- ///@param n the node
- ///@param g the graph
+ /// Sets the iterator to the first incoming arc.
+
+ /// Sets the iterator to the first incoming arc of the given node.
+ ///
InArcIt(const Graph& g, const Node& n) {
ignore_unused_variable_warning(n);
ignore_unused_variable_warning(g);
}
- /// Arc -> InArcIt conversion
-
- /// Sets the iterator to the value of the trivial iterator \c e.
- /// This feature necessitates that each time we
- /// iterate the arc-set, the iteration order is the same.
+ /// Sets the iterator to the given arc.
+
+ /// Sets the iterator to the given arc of the given graph.
+ ///
InArcIt(const Graph&, const Arc&) { }
/// Next incoming arc
- /// Assign the iterator to the next inarc of the corresponding node.
- ///
+ /// Assign the iterator to the next
+ /// incoming arc of the corresponding node.
InArcIt& operator++() { return *this; }
};
- /// \brief Reference map of the nodes to type \c T.
- ///
- /// Reference map of the nodes to type \c T.
+ /// \brief Standard graph map type for the nodes.
+ ///
+ /// Standard graph map type for the nodes.
+ /// It conforms to the ReferenceMap concept.
template
class NodeMap : public ReferenceMap
@@ -508,7 +515,7 @@
public:
- ///\e
- NodeMap(const Graph&) { }
- ///\e
+ /// Constructor
+ explicit NodeMap(const Graph&) { }
+ /// Constructor with given initial value
NodeMap(const Graph&, T) { }
@@ -525,7 +532,8 @@
};
- /// \brief Reference map of the arcs to type \c T.
- ///
- /// Reference map of the arcs to type \c T.
+ /// \brief Standard graph map type for the arcs.
+ ///
+ /// Standard graph map type for the arcs.
+ /// It conforms to the ReferenceMap concept.
template
class ArcMap : public ReferenceMap
@@ -533,8 +541,9 @@
public:
- ///\e
- ArcMap(const Graph&) { }
- ///\e
+ /// Constructor
+ explicit ArcMap(const Graph&) { }
+ /// Constructor with given initial value
ArcMap(const Graph&, T) { }
+
private:
///Copy constructor
@@ -549,7 +558,8 @@
};
- /// Reference map of the edges to type \c T.
-
- /// Reference map of the edges to type \c T.
+ /// \brief Standard graph map type for the edges.
+ ///
+ /// Standard graph map type for the edges.
+ /// It conforms to the ReferenceMap concept.
template
class EdgeMap : public ReferenceMap
@@ -557,8 +567,9 @@
public:
- ///\e
- EdgeMap(const Graph&) { }
- ///\e
+ /// Constructor
+ explicit EdgeMap(const Graph&) { }
+ /// Constructor with given initial value
EdgeMap(const Graph&, T) { }
+
private:
///Copy constructor
@@ -573,104 +584,121 @@
};
- /// \brief Direct the given edge.
- ///
- /// Direct the given edge. The returned arc source
- /// will be the given node.
- Arc direct(const Edge&, const Node&) const {
- return INVALID;
- }
-
- /// \brief Direct the given edge.
- ///
- /// Direct the given edge. The returned arc
- /// represents the given edge and the direction comes
- /// from the bool parameter. The source of the edge and
- /// the directed arc is the same when the given bool is true.
- Arc direct(const Edge&, bool) const {
- return INVALID;
- }
-
- /// \brief Returns true if the arc has default orientation.
- ///
- /// Returns whether the given directed arc is same orientation as
- /// the corresponding edge's default orientation.
- bool direction(Arc) const { return true; }
-
- /// \brief Returns the opposite directed arc.
- ///
- /// Returns the opposite directed arc.
- Arc oppositeArc(Arc) const { return INVALID; }
-
- /// \brief Opposite node on an arc
- ///
- /// \return The opposite of the given node on the given edge.
- Node oppositeNode(Node, Edge) const { return INVALID; }
-
- /// \brief First node of the edge.
- ///
- /// \return The first node of the given edge.
- ///
- /// Naturally edges don't have direction and thus
- /// don't have source and target node. However we use \c u() and \c v()
- /// methods to query the two nodes of the arc. The direction of the
- /// arc which arises this way is called the inherent direction of the
- /// edge, and is used to define the "default" direction
- /// of the directed versions of the arcs.
+ /// \brief The first node of the edge.
+ ///
+ /// Returns the first node of the given edge.
+ ///
+ /// Edges don't have source and target nodes, however, methods
+ /// u() and v() are used to query the two end-nodes of an edge.
+ /// The orientation of an edge that arises this way is called
+ /// the inherent direction, it is used to define the default
+ /// direction for the corresponding arcs.
/// \sa v()
/// \sa direction()
Node u(Edge) const { return INVALID; }
- /// \brief Second node of the edge.
- ///
- /// \return The second node of the given edge.
- ///
- /// Naturally edges don't have direction and thus
- /// don't have source and target node. However we use \c u() and \c v()
- /// methods to query the two nodes of the arc. The direction of the
- /// arc which arises this way is called the inherent direction of the
- /// edge, and is used to define the "default" direction
- /// of the directed versions of the arcs.
+ /// \brief The second node of the edge.
+ ///
+ /// Returns the second node of the given edge.
+ ///
+ /// Edges don't have source and target nodes, however, methods
+ /// u() and v() are used to query the two end-nodes of an edge.
+ /// The orientation of an edge that arises this way is called
+ /// the inherent direction, it is used to define the default
+ /// direction for the corresponding arcs.
/// \sa u()
/// \sa direction()
Node v(Edge) const { return INVALID; }
- /// \brief Source node of the directed arc.
+ /// \brief The source node of the arc.
+ ///
+ /// Returns the source node of the given arc.
Node source(Arc) const { return INVALID; }
- /// \brief Target node of the directed arc.
+ /// \brief The target node of the arc.
+ ///
+ /// Returns the target node of the given arc.
Node target(Arc) const { return INVALID; }
- /// \brief Returns the id of the node.
+ /// \brief The ID of the node.
+ ///
+ /// Returns the ID of the given node.
int id(Node) const { return -1; }
- /// \brief Returns the id of the edge.
+ /// \brief The ID of the edge.
+ ///
+ /// Returns the ID of the given edge.
int id(Edge) const { return -1; }
- /// \brief Returns the id of the arc.
+ /// \brief The ID of the arc.
+ ///
+ /// Returns the ID of the given arc.
int id(Arc) const { return -1; }
- /// \brief Returns the node with the given id.
- ///
- /// \pre The argument should be a valid node id in the graph.
+ /// \brief The node with the given ID.
+ ///
+ /// Returns the node with the given ID.
+ /// \pre The argument should be a valid node ID in the graph.
Node nodeFromId(int) const { return INVALID; }
- /// \brief Returns the edge with the given id.
- ///
- /// \pre The argument should be a valid edge id in the graph.
+ /// \brief The edge with the given ID.
+ ///
+ /// Returns the edge with the given ID.
+ /// \pre The argument should be a valid edge ID in the graph.
Edge edgeFromId(int) const { return INVALID; }
- /// \brief Returns the arc with the given id.
- ///
- /// \pre The argument should be a valid arc id in the graph.
+ /// \brief The arc with the given ID.
+ ///
+ /// Returns the arc with the given ID.
+ /// \pre The argument should be a valid arc ID in the graph.
Arc arcFromId(int) const { return INVALID; }
- /// \brief Returns an upper bound on the node IDs.
+ /// \brief An upper bound on the node IDs.
+ ///
+ /// Returns an upper bound on the node IDs.
int maxNodeId() const { return -1; }
- /// \brief Returns an upper bound on the edge IDs.
+ /// \brief An upper bound on the edge IDs.
+ ///
+ /// Returns an upper bound on the edge IDs.
int maxEdgeId() const { return -1; }
- /// \brief Returns an upper bound on the arc IDs.
+ /// \brief An upper bound on the arc IDs.
+ ///
+ /// Returns an upper bound on the arc IDs.
int maxArcId() const { return -1; }
+
+ /// \brief The direction of the arc.
+ ///
+ /// Returns \c true if the direction of the given arc is the same as
+ /// the inherent orientation of the represented edge.
+ bool direction(Arc) const { return true; }
+
+ /// \brief Direct the edge.
+ ///
+ /// Direct the given edge. The returned arc
+ /// represents the given edge and its direction comes
+ /// from the bool parameter. If it is \c true, then the direction
+ /// of the arc is the same as the inherent orientation of the edge.
+ Arc direct(Edge, bool) const {
+ return INVALID;
+ }
+
+ /// \brief Direct the edge.
+ ///
+ /// Direct the given edge. The returned arc represents the given
+ /// edge and its source node is the given node.
+ Arc direct(Edge, Node) const {
+ return INVALID;
+ }
+
+ /// \brief The oppositely directed arc.
+ ///
+ /// Returns the oppositely directed arc representing the same edge.
+ Arc oppositeArc(Arc) const { return INVALID; }
+
+ /// \brief The opposite node on the edge.
+ ///
+ /// Returns the opposite node on the given edge.
+ Node oppositeNode(Node, Edge) const { return INVALID; }
void first(Node&) const {}
@@ -706,45 +734,37 @@
int maxId(Arc) const { return -1; }
- /// \brief Base node of the iterator
- ///
- /// Returns the base node (the source in this case) of the iterator
- Node baseNode(OutArcIt e) const {
- return source(e);
- }
- /// \brief Running node of the iterator
- ///
- /// Returns the running node (the target in this case) of the
- /// iterator
- Node runningNode(OutArcIt e) const {
- return target(e);
- }
-
- /// \brief Base node of the iterator
- ///
- /// Returns the base node (the target in this case) of the iterator
- Node baseNode(InArcIt e) const {
- return target(e);
- }
- /// \brief Running node of the iterator
- ///
- /// Returns the running node (the source in this case) of the
- /// iterator
- Node runningNode(InArcIt e) const {
- return source(e);
- }
-
- /// \brief Base node of the iterator
- ///
- /// Returns the base node of the iterator
- Node baseNode(IncEdgeIt) const {
- return INVALID;
- }
-
- /// \brief Running node of the iterator
- ///
- /// Returns the running node of the iterator
- Node runningNode(IncEdgeIt) const {
- return INVALID;
- }
+ /// \brief The base node of the iterator.
+ ///
+ /// Returns the base node of the given incident edge iterator.
+ Node baseNode(IncEdgeIt) const { return INVALID; }
+
+ /// \brief The running node of the iterator.
+ ///
+ /// Returns the running node of the given incident edge iterator.
+ Node runningNode(IncEdgeIt) const { return INVALID; }
+
+ /// \brief The base node of the iterator.
+ ///
+ /// Returns the base node of the given outgoing arc iterator
+ /// (i.e. the source node of the corresponding arc).
+ Node baseNode(OutArcIt) const { return INVALID; }
+
+ /// \brief The running node of the iterator.
+ ///
+ /// Returns the running node of the given outgoing arc iterator
+ /// (i.e. the target node of the corresponding arc).
+ Node runningNode(OutArcIt) const { return INVALID; }
+
+ /// \brief The base node of the iterator.
+ ///
+ /// Returns the base node of the given incomming arc iterator
+ /// (i.e. the target node of the corresponding arc).
+ Node baseNode(InArcIt) const { return INVALID; }
+
+ /// \brief The running node of the iterator.
+ ///
+ /// Returns the running node of the given incomming arc iterator
+ /// (i.e. the source node of the corresponding arc).
+ Node runningNode(InArcIt) const { return INVALID; }
template
Index: lemon/concepts/graph_components.h
===================================================================
--- lemon/concepts/graph_components.h (revision 666)
+++ lemon/concepts/graph_components.h (revision 786)
@@ -19,5 +19,5 @@
///\ingroup graph_concepts
///\file
-///\brief The concept of graph components.
+///\brief The concepts of graph components.
#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
@@ -93,5 +93,5 @@
/// associative containers (e.g. \c std::map).
///
- /// \note This operator only have to define some strict ordering of
+ /// \note This operator only has to define some strict ordering of
/// the items; this order has nothing to do with the iteration
/// ordering of the items.
Index: lemon/concepts/maps.h
===================================================================
--- lemon/concepts/maps.h (revision 529)
+++ lemon/concepts/maps.h (revision 718)
@@ -183,5 +183,6 @@
template
struct Constraints {
- void constraints() {
+ typename enable_if::type
+ constraints() {
checkConcept, _ReferenceMap >();
ref = m[key];
Index: lemon/concepts/path.h
===================================================================
--- lemon/concepts/path.h (revision 559)
+++ lemon/concepts/path.h (revision 785)
@@ -19,5 +19,5 @@
///\ingroup concept
///\file
-///\brief Classes for representing paths in digraphs.
+///\brief The concept of paths
///
@@ -39,11 +39,20 @@
/// A skeleton structure for representing directed paths in a
/// digraph.
+ /// In a sense, a path can be treated as a list of arcs.
+ /// LEMON path types just store this list. As a consequence, they cannot
+ /// enumerate the nodes on the path directly and a zero length path
+ /// cannot store its source node.
+ ///
+ /// The arcs of a path should be stored in the order of their directions,
+ /// i.e. the target node of each arc should be the same as the source
+ /// node of the next arc. This consistency could be checked using
+ /// \ref checkPath().
+ /// The source and target nodes of a (consistent) path can be obtained
+ /// using \ref pathSource() and \ref pathTarget().
+ ///
+ /// A path can be constructed from another path of any type using the
+ /// copy constructor or the assignment operator.
+ ///
/// \tparam GR The digraph type in which the path is.
- ///
- /// In a sense, the path can be treated as a list of arcs. The
- /// lemon path type stores just this list. As a consequence it
- /// cannot enumerate the nodes in the path and the zero length
- /// paths cannot store the source.
- ///
template
class Path {
@@ -60,9 +69,9 @@
Path() {}
- /// \brief Template constructor
+ /// \brief Template copy constructor
template
Path(const CPath& cpath) {}
- /// \brief Template assigment
+ /// \brief Template assigment operator
template
Path& operator=(const CPath& cpath) {
@@ -71,5 +80,5 @@
}
- /// Length of the path ie. the number of arcs in the path.
+ /// Length of the path, i.e. the number of arcs on the path.
int length() const { return 0;}
@@ -80,7 +89,7 @@
void clear() {}
- /// \brief LEMON style iterator for path arcs
+ /// \brief LEMON style iterator for enumerating the arcs of a path.
///
- /// This class is used to iterate on the arcs of the paths.
+ /// LEMON style iterator class for enumerating the arcs of a path.
class ArcIt {
public:
@@ -89,8 +98,8 @@
/// Invalid constructor
ArcIt(Invalid) {}
- /// Constructor for first arc
+ /// Sets the iterator to the first arc of the given path
ArcIt(const Path &) {}
- /// Conversion to Arc
+ /// Conversion to \c Arc
operator Arc() const { return INVALID; }
@@ -193,22 +202,16 @@
///
/// A skeleton structure for path dumpers. The path dumpers are
- /// the generalization of the paths. The path dumpers can
- /// enumerate the arcs of the path wheter in forward or in
- /// backward order. In most time these classes are not used
- /// directly rather it used to assign a dumped class to a real
- /// path type.
+ /// the generalization of the paths, they can enumerate the arcs
+ /// of the path either in forward or in backward order.
+ /// These classes are typically not used directly, they are rather
+ /// used to be assigned to a real path type.
///
/// The main purpose of this concept is that the shortest path
- /// algorithms can enumerate easily the arcs in reverse order.
- /// If we would like to give back a real path from these
- /// algorithms then we should create a temporarly path object. In
- /// LEMON such algorithms gives back a path dumper what can
- /// assigned to a real path and the dumpers can be implemented as
+ /// algorithms can enumerate the arcs easily in reverse order.
+ /// In LEMON, such algorithms give back a (reverse) path dumper that
+ /// can be assigned to a real path. The dumpers can be implemented as
/// an adaptor class to the predecessor map.
///
/// \tparam GR The digraph type in which the path is.
- ///
- /// The paths can be constructed from any path type by a
- /// template constructor or a template assignment operator.
template
class PathDumper {
@@ -220,5 +223,5 @@
typedef typename Digraph::Arc Arc;
- /// Length of the path ie. the number of arcs in the path.
+ /// Length of the path, i.e. the number of arcs on the path.
int length() const { return 0;}
@@ -228,13 +231,12 @@
/// \brief Forward or reverse dumping
///
- /// If the RevPathTag is defined and true then reverse dumping
- /// is provided in the path dumper. In this case instead of the
- /// ArcIt the RevArcIt iterator should be implemented in the
- /// dumper.
+ /// If this tag is defined to be \c True, then reverse dumping
+ /// is provided in the path dumper. In this case, \c RevArcIt
+ /// iterator should be implemented instead of \c ArcIt iterator.
typedef False RevPathTag;
- /// \brief LEMON style iterator for path arcs
+ /// \brief LEMON style iterator for enumerating the arcs of a path.
///
- /// This class is used to iterate on the arcs of the paths.
+ /// LEMON style iterator class for enumerating the arcs of a path.
class ArcIt {
public:
@@ -243,8 +245,8 @@
/// Invalid constructor
ArcIt(Invalid) {}
- /// Constructor for first arc
+ /// Sets the iterator to the first arc of the given path
ArcIt(const PathDumper&) {}
- /// Conversion to Arc
+ /// Conversion to \c Arc
operator Arc() const { return INVALID; }
@@ -261,8 +263,9 @@
};
- /// \brief LEMON style iterator for path arcs
+ /// \brief LEMON style iterator for enumerating the arcs of a path
+ /// in reverse direction.
///
- /// This class is used to iterate on the arcs of the paths in
- /// reverse direction.
+ /// LEMON style iterator class for enumerating the arcs of a path
+ /// in reverse direction.
class RevArcIt {
public:
@@ -271,8 +274,8 @@
/// Invalid constructor
RevArcIt(Invalid) {}
- /// Constructor for first arc
+ /// Sets the iterator to the last arc of the given path
RevArcIt(const PathDumper &) {}
- /// Conversion to Arc
+ /// Conversion to \c Arc
operator Arc() const { return INVALID; }
Index: lemon/counter.h
===================================================================
--- lemon/counter.h (revision 440)
+++ lemon/counter.h (revision 786)
@@ -213,5 +213,5 @@
/// 'Do nothing' version of Counter.
- /// This class can be used in the same way as \ref Counter however it
+ /// This class can be used in the same way as \ref Counter, but it
/// does not count at all and does not print report on destruction.
///
Index: lemon/cplex.cc
===================================================================
--- lemon/cplex.cc (revision 576)
+++ lemon/cplex.cc (revision 746)
@@ -112,4 +112,37 @@
}
+ int CplexBase::_addRow(Value lb, ExprIterator b,
+ ExprIterator e, Value ub) {
+ int i = CPXgetnumrows(cplexEnv(), _prob);
+ if (lb == -INF) {
+ const char s = 'L';
+ CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
+ } else if (ub == INF) {
+ const char s = 'G';
+ CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
+ } else if (lb == ub){
+ const char s = 'E';
+ CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
+ } else {
+ const char s = 'R';
+ double len = ub - lb;
+ CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
+ }
+
+ std::vector indices;
+ std::vector rowlist;
+ std::vector values;
+
+ for(ExprIterator it=b; it!=e; ++it) {
+ indices.push_back(it->first);
+ values.push_back(it->second);
+ rowlist.push_back(i);
+ }
+
+ CPXchgcoeflist(cplexEnv(), _prob, values.size(),
+ &rowlist.front(), &indices.front(), &values.front());
+
+ return i;
+ }
void CplexBase::_eraseCol(int i) {
Index: lemon/cplex.h
===================================================================
--- lemon/cplex.h (revision 576)
+++ lemon/cplex.h (revision 746)
@@ -94,4 +94,5 @@
virtual int _addCol();
virtual int _addRow();
+ virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
virtual void _eraseCol(int i);
Index: lemon/dfs.h
===================================================================
--- lemon/dfs.h (revision 584)
+++ lemon/dfs.h (revision 788)
@@ -48,5 +48,5 @@
///The type of the map that stores the predecessor
///arcs of the %DFS paths.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap PredMap;
///Instantiates a \c PredMap.
@@ -63,5 +63,6 @@
///The type of the map that indicates which nodes are processed.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ ///By default, it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a \c ProcessedMap.
@@ -82,5 +83,5 @@
///The type of the map that indicates which nodes are reached.
- ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
///Instantiates a \c ReachedMap.
@@ -97,5 +98,5 @@
///The type of the map that stores the distances of the nodes.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap DistMap;
///Instantiates a \c DistMap.
@@ -225,5 +226,5 @@
///\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 Dfs > {
@@ -245,5 +246,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c DistMap type.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetDistMap : public Dfs< Digraph, SetDistMapTraits > {
@@ -265,5 +266,5 @@
///\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 Dfs< Digraph, SetReachedMapTraits > {
@@ -285,5 +286,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c ProcessedMap type.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits > {
@@ -412,6 +413,6 @@
///The simplest way to execute the DFS 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 a source node with \ref addSource()
+ ///If you need better control on the execution, you have to call
+ ///\ref init() first, then you can add a source node with \ref addSource()
///and perform the actual computation with \ref start().
///This procedure can be repeated if there are nodes that have not
@@ -633,10 +634,6 @@
///Runs the algorithm to visit all nodes in the digraph.
- ///This method runs the %DFS algorithm in order to compute the
- ///%DFS path to each node.
- ///
- ///The algorithm computes
- ///- the %DFS tree (forest),
- ///- the distance of each node from the root(s) in the %DFS tree.
+ ///This method runs the %DFS algorithm in order to visit all nodes
+ ///in the digraph.
///
///\note d.run() is just a shortcut of the following code.
@@ -670,7 +667,7 @@
///@{
- ///The DFS path to a node.
-
- ///Returns the DFS path to a node.
+ ///The DFS path to the given node.
+
+ ///Returns the DFS path to the given node from the root(s).
///
///\warning \c t should be reached from the root(s).
@@ -680,7 +677,7 @@
Path path(Node t) const { return Path(*G, *_pred, t); }
- ///The distance of a node from the root(s).
-
- ///Returns the distance of a node from the root(s).
+ ///The distance of the given node from the root(s).
+
+ ///Returns the distance of the given node from the root(s).
///
///\warning If node \c v is not reached from the root(s), then
@@ -691,5 +688,5 @@
int dist(Node v) const { return (*_dist)[v]; }
- ///Returns the 'previous arc' of the %DFS tree for a node.
+ ///Returns the 'previous arc' of the %DFS tree for the given node.
///This function returns the 'previous arc' of the %DFS tree for the
@@ -699,5 +696,5 @@
///
///The %DFS tree used here is equal to the %DFS tree used in
- ///\ref predNode().
+ ///\ref predNode() and \ref predMap().
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -705,13 +702,13 @@
Arc predArc(Node v) const { return (*_pred)[v];}
- ///Returns the 'previous node' of the %DFS tree.
+ ///Returns the 'previous node' of the %DFS tree for the given node.
///This function returns the 'previous node' of the %DFS
///tree for the node \c v, i.e. it returns the last but one node
- ///from a %DFS path from a root to \c v. It is \c INVALID
+ ///of a %DFS 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 %DFS tree used here is equal to the %DFS tree used in
- ///\ref predArc().
+ ///\ref predArc() and \ref predMap().
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -734,5 +731,5 @@
///
///Returns a const reference to the node map that stores the predecessor
- ///arcs, which form the DFS tree.
+ ///arcs, which form the DFS tree (forest).
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -740,5 +737,5 @@
const PredMap &predMap() const { return *_pred;}
- ///Checks if a node is reached from the root(s).
+ ///Checks if the given node. node is reached from the root(s).
///Returns \c true if \c v is reached from the root(s).
@@ -766,5 +763,5 @@
///The type of the map that stores the predecessor
///arcs of the %DFS 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.
@@ -781,6 +778,6 @@
///The type of the map that indicates which nodes are processed.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///By default it is a NullMap.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ ///By default, it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a ProcessedMap.
@@ -801,5 +798,5 @@
///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.
@@ -816,5 +813,5 @@
///The type of the map that stores the distances of the nodes.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap DistMap;
///Instantiates a DistMap.
@@ -831,5 +828,5 @@
///The type of the DFS paths.
- ///It must meet the \ref concepts::Path "Path" concept.
+ ///It must conform to the \ref concepts::Path "Path" concept.
typedef lemon::Path Path;
};
@@ -837,10 +834,6 @@
/// Default traits class used by DfsWizard
- /// To make it easier to use Dfs algorithm
- /// we have created a wizard class.
- /// This \ref DfsWizard class needs default traits,
- /// as well as the \ref Dfs class.
- /// The \ref DfsWizardBase is a class to be the default traits of the
- /// \ref DfsWizard class.
+ /// Default traits class used by DfsWizard.
+ /// \tparam GR The type of the digraph.
template
class DfsWizardBase : public DfsWizardDefaultTraits
@@ -870,5 +863,5 @@
/// Constructor.
- /// This constructor does not require parameters, therefore it initiates
+ /// This constructor does not require parameters, it initiates
/// all of the attributes to \c 0.
DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
@@ -900,5 +893,4 @@
typedef TR Base;
- ///The type of the digraph the algorithm runs on.
typedef typename TR::Digraph Digraph;
@@ -908,14 +900,8 @@
typedef typename Digraph::OutArcIt OutArcIt;
- ///\brief The type of the map that stores the predecessor
- ///arcs of the DFS 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 DFS paths
typedef typename TR::Path Path;
@@ -987,6 +973,6 @@
///Runs DFS algorithm to visit all nodes in the digraph.
- ///This method runs DFS algorithm in order to compute
- ///the DFS path to each node.
+ ///This method runs DFS algorithm in order to visit all nodes
+ ///in the digraph.
void run()
{
@@ -1000,9 +986,10 @@
SetPredMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting PredMap object.
- ///
- ///\ref named-func-param "Named parameter"
- ///for setting PredMap object.
+
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///the predecessor map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that stores the predecessor arcs of the nodes.
template
DfsWizard > predMap(const T &t)
@@ -1018,9 +1005,10 @@
SetReachedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting ReachedMap object.
- ///
- /// \ref named-func-param "Named parameter"
- ///for setting ReachedMap object.
+
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///the reached map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that indicates which nodes are reached.
template
DfsWizard > reachedMap(const T &t)
@@ -1036,9 +1024,11 @@
SetDistMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting DistMap object.
- ///
- /// \ref named-func-param "Named parameter"
- ///for setting DistMap object.
+
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///the distance map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that stores the distances of the nodes calculated
+ ///by the algorithm.
template
DfsWizard > distMap(const T &t)
@@ -1054,9 +1044,10 @@
SetProcessedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting ProcessedMap object.
- ///
- /// \ref named-func-param "Named parameter"
- ///for setting ProcessedMap object.
+
+ ///\brief \ref named-func-param "Named parameter" for setting
+ ///the processed map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that indicates which nodes are processed.
template
DfsWizard > processedMap(const T &t)
@@ -1209,5 +1200,5 @@
///
/// 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;
@@ -1370,6 +1361,6 @@
/// The simplest way to execute the DFS 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 a source node with \ref addSource()
+ /// If you need better control on the execution, you have to call
+ /// \ref init() first, then you can add a source node with \ref addSource()
/// and perform the actual computation with \ref start().
/// This procedure can be repeated if there are nodes that have not
@@ -1584,10 +1575,6 @@
/// \brief Runs the algorithm to visit all nodes in the digraph.
- /// This method runs the %DFS algorithm in order to
- /// compute the %DFS path to each node.
- ///
- /// The algorithm computes
- /// - the %DFS tree (forest),
- /// - the distance of each node from the root(s) in the %DFS tree.
+ /// This method runs the %DFS algorithm in order to visit all nodes
+ /// in the digraph.
///
/// \note d.run() is just a shortcut of the following code.
@@ -1621,5 +1608,5 @@
///@{
- /// \brief Checks if a node is reached from the root(s).
+ /// \brief Checks if the given node is reached from the root(s).
///
/// Returns \c true if \c v is reached from the root(s).
Index: lemon/dijkstra.h
===================================================================
--- lemon/dijkstra.h (revision 584)
+++ lemon/dijkstra.h (revision 788)
@@ -71,7 +71,7 @@
///The type of the map that stores the arc lengths.
- ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
+ ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
typedef LEN LengthMap;
- ///The type of the length of the arcs.
+ ///The type of the arc lengths.
typedef typename LEN::Value Value;
@@ -117,5 +117,5 @@
///The type of the map that stores the predecessor
///arcs of the shortest paths.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap PredMap;
///Instantiates a \c PredMap.
@@ -132,6 +132,6 @@
///The type of the map that indicates which nodes are processed.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///By default it is a NullMap.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ ///By default, it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a \c ProcessedMap.
@@ -152,5 +152,5 @@
///The type of the map that stores the distances of the nodes.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap DistMap;
///Instantiates a \c DistMap.
@@ -169,4 +169,8 @@
/// \ingroup shortest_path
///This class provides an efficient implementation of the %Dijkstra algorithm.
+ ///
+ ///The %Dijkstra algorithm solves the single-source shortest path problem
+ ///when all arc lengths are non-negative. If there are negative lengths,
+ ///the BellmanFord algorithm should be used instead.
///
///The arc lengths are passed to the algorithm using a
@@ -202,6 +206,6 @@
typedef typename TR::Digraph Digraph;
- ///The type of the length of the arcs.
- typedef typename TR::LengthMap::Value Value;
+ ///The type of the arc lengths.
+ typedef typename TR::Value Value;
///The type of the map that stores the arc lengths.
typedef typename TR::LengthMap LengthMap;
@@ -305,5 +309,5 @@
///\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
@@ -326,5 +330,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c DistMap type.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetDistMap
@@ -347,5 +351,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c ProcessedMap type.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetProcessedMap
@@ -423,5 +427,5 @@
///passed to the constructor of the cross reference and the cross
///reference should be passed to the constructor of the heap).
- ///However external heap and cross reference objects could also be
+ ///However, external heap and cross reference objects could also be
///passed to the algorithm using the \ref heap() function before
///calling \ref run(Node) "run()" or \ref init().
@@ -444,4 +448,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c OperationTraits type.
+ /// For more information, see \ref DijkstraDefaultOperationTraits.
template
struct SetOperationTraits
@@ -585,6 +590,6 @@
///The simplest way to execute the %Dijkstra 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.
@@ -802,12 +807,12 @@
///The results of the %Dijkstra algorithm can be obtained using these
///functions.\n
- ///Either \ref run(Node) "run()" or \ref start() should be called
+ ///Either \ref run(Node) "run()" or \ref init() should be called
///before using them.
///@{
- ///The shortest path to a node.
-
- ///Returns the shortest path to a node.
+ ///The shortest path to the given node.
+
+ ///Returns the shortest path to the given node from the root(s).
///
///\warning \c t should be reached from the root(s).
@@ -817,7 +822,7 @@
Path path(Node t) const { return Path(*G, *_pred, t); }
- ///The distance of a node from the root(s).
-
- ///Returns the distance of a node from the root(s).
+ ///The distance of the given node from the root(s).
+
+ ///Returns the distance of the given node from the root(s).
///
///\warning If node \c v is not reached from the root(s), then
@@ -828,6 +833,7 @@
Value 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
@@ -836,5 +842,5 @@
///
///The shortest path tree used here is equal to the shortest path
- ///tree used in \ref predNode().
+ ///tree used in \ref predNode() and \ref predMap().
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -842,13 +848,14 @@
Arc predArc(Node v) const { return (*_pred)[v]; }
- ///Returns the 'previous node' of the shortest path tree for a node.
-
+ ///\brief Returns the 'previous node' of the shortest path tree for
+ ///the given node.
+ ///
///This function returns the 'previous node' of the shortest path
///tree for the node \c v, i.e. it returns the last but one node
- ///from a shortest path from a root to \c v. It is \c INVALID
+ ///of a shortest path from a root to \c v. It is \c INVALID
///if \c v is not reached from the root(s) or if \c v is a root.
///
///The shortest path tree used here is equal to the shortest path
- ///tree used in \ref predArc().
+ ///tree used in \ref predArc() and \ref predMap().
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -871,5 +878,5 @@
///
///Returns a const reference to the node map that stores the predecessor
- ///arcs, which form the shortest path tree.
+ ///arcs, which form the shortest path tree (forest).
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -877,5 +884,5 @@
const PredMap &predMap() const { return *_pred;}
- ///Checks if a node is reached from the root(s).
+ ///Checks if the given node is reached from the root(s).
///Returns \c true if \c v is reached from the root(s).
@@ -896,7 +903,7 @@
Heap::POST_HEAP; }
- ///The current distance of a node from the root(s).
-
- ///Returns the current distance of a node from the root(s).
+ ///The current distance of the given node from the root(s).
+
+ ///Returns the current distance of the given node from the root(s).
///It may be decreased in the following processes.
///
@@ -925,7 +932,7 @@
///The type of the map that stores the arc lengths.
- ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
+ ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
typedef LEN LengthMap;
- ///The type of the length of the arcs.
+ ///The type of the arc lengths.
typedef typename LEN::Value Value;
@@ -974,5 +981,5 @@
///The type of the map that stores the predecessor
///arcs of the shortest paths.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap PredMap;
///Instantiates a PredMap.
@@ -989,6 +996,6 @@
///The type of the map that indicates which nodes are processed.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///By default it is a NullMap.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ ///By default, it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a ProcessedMap.
@@ -1009,5 +1016,5 @@
///The type of the map that stores the distances of the nodes.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap DistMap;
///Instantiates a DistMap.
@@ -1024,5 +1031,5 @@
///The type of the shortest paths.
- ///It must meet the \ref concepts::Path "Path" concept.
+ ///It must conform to the \ref concepts::Path "Path" concept.
typedef lemon::Path Path;
};
@@ -1030,10 +1037,7 @@
/// Default traits class used by DijkstraWizard
- /// To make it easier to use Dijkstra algorithm
- /// we have created a wizard class.
- /// This \ref DijkstraWizard class needs default traits,
- /// as well as the \ref Dijkstra class.
- /// The \ref DijkstraWizardBase is a class to be the default traits of the
- /// \ref DijkstraWizard class.
+ /// Default traits class used by DijkstraWizard.
+ /// \tparam GR The type of the digraph.
+ /// \tparam LEN The type of the length map.
template
class DijkstraWizardBase : public DijkstraWizardDefaultTraits
@@ -1094,5 +1098,4 @@
typedef TR Base;
- ///The type of the digraph the algorithm runs on.
typedef typename TR::Digraph Digraph;
@@ -1102,18 +1105,10 @@
typedef typename Digraph::OutArcIt OutArcIt;
- ///The type of the map that stores the arc lengths.
typedef typename TR::LengthMap LengthMap;
- ///The type of the length of the arcs.
typedef typename LengthMap::Value Value;
- ///\brief The type of the map that stores the predecessor
- ///arcs of the shortest paths.
typedef typename TR::PredMap PredMap;
- ///The type of the map that stores the distances of the nodes.
typedef typename TR::DistMap DistMap;
- ///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;
- ///The heap type used by the dijkstra algorithm.
typedef typename TR::Heap Heap;
@@ -1187,9 +1182,10 @@
SetPredMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting PredMap object.
- ///
- ///\ref named-func-param "Named parameter"
- ///for setting PredMap object.
+
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///the predecessor map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that stores the predecessor arcs of the nodes.
template
DijkstraWizard > predMap(const T &t)
@@ -1205,9 +1201,11 @@
SetDistMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting DistMap object.
- ///
- ///\ref named-func-param "Named parameter"
- ///for setting DistMap object.
+
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///the distance map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that stores the distances of the nodes calculated
+ ///by the algorithm.
template
DijkstraWizard > distMap(const T &t)
@@ -1223,9 +1221,10 @@
SetProcessedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-func-param "Named parameter"
- ///for setting ProcessedMap object.
- ///
- /// \ref named-func-param "Named parameter"
- ///for setting ProcessedMap object.
+
+ ///\brief \ref named-func-param "Named parameter" for setting
+ ///the processed map.
+ ///
+ ///\ref named-templ-param "Named parameter" function for setting
+ ///the map that indicates which nodes are processed.
template
DijkstraWizard > processedMap(const T &t)
@@ -1240,4 +1239,5 @@
SetPathBase(const TR &b) : TR(b) {}
};
+
///\brief \ref named-func-param "Named parameter"
///for getting the shortest path to the target node.
Index: lemon/dim2.h
===================================================================
--- lemon/dim2.h (revision 440)
+++ lemon/dim2.h (revision 714)
@@ -22,14 +22,7 @@
#include
-///\ingroup misc
+///\ingroup geomdat
///\file
///\brief A simple two dimensional vector and a bounding box implementation
-///
-/// The class \ref lemon::dim2::Point "dim2::Point" implements
-/// a two dimensional vector with the usual operations.
-///
-/// The class \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.
namespace lemon {
@@ -41,5 +34,5 @@
namespace dim2 {
- /// \addtogroup misc
+ /// \addtogroup geomdat
/// @{
Index: lemon/edge_set.h
===================================================================
--- lemon/edge_set.h (revision 670)
+++ lemon/edge_set.h (revision 787)
@@ -256,11 +256,12 @@
/// all arcs incident to the given node is erased from the arc set.
///
+ /// This class fully conforms to the \ref concepts::Digraph
+ /// "Digraph" concept.
+ /// It provides only linear time counting for nodes and arcs.
+ ///
/// \param GR The type of the graph which shares its node set with
/// this class. Its interface must conform to the
/// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
/// concept.
- ///
- /// This class fully conforms to the \ref concepts::Digraph
- /// "Digraph" concept.
template
class ListArcSet : public ArcSetExtender > {
@@ -686,10 +687,11 @@
/// incident to the given node is erased from the arc set.
///
+ /// This class fully conforms to the \ref concepts::Graph "Graph"
+ /// concept.
+ /// It provides only linear time counting for nodes, edges and arcs.
+ ///
/// \param GR The type of the graph which shares its node set
/// with this class. Its interface must conform to the
/// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
- /// concept.
- ///
- /// This class fully conforms to the \ref concepts::Graph "Graph"
/// concept.
template
@@ -868,5 +870,5 @@
}
- void next(Arc& arc) const {
+ static void next(Arc& arc) {
--arc.id;
}
@@ -955,11 +957,12 @@
/// arcs. Therefore the arcs cannot be erased from the arc sets.
///
+ /// This class fully conforms to the \ref concepts::Digraph "Digraph"
+ /// concept.
+ /// It provides only linear time counting for nodes and arcs.
+ ///
/// \warning If a node is erased from the underlying graph and this
/// node is the source or target of one arc in the arc set, then
/// the arc set is invalidated, and it cannot be used anymore. The
/// validity can be checked with the \c valid() member function.
- ///
- /// This class fully conforms to the \ref concepts::Digraph
- /// "Digraph" concept.
template
class SmartArcSet : public ArcSetExtender > {
@@ -1174,5 +1177,5 @@
}
- void next(Arc& arc) const {
+ static void next(Arc& arc) {
--arc.id;
}
@@ -1182,5 +1185,5 @@
}
- void next(Edge& arc) const {
+ static void next(Edge& arc) {
--arc.id;
}
@@ -1305,11 +1308,12 @@
/// edges cannot be erased from the edge sets.
///
+ /// This class fully conforms to the \ref concepts::Graph "Graph"
+ /// concept.
+ /// It provides only linear time counting for nodes, edges and arcs.
+ ///
/// \warning If a node is erased from the underlying graph and this
/// node is incident to one edge in the edge set, then the edge set
/// is invalidated, and it cannot be used anymore. The validity can
/// be checked with the \c valid() member function.
- ///
- /// This class fully conforms to the \ref concepts::Graph
- /// "Graph" concept.
template
class SmartEdgeSet : public EdgeSetExtender > {
Index: lemon/full_graph.h
===================================================================
--- lemon/full_graph.h (revision 617)
+++ lemon/full_graph.h (revision 787)
@@ -25,5 +25,5 @@
///\ingroup graphs
///\file
-///\brief FullGraph and FullDigraph classes.
+///\brief FullDigraph and FullGraph classes.
namespace lemon {
@@ -52,5 +52,5 @@
Node operator()(int ix) const { return Node(ix); }
- int index(const Node& node) const { return node._id; }
+ static int index(const Node& node) { return node._id; }
Arc arc(const Node& s, const Node& t) const {
@@ -149,22 +149,26 @@
/// \ingroup graphs
///
- /// \brief A full digraph class.
- ///
- /// This is a simple and fast directed full graph implementation.
- /// From each node go arcs to each node (including the source node),
- /// therefore the number of the arcs in the digraph is the square of
- /// the node number. This digraph type is completely static, so you
- /// can neither add nor delete either arcs or nodes, and it needs
- /// constant space in memory.
- ///
- /// This class fully conforms to the \ref concepts::Digraph
- /// "Digraph concept".
- ///
- /// The \c FullDigraph and \c FullGraph classes are very similar,
+ /// \brief A directed full graph class.
+ ///
+ /// FullDigraph is a simple and fast implmenetation of directed full
+ /// (complete) graphs. It contains an arc from each node to each node
+ /// (including a loop for each node), therefore the number of arcs
+ /// is the square of the number of nodes.
+ /// This class is completely static and it needs constant memory space.
+ /// Thus you can neither add nor delete nodes or arcs, however
+ /// the structure can be resized using resize().
+ ///
+ /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
+ /// Most of its member functions and nested classes are documented
+ /// only in the concept class.
+ ///
+ /// This class provides constant time counting for nodes and arcs.
+ ///
+ /// \note FullDigraph and FullGraph classes are very similar,
/// but there are two differences. While this class conforms only
- /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
- /// class conforms to the \ref concepts::Graph "Graph" concept,
- /// moreover \c FullGraph does not contain a loop arc for each
- /// node as \c FullDigraph does.
+ /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
+ /// conforms to the \ref concepts::Graph "Graph" concept,
+ /// moreover FullGraph does not contain a loop for each
+ /// node as this class does.
///
/// \sa FullGraph
@@ -174,5 +178,7 @@
public:
- /// \brief Constructor
+ /// \brief Default constructor.
+ ///
+ /// Default constructor. The number of nodes and arcs will be zero.
FullDigraph() { construct(0); }
@@ -185,6 +191,6 @@
/// \brief Resizes the digraph
///
- /// Resizes the digraph. The function will fully destroy and
- /// rebuild the digraph. This cause that the maps of the digraph will
+ /// This function resizes the digraph. It fully destroys and
+ /// rebuilds the structure, therefore the maps of the digraph will be
/// reallocated automatically and the previous values will be lost.
void resize(int n) {
@@ -198,7 +204,8 @@
/// \brief Returns the node with the given index.
///
- /// Returns the node with the given index. Since it is a static
- /// digraph its nodes can be indexed with integers from the range
- /// [0..nodeNum()-1].
+ /// Returns the node with the given index. Since this structure is
+ /// completely static, the nodes can be indexed with integers from
+ /// the range [0..nodeNum()-1].
+ /// The index of a node is the same as its ID.
/// \sa index()
Node operator()(int ix) const { return Parent::operator()(ix); }
@@ -206,14 +213,15 @@
/// \brief Returns the index of the given node.
///
- /// Returns the index of the given node. Since it is a static
- /// digraph its nodes can be indexed with integers from the range
- /// [0..nodeNum()-1].
- /// \sa operator()
- int index(const Node& node) const { return Parent::index(node); }
+ /// Returns the index of the given node. Since this structure is
+ /// completely static, the nodes can be indexed with integers from
+ /// the range [0..nodeNum()-1].
+ /// The index of a node is the same as its ID.
+ /// \sa operator()()
+ static int index(const Node& node) { return Parent::index(node); }
/// \brief Returns the arc connecting the given nodes.
///
/// Returns the arc connecting the given nodes.
- Arc arc(const Node& u, const Node& v) const {
+ Arc arc(Node u, Node v) const {
return Parent::arc(u, v);
}
@@ -284,5 +292,5 @@
Node operator()(int ix) const { return Node(ix); }
- int index(const Node& node) const { return node._id; }
+ static int index(const Node& node) { return node._id; }
Edge edge(const Node& u, const Node& v) const {
@@ -521,19 +529,23 @@
/// \brief An undirected full graph class.
///
- /// This is a simple and fast undirected full graph
- /// implementation. From each node go edge to each other node,
- /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
- /// This graph type is completely static, so you can neither
- /// add nor delete either edges or nodes, and it needs constant
- /// space in memory.
- ///
- /// This class fully conforms to the \ref concepts::Graph "Graph concept".
- ///
- /// The \c FullGraph and \c FullDigraph classes are very similar,
- /// but there are two differences. While the \c FullDigraph class
+ /// FullGraph is a simple and fast implmenetation of undirected full
+ /// (complete) graphs. It contains an edge between every distinct pair
+ /// of nodes, therefore the number of edges is n(n-1)/2.
+ /// This class is completely static and it needs constant memory space.
+ /// Thus you can neither add nor delete nodes or edges, however
+ /// the structure can be resized using resize().
+ ///
+ /// This type fully conforms to the \ref concepts::Graph "Graph concept".
+ /// Most of its member functions and nested classes are documented
+ /// only in the concept class.
+ ///
+ /// This class provides constant time counting for nodes, edges and arcs.
+ ///
+ /// \note FullDigraph and FullGraph classes are very similar,
+ /// but there are two differences. While FullDigraph
/// conforms only to the \ref concepts::Digraph "Digraph" concept,
/// this class conforms to the \ref concepts::Graph "Graph" concept,
- /// moreover \c FullGraph does not contain a loop arc for each
- /// node as \c FullDigraph does.
+ /// moreover this class does not contain a loop for each
+ /// node as FullDigraph does.
///
/// \sa FullDigraph
@@ -543,5 +555,7 @@
public:
- /// \brief Constructor
+ /// \brief Default constructor.
+ ///
+ /// Default constructor. The number of nodes and edges will be zero.
FullGraph() { construct(0); }
@@ -554,6 +568,6 @@
/// \brief Resizes the graph
///
- /// Resizes the graph. The function will fully destroy and
- /// rebuild the graph. This cause that the maps of the graph will
+ /// This function resizes the graph. It fully destroys and
+ /// rebuilds the structure, therefore the maps of the graph will be
/// reallocated automatically and the previous values will be lost.
void resize(int n) {
@@ -569,7 +583,8 @@
/// \brief Returns the node with the given index.
///
- /// Returns the node with the given index. Since it is a static
- /// graph its nodes can be indexed with integers from the range
- /// [0..nodeNum()-1].
+ /// Returns the node with the given index. Since this structure is
+ /// completely static, the nodes can be indexed with integers from
+ /// the range [0..nodeNum()-1].
+ /// The index of a node is the same as its ID.
/// \sa index()
Node operator()(int ix) const { return Parent::operator()(ix); }
@@ -577,21 +592,22 @@
/// \brief Returns the index of the given node.
///
- /// Returns the index of the given node. Since it is a static
- /// graph its nodes can be indexed with integers from the range
- /// [0..nodeNum()-1].
- /// \sa operator()
- int index(const Node& node) const { return Parent::index(node); }
+ /// Returns the index of the given node. Since this structure is
+ /// completely static, the nodes can be indexed with integers from
+ /// the range [0..nodeNum()-1].
+ /// The index of a node is the same as its ID.
+ /// \sa operator()()
+ static int index(const Node& node) { return Parent::index(node); }
/// \brief Returns the arc connecting the given nodes.
///
/// Returns the arc connecting the given nodes.
- Arc arc(const Node& s, const Node& t) const {
+ Arc arc(Node s, Node t) const {
return Parent::arc(s, t);
}
- /// \brief Returns the edge connects the given nodes.
- ///
- /// Returns the edge connects the given nodes.
- Edge edge(const Node& u, const Node& v) const {
+ /// \brief Returns the edge connecting the given nodes.
+ ///
+ /// Returns the edge connecting the given nodes.
+ Edge edge(Node u, Node v) const {
return Parent::edge(u, v);
}
Index: lemon/glpk.cc
===================================================================
--- lemon/glpk.cc (revision 576)
+++ lemon/glpk.cc (revision 746)
@@ -57,4 +57,40 @@
int i = glp_add_rows(lp, 1);
glp_set_row_bnds(lp, i, GLP_FR, 0.0, 0.0);
+ return i;
+ }
+
+ int GlpkBase::_addRow(Value lo, ExprIterator b,
+ ExprIterator e, Value up) {
+ int i = glp_add_rows(lp, 1);
+
+ if (lo == -INF) {
+ if (up == INF) {
+ glp_set_row_bnds(lp, i, GLP_FR, lo, up);
+ } else {
+ glp_set_row_bnds(lp, i, GLP_UP, lo, up);
+ }
+ } else {
+ if (up == INF) {
+ glp_set_row_bnds(lp, i, GLP_LO, lo, up);
+ } else if (lo != up) {
+ glp_set_row_bnds(lp, i, GLP_DB, lo, up);
+ } else {
+ glp_set_row_bnds(lp, i, GLP_FX, lo, up);
+ }
+ }
+
+ std::vector indexes;
+ std::vector values;
+
+ indexes.push_back(0);
+ values.push_back(0);
+
+ for(ExprIterator it = b; it != e; ++it) {
+ indexes.push_back(it->first);
+ values.push_back(it->second);
+ }
+
+ glp_set_mat_row(lp, i, values.size() - 1,
+ &indexes.front(), &values.front());
return i;
}
Index: lemon/glpk.h
===================================================================
--- lemon/glpk.h (revision 650)
+++ lemon/glpk.h (revision 746)
@@ -55,4 +55,5 @@
virtual int _addCol();
virtual int _addRow();
+ virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
virtual void _eraseCol(int i);
Index: lemon/gomory_hu.h
===================================================================
--- lemon/gomory_hu.h (revision 596)
+++ lemon/gomory_hu.h (revision 786)
@@ -295,9 +295,7 @@
/// \pre \ref run() must be called before using this function.
template
- Value minCutMap(const Node& s, ///<
+ Value minCutMap(const Node& s,
const Node& t,
- ///<
CutMap& cutMap
- ///<
) const {
Node sn = s, tn = t;
@@ -360,8 +358,8 @@
/// \c t.
/// \code
- /// GomoruHu gom(g, capacities);
+ /// GomoryHu gom(g, capacities);
/// gom.run();
/// int cnt=0;
- /// for(GomoruHu::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
+ /// for(GomoryHu::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
/// \endcode
class MinCutNodeIt
@@ -395,5 +393,5 @@
/// \endcode
/// does not necessarily give the same set of nodes.
- /// However it is ensured that
+ /// However, it is ensured that
/// \code
/// MinCutNodeIt(gomory, s, t, true);
@@ -457,8 +455,8 @@
/// \c t.
/// \code
- /// GomoruHu gom(g, capacities);
+ /// GomoryHu gom(g, capacities);
/// gom.run();
/// int value=0;
- /// for(GomoruHu::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
+ /// for(GomoryHu::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
/// value+=capacities[e];
/// \endcode
Index: lemon/graph_to_eps.h
===================================================================
--- lemon/graph_to_eps.h (revision 617)
+++ lemon/graph_to_eps.h (revision 786)
@@ -143,5 +143,5 @@
///\param gr Reference to the graph to be printed.
///\param ost Reference to the output stream.
- ///By default it is std::cout.
+ ///By default, it is std::cout.
///\param pros If it is \c true, then the \c ostream referenced by \c os
///will be explicitly deallocated by the destructor.
@@ -513,5 +513,5 @@
///Turn on/off pre-scaling
- ///By default graphToEps() rescales the whole image in order to avoid
+ ///By default, graphToEps() rescales the whole image in order to avoid
///very big or very small bounding boxes.
///
@@ -1115,5 +1115,5 @@
///\param g Reference to the graph to be printed.
///\param os Reference to the output stream.
-///By default it is std::cout.
+///By default, it is std::cout.
///
///This function also has a lot of
@@ -1127,5 +1127,5 @@
///\endcode
///
-///For more detailed examples see the \ref graph_to_eps_demo.cc demo file.
+///For more detailed examples, see the \ref graph_to_eps_demo.cc demo file.
///
///\warning Don't forget to put the \ref GraphToEps::run() "run()"
Index: lemon/grid_graph.h
===================================================================
--- lemon/grid_graph.h (revision 617)
+++ lemon/grid_graph.h (revision 787)
@@ -471,15 +471,19 @@
/// \brief Grid graph class
///
- /// This class implements a special graph type. The nodes of the
- /// graph can be indexed by two integer \c (i,j) value where \c i is
- /// in the \c [0..width()-1] range and j is in the \c
- /// [0..height()-1] range. Two nodes are connected in the graph if
- /// the indexes differ exactly on one position and exactly one is
- /// the difference. The nodes of the graph can be indexed by position
- /// with the \c operator()() function. The positions of the nodes can be
- /// get with \c pos(), \c col() and \c row() members. The outgoing
+ /// GridGraph implements a special graph type. The nodes of the
+ /// graph can be indexed by two integer values \c (i,j) where \c i is
+ /// in the range [0..width()-1] and j is in the range
+ /// [0..height()-1]. Two nodes are connected in the graph if
+ /// the indices differ exactly on one position and the difference is
+ /// also exactly one. The nodes of the graph can be obtained by position
+ /// using the \c operator()() function and the indices of the nodes can
+ /// be obtained using \c pos(), \c col() and \c row() members. The outgoing
/// arcs can be retrieved with the \c right(), \c up(), \c left()
/// and \c down() functions, where the bottom-left corner is the
/// origin.
+ ///
+ /// This class is completely static and it needs constant memory space.
+ /// Thus you can neither add nor delete nodes or edges, however
+ /// the structure can be resized using resize().
///
/// \image html grid_graph.png
@@ -497,6 +501,9 @@
///\endcode
///
- /// This graph type fully conforms to the \ref concepts::Graph
- /// "Graph concept".
+ /// This type fully conforms to the \ref concepts::Graph "Graph concept".
+ /// Most of its member functions and nested classes are documented
+ /// only in the concept class.
+ ///
+ /// This class provides constant time counting for nodes, edges and arcs.
class GridGraph : public ExtendedGridGraphBase {
typedef ExtendedGridGraphBase Parent;
@@ -504,7 +511,9 @@
public:
- /// \brief Map to get the indices of the nodes as dim2::Point.
- ///
- /// Map to get the indices of the nodes as dim2::Point.
+ /// \brief Map to get the indices of the nodes as \ref dim2::Point
+ /// "dim2::Point".
+ ///
+ /// Map to get the indices of the nodes as \ref dim2::Point
+ /// "dim2::Point".
class IndexMap {
public:
@@ -515,11 +524,7 @@
/// \brief Constructor
- ///
- /// Constructor
IndexMap(const GridGraph& graph) : _graph(graph) {}
/// \brief The subscript operator
- ///
- /// The subscript operator.
Value operator[](Key key) const {
return _graph.pos(key);
@@ -541,11 +546,7 @@
/// \brief Constructor
- ///
- /// Constructor
ColMap(const GridGraph& graph) : _graph(graph) {}
/// \brief The subscript operator
- ///
- /// The subscript operator.
Value operator[](Key key) const {
return _graph.col(key);
@@ -567,11 +568,7 @@
/// \brief Constructor
- ///
- /// Constructor
RowMap(const GridGraph& graph) : _graph(graph) {}
/// \brief The subscript operator
- ///
- /// The subscript operator.
Value operator[](Key key) const {
return _graph.row(key);
@@ -584,13 +581,12 @@
/// \brief Constructor
///
- /// Construct a grid graph with given size.
+ /// Construct a grid graph with the given size.
GridGraph(int width, int height) { construct(width, height); }
- /// \brief Resize the graph
- ///
- /// Resize the graph. The function will fully destroy and rebuild
- /// the graph. This cause that the maps of the graph will
- /// reallocated automatically and the previous values will be
- /// lost.
+ /// \brief Resizes the graph
+ ///
+ /// This function resizes the graph. It fully destroys and
+ /// rebuilds the structure, therefore the maps of the graph will be
+ /// reallocated automatically and the previous values will be lost.
void resize(int width, int height) {
Parent::notifier(Arc()).clear();
@@ -610,5 +606,5 @@
}
- /// \brief Gives back the column index of the node.
+ /// \brief The column index of the node.
///
/// Gives back the column index of the node.
@@ -617,5 +613,5 @@
}
- /// \brief Gives back the row index of the node.
+ /// \brief The row index of the node.
///
/// Gives back the row index of the node.
@@ -624,5 +620,5 @@
}
- /// \brief Gives back the position of the node.
+ /// \brief The position of the node.
///
/// Gives back the position of the node, ie. the (col,row) pair.
@@ -631,5 +627,5 @@
}
- /// \brief Gives back the number of the columns.
+ /// \brief The number of the columns.
///
/// Gives back the number of the columns.
@@ -638,5 +634,5 @@
}
- /// \brief Gives back the number of the rows.
+ /// \brief The number of the rows.
///
/// Gives back the number of the rows.
@@ -645,5 +641,5 @@
}
- /// \brief Gives back the arc goes right from the node.
+ /// \brief The arc goes right from the node.
///
/// Gives back the arc goes right from the node. If there is not
@@ -653,5 +649,5 @@
}
- /// \brief Gives back the arc goes left from the node.
+ /// \brief The arc goes left from the node.
///
/// Gives back the arc goes left from the node. If there is not
@@ -661,5 +657,5 @@
}
- /// \brief Gives back the arc goes up from the node.
+ /// \brief The arc goes up from the node.
///
/// Gives back the arc goes up from the node. If there is not
@@ -669,5 +665,5 @@
}
- /// \brief Gives back the arc goes down from the node.
+ /// \brief The arc goes down from the node.
///
/// Gives back the arc goes down from the node. If there is not
Index: lemon/hartmann_orlin.h
===================================================================
--- lemon/hartmann_orlin.h (revision 795)
+++ lemon/hartmann_orlin.h (revision 795)
@@ -0,0 +1,642 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * 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_HARTMANN_ORLIN_H
+#define LEMON_HARTMANN_ORLIN_H
+
+/// \ingroup min_mean_cycle
+///
+/// \file
+/// \brief Hartmann-Orlin's algorithm for finding a minimum mean cycle.
+
+#include
+#include
+#include
+#include
+#include
+#include
+
+namespace lemon {
+
+ /// \brief Default traits class of HartmannOrlin algorithm.
+ ///
+ /// Default traits class of HartmannOrlin algorithm.
+ /// \tparam GR The type of the digraph.
+ /// \tparam LEN The type of the length map.
+ /// It must conform to the \ref concepts::Rea_data "Rea_data" concept.
+#ifdef DOXYGEN
+ template
+#else
+ template ::is_integer>
+#endif
+ struct HartmannOrlinDefaultTraits
+ {
+ /// The type of the digraph
+ typedef GR Digraph;
+ /// The type of the length map
+ typedef LEN LengthMap;
+ /// The type of the arc lengths
+ typedef typename LengthMap::Value Value;
+
+ /// \brief The large value type used for internal computations
+ ///
+ /// The large value type used for internal computations.
+ /// It is \c long \c long if the \c Value type is integer,
+ /// otherwise it is \c double.
+ /// \c Value must be convertible to \c LargeValue.
+ typedef double LargeValue;
+
+ /// The tolerance type used for internal computations
+ typedef lemon::Tolerance Tolerance;
+
+ /// \brief The path type of the found cycles
+ ///
+ /// The path type of the found cycles.
+ /// It must conform to the \ref lemon::concepts::Path "Path" concept
+ /// and it must have an \c addFront() function.
+ typedef lemon::Path Path;
+ };
+
+ // Default traits class for integer value types
+ template
+ struct HartmannOrlinDefaultTraits
+ {
+ typedef GR Digraph;
+ typedef LEN LengthMap;
+ typedef typename LengthMap::Value Value;
+#ifdef LEMON_HAVE_LONG_LONG
+ typedef long long LargeValue;
+#else
+ typedef long LargeValue;
+#endif
+ typedef lemon::Tolerance Tolerance;
+ typedef lemon::Path Path;
+ };
+
+
+ /// \addtogroup min_mean_cycle
+ /// @{
+
+ /// \brief Implementation of the Hartmann-Orlin algorithm for finding
+ /// a minimum mean cycle.
+ ///
+ /// This class implements the Hartmann-Orlin algorithm for finding
+ /// a directed cycle of minimum mean length (cost) in a digraph
+ /// \ref amo93networkflows, \ref dasdan98minmeancycle.
+ /// It is an improved version of \ref Karp "Karp"'s original algorithm,
+ /// it applies an efficient early termination scheme.
+ /// It runs in time O(ne) and uses space O(n2+e).
+ ///
+ /// \tparam GR The type of the digraph the algorithm runs on.
+ /// \tparam LEN The type of the length map. The default
+ /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap".
+#ifdef DOXYGEN
+ template
+#else
+ template < typename GR,
+ typename LEN = typename GR::template ArcMap,
+ typename TR = HartmannOrlinDefaultTraits >
+#endif
+ class HartmannOrlin
+ {
+ public:
+
+ /// The type of the digraph
+ typedef typename TR::Digraph Digraph;
+ /// The type of the length map
+ typedef typename TR::LengthMap LengthMap;
+ /// The type of the arc lengths
+ typedef typename TR::Value Value;
+
+ /// \brief The large value type
+ ///
+ /// The large value type used for internal computations.
+ /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
+ /// it is \c long \c long if the \c Value type is integer,
+ /// otherwise it is \c double.
+ typedef typename TR::LargeValue LargeValue;
+
+ /// The tolerance type
+ typedef typename TR::Tolerance Tolerance;
+
+ /// \brief The path type of the found cycles
+ ///
+ /// The path type of the found cycles.
+ /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
+ /// it is \ref lemon::Path "Path".
+ typedef typename TR::Path Path;
+
+ /// The \ref HartmannOrlinDefaultTraits "traits class" of the algorithm
+ typedef TR Traits;
+
+ private:
+
+ TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+ // Data sturcture for path data
+ struct PathData
+ {
+ LargeValue dist;
+ Arc pred;
+ PathData(LargeValue d, Arc p = INVALID) :
+ dist(d), pred(p) {}
+ };
+
+ typedef typename Digraph::template NodeMap >
+ PathDataNodeMap;
+
+ private:
+
+ // The digraph the algorithm runs on
+ const Digraph &_gr;
+ // The length of the arcs
+ const LengthMap &_length;
+
+ // Data for storing the strongly connected components
+ int _comp_num;
+ typename Digraph::template NodeMap _comp;
+ std::vector > _comp_nodes;
+ std::vector* _nodes;
+ typename Digraph::template NodeMap > _out_arcs;
+
+ // Data for the found cycles
+ bool _curr_found, _best_found;
+ LargeValue _curr_length, _best_length;
+ int _curr_size, _best_size;
+ Node _curr_node, _best_node;
+ int _curr_level, _best_level;
+
+ Path *_cycle_path;
+ bool _local_path;
+
+ // Node map for storing path data
+ PathDataNodeMap _data;
+ // The processed nodes in the last round
+ std::vector _process;
+
+ Tolerance _tolerance;
+
+ // Infinite constant
+ const LargeValue INF;
+
+ public:
+
+ /// \name Named Template Parameters
+ /// @{
+
+ template
+ struct SetLargeValueTraits : public Traits {
+ typedef T LargeValue;
+ typedef lemon::Tolerance Tolerance;
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// \c LargeValue type.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting \c LargeValue
+ /// type. It is used for internal computations in the algorithm.
+ template
+ struct SetLargeValue
+ : public HartmannOrlin > {
+ typedef HartmannOrlin > Create;
+ };
+
+ template
+ struct SetPathTraits : public Traits {
+ typedef T Path;
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// \c %Path type.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting the \c %Path
+ /// type of the found cycles.
+ /// It must conform to the \ref lemon::concepts::Path "Path" concept
+ /// and it must have an \c addFront() function.
+ template
+ struct SetPath
+ : public HartmannOrlin > {
+ typedef HartmannOrlin > Create;
+ };
+
+ /// @}
+
+ public:
+
+ /// \brief Constructor.
+ ///
+ /// The constructor of the class.
+ ///
+ /// \param digraph The digraph the algorithm runs on.
+ /// \param length The lengths (costs) of the arcs.
+ HartmannOrlin( const Digraph &digraph,
+ const LengthMap &length ) :
+ _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
+ _best_found(false), _best_length(0), _best_size(1),
+ _cycle_path(NULL), _local_path(false), _data(digraph),
+ INF(std::numeric_limits::has_infinity ?
+ std::numeric_limits::infinity() :
+ std::numeric_limits::max())
+ {}
+
+ /// Destructor.
+ ~HartmannOrlin() {
+ if (_local_path) delete _cycle_path;
+ }
+
+ /// \brief Set the path structure for storing the found cycle.
+ ///
+ /// This function sets an external path structure for storing the
+ /// found cycle.
+ ///
+ /// If you don't call this function before calling \ref run() or
+ /// \ref findMinMean(), it will allocate a local \ref Path "path"
+ /// structure. The destuctor deallocates this automatically
+ /// allocated object, of course.
+ ///
+ /// \note The algorithm calls only the \ref lemon::Path::addFront()
+ /// "addFront()" function of the given path structure.
+ ///
+ /// \return (*this)
+ HartmannOrlin& cycle(Path &path) {
+ if (_local_path) {
+ delete _cycle_path;
+ _local_path = false;
+ }
+ _cycle_path = &path;
+ return *this;
+ }
+
+ /// \brief Set the tolerance used by the algorithm.
+ ///
+ /// This function sets the tolerance object used by the algorithm.
+ ///
+ /// \return (*this)
+ HartmannOrlin& tolerance(const Tolerance& tolerance) {
+ _tolerance = tolerance;
+ return *this;
+ }
+
+ /// \brief Return a const reference to the tolerance.
+ ///
+ /// This function returns a const reference to the tolerance object
+ /// used by the algorithm.
+ const Tolerance& tolerance() const {
+ return _tolerance;
+ }
+
+ /// \name Execution control
+ /// The simplest way to execute the algorithm is to call the \ref run()
+ /// function.\n
+ /// If you only need the minimum mean length, you may call
+ /// \ref findMinMean().
+
+ /// @{
+
+ /// \brief Run the algorithm.
+ ///
+ /// This function runs the algorithm.
+ /// It can be called more than once (e.g. if the underlying digraph
+ /// and/or the arc lengths have been modified).
+ ///
+ /// \return \c true if a directed cycle exists in the digraph.
+ ///
+ /// \note mmc.run() is just a shortcut of the following code.
+ /// \code
+ /// return mmc.findMinMean() && mmc.findCycle();
+ /// \endcode
+ bool run() {
+ return findMinMean() && findCycle();
+ }
+
+ /// \brief Find the minimum cycle mean.
+ ///
+ /// This function finds the minimum mean length of the directed
+ /// cycles in the digraph.
+ ///
+ /// \return \c true if a directed cycle exists in the digraph.
+ bool findMinMean() {
+ // Initialization and find strongly connected components
+ init();
+ findComponents();
+
+ // Find the minimum cycle mean in the components
+ for (int comp = 0; comp < _comp_num; ++comp) {
+ if (!initComponent(comp)) continue;
+ processRounds();
+
+ // Update the best cycle (global minimum mean cycle)
+ if ( _curr_found && (!_best_found ||
+ _curr_length * _best_size < _best_length * _curr_size) ) {
+ _best_found = true;
+ _best_length = _curr_length;
+ _best_size = _curr_size;
+ _best_node = _curr_node;
+ _best_level = _curr_level;
+ }
+ }
+ return _best_found;
+ }
+
+ /// \brief Find a minimum mean directed cycle.
+ ///
+ /// This function finds a directed cycle of minimum mean length
+ /// in the digraph using the data computed by findMinMean().
+ ///
+ /// \return \c true if a directed cycle exists in the digraph.
+ ///
+ /// \pre \ref findMinMean() must be called before using this function.
+ bool findCycle() {
+ if (!_best_found) return false;
+ IntNodeMap reached(_gr, -1);
+ int r = _best_level + 1;
+ Node u = _best_node;
+ while (reached[u] < 0) {
+ reached[u] = --r;
+ u = _gr.source(_data[u][r].pred);
+ }
+ r = reached[u];
+ Arc e = _data[u][r].pred;
+ _cycle_path->addFront(e);
+ _best_length = _length[e];
+ _best_size = 1;
+ Node v;
+ while ((v = _gr.source(e)) != u) {
+ e = _data[v][--r].pred;
+ _cycle_path->addFront(e);
+ _best_length += _length[e];
+ ++_best_size;
+ }
+ return true;
+ }
+
+ /// @}
+
+ /// \name Query Functions
+ /// The results of the algorithm can be obtained using these
+ /// functions.\n
+ /// The algorithm should be executed before using them.
+
+ /// @{
+
+ /// \brief Return the total length of the found cycle.
+ ///
+ /// This function returns the total length of the found cycle.
+ ///
+ /// \pre \ref run() or \ref findMinMean() must be called before
+ /// using this function.
+ LargeValue cycleLength() const {
+ return _best_length;
+ }
+
+ /// \brief Return the number of arcs on the found cycle.
+ ///
+ /// This function returns the number of arcs on the found cycle.
+ ///
+ /// \pre \ref run() or \ref findMinMean() must be called before
+ /// using this function.
+ int cycleArcNum() const {
+ return _best_size;
+ }
+
+ /// \brief Return the mean length of the found cycle.
+ ///
+ /// This function returns the mean length of the found cycle.
+ ///
+ /// \note alg.cycleMean() is just a shortcut of the
+ /// following code.
+ /// \code
+ /// return static_cast(alg.cycleLength()) / alg.cycleArcNum();
+ /// \endcode
+ ///
+ /// \pre \ref run() or \ref findMinMean() must be called before
+ /// using this function.
+ double cycleMean() const {
+ return static_cast(_best_length) / _best_size;
+ }
+
+ /// \brief Return the found cycle.
+ ///
+ /// This function returns a const reference to the path structure
+ /// storing the found cycle.
+ ///
+ /// \pre \ref run() or \ref findCycle() must be called before using
+ /// this function.
+ const Path& cycle() const {
+ return *_cycle_path;
+ }
+
+ ///@}
+
+ private:
+
+ // Initialization
+ void init() {
+ if (!_cycle_path) {
+ _local_path = true;
+ _cycle_path = new Path;
+ }
+ _cycle_path->clear();
+ _best_found = false;
+ _best_length = 0;
+ _best_size = 1;
+ _cycle_path->clear();
+ for (NodeIt u(_gr); u != INVALID; ++u)
+ _data[u].clear();
+ }
+
+ // Find strongly connected components and initialize _comp_nodes
+ // and _out_arcs
+ void findComponents() {
+ _comp_num = stronglyConnectedComponents(_gr, _comp);
+ _comp_nodes.resize(_comp_num);
+ if (_comp_num == 1) {
+ _comp_nodes[0].clear();
+ for (NodeIt n(_gr); n != INVALID; ++n) {
+ _comp_nodes[0].push_back(n);
+ _out_arcs[n].clear();
+ for (OutArcIt a(_gr, n); a != INVALID; ++a) {
+ _out_arcs[n].push_back(a);
+ }
+ }
+ } else {
+ for (int i = 0; i < _comp_num; ++i)
+ _comp_nodes[i].clear();
+ for (NodeIt n(_gr); n != INVALID; ++n) {
+ int k = _comp[n];
+ _comp_nodes[k].push_back(n);
+ _out_arcs[n].clear();
+ for (OutArcIt a(_gr, n); a != INVALID; ++a) {
+ if (_comp[_gr.target(a)] == k) _out_arcs[n].push_back(a);
+ }
+ }
+ }
+ }
+
+ // Initialize path data for the current component
+ bool initComponent(int comp) {
+ _nodes = &(_comp_nodes[comp]);
+ int n = _nodes->size();
+ if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) {
+ return false;
+ }
+ for (int i = 0; i < n; ++i) {
+ _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
+ }
+ return true;
+ }
+
+ // Process all rounds of computing path data for the current component.
+ // _data[v][k] is the length of a shortest directed walk from the root
+ // node to node v containing exactly k arcs.
+ void processRounds() {
+ Node start = (*_nodes)[0];
+ _data[start][0] = PathData(0);
+ _process.clear();
+ _process.push_back(start);
+
+ int k, n = _nodes->size();
+ int next_check = 4;
+ bool terminate = false;
+ for (k = 1; k <= n && int(_process.size()) < n && !terminate; ++k) {
+ processNextBuildRound(k);
+ if (k == next_check || k == n) {
+ terminate = checkTermination(k);
+ next_check = next_check * 3 / 2;
+ }
+ }
+ for ( ; k <= n && !terminate; ++k) {
+ processNextFullRound(k);
+ if (k == next_check || k == n) {
+ terminate = checkTermination(k);
+ next_check = next_check * 3 / 2;
+ }
+ }
+ }
+
+ // Process one round and rebuild _process
+ void processNextBuildRound(int k) {
+ std::vector next;
+ Node u, v;
+ Arc e;
+ LargeValue d;
+ for (int i = 0; i < int(_process.size()); ++i) {
+ u = _process[i];
+ for (int j = 0; j < int(_out_arcs[u].size()); ++j) {
+ e = _out_arcs[u][j];
+ v = _gr.target(e);
+ d = _data[u][k-1].dist + _length[e];
+ if (_tolerance.less(d, _data[v][k].dist)) {
+ if (_data[v][k].dist == INF) next.push_back(v);
+ _data[v][k] = PathData(d, e);
+ }
+ }
+ }
+ _process.swap(next);
+ }
+
+ // Process one round using _nodes instead of _process
+ void processNextFullRound(int k) {
+ Node u, v;
+ Arc e;
+ LargeValue d;
+ for (int i = 0; i < int(_nodes->size()); ++i) {
+ u = (*_nodes)[i];
+ for (int j = 0; j < int(_out_arcs[u].size()); ++j) {
+ e = _out_arcs[u][j];
+ v = _gr.target(e);
+ d = _data[u][k-1].dist + _length[e];
+ if (_tolerance.less(d, _data[v][k].dist)) {
+ _data[v][k] = PathData(d, e);
+ }
+ }
+ }
+ }
+
+ // Check early termination
+ bool checkTermination(int k) {
+ typedef std::pair Pair;
+ typename GR::template NodeMap level(_gr, Pair(-1, 0));
+ typename GR::template NodeMap pi(_gr);
+ int n = _nodes->size();
+ LargeValue length;
+ int size;
+ Node u;
+
+ // Search for cycles that are already found
+ _curr_found = false;
+ for (int i = 0; i < n; ++i) {
+ u = (*_nodes)[i];
+ if (_data[u][k].dist == INF) continue;
+ for (int j = k; j >= 0; --j) {
+ if (level[u].first == i && level[u].second > 0) {
+ // A cycle is found
+ length = _data[u][level[u].second].dist - _data[u][j].dist;
+ size = level[u].second - j;
+ if (!_curr_found || length * _curr_size < _curr_length * size) {
+ _curr_length = length;
+ _curr_size = size;
+ _curr_node = u;
+ _curr_level = level[u].second;
+ _curr_found = true;
+ }
+ }
+ level[u] = Pair(i, j);
+ if (j != 0) {
+ u = _gr.source(_data[u][j].pred);
+ }
+ }
+ }
+
+ // If at least one cycle is found, check the optimality condition
+ LargeValue d;
+ if (_curr_found && k < n) {
+ // Find node potentials
+ for (int i = 0; i < n; ++i) {
+ u = (*_nodes)[i];
+ pi[u] = INF;
+ for (int j = 0; j <= k; ++j) {
+ if (_data[u][j].dist < INF) {
+ d = _data[u][j].dist * _curr_size - j * _curr_length;
+ if (_tolerance.less(d, pi[u])) pi[u] = d;
+ }
+ }
+ }
+
+ // Check the optimality condition for all arcs
+ bool done = true;
+ for (ArcIt a(_gr); a != INVALID; ++a) {
+ if (_tolerance.less(_length[a] * _curr_size - _curr_length,
+ pi[_gr.target(a)] - pi[_gr.source(a)]) ) {
+ done = false;
+ break;
+ }
+ }
+ return done;
+ }
+ return (k == n);
+ }
+
+ }; //class HartmannOrlin
+
+ ///@}
+
+} //namespace lemon
+
+#endif //LEMON_HARTMANN_ORLIN_H
Index: lemon/howard.h
===================================================================
--- lemon/howard.h (revision 771)
+++ lemon/howard.h (revision 771)
@@ -0,0 +1,597 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * 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_HOWARD_H
+#define LEMON_HOWARD_H
+
+/// \ingroup min_mean_cycle
+///
+/// \file
+/// \brief Howard's algorithm for finding a minimum mean cycle.
+
+#include
+#include
+#include
+#include
+#include
+#include
+
+namespace lemon {
+
+ /// \brief Default traits class of Howard class.
+ ///
+ /// Default traits class of Howard class.
+ /// \tparam GR The type of the digraph.
+ /// \tparam LEN The type of the length map.
+ /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+#ifdef DOXYGEN
+ template
+#else
+ template ::is_integer>
+#endif
+ struct HowardDefaultTraits
+ {
+ /// The type of the digraph
+ typedef GR Digraph;
+ /// The type of the length map
+ typedef LEN LengthMap;
+ /// The type of the arc lengths
+ typedef typename LengthMap::Value Value;
+
+ /// \brief The large value type used for internal computations
+ ///
+ /// The large value type used for internal computations.
+ /// It is \c long \c long if the \c Value type is integer,
+ /// otherwise it is \c double.
+ /// \c Value must be convertible to \c LargeValue.
+ typedef double LargeValue;
+
+ /// The tolerance type used for internal computations
+ typedef lemon::Tolerance Tolerance;
+
+ /// \brief The path type of the found cycles
+ ///
+ /// The path type of the found cycles.
+ /// It must conform to the \ref lemon::concepts::Path "Path" concept
+ /// and it must have an \c addBack() function.
+ typedef lemon::Path Path;
+ };
+
+ // Default traits class for integer value types
+ template
+ struct HowardDefaultTraits
+ {
+ typedef GR Digraph;
+ typedef LEN LengthMap;
+ typedef typename LengthMap::Value Value;
+#ifdef LEMON_HAVE_LONG_LONG
+ typedef long long LargeValue;
+#else
+ typedef long LargeValue;
+#endif
+ typedef lemon::Tolerance Tolerance;
+ typedef lemon::Path Path;
+ };
+
+
+ /// \addtogroup min_mean_cycle
+ /// @{
+
+ /// \brief Implementation of Howard's algorithm for finding a minimum
+ /// mean cycle.
+ ///
+ /// This class implements Howard's policy iteration algorithm for finding
+ /// a directed cycle of minimum mean length (cost) in a digraph
+ /// \ref amo93networkflows, \ref dasdan98minmeancycle.
+ /// This class provides the most efficient algorithm for the
+ /// minimum mean cycle problem, though the best known theoretical
+ /// bound on its running time is exponential.
+ ///
+ /// \tparam GR The type of the digraph the algorithm runs on.
+ /// \tparam LEN The type of the length map. The default
+ /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap".
+#ifdef DOXYGEN
+ template
+#else
+ template < typename GR,
+ typename LEN = typename GR::template ArcMap,
+ typename TR = HowardDefaultTraits >
+#endif
+ class Howard
+ {
+ public:
+
+ /// The type of the digraph
+ typedef typename TR::Digraph Digraph;
+ /// The type of the length map
+ typedef typename TR::LengthMap LengthMap;
+ /// The type of the arc lengths
+ typedef typename TR::Value Value;
+
+ /// \brief The large value type
+ ///
+ /// The large value type used for internal computations.
+ /// Using the \ref HowardDefaultTraits "default traits class",
+ /// it is \c long \c long if the \c Value type is integer,
+ /// otherwise it is \c double.
+ typedef typename TR::LargeValue LargeValue;
+
+ /// The tolerance type
+ typedef typename TR::Tolerance Tolerance;
+
+ /// \brief The path type of the found cycles
+ ///
+ /// The path type of the found cycles.
+ /// Using the \ref HowardDefaultTraits "default traits class",
+ /// it is \ref lemon::Path "Path".
+ typedef typename TR::Path Path;
+
+ /// The \ref HowardDefaultTraits "traits class" of the algorithm
+ typedef TR Traits;
+
+ private:
+
+ TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+ // The digraph the algorithm runs on
+ const Digraph &_gr;
+ // The length of the arcs
+ const LengthMap &_length;
+
+ // Data for the found cycles
+ bool _curr_found, _best_found;
+ LargeValue _curr_length, _best_length;
+ int _curr_size, _best_size;
+ Node _curr_node, _best_node;
+
+ Path *_cycle_path;
+ bool _local_path;
+
+ // Internal data used by the algorithm
+ typename Digraph::template NodeMap _policy;
+ typename Digraph::template NodeMap _reached;
+ typename Digraph::template NodeMap _level;
+ typename Digraph::template NodeMap _dist;
+
+ // Data for storing the strongly connected components
+ int _comp_num;
+ typename Digraph::template NodeMap _comp;
+ std::vector > _comp_nodes;
+ std::vector* _nodes;
+ typename Digraph::template NodeMap > _in_arcs;
+
+ // Queue used for BFS search
+ std::vector _queue;
+ int _qfront, _qback;
+
+ Tolerance _tolerance;
+
+ // Infinite constant
+ const LargeValue INF;
+
+ public:
+
+ /// \name Named Template Parameters
+ /// @{
+
+ template
+ struct SetLargeValueTraits : public Traits {
+ typedef T LargeValue;
+ typedef lemon::Tolerance Tolerance;
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// \c LargeValue type.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting \c LargeValue
+ /// type. It is used for internal computations in the algorithm.
+ template
+ struct SetLargeValue
+ : public Howard > {
+ typedef Howard > Create;
+ };
+
+ template
+ struct SetPathTraits : public Traits {
+ typedef T Path;
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// \c %Path type.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting the \c %Path
+ /// type of the found cycles.
+ /// It must conform to the \ref lemon::concepts::Path "Path" concept
+ /// and it must have an \c addBack() function.
+ template
+ struct SetPath
+ : public Howard > {
+ typedef Howard > Create;
+ };
+
+ /// @}
+
+ public:
+
+ /// \brief Constructor.
+ ///
+ /// The constructor of the class.
+ ///
+ /// \param digraph The digraph the algorithm runs on.
+ /// \param length The lengths (costs) of the arcs.
+ Howard( const Digraph &digraph,
+ const LengthMap &length ) :
+ _gr(digraph), _length(length), _best_found(false),
+ _best_length(0), _best_size(1), _cycle_path(NULL), _local_path(false),
+ _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
+ _comp(digraph), _in_arcs(digraph),
+ INF(std::numeric_limits::has_infinity ?
+ std::numeric_limits::infinity() :
+ std::numeric_limits::max())
+ {}
+
+ /// Destructor.
+ ~Howard() {
+ if (_local_path) delete _cycle_path;
+ }
+
+ /// \brief Set the path structure for storing the found cycle.
+ ///
+ /// This function sets an external path structure for storing the
+ /// found cycle.
+ ///
+ /// If you don't call this function before calling \ref run() or
+ /// \ref findMinMean(), it will allocate a local \ref Path "path"
+ /// structure. The destuctor deallocates this automatically
+ /// allocated object, of course.
+ ///
+ /// \note The algorithm calls only the \ref lemon::Path::addBack()
+ /// "addBack()" function of the given path structure.
+ ///
+ /// \return (*this)
+ Howard& cycle(Path &path) {
+ if (_local_path) {
+ delete _cycle_path;
+ _local_path = false;
+ }
+ _cycle_path = &path;
+ return *this;
+ }
+
+ /// \brief Set the tolerance used by the algorithm.
+ ///
+ /// This function sets the tolerance object used by the algorithm.
+ ///
+ /// \return (*this)
+ Howard& tolerance(const Tolerance& tolerance) {
+ _tolerance = tolerance;
+ return *this;
+ }
+
+ /// \brief Return a const reference to the tolerance.
+ ///
+ /// This function returns a const reference to the tolerance object
+ /// used by the algorithm.
+ const Tolerance& tolerance() const {
+ return _tolerance;
+ }
+
+ /// \name Execution control
+ /// The simplest way to execute the algorithm is to call the \ref run()
+ /// function.\n
+ /// If you only need the minimum mean length, you may call
+ /// \ref findMinMean().
+
+ /// @{
+
+ /// \brief Run the algorithm.
+ ///
+ /// This function runs the algorithm.
+ /// It can be called more than once (e.g. if the underlying digraph
+ /// and/or the arc lengths have been modified).
+ ///
+ /// \return \c true if a directed cycle exists in the digraph.
+ ///
+ /// \note mmc.run() is just a shortcut of the following code.
+ /// \code
+ /// return mmc.findMinMean() && mmc.findCycle();
+ /// \endcode
+ bool run() {
+ return findMinMean() && findCycle();
+ }
+
+ /// \brief Find the minimum cycle mean.
+ ///
+ /// This function finds the minimum mean length of the directed
+ /// cycles in the digraph.
+ ///
+ /// \return \c true if a directed cycle exists in the digraph.
+ bool findMinMean() {
+ // Initialize and find strongly connected components
+ init();
+ findComponents();
+
+ // Find the minimum cycle mean in the components
+ for (int comp = 0; comp < _comp_num; ++comp) {
+ // Find the minimum mean cycle in the current component
+ if (!buildPolicyGraph(comp)) continue;
+ while (true) {
+ findPolicyCycle();
+ if (!computeNodeDistances()) break;
+ }
+ // Update the best cycle (global minimum mean cycle)
+ if ( _curr_found && (!_best_found ||
+ _curr_length * _best_size < _best_length * _curr_size) ) {
+ _best_found = true;
+ _best_length = _curr_length;
+ _best_size = _curr_size;
+ _best_node = _curr_node;
+ }
+ }
+ return _best_found;
+ }
+
+ /// \brief Find a minimum mean directed cycle.
+ ///
+ /// This function finds a directed cycle of minimum mean length
+ /// in the digraph using the data computed by findMinMean().
+ ///
+ /// \return \c true if a directed cycle exists in the digraph.
+ ///
+ /// \pre \ref findMinMean() must be called before using this function.
+ bool findCycle() {
+ if (!_best_found) return false;
+ _cycle_path->addBack(_policy[_best_node]);
+ for ( Node v = _best_node;
+ (v = _gr.target(_policy[v])) != _best_node; ) {
+ _cycle_path->addBack(_policy[v]);
+ }
+ return true;
+ }
+
+ /// @}
+
+ /// \name Query Functions
+ /// The results of the algorithm can be obtained using these
+ /// functions.\n
+ /// The algorithm should be executed before using them.
+
+ /// @{
+
+ /// \brief Return the total length of the found cycle.
+ ///
+ /// This function returns the total length of the found cycle.
+ ///
+ /// \pre \ref run() or \ref findMinMean() must be called before
+ /// using this function.
+ LargeValue cycleLength() const {
+ return _best_length;
+ }
+
+ /// \brief Return the number of arcs on the found cycle.
+ ///
+ /// This function returns the number of arcs on the found cycle.
+ ///
+ /// \pre \ref run() or \ref findMinMean() must be called before
+ /// using this function.
+ int cycleArcNum() const {
+ return _best_size;
+ }
+
+ /// \brief Return the mean length of the found cycle.
+ ///
+ /// This function returns the mean length of the found cycle.
+ ///
+ /// \note alg.cycleMean() is just a shortcut of the
+ /// following code.
+ /// \code
+ /// return static_cast(alg.cycleLength()) / alg.cycleArcNum();
+ /// \endcode
+ ///
+ /// \pre \ref run() or \ref findMinMean() must be called before
+ /// using this function.
+ double cycleMean() const {
+ return static_cast(_best_length) / _best_size;
+ }
+
+ /// \brief Return the found cycle.
+ ///
+ /// This function returns a const reference to the path structure
+ /// storing the found cycle.
+ ///
+ /// \pre \ref run() or \ref findCycle() must be called before using
+ /// this function.
+ const Path& cycle() const {
+ return *_cycle_path;
+ }
+
+ ///@}
+
+ private:
+
+ // Initialize
+ void init() {
+ if (!_cycle_path) {
+ _local_path = true;
+ _cycle_path = new Path;
+ }
+ _queue.resize(countNodes(_gr));
+ _best_found = false;
+ _best_length = 0;
+ _best_size = 1;
+ _cycle_path->clear();
+ }
+
+ // Find strongly connected components and initialize _comp_nodes
+ // and _in_arcs
+ void findComponents() {
+ _comp_num = stronglyConnectedComponents(_gr, _comp);
+ _comp_nodes.resize(_comp_num);
+ if (_comp_num == 1) {
+ _comp_nodes[0].clear();
+ for (NodeIt n(_gr); n != INVALID; ++n) {
+ _comp_nodes[0].push_back(n);
+ _in_arcs[n].clear();
+ for (InArcIt a(_gr, n); a != INVALID; ++a) {
+ _in_arcs[n].push_back(a);
+ }
+ }
+ } else {
+ for (int i = 0; i < _comp_num; ++i)
+ _comp_nodes[i].clear();
+ for (NodeIt n(_gr); n != INVALID; ++n) {
+ int k = _comp[n];
+ _comp_nodes[k].push_back(n);
+ _in_arcs[n].clear();
+ for (InArcIt a(_gr, n); a != INVALID; ++a) {
+ if (_comp[_gr.source(a)] == k) _in_arcs[n].push_back(a);
+ }
+ }
+ }
+ }
+
+ // Build the policy graph in the given strongly connected component
+ // (the out-degree of every node is 1)
+ bool buildPolicyGraph(int comp) {
+ _nodes = &(_comp_nodes[comp]);
+ if (_nodes->size() < 1 ||
+ (_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) {
+ return false;
+ }
+ for (int i = 0; i < int(_nodes->size()); ++i) {
+ _dist[(*_nodes)[i]] = INF;
+ }
+ Node u, v;
+ Arc e;
+ for (int i = 0; i < int(_nodes->size()); ++i) {
+ v = (*_nodes)[i];
+ for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
+ e = _in_arcs[v][j];
+ u = _gr.source(e);
+ if (_length[e] < _dist[u]) {
+ _dist[u] = _length[e];
+ _policy[u] = e;
+ }
+ }
+ }
+ return true;
+ }
+
+ // Find the minimum mean cycle in the policy graph
+ void findPolicyCycle() {
+ for (int i = 0; i < int(_nodes->size()); ++i) {
+ _level[(*_nodes)[i]] = -1;
+ }
+ LargeValue clength;
+ int csize;
+ Node u, v;
+ _curr_found = false;
+ for (int i = 0; i < int(_nodes->size()); ++i) {
+ u = (*_nodes)[i];
+ if (_level[u] >= 0) continue;
+ for (; _level[u] < 0; u = _gr.target(_policy[u])) {
+ _level[u] = i;
+ }
+ if (_level[u] == i) {
+ // A cycle is found
+ clength = _length[_policy[u]];
+ csize = 1;
+ for (v = u; (v = _gr.target(_policy[v])) != u; ) {
+ clength += _length[_policy[v]];
+ ++csize;
+ }
+ if ( !_curr_found ||
+ (clength * _curr_size < _curr_length * csize) ) {
+ _curr_found = true;
+ _curr_length = clength;
+ _curr_size = csize;
+ _curr_node = u;
+ }
+ }
+ }
+ }
+
+ // Contract the policy graph and compute node distances
+ bool computeNodeDistances() {
+ // Find the component of the main cycle and compute node distances
+ // using reverse BFS
+ for (int i = 0; i < int(_nodes->size()); ++i) {
+ _reached[(*_nodes)[i]] = false;
+ }
+ _qfront = _qback = 0;
+ _queue[0] = _curr_node;
+ _reached[_curr_node] = true;
+ _dist[_curr_node] = 0;
+ Node u, v;
+ Arc e;
+ while (_qfront <= _qback) {
+ v = _queue[_qfront++];
+ for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
+ e = _in_arcs[v][j];
+ u = _gr.source(e);
+ if (_policy[u] == e && !_reached[u]) {
+ _reached[u] = true;
+ _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
+ _queue[++_qback] = u;
+ }
+ }
+ }
+
+ // Connect all other nodes to this component and compute node
+ // distances using reverse BFS
+ _qfront = 0;
+ while (_qback < int(_nodes->size())-1) {
+ v = _queue[_qfront++];
+ for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
+ e = _in_arcs[v][j];
+ u = _gr.source(e);
+ if (!_reached[u]) {
+ _reached[u] = true;
+ _policy[u] = e;
+ _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
+ _queue[++_qback] = u;
+ }
+ }
+ }
+
+ // Improve node distances
+ bool improved = false;
+ for (int i = 0; i < int(_nodes->size()); ++i) {
+ v = (*_nodes)[i];
+ for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
+ e = _in_arcs[v][j];
+ u = _gr.source(e);
+ LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;
+ if (_tolerance.less(delta, _dist[u])) {
+ _dist[u] = delta;
+ _policy[u] = e;
+ improved = true;
+ }
+ }
+ }
+ return improved;
+ }
+
+ }; //class Howard
+
+ ///@}
+
+} //namespace lemon
+
+#endif //LEMON_HOWARD_H
Index: lemon/hypercube_graph.h
===================================================================
--- lemon/hypercube_graph.h (revision 617)
+++ lemon/hypercube_graph.h (revision 788)
@@ -263,5 +263,5 @@
}
- int index(Node node) const {
+ static int index(Node node) {
return node._id;
}
@@ -283,15 +283,21 @@
/// \brief Hypercube graph class
///
- /// This class implements a special graph type. The nodes of the graph
- /// are indiced with integers with at most \c dim binary digits.
+ /// HypercubeGraph implements a special graph type. The nodes of the
+ /// graph are indexed with integers having at most \c dim binary digits.
/// Two nodes are connected in the graph if and only if their indices
/// differ only on one position in the binary form.
+ /// This class is completely static and it needs constant memory space.
+ /// Thus you can neither add nor delete nodes or edges, however,
+ /// the structure can be resized using resize().
+ ///
+ /// This type fully conforms to the \ref concepts::Graph "Graph concept".
+ /// Most of its member functions and nested classes are documented
+ /// only in the concept class.
+ ///
+ /// This class provides constant time counting for nodes, edges and arcs.
///
/// \note The type of the indices is chosen to \c int for efficiency
/// reasons. Thus the maximum dimension of this implementation is 26
/// (assuming that the size of \c int is 32 bit).
- ///
- /// This graph type fully conforms to the \ref concepts::Graph
- /// "Graph concept".
class HypercubeGraph : public ExtendedHypercubeGraphBase {
typedef ExtendedHypercubeGraphBase Parent;
@@ -303,4 +309,19 @@
/// Constructs a hypercube graph with \c dim dimensions.
HypercubeGraph(int dim) { construct(dim); }
+
+ /// \brief Resizes the graph
+ ///
+ /// This function resizes the graph. It fully destroys and
+ /// rebuilds the structure, therefore the maps of the graph will be
+ /// reallocated automatically and the previous values will be lost.
+ void resize(int dim) {
+ Parent::notifier(Arc()).clear();
+ Parent::notifier(Edge()).clear();
+ Parent::notifier(Node()).clear();
+ construct(dim);
+ Parent::notifier(Node()).build();
+ Parent::notifier(Edge()).build();
+ Parent::notifier(Arc()).build();
+ }
/// \brief The number of dimensions.
@@ -321,5 +342,5 @@
///
/// Gives back the dimension id of the given edge.
- /// It is in the [0..dim-1] range.
+ /// It is in the range [0..dim-1].
int dimension(Edge edge) const {
return Parent::dimension(edge);
@@ -329,5 +350,5 @@
///
/// Gives back the dimension id of the given arc.
- /// It is in the [0..dim-1] range.
+ /// It is in the range [0..dim-1].
int dimension(Arc arc) const {
return Parent::dimension(arc);
@@ -338,5 +359,5 @@
/// Gives back the index of the given node.
/// The lower bits of the integer describes the node.
- int index(Node node) const {
+ static int index(Node node) {
return Parent::index(node);
}
Index: lemon/karp.h
===================================================================
--- lemon/karp.h (revision 772)
+++ lemon/karp.h (revision 772)
@@ -0,0 +1,582 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * 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_KARP_H
+#define LEMON_KARP_H
+
+/// \ingroup min_mean_cycle
+///
+/// \file
+/// \brief Karp's algorithm for finding a minimum mean cycle.
+
+#include
+#include
+#include
+#include
+#include
+#include
+
+namespace lemon {
+
+ /// \brief Default traits class of Karp algorithm.
+ ///
+ /// Default traits class of Karp algorithm.
+ /// \tparam GR The type of the digraph.
+ /// \tparam LEN The type of the length map.
+ /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+#ifdef DOXYGEN
+ template
+#else
+ template ::is_integer>
+#endif
+ struct KarpDefaultTraits
+ {
+ /// The type of the digraph
+ typedef GR Digraph;
+ /// The type of the length map
+ typedef LEN LengthMap;
+ /// The type of the arc lengths
+ typedef typename LengthMap::Value Value;
+
+ /// \brief The large value type used for internal computations
+ ///
+ /// The large value type used for internal computations.
+ /// It is \c long \c long if the \c Value type is integer,
+ /// otherwise it is \c double.
+ /// \c Value must be convertible to \c LargeValue.
+ typedef double LargeValue;
+
+ /// The tolerance type used for internal computations
+ typedef lemon::Tolerance Tolerance;
+
+ /// \brief The path type of the found cycles
+ ///
+ /// The path type of the found cycles.
+ /// It must conform to the \ref lemon::concepts::Path "Path" concept
+ /// and it must have an \c addFront() function.
+ typedef lemon::Path Path;
+ };
+
+ // Default traits class for integer value types
+ template
+ struct KarpDefaultTraits
+ {
+ typedef GR Digraph;
+ typedef LEN LengthMap;
+ typedef typename LengthMap::Value Value;
+#ifdef LEMON_HAVE_LONG_LONG
+ typedef long long LargeValue;
+#else
+ typedef long LargeValue;
+#endif
+ typedef lemon::Tolerance Tolerance;
+ typedef lemon::Path Path;
+ };
+
+
+ /// \addtogroup min_mean_cycle
+ /// @{
+
+ /// \brief Implementation of Karp's algorithm for finding a minimum
+ /// mean cycle.
+ ///
+ /// This class implements Karp's algorithm for finding a directed
+ /// cycle of minimum mean length (cost) in a digraph
+ /// \ref amo93networkflows, \ref dasdan98minmeancycle.
+ /// It runs in time O(ne) and uses space O(n2+e).
+ ///
+ /// \tparam GR The type of the digraph the algorithm runs on.
+ /// \tparam LEN The type of the length map. The default
+ /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap".
+#ifdef DOXYGEN
+ template
+#else
+ template < typename GR,
+ typename LEN = typename GR::template ArcMap,
+ typename TR = KarpDefaultTraits >
+#endif
+ class Karp
+ {
+ public:
+
+ /// The type of the digraph
+ typedef typename TR::Digraph Digraph;
+ /// The type of the length map
+ typedef typename TR::LengthMap LengthMap;
+ /// The type of the arc lengths
+ typedef typename TR::Value Value;
+
+ /// \brief The large value type
+ ///
+ /// The large value type used for internal computations.
+ /// Using the \ref KarpDefaultTraits "default traits class",
+ /// it is \c long \c long if the \c Value type is integer,
+ /// otherwise it is \c double.
+ typedef typename TR::LargeValue LargeValue;
+
+ /// The tolerance type
+ typedef typename TR::Tolerance Tolerance;
+
+ /// \brief The path type of the found cycles
+ ///
+ /// The path type of the found cycles.
+ /// Using the \ref KarpDefaultTraits "default traits class",
+ /// it is \ref lemon::Path "Path".
+ typedef typename TR::Path Path;
+
+ /// The \ref KarpDefaultTraits "traits class" of the algorithm
+ typedef TR Traits;
+
+ private:
+
+ TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+ // Data sturcture for path data
+ struct PathData
+ {
+ LargeValue dist;
+ Arc pred;
+ PathData(LargeValue d, Arc p = INVALID) :
+ dist(d), pred(p) {}
+ };
+
+ typedef typename Digraph::template NodeMap >
+ PathDataNodeMap;
+
+ private:
+
+ // The digraph the algorithm runs on
+ const Digraph &_gr;
+ // The length of the arcs
+ const LengthMap &_length;
+
+ // Data for storing the strongly connected components
+ int _comp_num;
+ typename Digraph::template NodeMap _comp;
+ std::vector > _comp_nodes;
+ std::vector* _nodes;
+ typename Digraph::template NodeMap > _out_arcs;
+
+ // Data for the found cycle
+ LargeValue _cycle_length;
+ int _cycle_size;
+ Node _cycle_node;
+
+ Path *_cycle_path;
+ bool _local_path;
+
+ // Node map for storing path data
+ PathDataNodeMap _data;
+ // The processed nodes in the last round
+ std::vector _process;
+
+ Tolerance _tolerance;
+
+ // Infinite constant
+ const LargeValue INF;
+
+ public:
+
+ /// \name Named Template Parameters
+ /// @{
+
+ template
+ struct SetLargeValueTraits : public Traits {
+ typedef T LargeValue;
+ typedef lemon::Tolerance Tolerance;
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// \c LargeValue type.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting \c LargeValue
+ /// type. It is used for internal computations in the algorithm.
+ template
+ struct SetLargeValue
+ : public Karp > {
+ typedef Karp > Create;
+ };
+
+ template