# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1266009866 -3600
# Node ID cc9e0c15d7477a877efb6ee9f299cff19b755314
# Parent 75c97c3786d67ff19a6421c06ed497166ed310bd# Parent 7762cab7f372510158f532f231f40b1cacbc81a4
Merge
diff -r 75c97c3786d6 -r cc9e0c15d747 INSTALL
--- a/INSTALL Wed Feb 10 19:05:20 2010 +0100
+++ b/INSTALL Fri Feb 12 22:24:26 2010 +0100
@@ -173,3 +173,25 @@
--without-coin
Disable COIN-OR support.
+
+
+Makefile Variables
+==================
+
+Some Makefile variables are reserved by the GNU Coding Standards for
+the use of the "user" - the person building the package. For instance,
+CXX and CXXFLAGS are such variables, and have the same meaning as
+explained in the previous section. These variables can be set on the
+command line when invoking `make' like this:
+`make [VARIABLE=VALUE]...'
+
+WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us
+to hold several compiler flags related to warnings. Its default value
+can be overridden when invoking `make'. For example to disable all
+warning flags use `make WARNINGCXXFLAGS='.
+
+In order to turn off a single flag from the default set of warning
+flags, you can use the CXXFLAGS variable, since this is passed after
+WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is
+used by default when g++ is detected) you can use
+`make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.
diff -r 75c97c3786d6 -r cc9e0c15d747 doc/CMakeLists.txt
--- a/doc/CMakeLists.txt Wed Feb 10 19:05:20 2010 +0100
+++ b/doc/CMakeLists.txt Fri Feb 12 22:24:26 2010 +0100
@@ -26,6 +26,7 @@
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
COMMAND ${CMAKE_COMMAND} -E remove_directory html
COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
diff -r 75c97c3786d6 -r cc9e0c15d747 doc/Makefile.am
--- a/doc/Makefile.am Wed Feb 10 19:05:20 2010 +0100
+++ b/doc/Makefile.am Fri Feb 12 22:24:26 2010 +0100
@@ -28,6 +28,7 @@
connected_components.eps \
edge_biconnected_components.eps \
node_biconnected_components.eps \
+ planar.eps \
strongly_connected_components.eps
DOC_EPS_IMAGES = \
diff -r 75c97c3786d6 -r cc9e0c15d747 doc/images/planar.eps
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/images/planar.eps Fri Feb 12 22:24:26 2010 +0100
@@ -0,0 +1,181 @@
+%!PS-Adobe-2.0 EPSF-2.0
+%%Creator: LEMON, graphToEps()
+%%CreationDate: Fri Oct 19 18:32:32 2007
+%%BoundingBox: 0 0 596 842
+%%DocumentPaperSizes: a4
+%%EndComments
+/lb { setlinewidth setrgbcolor newpath moveto
+ 4 2 roll 1 index 1 index curveto stroke } bind def
+/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
+/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
+/sq { newpath 2 index 1 index add 2 index 2 index add moveto
+ 2 index 1 index sub 2 index 2 index add lineto
+ 2 index 1 index sub 2 index 2 index sub lineto
+ 2 index 1 index add 2 index 2 index sub lineto
+ closepath pop pop pop} bind def
+/di { newpath 2 index 1 index add 2 index moveto
+ 2 index 2 index 2 index add lineto
+ 2 index 1 index sub 2 index lineto
+ 2 index 2 index 2 index sub lineto
+ closepath pop pop pop} bind def
+/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
+ setrgbcolor 1.1 div sq fill
+ } bind def
+/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
+ setrgbcolor 1.1 div di fill
+ } bind def
+/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+ newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
+ lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
+ 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
+ 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/nmale {
+ 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+ newpath 5 index 5 index moveto
+ 5 index 4 index 1 mul 1.5 mul add
+ 5 index 5 index 3 sqrt 1.5 mul mul add
+ 1 index 1 index lineto
+ 1 index 1 index 7 index sub moveto
+ 1 index 1 index lineto
+ exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
+ stroke
+ 5 index 5 index 5 index c fill
+ setrgbcolor 1.1 div c fill
+ } bind def
+/arrl 1 def
+/arrw 0.3 def
+/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
+/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
+ /w exch def /len exch def
+ newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
+ len w sub arrl sub dx dy lrl
+ arrw dy dx neg lrl
+ dx arrl w add mul dy w 2 div arrw add mul sub
+ dy arrl w add mul dx w 2 div arrw add mul add rlineto
+ dx arrl w add mul neg dy w 2 div arrw add mul sub
+ dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
+ arrw dy dx neg lrl
+ len w sub arrl sub neg dx dy lrl
+ closepath fill } bind def
+/cshow { 2 index 2 index moveto dup stringwidth pop
+ neg 2 div fosi .35 mul neg rmoveto show pop pop} def
+
+gsave
+15 138.307 translate
+12.7843 dup scale
+90 rotate
+0.608112 -43.6081 translate
+%Edges:
+gsave
+9 31 9.5 30.5 10 30 0 0 0 0.091217 lb
+9 31 5.5 34.5 2 38 0 0 0 0.091217 lb
+9 31 25.5 16 42 1 0 0 0 0.091217 lb
+3 40 23 20.5 43 1 0 0 0 0.091217 lb
+3 40 22.5 20.5 42 1 0 0 0 0.091217 lb
+3 40 2.5 40.5 2 41 0 0 0 0.091217 lb
+13 25 10.5 24.5 8 24 0 0 0 0.091217 lb
+13 25 12 27 11 29 0 0 0 0.091217 lb
+3 4 2.5 3 2 2 0 0 0 0.091217 lb
+3 4 4.5 3 6 2 0 0 0 0.091217 lb
+6 25 7 24.5 8 24 0 0 0 0.091217 lb
+6 25 6 24.5 6 24 0 0 0 0.091217 lb
+34 2 33.5 2 33 2 0 0 0 0.091217 lb
+34 2 35 2 36 2 0 0 0 0.091217 lb
+6 8 16 9 26 10 0 0 0 0.091217 lb
+6 8 6 10.5 6 13 0 0 0 0.091217 lb
+6 8 6 7.5 6 7 0 0 0 0.091217 lb
+26 10 27.5 8.5 29 7 0 0 0 0.091217 lb
+26 10 27.5 9 29 8 0 0 0 0.091217 lb
+10 30 10.5 29.5 11 29 0 0 0 0.091217 lb
+8 24 7 23.5 6 23 0 0 0 0.091217 lb
+8 24 8 24.5 8 25 0 0 0 0.091217 lb
+33 2 32.5 2 32 2 0 0 0 0.091217 lb
+29 7 17.5 7 6 7 0 0 0 0.091217 lb
+2 2 1.5 22 1 42 0 0 0 0.091217 lb
+2 2 3.5 2 5 2 0 0 0 0.091217 lb
+21 15 13.5 14.5 6 14 0 0 0 0.091217 lb
+21 15 21 15.5 21 16 0 0 0 0.091217 lb
+1 42 0.5 42.5 0 43 0 0 0 0.091217 lb
+1 42 1.5 41.5 2 41 0 0 0 0.091217 lb
+6 15 6 15.5 6 16 0 0 0 0.091217 lb
+6 15 6 14.5 6 14 0 0 0 0.091217 lb
+43 1 22 0.5 1 0 0 0 0 0.091217 lb
+31 2 18.5 2 6 2 0 0 0 0.091217 lb
+31 2 31.5 2 32 2 0 0 0 0.091217 lb
+6 24 6 23.5 6 23 0 0 0 0.091217 lb
+6 16 6 16.5 6 17 0 0 0 0.091217 lb
+6 23 6 20 6 17 0 0 0 0.091217 lb
+6 2 5.5 2 5 2 0 0 0 0.091217 lb
+6 2 6 4.5 6 7 0 0 0 0.091217 lb
+0 43 0.5 21.5 1 0 0 0 0 0.091217 lb
+1 1 19.5 1.5 38 2 0 0 0 0.091217 lb
+1 1 1 0.5 1 0 0 0 0 0.091217 lb
+2 38 5.5 31.5 9 25 0 0 0 0.091217 lb
+25 13 15.5 13 6 13 0 0 0 0.091217 lb
+25 13 15.5 13.5 6 14 0 0 0 0.091217 lb
+8 25 8.5 25 9 25 0 0 0 0.091217 lb
+11 29 24.5 15.5 38 2 0 0 0 0.091217 lb
+6 17 11.5 18 17 19 0 0 0 0.091217 lb
+16 23 26.5 12.5 37 2 0 0 0 0.091217 lb
+16 23 18.5 19.5 21 16 0 0 0 0.091217 lb
+36 2 36.5 2 37 2 0 0 0 0.091217 lb
+36 2 32.5 5 29 8 0 0 0 0.091217 lb
+6 13 6 13.5 6 14 0 0 0 0.091217 lb
+37 2 37.5 2 38 2 0 0 0 0.091217 lb
+21 16 19 17.5 17 19 0 0 0 0.091217 lb
+grestore
+%Nodes:
+gsave
+29 8 0.304556 1 1 1 nc
+2 41 0.304556 1 1 1 nc
+6 7 0.304556 1 1 1 nc
+5 2 0.304556 1 1 1 nc
+17 19 0.304556 1 1 1 nc
+21 16 0.304556 1 1 1 nc
+1 0 0.304556 1 1 1 nc
+9 25 0.304556 1 1 1 nc
+6 14 0.304556 1 1 1 nc
+42 1 0.304556 1 1 1 nc
+38 2 0.304556 1 1 1 nc
+37 2 0.304556 1 1 1 nc
+6 13 0.304556 1 1 1 nc
+36 2 0.304556 1 1 1 nc
+16 23 0.304556 1 1 1 nc
+6 17 0.304556 1 1 1 nc
+11 29 0.304556 1 1 1 nc
+8 25 0.304556 1 1 1 nc
+32 2 0.304556 1 1 1 nc
+25 13 0.304556 1 1 1 nc
+2 38 0.304556 1 1 1 nc
+1 1 0.304556 1 1 1 nc
+0 43 0.304556 1 1 1 nc
+6 2 0.304556 1 1 1 nc
+6 23 0.304556 1 1 1 nc
+6 16 0.304556 1 1 1 nc
+6 24 0.304556 1 1 1 nc
+31 2 0.304556 1 1 1 nc
+43 1 0.304556 1 1 1 nc
+6 15 0.304556 1 1 1 nc
+1 42 0.304556 1 1 1 nc
+21 15 0.304556 1 1 1 nc
+2 2 0.304556 1 1 1 nc
+29 7 0.304556 1 1 1 nc
+33 2 0.304556 1 1 1 nc
+8 24 0.304556 1 1 1 nc
+10 30 0.304556 1 1 1 nc
+26 10 0.304556 1 1 1 nc
+6 8 0.304556 1 1 1 nc
+34 2 0.304556 1 1 1 nc
+6 25 0.304556 1 1 1 nc
+3 4 0.304556 1 1 1 nc
+13 25 0.304556 1 1 1 nc
+3 40 0.304556 1 1 1 nc
+9 31 0.304556 1 1 1 nc
+grestore
+grestore
+showpage
diff -r 75c97c3786d6 -r cc9e0c15d747 lemon/bellman_ford.h
--- a/lemon/bellman_ford.h Wed Feb 10 19:05:20 2010 +0100
+++ b/lemon/bellman_ford.h Fri Feb 12 22:24:26 2010 +0100
@@ -171,6 +171,11 @@
/// \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<int>".
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm. By default, it is \ref BellmanFordDefaultTraits
+ /// "BellmanFordDefaultTraits<GR, LEN>".
+ /// In most cases, this parameter should not be set directly,
+ /// consider to use the named template parameters instead.
#ifdef DOXYGEN
template <typename GR, typename LEN, typename TR>
#else
@@ -933,6 +938,9 @@
///
/// 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 TR>
class BellmanFordWizard : public TR {
typedef TR Base;
diff -r 75c97c3786d6 -r cc9e0c15d747 lemon/bfs.h
--- a/lemon/bfs.h Wed Feb 10 19:05:20 2010 +0100
+++ b/lemon/bfs.h Fri Feb 12 22:24:26 2010 +0100
@@ -121,6 +121,11 @@
///
///\tparam GR The type of the digraph the algorithm runs on.
///The default type is \ref ListDigraph.
+ ///\tparam TR The traits class that defines various types used by the
+ ///algorithm. By default, it is \ref BfsDefaultTraits
+ ///"BfsDefaultTraits<GR>".
+ ///In most cases, this parameter should not be set directly,
+ ///consider to use the named template parameters instead.
#ifdef DOXYGEN
template <typename GR,
typename TR>
@@ -957,6 +962,9 @@
///
/// 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 TR>
class BfsWizard : public TR
{
@@ -1295,11 +1303,11 @@
/// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
/// does not observe the BFS events. If you want to observe the BFS
/// events, you should implement your own visitor class.
- /// \tparam TR Traits class to set various data types used by the
- /// algorithm. The default traits class is
- /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
- /// See \ref BfsVisitDefaultTraits for the documentation of
- /// a BFS visit traits class.
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm. By default, it is \ref BfsVisitDefaultTraits
+ /// "BfsVisitDefaultTraits<GR>".
+ /// In most cases, this parameter should not be set directly,
+ /// consider to use the named template parameters instead.
#ifdef DOXYGEN
template <typename GR, typename VS, typename TR>
#else
diff -r 75c97c3786d6 -r cc9e0c15d747 lemon/capacity_scaling.h
--- a/lemon/capacity_scaling.h Wed Feb 10 19:05:20 2010 +0100
+++ b/lemon/capacity_scaling.h Fri Feb 12 22:24:26 2010 +0100
@@ -77,9 +77,14 @@
///
/// \tparam GR The digraph type the algorithm runs on.
/// \tparam V The number type used for flow amounts, capacity bounds
- /// and supply values in the algorithm. By default it is \c int.
+ /// and supply values in the algorithm. By default, it is \c int.
/// \tparam C The number type used for costs and potentials in the
- /// algorithm. By default it is the same as \c V.
+ /// algorithm. By default, it is the same as \c V.
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm. By default, it is \ref CapacityScalingDefaultTraits
+ /// "CapacityScalingDefaultTraits<GR, V, C>".
+ /// In most cases, this parameter should not be set directly,
+ /// consider to use the named template parameters instead.
///
/// \warning Both number types must be signed and all input data must
/// be integer.
diff -r 75c97c3786d6 -r cc9e0c15d747 lemon/circulation.h
--- a/lemon/circulation.h Wed Feb 10 19:05:20 2010 +0100
+++ b/lemon/circulation.h Fri Feb 12 22:24:26 2010 +0100
@@ -173,6 +173,11 @@
The default map type is \c LM.
\tparam SM The type of the supply map. The default map type is
\ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
+ \tparam TR The traits class that defines various types used by the
+ algorithm. By default, it is \ref CirculationDefaultTraits
+ "CirculationDefaultTraits<GR, LM, UM, SM>".
+ In most cases, this parameter should not be set directly,
+ consider to use the named template parameters instead.
*/
#ifdef DOXYGEN
template< typename GR,
diff -r 75c97c3786d6 -r cc9e0c15d747 lemon/cost_scaling.h
--- a/lemon/cost_scaling.h Wed Feb 10 19:05:20 2010 +0100
+++ b/lemon/cost_scaling.h Fri Feb 12 22:24:26 2010 +0100
@@ -104,9 +104,14 @@
///
/// \tparam GR The digraph type the algorithm runs on.
/// \tparam V The number type used for flow amounts, capacity bounds
- /// and supply values in the algorithm. By default it is \c int.
+ /// and supply values in the algorithm. By default, it is \c int.
/// \tparam C The number type used for costs and potentials in the
- /// algorithm. By default it is the same as \c V.
+ /// algorithm. By default, it is the same as \c V.
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm. By default, it is \ref CostScalingDefaultTraits
+ /// "CostScalingDefaultTraits<GR, V, C>".
+ /// In most cases, this parameter should not be set directly,
+ /// consider to use the named template parameters instead.
///
/// \warning Both number types must be signed and all input data must
/// be integer.
@@ -136,8 +141,7 @@
/// \brief The large cost type
///
/// The large cost type used for internal computations.
- /// Using the \ref CostScalingDefaultTraits "default traits class",
- /// it is \c long \c long if the \c Cost type is integer,
+ /// By default, it is \c long \c long if the \c Cost type is integer,
/// otherwise it is \c double.
typedef typename TR::LargeCost LargeCost;
diff -r 75c97c3786d6 -r cc9e0c15d747 lemon/dfs.h
--- a/lemon/dfs.h Wed Feb 10 19:05:20 2010 +0100
+++ b/lemon/dfs.h Fri Feb 12 22:24:26 2010 +0100
@@ -121,6 +121,11 @@
///
///\tparam GR The type of the digraph the algorithm runs on.
///The default type is \ref ListDigraph.
+ ///\tparam TR The traits class that defines various types used by the
+ ///algorithm. By default, it is \ref DfsDefaultTraits
+ ///"DfsDefaultTraits<GR>".
+ ///In most cases, this parameter should not be set directly,
+ ///consider to use the named template parameters instead.
#ifdef DOXYGEN
template <typename GR,
typename TR>
@@ -887,6 +892,9 @@
///
/// This class should only be used through the \ref dfs() function,
/// which makes it easier to use the algorithm.
+ ///
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm.
template<class TR>
class DfsWizard : public TR
{
@@ -1237,11 +1245,11 @@
/// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
/// does not observe the DFS events. If you want to observe the DFS
/// events, you should implement your own visitor class.
- /// \tparam TR Traits class to set various data types used by the
- /// algorithm. The default traits class is
- /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
- /// See \ref DfsVisitDefaultTraits for the documentation of
- /// a DFS visit traits class.
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm. By default, it is \ref DfsVisitDefaultTraits
+ /// "DfsVisitDefaultTraits<GR>".
+ /// In most cases, this parameter should not be set directly,
+ /// consider to use the named template parameters instead.
#ifdef DOXYGEN
template <typename GR, typename VS, typename TR>
#else
diff -r 75c97c3786d6 -r cc9e0c15d747 lemon/dijkstra.h
--- a/lemon/dijkstra.h Wed Feb 10 19:05:20 2010 +0100
+++ b/lemon/dijkstra.h Fri Feb 12 22:24:26 2010 +0100
@@ -192,6 +192,11 @@
///relatively time consuming process to compute the arc lengths if
///it is necessary. The default map type is \ref
///concepts::Digraph::ArcMap "GR::ArcMap<int>".
+ ///\tparam TR The traits class that defines various types used by the
+ ///algorithm. By default, it is \ref DijkstraDefaultTraits
+ ///"DijkstraDefaultTraits<GR, LEN>".
+ ///In most cases, this parameter should not be set directly,
+ ///consider to use the named template parameters instead.
#ifdef DOXYGEN
template <typename GR, typename LEN, typename TR>
#else
@@ -1092,6 +1097,9 @@
///
/// This class should only be used through the \ref dijkstra() function,
/// which makes it easier to use the algorithm.
+ ///
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm.
template<class TR>
class DijkstraWizard : public TR
{
diff -r 75c97c3786d6 -r cc9e0c15d747 lemon/hartmann_orlin.h
--- a/lemon/hartmann_orlin.h Wed Feb 10 19:05:20 2010 +0100
+++ b/lemon/hartmann_orlin.h Fri Feb 12 22:24:26 2010 +0100
@@ -106,6 +106,11 @@
/// \tparam GR The type of the digraph the algorithm runs on.
/// \tparam LEN The type of the length map. The default
/// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm. By default, it is \ref HartmannOrlinDefaultTraits
+ /// "HartmannOrlinDefaultTraits<GR, LEN>".
+ /// In most cases, this parameter should not be set directly,
+ /// consider to use the named template parameters instead.
#ifdef DOXYGEN
template <typename GR, typename LEN, typename TR>
#else
@@ -127,8 +132,7 @@
/// \brief The large value type
///
/// The large value type used for internal computations.
- /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
- /// it is \c long \c long if the \c Value type is integer,
+ /// By default, it is \c long \c long if the \c Value type is integer,
/// otherwise it is \c double.
typedef typename TR::LargeValue LargeValue;
diff -r 75c97c3786d6 -r cc9e0c15d747 lemon/howard.h
--- a/lemon/howard.h Wed Feb 10 19:05:20 2010 +0100
+++ b/lemon/howard.h Fri Feb 12 22:24:26 2010 +0100
@@ -106,6 +106,11 @@
/// \tparam GR The type of the digraph the algorithm runs on.
/// \tparam LEN The type of the length map. The default
/// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm. By default, it is \ref HowardDefaultTraits
+ /// "HowardDefaultTraits<GR, LEN>".
+ /// In most cases, this parameter should not be set directly,
+ /// consider to use the named template parameters instead.
#ifdef DOXYGEN
template <typename GR, typename LEN, typename TR>
#else
@@ -127,8 +132,7 @@
/// \brief The large value type
///
/// The large value type used for internal computations.
- /// Using the \ref HowardDefaultTraits "default traits class",
- /// it is \c long \c long if the \c Value type is integer,
+ /// By default, it is \c long \c long if the \c Value type is integer,
/// otherwise it is \c double.
typedef typename TR::LargeValue LargeValue;
diff -r 75c97c3786d6 -r cc9e0c15d747 lemon/karp.h
--- a/lemon/karp.h Wed Feb 10 19:05:20 2010 +0100
+++ b/lemon/karp.h Fri Feb 12 22:24:26 2010 +0100
@@ -104,6 +104,11 @@
/// \tparam GR The type of the digraph the algorithm runs on.
/// \tparam LEN The type of the length map. The default
/// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm. By default, it is \ref KarpDefaultTraits
+ /// "KarpDefaultTraits<GR, LEN>".
+ /// In most cases, this parameter should not be set directly,
+ /// consider to use the named template parameters instead.
#ifdef DOXYGEN
template <typename GR, typename LEN, typename TR>
#else
@@ -125,8 +130,7 @@
/// \brief The large value type
///
/// The large value type used for internal computations.
- /// Using the \ref KarpDefaultTraits "default traits class",
- /// it is \c long \c long if the \c Value type is integer,
+ /// By default, it is \c long \c long if the \c Value type is integer,
/// otherwise it is \c double.
typedef typename TR::LargeValue LargeValue;
diff -r 75c97c3786d6 -r cc9e0c15d747 lemon/min_cost_arborescence.h
--- a/lemon/min_cost_arborescence.h Wed Feb 10 19:05:20 2010 +0100
+++ b/lemon/min_cost_arborescence.h Fri Feb 12 22:24:26 2010 +0100
@@ -112,17 +112,18 @@
/// relatively time consuming process to compute the arc costs if
/// it is necessary. The default map type is \ref
/// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
- /// \param TR Traits class to set various data types used
- /// by the algorithm. The default traits class is
- /// \ref MinCostArborescenceDefaultTraits
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm. By default, it is \ref MinCostArborescenceDefaultTraits
/// "MinCostArborescenceDefaultTraits<GR, CM>".
+ /// In most cases, this parameter should not be set directly,
+ /// consider to use the named template parameters instead.
#ifndef DOXYGEN
template <typename GR,
typename CM = typename GR::template ArcMap<int>,
typename TR =
MinCostArborescenceDefaultTraits<GR, CM> >
#else
- template <typename GR, typename CM, typedef TR>
+ template <typename GR, typename CM, typename TR>
#endif
class MinCostArborescence {
public:
diff -r 75c97c3786d6 -r cc9e0c15d747 lemon/planarity.h
--- a/lemon/planarity.h Wed Feb 10 19:05:20 2010 +0100
+++ b/lemon/planarity.h Fri Feb 12 22:24:26 2010 +0100
@@ -518,9 +518,9 @@
/// \brief Planarity checking of an undirected simple graph
///
/// This function implements the Boyer-Myrvold algorithm for
- /// planarity checking of an undirected graph. It is a simplified
+ /// planarity checking of an undirected simple graph. It is a simplified
/// version of the PlanarEmbedding algorithm class because neither
- /// the embedding nor the kuratowski subdivisons are not computed.
+ /// the embedding nor the Kuratowski subdivisons are computed.
template <typename GR>
bool checkPlanarity(const GR& graph) {
_planarity_bits::PlanarityChecking<GR> pc(graph);
@@ -532,16 +532,17 @@
/// \brief Planar embedding of an undirected simple graph
///
/// This class implements the Boyer-Myrvold algorithm for planar
- /// embedding of an undirected graph. The planar embedding is an
+ /// embedding of an undirected simple graph. The planar embedding is an
/// ordering of the outgoing edges of the nodes, which is a possible
/// configuration to draw the graph in the plane. If there is not
- /// such ordering then the graph contains a \f$ K_5 \f$ (full graph
- /// with 5 nodes) or a \f$ K_{3,3} \f$ (complete bipartite graph on
- /// 3 ANode and 3 BNode) subdivision.
+ /// such ordering then the graph contains a K<sub>5</sub> (full graph
+ /// with 5 nodes) or a K<sub>3,3</sub> (complete bipartite graph on
+ /// 3 Red and 3 Blue nodes) subdivision.
///
/// The current implementation calculates either an embedding or a
- /// Kuratowski subdivision. The running time of the algorithm is
- /// \f$ O(n) \f$.
+ /// Kuratowski subdivision. The running time of the algorithm is O(n).
+ ///
+ /// \see PlanarDrawing, checkPlanarity()
template <typename Graph>
class PlanarEmbedding {
private:
@@ -591,22 +592,26 @@
public:
- /// \brief The map for store of embedding
+ /// \brief The map type for storing the embedding
+ ///
+ /// The map type for storing the embedding.
+ /// \see embeddingMap()
typedef typename Graph::template ArcMap<Arc> EmbeddingMap;
/// \brief Constructor
///
- /// \note The graph should be simple, i.e. parallel and loop arc
- /// free.
+ /// Constructor.
+ /// \pre The graph must be simple, i.e. it should not
+ /// contain parallel or loop arcs.
PlanarEmbedding(const Graph& graph)
: _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}
- /// \brief Runs the algorithm.
+ /// \brief Run the algorithm.
///
- /// Runs the algorithm.
- /// \param kuratowski If the parameter is false, then the
+ /// This function runs the algorithm.
+ /// \param kuratowski If this parameter is set to \c false, then the
/// algorithm does not compute a Kuratowski subdivision.
- ///\return %True when the graph is planar.
+ /// \return \c true if the graph is planar.
bool run(bool kuratowski = true) {
typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
@@ -699,30 +704,32 @@
return true;
}
- /// \brief Gives back the successor of an arc
+ /// \brief Give back the successor of an arc
///
- /// Gives back the successor of an arc. This function makes
+ /// This function gives back the successor of an arc. It makes
/// possible to query the cyclic order of the outgoing arcs from
/// a node.
Arc next(const Arc& arc) const {
return _embedding[arc];
}
- /// \brief Gives back the calculated embedding map
+ /// \brief Give back the calculated embedding map
///
- /// The returned map contains the successor of each arc in the
- /// graph.
+ /// This function gives back the calculated embedding map, which
+ /// contains the successor of each arc in the cyclic order of the
+ /// outgoing arcs of its source node.
const EmbeddingMap& embeddingMap() const {
return _embedding;
}
- /// \brief Gives back true if the undirected arc is in the
- /// kuratowski subdivision
+ /// \brief Give back \c true if the given edge is in the Kuratowski
+ /// subdivision
///
- /// Gives back true if the undirected arc is in the kuratowski
- /// subdivision
- /// \note The \c run() had to be called with true value.
- bool kuratowski(const Edge& edge) {
+ /// This function gives back \c true if the given edge is in the found
+ /// Kuratowski subdivision.
+ /// \pre The \c run() function must be called with \c true parameter
+ /// before using this function.
+ bool kuratowski(const Edge& edge) const {
return _kuratowski[edge];
}
@@ -2059,29 +2066,32 @@
/// \brief Schnyder's planar drawing algorithm
///
/// The planar drawing algorithm calculates positions for the nodes
- /// in the plane which coordinates satisfy that if the arcs are
- /// represented with straight lines then they will not intersect
+ /// in the plane. These coordinates satisfy that if the edges are
+ /// represented with straight lines, then they will not intersect
/// each other.
///
- /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid,
- /// i.e. each node will be located in the \c [0,n-2]x[0,n-2] square.
+ /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid,
+ /// i.e. each node will be located in the \c [0..n-2]x[0..n-2] square.
/// The time complexity of the algorithm is O(n).
+ ///
+ /// \see PlanarEmbedding
template <typename Graph>
class PlanarDrawing {
public:
TEMPLATE_GRAPH_TYPEDEFS(Graph);
- /// \brief The point type for store coordinates
+ /// \brief The point type for storing coordinates
typedef dim2::Point<int> Point;
- /// \brief The map type for store coordinates
+ /// \brief The map type for storing the coordinates of the nodes
typedef typename Graph::template NodeMap<Point> PointMap;
/// \brief Constructor
///
/// Constructor
- /// \pre The graph should be simple, i.e. loop and parallel arc free.
+ /// \pre The graph must be simple, i.e. it should not
+ /// contain parallel or loop arcs.
PlanarDrawing(const Graph& graph)
: _graph(graph), _point_map(graph) {}
@@ -2366,10 +2376,10 @@
public:
- /// \brief Calculates the node positions
+ /// \brief Calculate the node positions
///
- /// This function calculates the node positions.
- /// \return %True if the graph is planar.
+ /// This function calculates the node positions on the plane.
+ /// \return \c true if the graph is planar.
bool run() {
PlanarEmbedding<Graph> pe(_graph);
if (!pe.run()) return false;
@@ -2378,12 +2388,13 @@
return true;
}
- /// \brief Calculates the node positions according to a
+ /// \brief Calculate the node positions according to a
/// combinatorical embedding
///
- /// This function calculates the node locations. The \c embedding
- /// parameter should contain a valid combinatorical embedding, i.e.
- /// a valid cyclic order of the arcs.
+ /// This function calculates the node positions on the plane.
+ /// The given \c embedding map should contain a valid combinatorical
+ /// embedding, i.e. a valid cyclic order of the arcs.
+ /// It can be computed using PlanarEmbedding.
template <typename EmbeddingMap>
void run(const EmbeddingMap& embedding) {
typedef SmartEdgeSet<Graph> AuxGraph;
@@ -2423,14 +2434,15 @@
/// \brief The coordinate of the given node
///
- /// The coordinate of the given node.
+ /// This function returns the coordinate of the given node.
Point operator[](const Node& node) const {
return _point_map[node];
}
- /// \brief Returns the grid embedding in a \e NodeMap.
+ /// \brief Return the grid embedding in a node map
///
- /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> .
+ /// This function returns the grid embedding in a node map of
+ /// \c dim2::Point<int> coordinates.
const PointMap& coords() const {
return _point_map;
}
@@ -2470,23 +2482,22 @@
/// \brief Coloring planar graphs
///
/// The graph coloring problem is the coloring of the graph nodes
- /// that there are not adjacent nodes with the same color. The
- /// planar graphs can be always colored with four colors, it is
- /// proved by Appel and Haken and their proofs provide a quadratic
+ /// so that there are no adjacent nodes with the same color. The
+ /// planar graphs can always be colored with four colors, which is
+ /// proved by Appel and Haken. Their proofs provide a quadratic
/// time algorithm for four coloring, but it could not be used to
- /// implement efficient algorithm. The five and six coloring can be
- /// made in linear time, but in this class the five coloring has
+ /// implement an efficient algorithm. The five and six coloring can be
+ /// made in linear time, but in this class, the five coloring has
/// quadratic worst case time complexity. The two coloring (if
/// possible) is solvable with a graph search algorithm and it is
/// implemented in \ref bipartitePartitions() function in LEMON. To
- /// decide whether the planar graph is three colorable is
- /// NP-complete.
+ /// decide whether a planar graph is three colorable is NP-complete.
///
/// This class contains member functions for calculate colorings
/// with five and six colors. The six coloring algorithm is a simple
/// greedy coloring on the backward minimum outgoing order of nodes.
- /// This order can be computed as in each phase the node with least
- /// outgoing arcs to unprocessed nodes is chosen. This order
+ /// This order can be computed by selecting the node with least
+ /// outgoing arcs to unprocessed nodes in each phase. This order
/// guarantees that when a node is chosen for coloring it has at
/// most five already colored adjacents. The five coloring algorithm
/// use the same method, but if the greedy approach fails to color
@@ -2499,15 +2510,19 @@
TEMPLATE_GRAPH_TYPEDEFS(Graph);
- /// \brief The map type for store color indexes
+ /// \brief The map type for storing color indices
typedef typename Graph::template NodeMap<int> IndexMap;
- /// \brief The map type for store colors
+ /// \brief The map type for storing colors
+ ///
+ /// The map type for storing colors.
+ /// \see Palette, Color
typedef ComposeMap<Palette, IndexMap> ColorMap;
/// \brief Constructor
///
- /// Constructor
- /// \pre The graph should be simple, i.e. loop and parallel arc free.
+ /// Constructor.
+ /// \pre The graph must be simple, i.e. it should not
+ /// contain parallel or loop arcs.
PlanarColoring(const Graph& graph)
: _graph(graph), _color_map(graph), _palette(0) {
_palette.add(Color(1,0,0));
@@ -2518,47 +2533,47 @@
_palette.add(Color(0,1,1));
}
- /// \brief Returns the \e NodeMap of color indexes
+ /// \brief Return the node map of color indices
///
- /// Returns the \e NodeMap of color indexes. The values are in the
- /// range \c [0..4] or \c [0..5] according to the coloring method.
+ /// This function returns the node map of color indices. The values are
+ /// in the range \c [0..4] or \c [0..5] according to the coloring method.
IndexMap colorIndexMap() const {
return _color_map;
}
- /// \brief Returns the \e NodeMap of colors
+ /// \brief Return the node map of colors
///
- /// Returns the \e NodeMap of colors. The values are five or six
- /// distinct \ref lemon::Color "colors".
+ /// This function returns the node map of colors. The values are among
+ /// five or six distinct \ref lemon::Color "colors".
ColorMap colorMap() const {
return composeMap(_palette, _color_map);
}
- /// \brief Returns the color index of the node
+ /// \brief Return the color index of the node
///
- /// Returns the color index of the node. The values are in the
- /// range \c [0..4] or \c [0..5] according to the coloring method.
+ /// This function returns the color index of the given node. The value is
+ /// in the range \c [0..4] or \c [0..5] according to the coloring method.
int colorIndex(const Node& node) const {
return _color_map[node];
}
- /// \brief Returns the color of the node
+ /// \brief Return the color of the node
///
- /// Returns the color of the node. The values are five or six
- /// distinct \ref lemon::Color "colors".
+ /// This function returns the color of the given node. The value is among
+ /// five or six distinct \ref lemon::Color "colors".
Color color(const Node& node) const {
return _palette[_color_map[node]];
}
- /// \brief Calculates a coloring with at most six colors
+ /// \brief Calculate a coloring with at most six colors
///
/// This function calculates a coloring with at most six colors. The time
/// complexity of this variant is linear in the size of the graph.
- /// \return %True when the algorithm could color the graph with six color.
- /// If the algorithm fails, then the graph could not be planar.
- /// \note This function can return true if the graph is not
- /// planar but it can be colored with 6 colors.
+ /// \return \c true if the algorithm could color the graph with six colors.
+ /// If the algorithm fails, then the graph is not planar.
+ /// \note This function can return \c true if the graph is not
+ /// planar, but it can be colored with at most six colors.
bool runSixColoring() {
typename Graph::template NodeMap<int> heap_index(_graph, -1);
@@ -2660,11 +2675,14 @@
public:
- /// \brief Calculates a coloring with at most five colors
+ /// \brief Calculate a coloring with at most five colors
///
/// This function calculates a coloring with at most five
/// colors. The worst case time complexity of this variant is
/// quadratic in the size of the graph.
+ /// \param embedding This map should contain a valid combinatorical
+ /// embedding, i.e. a valid cyclic order of the arcs.
+ /// It can be computed using PlanarEmbedding.
template <typename EmbeddingMap>
void runFiveColoring(const EmbeddingMap& embedding) {
@@ -2711,12 +2729,12 @@
}
}
- /// \brief Calculates a coloring with at most five colors
+ /// \brief Calculate a coloring with at most five colors
///
/// This function calculates a coloring with at most five
/// colors. The worst case time complexity of this variant is
/// quadratic in the size of the graph.
- /// \return %True when the graph is planar.
+ /// \return \c true if the graph is planar.
bool runFiveColoring() {
PlanarEmbedding<Graph> pe(_graph);
if (!pe.run()) return false;
diff -r 75c97c3786d6 -r cc9e0c15d747 lemon/preflow.h
--- a/lemon/preflow.h Wed Feb 10 19:05:20 2010 +0100
+++ b/lemon/preflow.h Fri Feb 12 22:24:26 2010 +0100
@@ -119,6 +119,11 @@
/// \tparam GR The type of the digraph the algorithm runs on.
/// \tparam CAP The type of the capacity map. The default map
/// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+ /// \tparam TR The traits class that defines various types used by the
+ /// algorithm. By default, it is \ref PreflowDefaultTraits
+ /// "PreflowDefaultTraits<GR, CAP>".
+ /// In most cases, this parameter should not be set directly,
+ /// consider to use the named template parameters instead.
#ifdef DOXYGEN
template <typename GR, typename CAP, typename TR>
#else