Index: gtags
===================================================================
--- .hgtags (revision 854)
+++ (revision )
@@ -1,2 +1,0 @@
-06f816565bef381024acd7c15beb74ba407e3546 r1.1
-78b7231f0b2e786f74a9b0dbb345fe8b17fa35f9 r1.1.1
Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt (revision 727)
+++ CMakeLists.txt (revision 791)
@@ -35,4 +35,6 @@
CHECK_TYPE_SIZE("long long" LONG_LONG)
SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
+
+INCLUDE(FindPythonInterp)
ENABLE_TESTING()
Index: Makefile.am
===================================================================
--- Makefile.am (revision 799)
+++ Makefile.am (revision 840)
@@ -45,4 +45,5 @@
include doc/Makefile.am
include tools/Makefile.am
+include scripts/Makefile.am
DIST_SUBDIRS = demo
Index: NEWS
===================================================================
--- NEWS (revision 853)
+++ NEWS (revision 712)
@@ -1,22 +1,2 @@
-2009-10-03 Version 1.1.1 released
-
- Bugfix release.
-
- #295: Suppress MSVC warnings using pragmas
- ----: Various CMAKE related improvements
- * Remove duplications from doc/CMakeLists.txt
- * Rename documentation install folder from 'docs' to 'html'
- * Add tools/CMakeLists.txt to the tarball
- * Generate and install LEMONConfig.cmake
- * Change the label of the html project in Visual Studio
- * Fix the check for the 'long long' type
- * Put the version string into config.h
- * Minor CMake improvements
- * Set the version to 'hg-tip' if everything fails
- #311: Add missing 'explicit' keywords
- #302: Fix the implementation and doc of CrossRefMap
- #308: Remove duplicate list_graph.h entry from source list
- #307: Bug fix in Preflow and Circulation
-
2009-05-13 Version 1.1 released
Index: configure.ac
===================================================================
--- configure.ac (revision 727)
+++ configure.ac (revision 840)
@@ -42,4 +42,5 @@
AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
+AC_CHECK_PROG([python_found],[python],[yes],[no])
AC_CHECK_PROG([gs_found],[gs],[yes],[no])
@@ -82,4 +83,19 @@
fi
AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
+
+dnl Support for running test cases using valgrind.
+use_valgrind=no
+AC_ARG_ENABLE([valgrind],
+AS_HELP_STRING([--enable-valgrind], [use valgrind when running tests]),
+ [use_valgrind=yes])
+
+if [[ "$use_valgrind" = "yes" ]]; then
+ AC_CHECK_PROG(HAVE_VALGRIND, valgrind, yes, no)
+
+ if [[ "$HAVE_VALGRIND" = "no" ]]; then
+ AC_MSG_ERROR([Valgrind not found in PATH.])
+ fi
+fi
+AM_CONDITIONAL(USE_VALGRIND, [test "$use_valgrind" = "yes"])
dnl Checks for header files.
@@ -128,4 +144,5 @@
echo
echo Build additional tools........ : $enable_tools
+echo Use valgrind for tests........ : $use_valgrind
echo
echo The packace will be installed in
Index: doc/CMakeLists.txt
===================================================================
--- doc/CMakeLists.txt (revision 726)
+++ doc/CMakeLists.txt (revision 895)
@@ -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)
@@ -27,6 +27,8 @@
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
COMMAND ${CMAKE_COMMAND} -E remove_directory html
+ COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
Index: doc/Doxyfile.in
===================================================================
--- doc/Doxyfile.in (revision 379)
+++ doc/Doxyfile.in (revision 803)
@@ -1,3 +1,3 @@
-# Doxyfile 1.5.7.1
+# Doxyfile 1.5.9
#---------------------------------------------------------------------------
@@ -22,5 +22,4 @@
QT_AUTOBRIEF = NO
MULTILINE_CPP_IS_BRIEF = NO
-DETAILS_AT_TOP = YES
INHERIT_DOCS = NO
SEPARATE_MEMBER_PAGES = NO
@@ -92,5 +91,6 @@
"@abs_top_srcdir@/demo" \
"@abs_top_srcdir@/tools" \
- "@abs_top_srcdir@/test/test_tools.h"
+ "@abs_top_srcdir@/test/test_tools.h" \
+ "@abs_top_builddir@/doc/references.dox"
INPUT_ENCODING = UTF-8
FILE_PATTERNS = *.h \
@@ -224,5 +224,5 @@
SKIP_FUNCTION_MACROS = YES
#---------------------------------------------------------------------------
-# Configuration::additions related to external references
+# Options related to the search engine
#---------------------------------------------------------------------------
TAGFILES = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ "
Index: doc/Makefile.am
===================================================================
--- doc/Makefile.am (revision 720)
+++ doc/Makefile.am (revision 895)
@@ -29,4 +29,5 @@
edge_biconnected_components.eps \
node_biconnected_components.eps \
+ planar.eps \
strongly_connected_components.eps
@@ -67,5 +68,17 @@
fi
-html-local: $(DOC_PNG_IMAGES)
+references.dox: doc/references.bib
+ if test ${python_found} = yes; then \
+ cd doc; \
+ python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \
+ cd ..; \
+ else \
+ echo; \
+ echo "Python not found."; \
+ echo; \
+ exit 1; \
+ fi
+
+html-local: $(DOC_PNG_IMAGES) references.dox
if test ${doxygen_found} = yes; then \
cd doc; \
Index: doc/groups.dox
===================================================================
--- doc/groups.dox (revision 844)
+++ doc/groups.dox (revision 879)
@@ -239,5 +239,34 @@
any kind of path structure.
-\sa lemon::concepts::Path
+\sa \ref concepts::Path "Path concept"
+*/
+
+/**
+@defgroup heaps Heap Structures
+@ingroup datas
+\brief %Heap structures implemented in LEMON.
+
+This group contains the heap structures implemented in LEMON.
+
+LEMON provides several heap classes. They are efficient implementations
+of the abstract data type \e priority \e queue. They store items with
+specified values called \e priorities in such a way that finding and
+removing the item with minimum priority are efficient.
+The basic operations are adding and erasing items, changing the priority
+of an item, etc.
+
+Heaps are crucial in several algorithms, such as Dijkstra and Prim.
+The heap implementations have the same interface, thus any of them can be
+used easily in such algorithms.
+
+\sa \ref concepts::Heap "Heap concept"
+*/
+
+/**
+@defgroup matrices Matrices
+@ingroup datas
+\brief Two dimensional data storages implemented in LEMON.
+
+This group contains two dimensional data storages implemented in LEMON.
*/
@@ -252,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
@@ -266,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.
*/
@@ -274,8 +326,17 @@
\brief Algorithms for finding shortest paths.
-This group contains the algorithms for finding shortest paths in digraphs.
-
- - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
- source node when all arc lengths are non-negative.
+This group contains the algorithms for finding shortest paths in digraphs
+\ref clrs01algorithms.
+
+ - \ref Dijkstra algorithm for finding shortest paths from a source node
+ when all arc lengths are non-negative.
+ - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
+ from a source node when arc lenghts can be either positive or negative,
+ but the digraph should not contain directed cycles with negative total
+ length.
+ - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
+ for solving the \e all-pairs \e shortest \e paths \e problem when arc
+ lenghts can be either positive or negative, but the digraph should
+ not contain directed cycles with negative total length.
- \ref Suurballe A successive shortest path algorithm for finding
arc-disjoint paths between two nodes having minimum total length.
@@ -283,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
@@ -288,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
@@ -302,8 +372,18 @@
\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
-\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
-Tarjan for solving this problem. It also provides functions to query the
-minimum cut, which is the dual problem of maximum flow.
-
+LEMON contains several algorithms for solving maximum flow problems:
+- \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
+problem of maximum flow.
\ref Circulation is a preflow push-relabel algorithm implemented directly
@@ -320,10 +400,23 @@
This group contains the algorithms for finding minimum cost flows and
-circulations. For more information about this problem and its dual
-solution see \ref min_cost_flow "Minimum Cost Flow Problem".
-
-\ref NetworkSimplex is an efficient implementation of the primal Network
-Simplex algorithm for finding minimum cost flows. It also provides dual
-solution (node potentials), if an optimal flow is found.
+circulations \ref amo93networkflows. For more information about this
+problem and its dual solution, see \ref min_cost_flow
+"Minimum Cost Flow Problem".
+
+LEMON contains several algorithms for this problem.
+ - \ref NetworkSimplex Primal Network Simplex algorithm with various
+ pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
+ - \ref CostScaling Cost Scaling algorithm based on push/augment and
+ relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
+ \ref bunnagel98efficient.
+ - \ref CapacityScaling Capacity Scaling algorithm based on the successive
+ shortest path method \ref edmondskarp72theoretical.
+ - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
+ strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
+
+In general NetworkSimplex is the most efficient implementation,
+but in special cases other algorithms could be faster.
+For example, if the total supply and/or capacities are rather small,
+CapacityScaling is usually the fastest algorithm (without effective scaling).
*/
@@ -343,5 +436,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:
@@ -349,4 +442,6 @@
- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
in directed graphs.
+- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
+ calculating minimum cut in undirected graphs.
- \ref GomoryHu "Gomory-Hu tree computation" for calculating
all-pairs minimum cut in undirected graphs.
@@ -357,13 +452,38 @@
/**
-@defgroup graph_properties Connectivity and Other Graph Properties
-@ingroup algs
-\brief Algorithms for discovering the graph properties
-
-This group contains the algorithms for discovering the graph properties
-like connectivity, bipartiteness, euler property, simplicity etc.
-
-\image html edge_biconnected_components.png
-\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
+@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
+@ingroup algs
+\brief Algorithms for finding minimum mean cycles.
+
+This group contains the algorithms for finding minimum mean cycles
+\ref clrs01algorithms, \ref amo93networkflows.
+
+The \e minimum \e mean \e cycle \e problem is to find a directed cycle
+of minimum mean length (cost) in a digraph.
+The mean length of a cycle is the average length of its arcs, i.e. the
+ratio between the total length of the cycle and the number of arcs on it.
+
+This problem has an important connection to \e conservative \e length
+\e functions, too. A length function on the arcs of a digraph is called
+conservative if and only if there is no directed cycle of negative total
+length. For an arbitrary length function, the negative of the minimum
+cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
+arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
+function.
+
+LEMON contains three algorithms for solving the minimum mean cycle problem:
+- \ref 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.
*/
@@ -373,10 +493,12 @@
\brief Algorithms for finding matchings in graphs and bipartite graphs.
-This group contains the algorithms for calculating matchings in graphs.
-The general matching problem is finding a subset of the edges for which
-each node has at most one incident edge.
+This group contains the algorithms for calculating
+matchings in graphs and bipartite graphs. The general matching problem is
+finding a subset of the edges for which each node has at most one incident
+edge.
There are several different algorithms for calculate matchings in
-graphs. The goal of the matching optimization
+graphs. The matching problems in bipartite graphs are generally
+easier than in general graphs. The goal of the matching optimization
can be finding maximum cardinality, maximum weight or minimum cost
matching. The search can be constrained to find perfect or
@@ -384,4 +506,14 @@
The matching algorithms implemented in LEMON:
+- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
+ for calculating maximum cardinality matching in bipartite graphs.
+- \ref PrBipartiteMatching Push-relabel algorithm
+ for calculating maximum cardinality matching in bipartite graphs.
+- \ref MaxWeightedBipartiteMatching
+ Successive shortest path algorithm for calculating maximum weighted
+ matching and maximum weighted bipartite matching in bipartite graphs.
+- \ref MinCostMaxBipartiteMatching
+ Successive shortest path algorithm for calculating minimum cost maximum
+ matching in bipartite graphs.
- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
maximum cardinality matching in general graphs.
@@ -397,10 +529,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.
*/
@@ -424,11 +580,31 @@
/**
-@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.
+*/
+
+/**
+@defgroup lp_utils Tools for Lp and Mip Solvers
+@ingroup lp_group
+\brief Helper tools to the Lp and Mip solvers.
+
+This group adds some helper tools to general optimization framework
+implemented in LEMON.
+*/
+
+/**
+@defgroup metah Metaheuristics
+@ingroup gen_opt_group
+\brief Metaheuristics for LEMON library.
+
+This group contains some metaheuristic optimization tools.
*/
@@ -503,5 +679,5 @@
/**
-@defgroup dimacs_group DIMACS format
+@defgroup dimacs_group DIMACS Format
@ingroup io_group
\brief Read and write files in DIMACS format
@@ -552,6 +728,6 @@
\brief Skeleton and concept checking classes for graph structures
-This group contains the skeletons and concept checking classes of LEMON's
-graph structures and helper classes used to implement these.
+This group contains the skeletons and concept checking classes of
+graph structures.
*/
@@ -565,4 +741,13 @@
/**
+@defgroup tools Standalone Utility Applications
+
+Some utility applications are listed here.
+
+The standard compilation procedure (./configure;make) will compile
+them, as well.
+*/
+
+/**
\anchor demoprograms
@@ -576,12 +761,3 @@
*/
-/**
-@defgroup tools Standalone Utility Applications
-
-Some utility applications are listed here.
-
-The standard compilation procedure (./configure;make) will compile
-them, as well.
-*/
-
}
Index: doc/images/planar.eps
===================================================================
--- doc/images/planar.eps (revision 895)
+++ doc/images/planar.eps (revision 895)
@@ -0,0 +1,181 @@
+%!PS-Adobe-2.0 EPSF-2.0
+%%Creator: LEMON, graphToEps()
+%%CreationDate: Fri Oct 19 18:32:32 2007
+%%BoundingBox: 0 0 596 842
+%%DocumentPaperSizes: a4
+%%EndComments
+/lb { setlinewidth setrgbcolor newpath moveto
+ 4 2 roll 1 index 1 index curveto stroke } bind def
+/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
+/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
+/sq { newpath 2 index 1 index add 2 index 2 index add moveto
+ 2 index 1 index sub 2 index 2 index add lineto
+ 2 index 1 index sub 2 index 2 index sub lineto
+ 2 index 1 index add 2 index 2 index sub lineto
+ closepath pop pop pop} bind def
+/di { newpath 2 index 1 index add 2 index moveto
+ 2 index 2 index 2 index add lineto
+ 2 index 1 index sub 2 index lineto
+ 2 index 2 index 2 index sub lineto
+ closepath pop pop pop} bind def
+/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
+ setrgbcolor 1.1 div sq fill
+ } bind def
+/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
+ setrgbcolor 1.1 div di fill
+ } bind def
+/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+ newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
+ lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
+ 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
+ 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/nmale {
+ 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+ newpath 5 index 5 index moveto
+ 5 index 4 index 1 mul 1.5 mul add
+ 5 index 5 index 3 sqrt 1.5 mul mul add
+ 1 index 1 index lineto
+ 1 index 1 index 7 index sub moveto
+ 1 index 1 index lineto
+ exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
+ stroke
+ 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/arrl 1 def
+/arrw 0.3 def
+/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
+/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
+ /w exch def /len exch def
+ newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
+ len w sub arrl sub dx dy lrl
+ arrw dy dx neg lrl
+ dx arrl w add mul dy w 2 div arrw add mul sub
+ dy arrl w add mul dx w 2 div arrw add mul add rlineto
+ dx arrl w add mul neg dy w 2 div arrw add mul sub
+ dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
+ arrw dy dx neg lrl
+ len w sub arrl sub neg dx dy lrl
+ closepath fill } bind def
+/cshow { 2 index 2 index moveto dup stringwidth pop
+ neg 2 div fosi .35 mul neg rmoveto show pop pop} def
+
+gsave
+15 138.307 translate
+12.7843 dup scale
+90 rotate
+0.608112 -43.6081 translate
+%Edges:
+gsave
+9 31 9.5 30.5 10 30 0 0 0 0.091217 lb
+9 31 5.5 34.5 2 38 0 0 0 0.091217 lb
+9 31 25.5 16 42 1 0 0 0 0.091217 lb
+3 40 23 20.5 43 1 0 0 0 0.091217 lb
+3 40 22.5 20.5 42 1 0 0 0 0.091217 lb
+3 40 2.5 40.5 2 41 0 0 0 0.091217 lb
+13 25 10.5 24.5 8 24 0 0 0 0.091217 lb
+13 25 12 27 11 29 0 0 0 0.091217 lb
+3 4 2.5 3 2 2 0 0 0 0.091217 lb
+3 4 4.5 3 6 2 0 0 0 0.091217 lb
+6 25 7 24.5 8 24 0 0 0 0.091217 lb
+6 25 6 24.5 6 24 0 0 0 0.091217 lb
+34 2 33.5 2 33 2 0 0 0 0.091217 lb
+34 2 35 2 36 2 0 0 0 0.091217 lb
+6 8 16 9 26 10 0 0 0 0.091217 lb
+6 8 6 10.5 6 13 0 0 0 0.091217 lb
+6 8 6 7.5 6 7 0 0 0 0.091217 lb
+26 10 27.5 8.5 29 7 0 0 0 0.091217 lb
+26 10 27.5 9 29 8 0 0 0 0.091217 lb
+10 30 10.5 29.5 11 29 0 0 0 0.091217 lb
+8 24 7 23.5 6 23 0 0 0 0.091217 lb
+8 24 8 24.5 8 25 0 0 0 0.091217 lb
+33 2 32.5 2 32 2 0 0 0 0.091217 lb
+29 7 17.5 7 6 7 0 0 0 0.091217 lb
+2 2 1.5 22 1 42 0 0 0 0.091217 lb
+2 2 3.5 2 5 2 0 0 0 0.091217 lb
+21 15 13.5 14.5 6 14 0 0 0 0.091217 lb
+21 15 21 15.5 21 16 0 0 0 0.091217 lb
+1 42 0.5 42.5 0 43 0 0 0 0.091217 lb
+1 42 1.5 41.5 2 41 0 0 0 0.091217 lb
+6 15 6 15.5 6 16 0 0 0 0.091217 lb
+6 15 6 14.5 6 14 0 0 0 0.091217 lb
+43 1 22 0.5 1 0 0 0 0 0.091217 lb
+31 2 18.5 2 6 2 0 0 0 0.091217 lb
+31 2 31.5 2 32 2 0 0 0 0.091217 lb
+6 24 6 23.5 6 23 0 0 0 0.091217 lb
+6 16 6 16.5 6 17 0 0 0 0.091217 lb
+6 23 6 20 6 17 0 0 0 0.091217 lb
+6 2 5.5 2 5 2 0 0 0 0.091217 lb
+6 2 6 4.5 6 7 0 0 0 0.091217 lb
+0 43 0.5 21.5 1 0 0 0 0 0.091217 lb
+1 1 19.5 1.5 38 2 0 0 0 0.091217 lb
+1 1 1 0.5 1 0 0 0 0 0.091217 lb
+2 38 5.5 31.5 9 25 0 0 0 0.091217 lb
+25 13 15.5 13 6 13 0 0 0 0.091217 lb
+25 13 15.5 13.5 6 14 0 0 0 0.091217 lb
+8 25 8.5 25 9 25 0 0 0 0.091217 lb
+11 29 24.5 15.5 38 2 0 0 0 0.091217 lb
+6 17 11.5 18 17 19 0 0 0 0.091217 lb
+16 23 26.5 12.5 37 2 0 0 0 0.091217 lb
+16 23 18.5 19.5 21 16 0 0 0 0.091217 lb
+36 2 36.5 2 37 2 0 0 0 0.091217 lb
+36 2 32.5 5 29 8 0 0 0 0.091217 lb
+6 13 6 13.5 6 14 0 0 0 0.091217 lb
+37 2 37.5 2 38 2 0 0 0 0.091217 lb
+21 16 19 17.5 17 19 0 0 0 0.091217 lb
+grestore
+%Nodes:
+gsave
+29 8 0.304556 1 1 1 nc
+2 41 0.304556 1 1 1 nc
+6 7 0.304556 1 1 1 nc
+5 2 0.304556 1 1 1 nc
+17 19 0.304556 1 1 1 nc
+21 16 0.304556 1 1 1 nc
+1 0 0.304556 1 1 1 nc
+9 25 0.304556 1 1 1 nc
+6 14 0.304556 1 1 1 nc
+42 1 0.304556 1 1 1 nc
+38 2 0.304556 1 1 1 nc
+37 2 0.304556 1 1 1 nc
+6 13 0.304556 1 1 1 nc
+36 2 0.304556 1 1 1 nc
+16 23 0.304556 1 1 1 nc
+6 17 0.304556 1 1 1 nc
+11 29 0.304556 1 1 1 nc
+8 25 0.304556 1 1 1 nc
+32 2 0.304556 1 1 1 nc
+25 13 0.304556 1 1 1 nc
+2 38 0.304556 1 1 1 nc
+1 1 0.304556 1 1 1 nc
+0 43 0.304556 1 1 1 nc
+6 2 0.304556 1 1 1 nc
+6 23 0.304556 1 1 1 nc
+6 16 0.304556 1 1 1 nc
+6 24 0.304556 1 1 1 nc
+31 2 0.304556 1 1 1 nc
+43 1 0.304556 1 1 1 nc
+6 15 0.304556 1 1 1 nc
+1 42 0.304556 1 1 1 nc
+21 15 0.304556 1 1 1 nc
+2 2 0.304556 1 1 1 nc
+29 7 0.304556 1 1 1 nc
+33 2 0.304556 1 1 1 nc
+8 24 0.304556 1 1 1 nc
+10 30 0.304556 1 1 1 nc
+26 10 0.304556 1 1 1 nc
+6 8 0.304556 1 1 1 nc
+34 2 0.304556 1 1 1 nc
+6 25 0.304556 1 1 1 nc
+3 4 0.304556 1 1 1 nc
+13 25 0.304556 1 1 1 nc
+3 40 0.304556 1 1 1 nc
+9 31 0.304556 1 1 1 nc
+grestore
+grestore
+showpage
Index: doc/mainpage.dox
===================================================================
--- doc/mainpage.dox (revision 705)
+++ doc/mainpage.dox (revision 802)
@@ -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 710)
+++ doc/min_cost_flow.dox (revision 835)
@@ -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 802)
+++ doc/references.bib (revision 802)
@@ -0,0 +1,301 @@
+%%%%% Defining LEMON %%%%%
+
+@misc{lemon,
+ key = {LEMON},
+ title = {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and
+ {O}ptimization in {N}etworks},
+ howpublished = {\url{http://lemon.cs.elte.hu/}},
+ year = 2009
+}
+
+@misc{egres,
+ key = {EGRES},
+ title = {{EGRES} -- {E}gerv{\'a}ry {R}esearch {G}roup on
+ {C}ombinatorial {O}ptimization},
+ url = {http://www.cs.elte.hu/egres/}
+}
+
+@misc{coinor,
+ key = {COIN-OR},
+ title = {{COIN-OR} -- {C}omputational {I}nfrastructure for
+ {O}perations {R}esearch},
+ url = {http://www.coin-or.org/}
+}
+
+
+%%%%% Other libraries %%%%%%
+
+@misc{boost,
+ key = {Boost},
+ title = {{B}oost {C++} {L}ibraries},
+ url = {http://www.boost.org/}
+}
+
+@book{bglbook,
+ author = {Jeremy G. Siek and Lee-Quan Lee and Andrew
+ Lumsdaine},
+ title = {The Boost Graph Library: User Guide and Reference
+ Manual},
+ publisher = {Addison-Wesley},
+ year = 2002
+}
+
+@misc{leda,
+ key = {LEDA},
+ title = {{LEDA} -- {L}ibrary of {E}fficient {D}ata {T}ypes and
+ {A}lgorithms},
+ url = {http://www.algorithmic-solutions.com/}
+}
+
+@book{ledabook,
+ author = {Kurt Mehlhorn and Stefan N{\"a}her},
+ title = {{LEDA}: {A} platform for combinatorial and geometric
+ computing},
+ isbn = {0-521-56329-1},
+ publisher = {Cambridge University Press},
+ address = {New York, NY, USA},
+ year = 1999
+}
+
+
+%%%%% Tools that LEMON depends on %%%%%
+
+@misc{cmake,
+ key = {CMake},
+ title = {{CMake} -- {C}ross {P}latform {M}ake},
+ url = {http://www.cmake.org/}
+}
+
+@misc{doxygen,
+ key = {Doxygen},
+ title = {{Doxygen} -- {S}ource code documentation generator
+ tool},
+ url = {http://www.doxygen.org/}
+}
+
+
+%%%%% LP/MIP libraries %%%%%
+
+@misc{glpk,
+ key = {GLPK},
+ title = {{GLPK} -- {GNU} {L}inear {P}rogramming {K}it},
+ url = {http://www.gnu.org/software/glpk/}
+}
+
+@misc{clp,
+ key = {Clp},
+ title = {{Clp} -- {Coin-Or} {L}inear {P}rogramming},
+ url = {http://projects.coin-or.org/Clp/}
+}
+
+@misc{cbc,
+ key = {Cbc},
+ title = {{Cbc} -- {Coin-Or} {B}ranch and {C}ut},
+ url = {http://projects.coin-or.org/Cbc/}
+}
+
+@misc{cplex,
+ key = {CPLEX},
+ title = {{ILOG} {CPLEX}},
+ url = {http://www.ilog.com/}
+}
+
+@misc{soplex,
+ key = {SoPlex},
+ title = {{SoPlex} -- {T}he {S}equential {O}bject-{O}riented
+ {S}implex},
+ url = {http://soplex.zib.de/}
+}
+
+
+%%%%% General books %%%%%
+
+@book{amo93networkflows,
+ author = {Ravindra K. Ahuja and Thomas L. Magnanti and James
+ B. Orlin},
+ title = {Network Flows: Theory, Algorithms, and Applications},
+ publisher = {Prentice-Hall, Inc.},
+ year = 1993,
+ month = feb,
+ isbn = {978-0136175490}
+}
+
+@book{schrijver03combinatorial,
+ author = {Alexander Schrijver},
+ title = {Combinatorial Optimization: Polyhedra and Efficiency},
+ publisher = {Springer-Verlag},
+ year = 2003,
+ isbn = {978-3540443896}
+}
+
+@book{clrs01algorithms,
+ author = {Thomas H. Cormen and Charles E. Leiserson and Ronald
+ L. Rivest and Clifford Stein},
+ title = {Introduction to Algorithms},
+ publisher = {The MIT Press},
+ year = 2001,
+ edition = {2nd}
+}
+
+@book{stroustrup00cpp,
+ author = {Bjarne Stroustrup},
+ title = {The C++ Programming Language},
+ edition = {3rd},
+ publisher = {Addison-Wesley Professional},
+ isbn = 0201700735,
+ month = {February},
+ year = 2000
+}
+
+
+%%%%% Maximum flow algorithms %%%%%
+
+@article{edmondskarp72theoretical,
+ author = {Jack Edmonds and Richard M. Karp},
+ title = {Theoretical improvements in algorithmic efficiency
+ for network flow problems},
+ journal = {Journal of the ACM},
+ year = 1972,
+ volume = 19,
+ number = 2,
+ pages = {248-264}
+}
+
+@article{goldberg88newapproach,
+ author = {Andrew V. Goldberg and Robert E. Tarjan},
+ title = {A new approach to the maximum flow problem},
+ journal = {Journal of the ACM},
+ year = 1988,
+ volume = 35,
+ number = 4,
+ pages = {921-940}
+}
+
+@article{dinic70algorithm,
+ author = {E. A. Dinic},
+ title = {Algorithm for solution of a problem of maximum flow
+ in a network with power estimation},
+ journal = {Soviet Math. Doklady},
+ year = 1970,
+ volume = 11,
+ pages = {1277-1280}
+}
+
+@article{goldberg08partial,
+ author = {Andrew V. Goldberg},
+ title = {The Partial Augment-Relabel Algorithm for the
+ Maximum Flow Problem},
+ journal = {16th Annual European Symposium on Algorithms},
+ year = 2008,
+ pages = {466-477}
+}
+
+@article{sleator83dynamic,
+ author = {Daniel D. Sleator and Robert E. Tarjan},
+ title = {A data structure for dynamic trees},
+ journal = {Journal of Computer and System Sciences},
+ year = 1983,
+ volume = 26,
+ number = 3,
+ pages = {362-391}
+}
+
+
+%%%%% Minimum mean cycle algorithms %%%%%
+
+@article{karp78characterization,
+ author = {Richard M. Karp},
+ title = {A characterization of the minimum cycle mean in a
+ digraph},
+ journal = {Discrete Math.},
+ year = 1978,
+ volume = 23,
+ pages = {309-311}
+}
+
+@article{dasdan98minmeancycle,
+ author = {Ali Dasdan and Rajesh K. Gupta},
+ title = {Faster Maximum and Minimum Mean Cycle Alogrithms for
+ System Performance Analysis},
+ journal = {IEEE Transactions on Computer-Aided Design of
+ Integrated Circuits and Systems},
+ year = 1998,
+ volume = 17,
+ number = 10,
+ pages = {889-899}
+}
+
+
+%%%%% Minimum cost flow algorithms %%%%%
+
+@article{klein67primal,
+ author = {Morton Klein},
+ title = {A primal method for minimal cost flows with
+ applications to the assignment and transportation
+ problems},
+ journal = {Management Science},
+ year = 1967,
+ volume = 14,
+ pages = {205-220}
+}
+
+@article{goldberg89cyclecanceling,
+ author = {Andrew V. Goldberg and Robert E. Tarjan},
+ title = {Finding minimum-cost circulations by canceling
+ negative cycles},
+ journal = {Journal of the ACM},
+ year = 1989,
+ volume = 36,
+ number = 4,
+ pages = {873-886}
+}
+
+@article{goldberg90approximation,
+ author = {Andrew V. Goldberg and Robert E. Tarjan},
+ title = {Finding Minimum-Cost Circulations by Successive
+ Approximation},
+ journal = {Mathematics of Operations Research},
+ year = 1990,
+ volume = 15,
+ number = 3,
+ pages = {430-466}
+}
+
+@article{goldberg97efficient,
+ author = {Andrew V. Goldberg},
+ title = {An Efficient Implementation of a Scaling
+ Minimum-Cost Flow Algorithm},
+ journal = {Journal of Algorithms},
+ year = 1997,
+ volume = 22,
+ number = 1,
+ pages = {1-29}
+}
+
+@article{bunnagel98efficient,
+ author = {Ursula B{\"u}nnagel and Bernhard Korte and Jens
+ Vygen},
+ title = {Efficient implementation of the {G}oldberg-{T}arjan
+ minimum-cost flow algorithm},
+ journal = {Optimization Methods and Software},
+ year = 1998,
+ volume = 10,
+ pages = {157-174}
+}
+
+@book{dantzig63linearprog,
+ author = {George B. Dantzig},
+ title = {Linear Programming and Extensions},
+ publisher = {Princeton University Press},
+ year = 1963
+}
+
+@mastersthesis{kellyoneill91netsimplex,
+ author = {Damian J. Kelly and Garrett M. O'Neill},
+ title = {The Minimum Cost Flow Problem and The Network
+ Simplex Method},
+ school = {University College},
+ address = {Dublin, Ireland},
+ year = 1991,
+ month = sep,
+}
Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am (revision 868)
+++ lemon/Makefile.am (revision 888)
@@ -58,7 +58,10 @@
lemon/arg_parser.h \
lemon/assert.h \
+ lemon/bellman_ford.h \
lemon/bfs.h \
lemon/bin_heap.h \
+ lemon/binom_heap.h \
lemon/bucket_heap.h \
+ lemon/capacity_scaling.h \
lemon/cbc.h \
lemon/circulation.h \
@@ -67,7 +70,9 @@
lemon/concept_check.h \
lemon/connectivity.h \
+ lemon/core.h \
+ lemon/cost_scaling.h \
lemon/counter.h \
- lemon/core.h \
lemon/cplex.h \
+ lemon/cycle_canceling.h \
lemon/dfs.h \
lemon/dijkstra.h \
@@ -79,4 +84,5 @@
lemon/euler.h \
lemon/fib_heap.h \
+ lemon/fourary_heap.h \
lemon/full_graph.h \
lemon/glpk.h \
@@ -84,5 +90,9 @@
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 \
lemon/hao_orlin.h \
@@ -99,5 +109,7 @@
lemon/nauty_reader.h \
lemon/network_simplex.h \
+ lemon/pairing_heap.h \
lemon/path.h \
+ lemon/planarity.h \
lemon/preflow.h \
lemon/radix_heap.h \
@@ -106,4 +118,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 703)
+++ lemon/adaptors.h (revision 834)
@@ -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 870)
+++ lemon/bellman_ford.h (revision 870)
@@ -0,0 +1,1107 @@
+/* -*- 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_BELLMAN_FORD_H
+#define LEMON_BELLMAN_FORD_H
+
+/// \ingroup shortest_path
+/// \file
+/// \brief Bellman-Ford algorithm.
+
+#include
+#include
+#include
+#include
+#include
+#include
+
+#include
+
+namespace lemon {
+
+ /// \brief Default OperationTraits for the BellmanFord algorithm class.
+ ///
+ /// This operation traits class defines all computational operations
+ /// and constants that are used in the Bellman-Ford algorithm.
+ /// The default implementation is based on the \c numeric_limits class.
+ /// If the numeric type does not have infinity value, then the maximum
+ /// value is used as extremal infinity value.
+ template <
+ typename V,
+ bool has_inf = std::numeric_limits::has_infinity>
+ struct BellmanFordDefaultOperationTraits {
+ /// \e
+ typedef V Value;
+ /// \brief Gives back the zero value of the type.
+ static Value zero() {
+ return static_cast(0);
+ }
+ /// \brief Gives back the positive infinity value of the type.
+ static Value infinity() {
+ return std::numeric_limits::infinity();
+ }
+ /// \brief Gives back the sum of the given two elements.
+ static Value plus(const Value& left, const Value& right) {
+ return left + right;
+ }
+ /// \brief Gives back \c true only if the first value is less than
+ /// the second.
+ static bool less(const Value& left, const Value& right) {
+ return left < right;
+ }
+ };
+
+ template
+ struct BellmanFordDefaultOperationTraits {
+ typedef V Value;
+ static Value zero() {
+ return static_cast(0);
+ }
+ static Value infinity() {
+ return std::numeric_limits::max();
+ }
+ static Value plus(const Value& left, const Value& right) {
+ if (left == infinity() || right == infinity()) return infinity();
+ return left + right;
+ }
+ static bool less(const Value& left, const Value& right) {
+ return left < right;
+ }
+ };
+
+ /// \brief Default traits class of BellmanFord class.
+ ///
+ /// Default traits class of BellmanFord class.
+ /// \param GR The type of the digraph.
+ /// \param LEN The type of the length map.
+ template
+ struct BellmanFordDefaultTraits {
+ /// The type of the digraph the algorithm runs on.
+ typedef GR Digraph;
+
+ /// \brief The type of the map that stores the arc lengths.
+ ///
+ /// The type of the map that stores the arc lengths.
+ /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+ typedef LEN LengthMap;
+
+ /// The type of the arc lengths.
+ typedef typename LEN::Value Value;
+
+ /// \brief Operation traits for Bellman-Ford algorithm.
+ ///
+ /// It defines the used operations and the infinity value for the
+ /// given \c Value type.
+ /// \see BellmanFordDefaultOperationTraits
+ typedef BellmanFordDefaultOperationTraits OperationTraits;
+
+ /// \brief The type of the map that stores the last arcs of the
+ /// shortest paths.
+ ///
+ /// The type of the map that stores the last
+ /// arcs of the shortest paths.
+ /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ typedef typename GR::template NodeMap PredMap;
+
+ /// \brief Instantiates a \c PredMap.
+ ///
+ /// This function instantiates a \ref PredMap.
+ /// \param g is the digraph to which we would like to define the
+ /// \ref PredMap.
+ static PredMap *createPredMap(const GR& g) {
+ return new PredMap(g);
+ }
+
+ /// \brief The type of the map that stores the distances of the nodes.
+ ///
+ /// The type of the map that stores the distances of the nodes.
+ /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ typedef typename GR::template NodeMap DistMap;
+
+ /// \brief Instantiates a \c DistMap.
+ ///
+ /// This function instantiates a \ref DistMap.
+ /// \param g is the digraph to which we would like to define the
+ /// \ref DistMap.
+ static DistMap *createDistMap(const GR& g) {
+ return new DistMap(g);
+ }
+
+ };
+
+ /// \brief %BellmanFord algorithm class.
+ ///
+ /// \ingroup shortest_path
+ /// This class provides an efficient implementation of the Bellman-Ford
+ /// algorithm. The maximum time complexity of the algorithm is
+ /// O(ne).
+ ///
+ /// The Bellman-Ford algorithm solves the single-source shortest path
+ /// problem when the arcs can have negative lengths, but the digraph
+ /// should not contain directed cycles with negative total length.
+ /// If all arc costs are non-negative, consider to use the Dijkstra
+ /// algorithm instead, since it is more efficient.
+ ///
+ /// The arc lengths are passed to the algorithm using a
+ /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
+ /// kind of length. The type of the length values is determined by the
+ /// \ref concepts::ReadMap::Value "Value" type of the length map.
+ ///
+ /// There is also a \ref bellmanFord() "function-type interface" for the
+ /// Bellman-Ford algorithm, which is convenient in the simplier cases and
+ /// it can be used easier.
+ ///
+ /// \tparam GR The type of the digraph the algorithm runs on.
+ /// The default type is \ref ListDigraph.
+ /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
+ /// the lengths of the arcs. The default map type is
+ /// \ref concepts::Digraph::ArcMap "GR::ArcMap".
+#ifdef DOXYGEN
+ template
+#else
+ template ,
+ typename TR=BellmanFordDefaultTraits >
+#endif
+ class BellmanFord {
+ public:
+
+ ///The type of the underlying digraph.
+ typedef typename TR::Digraph Digraph;
+
+ /// \brief The type of the arc lengths.
+ typedef typename TR::LengthMap::Value Value;
+ /// \brief The type of the map that stores the arc lengths.
+ typedef typename TR::LengthMap LengthMap;
+ /// \brief The type of the map that stores the last
+ /// arcs of the shortest paths.
+ typedef typename TR::PredMap PredMap;
+ /// \brief The type of the map that stores the distances of the nodes.
+ typedef typename TR::DistMap DistMap;
+ /// The type of the paths.
+ typedef PredMapPath Path;
+ ///\brief The \ref BellmanFordDefaultOperationTraits
+ /// "operation traits class" of the algorithm.
+ typedef typename TR::OperationTraits OperationTraits;
+
+ ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
+ typedef TR Traits;
+
+ private:
+
+ typedef typename Digraph::Node Node;
+ typedef typename Digraph::NodeIt NodeIt;
+ typedef typename Digraph::Arc Arc;
+ typedef typename Digraph::OutArcIt OutArcIt;
+
+ // Pointer to the underlying digraph.
+ const Digraph *_gr;
+ // Pointer to the length map
+ const LengthMap *_length;
+ // Pointer to the map of predecessors arcs.
+ PredMap *_pred;
+ // Indicates if _pred is locally allocated (true) or not.
+ bool _local_pred;
+ // Pointer to the map of distances.
+ DistMap *_dist;
+ // Indicates if _dist is locally allocated (true) or not.
+ bool _local_dist;
+
+ typedef typename Digraph::template NodeMap MaskMap;
+ MaskMap *_mask;
+
+ std::vector _process;
+
+ // Creates the maps if necessary.
+ void create_maps() {
+ if(!_pred) {
+ _local_pred = true;
+ _pred = Traits::createPredMap(*_gr);
+ }
+ if(!_dist) {
+ _local_dist = true;
+ _dist = Traits::createDistMap(*_gr);
+ }
+ if(!_mask) {
+ _mask = new MaskMap(*_gr);
+ }
+ }
+
+ public :
+
+ typedef BellmanFord Create;
+
+ /// \name Named Template Parameters
+
+ ///@{
+
+ template
+ struct SetPredMapTraits : public Traits {
+ typedef T PredMap;
+ static PredMap *createPredMap(const Digraph&) {
+ LEMON_ASSERT(false, "PredMap is not initialized");
+ return 0; // ignore warnings
+ }
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// \c PredMap type.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting
+ /// \c PredMap type.
+ /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ template
+ struct SetPredMap
+ : public BellmanFord< Digraph, LengthMap, SetPredMapTraits > {
+ typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits > Create;
+ };
+
+ template
+ struct SetDistMapTraits : public Traits {
+ typedef T DistMap;
+ static DistMap *createDistMap(const Digraph&) {
+ LEMON_ASSERT(false, "DistMap is not initialized");
+ return 0; // ignore warnings
+ }
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// \c DistMap type.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting
+ /// \c DistMap type.
+ /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ template
+ struct SetDistMap
+ : public BellmanFord< Digraph, LengthMap, SetDistMapTraits > {
+ typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits > Create;
+ };
+
+ template
+ struct SetOperationTraitsTraits : public Traits {
+ typedef T OperationTraits;
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// \c OperationTraits type.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting
+ /// \c OperationTraits type.
+ /// For more information, see \ref BellmanFordDefaultOperationTraits.
+ template
+ struct SetOperationTraits
+ : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits > {
+ typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits >
+ Create;
+ };
+
+ ///@}
+
+ protected:
+
+ BellmanFord() {}
+
+ public:
+
+ /// \brief Constructor.
+ ///
+ /// Constructor.
+ /// \param g The digraph the algorithm runs on.
+ /// \param length The length map used by the algorithm.
+ BellmanFord(const Digraph& g, const LengthMap& length) :
+ _gr(&g), _length(&length),
+ _pred(0), _local_pred(false),
+ _dist(0), _local_dist(false), _mask(0) {}
+
+ ///Destructor.
+ ~BellmanFord() {
+ if(_local_pred) delete _pred;
+ if(_local_dist) delete _dist;
+ if(_mask) delete _mask;
+ }
+
+ /// \brief Sets the length map.
+ ///
+ /// Sets the length map.
+ /// \return (*this)
+ BellmanFord &lengthMap(const LengthMap &map) {
+ _length = ↦
+ return *this;
+ }
+
+ /// \brief Sets the map that stores the predecessor arcs.
+ ///
+ /// Sets the map that stores the predecessor arcs.
+ /// If you don't use this function before calling \ref run()
+ /// or \ref init(), an instance will be allocated automatically.
+ /// The destructor deallocates this automatically allocated map,
+ /// of course.
+ /// \return (*this)
+ BellmanFord &predMap(PredMap &map) {
+ if(_local_pred) {
+ delete _pred;
+ _local_pred=false;
+ }
+ _pred = ↦
+ return *this;
+ }
+
+ /// \brief Sets the map that stores the distances of the nodes.
+ ///
+ /// Sets the map that stores the distances of the nodes calculated
+ /// by the algorithm.
+ /// If you don't use this function before calling \ref run()
+ /// or \ref init(), an instance will be allocated automatically.
+ /// The destructor deallocates this automatically allocated map,
+ /// of course.
+ /// \return (*this)
+ BellmanFord &distMap(DistMap &map) {
+ if(_local_dist) {
+ delete _dist;
+ _local_dist=false;
+ }
+ _dist = ↦
+ return *this;
+ }
+
+ /// \name Execution Control
+ /// The simplest way to execute the Bellman-Ford algorithm is to use
+ /// one of the member functions called \ref run().\n
+ /// If you need better control on the execution, you have to call
+ /// \ref init() first, then you can add several source nodes
+ /// with \ref addSource(). Finally the actual path computation can be
+ /// performed with \ref start(), \ref checkedStart() or
+ /// \ref limitedStart().
+
+ ///@{
+
+ /// \brief Initializes the internal data structures.
+ ///
+ /// Initializes the internal data structures. The optional parameter
+ /// is the initial distance of each node.
+ void init(const Value value = OperationTraits::infinity()) {
+ create_maps();
+ for (NodeIt it(*_gr); it != INVALID; ++it) {
+ _pred->set(it, INVALID);
+ _dist->set(it, value);
+ }
+ _process.clear();
+ if (OperationTraits::less(value, OperationTraits::infinity())) {
+ for (NodeIt it(*_gr); it != INVALID; ++it) {
+ _process.push_back(it);
+ _mask->set(it, true);
+ }
+ } else {
+ for (NodeIt it(*_gr); it != INVALID; ++it) {
+ _mask->set(it, false);
+ }
+ }
+ }
+
+ /// \brief Adds a new source node.
+ ///
+ /// This function adds a new source node. The optional second parameter
+ /// is the initial distance of the node.
+ void addSource(Node source, Value dst = OperationTraits::zero()) {
+ _dist->set(source, dst);
+ if (!(*_mask)[source]) {
+ _process.push_back(source);
+ _mask->set(source, true);
+ }
+ }
+
+ /// \brief Executes one round from the Bellman-Ford algorithm.
+ ///
+ /// If the algoritm calculated the distances in the previous round
+ /// exactly for the paths of at most \c k arcs, then this function
+ /// will calculate the distances exactly for the paths of at most
+ /// k+1 arcs. Performing \c k iterations using this function
+ /// calculates the shortest path distances exactly for the paths
+ /// consisting of at most \c k arcs.
+ ///
+ /// \warning The paths with limited arc number cannot be retrieved
+ /// easily with \ref path() or \ref predArc() functions. If you also
+ /// need the shortest paths and not only the distances, you should
+ /// store the \ref predMap() "predecessor map" after each iteration
+ /// and build the path manually.
+ ///
+ /// \return \c true when the algorithm have not found more shorter
+ /// paths.
+ ///
+ /// \see ActiveIt
+ bool processNextRound() {
+ for (int i = 0; i < int(_process.size()); ++i) {
+ _mask->set(_process[i], false);
+ }
+ std::vector nextProcess;
+ std::vector values(_process.size());
+ for (int i = 0; i < int(_process.size()); ++i) {
+ values[i] = (*_dist)[_process[i]];
+ }
+ for (int i = 0; i < int(_process.size()); ++i) {
+ for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
+ Node target = _gr->target(it);
+ Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
+ if (OperationTraits::less(relaxed, (*_dist)[target])) {
+ _pred->set(target, it);
+ _dist->set(target, relaxed);
+ if (!(*_mask)[target]) {
+ _mask->set(target, true);
+ nextProcess.push_back(target);
+ }
+ }
+ }
+ }
+ _process.swap(nextProcess);
+ return _process.empty();
+ }
+
+ /// \brief Executes one weak round from the Bellman-Ford algorithm.
+ ///
+ /// If the algorithm calculated the distances in the previous round
+ /// at least for the paths of at most \c k arcs, then this function
+ /// will calculate the distances at least for the paths of at most
+ /// k+1 arcs.
+ /// This function does not make it possible to calculate the shortest
+ /// path distances exactly for paths consisting of at most \c k arcs,
+ /// this is why it is called weak round.
+ ///
+ /// \return \c true when the algorithm have not found more shorter
+ /// paths.
+ ///
+ /// \see ActiveIt
+ bool processNextWeakRound() {
+ for (int i = 0; i < int(_process.size()); ++i) {
+ _mask->set(_process[i], false);
+ }
+ std::vector nextProcess;
+ for (int i = 0; i < int(_process.size()); ++i) {
+ for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
+ Node target = _gr->target(it);
+ Value relaxed =
+ OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
+ if (OperationTraits::less(relaxed, (*_dist)[target])) {
+ _pred->set(target, it);
+ _dist->set(target, relaxed);
+ if (!(*_mask)[target]) {
+ _mask->set(target, true);
+ nextProcess.push_back(target);
+ }
+ }
+ }
+ }
+ _process.swap(nextProcess);
+ return _process.empty();
+ }
+
+ /// \brief Executes the algorithm.
+ ///
+ /// Executes the algorithm.
+ ///
+ /// This method runs the Bellman-Ford algorithm from the root node(s)
+ /// in order to compute the shortest path to each node.
+ ///
+ /// The algorithm computes
+ /// - the shortest path tree (forest),
+ /// - the distance of each node from the root(s).
+ ///
+ /// \pre init() must be called and at least one root node should be
+ /// added with addSource() before using this function.
+ void start() {
+ int num = countNodes(*_gr) - 1;
+ for (int i = 0; i < num; ++i) {
+ if (processNextWeakRound()) break;
+ }
+ }
+
+ /// \brief Executes the algorithm and checks the negative cycles.
+ ///
+ /// Executes the algorithm and checks the negative cycles.
+ ///
+ /// This method runs the Bellman-Ford algorithm from the root node(s)
+ /// in order to compute the shortest path to each node and also checks
+ /// if the digraph contains cycles with negative total length.
+ ///
+ /// The algorithm computes
+ /// - the shortest path tree (forest),
+ /// - the distance of each node from the root(s).
+ ///
+ /// \return \c false if there is a negative cycle in the digraph.
+ ///
+ /// \pre init() must be called and at least one root node should be
+ /// added with addSource() before using this function.
+ bool checkedStart() {
+ int num = countNodes(*_gr);
+ for (int i = 0; i < num; ++i) {
+ if (processNextWeakRound()) return true;
+ }
+ return _process.empty();
+ }
+
+ /// \brief Executes the algorithm with arc number limit.
+ ///
+ /// Executes the algorithm with arc number limit.
+ ///
+ /// This method runs the Bellman-Ford algorithm from the root node(s)
+ /// in order to compute the shortest path distance for each node
+ /// using only the paths consisting of at most \c num arcs.
+ ///
+ /// The algorithm computes
+ /// - the limited distance of each node from the root(s),
+ /// - the predecessor arc for each node.
+ ///
+ /// \warning The paths with limited arc number cannot be retrieved
+ /// easily with \ref path() or \ref predArc() functions. If you also
+ /// need the shortest paths and not only the distances, you should
+ /// store the \ref predMap() "predecessor map" after each iteration
+ /// and build the path manually.
+ ///
+ /// \pre init() must be called and at least one root node should be
+ /// added with addSource() before using this function.
+ void limitedStart(int num) {
+ for (int i = 0; i < num; ++i) {
+ if (processNextRound()) break;
+ }
+ }
+
+ /// \brief Runs the algorithm from the given root node.
+ ///
+ /// This method runs the Bellman-Ford algorithm from the given root
+ /// node \c s in order to compute the shortest path to each node.
+ ///
+ /// The algorithm computes
+ /// - the shortest path tree (forest),
+ /// - the distance of each node from the root(s).
+ ///
+ /// \note bf.run(s) is just a shortcut of the following code.
+ /// \code
+ /// bf.init();
+ /// bf.addSource(s);
+ /// bf.start();
+ /// \endcode
+ void run(Node s) {
+ init();
+ addSource(s);
+ start();
+ }
+
+ /// \brief Runs the algorithm from the given root node with arc
+ /// number limit.
+ ///
+ /// This method runs the Bellman-Ford algorithm from the given root
+ /// node \c s in order to compute the shortest path distance for each
+ /// node using only the paths consisting of at most \c num arcs.
+ ///
+ /// The algorithm computes
+ /// - the limited distance of each node from the root(s),
+ /// - the predecessor arc for each node.
+ ///
+ /// \warning The paths with limited arc number cannot be retrieved
+ /// easily with \ref path() or \ref predArc() functions. If you also
+ /// need the shortest paths and not only the distances, you should
+ /// store the \ref predMap() "predecessor map" after each iteration
+ /// and build the path manually.
+ ///
+ /// \note bf.run(s, num) is just a shortcut of the following code.
+ /// \code
+ /// bf.init();
+ /// bf.addSource(s);
+ /// bf.limitedStart(num);
+ /// \endcode
+ void run(Node s, int num) {
+ init();
+ addSource(s);
+ limitedStart(num);
+ }
+
+ ///@}
+
+ /// \brief LEMON iterator for getting the active nodes.
+ ///
+ /// This class provides a common style LEMON iterator that traverses
+ /// the active nodes of the Bellman-Ford algorithm after the last
+ /// phase. These nodes should be checked in the next phase to
+ /// find augmenting arcs outgoing from them.
+ class ActiveIt {
+ public:
+
+ /// \brief Constructor.
+ ///
+ /// Constructor for getting the active nodes of the given BellmanFord
+ /// instance.
+ ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
+ {
+ _index = _algorithm->_process.size() - 1;
+ }
+
+ /// \brief Invalid constructor.
+ ///
+ /// Invalid constructor.
+ ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
+
+ /// \brief Conversion to \c Node.
+ ///
+ /// Conversion to \c Node.
+ operator Node() const {
+ return _index >= 0 ? _algorithm->_process[_index] : INVALID;
+ }
+
+ /// \brief Increment operator.
+ ///
+ /// Increment operator.
+ ActiveIt& operator++() {
+ --_index;
+ return *this;
+ }
+
+ bool operator==(const ActiveIt& it) const {
+ return static_cast(*this) == static_cast(it);
+ }
+ bool operator!=(const ActiveIt& it) const {
+ return static_cast(*this) != static_cast(it);
+ }
+ bool operator<(const ActiveIt& it) const {
+ return static_cast(*this) < static_cast(it);
+ }
+
+ private:
+ const BellmanFord* _algorithm;
+ int _index;
+ };
+
+ /// \name Query Functions
+ /// The result of the Bellman-Ford algorithm can be obtained using these
+ /// functions.\n
+ /// Either \ref run() or \ref init() should be called before using them.
+
+ ///@{
+
+ /// \brief The shortest path to the given node.
+ ///
+ /// Gives back the shortest path to the given node from the root(s).
+ ///
+ /// \warning \c t should be reached from the root(s).
+ ///
+ /// \pre Either \ref run() or \ref init() must be called before
+ /// using this function.
+ Path path(Node t) const
+ {
+ return Path(*_gr, *_pred, t);
+ }
+
+ /// \brief The distance of the given node from the root(s).
+ ///
+ /// Returns the distance of the given node from the root(s).
+ ///
+ /// \warning If node \c v is not reached from the root(s), then
+ /// the return value of this function is undefined.
+ ///
+ /// \pre Either \ref run() or \ref init() must be called before
+ /// using this function.
+ Value dist(Node v) const { return (*_dist)[v]; }
+
+ /// \brief Returns the 'previous arc' of the shortest path tree for
+ /// the given node.
+ ///
+ /// This function returns the 'previous arc' of the shortest path
+ /// tree for node \c v, i.e. it returns the last arc of a
+ /// shortest path from a root to \c v. It is \c INVALID if \c v
+ /// is not reached from the root(s) or if \c v is a root.
+ ///
+ /// The shortest path tree used here is equal to the shortest path
+ /// tree used in \ref predNode() and \ref predMap().
+ ///
+ /// \pre Either \ref run() or \ref init() must be called before
+ /// using this function.
+ Arc predArc(Node v) const { return (*_pred)[v]; }
+
+ /// \brief Returns the 'previous node' of the shortest path tree for
+ /// the given node.
+ ///
+ /// This function returns the 'previous node' of the shortest path
+ /// tree for node \c v, i.e. it returns the last but one node of
+ /// a shortest path from a root to \c v. It is \c INVALID if \c v
+ /// is not reached from the root(s) or if \c v is a root.
+ ///
+ /// The shortest path tree used here is equal to the shortest path
+ /// tree used in \ref predArc() and \ref predMap().
+ ///
+ /// \pre Either \ref run() or \ref init() must be called before
+ /// using this function.
+ Node predNode(Node v) const {
+ return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
+ }
+
+ /// \brief Returns a const reference to the node map that stores the
+ /// distances of the nodes.
+ ///
+ /// Returns a const reference to the node map that stores the distances
+ /// of the nodes calculated by the algorithm.
+ ///
+ /// \pre Either \ref run() or \ref init() must be called before
+ /// using this function.
+ const DistMap &distMap() const { return *_dist;}
+
+ /// \brief Returns a const reference to the node map that stores the
+ /// predecessor arcs.
+ ///
+ /// Returns a const reference to the node map that stores the predecessor
+ /// arcs, which form the shortest path tree (forest).
+ ///
+ /// \pre Either \ref run() or \ref init() must be called before
+ /// using this function.
+ const PredMap &predMap() const { return *_pred; }
+
+ /// \brief Checks if a node is reached from the root(s).
+ ///
+ /// Returns \c true if \c v is reached from the root(s).
+ ///
+ /// \pre Either \ref run() or \ref init() must be called before
+ /// using this function.
+ bool reached(Node v) const {
+ return (*_dist)[v] != OperationTraits::infinity();
+ }
+
+ /// \brief Gives back a negative cycle.
+ ///
+ /// This function gives back a directed cycle with negative total
+ /// length if the algorithm has already found one.
+ /// Otherwise it gives back an empty path.
+ lemon::Path negativeCycle() const {
+ typename Digraph::template NodeMap state(*_gr, -1);
+ lemon::Path cycle;
+ for (int i = 0; i < int(_process.size()); ++i) {
+ if (state[_process[i]] != -1) continue;
+ for (Node v = _process[i]; (*_pred)[v] != INVALID;
+ v = _gr->source((*_pred)[v])) {
+ if (state[v] == i) {
+ cycle.addFront((*_pred)[v]);
+ for (Node u = _gr->source((*_pred)[v]); u != v;
+ u = _gr->source((*_pred)[u])) {
+ cycle.addFront((*_pred)[u]);
+ }
+ return cycle;
+ }
+ else if (state[v] >= 0) {
+ break;
+ }
+ state[v] = i;
+ }
+ }
+ return cycle;
+ }
+
+ ///@}
+ };
+
+ /// \brief Default traits class of bellmanFord() function.
+ ///
+ /// Default traits class of bellmanFord() function.
+ /// \tparam GR The type of the digraph.
+ /// \tparam LEN The type of the length map.
+ template
+ struct BellmanFordWizardDefaultTraits {
+ /// The type of the digraph the algorithm runs on.
+ typedef GR Digraph;
+
+ /// \brief The type of the map that stores the arc lengths.
+ ///
+ /// The type of the map that stores the arc lengths.
+ /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
+ typedef LEN LengthMap;
+
+ /// The type of the arc lengths.
+ typedef typename LEN::Value Value;
+
+ /// \brief Operation traits for Bellman-Ford algorithm.
+ ///
+ /// It defines the used operations and the infinity value for the
+ /// given \c Value type.
+ /// \see BellmanFordDefaultOperationTraits
+ typedef BellmanFordDefaultOperationTraits OperationTraits;
+
+ /// \brief The type of the map that stores the last
+ /// arcs of the shortest paths.
+ ///
+ /// The type of the map that stores the last arcs of the shortest paths.
+ /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ typedef typename GR::template NodeMap PredMap;
+
+ /// \brief Instantiates a \c PredMap.
+ ///
+ /// This function instantiates a \ref PredMap.
+ /// \param g is the digraph to which we would like to define the
+ /// \ref PredMap.
+ static PredMap *createPredMap(const GR &g) {
+ return new PredMap(g);
+ }
+
+ /// \brief The type of the map that stores the distances of the nodes.
+ ///
+ /// The type of the map that stores the distances of the nodes.
+ /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ typedef typename GR::template NodeMap DistMap;
+
+ /// \brief Instantiates a \c DistMap.
+ ///
+ /// This function instantiates a \ref DistMap.
+ /// \param g is the digraph to which we would like to define the
+ /// \ref DistMap.
+ static DistMap *createDistMap(const GR &g) {
+ return new DistMap(g);
+ }
+
+ ///The type of the shortest paths.
+
+ ///The type of the shortest paths.
+ ///It must meet the \ref concepts::Path "Path" concept.
+ typedef lemon::Path Path;
+ };
+
+ /// \brief Default traits class used by BellmanFordWizard.
+ ///
+ /// Default traits class used by BellmanFordWizard.
+ /// \tparam GR The type of the digraph.
+ /// \tparam LEN The type of the length map.
+ template
+ class BellmanFordWizardBase
+ : public BellmanFordWizardDefaultTraits {
+
+ typedef BellmanFordWizardDefaultTraits Base;
+ protected:
+ // Type of the nodes in the digraph.
+ typedef typename Base::Digraph::Node Node;
+
+ // Pointer to the underlying digraph.
+ void *_graph;
+ // Pointer to the length map
+ void *_length;
+ // Pointer to the map of predecessors arcs.
+ void *_pred;
+ // Pointer to the map of distances.
+ void *_dist;
+ //Pointer to the shortest path to the target node.
+ void *_path;
+ //Pointer to the distance of the target node.
+ void *_di;
+
+ public:
+ /// Constructor.
+
+ /// This constructor does not require parameters, it initiates
+ /// all of the attributes to default values \c 0.
+ BellmanFordWizardBase() :
+ _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
+
+ /// Constructor.
+
+ /// This constructor requires two parameters,
+ /// others are initiated to \c 0.
+ /// \param gr The digraph the algorithm runs on.
+ /// \param len The length map.
+ BellmanFordWizardBase(const GR& gr,
+ const LEN& len) :
+ _graph(reinterpret_cast(const_cast(&gr))),
+ _length(reinterpret_cast(const_cast(&len))),
+ _pred(0), _dist(0), _path(0), _di(0) {}
+
+ };
+
+ /// \brief Auxiliary class for the function-type interface of the
+ /// \ref BellmanFord "Bellman-Ford" algorithm.
+ ///
+ /// This auxiliary class is created to implement the
+ /// \ref bellmanFord() "function-type interface" of the
+ /// \ref BellmanFord "Bellman-Ford" algorithm.
+ /// It does not have own \ref run() method, it uses the
+ /// functions and features of the plain \ref BellmanFord.
+ ///
+ /// This class should only be used through the \ref bellmanFord()
+ /// function, which makes it easier to use the algorithm.
+ template
+ class BellmanFordWizard : public TR {
+ typedef TR Base;
+
+ typedef typename TR::Digraph Digraph;
+
+ typedef typename Digraph::Node Node;
+ typedef typename Digraph::NodeIt NodeIt;
+ typedef typename Digraph::Arc Arc;
+ typedef typename Digraph::OutArcIt ArcIt;
+
+ typedef typename TR::LengthMap LengthMap;
+ typedef typename LengthMap::Value Value;
+ typedef typename TR::PredMap PredMap;
+ typedef typename TR::DistMap DistMap;
+ typedef typename TR::Path Path;
+
+ public:
+ /// Constructor.
+ BellmanFordWizard() : TR() {}
+
+ /// \brief Constructor that requires parameters.
+ ///
+ /// Constructor that requires parameters.
+ /// These parameters will be the default values for the traits class.
+ /// \param gr The digraph the algorithm runs on.
+ /// \param len The length map.
+ BellmanFordWizard(const Digraph& gr, const LengthMap& len)
+ : TR(gr, len) {}
+
+ /// \brief Copy constructor
+ BellmanFordWizard(const TR &b) : TR(b) {}
+
+ ~BellmanFordWizard() {}
+
+ /// \brief Runs the Bellman-Ford algorithm from the given source node.
+ ///
+ /// This method runs the Bellman-Ford algorithm from the given source
+ /// node in order to compute the shortest path to each node.
+ void run(Node s) {
+ BellmanFord
+ bf(*reinterpret_cast(Base::_graph),
+ *reinterpret_cast(Base::_length));
+ if (Base::_pred) bf.predMap(*reinterpret_cast(Base::_pred));
+ if (Base::_dist) bf.distMap(*reinterpret_cast(Base::_dist));
+ bf.run(s);
+ }
+
+ /// \brief Runs the Bellman-Ford algorithm to find the shortest path
+ /// between \c s and \c t.
+ ///
+ /// This method runs the Bellman-Ford algorithm from node \c s
+ /// in order to compute the shortest path to node \c t.
+ /// Actually, it computes the shortest path to each node, but using
+ /// this function you can retrieve the distance and the shortest path
+ /// for a single target node easier.
+ ///
+ /// \return \c true if \c t is reachable form \c s.
+ bool run(Node s, Node t) {
+ BellmanFord
+ bf(*reinterpret_cast(Base::_graph),
+ *reinterpret_cast(Base::_length));
+ if (Base::_pred) bf.predMap(*reinterpret_cast(Base::_pred));
+ if (Base::_dist) bf.distMap(*reinterpret_cast(Base::_dist));
+ bf.run(s);
+ if (Base::_path) *reinterpret_cast(Base::_path) = bf.path(t);
+ if (Base::_di) *reinterpret_cast(Base::_di) = bf.dist(t);
+ return bf.reached(t);
+ }
+
+ template
+ struct SetPredMapBase : public Base {
+ typedef T PredMap;
+ static PredMap *createPredMap(const Digraph &) { return 0; };
+ SetPredMapBase(const TR &b) : TR(b) {}
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// the predecessor map.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting
+ /// the map that stores the predecessor arcs of the nodes.
+ template
+ BellmanFordWizard > predMap(const T &t) {
+ Base::_pred=reinterpret_cast(const_cast(&t));
+ return BellmanFordWizard >(*this);
+ }
+
+ template
+ struct SetDistMapBase : public Base {
+ typedef T DistMap;
+ static DistMap *createDistMap(const Digraph &) { return 0; };
+ SetDistMapBase(const TR &b) : TR(b) {}
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// the distance map.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting
+ /// the map that stores the distances of the nodes calculated
+ /// by the algorithm.
+ template
+ BellmanFordWizard > distMap(const T &t) {
+ Base::_dist=reinterpret_cast(const_cast(&t));
+ return BellmanFordWizard >(*this);
+ }
+
+ template
+ struct SetPathBase : public Base {
+ typedef T Path;
+ SetPathBase(const TR &b) : TR(b) {}
+ };
+
+ /// \brief \ref named-func-param "Named parameter" for getting
+ /// the shortest path to the target node.
+ ///
+ /// \ref named-func-param "Named parameter" for getting
+ /// the shortest path to the target node.
+ template
+ BellmanFordWizard > path(const T &t)
+ {
+ Base::_path=reinterpret_cast(const_cast(&t));
+ return BellmanFordWizard >(*this);
+ }
+
+ /// \brief \ref named-func-param "Named parameter" for getting
+ /// the distance of the target node.
+ ///
+ /// \ref named-func-param "Named parameter" for getting
+ /// the distance of the target node.
+ BellmanFordWizard dist(const Value &d)
+ {
+ Base::_di=reinterpret_cast(const_cast(&d));
+ return *this;
+ }
+
+ };
+
+ /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
+ /// algorithm.
+ ///
+ /// \ingroup shortest_path
+ /// Function type interface for the \ref BellmanFord "Bellman-Ford"
+ /// algorithm.
+ ///
+ /// This function also has several \ref named-templ-func-param
+ /// "named parameters", they are declared as the members of class
+ /// \ref BellmanFordWizard.
+ /// The following examples show how to use these parameters.
+ /// \code
+ /// // Compute shortest path from node s to each node
+ /// bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
+ ///
+ /// // Compute shortest path from s to t
+ /// bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
+ /// \endcode
+ /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
+ /// to the end of the parameter list.
+ /// \sa BellmanFordWizard
+ /// \sa BellmanFord
+ template
+ BellmanFordWizard >
+ bellmanFord(const GR& digraph,
+ const LEN& length)
+ {
+ return BellmanFordWizard >(digraph, length);
+ }
+
+} //END OF NAMESPACE LEMON
+
+#endif
+
Index: lemon/bfs.h
===================================================================
--- lemon/bfs.h (revision 525)
+++ lemon/bfs.h (revision 835)
@@ -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/bin_heap.h
===================================================================
--- lemon/bin_heap.h (revision 730)
+++ lemon/bin_heap.h (revision 758)
@@ -20,7 +20,7 @@
#define LEMON_BIN_HEAP_H
-///\ingroup auxdat
+///\ingroup heaps
///\file
-///\brief Binary Heap implementation.
+///\brief Binary heap implementation.
#include
@@ -30,43 +30,39 @@
namespace lemon {
- ///\ingroup auxdat
+ /// \ingroup heaps
///
- ///\brief A Binary Heap implementation.
+ /// \brief Binary heap data structure.
///
- ///This class implements the \e binary \e heap data structure.
+ /// This class implements the \e binary \e heap data structure.
+ /// It fully conforms to the \ref concepts::Heap "heap concept".
///
- ///A \e heap is a data structure for storing items with specified values
- ///called \e priorities in such a way that finding the item with minimum
- ///priority is efficient. \c CMP specifies the ordering of the priorities.
- ///In a heap one can change the priority of an item, add or erase an
- ///item, etc.
- ///
- ///\tparam PR Type of the priority of the items.
- ///\tparam IM A read and writable item map with int values, used internally
- ///to handle the cross references.
- ///\tparam CMP A functor class for the ordering of the priorities.
- ///The default is \c std::less.
- ///
- ///\sa FibHeap
- ///\sa Dijkstra
+ /// \tparam PR Type of the priorities of the items.
+ /// \tparam IM A read-writable item map with \c int values, used
+ /// internally to handle the cross references.
+ /// \tparam CMP A functor class for comparing the priorities.
+ /// The default is \c std::less.
+#ifdef DOXYGEN
+ template
+#else
template >
+#endif
class BinHeap {
-
public:
- ///\e
+
+ /// Type of the item-int map.
typedef IM ItemIntMap;
- ///\e
+ /// Type of the priorities.
typedef PR Prio;
- ///\e
+ /// Type of the items stored in the heap.
typedef typename ItemIntMap::Key Item;
- ///\e
+ /// Type of the item-priority pairs.
typedef std::pair- Pair;
- ///\e
+ /// Functor type for comparing the priorities.
typedef CMP Compare;
- /// \brief Type to represent the items states.
- ///
- /// Each Item element have a state associated to it. It may be "in heap",
- /// "pre heap" or "post heap". The latter two are indifferent from the
+ /// \brief Type to represent the states of the items.
+ ///
+ /// Each item has a state associated to it. It can be "in heap",
+ /// "pre-heap" or "post-heap". The latter two are indifferent from the
/// heap's point of view, but may be useful to the user.
///
@@ -85,40 +81,41 @@
public:
- /// \brief The constructor.
- ///
- /// The constructor.
- /// \param map should be given to the constructor, since it is used
- /// internally to handle the cross references. The value of the map
- /// must be \c PRE_HEAP (-1) for every item.
+
+ /// \brief Constructor.
+ ///
+ /// Constructor.
+ /// \param map A map that assigns \c int values to the items.
+ /// It is used internally to handle the cross references.
+ /// The assigned value must be \c PRE_HEAP (-1) for each item.
explicit BinHeap(ItemIntMap &map) : _iim(map) {}
- /// \brief The constructor.
- ///
- /// The constructor.
- /// \param map should be given to the constructor, since it is used
- /// internally to handle the cross references. The value of the map
- /// should be PRE_HEAP (-1) for each element.
- ///
- /// \param comp The comparator function object.
+ /// \brief Constructor.
+ ///
+ /// Constructor.
+ /// \param map A map that assigns \c int values to the items.
+ /// It is used internally to handle the cross references.
+ /// The assigned value must be \c PRE_HEAP (-1) for each item.
+ /// \param comp The function object used for comparing the priorities.
BinHeap(ItemIntMap &map, const Compare &comp)
: _iim(map), _comp(comp) {}
- /// The number of items stored in the heap.
- ///
- /// \brief Returns the number of items stored in the heap.
+ /// \brief The number of items stored in the heap.
+ ///
+ /// This function returns the number of items stored in the heap.
int size() const { return _data.size(); }
- /// \brief Checks if the heap stores no items.
- ///
- /// Returns \c true if and only if the heap stores no items.
+ /// \brief Check if the heap is empty.
+ ///
+ /// This function returns \c true if the heap is empty.
bool empty() const { return _data.empty(); }
- /// \brief Make empty this heap.
- ///
- /// Make empty this heap. It does not change the cross reference map.
- /// If you want to reuse what is not surely empty you should first clear
- /// the heap and after that you should set the cross reference map for
- /// each item to \c PRE_HEAP.
+ /// \brief Make the heap empty.
+ ///
+ /// This functon makes the heap empty.
+ /// It does not change the cross reference map. If you want to reuse
+ /// a heap that is not surely empty, you should first clear it and
+ /// then you should set the cross reference map to \c PRE_HEAP
+ /// for each item.
void clear() {
_data.clear();
@@ -128,10 +125,10 @@
static int parent(int i) { return (i-1)/2; }
- static int second_child(int i) { return 2*i+2; }
+ static int secondChild(int i) { return 2*i+2; }
bool less(const Pair &p1, const Pair &p2) const {
return _comp(p1.second, p2.second);
}
- int bubble_up(int hole, Pair p) {
+ int bubbleUp(int hole, Pair p) {
int par = parent(hole);
while( hole>0 && less(p,_data[par]) ) {
@@ -144,6 +141,6 @@
}
- int bubble_down(int hole, Pair p, int length) {
- int child = second_child(hole);
+ int bubbleDown(int hole, Pair p, int length) {
+ int child = secondChild(hole);
while(child < length) {
if( less(_data[child-1], _data[child]) ) {
@@ -154,5 +151,5 @@
move(_data[child], hole);
hole = child;
- child = second_child(hole);
+ child = secondChild(hole);
}
child--;
@@ -172,42 +169,45 @@
public:
+
/// \brief Insert a pair of item and priority into the heap.
///
- /// Adds \c p.first to the heap with priority \c p.second.
+ /// This function inserts \c p.first to the heap with priority
+ /// \c p.second.
/// \param p The pair to insert.
+ /// \pre \c p.first must not be stored in the heap.
void push(const Pair &p) {
int n = _data.size();
_data.resize(n+1);
- bubble_up(n, p);
- }
-
- /// \brief Insert an item into the heap with the given heap.
- ///
- /// Adds \c i to the heap with priority \c p.
+ bubbleUp(n, p);
+ }
+
+ /// \brief Insert an item into the heap with the given priority.
+ ///
+ /// This function inserts the given item into the heap with the
+ /// given priority.
/// \param i The item to insert.
/// \param p The priority of the item.
+ /// \pre \e i must not be stored in the heap.
void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
- /// \brief Returns the item with minimum priority relative to \c Compare.
- ///
- /// This method returns the item with minimum priority relative to \c
- /// Compare.
- /// \pre The heap must be nonempty.
+ /// \brief Return the item having minimum priority.
+ ///
+ /// This function returns the item having minimum priority.
+ /// \pre The heap must be non-empty.
Item top() const {
return _data[0].first;
}
- /// \brief Returns the minimum priority relative to \c Compare.
- ///
- /// It returns the minimum priority relative to \c Compare.
- /// \pre The heap must be nonempty.
+ /// \brief The minimum priority.
+ ///
+ /// This function returns the minimum priority.
+ /// \pre The heap must be non-empty.
Prio prio() const {
return _data[0].second;
}
- /// \brief Deletes the item with minimum priority relative to \c Compare.
- ///
- /// This method deletes the item with minimum priority relative to \c
- /// Compare from the heap.
+ /// \brief Remove the item having minimum priority.
+ ///
+ /// This function removes the item having minimum priority.
/// \pre The heap must be non-empty.
void pop() {
@@ -215,14 +215,15 @@
_iim.set(_data[0].first, POST_HEAP);
if (n > 0) {
- bubble_down(0, _data[n], n);
+ bubbleDown(0, _data[n], n);
}
_data.pop_back();
}
- /// \brief Deletes \c i from the heap.
- ///
- /// This method deletes item \c i from the heap.
- /// \param i The item to erase.
- /// \pre The item should be in the heap.
+ /// \brief Remove the given item from the heap.
+ ///
+ /// This function removes the given item from the heap if it is
+ /// already stored.
+ /// \param i The item to delete.
+ /// \pre \e i must be in the heap.
void erase(const Item &i) {
int h = _iim[i];
@@ -230,6 +231,6 @@
_iim.set(_data[h].first, POST_HEAP);
if( h < n ) {
- if ( bubble_up(h, _data[n]) == h) {
- bubble_down(h, _data[n], n);
+ if ( bubbleUp(h, _data[n]) == h) {
+ bubbleDown(h, _data[n], n);
}
}
@@ -237,10 +238,9 @@
}
-
- /// \brief Returns the priority of \c i.
- ///
- /// This function returns the priority of item \c i.
- /// \param i The item.
- /// \pre \c i must be in the heap.
+ /// \brief The priority of the given item.
+ ///
+ /// This function returns the priority of the given item.
+ /// \param i The item.
+ /// \pre \e i must be in the heap.
Prio operator[](const Item &i) const {
int idx = _iim[i];
@@ -248,9 +248,10 @@
}
- /// \brief \c i gets to the heap with priority \c p independently
- /// if \c i was already there.
- ///
- /// This method calls \ref push(\c i, \c p) if \c i is not stored
- /// in the heap and sets the priority of \c i to \c p otherwise.
+ /// \brief Set the priority of an item or insert it, if it is
+ /// not stored in the heap.
+ ///
+ /// This method sets the priority of the given item if it is
+ /// already stored in the heap. Otherwise it inserts the given
+ /// item into the heap with the given priority.
/// \param i The item.
/// \param p The priority.
@@ -261,42 +262,40 @@
}
else if( _comp(p, _data[idx].second) ) {
- bubble_up(idx, Pair(i,p));
+ bubbleUp(idx, Pair(i,p));
}
else {
- bubble_down(idx, Pair(i,p), _data.size());
- }
- }
-
- /// \brief Decreases the priority of \c i to \c p.
- ///
- /// This method decreases the priority of item \c i to \c p.
+ bubbleDown(idx, Pair(i,p), _data.size());
+ }
+ }
+
+ /// \brief Decrease the priority of an item to the given value.
+ ///
+ /// This function decreases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
- /// \pre \c i must be stored in the heap with priority at least \c
- /// p relative to \c Compare.
+ /// \pre \e i must be stored in the heap with priority at least \e p.
void decrease(const Item &i, const Prio &p) {
int idx = _iim[i];
- bubble_up(idx, Pair(i,p));
- }
-
- /// \brief Increases the priority of \c i to \c p.
- ///
- /// This method sets the priority of item \c i to \c p.
+ bubbleUp(idx, Pair(i,p));
+ }
+
+ /// \brief Increase the priority of an item to the given value.
+ ///
+ /// This function increases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
- /// \pre \c i must be stored in the heap with priority at most \c
- /// p relative to \c Compare.
+ /// \pre \e i must be stored in the heap with priority at most \e p.
void increase(const Item &i, const Prio &p) {
int idx = _iim[i];
- bubble_down(idx, Pair(i,p), _data.size());
- }
-
- /// \brief Returns if \c item is in, has already been in, or has
- /// never been in the heap.
- ///
- /// This method returns PRE_HEAP if \c item has never been in the
- /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
- /// otherwise. In the latter case it is possible that \c item will
- /// get back to the heap again.
+ bubbleDown(idx, Pair(i,p), _data.size());
+ }
+
+ /// \brief Return the state of an item.
+ ///
+ /// This method returns \c PRE_HEAP if the given item has never
+ /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
+ /// and \c POST_HEAP otherwise.
+ /// In the latter case it is possible that the item will get back
+ /// to the heap again.
/// \param i The item.
State state(const Item &i) const {
@@ -307,9 +306,9 @@
}
- /// \brief Sets the state of the \c item in the heap.
- ///
- /// Sets the state of the \c item in the heap. It can be used to
- /// manually clear the heap when it is important to achive the
- /// better time complexity.
+ /// \brief Set the state of an item in the heap.
+ ///
+ /// This function sets the state of the given item in the heap.
+ /// It can be used to manually clear the heap when it is important
+ /// to achive better time complexity.
/// \param i The item.
/// \param st The state. It should not be \c IN_HEAP.
@@ -328,10 +327,11 @@
}
- /// \brief Replaces an item in the heap.
- ///
- /// The \c i item is replaced with \c j item. The \c i item should
- /// be in the heap, while the \c j should be out of the heap. The
- /// \c i item will out of the heap and \c j will be in the heap
- /// with the same prioriority as prevoiusly the \c i item.
+ /// \brief Replace an item in the heap.
+ ///
+ /// This function replaces item \c i with item \c j.
+ /// Item \c i must be in the heap, while \c j must be out of the heap.
+ /// After calling this method, item \c i will be out of the
+ /// heap and \c j will be in the heap with the same prioriority
+ /// as item \c i had before.
void replace(const Item& i, const Item& j) {
int idx = _iim[i];
Index: lemon/binom_heap.h
===================================================================
--- lemon/binom_heap.h (revision 754)
+++ lemon/binom_heap.h (revision 754)
@@ -0,0 +1,445 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2009
+ * 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_BINOM_HEAP_H
+#define LEMON_BINOM_HEAP_H
+
+///\file
+///\ingroup heaps
+///\brief Binomial Heap implementation.
+
+#include
+#include
+#include
+#include
+#include
+
+namespace lemon {
+
+ /// \ingroup heaps
+ ///
+ ///\brief Binomial heap data structure.
+ ///
+ /// This class implements the \e binomial \e heap data structure.
+ /// It fully conforms to the \ref concepts::Heap "heap concept".
+ ///
+ /// The methods \ref increase() and \ref erase() are not efficient
+ /// in a binomial heap. In case of many calls of these operations,
+ /// it is better to use other heap structure, e.g. \ref BinHeap
+ /// "binary heap".
+ ///
+ /// \tparam PR Type of the priorities of the items.
+ /// \tparam IM A read-writable item map with \c int values, used
+ /// internally to handle the cross references.
+ /// \tparam CMP A functor class for comparing the priorities.
+ /// The default is \c std::less.
+#ifdef DOXYGEN
+ template
+#else
+ template >
+#endif
+ class BinomHeap {
+ public:
+ /// Type of the item-int map.
+ typedef IM ItemIntMap;
+ /// Type of the priorities.
+ typedef PR Prio;
+ /// Type of the items stored in the heap.
+ typedef typename ItemIntMap::Key Item;
+ /// Functor type for comparing the priorities.
+ typedef CMP Compare;
+
+ /// \brief Type to represent the states of the items.
+ ///
+ /// Each item has a state associated to it. It can be "in heap",
+ /// "pre-heap" or "post-heap". The latter two are indifferent from the
+ /// heap's point of view, but may be useful to the user.
+ ///
+ /// The item-int map must be initialized in such way that it assigns
+ /// \c PRE_HEAP (-1) to any element to be put in the heap.
+ enum State {
+ IN_HEAP = 0, ///< = 0.
+ PRE_HEAP = -1, ///< = -1.
+ POST_HEAP = -2 ///< = -2.
+ };
+
+ private:
+ class Store;
+
+ std::vector _data;
+ int _min, _head;
+ ItemIntMap &_iim;
+ Compare _comp;
+ int _num_items;
+
+ public:
+ /// \brief Constructor.
+ ///
+ /// Constructor.
+ /// \param map A map that assigns \c int values to the items.
+ /// It is used internally to handle the cross references.
+ /// The assigned value must be \c PRE_HEAP (-1) for each item.
+ explicit BinomHeap(ItemIntMap &map)
+ : _min(0), _head(-1), _iim(map), _num_items(0) {}
+
+ /// \brief Constructor.
+ ///
+ /// Constructor.
+ /// \param map A map that assigns \c int values to the items.
+ /// It is used internally to handle the cross references.
+ /// The assigned value must be \c PRE_HEAP (-1) for each item.
+ /// \param comp The function object used for comparing the priorities.
+ BinomHeap(ItemIntMap &map, const Compare &comp)
+ : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
+
+ /// \brief The number of items stored in the heap.
+ ///
+ /// This function returns the number of items stored in the heap.
+ int size() const { return _num_items; }
+
+ /// \brief Check if the heap is empty.
+ ///
+ /// This function returns \c true if the heap is empty.
+ bool empty() const { return _num_items==0; }
+
+ /// \brief Make the heap empty.
+ ///
+ /// This functon makes the heap empty.
+ /// It does not change the cross reference map. If you want to reuse
+ /// a heap that is not surely empty, you should first clear it and
+ /// then you should set the cross reference map to \c PRE_HEAP
+ /// for each item.
+ void clear() {
+ _data.clear(); _min=0; _num_items=0; _head=-1;
+ }
+
+ /// \brief Set the priority of an item or insert it, if it is
+ /// not stored in the heap.
+ ///
+ /// This method sets the priority of the given item if it is
+ /// already stored in the heap. Otherwise it inserts the given
+ /// item into the heap with the given priority.
+ /// \param item The item.
+ /// \param value The priority.
+ void set (const Item& item, const Prio& value) {
+ int i=_iim[item];
+ if ( i >= 0 && _data[i].in ) {
+ if ( _comp(value, _data[i].prio) ) decrease(item, value);
+ if ( _comp(_data[i].prio, value) ) increase(item, value);
+ } else push(item, value);
+ }
+
+ /// \brief Insert an item into the heap with the given priority.
+ ///
+ /// This function inserts the given item into the heap with the
+ /// given priority.
+ /// \param item The item to insert.
+ /// \param value The priority of the item.
+ /// \pre \e item must not be stored in the heap.
+ void push (const Item& item, const Prio& value) {
+ int i=_iim[item];
+ if ( i<0 ) {
+ int s=_data.size();
+ _iim.set( item,s );
+ Store st;
+ st.name=item;
+ st.prio=value;
+ _data.push_back(st);
+ i=s;
+ }
+ else {
+ _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
+ _data[i].degree=0;
+ _data[i].in=true;
+ _data[i].prio=value;
+ }
+
+ if( 0==_num_items ) {
+ _head=i;
+ _min=i;
+ } else {
+ merge(i);
+ if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
+ }
+ ++_num_items;
+ }
+
+ /// \brief Return the item having minimum priority.
+ ///
+ /// This function returns the item having minimum priority.
+ /// \pre The heap must be non-empty.
+ Item top() const { return _data[_min].name; }
+
+ /// \brief The minimum priority.
+ ///
+ /// This function returns the minimum priority.
+ /// \pre The heap must be non-empty.
+ Prio prio() const { return _data[_min].prio; }
+
+ /// \brief The priority of the given item.
+ ///
+ /// This function returns the priority of the given item.
+ /// \param item The item.
+ /// \pre \e item must be in the heap.
+ const Prio& operator[](const Item& item) const {
+ return _data[_iim[item]].prio;
+ }
+
+ /// \brief Remove the item having minimum priority.
+ ///
+ /// This function removes the item having minimum priority.
+ /// \pre The heap must be non-empty.
+ void pop() {
+ _data[_min].in=false;
+
+ int head_child=-1;
+ if ( _data[_min].child!=-1 ) {
+ int child=_data[_min].child;
+ int neighb;
+ while( child!=-1 ) {
+ neighb=_data[child].right_neighbor;
+ _data[child].parent=-1;
+ _data[child].right_neighbor=head_child;
+ head_child=child;
+ child=neighb;
+ }
+ }
+
+ if ( _data[_head].right_neighbor==-1 ) {
+ // there was only one root
+ _head=head_child;
+ }
+ else {
+ // there were more roots
+ if( _head!=_min ) { unlace(_min); }
+ else { _head=_data[_head].right_neighbor; }
+ merge(head_child);
+ }
+ _min=findMin();
+ --_num_items;
+ }
+
+ /// \brief Remove the given item from the heap.
+ ///
+ /// This function removes the given item from the heap if it is
+ /// already stored.
+ /// \param item The item to delete.
+ /// \pre \e item must be in the heap.
+ void erase (const Item& item) {
+ int i=_iim[item];
+ if ( i >= 0 && _data[i].in ) {
+ decrease( item, _data[_min].prio-1 );
+ pop();
+ }
+ }
+
+ /// \brief Decrease the priority of an item to the given value.
+ ///
+ /// This function decreases the priority of an item to the given value.
+ /// \param item The item.
+ /// \param value The priority.
+ /// \pre \e item must be stored in the heap with priority at least \e value.
+ void decrease (Item item, const Prio& value) {
+ int i=_iim[item];
+ int p=_data[i].parent;
+ _data[i].prio=value;
+
+ while( p!=-1 && _comp(value, _data[p].prio) ) {
+ _data[i].name=_data[p].name;
+ _data[i].prio=_data[p].prio;
+ _data[p].name=item;
+ _data[p].prio=value;
+ _iim[_data[i].name]=i;
+ i=p;
+ p=_data[p].parent;
+ }
+ _iim[item]=i;
+ if ( _comp(value, _data[_min].prio) ) _min=i;
+ }
+
+ /// \brief Increase the priority of an item to the given value.
+ ///
+ /// This function increases the priority of an item to the given value.
+ /// \param item The item.
+ /// \param value The priority.
+ /// \pre \e item must be stored in the heap with priority at most \e value.
+ void increase (Item item, const Prio& value) {
+ erase(item);
+ push(item, value);
+ }
+
+ /// \brief Return the state of an item.
+ ///
+ /// This method returns \c PRE_HEAP if the given item has never
+ /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
+ /// and \c POST_HEAP otherwise.
+ /// In the latter case it is possible that the item will get back
+ /// to the heap again.
+ /// \param item The item.
+ State state(const Item &item) const {
+ int i=_iim[item];
+ if( i>=0 ) {
+ if ( _data[i].in ) i=0;
+ else i=-2;
+ }
+ return State(i);
+ }
+
+ /// \brief Set the state of an item in the heap.
+ ///
+ /// This function sets the state of the given item in the heap.
+ /// It can be used to manually clear the heap when it is important
+ /// to achive better time complexity.
+ /// \param i The item.
+ /// \param st The state. It should not be \c IN_HEAP.
+ void state(const Item& i, State st) {
+ switch (st) {
+ case POST_HEAP:
+ case PRE_HEAP:
+ if (state(i) == IN_HEAP) {
+ erase(i);
+ }
+ _iim[i] = st;
+ break;
+ case IN_HEAP:
+ break;
+ }
+ }
+
+ private:
+
+ // Find the minimum of the roots
+ int findMin() {
+ if( _head!=-1 ) {
+ int min_loc=_head, min_val=_data[_head].prio;
+ for( int x=_data[_head].right_neighbor; x!=-1;
+ x=_data[x].right_neighbor ) {
+ if( _comp( _data[x].prio,min_val ) ) {
+ min_val=_data[x].prio;
+ min_loc=x;
+ }
+ }
+ return min_loc;
+ }
+ else return -1;
+ }
+
+ // Merge the heap with another heap starting at the given position
+ void merge(int a) {
+ if( _head==-1 || a==-1 ) return;
+ if( _data[a].right_neighbor==-1 &&
+ _data[a].degree<=_data[_head].degree ) {
+ _data[a].right_neighbor=_head;
+ _head=a;
+ } else {
+ interleave(a);
+ }
+ if( _data[_head].right_neighbor==-1 ) return;
+
+ int x=_head;
+ int x_prev=-1, x_next=_data[x].right_neighbor;
+ while( x_next!=-1 ) {
+ if( _data[x].degree!=_data[x_next].degree ||
+ ( _data[x_next].right_neighbor!=-1 &&
+ _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
+ x_prev=x;
+ x=x_next;
+ }
+ else {
+ if( _comp(_data[x_next].prio,_data[x].prio) ) {
+ if( x_prev==-1 ) {
+ _head=x_next;
+ } else {
+ _data[x_prev].right_neighbor=x_next;
+ }
+ fuse(x,x_next);
+ x=x_next;
+ }
+ else {
+ _data[x].right_neighbor=_data[x_next].right_neighbor;
+ fuse(x_next,x);
+ }
+ }
+ x_next=_data[x].right_neighbor;
+ }
+ }
+
+ // Interleave the elements of the given list into the list of the roots
+ void interleave(int a) {
+ int p=_head, q=a;
+ int curr=_data.size();
+ _data.push_back(Store());
+
+ while( p!=-1 || q!=-1 ) {
+ if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
+ _data[curr].right_neighbor=p;
+ curr=p;
+ p=_data[p].right_neighbor;
+ }
+ else {
+ _data[curr].right_neighbor=q;
+ curr=q;
+ q=_data[q].right_neighbor;
+ }
+ }
+
+ _head=_data.back().right_neighbor;
+ _data.pop_back();
+ }
+
+ // Lace node a under node b
+ void fuse(int a, int b) {
+ _data[a].parent=b;
+ _data[a].right_neighbor=_data[b].child;
+ _data[b].child=a;
+
+ ++_data[b].degree;
+ }
+
+ // Unlace node a (if it has siblings)
+ void unlace(int a) {
+ int neighb=_data[a].right_neighbor;
+ int other=_head;
+
+ while( _data[other].right_neighbor!=a )
+ other=_data[other].right_neighbor;
+ _data[other].right_neighbor=neighb;
+ }
+
+ private:
+
+ class Store {
+ friend class BinomHeap;
+
+ Item name;
+ int parent;
+ int right_neighbor;
+ int child;
+ int degree;
+ bool in;
+ Prio prio;
+
+ Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
+ in(true) {}
+ };
+ };
+
+} //namespace lemon
+
+#endif //LEMON_BINOM_HEAP_H
+
Index: lemon/bits/graph_extender.h
===================================================================
--- lemon/bits/graph_extender.h (revision 732)
+++ lemon/bits/graph_extender.h (revision 825)
@@ -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/bucket_heap.h
===================================================================
--- lemon/bucket_heap.h (revision 730)
+++ lemon/bucket_heap.h (revision 758)
@@ -20,7 +20,7 @@
#define LEMON_BUCKET_HEAP_H
-///\ingroup auxdat
+///\ingroup heaps
///\file
-///\brief Bucket Heap implementation.
+///\brief Bucket heap implementation.
#include
@@ -54,33 +54,39 @@
}
- /// \ingroup auxdat
- ///
- /// \brief A Bucket Heap implementation.
- ///
- /// This class implements the \e bucket \e heap data structure. A \e heap
- /// is a data structure for storing items with specified values called \e
- /// priorities in such a way that finding the item with minimum priority is
- /// efficient. The bucket heap is very simple implementation, it can store
- /// only integer priorities and it stores for each priority in the
- /// \f$ [0..C) \f$ range a list of items. So it should be used only when
- /// the priorities are small. It is not intended to use as dijkstra heap.
- ///
- /// \param IM A read and write Item int map, used internally
- /// to handle the cross references.
- /// \param MIN If the given parameter is false then instead of the
- /// minimum value the maximum can be retrivied with the top() and
- /// prio() member functions.
+ /// \ingroup heaps
+ ///
+ /// \brief Bucket heap data structure.
+ ///
+ /// This class implements the \e bucket \e heap data structure.
+ /// It practically conforms to the \ref concepts::Heap "heap concept",
+ /// but it has some limitations.
+ ///
+ /// The bucket heap is a very simple structure. It can store only
+ /// \c int priorities and it maintains a list of items for each priority
+ /// in the range [0..C). So it should only be used when the
+ /// priorities are small. It is not intended to use as a Dijkstra heap.
+ ///
+ /// \tparam IM A read-writable item map with \c int values, used
+ /// internally to handle the cross references.
+ /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
+ /// The default is \e min-heap. If this parameter is set to \c false,
+ /// then the comparison is reversed, so the top(), prio() and pop()
+ /// functions deal with the item having maximum priority instead of the
+ /// minimum.
+ ///
+ /// \sa SimpleBucketHeap
template
class BucketHeap {
public:
- /// \e
- typedef typename IM::Key Item;
- /// \e
+
+ /// Type of the item-int map.
+ typedef IM ItemIntMap;
+ /// Type of the priorities.
typedef int Prio;
- /// \e
- typedef std::pair
- Pair;
- /// \e
- typedef IM ItemIntMap;
+ /// Type of the items stored in the heap.
+ typedef typename ItemIntMap::Key Item;
+ /// Type of the item-priority pairs.
+ typedef std::pair
- Pair;
private:
@@ -90,8 +96,8 @@
public:
- /// \brief Type to represent the items states.
- ///
- /// Each Item element have a state associated to it. It may be "in heap",
- /// "pre heap" or "post heap". The latter two are indifferent from the
+ /// \brief Type to represent the states of the items.
+ ///
+ /// Each item has a state associated to it. It can be "in heap",
+ /// "pre-heap" or "post-heap". The latter two are indifferent from the
/// heap's point of view, but may be useful to the user.
///
@@ -105,28 +111,30 @@
public:
- /// \brief The constructor.
- ///
- /// The constructor.
- /// \param map should be given to the constructor, since it is used
- /// internally to handle the cross references. The value of the map
- /// should be PRE_HEAP (-1) for each element.
+
+ /// \brief Constructor.
+ ///
+ /// Constructor.
+ /// \param map A map that assigns \c int values to the items.
+ /// It is used internally to handle the cross references.
+ /// The assigned value must be \c PRE_HEAP (-1) for each item.
explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
- /// The number of items stored in the heap.
- ///
- /// \brief Returns the number of items stored in the heap.
+ /// \brief The number of items stored in the heap.
+ ///
+ /// This function returns the number of items stored in the heap.
int size() const { return _data.size(); }
- /// \brief Checks if the heap stores no items.
- ///
- /// Returns \c true if and only if the heap stores no items.
+ /// \brief Check if the heap is empty.
+ ///
+ /// This function returns \c true if the heap is empty.
bool empty() const { return _data.empty(); }
- /// \brief Make empty this heap.
- ///
- /// Make empty this heap. It does not change the cross reference
- /// map. If you want to reuse a heap what is not surely empty you
- /// should first clear the heap and after that you should set the
- /// cross reference map for each item to \c PRE_HEAP.
+ /// \brief Make the heap empty.
+ ///
+ /// This functon makes the heap empty.
+ /// It does not change the cross reference map. If you want to reuse
+ /// a heap that is not surely empty, you should first clear it and
+ /// then you should set the cross reference map to \c PRE_HEAP
+ /// for each item.
void clear() {
_data.clear(); _first.clear(); _minimum = 0;
@@ -135,5 +143,5 @@
private:
- void relocate_last(int idx) {
+ void relocateLast(int idx) {
if (idx + 1 < int(_data.size())) {
_data[idx] = _data.back();
@@ -175,8 +183,11 @@
public:
+
/// \brief Insert a pair of item and priority into the heap.
///
- /// Adds \c p.first to the heap with priority \c p.second.
+ /// This function inserts \c p.first to the heap with priority
+ /// \c p.second.
/// \param p The pair to insert.
+ /// \pre \c p.first must not be stored in the heap.
void push(const Pair& p) {
push(p.first, p.second);
@@ -185,7 +196,9 @@
/// \brief Insert an item into the heap with the given priority.
///
- /// Adds \c i to the heap with priority \c p.
+ /// This function inserts the given item into the heap with the
+ /// given priority.
/// \param i The item to insert.
/// \param p The priority of the item.
+ /// \pre \e i must not be stored in the heap.
void push(const Item &i, const Prio &p) {
int idx = _data.size();
@@ -198,8 +211,8 @@
}
- /// \brief Returns the item with minimum priority.
- ///
- /// This method returns the item with minimum priority.
- /// \pre The heap must be nonempty.
+ /// \brief Return the item having minimum priority.
+ ///
+ /// This function returns the item having minimum priority.
+ /// \pre The heap must be non-empty.
Item top() const {
while (_first[_minimum] == -1) {
@@ -209,8 +222,8 @@
}
- /// \brief Returns the minimum priority.
- ///
- /// It returns the minimum priority.
- /// \pre The heap must be nonempty.
+ /// \brief The minimum priority.
+ ///
+ /// This function returns the minimum priority.
+ /// \pre The heap must be non-empty.
Prio prio() const {
while (_first[_minimum] == -1) {
@@ -220,7 +233,7 @@
}
- /// \brief Deletes the item with minimum priority.
- ///
- /// This method deletes the item with minimum priority from the heap.
+ /// \brief Remove the item having minimum priority.
+ ///
+ /// This function removes the item having minimum priority.
/// \pre The heap must be non-empty.
void pop() {
@@ -231,25 +244,25 @@
_iim[_data[idx].item] = -2;
unlace(idx);
- relocate_last(idx);
- }
-
- /// \brief Deletes \c i from the heap.
- ///
- /// This method deletes item \c i from the heap, if \c i was
- /// already stored in the heap.
- /// \param i The item to erase.
+ relocateLast(idx);
+ }
+
+ /// \brief Remove the given item from the heap.
+ ///
+ /// This function removes the given item from the heap if it is
+ /// already stored.
+ /// \param i The item to delete.
+ /// \pre \e i must be in the heap.
void erase(const Item &i) {
int idx = _iim[i];
_iim[_data[idx].item] = -2;
unlace(idx);
- relocate_last(idx);
- }
-
-
- /// \brief Returns the priority of \c i.
- ///
- /// This function returns the priority of item \c i.
- /// \pre \c i must be in the heap.
- /// \param i The item.
+ relocateLast(idx);
+ }
+
+ /// \brief The priority of the given item.
+ ///
+ /// This function returns the priority of the given item.
+ /// \param i The item.
+ /// \pre \e i must be in the heap.
Prio operator[](const Item &i) const {
int idx = _iim[i];
@@ -257,9 +270,10 @@
}
- /// \brief \c i gets to the heap with priority \c p independently
- /// if \c i was already there.
- ///
- /// This method calls \ref push(\c i, \c p) if \c i is not stored
- /// in the heap and sets the priority of \c i to \c p otherwise.
+ /// \brief Set the priority of an item or insert it, if it is
+ /// not stored in the heap.
+ ///
+ /// This method sets the priority of the given item if it is
+ /// already stored in the heap. Otherwise it inserts the given
+ /// item into the heap with the given priority.
/// \param i The item.
/// \param p The priority.
@@ -275,11 +289,10 @@
}
- /// \brief Decreases the priority of \c i to \c p.
- ///
- /// This method decreases the priority of item \c i to \c p.
- /// \pre \c i must be stored in the heap with priority at least \c
- /// p relative to \c Compare.
+ /// \brief Decrease the priority of an item to the given value.
+ ///
+ /// This function decreases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
+ /// \pre \e i must be stored in the heap with priority at least \e p.
void decrease(const Item &i, const Prio &p) {
int idx = _iim[i];
@@ -292,11 +305,10 @@
}
- /// \brief Increases the priority of \c i to \c p.
- ///
- /// This method sets the priority of item \c i to \c p.
- /// \pre \c i must be stored in the heap with priority at most \c
- /// p relative to \c Compare.
+ /// \brief Increase the priority of an item to the given value.
+ ///
+ /// This function increases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
+ /// \pre \e i must be stored in the heap with priority at most \e p.
void increase(const Item &i, const Prio &p) {
int idx = _iim[i];
@@ -306,11 +318,11 @@
}
- /// \brief Returns if \c item is in, has already been in, or has
- /// never been in the heap.
- ///
- /// This method returns PRE_HEAP if \c item has never been in the
- /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
- /// otherwise. In the latter case it is possible that \c item will
- /// get back to the heap again.
+ /// \brief Return the state of an item.
+ ///
+ /// This method returns \c PRE_HEAP if the given item has never
+ /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
+ /// and \c POST_HEAP otherwise.
+ /// In the latter case it is possible that the item will get back
+ /// to the heap again.
/// \param i The item.
State state(const Item &i) const {
@@ -320,9 +332,9 @@
}
- /// \brief Sets the state of the \c item in the heap.
- ///
- /// Sets the state of the \c item in the heap. It can be used to
- /// manually clear the heap when it is important to achive the
- /// better time complexity.
+ /// \brief Set the state of an item in the heap.
+ ///
+ /// This function sets the state of the given item in the heap.
+ /// It can be used to manually clear the heap when it is important
+ /// to achive better time complexity.
/// \param i The item.
/// \param st The state. It should not be \c IN_HEAP.
@@ -360,21 +372,27 @@
}; // class BucketHeap
- /// \ingroup auxdat
- ///
- /// \brief A Simplified Bucket Heap implementation.
+ /// \ingroup heaps
+ ///
+ /// \brief Simplified bucket heap data structure.
///
/// This class implements a simplified \e bucket \e heap data
- /// structure. It does not provide some functionality but it faster
- /// and simplier data structure than the BucketHeap. The main
- /// difference is that the BucketHeap stores for every key a double
- /// linked list while this class stores just simple lists. In the
- /// other way it does not support erasing each elements just the
- /// minimal and it does not supports key increasing, decreasing.
- ///
- /// \param IM A read and write Item int map, used internally
- /// to handle the cross references.
- /// \param MIN If the given parameter is false then instead of the
- /// minimum value the maximum can be retrivied with the top() and
- /// prio() member functions.
+ /// structure. It does not provide some functionality, but it is
+ /// faster and simpler than BucketHeap. The main difference is
+ /// that BucketHeap stores a doubly-linked list for each key while
+ /// this class stores only simply-linked lists. It supports erasing
+ /// only for the item having minimum priority and it does not support
+ /// key increasing and decreasing.
+ ///
+ /// Note that this implementation does not conform to the
+ /// \ref concepts::Heap "heap concept" due to the lack of some
+ /// functionality.
+ ///
+ /// \tparam IM A read-writable item map with \c int values, used
+ /// internally to handle the cross references.
+ /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
+ /// The default is \e min-heap. If this parameter is set to \c false,
+ /// then the comparison is reversed, so the top(), prio() and pop()
+ /// functions deal with the item having maximum priority instead of the
+ /// minimum.
///
/// \sa BucketHeap
@@ -383,8 +401,13 @@
public:
- typedef typename IM::Key Item;
+
+ /// Type of the item-int map.
+ typedef IM ItemIntMap;
+ /// Type of the priorities.
typedef int Prio;
- typedef std::pair
- Pair;
- typedef IM ItemIntMap;
+ /// Type of the items stored in the heap.
+ typedef typename ItemIntMap::Key Item;
+ /// Type of the item-priority pairs.
+ typedef std::pair
- Pair;
private:
@@ -394,8 +417,8 @@
public:
- /// \brief Type to represent the items states.
- ///
- /// Each Item element have a state associated to it. It may be "in heap",
- /// "pre heap" or "post heap". The latter two are indifferent from the
+ /// \brief Type to represent the states of the items.
+ ///
+ /// Each item has a state associated to it. It can be "in heap",
+ /// "pre-heap" or "post-heap". The latter two are indifferent from the
/// heap's point of view, but may be useful to the user.
///
@@ -410,29 +433,30 @@
public:
- /// \brief The constructor.
- ///
- /// The constructor.
- /// \param map should be given to the constructor, since it is used
- /// internally to handle the cross references. The value of the map
- /// should be PRE_HEAP (-1) for each element.
+ /// \brief Constructor.
+ ///
+ /// Constructor.
+ /// \param map A map that assigns \c int values to the items.
+ /// It is used internally to handle the cross references.
+ /// The assigned value must be \c PRE_HEAP (-1) for each item.
explicit SimpleBucketHeap(ItemIntMap &map)
: _iim(map), _free(-1), _num(0), _minimum(0) {}
- /// \brief Returns the number of items stored in the heap.
- ///
- /// The number of items stored in the heap.
+ /// \brief The number of items stored in the heap.
+ ///
+ /// This function returns the number of items stored in the heap.
int size() const { return _num; }
- /// \brief Checks if the heap stores no items.
- ///
- /// Returns \c true if and only if the heap stores no items.
+ /// \brief Check if the heap is empty.
+ ///
+ /// This function returns \c true if the heap is empty.
bool empty() const { return _num == 0; }
- /// \brief Make empty this heap.
- ///
- /// Make empty this heap. It does not change the cross reference
- /// map. If you want to reuse a heap what is not surely empty you
- /// should first clear the heap and after that you should set the
- /// cross reference map for each item to \c PRE_HEAP.
+ /// \brief Make the heap empty.
+ ///
+ /// This functon makes the heap empty.
+ /// It does not change the cross reference map. If you want to reuse
+ /// a heap that is not surely empty, you should first clear it and
+ /// then you should set the cross reference map to \c PRE_HEAP
+ /// for each item.
void clear() {
_data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
@@ -441,6 +465,8 @@
/// \brief Insert a pair of item and priority into the heap.
///
- /// Adds \c p.first to the heap with priority \c p.second.
+ /// This function inserts \c p.first to the heap with priority
+ /// \c p.second.
/// \param p The pair to insert.
+ /// \pre \c p.first must not be stored in the heap.
void push(const Pair& p) {
push(p.first, p.second);
@@ -449,7 +475,9 @@
/// \brief Insert an item into the heap with the given priority.
///
- /// Adds \c i to the heap with priority \c p.
+ /// This function inserts the given item into the heap with the
+ /// given priority.
/// \param i The item to insert.
/// \param p The priority of the item.
+ /// \pre \e i must not be stored in the heap.
void push(const Item &i, const Prio &p) {
int idx;
@@ -472,8 +500,8 @@
}
- /// \brief Returns the item with minimum priority.
- ///
- /// This method returns the item with minimum priority.
- /// \pre The heap must be nonempty.
+ /// \brief Return the item having minimum priority.
+ ///
+ /// This function returns the item having minimum priority.
+ /// \pre The heap must be non-empty.
Item top() const {
while (_first[_minimum] == -1) {
@@ -483,8 +511,8 @@
}
- /// \brief Returns the minimum priority.
- ///
- /// It returns the minimum priority.
- /// \pre The heap must be nonempty.
+ /// \brief The minimum priority.
+ ///
+ /// This function returns the minimum priority.
+ /// \pre The heap must be non-empty.
Prio prio() const {
while (_first[_minimum] == -1) {
@@ -494,7 +522,7 @@
}
- /// \brief Deletes the item with minimum priority.
- ///
- /// This method deletes the item with minimum priority from the heap.
+ /// \brief Remove the item having minimum priority.
+ ///
+ /// This function removes the item having minimum priority.
/// \pre The heap must be non-empty.
void pop() {
@@ -510,14 +538,13 @@
}
- /// \brief Returns the priority of \c i.
- ///
- /// This function returns the priority of item \c i.
- /// \warning This operator is not a constant time function
- /// because it scans the whole data structure to find the proper
- /// value.
- /// \pre \c i must be in the heap.
- /// \param i The item.
+ /// \brief The priority of the given item.
+ ///
+ /// This function returns the priority of the given item.
+ /// \param i The item.
+ /// \pre \e i must be in the heap.
+ /// \warning This operator is not a constant time function because
+ /// it scans the whole data structure to find the proper value.
Prio operator[](const Item &i) const {
- for (int k = 0; k < _first.size(); ++k) {
+ for (int k = 0; k < int(_first.size()); ++k) {
int idx = _first[k];
while (idx != -1) {
@@ -531,11 +558,11 @@
}
- /// \brief Returns if \c item is in, has already been in, or has
- /// never been in the heap.
- ///
- /// This method returns PRE_HEAP if \c item has never been in the
- /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
- /// otherwise. In the latter case it is possible that \c item will
- /// get back to the heap again.
+ /// \brief Return the state of an item.
+ ///
+ /// This method returns \c PRE_HEAP if the given item has never
+ /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
+ /// and \c POST_HEAP otherwise.
+ /// In the latter case it is possible that the item will get back
+ /// to the heap again.
/// \param i The item.
State state(const Item &i) const {
Index: lemon/capacity_scaling.h
===================================================================
--- lemon/capacity_scaling.h (revision 887)
+++ lemon/capacity_scaling.h (revision 887)
@@ -0,0 +1,951 @@
+/* -*- 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_CAPACITY_SCALING_H
+#define LEMON_CAPACITY_SCALING_H
+
+/// \ingroup min_cost_flow_algs
+///
+/// \file
+/// \brief Capacity Scaling algorithm for finding a minimum cost flow.
+
+#include
+#include
+#include
+#include
+
+namespace lemon {
+
+ /// \brief Default traits class of CapacityScaling algorithm.
+ ///
+ /// Default traits class of CapacityScaling algorithm.
+ /// \tparam GR Digraph type.
+ /// \tparam V The number type used for flow amounts, capacity bounds
+ /// and supply values. By default it is \c int.
+ /// \tparam C The number type used for costs and potentials.
+ /// By default it is the same as \c V.
+ template
+ struct CapacityScalingDefaultTraits
+ {
+ /// The type of the digraph
+ typedef GR Digraph;
+ /// The type of the flow amounts, capacity bounds and supply values
+ typedef V Value;
+ /// The type of the arc costs
+ typedef C Cost;
+
+ /// \brief The type of the heap used for internal Dijkstra computations.
+ ///
+ /// The type of the heap used for internal Dijkstra computations.
+ /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
+ /// its priority type must be \c Cost and its cross reference type
+ /// must be \ref RangeMap "RangeMap".
+ typedef BinHeap > Heap;
+ };
+
+ /// \addtogroup min_cost_flow_algs
+ /// @{
+
+ /// \brief Implementation of the Capacity Scaling algorithm for
+ /// finding a \ref min_cost_flow "minimum cost flow".
+ ///
+ /// \ref CapacityScaling implements the capacity scaling version
+ /// of the successive shortest path algorithm for finding a
+ /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
+ /// \ref edmondskarp72theoretical. It is an efficient dual
+ /// solution method.
+ ///
+ /// Most of the parameters of the problem (except for the digraph)
+ /// can be given using separate functions, and the algorithm can be
+ /// executed using the \ref run() function. If some parameters are not
+ /// specified, then default values will be used.
+ ///
+ /// \tparam GR The digraph type the algorithm runs on.
+ /// \tparam V The number type used for flow amounts, capacity bounds
+ /// and supply values in the algorithm. By default it is \c int.
+ /// \tparam C The number type used for costs and potentials in the
+ /// algorithm. By default it is the same as \c V.
+ ///
+ /// \warning Both number types must be signed and all input data must
+ /// be integer.
+ /// \warning This algorithm does not support negative costs for such
+ /// arcs that have infinite upper bound.
+#ifdef DOXYGEN
+ template
+#else
+ template < typename GR, typename V = int, typename C = V,
+ typename TR = CapacityScalingDefaultTraits >
+#endif
+ class CapacityScaling
+ {
+ public:
+
+ /// The type of the digraph
+ typedef typename TR::Digraph Digraph;
+ /// The type of the flow amounts, capacity bounds and supply values
+ typedef typename TR::Value Value;
+ /// The type of the arc costs
+ typedef typename TR::Cost Cost;
+
+ /// The type of the heap used for internal Dijkstra computations
+ typedef typename TR::Heap Heap;
+
+ /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
+ typedef TR Traits;
+
+ public:
+
+ /// \brief Problem type constants for the \c run() function.
+ ///
+ /// Enum type containing the problem type constants that can be
+ /// returned by the \ref run() function of the algorithm.
+ enum ProblemType {
+ /// The problem has no feasible solution (flow).
+ INFEASIBLE,
+ /// The problem has optimal solution (i.e. it is feasible and
+ /// bounded), and the algorithm has found optimal flow and node
+ /// potentials (primal and dual solutions).
+ OPTIMAL,
+ /// The digraph contains an arc of negative cost and infinite
+ /// upper bound. It means that the objective function is unbounded
+ /// on that arc, however, note that it could actually be bounded
+ /// over the feasible flows, but this algroithm cannot handle
+ /// these cases.
+ UNBOUNDED
+ };
+
+ private:
+
+ TEMPLATE_DIGRAPH_TYPEDEFS(GR);
+
+ typedef std::vector IntVector;
+ typedef std::vector BoolVector;
+ typedef std::vector ValueVector;
+ typedef std::vector CostVector;
+
+ private:
+
+ // Data related to the underlying digraph
+ const GR &_graph;
+ int _node_num;
+ int _arc_num;
+ int _res_arc_num;
+ int _root;
+
+ // Parameters of the problem
+ bool _have_lower;
+ Value _sum_supply;
+
+ // Data structures for storing the digraph
+ IntNodeMap _node_id;
+ IntArcMap _arc_idf;
+ IntArcMap _arc_idb;
+ IntVector _first_out;
+ BoolVector _forward;
+ IntVector _source;
+ IntVector _target;
+ IntVector _reverse;
+
+ // Node and arc data
+ ValueVector _lower;
+ ValueVector _upper;
+ CostVector _cost;
+ ValueVector _supply;
+
+ ValueVector _res_cap;
+ CostVector _pi;
+ ValueVector _excess;
+ IntVector _excess_nodes;
+ IntVector _deficit_nodes;
+
+ Value _delta;
+ int _factor;
+ IntVector _pred;
+
+ public:
+
+ /// \brief Constant for infinite upper bounds (capacities).
+ ///
+ /// Constant for infinite upper bounds (capacities).
+ /// It is \c std::numeric_limits::infinity() if available,
+ /// \c std::numeric_limits::max() otherwise.
+ const Value INF;
+
+ private:
+
+ // Special implementation of the Dijkstra algorithm for finding
+ // shortest paths in the residual network of the digraph with
+ // respect to the reduced arc costs and modifying the node
+ // potentials according to the found distance labels.
+ class ResidualDijkstra
+ {
+ private:
+
+ int _node_num;
+ bool _geq;
+ const IntVector &_first_out;
+ const IntVector &_target;
+ const CostVector &_cost;
+ const ValueVector &_res_cap;
+ const ValueVector &_excess;
+ CostVector &_pi;
+ IntVector &_pred;
+
+ IntVector _proc_nodes;
+ CostVector _dist;
+
+ public:
+
+ ResidualDijkstra(CapacityScaling& cs) :
+ _node_num(cs._node_num), _geq(cs._sum_supply < 0),
+ _first_out(cs._first_out), _target(cs._target), _cost(cs._cost),
+ _res_cap(cs._res_cap), _excess(cs._excess), _pi(cs._pi),
+ _pred(cs._pred), _dist(cs._node_num)
+ {}
+
+ int run(int s, Value delta = 1) {
+ RangeMap heap_cross_ref(_node_num, Heap::PRE_HEAP);
+ Heap heap(heap_cross_ref);
+ heap.push(s, 0);
+ _pred[s] = -1;
+ _proc_nodes.clear();
+
+ // Process nodes
+ while (!heap.empty() && _excess[heap.top()] > -delta) {
+ int u = heap.top(), v;
+ Cost d = heap.prio() + _pi[u], dn;
+ _dist[u] = heap.prio();
+ _proc_nodes.push_back(u);
+ heap.pop();
+
+ // Traverse outgoing residual arcs
+ int last_out = _geq ? _first_out[u+1] : _first_out[u+1] - 1;
+ for (int a = _first_out[u]; a != last_out; ++a) {
+ if (_res_cap[a] < delta) continue;
+ v = _target[a];
+ switch (heap.state(v)) {
+ case Heap::PRE_HEAP:
+ heap.push(v, d + _cost[a] - _pi[v]);
+ _pred[v] = a;
+ break;
+ case Heap::IN_HEAP:
+ dn = d + _cost[a] - _pi[v];
+ if (dn < heap[v]) {
+ heap.decrease(v, dn);
+ _pred[v] = a;
+ }
+ break;
+ case Heap::POST_HEAP:
+ break;
+ }
+ }
+ }
+ if (heap.empty()) return -1;
+
+ // Update potentials of processed nodes
+ int t = heap.top();
+ Cost dt = heap.prio();
+ for (int i = 0; i < int(_proc_nodes.size()); ++i) {
+ _pi[_proc_nodes[i]] += _dist[_proc_nodes[i]] - dt;
+ }
+
+ return t;
+ }
+
+ }; //class ResidualDijkstra
+
+ public:
+
+ /// \name Named Template Parameters
+ /// @{
+
+ template
+ struct SetHeapTraits : public Traits {
+ typedef T Heap;
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// \c Heap type.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting \c Heap
+ /// type, which is used for internal Dijkstra computations.
+ /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
+ /// its priority type must be \c Cost and its cross reference type
+ /// must be \ref RangeMap "RangeMap".
+ template
+ struct SetHeap
+ : public CapacityScaling > {
+ typedef CapacityScaling > Create;
+ };
+
+ /// @}
+
+ public:
+
+ /// \brief Constructor.
+ ///
+ /// The constructor of the class.
+ ///
+ /// \param graph The digraph the algorithm runs on.
+ CapacityScaling(const GR& graph) :
+ _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
+ INF(std::numeric_limits::has_infinity ?
+ std::numeric_limits::infinity() :
+ std::numeric_limits::max())
+ {
+ // Check the number types
+ LEMON_ASSERT(std::numeric_limits::is_signed,
+ "The flow type of CapacityScaling must be signed");
+ LEMON_ASSERT(std::numeric_limits::is_signed,
+ "The cost type of CapacityScaling must be signed");
+
+ // Resize vectors
+ _node_num = countNodes(_graph);
+ _arc_num = countArcs(_graph);
+ _res_arc_num = 2 * (_arc_num + _node_num);
+ _root = _node_num;
+ ++_node_num;
+
+ _first_out.resize(_node_num + 1);
+ _forward.resize(_res_arc_num);
+ _source.resize(_res_arc_num);
+ _target.resize(_res_arc_num);
+ _reverse.resize(_res_arc_num);
+
+ _lower.resize(_res_arc_num);
+ _upper.resize(_res_arc_num);
+ _cost.resize(_res_arc_num);
+ _supply.resize(_node_num);
+
+ _res_cap.resize(_res_arc_num);
+ _pi.resize(_node_num);
+ _excess.resize(_node_num);
+ _pred.resize(_node_num);
+
+ // Copy the graph
+ int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1;
+ for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
+ _node_id[n] = i;
+ }
+ i = 0;
+ for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
+ _first_out[i] = j;
+ for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
+ _arc_idf[a] = j;
+ _forward[j] = true;
+ _source[j] = i;
+ _target[j] = _node_id[_graph.runningNode(a)];
+ }
+ for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
+ _arc_idb[a] = j;
+ _forward[j] = false;
+ _source[j] = i;
+ _target[j] = _node_id[_graph.runningNode(a)];
+ }
+ _forward[j] = false;
+ _source[j] = i;
+ _target[j] = _root;
+ _reverse[j] = k;
+ _forward[k] = true;
+ _source[k] = _root;
+ _target[k] = i;
+ _reverse[k] = j;
+ ++j; ++k;
+ }
+ _first_out[i] = j;
+ _first_out[_node_num] = k;
+ for (ArcIt a(_graph); a != INVALID; ++a) {
+ int fi = _arc_idf[a];
+ int bi = _arc_idb[a];
+ _reverse[fi] = bi;
+ _reverse[bi] = fi;
+ }
+
+ // Reset parameters
+ reset();
+ }
+
+ /// \name Parameters
+ /// The parameters of the algorithm can be specified using these
+ /// functions.
+
+ /// @{
+
+ /// \brief Set the lower bounds on the arcs.
+ ///
+ /// This function sets the lower bounds on the arcs.
+ /// If it is not used before calling \ref run(), the lower bounds
+ /// will be set to zero on all arcs.
+ ///
+ /// \param map An arc map storing the lower bounds.
+ /// Its \c Value type must be convertible to the \c Value type
+ /// of the algorithm.
+ ///
+ /// \return (*this)
+ template
+ CapacityScaling& lowerMap(const LowerMap& map) {
+ _have_lower = true;
+ for (ArcIt a(_graph); a != INVALID; ++a) {
+ _lower[_arc_idf[a]] = map[a];
+ _lower[_arc_idb[a]] = map[a];
+ }
+ return *this;
+ }
+
+ /// \brief Set the upper bounds (capacities) on the arcs.
+ ///
+ /// This function sets the upper bounds (capacities) on the arcs.
+ /// If it is not used before calling \ref run(), the upper bounds
+ /// will be set to \ref INF on all arcs (i.e. the flow value will be
+ /// unbounded from above).
+ ///
+ /// \param map An arc map storing the upper bounds.
+ /// Its \c Value type must be convertible to the \c Value type
+ /// of the algorithm.
+ ///
+ /// \return (*this)
+ template
+ CapacityScaling& upperMap(const UpperMap& map) {
+ for (ArcIt a(_graph); a != INVALID; ++a) {
+ _upper[_arc_idf[a]] = map[a];
+ }
+ return *this;
+ }
+
+ /// \brief Set the costs of the arcs.
+ ///
+ /// This function sets the costs of the arcs.
+ /// If it is not used before calling \ref run(), the costs
+ /// will be set to \c 1 on all arcs.
+ ///
+ /// \param map An arc map storing the costs.
+ /// Its \c Value type must be convertible to the \c Cost type
+ /// of the algorithm.
+ ///
+ /// \return (*this)
+ template
+ CapacityScaling& costMap(const CostMap& map) {
+ for (ArcIt a(_graph); a != INVALID; ++a) {
+ _cost[_arc_idf[a]] = map[a];
+ _cost[_arc_idb[a]] = -map[a];
+ }
+ return *this;
+ }
+
+ /// \brief Set the supply values of the nodes.
+ ///
+ /// This function sets the supply values of the nodes.
+ /// If neither this function nor \ref stSupply() is used before
+ /// calling \ref run(), the supply of each node will be set to zero.
+ ///
+ /// \param map A node map storing the supply values.
+ /// Its \c Value type must be convertible to the \c Value type
+ /// of the algorithm.
+ ///
+ /// \return (*this)
+ template
+ CapacityScaling& supplyMap(const SupplyMap& map) {
+ for (NodeIt n(_graph); n != INVALID; ++n) {
+ _supply[_node_id[n]] = map[n];
+ }
+ return *this;
+ }
+
+ /// \brief Set single source and target nodes and a supply value.
+ ///
+ /// This function sets a single source node and a single target node
+ /// and the required flow value.
+ /// If neither this function nor \ref supplyMap() is used before
+ /// calling \ref run(), the supply of each node will be set to zero.
+ ///
+ /// Using this function has the same effect as using \ref supplyMap()
+ /// with such a map in which \c k is assigned to \c s, \c -k is
+ /// assigned to \c t and all other nodes have zero supply value.
+ ///
+ /// \param s The source node.
+ /// \param t The target node.
+ /// \param k The required amount of flow from node \c s to node \c t
+ /// (i.e. the supply of \c s and the demand of \c t).
+ ///
+ /// \return (*this)
+ CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
+ for (int i = 0; i != _node_num; ++i) {
+ _supply[i] = 0;
+ }
+ _supply[_node_id[s]] = k;
+ _supply[_node_id[t]] = -k;
+ return *this;
+ }
+
+ /// @}
+
+ /// \name Execution control
+ /// The algorithm can be executed using \ref run().
+
+ /// @{
+
+ /// \brief Run the algorithm.
+ ///
+ /// This function runs the algorithm.
+ /// The paramters can be specified using functions \ref lowerMap(),
+ /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
+ /// For example,
+ /// \code
+ /// CapacityScaling cs(graph);
+ /// cs.lowerMap(lower).upperMap(upper).costMap(cost)
+ /// .supplyMap(sup).run();
+ /// \endcode
+ ///
+ /// This function can be called more than once. All the parameters
+ /// that have been given are kept for the next call, unless
+ /// \ref reset() is called, thus only the modified parameters
+ /// have to be set again. See \ref reset() for examples.
+ /// However, the underlying digraph must not be modified after this
+ /// class have been constructed, since it copies and extends the graph.
+ ///
+ /// \param factor The capacity scaling factor. It must be larger than
+ /// one to use scaling. If it is less or equal to one, then scaling
+ /// will be disabled.
+ ///
+ /// \return \c INFEASIBLE if no feasible flow exists,
+ /// \n \c OPTIMAL if the problem has optimal solution
+ /// (i.e. it is feasible and bounded), and the algorithm has found
+ /// optimal flow and node potentials (primal and dual solutions),
+ /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
+ /// and infinite upper bound. It means that the objective function
+ /// is unbounded on that arc, however, note that it could actually be
+ /// bounded over the feasible flows, but this algroithm cannot handle
+ /// these cases.
+ ///
+ /// \see ProblemType
+ ProblemType run(int factor = 4) {
+ _factor = factor;
+ ProblemType pt = init();
+ if (pt != OPTIMAL) return pt;
+ return start();
+ }
+
+ /// \brief Reset all the parameters that have been given before.
+ ///
+ /// This function resets all the paramaters that have been given
+ /// before using functions \ref lowerMap(), \ref upperMap(),
+ /// \ref costMap(), \ref supplyMap(), \ref stSupply().
+ ///
+ /// It is useful for multiple run() calls. If this function is not
+ /// used, all the parameters given before are kept for the next
+ /// \ref run() call.
+ /// However, the underlying digraph must not be modified after this
+ /// class have been constructed, since it copies and extends the graph.
+ ///
+ /// For example,
+ /// \code
+ /// CapacityScaling cs(graph);
+ ///
+ /// // First run
+ /// cs.lowerMap(lower).upperMap(upper).costMap(cost)
+ /// .supplyMap(sup).run();
+ ///
+ /// // Run again with modified cost map (reset() is not called,
+ /// // so only the cost map have to be set again)
+ /// cost[e] += 100;
+ /// cs.costMap(cost).run();
+ ///
+ /// // Run again from scratch using reset()
+ /// // (the lower bounds will be set to zero on all arcs)
+ /// cs.reset();
+ /// cs.upperMap(capacity).costMap(cost)
+ /// .supplyMap(sup).run();
+ /// \endcode
+ ///
+ /// \return (*this)
+ CapacityScaling& reset() {
+ for (int i = 0; i != _node_num; ++i) {
+ _supply[i] = 0;
+ }
+ for (int j = 0; j != _res_arc_num; ++j) {
+ _lower[j] = 0;
+ _upper[j] = INF;
+ _cost[j] = _forward[j] ? 1 : -1;
+ }
+ _have_lower = false;
+ return *this;
+ }
+
+ /// @}
+
+ /// \name Query Functions
+ /// The results of the algorithm can be obtained using these
+ /// functions.\n
+ /// The \ref run() function must be called before using them.
+
+ /// @{
+
+ /// \brief Return the total cost of the found flow.
+ ///
+ /// This function returns the total cost of the found flow.
+ /// Its complexity is O(e).
+ ///
+ /// \note The return type of the function can be specified as a
+ /// template parameter. For example,
+ /// \code
+ /// cs.totalCost();
+ /// \endcode
+ /// It is useful if the total cost cannot be stored in the \c Cost
+ /// type of the algorithm, which is the default return type of the
+ /// function.
+ ///
+ /// \pre \ref run() must be called before using this function.
+ template
+ Number totalCost() const {
+ Number c = 0;
+ for (ArcIt a(_graph); a != INVALID; ++a) {
+ int i = _arc_idb[a];
+ c += static_cast(_res_cap[i]) *
+ (-static_cast(_cost[i]));
+ }
+ return c;
+ }
+
+#ifndef DOXYGEN
+ Cost totalCost() const {
+ return totalCost();
+ }
+#endif
+
+ /// \brief Return the flow on the given arc.
+ ///
+ /// This function returns the flow on the given arc.
+ ///
+ /// \pre \ref run() must be called before using this function.
+ Value flow(const Arc& a) const {
+ return _res_cap[_arc_idb[a]];
+ }
+
+ /// \brief Return the flow map (the primal solution).
+ ///
+ /// This function copies the flow value on each arc into the given
+ /// map. The \c Value type of the algorithm must be convertible to
+ /// the \c Value type of the map.
+ ///
+ /// \pre \ref run() must be called before using this function.
+ template
+ void flowMap(FlowMap &map) const {
+ for (ArcIt a(_graph); a != INVALID; ++a) {
+ map.set(a, _res_cap[_arc_idb[a]]);
+ }
+ }
+
+ /// \brief Return the potential (dual value) of the given node.
+ ///
+ /// This function returns the potential (dual value) of the
+ /// given node.
+ ///
+ /// \pre \ref run() must be called before using this function.
+ Cost potential(const Node& n) const {
+ return _pi[_node_id[n]];
+ }
+
+ /// \brief Return the potential map (the dual solution).
+ ///
+ /// This function copies the potential (dual value) of each node
+ /// into the given map.
+ /// The \c Cost type of the algorithm must be convertible to the
+ /// \c Value type of the map.
+ ///
+ /// \pre \ref run() must be called before using this function.
+ template
+ void potentialMap(PotentialMap &map) const {
+ for (NodeIt n(_graph); n != INVALID; ++n) {
+ map.set(n, _pi[_node_id[n]]);
+ }
+ }
+
+ /// @}
+
+ private:
+
+ // Initialize the algorithm
+ ProblemType init() {
+ if (_node_num <= 1) return INFEASIBLE;
+
+ // Check the sum of supply values
+ _sum_supply = 0;
+ for (int i = 0; i != _root; ++i) {
+ _sum_supply += _supply[i];
+ }
+ if (_sum_supply > 0) return INFEASIBLE;
+
+ // Initialize vectors
+ for (int i = 0; i != _root; ++i) {
+ _pi[i] = 0;
+ _excess[i] = _supply[i];
+ }
+
+ // Remove non-zero lower bounds
+ const Value MAX = std::numeric_limits::max();
+ int last_out;
+ if (_have_lower) {
+ for (int i = 0; i != _root; ++i) {
+ last_out = _first_out[i+1];
+ for (int j = _first_out[i]; j != last_out; ++j) {
+ if (_forward[j]) {
+ Value c = _lower[j];
+ if (c >= 0) {
+ _res_cap[j] = _upper[j] < MAX ? _upper[j] - c : INF;
+ } else {
+ _res_cap[j] = _upper[j] < MAX + c ? _upper[j] - c : INF;
+ }
+ _excess[i] -= c;
+ _excess[_target[j]] += c;
+ } else {
+ _res_cap[j] = 0;
+ }
+ }
+ }
+ } else {
+ for (int j = 0; j != _res_arc_num; ++j) {
+ _res_cap[j] = _forward[j] ? _upper[j] : 0;
+ }
+ }
+
+ // Handle negative costs
+ for (int i = 0; i != _root; ++i) {
+ last_out = _first_out[i+1] - 1;
+ for (int j = _first_out[i]; j != last_out; ++j) {
+ Value rc = _res_cap[j];
+ if (_cost[j] < 0 && rc > 0) {
+ if (rc >= MAX) return UNBOUNDED;
+ _excess[i] -= rc;
+ _excess[_target[j]] += rc;
+ _res_cap[j] = 0;
+ _res_cap[_reverse[j]] += rc;
+ }
+ }
+ }
+
+ // Handle GEQ supply type
+ if (_sum_supply < 0) {
+ _pi[_root] = 0;
+ _excess[_root] = -_sum_supply;
+ for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
+ int ra = _reverse[a];
+ _res_cap[a] = -_sum_supply + 1;
+ _res_cap[ra] = 0;
+ _cost[a] = 0;
+ _cost[ra] = 0;
+ }
+ } else {
+ _pi[_root] = 0;
+ _excess[_root] = 0;
+ for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
+ int ra = _reverse[a];
+ _res_cap[a] = 1;
+ _res_cap[ra] = 0;
+ _cost[a] = 0;
+ _cost[ra] = 0;
+ }
+ }
+
+ // Initialize delta value
+ if (_factor > 1) {
+ // With scaling
+ Value max_sup = 0, max_dem = 0;
+ for (int i = 0; i != _node_num; ++i) {
+ Value ex = _excess[i];
+ if ( ex > max_sup) max_sup = ex;
+ if (-ex > max_dem) max_dem = -ex;
+ }
+ Value max_cap = 0;
+ for (int j = 0; j != _res_arc_num; ++j) {
+ if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
+ }
+ max_sup = std::min(std::min(max_sup, max_dem), max_cap);
+ for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ;
+ } else {
+ // Without scaling
+ _delta = 1;
+ }
+
+ return OPTIMAL;
+ }
+
+ ProblemType start() {
+ // Execute the algorithm
+ ProblemType pt;
+ if (_delta > 1)
+ pt = startWithScaling();
+ else
+ pt = startWithoutScaling();
+
+ // Handle non-zero lower bounds
+ if (_have_lower) {
+ int limit = _first_out[_root];
+ for (int j = 0; j != limit; ++j) {
+ if (!_forward[j]) _res_cap[j] += _lower[j];
+ }
+ }
+
+ // Shift potentials if necessary
+ Cost pr = _pi[_root];
+ if (_sum_supply < 0 || pr > 0) {
+ for (int i = 0; i != _node_num; ++i) {
+ _pi[i] -= pr;
+ }
+ }
+
+ return pt;
+ }
+
+ // Execute the capacity scaling algorithm
+ ProblemType startWithScaling() {
+ // Perform capacity scaling phases
+ int s, t;
+ ResidualDijkstra _dijkstra(*this);
+ while (true) {
+ // Saturate all arcs not satisfying the optimality condition
+ int last_out;
+ for (int u = 0; u != _node_num; ++u) {
+ last_out = _sum_supply < 0 ?
+ _first_out[u+1] : _first_out[u+1] - 1;
+ for (int a = _first_out[u]; a != last_out; ++a) {
+ int v = _target[a];
+ Cost c = _cost[a] + _pi[u] - _pi[v];
+ Value rc = _res_cap[a];
+ if (c < 0 && rc >= _delta) {
+ _excess[u] -= rc;
+ _excess[v] += rc;
+ _res_cap[a] = 0;
+ _res_cap[_reverse[a]] += rc;
+ }
+ }
+ }
+
+ // Find excess nodes and deficit nodes
+ _excess_nodes.clear();
+ _deficit_nodes.clear();
+ for (int u = 0; u != _node_num; ++u) {
+ Value ex = _excess[u];
+ if (ex >= _delta) _excess_nodes.push_back(u);
+ if (ex <= -_delta) _deficit_nodes.push_back(u);
+ }
+ int next_node = 0, next_def_node = 0;
+
+ // Find augmenting shortest paths
+ while (next_node < int(_excess_nodes.size())) {
+ // Check deficit nodes
+ if (_delta > 1) {
+ bool delta_deficit = false;
+ for ( ; next_def_node < int(_deficit_nodes.size());
+ ++next_def_node ) {
+ if (_excess[_deficit_nodes[next_def_node]] <= -_delta) {
+ delta_deficit = true;
+ break;
+ }
+ }
+ if (!delta_deficit) break;
+ }
+
+ // Run Dijkstra in the residual network
+ s = _excess_nodes[next_node];
+ if ((t = _dijkstra.run(s, _delta)) == -1) {
+ if (_delta > 1) {
+ ++next_node;
+ continue;
+ }
+ return INFEASIBLE;
+ }
+
+ // Augment along a shortest path from s to t
+ Value d = std::min(_excess[s], -_excess[t]);
+ int u = t;
+ int a;
+ if (d > _delta) {
+ while ((a = _pred[u]) != -1) {
+ if (_res_cap[a] < d) d = _res_cap[a];
+ u = _source[a];
+ }
+ }
+ u = t;
+ while ((a = _pred[u]) != -1) {
+ _res_cap[a] -= d;
+ _res_cap[_reverse[a]] += d;
+ u = _source[a];
+ }
+ _excess[s] -= d;
+ _excess[t] += d;
+
+ if (_excess[s] < _delta) ++next_node;
+ }
+
+ if (_delta == 1) break;
+ _delta = _delta <= _factor ? 1 : _delta / _factor;
+ }
+
+ return OPTIMAL;
+ }
+
+ // Execute the successive shortest path algorithm
+ ProblemType startWithoutScaling() {
+ // Find excess nodes
+ _excess_nodes.clear();
+ for (int i = 0; i != _node_num; ++i) {
+ if (_excess[i] > 0) _excess_nodes.push_back(i);
+ }
+ if (_excess_nodes.size() == 0) return OPTIMAL;
+ int next_node = 0;
+
+ // Find shortest paths
+ int s, t;
+ ResidualDijkstra _dijkstra(*this);
+ while ( _excess[_excess_nodes[next_node]] > 0 ||
+ ++next_node < int(_excess_nodes.size()) )
+ {
+ // Run Dijkstra in the residual network
+ s = _excess_nodes[next_node];
+ if ((t = _dijkstra.run(s)) == -1) return INFEASIBLE;
+
+ // Augment along a shortest path from s to t
+ Value d = std::min(_excess[s], -_excess[t]);
+ int u = t;
+ int a;
+ if (d > 1) {
+ while ((a = _pred[u]) != -1) {
+ if (_res_cap[a] < d) d = _res_cap[a];
+ u = _source[a];
+ }
+ }
+ u = t;
+ while ((a = _pred[u]) != -1) {
+ _res_cap[a] -= d;
+ _res_cap[_reverse[a]] += d;
+ u = _source[a];
+ }
+ _excess[s] -= d;
+ _excess[t] += d;
+ }
+
+ return OPTIMAL;
+ }
+
+ }; //class CapacityScaling
+
+ ///@}
+
+} //namespace lemon
+
+#endif //LEMON_CAPACITY_SCALING_H
Index: lemon/cbc.cc
===================================================================
--- lemon/cbc.cc (revision 623)
+++ lemon/cbc.cc (revision 793)
@@ -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 623)
+++ lemon/cbc.h (revision 793)
@@ -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 735)
+++ lemon/circulation.h (revision 833)
@@ -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().
@@ -451,7 +458,8 @@
}
- /// \brief Sets the tolerance used by algorithm.
- ///
- /// Sets the tolerance used by algorithm.
+ /// \brief Sets the tolerance used by the algorithm.
+ ///
+ /// Sets the tolerance object used by the algorithm.
+ /// \return (*this)
Circulation& tolerance(const Tolerance& tolerance) {
_tol = tolerance;
@@ -461,5 +469,6 @@
/// \brief Returns a const reference to the tolerance.
///
- /// Returns a const reference to the tolerance.
+ /// Returns a const reference to the tolerance object used by
+ /// the algorithm.
const Tolerance& tolerance() const {
return _tol;
@@ -468,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 623)
+++ lemon/clp.cc (revision 793)
@@ -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 623)
+++ lemon/clp.h (revision 793)
@@ -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 627)
+++ lemon/concepts/digraph.h (revision 833)
@@ -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 704)
+++ lemon/concepts/graph.h (revision 833)
@@ -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 713)
+++ lemon/concepts/graph_components.h (revision 833)
@@ -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/heap.h
===================================================================
--- lemon/concepts/heap.h (revision 631)
+++ lemon/concepts/heap.h (revision 883)
@@ -17,11 +17,11 @@
*/
+#ifndef LEMON_CONCEPTS_HEAP_H
+#define LEMON_CONCEPTS_HEAP_H
+
///\ingroup concept
///\file
///\brief The concept of heaps.
-#ifndef LEMON_CONCEPTS_HEAP_H
-#define LEMON_CONCEPTS_HEAP_H
-
#include
#include
@@ -36,19 +36,25 @@
/// \brief The heap concept.
///
- /// Concept class describing the main interface of heaps. A \e heap
- /// is a data structure for storing items with specified values called
- /// \e priorities in such a way that finding the item with minimum
- /// priority is efficient. In a heap one can change the priority of an
- /// item, add or erase an item, etc.
+ /// This concept class describes the main interface of heaps.
+ /// The various \ref heaps "heap structures" are efficient
+ /// implementations of the abstract data type \e priority \e queue.
+ /// They store items with specified values called \e priorities
+ /// in such a way that finding and removing the item with minimum
+ /// priority are efficient. The basic operations are adding and
+ /// erasing items, changing the priority of an item, etc.
///
- /// \tparam PR Type of the priority of the items.
- /// \tparam IM A read and writable item map with int values, used
+ /// Heaps are crucial in several algorithms, such as Dijkstra and Prim.
+ /// Any class that conforms to this concept can be used easily in such
+ /// algorithms.
+ ///
+ /// \tparam PR Type of the priorities of the items.
+ /// \tparam IM A read-writable item map with \c int values, used
/// internally to handle the cross references.
- /// \tparam Comp A functor class for the ordering of the priorities.
+ /// \tparam CMP A functor class for comparing the priorities.
/// The default is \c std::less.
#ifdef DOXYGEN
- template >
-#else
- template
+ template
+#else
+ template >
#endif
class Heap {
@@ -65,7 +71,6 @@
///
/// Each item has a state associated to it. It can be "in heap",
- /// "pre heap" or "post heap". The later two are indifferent
- /// from the point of view of the heap, but may be useful for
- /// the user.
+ /// "pre-heap" or "post-heap". The latter two are indifferent from the
+ /// heap's point of view, but may be useful to the user.
///
/// The item-int map must be initialized in such way that it assigns
@@ -73,99 +78,148 @@
enum State {
IN_HEAP = 0, ///< = 0. The "in heap" state constant.
- PRE_HEAP = -1, ///< = -1. The "pre heap" state constant.
- POST_HEAP = -2 ///< = -2. The "post heap" state constant.
+ PRE_HEAP = -1, ///< = -1. The "pre-heap" state constant.
+ POST_HEAP = -2 ///< = -2. The "post-heap" state constant.
};
- /// \brief The constructor.
- ///
- /// The constructor.
+ /// \brief Constructor.
+ ///
+ /// Constructor.
/// \param map A map that assigns \c int values to keys of type
/// \c Item. It is used internally by the heap implementations to
/// handle the cross references. The assigned value must be
- /// \c PRE_HEAP (-1) for every item.
+ /// \c PRE_HEAP (-1) for each item.
+#ifdef DOXYGEN
explicit Heap(ItemIntMap &map) {}
+#else
+ explicit Heap(ItemIntMap&) {}
+#endif
+
+ /// \brief Constructor.
+ ///
+ /// Constructor.
+ /// \param map A map that assigns \c int values to keys of type
+ /// \c Item. It is used internally by the heap implementations to
+ /// handle the cross references. The assigned value must be
+ /// \c PRE_HEAP (-1) for each item.
+ /// \param comp The function object used for comparing the priorities.
+#ifdef DOXYGEN
+ explicit Heap(ItemIntMap &map, const CMP &comp) {}
+#else
+ explicit Heap(ItemIntMap&, const CMP&) {}
+#endif
/// \brief The number of items stored in the heap.
///
- /// Returns the number of items stored in the heap.
+ /// This function returns the number of items stored in the heap.
int size() const { return 0; }
- /// \brief Checks if the heap is empty.
- ///
- /// Returns \c true if the heap is empty.
+ /// \brief Check if the heap is empty.
+ ///
+ /// This function returns \c true if the heap is empty.
bool empty() const { return false; }
- /// \brief Makes the heap empty.
- ///
- /// Makes the heap empty.
- void clear();
-
- /// \brief Inserts an item into the heap with the given priority.
- ///
- /// Inserts the given item into the heap with the given priority.
+ /// \brief Make the heap empty.
+ ///
+ /// This functon makes the heap empty.
+ /// It does not change the cross reference map. If you want to reuse
+ /// a heap that is not surely empty, you should first clear it and
+ /// then you should set the cross reference map to \c PRE_HEAP
+ /// for each item.
+ void clear() {}
+
+ /// \brief Insert an item into the heap with the given priority.
+ ///
+ /// This function inserts the given item into the heap with the
+ /// given priority.
/// \param i The item to insert.
/// \param p The priority of the item.
+ /// \pre \e i must not be stored in the heap.
+#ifdef DOXYGEN
void push(const Item &i, const Prio &p) {}
-
- /// \brief Returns the item having minimum priority.
- ///
- /// Returns the item having minimum priority.
+#else
+ void push(const Item&, const Prio&) {}
+#endif
+
+ /// \brief Return the item having minimum priority.
+ ///
+ /// This function returns the item having minimum priority.
/// \pre The heap must be non-empty.
- Item top() const {}
+ Item top() const { return Item(); }
/// \brief The minimum priority.
///
- /// Returns the minimum priority.
+ /// This function returns the minimum priority.
/// \pre The heap must be non-empty.
- Prio prio() const {}
-
- /// \brief Removes the item having minimum priority.
- ///
- /// Removes the item having minimum priority.
+ Prio prio() const { return Prio(); }
+
+ /// \brief Remove the item having minimum priority.
+ ///
+ /// This function removes the item having minimum priority.
/// \pre The heap must be non-empty.
void pop() {}
- /// \brief Removes an item from the heap.
- ///
- /// Removes the given item from the heap if it is already stored.
+ /// \brief Remove the given item from the heap.
+ ///
+ /// This function removes the given item from the heap if it is
+ /// already stored.
/// \param i The item to delete.
+ /// \pre \e i must be in the heap.
+#ifdef DOXYGEN
void erase(const Item &i) {}
-
- /// \brief The priority of an item.
- ///
- /// Returns the priority of the given item.
- /// \param i The item.
- /// \pre \c i must be in the heap.
+#else
+ void erase(const Item&) {}
+#endif
+
+ /// \brief The priority of the given item.
+ ///
+ /// This function returns the priority of the given item.
+ /// \param i The item.
+ /// \pre \e i must be in the heap.
+#ifdef DOXYGEN
Prio operator[](const Item &i) const {}
-
- /// \brief Sets the priority of an item or inserts it, if it is
+#else
+ Prio operator[](const Item&) const { return Prio(); }
+#endif
+
+ /// \brief Set the priority of an item or insert it, if it is
/// not stored in the heap.
///
/// This method sets the priority of the given item if it is
- /// already stored in the heap.
- /// Otherwise it inserts the given item with the given priority.
+ /// already stored in the heap. Otherwise it inserts the given
+ /// item into the heap with the given priority.
///
/// \param i The item.
/// \param p The priority.
+#ifdef DOXYGEN
void set(const Item &i, const Prio &p) {}
-
- /// \brief Decreases the priority of an item to the given value.
- ///
- /// Decreases the priority of an item to the given value.
+#else
+ void set(const Item&, const Prio&) {}
+#endif
+
+ /// \brief Decrease the priority of an item to the given value.
+ ///
+ /// This function decreases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
- /// \pre \c i must be stored in the heap with priority at least \c p.
+ /// \pre \e i must be stored in the heap with priority at least \e p.
+#ifdef DOXYGEN
void decrease(const Item &i, const Prio &p) {}
-
- /// \brief Increases the priority of an item to the given value.
- ///
- /// Increases the priority of an item to the given value.
+#else
+ void decrease(const Item&, const Prio&) {}
+#endif
+
+ /// \brief Increase the priority of an item to the given value.
+ ///
+ /// This function increases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
- /// \pre \c i must be stored in the heap with priority at most \c p.
+ /// \pre \e i must be stored in the heap with priority at most \e p.
+#ifdef DOXYGEN
void increase(const Item &i, const Prio &p) {}
-
- /// \brief Returns if an item is in, has already been in, or has
- /// never been in the heap.
+#else
+ void increase(const Item&, const Prio&) {}
+#endif
+
+ /// \brief Return the state of an item.
///
/// This method returns \c PRE_HEAP if the given item has never
@@ -175,14 +229,22 @@
/// to the heap again.
/// \param i The item.
+#ifdef DOXYGEN
State state(const Item &i) const {}
-
- /// \brief Sets the state of an item in the heap.
- ///
- /// Sets the state of the given item in the heap. It can be used
- /// to manually clear the heap when it is important to achive the
- /// better time complexity.
+#else
+ State state(const Item&) const { return PRE_HEAP; }
+#endif
+
+ /// \brief Set the state of an item in the heap.
+ ///
+ /// This function sets the state of the given item in the heap.
+ /// It can be used to manually clear the heap when it is important
+ /// to achive better time complexity.
/// \param i The item.
/// \param st The state. It should not be \c IN_HEAP.
+#ifdef DOXYGEN
void state(const Item& i, State st) {}
+#else
+ void state(const Item&, State) {}
+#endif
Index: lemon/concepts/path.h
===================================================================
--- lemon/concepts/path.h (revision 606)
+++ lemon/concepts/path.h (revision 832)
@@ -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/cost_scaling.h
===================================================================
--- lemon/cost_scaling.h (revision 887)
+++ lemon/cost_scaling.h (revision 887)
@@ -0,0 +1,1170 @@
+/* -*- 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_COST_SCALING_H
+#define LEMON_COST_SCALING_H
+
+/// \ingroup min_cost_flow_algs
+/// \file
+/// \brief Cost scaling algorithm for finding a minimum cost flow.
+
+#include
+#include
+#include
+
+#include
+#include
+#include
+#include
+#include
+#include
+
+namespace lemon {
+
+ /// \brief Default traits class of CostScaling algorithm.
+ ///
+ /// Default traits class of CostScaling algorithm.
+ /// \tparam GR Digraph type.
+ /// \tparam V The number type used for flow amounts, capacity bounds
+ /// and supply values. By default it is \c int.
+ /// \tparam C The number type used for costs and potentials.
+ /// By default it is the same as \c V.
+#ifdef DOXYGEN
+ template
+#else
+ template < typename GR, typename V = int, typename C = V,
+ bool integer = std::numeric_limits::is_integer >
+#endif
+ struct CostScalingDefaultTraits
+ {
+ /// The type of the digraph
+ typedef GR Digraph;
+ /// The type of the flow amounts, capacity bounds and supply values
+ typedef V Value;
+ /// The type of the arc costs
+ typedef C Cost;
+
+ /// \brief The large cost type used for internal computations
+ ///
+ /// The large cost type used for internal computations.
+ /// It is \c long \c long if the \c Cost type is integer,
+ /// otherwise it is \c double.
+ /// \c Cost must be convertible to \c LargeCost.
+ typedef double LargeCost;
+ };
+
+ // Default traits class for integer cost types
+ template
+ struct CostScalingDefaultTraits
+ {
+ typedef GR Digraph;
+ typedef V Value;
+ typedef C Cost;
+#ifdef LEMON_HAVE_LONG_LONG
+ typedef long long LargeCost;
+#else
+ typedef long LargeCost;
+#endif
+ };
+
+
+ /// \addtogroup min_cost_flow_algs
+ /// @{
+
+ /// \brief Implementation of the Cost Scaling algorithm for
+ /// finding a \ref min_cost_flow "minimum cost flow".
+ ///
+ /// \ref CostScaling implements a cost scaling algorithm that performs
+ /// push/augment and relabel operations for finding a \ref min_cost_flow
+ /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
+ /// \ref goldberg97efficient, \ref bunnagel98efficient.
+ /// It is a highly efficient primal-dual solution method, which
+ /// can be viewed as the generalization of the \ref Preflow
+ /// "preflow push-relabel" algorithm for the maximum flow problem.
+ ///
+ /// Most of the parameters of the problem (except for the digraph)
+ /// can be given using separate functions, and the algorithm can be
+ /// executed using the \ref run() function. If some parameters are not
+ /// specified, then default values will be used.
+ ///
+ /// \tparam GR The digraph type the algorithm runs on.
+ /// \tparam V The number type used for flow amounts, capacity bounds
+ /// and supply values in the algorithm. By default it is \c int.
+ /// \tparam C The number type used for costs and potentials in the
+ /// algorithm. By default it is the same as \c V.
+ ///
+ /// \warning Both number types must be signed and all input data must
+ /// be integer.
+ /// \warning This algorithm does not support negative costs for such
+ /// arcs that have infinite upper bound.
+ ///
+ /// \note %CostScaling provides three different internal methods,
+ /// from which the most efficient one is used by default.
+ /// For more information, see \ref Method.
+#ifdef DOXYGEN
+ template
+#else
+ template < typename GR, typename V = int, typename C = V,
+ typename TR = CostScalingDefaultTraits >
+#endif
+ class CostScaling
+ {
+ public:
+
+ /// The type of the digraph
+ typedef typename TR::Digraph Digraph;
+ /// The type of the flow amounts, capacity bounds and supply values
+ typedef typename TR::Value Value;
+ /// The type of the arc costs
+ typedef typename TR::Cost Cost;
+
+ /// \brief The large cost type
+ ///
+ /// The large cost type used for internal computations.
+ /// Using the \ref CostScalingDefaultTraits "default traits class",
+ /// it is \c long \c long if the \c Cost type is integer,
+ /// otherwise it is \c double.
+ typedef typename TR::LargeCost LargeCost;
+
+ /// The \ref CostScalingDefaultTraits "traits class" of the algorithm
+ typedef TR Traits;
+
+ public:
+
+ /// \brief Problem type constants for the \c run() function.
+ ///
+ /// Enum type containing the problem type constants that can be
+ /// returned by the \ref run() function of the algorithm.
+ enum ProblemType {
+ /// The problem has no feasible solution (flow).
+ INFEASIBLE,
+ /// The problem has optimal solution (i.e. it is feasible and
+ /// bounded), and the algorithm has found optimal flow and node
+ /// potentials (primal and dual solutions).
+ OPTIMAL,
+ /// The digraph contains an arc of negative cost and infinite
+ /// upper bound. It means that the objective function is unbounded
+ /// on that arc, however, note that it could actually be bounded
+ /// over the feasible flows, but this algroithm cannot handle
+ /// these cases.
+ UNBOUNDED
+ };
+
+ /// \brief Constants for selecting the internal method.
+ ///
+ /// Enum type containing constants for selecting the internal method
+ /// for the \ref run() function.
+ ///
+ /// \ref CostScaling provides three internal methods that differ mainly
+ /// in their base operations, which are used in conjunction with the
+ /// relabel operation.
+ /// By default, the so called \ref PARTIAL_AUGMENT
+ /// "Partial Augment-Relabel" method is used, which proved to be
+ /// the most efficient and the most robust on various test inputs.
+ /// However, the other methods can be selected using the \ref run()
+ /// function with the proper parameter.
+ enum Method {
+ /// Local push operations are used, i.e. flow is moved only on one
+ /// admissible arc at once.
+ PUSH,
+ /// Augment operations are used, i.e. flow is moved on admissible
+ /// paths from a node with excess to a node with deficit.
+ AUGMENT,
+ /// Partial augment operations are used, i.e. flow is moved on
+ /// admissible paths started from a node with excess, but the
+ /// lengths of these paths are limited. This method can be viewed
+ /// as a combined version of the previous two operations.
+ PARTIAL_AUGMENT
+ };
+
+ private:
+
+ TEMPLATE_DIGRAPH_TYPEDEFS(GR);
+
+ typedef std::vector IntVector;
+ typedef std::vector BoolVector;
+ typedef std::vector ValueVector;
+ typedef std::vector CostVector;
+ typedef std::vector LargeCostVector;
+
+ private:
+
+ template
+ class StaticVectorMap {
+ public:
+ typedef KT Key;
+ typedef VT Value;
+
+ StaticVectorMap(std::vector& v) : _v(v) {}
+
+ const Value& operator[](const Key& key) const {
+ return _v[StaticDigraph::id(key)];
+ }
+
+ Value& operator[](const Key& key) {
+ return _v[StaticDigraph::id(key)];
+ }
+
+ void set(const Key& key, const Value& val) {
+ _v[StaticDigraph::id(key)] = val;
+ }
+
+ private:
+ std::vector& _v;
+ };
+
+ typedef StaticVectorMap LargeCostNodeMap;
+ typedef StaticVectorMap LargeCostArcMap;
+
+ private:
+
+ // Data related to the underlying digraph
+ const GR &_graph;
+ int _node_num;
+ int _arc_num;
+ int _res_node_num;
+ int _res_arc_num;
+ int _root;
+
+ // Parameters of the problem
+ bool _have_lower;
+ Value _sum_supply;
+
+ // Data structures for storing the digraph
+ IntNodeMap _node_id;
+ IntArcMap _arc_idf;
+ IntArcMap _arc_idb;
+ IntVector _first_out;
+ BoolVector _forward;
+ IntVector _source;
+ IntVector _target;
+ IntVector _reverse;
+
+ // Node and arc data
+ ValueVector _lower;
+ ValueVector _upper;
+ CostVector _scost;
+ ValueVector _supply;
+
+ ValueVector _res_cap;
+ LargeCostVector _cost;
+ LargeCostVector _pi;
+ ValueVector _excess;
+ IntVector _next_out;
+ std::deque _active_nodes;
+
+ // Data for scaling
+ LargeCost _epsilon;
+ int _alpha;
+
+ // Data for a StaticDigraph structure
+ typedef std::pair IntPair;
+ StaticDigraph _sgr;
+ std::vector _arc_vec;
+ std::vector _cost_vec;
+ LargeCostArcMap _cost_map;
+ LargeCostNodeMap _pi_map;
+
+ public:
+
+ /// \brief Constant for infinite upper bounds (capacities).
+ ///
+ /// Constant for infinite upper bounds (capacities).
+ /// It is \c std::numeric_limits::infinity() if available,
+ /// \c std::numeric_limits::max() otherwise.
+ const Value INF;
+
+ public:
+
+ /// \name Named Template Parameters
+ /// @{
+
+ template
+ struct SetLargeCostTraits : public Traits {
+ typedef T LargeCost;
+ };
+
+ /// \brief \ref named-templ-param "Named parameter" for setting
+ /// \c LargeCost type.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting \c LargeCost
+ /// type, which is used for internal computations in the algorithm.
+ /// \c Cost must be convertible to \c LargeCost.
+ template
+ struct SetLargeCost
+ : public CostScaling > {
+ typedef CostScaling