Index: .hgignore
===================================================================
--- .hgignore (revision 866)
+++ .hgignore (revision 563)
@@ -23,5 +23,4 @@
lemon/stamp-h2
doc/Doxyfile
-doc/references.dox
cmake/version.cmake
.dirstamp
Index: gtags
===================================================================
--- .hgtags (revision 898)
+++ (revision )
@@ -1,2 +1,0 @@
-3ed8f7c8bed8f51aecdc8395aa11af2f1fa12d9f r1.2
-ffc2d2559fc916e90c3f000582a2d4761d229d44 r1.2.1
Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt (revision 914)
+++ CMakeLists.txt (revision 904)
@@ -52,5 +52,5 @@
ELSE()
IF(CMAKE_COMPILER_IS_GNUCXX)
- SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
+ SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
@@ -115,6 +115,4 @@
SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
-INCLUDE(FindPythonInterp)
-
ENABLE_TESTING()
Index: INSTALL
===================================================================
--- INSTALL (revision 824)
+++ INSTALL (revision 568)
@@ -174,24 +174,2 @@
Disable COIN-OR support.
-
-
-Makefile Variables
-==================
-
-Some Makefile variables are reserved by the GNU Coding Standards for
-the use of the "user" - the person building the package. For instance,
-CXX and CXXFLAGS are such variables, and have the same meaning as
-explained in the previous section. These variables can be set on the
-command line when invoking `make' like this:
-`make [VARIABLE=VALUE]...'
-
-WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us
-to hold several compiler flags related to warnings. Its default value
-can be overridden when invoking `make'. For example to disable all
-warning flags use `make WARNINGCXXFLAGS='.
-
-In order to turn off a single flag from the default set of warning
-flags, you can use the CXXFLAGS variable, since this is passed after
-WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is
-used by default when g++ is detected) you can use
-`make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.
Index: LICENSE
===================================================================
--- LICENSE (revision 880)
+++ LICENSE (revision 553)
@@ -2,5 +2,5 @@
copyright/license.
-Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi
+Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi
Kutatocsoport (Egervary Combinatorial Optimization Research Group,
EGRES).
Index: Makefile.am
===================================================================
--- Makefile.am (revision 793)
+++ Makefile.am (revision 752)
@@ -45,5 +45,4 @@
include doc/Makefile.am
include tools/Makefile.am
-include scripts/Makefile.am
DIST_SUBDIRS = demo
Index: NEWS
===================================================================
--- NEWS (revision 897)
+++ NEWS (revision 665)
@@ -1,94 +1,2 @@
-2010-10-21 Version 1.2.1 released
-
- Bugfix release.
-
- #366: Fix Pred[Matrix]MapPath::empty()
- #371: Bug fix in (di)graphCopy()
- The target graph is cleared before adding nodes and arcs/edges.
-
- #364: Add missing UndirectedTags
- #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
- #372: Fix a critical bug in preflow
-
-2010-03-19 Version 1.2 released
-
- This is major feature release
-
- * New algorithms
- * Bellman-Ford algorithm (#51)
- * Minimum mean cycle algorithms (#179)
- * Karp, Hartman-Orlin and Howard algorithms
- * New minimum cost flow algorithms (#180)
- * Cost Scaling algorithms
- * Capacity Scaling algorithm
- * Cycle-Canceling algorithms
- * Planarity related algorithms (#62)
- * Planarity checking algorithm
- * Planar embedding algorithm
- * Schnyder's planar drawing algorithm
- * Coloring planar graphs with five or six colors
- * Fractional matching algorithms (#314)
- * New data structures
- * StaticDigraph structure (#68)
- * Several new priority queue structures (#50, #301)
- * Fibonacci, Radix, Bucket, Pairing, Binomial
- D-ary and fourary heaps (#301)
- * Iterable map structures (#73)
- * Other new tools and functionality
- * Map utility functions (#320)
- * Reserve functions are added to ListGraph and SmartGraph (#311)
- * A resize() function is added to HypercubeGraph (#311)
- * A count() function is added to CrossRefMap (#302)
- * Support for multiple targets in Suurballe using fullInit() (#181)
- * Traits class and named parameters for Suurballe (#323)
- * Separate reset() and resetParams() functions in NetworkSimplex
- to handle graph changes (#327)
- * tolerance() functions are added to HaoOrlin (#306)
- * Implementation improvements
- * Improvements in weighted matching algorithms (#314)
- * Jumpstart initialization
- * ArcIt iteration is based on out-arc lists instead of in-arc lists
- in ListDigraph (#311)
- * Faster add row operation in CbcMip (#203)
- * Better implementation for split() in ListDigraph (#311)
- * ArgParser can also throw exception instead of exit(1) (#332)
- * Miscellaneous
- * A simple interactive bootstrap script
- * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,
- #316,#319)
- * BibTeX references in the doc (#184)
- * Optionally use valgrind when running tests
- * Also check ReferenceMapTag in concept checks (#312)
- * dimacs-solver uses long long type by default.
- * Several bugfixes (compared to release 1.1):
- #295: Suppress MSVC warnings using pragmas
- ----: Various CMAKE related improvements
- * Remove duplications from doc/CMakeLists.txt
- * Rename documentation install folder from 'docs' to 'html'
- * Add tools/CMakeLists.txt to the tarball
- * Generate and install LEMONConfig.cmake
- * Change the label of the html project in Visual Studio
- * Fix the check for the 'long long' type
- * Put the version string into config.h
- * Minor CMake improvements
- * Set the version to 'hg-tip' if everything fails
- #311: Add missing 'explicit' keywords
- #302: Fix the implementation and doc of CrossRefMap
- #308: Remove duplicate list_graph.h entry from source list
- #307: Bugfix in Preflow and Circulation
- #305: Bugfix and extension in the rename script
- #312: Also check ReferenceMapTag in concept checks
- #250: Bugfix in pathSource() and pathTarget()
- #321: Use pathCopy(from,to) instead of copyPath(to,from)
- #322: Distribure LEMONConfig.cmake.in
- #330: Bug fix in map_extender.h
- #336: Fix the date field comment of graphToEps() output
- #323: Bug fix in Suurballe
- #335: Fix clear() function in ExtendFindEnum
- #337: Use void* as the LPX object pointer
- #317: Fix (and improve) error message in mip_test.cc
- Remove unnecessary OsiCbc dependency
- #356: Allow multiple executions of weighted matching algorithms (#356)
-
2009-05-13 Version 1.1 released
@@ -165,5 +73,5 @@
----: Add missing unistd.h include to time_measure.h
#204: Compilation bug fixed in graph_to_eps.h with VS2005
- #214,#215: windows.h should never be included by LEMON headers
+ #214,#215: windows.h should never be included by lemon headers
#230: Build systems check the availability of 'long long' type
#229: Default implementation of Tolerance<> is used for integer types
@@ -187,50 +95,50 @@
2008-10-13 Version 1.0 released
- This is the first stable release of LEMON. Compared to the 0.x
- release series, it features a considerably smaller but more
- matured set of tools. The API has also completely revised and
- changed in several places.
+ This is the first stable release of LEMON. Compared to the 0.x
+ release series, it features a considerably smaller but more
+ matured set of tools. The API has also completely revised and
+ changed in several places.
- * The major name changes compared to the 0.x series (see the
+ * The major name changes compared to the 0.x series (see the
Migration Guide in the doc for more details)
* Graph -> Digraph, UGraph -> Graph
* Edge -> Arc, UEdge -> Edge
- * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
- * Other improvements
- * Better documentation
- * Reviewed and cleaned up codebase
- * CMake based build system (along with the autotools based one)
- * Contents of the library (ported from 0.x)
- * Algorithms
- * breadth-first search (bfs.h)
- * depth-first search (dfs.h)
- * Dijkstra's algorithm (dijkstra.h)
- * Kruskal's algorithm (kruskal.h)
- * Data structures
- * graph data structures (list_graph.h, smart_graph.h)
- * path data structures (path.h)
- * binary heap data structure (bin_heap.h)
- * union-find data structures (unionfind.h)
- * miscellaneous property maps (maps.h)
- * two dimensional vector and bounding box (dim2.h)
+ * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
+ * Other improvements
+ * Better documentation
+ * Reviewed and cleaned up codebase
+ * CMake based build system (along with the autotools based one)
+ * Contents of the library (ported from 0.x)
+ * Algorithms
+ * breadth-first search (bfs.h)
+ * depth-first search (dfs.h)
+ * Dijkstra's algorithm (dijkstra.h)
+ * Kruskal's algorithm (kruskal.h)
+ * Data structures
+ * graph data structures (list_graph.h, smart_graph.h)
+ * path data structures (path.h)
+ * binary heap data structure (bin_heap.h)
+ * union-find data structures (unionfind.h)
+ * miscellaneous property maps (maps.h)
+ * two dimensional vector and bounding box (dim2.h)
* Concepts
- * graph structure concepts (concepts/digraph.h, concepts/graph.h,
+ * graph structure concepts (concepts/digraph.h, concepts/graph.h,
concepts/graph_components.h)
- * concepts for other structures (concepts/heap.h, concepts/maps.h,
- concepts/path.h)
- * Tools
- * Mersenne twister random number generator (random.h)
- * tools for measuring cpu and wall clock time (time_measure.h)
- * tools for counting steps and events (counter.h)
- * tool for parsing command line arguments (arg_parser.h)
- * tool for visualizing graphs (graph_to_eps.h)
- * tools for reading and writing data in LEMON Graph Format
+ * concepts for other structures (concepts/heap.h, concepts/maps.h,
+ concepts/path.h)
+ * Tools
+ * Mersenne twister random number generator (random.h)
+ * tools for measuring cpu and wall clock time (time_measure.h)
+ * tools for counting steps and events (counter.h)
+ * tool for parsing command line arguments (arg_parser.h)
+ * tool for visualizing graphs (graph_to_eps.h)
+ * tools for reading and writing data in LEMON Graph Format
(lgf_reader.h, lgf_writer.h)
* tools to handle the anomalies of calculations with
- floating point numbers (tolerance.h)
+ floating point numbers (tolerance.h)
* tools to manage RGB colors (color.h)
- * Infrastructure
- * extended assertion handling (assert.h)
- * exception classes and error handling (error.h)
- * concept checking (concept_check.h)
- * commonly used mathematical constants (math.h)
+ * Infrastructure
+ * extended assertion handling (assert.h)
+ * exception classes and error handling (error.h)
+ * concept checking (concept_check.h)
+ * commonly used mathematical constants (math.h)
Index: README
===================================================================
--- README (revision 848)
+++ README (revision 658)
@@ -18,8 +18,4 @@
Copying, distribution and modification conditions and terms.
-NEWS
-
- News and version history.
-
INSTALL
@@ -38,8 +34,4 @@
Some example programs to make you easier to get familiar with LEMON.
-scripts/
-
- Scripts that make it easier to develop LEMON.
-
test/
Index: configure.ac
===================================================================
--- configure.ac (revision 908)
+++ configure.ac (revision 907)
@@ -42,5 +42,4 @@
AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
-AC_CHECK_PROG([python_found],[python],[yes],[no])
AC_CHECK_PROG([gs_found],[gs],[yes],[no])
@@ -83,19 +82,4 @@
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.
@@ -145,5 +129,4 @@
echo
echo Build additional tools........ : $enable_tools
-echo Use valgrind for tests........ : $use_valgrind
echo
echo The packace will be installed in
Index: demo/arg_parser_demo.cc
===================================================================
--- demo/arg_parser_demo.cc (revision 877)
+++ demo/arg_parser_demo.cc (revision 440)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -66,16 +66,7 @@
.other("...");
- // Throw an exception when problems occurs. The default behavior is to
- // exit(1) on these cases, but this makes Valgrind falsely warn
- // about memory leaks.
- ap.throwOnProblems();
-
// Perform the parsing process
// (in case of any error it terminates the program)
- // The try {} construct is necessary only if the ap.trowOnProblems()
- // setting is in use.
- try {
- ap.parse();
- } catch (ArgParserException &) { return 1; }
+ ap.parse();
// Check each option if it has been given and print its value
Index: doc/CMakeLists.txt
===================================================================
--- doc/CMakeLists.txt (revision 908)
+++ doc/CMakeLists.txt (revision 907)
@@ -18,5 +18,5 @@
)
-IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
+IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
@@ -29,5 +29,4 @@
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
@@ -36,8 +35,6 @@
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 908)
+++ doc/Doxyfile.in (revision 907)
@@ -98,6 +98,5 @@
"@abs_top_srcdir@/tools" \
"@abs_top_srcdir@/test/test_tools.h" \
- "@abs_top_builddir@/doc/mainpage.dox" \
- "@abs_top_builddir@/doc/references.dox"
+ "@abs_top_builddir@/doc/mainpage.dox"
INPUT_ENCODING = UTF-8
FILE_PATTERNS = *.h \
Index: doc/Makefile.am
===================================================================
--- doc/Makefile.am (revision 865)
+++ doc/Makefile.am (revision 673)
@@ -28,7 +28,5 @@
connected_components.eps \
edge_biconnected_components.eps \
- matching.eps \
node_biconnected_components.eps \
- planar.eps \
strongly_connected_components.eps
@@ -69,17 +67,5 @@
fi
-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
+html-local: $(DOC_PNG_IMAGES)
if test ${doxygen_found} = yes; then \
cd doc; \
Index: doc/groups.dox
===================================================================
--- doc/groups.dox (revision 884)
+++ doc/groups.dox (revision 663)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -227,4 +227,12 @@
/**
+@defgroup matrices Matrices
+@ingroup datas
+\brief Two dimensional data storages implemented in LEMON.
+
+This group contains two dimensional data storages implemented in LEMON.
+*/
+
+/**
@defgroup paths Path Structures
@ingroup datas
@@ -239,26 +247,5 @@
any kind of path structure.
-\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"
+\sa lemon::concepts::Path
*/
@@ -273,18 +260,4 @@
/**
-@defgroup geomdat Geometric Data Structures
-@ingroup auxdat
-\brief Geometric data structures implemented in LEMON.
-
-This group contains geometric data structures implemented in LEMON.
-
- - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
- vector with the usual operations.
- - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
- rectangular bounding box of a set of \ref lemon::dim2::Point
- "dim2::Point"'s.
-*/
-
-/**
@defgroup algs Algorithms
\brief This group contains the several algorithms
@@ -301,6 +274,5 @@
This group contains the common graph search algorithms, namely
-\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
-\ref clrs01algorithms.
+\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
*/
@@ -310,6 +282,5 @@
\brief Algorithms for finding shortest paths.
-This group contains the algorithms for finding shortest paths in digraphs
-\ref clrs01algorithms.
+This group contains the algorithms for finding shortest paths in digraphs.
- \ref Dijkstra algorithm for finding shortest paths from a source node
@@ -319,4 +290,8 @@
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.
@@ -324,13 +299,4 @@
/**
-@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
@@ -338,5 +304,5 @@
This group contains the algorithms for finding maximum flows and
-feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
+feasible circulations.
The \e maximum \e flow \e problem is to find a flow of maximum value between
@@ -352,10 +318,16 @@
\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
-\ref Preflow is an efficient implementation of Goldberg-Tarjan's
-preflow push-relabel algorithm \ref goldberg88newapproach for finding
-maximum flows. It also provides functions to query the minimum cut,
-which is the dual problem of maximum flow.
-
-\ref Circulation is a preflow push-relabel algorithm implemented directly
+LEMON contains several algorithms for solving maximum flow problems:
+- \ref EdmondsKarp Edmonds-Karp algorithm.
+- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
+- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
+- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
+
+In most cases the \ref Preflow "Preflow" algorithm provides the
+fastest method for computing a maximum flow. All implementations
+also provide functions to query the minimum cut, which is the dual
+problem of maximum flow.
+
+\ref Circulation is a preflow push-relabel algorithm implemented directly
for finding feasible circulations, which is a somewhat different problem,
but it is strongly related to maximum flow.
@@ -370,18 +342,16 @@
This group contains the algorithms for finding minimum cost flows and
-circulations \ref amo93networkflows. For more information about this
-problem and its dual solution, see \ref min_cost_flow
-"Minimum Cost Flow Problem".
+circulations. 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.
+ pivot strategies.
+ - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
+ cost scaling.
+ - \ref CapacityScaling Successive Shortest %Path algorithm with optional
+ capacity scaling.
+ - \ref CancelAndTighten The Cancel and Tighten algorithm.
+ - \ref CycleCanceling Cycle-Canceling algorithms.
In general NetworkSimplex is the most efficient implementation,
@@ -406,5 +376,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:
@@ -412,4 +382,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.
@@ -420,38 +392,25 @@
/**
-@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
-@ingroup algs
-\brief Algorithms for finding minimum mean cycles.
-
-This group contains the algorithms for finding minimum mean cycles
-\ref clrs01algorithms, \ref amo93networkflows.
-
-The \e minimum \e mean \e cycle \e problem is to find a directed cycle
-of minimum mean length (cost) in a digraph.
-The mean length of a cycle is the average length of its arcs, i.e. the
-ratio between the total length of the cycle and the number of arcs on it.
-
-This problem has an important connection to \e conservative \e length
-\e functions, too. A length function on the arcs of a digraph is called
-conservative if and only if there is no directed cycle of negative total
-length. For an arbitrary length function, the negative of the minimum
-cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
-arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
-function.
-
-LEMON contains three algorithms for solving the minimum mean cycle problem:
-- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
- \ref dasdan98minmeancycle.
-- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
- version of Karp's algorithm \ref dasdan98minmeancycle.
-- \ref HowardMmc Howard's policy iteration algorithm
- \ref dasdan98minmeancycle.
-
-In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
-most efficient one, though the best known theoretical bound on its running
-time is exponential.
-Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
-run in time O(ne) and use space O(n2+e), but the latter one is
-typically faster due to the applied early termination scheme.
+@defgroup graph_properties Connectivity and Other Graph Properties
+@ingroup algs
+\brief Algorithms for discovering the graph properties
+
+This group contains the algorithms for discovering the graph properties
+like connectivity, bipartiteness, euler property, simplicity etc.
+
+\image html edge_biconnected_components.png
+\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
+*/
+
+/**
+@defgroup planar Planarity Embedding and Drawing
+@ingroup algs
+\brief Algorithms for planarity checking, embedding and drawing
+
+This group contains the algorithms for planarity checking,
+embedding and drawing.
+
+\image html planar.png
+\image latex planar.eps "Plane graph" width=\textwidth
*/
@@ -474,4 +433,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.
@@ -481,38 +450,16 @@
Edmond's blossom shrinking algorithm for calculating maximum weighted
perfect matching in general graphs.
-- \ref MaxFractionalMatching Push-relabel algorithm for calculating
- maximum cardinality fractional matching in general graphs.
-- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
- maximum weighted fractional matching in general graphs.
-- \ref MaxWeightedPerfectFractionalMatching
- Augmenting path algorithm for calculating maximum weighted
- perfect fractional matching in general graphs.
-
-\image html matching.png
-\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
-*/
-
-/**
-@defgroup graph_properties Connectivity and Other Graph Properties
-@ingroup algs
-\brief Algorithms for discovering the graph properties
-
-This group contains the algorithms for discovering the graph properties
-like connectivity, bipartiteness, euler property, simplicity etc.
-
-\image html connected_components.png
-\image latex connected_components.eps "Connected components" width=\textwidth
-*/
-
-/**
-@defgroup planar Planarity Embedding and Drawing
-@ingroup algs
-\brief Algorithms for planarity checking, embedding and drawing
-
-This group contains the algorithms for planarity checking,
-embedding and drawing.
-
-\image html planar.png
-\image latex planar.eps "Plane graph" width=\textwidth
+
+\image html bipartite_matching.png
+\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
+*/
+
+/**
+@defgroup spantree Minimum Spanning Tree Algorithms
+@ingroup algs
+\brief Algorithms for finding minimum cost spanning trees and arborescences.
+
+This group contains the algorithms for finding minimum cost spanning
+trees and arborescences.
*/
@@ -524,4 +471,13 @@
This group contains some algorithms implemented in LEMON
in order to make it easier to implement complex algorithms.
+*/
+
+/**
+@defgroup approx Approximation Algorithms
+@ingroup algs
+\brief Approximation algorithms.
+
+This group contains the approximation and heuristic algorithms
+implemented in LEMON.
*/
@@ -536,14 +492,28 @@
/**
-@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.
-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.
+\brief Lp and Mip solver interfaces for LEMON.
+
+This group contains Lp and Mip solver interfaces for LEMON. The
+various LP solvers could be used in the same manner with this
+interface.
+*/
+
+/**
+@defgroup lp_utils Tools for Lp and Mip Solvers
+@ingroup lp_group
+\brief Helper tools to the Lp and Mip solvers.
+
+This group adds some helper tools to general optimization framework
+implemented in LEMON.
+*/
+
+/**
+@defgroup metah Metaheuristics
+@ingroup gen_opt_group
+\brief Metaheuristics for LEMON library.
+
+This group contains some metaheuristic optimization tools.
*/
@@ -618,5 +588,5 @@
/**
-@defgroup dimacs_group DIMACS Format
+@defgroup dimacs_group DIMACS format
@ingroup io_group
\brief Read and write files in DIMACS format
@@ -667,6 +637,6 @@
\brief Skeleton and concept checking classes for graph structures
-This group contains the skeletons and concept checking classes of
-graph structures.
+This group contains the skeletons and concept checking classes of LEMON's
+graph structures and helper classes used to implement these.
*/
@@ -680,4 +650,16 @@
/**
+\anchor demoprograms
+
+@defgroup demos Demo Programs
+
+Some demo programs are listed here. Their full source codes can be found in
+the \c demo subdirectory of the source tree.
+
+In order to compile them, use the make demo or the
+make check commands.
+*/
+
+/**
@defgroup tools Standalone Utility Applications
@@ -688,15 +670,3 @@
*/
-/**
-\anchor demoprograms
-
-@defgroup demos Demo Programs
-
-Some demo programs are listed here. Their full source codes can be found in
-the \c demo subdirectory of the source tree.
-
-In order to compile them, use the make demo or the
-make check commands.
-*/
-
}
Index: c/images/matching.eps
===================================================================
--- doc/images/matching.eps (revision 865)
+++ (revision )
@@ -1,130 +1,0 @@
-%!PS-Adobe-2.0 EPSF-2.0
-%%Creator: LEMON, graphToEps()
-%%CreationDate: Sun Mar 14 09:08:34 2010
-%%BoundingBox: -353 -264 559 292
-%%EndComments
-/lb { setlinewidth setrgbcolor newpath moveto
- 4 2 roll 1 index 1 index curveto stroke } bind def
-/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
-/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
-/sq { newpath 2 index 1 index add 2 index 2 index add moveto
- 2 index 1 index sub 2 index 2 index add lineto
- 2 index 1 index sub 2 index 2 index sub lineto
- 2 index 1 index add 2 index 2 index sub lineto
- closepath pop pop pop} bind def
-/di { newpath 2 index 1 index add 2 index moveto
- 2 index 2 index 2 index add lineto
- 2 index 1 index sub 2 index lineto
- 2 index 2 index 2 index sub lineto
- closepath pop pop pop} bind def
-/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
- setrgbcolor 1.1 div c fill
- } bind def
-/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
- setrgbcolor 1.1 div sq fill
- } bind def
-/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
- setrgbcolor 1.1 div di fill
- } bind def
-/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
- newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
- lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
- 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
- 5 index 5 index 5 index c fill
- setrgbcolor 1.1 div c fill
- } bind def
-/nmale {
- 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
- newpath 5 index 5 index moveto
- 5 index 4 index 1 mul 1.5 mul add
- 5 index 5 index 3 sqrt 1.5 mul mul add
- 1 index 1 index lineto
- 1 index 1 index 7 index sub moveto
- 1 index 1 index lineto
- exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
- stroke
- 5 index 5 index 5 index c fill
- setrgbcolor 1.1 div c fill
- } bind def
-/arrl 1 def
-/arrw 0.3 def
-/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
-/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
- /w exch def /len exch def
- newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
- len w sub arrl sub dx dy lrl
- arrw dy dx neg lrl
- dx arrl w add mul dy w 2 div arrw add mul sub
- dy arrl w add mul dx w 2 div arrw add mul add rlineto
- dx arrl w add mul neg dy w 2 div arrw add mul sub
- dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
- arrw dy dx neg lrl
- len w sub arrl sub neg dx dy lrl
- closepath fill } bind def
-/cshow { 2 index 2 index moveto dup stringwidth pop
- neg 2 div fosi .35 mul neg rmoveto show pop pop} def
-
-gsave
-%Arcs:
-gsave
-140.321 266.249 -327.729 150.06 0 0 0 4.99223 l
-82.1207 -238.726 -245.288 -110.743 0 0 0 4.99223 l
-336.635 -229.036 533.603 13.109 0 0 0 4.99223 l
-53.8598 -45.8071 -245.288 -110.743 0 0 0 4.99223 l
--75.5617 118.579 -327.729 150.06 0 0 0 4.99223 l
--327.729 150.06 -245.288 -110.743 1 0 0 11.9813 l
-533.603 13.109 218.184 -84.2955 0 0 0 4.99223 l
-39.87 175.035 141.163 67.2575 0 0 0 4.99223 l
-53.8598 -45.8071 -75.5617 118.579 0 0 0 4.99223 l
--102.406 -141.267 82.1207 -238.726 0 0 0 4.99223 l
-399.144 166.894 533.603 13.109 1 0 0 11.9813 l
-39.87 175.035 140.321 266.249 1 0 0 11.9813 l
-399.144 166.894 140.321 266.249 0 0 0 4.99223 l
-399.144 166.894 141.163 67.2575 0 0 0 4.99223 l
-53.8598 -45.8071 204.765 -173.77 0 0 0 4.99223 l
-82.1207 -238.726 204.765 -173.77 0 0 0 4.99223 l
-258.227 61.658 399.144 166.894 0 0 0 4.99223 l
-53.8598 -45.8071 -102.406 -141.267 1 0 0 11.9813 l
-175.073 -37.4477 141.163 67.2575 0 0 0 4.99223 l
-258.227 61.658 380 0 0 0 0 4.99223 l
-34.6739 40.8267 -75.5617 118.579 1 0 0 11.9813 l
-380 0 533.603 13.109 0 0 0 4.99223 l
-175.073 -37.4477 380 0 0 0 0 4.99223 l
-218.184 -84.2955 204.765 -173.77 0 0 0 4.99223 l
-53.8598 -45.8071 34.6739 40.8267 0 0 0 4.99223 l
-167.905 -213.988 82.1207 -238.726 1 0 0 11.9813 l
-336.635 -229.036 204.765 -173.77 1 0 0 11.9813 l
-336.635 -229.036 167.905 -213.988 0 0 0 4.99223 l
-329.08 -26.3098 218.184 -84.2955 0 0 0 4.99223 l
-39.87 175.035 -75.5617 118.579 0 0 0 4.99223 l
-53.8598 -45.8071 175.073 -37.4477 0 0 0 4.99223 l
-34.6739 40.8267 141.163 67.2575 0 0 0 4.99223 l
-258.227 61.658 141.163 67.2575 1 0 0 11.9813 l
-175.073 -37.4477 218.184 -84.2955 1 0 0 11.9813 l
-380 0 329.08 -26.3098 1 0 0 11.9813 l
-grestore
-%Nodes:
-gsave
--245.288 -110.743 14.9767 1 1 1 nc
-204.765 -173.77 14.9767 1 1 1 nc
--327.729 150.06 14.9767 1 1 1 nc
--75.5617 118.579 14.9767 1 1 1 nc
-218.184 -84.2955 14.9767 1 1 1 nc
-140.321 266.249 14.9767 1 1 1 nc
-141.163 67.2575 14.9767 1 1 1 nc
-82.1207 -238.726 14.9767 1 1 1 nc
-329.08 -26.3098 14.9767 1 1 1 nc
--102.406 -141.267 14.9767 1 1 1 nc
-533.603 13.109 14.9767 1 1 1 nc
-167.905 -213.988 14.9767 1 1 1 nc
-336.635 -229.036 14.9767 1 1 1 nc
-380 0 14.9767 1 1 1 nc
-399.144 166.894 14.9767 1 1 1 nc
-34.6739 40.8267 14.9767 1 1 1 nc
-39.87 175.035 14.9767 1 1 1 nc
-175.073 -37.4477 14.9767 1 1 1 nc
-53.8598 -45.8071 14.9767 1 1 1 nc
-258.227 61.658 14.9767 1 1 1 nc
-grestore
-grestore
-showpage
Index: c/images/planar.eps
===================================================================
--- doc/images/planar.eps (revision 827)
+++ (revision )
@@ -1,181 +1,0 @@
-%!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.in
===================================================================
--- doc/mainpage.dox.in (revision 908)
+++ doc/mainpage.dox.in (revision 907)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -22,9 +22,12 @@
\section intro Introduction
-LEMON stands for Library for Efficient Modeling
-and Optimization in Networks.
-It is a C++ template library providing efficient implementations of common
-data structures and algorithms with focus on combinatorial optimization
-tasks connected mainly with graphs and networks.
+\subsection 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.
@@ -36,21 +39,8 @@
-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
+\subsection howtoread How to read the documentation
If you would like to get to know the library, see
LEMON Tutorial.
-
-If you are interested in starting to use the library, see the Installation
-Guide.
If you know what you are looking for, then try to find it under the
Index: doc/min_cost_flow.dox
===================================================================
--- doc/min_cost_flow.dox (revision 877)
+++ doc/min_cost_flow.dox (revision 663)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -27,5 +27,5 @@
minimum total cost from a set of supply nodes to a set of demand nodes
in a network with capacity constraints (lower and upper bounds)
-and arc costs \ref amo93networkflows.
+and arc costs.
Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
@@ -79,8 +79,8 @@
- if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
- For all \f$u\in V\f$ nodes:
- - \f$\pi(u)\leq 0\f$;
+ - \f$\pi(u)<=0\f$;
- if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
then \f$\pi(u)=0\f$.
-
+
Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
@@ -120,5 +120,5 @@
\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
-It means that the total demand must be less or equal to the
+It means that the total demand must be less or equal to the
total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
positive) and all the demands have to be satisfied, but there
@@ -146,5 +146,5 @@
- if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
- For all \f$u\in V\f$ nodes:
- - \f$\pi(u)\geq 0\f$;
+ - \f$\pi(u)>=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: c/references.bib
===================================================================
--- doc/references.bib (revision 755)
+++ (revision )
@@ -1,301 +1,0 @@
-%%%%% 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 874)
+++ lemon/Makefile.am (revision 681)
@@ -58,10 +58,7 @@
lemon/arg_parser.h \
lemon/assert.h \
- lemon/bellman_ford.h \
lemon/bfs.h \
lemon/bin_heap.h \
- lemon/binomial_heap.h \
lemon/bucket_heap.h \
- lemon/capacity_scaling.h \
lemon/cbc.h \
lemon/circulation.h \
@@ -70,11 +67,8 @@
lemon/concept_check.h \
lemon/connectivity.h \
+ lemon/counter.h \
lemon/core.h \
- lemon/cost_scaling.h \
- lemon/counter.h \
lemon/cplex.h \
- lemon/cycle_canceling.h \
lemon/dfs.h \
- lemon/dheap.h \
lemon/dijkstra.h \
lemon/dim2.h \
@@ -85,5 +79,4 @@
lemon/euler.h \
lemon/fib_heap.h \
- lemon/fractional_matching.h \
lemon/full_graph.h \
lemon/glpk.h \
@@ -91,8 +84,5 @@
lemon/graph_to_eps.h \
lemon/grid_graph.h \
- lemon/hartmann_orlin_mmc.h \
- lemon/howard_mmc.h \
lemon/hypercube_graph.h \
- lemon/karp_mmc.h \
lemon/kruskal.h \
lemon/hao_orlin.h \
@@ -103,4 +93,5 @@
lemon/lp_base.h \
lemon/lp_skeleton.h \
+ lemon/list_graph.h \
lemon/maps.h \
lemon/matching.h \
@@ -109,9 +100,6 @@
lemon/nauty_reader.h \
lemon/network_simplex.h \
- lemon/pairing_heap.h \
lemon/path.h \
- lemon/planarity.h \
lemon/preflow.h \
- lemon/quad_heap.h \
lemon/radix_heap.h \
lemon/radix_sort.h \
@@ -119,5 +107,4 @@
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 877)
+++ lemon/adaptors.h (revision 656)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -361,7 +361,4 @@
/// 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.
@@ -422,5 +419,5 @@
Parent::initialize(digraph);
_node_filter = &node_filter;
- _arc_filter = &arc_filter;
+ _arc_filter = &arc_filter;
}
@@ -509,9 +506,9 @@
template
- class NodeMap
- : public SubMapExtender,
- LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> {
+ class NodeMap
+ : public SubMapExtender,
+ LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> {
typedef SubMapExtender,
- LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent;
+ LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent;
public:
@@ -536,7 +533,7 @@
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
- LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> {
+ LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> {
typedef SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> Parent;
@@ -583,5 +580,5 @@
Parent::initialize(digraph);
_node_filter = &node_filter;
- _arc_filter = &arc_filter;
+ _arc_filter = &arc_filter;
}
@@ -652,8 +649,8 @@
template
- class NodeMap
+ class NodeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent;
@@ -679,5 +676,5 @@
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> {
@@ -722,6 +719,4 @@
/// 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.
@@ -1022,8 +1017,8 @@
template
- class NodeMap
+ class NodeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent;
@@ -1049,8 +1044,8 @@
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent;
@@ -1076,8 +1071,8 @@
template
- class EdgeMap
+ class EdgeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent;
@@ -1118,6 +1113,6 @@
NF* _node_filter;
EF* _edge_filter;
- SubGraphBase()
- : Parent(), _node_filter(0), _edge_filter(0) { }
+ SubGraphBase()
+ : Parent(), _node_filter(0), _edge_filter(0) { }
void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
@@ -1220,8 +1215,8 @@
template
- class NodeMap
+ class NodeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent;
@@ -1247,8 +1242,8 @@
template
- class ArcMap
+ class ArcMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> {
- typedef SubMapExtender,
+ typedef SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent;
@@ -1274,9 +1269,9 @@
template
- class EdgeMap
+ class EdgeMap
: public SubMapExtender,
LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> {
- typedef SubMapExtender,
- LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent;
+ typedef SubMapExtender,
+ LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent;
public:
@@ -1319,6 +1314,4 @@
/// 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.
@@ -1478,6 +1471,4 @@
/// 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.
@@ -1505,5 +1496,5 @@
#endif
typedef DigraphAdaptorExtender<
- SubDigraphBase >,
+ SubDigraphBase >,
true> > Parent;
@@ -1526,5 +1517,5 @@
/// Creates a subgraph for the given digraph or graph with the
/// given node filter map.
- FilterNodes(GR& graph, NF& node_filter)
+ FilterNodes(GR& graph, NF& node_filter)
: Parent(), const_true_map()
{
@@ -1564,9 +1555,9 @@
typename enable_if >::type> :
public GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
true> > {
typedef GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
true> > Parent;
@@ -1628,6 +1619,4 @@
/// 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.
@@ -1654,5 +1643,5 @@
#endif
typedef DigraphAdaptorExtender<
- SubDigraphBase >,
+ SubDigraphBase >,
AF, false> > Parent;
@@ -1740,6 +1729,4 @@
/// 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.
@@ -1762,9 +1749,9 @@
class FilterEdges :
public GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
EF, false> > {
#endif
typedef GraphAdaptorExtender<
- SubGraphBase >,
+ SubGraphBase >,
EF, false> > Parent;
@@ -1791,5 +1778,5 @@
/// Creates a subgraph for the given graph with the given edge
/// filter map.
- FilterEdges(GR& graph, EF& edge_filter)
+ FilterEdges(GR& graph, EF& edge_filter)
: Parent(), const_true_map() {
Parent::initialize(graph, const_true_map, edge_filter);
@@ -1859,5 +1846,5 @@
bool _forward;
- Arc(const Edge& edge, bool forward)
+ Arc(const Edge& edge, bool forward)
: _edge(edge), _forward(forward) {}
@@ -2099,5 +2086,5 @@
ArcMapBase(const UndirectorBase& adaptor, const V& value)
- : _forward(*adaptor._digraph, value),
+ : _forward(*adaptor._digraph, value),
_backward(*adaptor._digraph, value) {}
@@ -2217,5 +2204,5 @@
typedef typename ItemSetTraits::ItemNotifier EdgeNotifier;
EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
-
+
typedef EdgeNotifier ArcNotifier;
ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
@@ -2245,7 +2232,4 @@
/// by adding or removing nodes or edges, unless the \c GR template
/// parameter is set to be \c const.
- ///
- /// This class provides item counting in the same time as the adapted
- /// digraph structure.
///
/// \tparam DGR The type of the adapted digraph.
@@ -2551,7 +2535,4 @@
/// 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.
@@ -2698,6 +2679,4 @@
/// This class conforms to the \ref concepts::Digraph "Digraph" concept.
///
- /// This class provides only linear time counting for nodes and arcs.
- ///
/// \tparam DGR The type of the adapted digraph.
/// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -2729,5 +2708,5 @@
typename FM = CM,
typename TL = Tolerance >
- class ResidualDigraph
+ class ResidualDigraph
: public SubDigraph<
Undirector,
@@ -2786,5 +2765,5 @@
ResidualDigraph(const DGR& digraph, const CM& capacity,
FM& flow, const TL& tolerance = Tolerance())
- : Parent(), _capacity(&capacity), _flow(&flow),
+ : Parent(), _capacity(&capacity), _flow(&flow),
_graph(digraph), _node_filter(),
_forward_filter(capacity, flow, tolerance),
@@ -2868,5 +2847,5 @@
/// Constructor
- ResidualCapacity(const ResidualDigraph& adaptor)
+ ResidualCapacity(const ResidualDigraph& adaptor)
: _adaptor(&adaptor) {}
@@ -3347,7 +3326,4 @@
/// 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.
@@ -3448,5 +3424,5 @@
/// to get a node map of the split digraph.
/// Its value type is inherited from the first node map type (\c IN).
- /// \tparam IN The type of the node map for the in-nodes.
+ /// \tparam IN The type of the node map for the in-nodes.
/// \tparam OUT The type of the node map for the out-nodes.
template
Index: lemon/arg_parser.cc
===================================================================
--- lemon/arg_parser.cc (revision 877)
+++ lemon/arg_parser.cc (revision 440)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -21,21 +21,12 @@
namespace lemon {
- void ArgParser::_terminate(ArgParserException::Reason reason) const
- {
- if(_exit_on_problems)
- exit(1);
- else throw(ArgParserException(reason));
- }
-
-
void ArgParser::_showHelp(void *p)
{
(static_cast(p))->showHelp();
- (static_cast(p))->_terminate(ArgParserException::HELP);
+ exit(1);
}
ArgParser::ArgParser(int argc, const char * const *argv)
- :_argc(argc), _argv(argv), _command_name(argv[0]),
- _exit_on_problems(true) {
+ :_argc(argc), _argv(argv), _command_name(argv[0]) {
funcOption("-help","Print a short help message",_showHelp,this);
synonym("help","-help");
@@ -352,5 +343,5 @@
i!=_others_help.end();++i) showHelp(i);
for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i);
- _terminate(ArgParserException::HELP);
+ exit(1);
}
@@ -361,5 +352,5 @@
std::cerr << "\nType '" << _command_name <<
" --help' to obtain a short summary on the usage.\n\n";
- _terminate(ArgParserException::UNKNOWN_OPT);
+ exit(1);
}
@@ -424,5 +415,5 @@
std::cerr << "\nType '" << _command_name <<
" --help' to obtain a short summary on the usage.\n\n";
- _terminate(ArgParserException::INVALID_OPT);
+ exit(1);
}
}
Index: lemon/arg_parser.h
===================================================================
--- lemon/arg_parser.h (revision 880)
+++ lemon/arg_parser.h (revision 440)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -34,49 +34,4 @@
namespace lemon {
-
- ///Exception used by ArgParser
-
- ///Exception used by ArgParser.
- ///
- class ArgParserException : public Exception {
- public:
- /// Reasons for failure
-
- /// Reasons for failure.
- ///
- enum Reason {
- HELP, ///< --help option was given.
- UNKNOWN_OPT, ///< Unknown option was given.
- INVALID_OPT ///< Invalid combination of options.
- };
-
- private:
- Reason _reason;
-
- public:
- ///Constructor
- ArgParserException(Reason r) throw() : _reason(r) {}
- ///Virtual destructor
- virtual ~ArgParserException() throw() {}
- ///A short description of the exception
- virtual const char* what() const throw() {
- switch(_reason)
- {
- case HELP:
- return "lemon::ArgParseException: ask for help";
- break;
- case UNKNOWN_OPT:
- return "lemon::ArgParseException: unknown option";
- break;
- case INVALID_OPT:
- return "lemon::ArgParseException: invalid combination of options";
- break;
- }
- return "";
- }
- ///Return the reason for the failure
- Reason reason() const {return _reason; }
- };
-
///Command line arguments parser
@@ -162,8 +117,4 @@
void (*func)(void *),void *data);
- bool _exit_on_problems;
-
- void _terminate(ArgParserException::Reason reason) const;
-
public:
@@ -430,9 +381,4 @@
const std::vector &files() const { return _file_args; }
- ///Throw instead of exit in case of problems
- void throwOnProblems()
- {
- _exit_on_problems=false;
- }
};
}
Index: mon/bellman_ford.h
===================================================================
--- lemon/bellman_ford.h (revision 881)
+++ (revision )
@@ -1,1115 +1,0 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library.
- *
- * Copyright (C) 2003-2010
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_BELLMAN_FORD_H
-#define LEMON_BELLMAN_FORD_H
-
-/// \ingroup shortest_path
-/// \file
-/// \brief Bellman-Ford algorithm.
-
-#include
-#include
-#include
-#include
-#include
-#include
-
-#include
-
-namespace lemon {
-
- /// \brief Default OperationTraits for the BellmanFord algorithm class.
- ///
- /// This operation traits class defines all computational operations
- /// and constants that are used in the Bellman-Ford algorithm.
- /// The default implementation is based on the \c numeric_limits class.
- /// If the numeric type does not have infinity value, then the maximum
- /// value is used as extremal infinity value.
- template <
- typename V,
- bool has_inf = std::numeric_limits::has_infinity>
- struct BellmanFordDefaultOperationTraits {
- /// \e
- typedef V Value;
- /// \brief Gives back the zero value of the type.
- static Value zero() {
- return static_cast(0);
- }
- /// \brief Gives back the positive infinity value of the type.
- static Value infinity() {
- return std::numeric_limits::infinity();
- }
- /// \brief Gives back the sum of the given two elements.
- static Value plus(const Value& left, const Value& right) {
- return left + right;
- }
- /// \brief Gives back \c true only if the first value is less than
- /// the second.
- static bool less(const Value& left, const Value& right) {
- return left < right;
- }
- };
-
- template
- struct BellmanFordDefaultOperationTraits {
- typedef V Value;
- static Value zero() {
- return static_cast(0);
- }
- static Value infinity() {
- return std::numeric_limits::max();
- }
- static Value plus(const Value& left, const Value& right) {
- if (left == infinity() || right == infinity()) return infinity();
- return left + right;
- }
- static bool less(const Value& left, const Value& right) {
- return left < right;
- }
- };
-
- /// \brief Default traits class of BellmanFord class.
- ///
- /// Default traits class of BellmanFord class.
- /// \param GR The type of the digraph.
- /// \param LEN The type of the length map.
- template
- struct BellmanFordDefaultTraits {
- /// The type of the digraph the algorithm runs on.
- typedef GR Digraph;
-
- /// \brief The type of the map that stores the arc lengths.
- ///
- /// The type of the map that stores the arc lengths.
- /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
- typedef LEN LengthMap;
-
- /// The type of the arc lengths.
- typedef typename LEN::Value Value;
-
- /// \brief Operation traits for Bellman-Ford algorithm.
- ///
- /// It defines the used operations and the infinity value for the
- /// given \c Value type.
- /// \see BellmanFordDefaultOperationTraits
- typedef BellmanFordDefaultOperationTraits OperationTraits;
-
- /// \brief The type of the map that stores the last arcs of the
- /// shortest paths.
- ///
- /// The type of the map that stores the last
- /// arcs of the shortest paths.
- /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
- typedef typename GR::template NodeMap PredMap;
-
- /// \brief Instantiates a \c PredMap.
- ///
- /// This function instantiates a \ref PredMap.
- /// \param g is the digraph to which we would like to define the
- /// \ref PredMap.
- static PredMap *createPredMap(const GR& g) {
- return new PredMap(g);
- }
-
- /// \brief The type of the map that stores the distances of the nodes.
- ///
- /// The type of the map that stores the distances of the nodes.
- /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
- typedef typename GR::template NodeMap DistMap;
-
- /// \brief Instantiates a \c DistMap.
- ///
- /// This function instantiates a \ref DistMap.
- /// \param g is the digraph to which we would like to define the
- /// \ref DistMap.
- static DistMap *createDistMap(const GR& g) {
- return new DistMap(g);
- }
-
- };
-
- /// \brief %BellmanFord algorithm class.
- ///
- /// \ingroup shortest_path
- /// This class provides an efficient implementation of the Bellman-Ford
- /// algorithm. The maximum time complexity of the algorithm is
- /// O(ne).
- ///
- /// The Bellman-Ford algorithm solves the single-source shortest path
- /// problem when the arcs can have negative lengths, but the digraph
- /// should not contain directed cycles with negative total length.
- /// If all arc costs are non-negative, consider to use the Dijkstra
- /// algorithm instead, since it is more efficient.
- ///
- /// The arc lengths are passed to the algorithm using a
- /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
- /// kind of length. The type of the length values is determined by the
- /// \ref concepts::ReadMap::Value "Value" type of the length map.
- ///
- /// There is also a \ref bellmanFord() "function-type interface" for the
- /// Bellman-Ford algorithm, which is convenient in the simplier cases and
- /// it can be used easier.
- ///
- /// \tparam GR The type of the digraph the algorithm runs on.
- /// The default type is \ref ListDigraph.
- /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
- /// the lengths of the arcs. The default map type is
- /// \ref concepts::Digraph::ArcMap "GR::ArcMap".
- /// \tparam TR The traits class that defines various types used by the
- /// algorithm. By default, it is \ref BellmanFordDefaultTraits
- /// "BellmanFordDefaultTraits".
- /// In most cases, this parameter should not be set directly,
- /// consider to use the named template parameters instead.
-#ifdef DOXYGEN
- template
-#else
- template ,
- typename TR=BellmanFordDefaultTraits >
-#endif
- class BellmanFord {
- public:
-
- ///The type of the underlying digraph.
- typedef typename TR::Digraph Digraph;
-
- /// \brief The type of the arc lengths.
- typedef typename TR::LengthMap::Value Value;
- /// \brief The type of the map that stores the arc lengths.
- typedef typename TR::LengthMap LengthMap;
- /// \brief The type of the map that stores the last
- /// arcs of the shortest paths.
- typedef typename TR::PredMap PredMap;
- /// \brief The type of the map that stores the distances of the nodes.
- typedef typename TR::DistMap DistMap;
- /// The type of the paths.
- typedef PredMapPath Path;
- ///\brief The \ref BellmanFordDefaultOperationTraits
- /// "operation traits class" of the algorithm.
- typedef typename TR::OperationTraits OperationTraits;
-
- ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
- typedef TR Traits;
-
- private:
-
- typedef typename Digraph::Node Node;
- typedef typename Digraph::NodeIt NodeIt;
- typedef typename Digraph::Arc Arc;
- typedef typename Digraph::OutArcIt OutArcIt;
-
- // Pointer to the underlying digraph.
- const Digraph *_gr;
- // Pointer to the length map
- const LengthMap *_length;
- // Pointer to the map of predecessors arcs.
- PredMap *_pred;
- // Indicates if _pred is locally allocated (true) or not.
- bool _local_pred;
- // Pointer to the map of distances.
- DistMap *_dist;
- // Indicates if _dist is locally allocated (true) or not.
- bool _local_dist;
-
- typedef typename Digraph::template NodeMap MaskMap;
- MaskMap *_mask;
-
- std::vector _process;
-
- // Creates the maps if necessary.
- void create_maps() {
- if(!_pred) {
- _local_pred = true;
- _pred = Traits::createPredMap(*_gr);
- }
- if(!_dist) {
- _local_dist = true;
- _dist = Traits::createDistMap(*_gr);
- }
- if(!_mask) {
- _mask = new MaskMap(*_gr);
- }
- }
-
- public :
-
- typedef BellmanFord Create;
-
- /// \name Named Template Parameters
-
- ///@{
-
- template
- struct SetPredMapTraits : public Traits {
- typedef T PredMap;
- static PredMap *createPredMap(const Digraph&) {
- LEMON_ASSERT(false, "PredMap is not initialized");
- return 0; // ignore warnings
- }
- };
-
- /// \brief \ref named-templ-param "Named parameter" for setting
- /// \c PredMap type.
- ///
- /// \ref named-templ-param "Named parameter" for setting
- /// \c PredMap type.
- /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
- template
- struct SetPredMap
- : public BellmanFord< Digraph, LengthMap, SetPredMapTraits > {
- typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits > Create;
- };
-
- template
- struct SetDistMapTraits : public Traits {
- typedef T DistMap;
- static DistMap *createDistMap(const Digraph&) {
- LEMON_ASSERT(false, "DistMap is not initialized");
- return 0; // ignore warnings
- }
- };
-
- /// \brief \ref named-templ-param "Named parameter" for setting
- /// \c DistMap type.
- ///
- /// \ref named-templ-param "Named parameter" for setting
- /// \c DistMap type.
- /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
- template
- struct SetDistMap
- : public BellmanFord< Digraph, LengthMap, SetDistMapTraits > {
- typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits > Create;
- };
-
- template
- struct SetOperationTraitsTraits : public Traits {
- typedef T OperationTraits;
- };
-
- /// \brief \ref named-templ-param "Named parameter" for setting
- /// \c OperationTraits type.
- ///
- /// \ref named-templ-param "Named parameter" for setting
- /// \c OperationTraits type.
- /// For more information, see \ref BellmanFordDefaultOperationTraits.
- template
- struct SetOperationTraits
- : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits > {
- typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits >
- Create;
- };
-
- ///@}
-
- protected:
-
- BellmanFord() {}
-
- public:
-
- /// \brief Constructor.
- ///
- /// Constructor.
- /// \param g The digraph the algorithm runs on.
- /// \param length The length map used by the algorithm.
- BellmanFord(const Digraph& g, const LengthMap& length) :
- _gr(&g), _length(&length),
- _pred(0), _local_pred(false),
- _dist(0), _local_dist(false), _mask(0) {}
-
- ///Destructor.
- ~BellmanFord() {
- if(_local_pred) delete _pred;
- if(_local_dist) delete _dist;
- if(_mask) delete _mask;
- }
-
- /// \brief Sets the length map.
- ///
- /// Sets the length map.
- /// \return (*this)
- BellmanFord &lengthMap(const LengthMap &map) {
- _length = ↦
- return *this;
- }
-
- /// \brief Sets the map that stores the predecessor arcs.
- ///
- /// Sets the map that stores the predecessor arcs.
- /// If you don't use this function before calling \ref run()
- /// or \ref init(), an instance will be allocated automatically.
- /// The destructor deallocates this automatically allocated map,
- /// of course.
- /// \return (*this)
- BellmanFord &predMap(PredMap &map) {
- if(_local_pred) {
- delete _pred;
- _local_pred=false;
- }
- _pred = ↦
- return *this;
- }
-
- /// \brief Sets the map that stores the distances of the nodes.
- ///
- /// Sets the map that stores the distances of the nodes calculated
- /// by the algorithm.
- /// If you don't use this function before calling \ref run()
- /// or \ref init(), an instance will be allocated automatically.
- /// The destructor deallocates this automatically allocated map,
- /// of course.
- /// \return (*this)
- BellmanFord &distMap(DistMap &map) {
- if(_local_dist) {
- delete _dist;
- _local_dist=false;
- }
- _dist = ↦
- return *this;
- }
-
- /// \name Execution Control
- /// The simplest way to execute the Bellman-Ford algorithm is to use
- /// one of the member functions called \ref run().\n
- /// If you need better control on the execution, you have to call
- /// \ref init() first, then you can add several source nodes
- /// with \ref addSource(). Finally the actual path computation can be
- /// performed with \ref start(), \ref checkedStart() or
- /// \ref limitedStart().
-
- ///@{
-
- /// \brief Initializes the internal data structures.
- ///
- /// Initializes the internal data structures. The optional parameter
- /// is the initial distance of each node.
- void init(const Value value = OperationTraits::infinity()) {
- create_maps();
- for (NodeIt it(*_gr); it != INVALID; ++it) {
- _pred->set(it, INVALID);
- _dist->set(it, value);
- }
- _process.clear();
- if (OperationTraits::less(value, OperationTraits::infinity())) {
- for (NodeIt it(*_gr); it != INVALID; ++it) {
- _process.push_back(it);
- _mask->set(it, true);
- }
- } else {
- for (NodeIt it(*_gr); it != INVALID; ++it) {
- _mask->set(it, false);
- }
- }
- }
-
- /// \brief Adds a new source node.
- ///
- /// This function adds a new source node. The optional second parameter
- /// is the initial distance of the node.
- void addSource(Node source, Value dst = OperationTraits::zero()) {
- _dist->set(source, dst);
- if (!(*_mask)[source]) {
- _process.push_back(source);
- _mask->set(source, true);
- }
- }
-
- /// \brief Executes one round from the Bellman-Ford algorithm.
- ///
- /// If the algoritm calculated the distances in the previous round
- /// exactly for the paths of at most \c k arcs, then this function
- /// will calculate the distances exactly for the paths of at most
- /// k+1 arcs. Performing \c k iterations using this function
- /// calculates the shortest path distances exactly for the paths
- /// consisting of at most \c k arcs.
- ///
- /// \warning The paths with limited arc number cannot be retrieved
- /// easily with \ref path() or \ref predArc() functions. If you also
- /// need the shortest paths and not only the distances, you should
- /// store the \ref predMap() "predecessor map" after each iteration
- /// and build the path manually.
- ///
- /// \return \c true when the algorithm have not found more shorter
- /// paths.
- ///
- /// \see ActiveIt
- bool processNextRound() {
- for (int i = 0; i < int(_process.size()); ++i) {
- _mask->set(_process[i], false);
- }
- std::vector nextProcess;
- std::vector values(_process.size());
- for (int i = 0; i < int(_process.size()); ++i) {
- values[i] = (*_dist)[_process[i]];
- }
- for (int i = 0; i < int(_process.size()); ++i) {
- for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
- Node target = _gr->target(it);
- Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
- if (OperationTraits::less(relaxed, (*_dist)[target])) {
- _pred->set(target, it);
- _dist->set(target, relaxed);
- if (!(*_mask)[target]) {
- _mask->set(target, true);
- nextProcess.push_back(target);
- }
- }
- }
- }
- _process.swap(nextProcess);
- return _process.empty();
- }
-
- /// \brief Executes one weak round from the Bellman-Ford algorithm.
- ///
- /// If the algorithm calculated the distances in the previous round
- /// at least for the paths of at most \c k arcs, then this function
- /// will calculate the distances at least for the paths of at most
- /// k+1 arcs.
- /// This function does not make it possible to calculate the shortest
- /// path distances exactly for paths consisting of at most \c k arcs,
- /// this is why it is called weak round.
- ///
- /// \return \c true when the algorithm have not found more shorter
- /// paths.
- ///
- /// \see ActiveIt
- bool processNextWeakRound() {
- for (int i = 0; i < int(_process.size()); ++i) {
- _mask->set(_process[i], false);
- }
- std::vector nextProcess;
- for (int i = 0; i < int(_process.size()); ++i) {
- for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
- Node target = _gr->target(it);
- Value relaxed =
- OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
- if (OperationTraits::less(relaxed, (*_dist)[target])) {
- _pred->set(target, it);
- _dist->set(target, relaxed);
- if (!(*_mask)[target]) {
- _mask->set(target, true);
- nextProcess.push_back(target);
- }
- }
- }
- }
- _process.swap(nextProcess);
- return _process.empty();
- }
-
- /// \brief Executes the algorithm.
- ///
- /// Executes the algorithm.
- ///
- /// This method runs the Bellman-Ford algorithm from the root node(s)
- /// in order to compute the shortest path to each node.
- ///
- /// The algorithm computes
- /// - the shortest path tree (forest),
- /// - the distance of each node from the root(s).
- ///
- /// \pre init() must be called and at least one root node should be
- /// added with addSource() before using this function.
- void start() {
- int num = countNodes(*_gr) - 1;
- for (int i = 0; i < num; ++i) {
- if (processNextWeakRound()) break;
- }
- }
-
- /// \brief Executes the algorithm and checks the negative cycles.
- ///
- /// Executes the algorithm and checks the negative cycles.
- ///
- /// This method runs the Bellman-Ford algorithm from the root node(s)
- /// in order to compute the shortest path to each node and also checks
- /// if the digraph contains cycles with negative total length.
- ///
- /// The algorithm computes
- /// - the shortest path tree (forest),
- /// - the distance of each node from the root(s).
- ///
- /// \return \c false if there is a negative cycle in the digraph.
- ///
- /// \pre init() must be called and at least one root node should be
- /// added with addSource() before using this function.
- bool checkedStart() {
- int num = countNodes(*_gr);
- for (int i = 0; i < num; ++i) {
- if (processNextWeakRound()) return true;
- }
- return _process.empty();
- }
-
- /// \brief Executes the algorithm with arc number limit.
- ///
- /// Executes the algorithm with arc number limit.
- ///
- /// This method runs the Bellman-Ford algorithm from the root node(s)
- /// in order to compute the shortest path distance for each node
- /// using only the paths consisting of at most \c num arcs.
- ///
- /// The algorithm computes
- /// - the limited distance of each node from the root(s),
- /// - the predecessor arc for each node.
- ///
- /// \warning The paths with limited arc number cannot be retrieved
- /// easily with \ref path() or \ref predArc() functions. If you also
- /// need the shortest paths and not only the distances, you should
- /// store the \ref predMap() "predecessor map" after each iteration
- /// and build the path manually.
- ///
- /// \pre init() must be called and at least one root node should be
- /// added with addSource() before using this function.
- void limitedStart(int num) {
- for (int i = 0; i < num; ++i) {
- if (processNextRound()) break;
- }
- }
-
- /// \brief Runs the algorithm from the given root node.
- ///
- /// This method runs the Bellman-Ford algorithm from the given root
- /// node \c s in order to compute the shortest path to each node.
- ///
- /// The algorithm computes
- /// - the shortest path tree (forest),
- /// - the distance of each node from the root(s).
- ///
- /// \note bf.run(s) is just a shortcut of the following code.
- /// \code
- /// bf.init();
- /// bf.addSource(s);
- /// bf.start();
- /// \endcode
- void run(Node s) {
- init();
- addSource(s);
- start();
- }
-
- /// \brief Runs the algorithm from the given root node with arc
- /// number limit.
- ///
- /// This method runs the Bellman-Ford algorithm from the given root
- /// node \c s in order to compute the shortest path distance for each
- /// node using only the paths consisting of at most \c num arcs.
- ///
- /// The algorithm computes
- /// - the limited distance of each node from the root(s),
- /// - the predecessor arc for each node.
- ///
- /// \warning The paths with limited arc number cannot be retrieved
- /// easily with \ref path() or \ref predArc() functions. If you also
- /// need the shortest paths and not only the distances, you should
- /// store the \ref predMap() "predecessor map" after each iteration
- /// and build the path manually.
- ///
- /// \note bf.run(s, num) is just a shortcut of the following code.
- /// \code
- /// bf.init();
- /// bf.addSource(s);
- /// bf.limitedStart(num);
- /// \endcode
- void run(Node s, int num) {
- init();
- addSource(s);
- limitedStart(num);
- }
-
- ///@}
-
- /// \brief LEMON iterator for getting the active nodes.
- ///
- /// This class provides a common style LEMON iterator that traverses
- /// the active nodes of the Bellman-Ford algorithm after the last
- /// phase. These nodes should be checked in the next phase to
- /// find augmenting arcs outgoing from them.
- class ActiveIt {
- public:
-
- /// \brief Constructor.
- ///
- /// Constructor for getting the active nodes of the given BellmanFord
- /// instance.
- ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
- {
- _index = _algorithm->_process.size() - 1;
- }
-
- /// \brief Invalid constructor.
- ///
- /// Invalid constructor.
- ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
-
- /// \brief Conversion to \c Node.
- ///
- /// Conversion to \c Node.
- operator Node() const {
- return _index >= 0 ? _algorithm->_process[_index] : INVALID;
- }
-
- /// \brief Increment operator.
- ///
- /// Increment operator.
- ActiveIt& operator++() {
- --_index;
- return *this;
- }
-
- bool operator==(const ActiveIt& it) const {
- return static_cast(*this) == static_cast(it);
- }
- bool operator!=(const ActiveIt& it) const {
- return static_cast(*this) != static_cast(it);
- }
- bool operator<(const ActiveIt& it) const {
- return static_cast(*this) < static_cast(it);
- }
-
- private:
- const BellmanFord* _algorithm;
- int _index;
- };
-
- /// \name Query Functions
- /// The result of the Bellman-Ford algorithm can be obtained using these
- /// functions.\n
- /// Either \ref run() or \ref init() should be called before using them.
-
- ///@{
-
- /// \brief The shortest path to the given node.
- ///
- /// Gives back the shortest path to the given node from the root(s).
- ///
- /// \warning \c t should be reached from the root(s).
- ///
- /// \pre Either \ref run() or \ref init() must be called before
- /// using this function.
- Path path(Node t) const
- {
- return Path(*_gr, *_pred, t);
- }
-
- /// \brief The distance of the given node from the root(s).
- ///
- /// Returns the distance of the given node from the root(s).
- ///
- /// \warning If node \c v is not reached from the root(s), then
- /// the return value of this function is undefined.
- ///
- /// \pre Either \ref run() or \ref init() must be called before
- /// using this function.
- Value dist(Node v) const { return (*_dist)[v]; }
-
- /// \brief Returns the 'previous arc' of the shortest path tree for
- /// the given node.
- ///
- /// This function returns the 'previous arc' of the shortest path
- /// tree for node \c v, i.e. it returns the last arc of a
- /// shortest path from a root to \c v. It is \c INVALID if \c v
- /// is not reached from the root(s) or if \c v is a root.
- ///
- /// The shortest path tree used here is equal to the shortest path
- /// tree used in \ref predNode() and \ref predMap().
- ///
- /// \pre Either \ref run() or \ref init() must be called before
- /// using this function.
- Arc predArc(Node v) const { return (*_pred)[v]; }
-
- /// \brief Returns the 'previous node' of the shortest path tree for
- /// the given node.
- ///
- /// This function returns the 'previous node' of the shortest path
- /// tree for node \c v, i.e. it returns the last but one node of
- /// a shortest path from a root to \c v. It is \c INVALID if \c v
- /// is not reached from the root(s) or if \c v is a root.
- ///
- /// The shortest path tree used here is equal to the shortest path
- /// tree used in \ref predArc() and \ref predMap().
- ///
- /// \pre Either \ref run() or \ref init() must be called before
- /// using this function.
- Node predNode(Node v) const {
- return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
- }
-
- /// \brief Returns a const reference to the node map that stores the
- /// distances of the nodes.
- ///
- /// Returns a const reference to the node map that stores the distances
- /// of the nodes calculated by the algorithm.
- ///
- /// \pre Either \ref run() or \ref init() must be called before
- /// using this function.
- const DistMap &distMap() const { return *_dist;}
-
- /// \brief Returns a const reference to the node map that stores the
- /// predecessor arcs.
- ///
- /// Returns a const reference to the node map that stores the predecessor
- /// arcs, which form the shortest path tree (forest).
- ///
- /// \pre Either \ref run() or \ref init() must be called before
- /// using this function.
- const PredMap &predMap() const { return *_pred; }
-
- /// \brief Checks if a node is reached from the root(s).
- ///
- /// Returns \c true if \c v is reached from the root(s).
- ///
- /// \pre Either \ref run() or \ref init() must be called before
- /// using this function.
- bool reached(Node v) const {
- return (*_dist)[v] != OperationTraits::infinity();
- }
-
- /// \brief Gives back a negative cycle.
- ///
- /// This function gives back a directed cycle with negative total
- /// length if the algorithm has already found one.
- /// Otherwise it gives back an empty path.
- lemon::Path negativeCycle() const {
- typename Digraph::template NodeMap state(*_gr, -1);
- lemon::Path cycle;
- for (int i = 0; i < int(_process.size()); ++i) {
- if (state[_process[i]] != -1) continue;
- for (Node v = _process[i]; (*_pred)[v] != INVALID;
- v = _gr->source((*_pred)[v])) {
- if (state[v] == i) {
- cycle.addFront((*_pred)[v]);
- for (Node u = _gr->source((*_pred)[v]); u != v;
- u = _gr->source((*_pred)[u])) {
- cycle.addFront((*_pred)[u]);
- }
- return cycle;
- }
- else if (state[v] >= 0) {
- break;
- }
- state[v] = i;
- }
- }
- return cycle;
- }
-
- ///@}
- };
-
- /// \brief Default traits class of bellmanFord() function.
- ///
- /// Default traits class of bellmanFord() function.
- /// \tparam GR The type of the digraph.
- /// \tparam LEN The type of the length map.
- template
- struct BellmanFordWizardDefaultTraits {
- /// The type of the digraph the algorithm runs on.
- typedef GR Digraph;
-
- /// \brief The type of the map that stores the arc lengths.
- ///
- /// The type of the map that stores the arc lengths.
- /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
- typedef LEN LengthMap;
-
- /// The type of the arc lengths.
- typedef typename LEN::Value Value;
-
- /// \brief Operation traits for Bellman-Ford algorithm.
- ///
- /// It defines the used operations and the infinity value for the
- /// given \c Value type.
- /// \see BellmanFordDefaultOperationTraits
- typedef BellmanFordDefaultOperationTraits OperationTraits;
-
- /// \brief The type of the map that stores the last
- /// arcs of the shortest paths.
- ///
- /// The type of the map that stores the last arcs of the shortest paths.
- /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
- typedef typename GR::template NodeMap PredMap;
-
- /// \brief Instantiates a \c PredMap.
- ///
- /// This function instantiates a \ref PredMap.
- /// \param g is the digraph to which we would like to define the
- /// \ref PredMap.
- static PredMap *createPredMap(const GR &g) {
- return new PredMap(g);
- }
-
- /// \brief The type of the map that stores the distances of the nodes.
- ///
- /// The type of the map that stores the distances of the nodes.
- /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
- typedef typename GR::template NodeMap DistMap;
-
- /// \brief Instantiates a \c DistMap.
- ///
- /// This function instantiates a \ref DistMap.
- /// \param g is the digraph to which we would like to define the
- /// \ref DistMap.
- static DistMap *createDistMap(const GR &g) {
- return new DistMap(g);
- }
-
- ///The type of the shortest paths.
-
- ///The type of the shortest paths.
- ///It must meet the \ref concepts::Path "Path" concept.
- typedef lemon::Path Path;
- };
-
- /// \brief Default traits class used by BellmanFordWizard.
- ///
- /// Default traits class used by BellmanFordWizard.
- /// \tparam GR The type of the digraph.
- /// \tparam LEN The type of the length map.
- template
- class BellmanFordWizardBase
- : public BellmanFordWizardDefaultTraits {
-
- typedef BellmanFordWizardDefaultTraits Base;
- protected:
- // Type of the nodes in the digraph.
- typedef typename Base::Digraph::Node Node;
-
- // Pointer to the underlying digraph.
- void *_graph;
- // Pointer to the length map
- void *_length;
- // Pointer to the map of predecessors arcs.
- void *_pred;
- // Pointer to the map of distances.
- void *_dist;
- //Pointer to the shortest path to the target node.
- void *_path;
- //Pointer to the distance of the target node.
- void *_di;
-
- public:
- /// Constructor.
-
- /// This constructor does not require parameters, it initiates
- /// all of the attributes to default values \c 0.
- BellmanFordWizardBase() :
- _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
-
- /// Constructor.
-
- /// This constructor requires two parameters,
- /// others are initiated to \c 0.
- /// \param gr The digraph the algorithm runs on.
- /// \param len The length map.
- BellmanFordWizardBase(const GR& gr,
- const LEN& len) :
- _graph(reinterpret_cast(const_cast(&gr))),
- _length(reinterpret_cast(const_cast(&len))),
- _pred(0), _dist(0), _path(0), _di(0) {}
-
- };
-
- /// \brief Auxiliary class for the function-type interface of the
- /// \ref BellmanFord "Bellman-Ford" algorithm.
- ///
- /// This auxiliary class is created to implement the
- /// \ref bellmanFord() "function-type interface" of the
- /// \ref BellmanFord "Bellman-Ford" algorithm.
- /// It does not have own \ref run() method, it uses the
- /// functions and features of the plain \ref BellmanFord.
- ///
- /// This class should only be used through the \ref bellmanFord()
- /// function, which makes it easier to use the algorithm.
- ///
- /// \tparam TR The traits class that defines various types used by the
- /// algorithm.
- template
- class BellmanFordWizard : public TR {
- typedef TR Base;
-
- typedef typename TR::Digraph Digraph;
-
- typedef typename Digraph::Node Node;
- typedef typename Digraph::NodeIt NodeIt;
- typedef typename Digraph::Arc Arc;
- typedef typename Digraph::OutArcIt ArcIt;
-
- typedef typename TR::LengthMap LengthMap;
- typedef typename LengthMap::Value Value;
- typedef typename TR::PredMap PredMap;
- typedef typename TR::DistMap DistMap;
- typedef typename TR::Path Path;
-
- public:
- /// Constructor.
- BellmanFordWizard() : TR() {}
-
- /// \brief Constructor that requires parameters.
- ///
- /// Constructor that requires parameters.
- /// These parameters will be the default values for the traits class.
- /// \param gr The digraph the algorithm runs on.
- /// \param len The length map.
- BellmanFordWizard(const Digraph& gr, const LengthMap& len)
- : TR(gr, len) {}
-
- /// \brief Copy constructor
- BellmanFordWizard(const TR &b) : TR(b) {}
-
- ~BellmanFordWizard() {}
-
- /// \brief Runs the Bellman-Ford algorithm from the given source node.
- ///
- /// This method runs the Bellman-Ford algorithm from the given source
- /// node in order to compute the shortest path to each node.
- void run(Node s) {
- BellmanFord
- bf(*reinterpret_cast(Base::_graph),
- *reinterpret_cast(Base::_length));
- if (Base::_pred) bf.predMap(*reinterpret_cast(Base::_pred));
- if (Base::_dist) bf.distMap(*reinterpret_cast(Base::_dist));
- bf.run(s);
- }
-
- /// \brief Runs the Bellman-Ford algorithm to find the shortest path
- /// between \c s and \c t.
- ///
- /// This method runs the Bellman-Ford algorithm from node \c s
- /// in order to compute the shortest path to node \c t.
- /// Actually, it computes the shortest path to each node, but using
- /// this function you can retrieve the distance and the shortest path
- /// for a single target node easier.
- ///
- /// \return \c true if \c t is reachable form \c s.
- bool run(Node s, Node t) {
- BellmanFord
- bf(*reinterpret_cast(Base::_graph),
- *reinterpret_cast(Base::_length));
- if (Base::_pred) bf.predMap(*reinterpret_cast(Base::_pred));
- if (Base::_dist) bf.distMap(*reinterpret_cast(Base::_dist));
- bf.run(s);
- if (Base::_path) *reinterpret_cast(Base::_path) = bf.path(t);
- if (Base::_di) *reinterpret_cast(Base::_di) = bf.dist(t);
- return bf.reached(t);
- }
-
- template
- struct SetPredMapBase : public Base {
- typedef T PredMap;
- static PredMap *createPredMap(const Digraph &) { return 0; };
- SetPredMapBase(const TR &b) : TR(b) {}
- };
-
- /// \brief \ref named-templ-param "Named parameter" for setting
- /// the predecessor map.
- ///
- /// \ref named-templ-param "Named parameter" for setting
- /// the map that stores the predecessor arcs of the nodes.
- template
- BellmanFordWizard > predMap(const T &t) {
- Base::_pred=reinterpret_cast(const_cast(&t));
- return BellmanFordWizard >(*this);
- }
-
- template
- struct SetDistMapBase : public Base {
- typedef T DistMap;
- static DistMap *createDistMap(const Digraph &) { return 0; };
- SetDistMapBase(const TR &b) : TR(b) {}
- };
-
- /// \brief \ref named-templ-param "Named parameter" for setting
- /// the distance map.
- ///
- /// \ref named-templ-param "Named parameter" for setting
- /// the map that stores the distances of the nodes calculated
- /// by the algorithm.
- template
- BellmanFordWizard > distMap(const T &t) {
- Base::_dist=reinterpret_cast(const_cast(&t));
- return BellmanFordWizard >(*this);
- }
-
- template
- struct SetPathBase : public Base {
- typedef T Path;
- SetPathBase(const TR &b) : TR(b) {}
- };
-
- /// \brief \ref named-func-param "Named parameter" for getting
- /// the shortest path to the target node.
- ///
- /// \ref named-func-param "Named parameter" for getting
- /// the shortest path to the target node.
- template
- BellmanFordWizard > path(const T &t)
- {
- Base::_path=reinterpret_cast(const_cast(&t));
- return BellmanFordWizard >(*this);
- }
-
- /// \brief \ref named-func-param "Named parameter" for getting
- /// the distance of the target node.
- ///
- /// \ref named-func-param "Named parameter" for getting
- /// the distance of the target node.
- BellmanFordWizard dist(const Value &d)
- {
- Base::_di=reinterpret_cast(const_cast(&d));
- return *this;
- }
-
- };
-
- /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
- /// algorithm.
- ///
- /// \ingroup shortest_path
- /// Function type interface for the \ref BellmanFord "Bellman-Ford"
- /// algorithm.
- ///
- /// This function also has several \ref named-templ-func-param
- /// "named parameters", they are declared as the members of class
- /// \ref BellmanFordWizard.
- /// The following examples show how to use these parameters.
- /// \code
- /// // Compute shortest path from node s to each node
- /// bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
- ///
- /// // Compute shortest path from s to t
- /// bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
- /// \endcode
- /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
- /// to the end of the parameter list.
- /// \sa BellmanFordWizard
- /// \sa BellmanFord
- template
- BellmanFordWizard >
- bellmanFord(const GR& digraph,
- const LEN& length)
- {
- return BellmanFordWizard >(digraph, length);
- }
-
-} //END OF NAMESPACE LEMON
-
-#endif
-
Index: lemon/bfs.h
===================================================================
--- lemon/bfs.h (revision 877)
+++ lemon/bfs.h (revision 492)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -48,5 +48,5 @@
///The type of the map that stores the predecessor
///arcs of the shortest paths.
- ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap PredMap;
///Instantiates a \c PredMap.
@@ -63,6 +63,5 @@
///The type of the map that indicates which nodes are processed.
- ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
- ///By default, it is a NullMap.
+ ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
typedef NullMap ProcessedMap;
///Instantiates a \c ProcessedMap.
@@ -83,6 +82,5 @@
///The type of the map that indicates which nodes are reached.
- ///It must conform to
- ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
///Instantiates a \c ReachedMap.
@@ -99,5 +97,5 @@
///The type of the map that stores the distances of the nodes.
- ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap DistMap;
///Instantiates a \c DistMap.
@@ -123,9 +121,4 @@
///\tparam GR The type of the digraph the algorithm runs on.
///The default type is \ref ListDigraph.
- ///\tparam TR The traits class that defines various types used by the
- ///algorithm. By default, it is \ref BfsDefaultTraits
- ///"BfsDefaultTraits".
- ///In most cases, this parameter should not be set directly,
- ///consider to use the named template parameters instead.
#ifdef DOXYGEN
template
struct SetPredMap : public Bfs< Digraph, SetPredMapTraits > {
@@ -253,5 +246,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c DistMap type.
- ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetDistMap : public Bfs< Digraph, SetDistMapTraits > {
@@ -273,6 +266,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c ReachedMap type.
- ///It must conform to
- ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
template
struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits > {
@@ -294,5 +286,5 @@
///\ref named-templ-param "Named parameter" for setting
///\c ProcessedMap type.
- ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
template
struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits > {
@@ -422,6 +414,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 better control on the execution, you have to call
- ///\ref init() first, then you can add several source nodes with
+ ///If you need more control on the execution, first you have to call
+ ///\ref init(), 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.
@@ -709,6 +701,10 @@
///Runs the algorithm to visit all nodes in the digraph.
- ///This method runs the %BFS algorithm in order 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).
///
///\note b.run(s) is just a shortcut of the following code.
@@ -742,7 +738,7 @@
///@{
- ///The shortest path to the given node.
-
- ///Returns the shortest path to the given node from the root(s).
+ ///The shortest path to a node.
+
+ ///Returns the shortest path to a node.
///
///\warning \c t should be reached from the root(s).
@@ -752,7 +748,7 @@
Path path(Node t) const { return Path(*G, *_pred, t); }
- ///The distance of the given node from the root(s).
-
- ///Returns the distance of the given node from the root(s).
+ ///The distance of a node from the root(s).
+
+ ///Returns the distance of a node from the root(s).
///
///\warning If node \c v is not reached from the root(s), then
@@ -763,7 +759,6 @@
int dist(Node v) const { return (*_dist)[v]; }
- ///\brief Returns the 'previous arc' of the shortest path tree for
- ///the given node.
- ///
+ ///Returns the 'previous arc' of the shortest path tree for a 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
@@ -772,5 +767,5 @@
///
///The shortest path tree used here is equal to the shortest path
- ///tree used in \ref predNode() and \ref predMap().
+ ///tree used in \ref predNode().
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -778,14 +773,13 @@
Arc predArc(Node v) const { return (*_pred)[v];}
- ///\brief Returns the 'previous node' of the shortest path tree for
- ///the given node.
- ///
+ ///Returns the 'previous node' of the shortest path tree for a 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
- ///of a shortest path from a root to \c v. It is \c INVALID
+ ///from 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().
+ ///tree used in \ref predArc().
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -808,5 +802,5 @@
///
///Returns a const reference to the node map that stores the predecessor
- ///arcs, which form the shortest path tree (forest).
+ ///arcs, which form the shortest path tree.
///
///\pre Either \ref run(Node) "run()" or \ref init()
@@ -814,5 +808,5 @@
const PredMap &predMap() const { return *_pred;}
- ///Checks if the given node is reached from the root(s).
+ ///Checks if a node is reached from the root(s).
///Returns \c true if \c v is reached from the root(s).
@@ -840,5 +834,5 @@
///The type of the map that stores the predecessor
///arcs of the shortest paths.
- ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap PredMap;
///Instantiates a PredMap.
@@ -855,6 +849,6 @@
///The type of the map that indicates which nodes are processed.
- ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
- ///By default, it is a NullMap.
+ ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///By default it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a ProcessedMap.
@@ -875,6 +869,5 @@
///The type of the map that indicates which nodes are reached.
- ///It must conform to
- ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
///Instantiates a ReachedMap.
@@ -891,5 +884,5 @@
///The type of the map that stores the distances of the nodes.
- ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+ ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
typedef typename Digraph::template NodeMap DistMap;
///Instantiates a DistMap.
@@ -906,5 +899,5 @@
///The type of the shortest paths.
- ///It must conform to the \ref concepts::Path "Path" concept.
+ ///It must meet the \ref concepts::Path "Path" concept.
typedef lemon::Path Path;
};
@@ -912,6 +905,10 @@
/// Default traits class used by BfsWizard
- /// Default traits class used by BfsWizard.
- /// \tparam GR The type of the digraph.
+ /// 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.
template
class BfsWizardBase : public BfsWizardDefaultTraits
@@ -941,5 +938,5 @@
/// Constructor.
- /// This constructor does not require parameters, it initiates
+ /// This constructor does not require parameters, therefore it initiates
/// all of the attributes to \c 0.
BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
@@ -966,7 +963,4 @@
/// This class should only be used through the \ref bfs() function,
/// which makes it easier to use the algorithm.
- ///
- /// \tparam TR The traits class that defines various types used by the
- /// algorithm.
template
class BfsWizard : public TR
@@ -974,4 +968,5 @@
typedef TR Base;
+ ///The type of the digraph the algorithm runs on.
typedef typename TR::Digraph Digraph;
@@ -981,8 +976,14 @@
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;
@@ -1054,6 +1055,6 @@
///Runs BFS algorithm to visit all nodes in the digraph.
- ///This method runs BFS algorithm in order to visit all nodes
- ///in the digraph.
+ ///This method runs BFS algorithm in order to compute
+ ///the shortest path to each node.
void run()
{
@@ -1067,10 +1068,9 @@
SetPredMapBase(const TR &b) : TR(b) {}
};
-
- ///\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.
+ ///\brief \ref named-func-param "Named parameter"
+ ///for setting PredMap object.
+ ///
+ ///\ref named-func-param "Named parameter"
+ ///for setting PredMap object.
template
BfsWizard > predMap(const T &t)
@@ -1086,10 +1086,9 @@
SetReachedMapBase(const TR &b) : TR(b) {}
};
-
- ///\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.
+ ///\brief \ref named-func-param "Named parameter"
+ ///for setting ReachedMap object.
+ ///
+ /// \ref named-func-param "Named parameter"
+ ///for setting ReachedMap object.
template
BfsWizard > reachedMap(const T &t)
@@ -1105,11 +1104,9 @@
SetDistMapBase(const TR &b) : TR(b) {}
};
-
- ///\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.
+ ///\brief \ref named-func-param "Named parameter"
+ ///for setting DistMap object.
+ ///
+ /// \ref named-func-param "Named parameter"
+ ///for setting DistMap object.
template
BfsWizard > distMap(const T &t)
@@ -1125,10 +1122,9 @@
SetProcessedMapBase(const TR &b) : TR(b) {}
};
-
- ///\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.
+ ///\brief \ref named-func-param "Named parameter"
+ ///for setting ProcessedMap object.
+ ///
+ /// \ref named-func-param "Named parameter"
+ ///for setting ProcessedMap object.
template
BfsWizard > processedMap(const T &t)
@@ -1269,6 +1265,5 @@
///
/// The type of the map that indicates which nodes are reached.
- /// It must conform to
- ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
@@ -1308,9 +1303,9 @@
/// does not observe the BFS events. If you want to observe the BFS
/// events, you should implement your own visitor class.
- /// \tparam TR The traits class that defines various types used by the
- /// algorithm. By default, it is \ref BfsVisitDefaultTraits
- /// "BfsVisitDefaultTraits".
- /// In most cases, this parameter should not be set directly,
- /// consider to use the named template parameters instead.
+ /// \tparam TR Traits class to set various data types used by the
+ /// algorithm. The default traits class is
+ /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits".
+ /// See \ref BfsVisitDefaultTraits for the documentation of
+ /// a BFS visit traits class.
#ifdef DOXYGEN
template
@@ -1431,6 +1426,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 better control on the execution, you have to call
- /// \ref init() first, then you can add several source nodes with
+ /// If you need more control on the execution, first you have to call
+ /// \ref init(), 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.
@@ -1704,6 +1699,10 @@
/// \brief Runs the algorithm to visit all nodes in the digraph.
///
- /// This method runs the %BFS algorithm in order 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).
///
/// \note b.run(s) is just a shortcut of the following code.
@@ -1737,5 +1736,5 @@
///@{
- /// \brief Checks if the given node is reached from the root(s).
+ /// \brief Checks if a 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 711)
+++ lemon/bin_heap.h (revision 683)
@@ -20,7 +20,7 @@
#define LEMON_BIN_HEAP_H
-///\ingroup heaps
+///\ingroup auxdat
///\file
-///\brief Binary heap implementation.
+///\brief Binary Heap implementation.
#include
@@ -30,39 +30,43 @@
namespace lemon {
- /// \ingroup heaps
- ///
- /// \brief Binary heap data structure.
- ///
- /// This class implements the \e binary \e heap data structure.
- /// It fully conforms to the \ref concepts::Heap "heap concept".
- ///
- /// \tparam PR Type of the 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
+ ///\ingroup auxdat
+ ///
+ ///\brief A Binary Heap implementation.
+ ///
+ ///This class implements the \e binary \e heap data structure.
+ ///
+ ///A \e heap is a data structure for storing items with specified values
+ ///called \e priorities in such a way that finding the item with minimum
+ ///priority is efficient. \c 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
template >
-#endif
class BinHeap {
+
public:
-
- /// Type of the item-int map.
+ ///\e
typedef IM ItemIntMap;
- /// Type of the priorities.
+ ///\e
typedef PR Prio;
- /// Type of the items stored in the heap.
+ ///\e
typedef typename ItemIntMap::Key Item;
- /// Type of the item-priority pairs.
+ ///\e
typedef std::pair- Pair;
- /// Functor type for comparing the priorities.
+ ///\e
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
+ /// \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
/// heap's point of view, but may be useful to the user.
///
@@ -81,41 +85,40 @@
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.
+ /// \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.
explicit BinHeap(ItemIntMap &map) : _iim(map) {}
- /// \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.
+ /// \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.
BinHeap(ItemIntMap &map, const Compare &comp)
: _iim(map), _comp(comp) {}
- /// \brief The number of items stored in the heap.
- ///
- /// This function returns the number of items stored in the heap.
+ /// The number of items stored in the heap.
+ ///
+ /// \brief Returns the number of items stored in the heap.
int size() const { return _data.size(); }
- /// \brief Check if the heap is empty.
- ///
- /// This function returns \c true if the heap is empty.
+ /// \brief Checks if the heap stores no items.
+ ///
+ /// Returns \c true if and only if the heap stores no items.
bool empty() const { return _data.empty(); }
- /// \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.
+ /// \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.
void clear() {
_data.clear();
@@ -125,10 +128,10 @@
static int parent(int i) { return (i-1)/2; }
- static int secondChild(int i) { return 2*i+2; }
+ static int second_child(int i) { return 2*i+2; }
bool less(const Pair &p1, const Pair &p2) const {
return _comp(p1.second, p2.second);
}
- int bubbleUp(int hole, Pair p) {
+ int bubble_up(int hole, Pair p) {
int par = parent(hole);
while( hole>0 && less(p,_data[par]) ) {
@@ -141,6 +144,6 @@
}
- int bubbleDown(int hole, Pair p, int length) {
- int child = secondChild(hole);
+ int bubble_down(int hole, Pair p, int length) {
+ int child = second_child(hole);
while(child < length) {
if( less(_data[child-1], _data[child]) ) {
@@ -151,5 +154,5 @@
move(_data[child], hole);
hole = child;
- child = secondChild(hole);
+ child = second_child(hole);
}
child--;
@@ -169,45 +172,42 @@
public:
-
/// \brief Insert a pair of item and priority into the heap.
///
- /// This function inserts \c p.first to the heap with priority
- /// \c p.second.
+ /// Adds \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);
- 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.
+ 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.
/// \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 Return the item having minimum priority.
- ///
- /// This function returns the item having minimum priority.
- /// \pre The heap must be non-empty.
+ /// \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.
Item top() const {
return _data[0].first;
}
- /// \brief The minimum priority.
- ///
- /// This function returns the minimum priority.
- /// \pre The heap must be non-empty.
+ /// \brief Returns the minimum priority relative to \c Compare.
+ ///
+ /// It returns the minimum priority relative to \c Compare.
+ /// \pre The heap must be nonempty.
Prio prio() const {
return _data[0].second;
}
- /// \brief Remove the item having minimum priority.
- ///
- /// This function removes the item having minimum priority.
+ /// \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.
/// \pre The heap must be non-empty.
void pop() {
@@ -215,15 +215,14 @@
_iim.set(_data[0].first, POST_HEAP);
if (n > 0) {
- bubbleDown(0, _data[n], n);
+ bubble_down(0, _data[n], n);
}
_data.pop_back();
}
- /// \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.
+ /// \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.
void erase(const Item &i) {
int h = _iim[i];
@@ -231,6 +230,6 @@
_iim.set(_data[h].first, POST_HEAP);
if( h < n ) {
- if ( bubbleUp(h, _data[n]) == h) {
- bubbleDown(h, _data[n], n);
+ if ( bubble_up(h, _data[n]) == h) {
+ bubble_down(h, _data[n], n);
}
}
@@ -238,9 +237,10 @@
}
- /// \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.
+
+ /// \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.
Prio operator[](const Item &i) const {
int idx = _iim[i];
@@ -248,10 +248,9 @@
}
- /// \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.
+ /// \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.
/// \param i The item.
/// \param p The priority.
@@ -262,40 +261,42 @@
}
else if( _comp(p, _data[idx].second) ) {
- bubbleUp(idx, Pair(i,p));
+ bubble_up(idx, Pair(i,p));
}
else {
- 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.
+ 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.
/// \param i The item.
/// \param p The priority.
- /// \pre \e i must be stored in the heap with priority at least \e p.
+ /// \pre \c i must be stored in the heap with priority at least \c
+ /// p relative to \c Compare.
void decrease(const Item &i, const Prio &p) {
int idx = _iim[i];
- 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.
+ 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.
/// \param i The item.
/// \param p The priority.
- /// \pre \e i must be stored in the heap with priority at most \e p.
+ /// \pre \c i must be stored in the heap with priority at most \c
+ /// p relative to \c Compare.
void increase(const Item &i, const Prio &p) {
int idx = _iim[i];
- 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.
+ 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.
/// \param i The item.
State state(const Item &i) const {
@@ -306,9 +307,9 @@
}
- /// \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.
+ /// \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.
/// \param i The item.
/// \param st The state. It should not be \c IN_HEAP.
@@ -327,11 +328,10 @@
}
- /// \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.
+ /// \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.
void replace(const Item& i, const Item& j) {
int idx = _iim[i];
Index: mon/binomial_heap.h
===================================================================
--- lemon/binomial_heap.h (revision 877)
+++ (revision )
@@ -1,445 +1,0 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library.
- *
- * Copyright (C) 2003-2010
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_BINOMIAL_HEAP_H
-#define LEMON_BINOMIAL_HEAP_H
-
-///\file
-///\ingroup heaps
-///\brief Binomial Heap implementation.
-
-#include
-#include
-#include
-#include
-#include
-
-namespace lemon {
-
- /// \ingroup heaps
- ///
- ///\brief Binomial heap data structure.
- ///
- /// This class implements the \e binomial \e heap data structure.
- /// It fully conforms to the \ref concepts::Heap "heap concept".
- ///
- /// The methods \ref increase() and \ref erase() are not efficient
- /// in a binomial heap. In case of many calls of these operations,
- /// it is better to use other heap structure, e.g. \ref BinHeap
- /// "binary heap".
- ///
- /// \tparam PR Type of the priorities of the items.
- /// \tparam IM A read-writable item map with \c int values, used
- /// internally to handle the cross references.
- /// \tparam CMP A functor class for comparing the priorities.
- /// The default is \c std::less.
-#ifdef DOXYGEN
- template
-#else
- template >
-#endif
- class BinomialHeap {
- public:
- /// Type of the item-int map.
- typedef IM ItemIntMap;
- /// Type of the priorities.
- typedef PR Prio;
- /// Type of the items stored in the heap.
- typedef typename ItemIntMap::Key Item;
- /// Functor type for comparing the priorities.
- typedef CMP Compare;
-
- /// \brief Type to represent the states of the items.
- ///
- /// Each item has a state associated to it. It can be "in heap",
- /// "pre-heap" or "post-heap". The latter two are indifferent from the
- /// heap's point of view, but may be useful to the user.
- ///
- /// The item-int map must be initialized in such way that it assigns
- /// \c PRE_HEAP (-1) to any element to be put in the heap.
- enum State {
- IN_HEAP = 0, ///< = 0.
- PRE_HEAP = -1, ///< = -1.
- POST_HEAP = -2 ///< = -2.
- };
-
- private:
- class Store;
-
- std::vector _data;
- int _min, _head;
- ItemIntMap &_iim;
- Compare _comp;
- int _num_items;
-
- public:
- /// \brief Constructor.
- ///
- /// Constructor.
- /// \param map A map that assigns \c int values to the items.
- /// It is used internally to handle the cross references.
- /// The assigned value must be \c PRE_HEAP (-1) for each item.
- explicit BinomialHeap(ItemIntMap &map)
- : _min(0), _head(-1), _iim(map), _num_items(0) {}
-
- /// \brief Constructor.
- ///
- /// Constructor.
- /// \param map A map that assigns \c int values to the items.
- /// It is used internally to handle the cross references.
- /// The assigned value must be \c PRE_HEAP (-1) for each item.
- /// \param comp The function object used for comparing the priorities.
- BinomialHeap(ItemIntMap &map, const Compare &comp)
- : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
-
- /// \brief The number of items stored in the heap.
- ///
- /// This function returns the number of items stored in the heap.
- int size() const { return _num_items; }
-
- /// \brief Check if the heap is empty.
- ///
- /// This function returns \c true if the heap is empty.
- bool empty() const { return _num_items==0; }
-
- /// \brief Make the heap empty.
- ///
- /// This functon makes the heap empty.
- /// It does not change the cross reference map. If you want to reuse
- /// a heap that is not surely empty, you should first clear it and
- /// then you should set the cross reference map to \c PRE_HEAP
- /// for each item.
- void clear() {
- _data.clear(); _min=0; _num_items=0; _head=-1;
- }
-
- /// \brief Set the priority of an item or insert it, if it is
- /// not stored in the heap.
- ///
- /// This method sets the priority of the given item if it is
- /// already stored in the heap. Otherwise it inserts the given
- /// item into the heap with the given priority.
- /// \param item The item.
- /// \param value The priority.
- void set (const Item& item, const Prio& value) {
- int i=_iim[item];
- if ( i >= 0 && _data[i].in ) {
- if ( _comp(value, _data[i].prio) ) decrease(item, value);
- if ( _comp(_data[i].prio, value) ) increase(item, value);
- } else push(item, value);
- }
-
- /// \brief Insert an item into the heap with the given priority.
- ///
- /// This function inserts the given item into the heap with the
- /// given priority.
- /// \param item The item to insert.
- /// \param value The priority of the item.
- /// \pre \e item must not be stored in the heap.
- void push (const Item& item, const Prio& value) {
- int i=_iim[item];
- if ( i<0 ) {
- int s=_data.size();
- _iim.set( item,s );
- Store st;
- st.name=item;
- st.prio=value;
- _data.push_back(st);
- i=s;
- }
- else {
- _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
- _data[i].degree=0;
- _data[i].in=true;
- _data[i].prio=value;
- }
-
- if( 0==_num_items ) {
- _head=i;
- _min=i;
- } else {
- merge(i);
- if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
- }
- ++_num_items;
- }
-
- /// \brief Return the item having minimum priority.
- ///
- /// This function returns the item having minimum priority.
- /// \pre The heap must be non-empty.
- Item top() const { return _data[_min].name; }
-
- /// \brief The minimum priority.
- ///
- /// This function returns the minimum priority.
- /// \pre The heap must be non-empty.
- Prio prio() const { return _data[_min].prio; }
-
- /// \brief The priority of the given item.
- ///
- /// This function returns the priority of the given item.
- /// \param item The item.
- /// \pre \e item must be in the heap.
- const Prio& operator[](const Item& item) const {
- return _data[_iim[item]].prio;
- }
-
- /// \brief Remove the item having minimum priority.
- ///
- /// This function removes the item having minimum priority.
- /// \pre The heap must be non-empty.
- void pop() {
- _data[_min].in=false;
-
- int head_child=-1;
- if ( _data[_min].child!=-1 ) {
- int child=_data[_min].child;
- int neighb;
- while( child!=-1 ) {
- neighb=_data[child].right_neighbor;
- _data[child].parent=-1;
- _data[child].right_neighbor=head_child;
- head_child=child;
- child=neighb;
- }
- }
-
- if ( _data[_head].right_neighbor==-1 ) {
- // there was only one root
- _head=head_child;
- }
- else {
- // there were more roots
- if( _head!=_min ) { unlace(_min); }
- else { _head=_data[_head].right_neighbor; }
- merge(head_child);
- }
- _min=findMin();
- --_num_items;
- }
-
- /// \brief Remove the given item from the heap.
- ///
- /// This function removes the given item from the heap if it is
- /// already stored.
- /// \param item The item to delete.
- /// \pre \e item must be in the heap.
- void erase (const Item& item) {
- int i=_iim[item];
- if ( i >= 0 && _data[i].in ) {
- decrease( item, _data[_min].prio-1 );
- pop();
- }
- }
-
- /// \brief Decrease the priority of an item to the given value.
- ///
- /// This function decreases the priority of an item to the given value.
- /// \param item The item.
- /// \param value The priority.
- /// \pre \e item must be stored in the heap with priority at least \e value.
- void decrease (Item item, const Prio& value) {
- int i=_iim[item];
- int p=_data[i].parent;
- _data[i].prio=value;
-
- while( p!=-1 && _comp(value, _data[p].prio) ) {
- _data[i].name=_data[p].name;
- _data[i].prio=_data[p].prio;
- _data[p].name=item;
- _data[p].prio=value;
- _iim[_data[i].name]=i;
- i=p;
- p=_data[p].parent;
- }
- _iim[item]=i;
- if ( _comp(value, _data[_min].prio) ) _min=i;
- }
-
- /// \brief Increase the priority of an item to the given value.
- ///
- /// This function increases the priority of an item to the given value.
- /// \param item The item.
- /// \param value The priority.
- /// \pre \e item must be stored in the heap with priority at most \e value.
- void increase (Item item, const Prio& value) {
- erase(item);
- push(item, value);
- }
-
- /// \brief Return the state of an item.
- ///
- /// This method returns \c PRE_HEAP if the given item has never
- /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
- /// and \c POST_HEAP otherwise.
- /// In the latter case it is possible that the item will get back
- /// to the heap again.
- /// \param item The item.
- State state(const Item &item) const {
- int i=_iim[item];
- if( i>=0 ) {
- if ( _data[i].in ) i=0;
- else i=-2;
- }
- return State(i);
- }
-
- /// \brief Set the state of an item in the heap.
- ///
- /// This function sets the state of the given item in the heap.
- /// It can be used to manually clear the heap when it is important
- /// to achive better time complexity.
- /// \param i The item.
- /// \param st The state. It should not be \c IN_HEAP.
- void state(const Item& i, State st) {
- switch (st) {
- case POST_HEAP:
- case PRE_HEAP:
- if (state(i) == IN_HEAP) {
- erase(i);
- }
- _iim[i] = st;
- break;
- case IN_HEAP:
- break;
- }
- }
-
- private:
-
- // Find the minimum of the roots
- int findMin() {
- if( _head!=-1 ) {
- int min_loc=_head, min_val=_data[_head].prio;
- for( int x=_data[_head].right_neighbor; x!=-1;
- x=_data[x].right_neighbor ) {
- if( _comp( _data[x].prio,min_val ) ) {
- min_val=_data[x].prio;
- min_loc=x;
- }
- }
- return min_loc;
- }
- else return -1;
- }
-
- // Merge the heap with another heap starting at the given position
- void merge(int a) {
- if( _head==-1 || a==-1 ) return;
- if( _data[a].right_neighbor==-1 &&
- _data[a].degree<=_data[_head].degree ) {
- _data[a].right_neighbor=_head;
- _head=a;
- } else {
- interleave(a);
- }
- if( _data[_head].right_neighbor==-1 ) return;
-
- int x=_head;
- int x_prev=-1, x_next=_data[x].right_neighbor;
- while( x_next!=-1 ) {
- if( _data[x].degree!=_data[x_next].degree ||
- ( _data[x_next].right_neighbor!=-1 &&
- _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
- x_prev=x;
- x=x_next;
- }
- else {
- if( _comp(_data[x_next].prio,_data[x].prio) ) {
- if( x_prev==-1 ) {
- _head=x_next;
- } else {
- _data[x_prev].right_neighbor=x_next;
- }
- fuse(x,x_next);
- x=x_next;
- }
- else {
- _data[x].right_neighbor=_data[x_next].right_neighbor;
- fuse(x_next,x);
- }
- }
- x_next=_data[x].right_neighbor;
- }
- }
-
- // Interleave the elements of the given list into the list of the roots
- void interleave(int a) {
- int p=_head, q=a;
- int curr=_data.size();
- _data.push_back(Store());
-
- while( p!=-1 || q!=-1 ) {
- if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
- _data[curr].right_neighbor=p;
- curr=p;
- p=_data[p].right_neighbor;
- }
- else {
- _data[curr].right_neighbor=q;
- curr=q;
- q=_data[q].right_neighbor;
- }
- }
-
- _head=_data.back().right_neighbor;
- _data.pop_back();
- }
-
- // Lace node a under node b
- void fuse(int a, int b) {
- _data[a].parent=b;
- _data[a].right_neighbor=_data[b].child;
- _data[b].child=a;
-
- ++_data[b].degree;
- }
-
- // Unlace node a (if it has siblings)
- void unlace(int a) {
- int neighb=_data[a].right_neighbor;
- int other=_head;
-
- while( _data[other].right_neighbor!=a )
- other=_data[other].right_neighbor;
- _data[other].right_neighbor=neighb;
- }
-
- private:
-
- class Store {
- friend class BinomialHeap;
-
- Item name;
- int parent;
- int right_neighbor;
- int child;
- int degree;
- bool in;
- Prio prio;
-
- Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
- in(true) {}
- };
- };
-
-} //namespace lemon
-
-#endif //LEMON_BINOMIAL_HEAP_H
-
Index: lemon/bits/array_map.h
===================================================================
--- lemon/bits/array_map.h (revision 877)
+++ lemon/bits/array_map.h (revision 617)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -71,5 +71,5 @@
private:
-
+
// The MapBase of the Map which imlements the core regisitry function.
typedef typename Notifier::ObserverBase Parent;
Index: lemon/bits/default_map.h
===================================================================
--- lemon/bits/default_map.h (revision 877)
+++ lemon/bits/default_map.h (revision 627)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -158,5 +158,5 @@
public:
typedef DefaultMap<_Graph, _Item, _Value> Map;
-
+
typedef typename Parent::GraphType GraphType;
typedef typename Parent::Value Value;
Index: lemon/bits/edge_set_extender.h
===================================================================
--- lemon/bits/edge_set_extender.h (revision 887)
+++ lemon/bits/edge_set_extender.h (revision 617)
@@ -1,7 +1,7 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
+/* -*- C++ -*-
*
- * This file is a part of LEMON, a generic C++ optimization library.
+ * This file is a part of LEMON, a generic C++ optimization library
*
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2008
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -64,9 +64,9 @@
Node oppositeNode(const Node &n, const Arc &e) const {
if (n == Parent::source(e))
- return Parent::target(e);
+ return Parent::target(e);
else if(n==Parent::target(e))
- return Parent::source(e);
+ return Parent::source(e);
else
- return INVALID;
+ return INVALID;
}
@@ -92,5 +92,5 @@
// Iterable extensions
- class NodeIt : public Node {
+ class NodeIt : public Node {
const Digraph* digraph;
public:
@@ -101,19 +101,19 @@
explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
- _graph.first(static_cast(*this));
- }
-
- NodeIt(const Digraph& _graph, const Node& node)
- : Node(node), digraph(&_graph) {}
-
- NodeIt& operator++() {
- digraph->next(*this);
- return *this;
- }
-
- };
-
-
- class ArcIt : public Arc {
+ _graph.first(static_cast(*this));
+ }
+
+ NodeIt(const Digraph& _graph, const Node& node)
+ : Node(node), digraph(&_graph) {}
+
+ NodeIt& operator++() {
+ digraph->next(*this);
+ return *this;
+ }
+
+ };
+
+
+ class ArcIt : public Arc {
const Digraph* digraph;
public:
@@ -124,19 +124,19 @@
explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
- _graph.first(static_cast