# HG changeset patch # User Alpar Juttner # 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". + /// \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 @@ -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 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". + ///In most cases, this parameter should not be set directly, + ///consider to use the named template parameters instead. #ifdef DOXYGEN template @@ -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 BfsWizard : public TR { @@ -1295,11 +1303,11 @@ /// \ref BfsVisitor "BfsVisitor" is an empty visitor, which /// does not observe the BFS events. If you want to observe the BFS /// events, you should implement your own visitor class. - /// \tparam TR Traits class to set various data types used by the - /// algorithm. The default traits class is - /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits". - /// See \ref BfsVisitDefaultTraits for the documentation of - /// a BFS visit traits class. + /// \tparam TR The traits class that defines various types used by the + /// algorithm. By default, it is \ref BfsVisitDefaultTraits + /// "BfsVisitDefaultTraits". + /// In most cases, this parameter should not be set directly, + /// consider to use the named template parameters instead. #ifdef DOXYGEN template #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". + /// 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". + \tparam TR The traits class that defines various types used by the + algorithm. By default, it is \ref CirculationDefaultTraits + "CirculationDefaultTraits". + 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". + /// 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". + ///In most cases, this parameter should not be set directly, + ///consider to use the named template parameters instead. #ifdef DOXYGEN template @@ -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 DfsWizard : public TR { @@ -1237,11 +1245,11 @@ /// \ref DfsVisitor "DfsVisitor" 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". - /// 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". + /// In most cases, this parameter should not be set directly, + /// consider to use the named template parameters instead. #ifdef DOXYGEN template #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". + ///\tparam TR The traits class that defines various types used by the + ///algorithm. By default, it is \ref DijkstraDefaultTraits + ///"DijkstraDefaultTraits". + ///In most cases, this parameter should not be set directly, + ///consider to use the named template parameters instead. #ifdef DOXYGEN template #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 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". + /// \tparam TR The traits class that defines various types used by the + /// algorithm. By default, it is \ref HartmannOrlinDefaultTraits + /// "HartmannOrlinDefaultTraits". + /// In most cases, this parameter should not be set directly, + /// consider to use the named template parameters instead. #ifdef DOXYGEN template #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". + /// \tparam TR The traits class that defines various types used by the + /// algorithm. By default, it is \ref HowardDefaultTraits + /// "HowardDefaultTraits". + /// In most cases, this parameter should not be set directly, + /// consider to use the named template parameters instead. #ifdef DOXYGEN template #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". + /// \tparam TR The traits class that defines various types used by the + /// algorithm. By default, it is \ref KarpDefaultTraits + /// "KarpDefaultTraits". + /// In most cases, this parameter should not be set directly, + /// consider to use the named template parameters instead. #ifdef DOXYGEN template #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". - /// \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". + /// In most cases, this parameter should not be set directly, + /// consider to use the named template parameters instead. #ifndef DOXYGEN template , typename TR = MinCostArborescenceDefaultTraits > #else - template + template #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 bool checkPlanarity(const GR& graph) { _planarity_bits::PlanarityChecking 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 K5 (full graph + /// with 5 nodes) or a K3,3 (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 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 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 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 class PlanarDrawing { public: TEMPLATE_GRAPH_TYPEDEFS(Graph); - /// \brief The point type for store coordinates + /// \brief The point type for storing coordinates typedef dim2::Point Point; - /// \brief The map type for store coordinates + /// \brief The map type for storing the coordinates of the nodes typedef typename Graph::template NodeMap 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 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 void run(const EmbeddingMap& embedding) { typedef SmartEdgeSet 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 . + /// This function returns the grid embedding in a node map of + /// \c dim2::Point 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 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 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 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 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 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". + /// \tparam TR The traits class that defines various types used by the + /// algorithm. By default, it is \ref PreflowDefaultTraits + /// "PreflowDefaultTraits". + /// In most cases, this parameter should not be set directly, + /// consider to use the named template parameters instead. #ifdef DOXYGEN template #else