1.1 --- a/INSTALL Wed Feb 10 19:05:20 2010 +0100
1.2 +++ b/INSTALL Fri Feb 12 22:24:26 2010 +0100
1.3 @@ -173,3 +173,25 @@
1.4 --without-coin
1.5
1.6 Disable COIN-OR support.
1.7 +
1.8 +
1.9 +Makefile Variables
1.10 +==================
1.11 +
1.12 +Some Makefile variables are reserved by the GNU Coding Standards for
1.13 +the use of the "user" - the person building the package. For instance,
1.14 +CXX and CXXFLAGS are such variables, and have the same meaning as
1.15 +explained in the previous section. These variables can be set on the
1.16 +command line when invoking `make' like this:
1.17 +`make [VARIABLE=VALUE]...'
1.18 +
1.19 +WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us
1.20 +to hold several compiler flags related to warnings. Its default value
1.21 +can be overridden when invoking `make'. For example to disable all
1.22 +warning flags use `make WARNINGCXXFLAGS='.
1.23 +
1.24 +In order to turn off a single flag from the default set of warning
1.25 +flags, you can use the CXXFLAGS variable, since this is passed after
1.26 +WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is
1.27 +used by default when g++ is detected) you can use
1.28 +`make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.
2.1 --- a/doc/CMakeLists.txt Wed Feb 10 19:05:20 2010 +0100
2.2 +++ b/doc/CMakeLists.txt Fri Feb 12 22:24:26 2010 +0100
2.3 @@ -26,6 +26,7 @@
2.4 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
2.5 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
2.6 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
2.7 + COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
2.8 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
2.9 COMMAND ${CMAKE_COMMAND} -E remove_directory html
2.10 COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
3.1 --- a/doc/Makefile.am Wed Feb 10 19:05:20 2010 +0100
3.2 +++ b/doc/Makefile.am Fri Feb 12 22:24:26 2010 +0100
3.3 @@ -28,6 +28,7 @@
3.4 connected_components.eps \
3.5 edge_biconnected_components.eps \
3.6 node_biconnected_components.eps \
3.7 + planar.eps \
3.8 strongly_connected_components.eps
3.9
3.10 DOC_EPS_IMAGES = \
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/doc/images/planar.eps Fri Feb 12 22:24:26 2010 +0100
4.3 @@ -0,0 +1,181 @@
4.4 +%!PS-Adobe-2.0 EPSF-2.0
4.5 +%%Creator: LEMON, graphToEps()
4.6 +%%CreationDate: Fri Oct 19 18:32:32 2007
4.7 +%%BoundingBox: 0 0 596 842
4.8 +%%DocumentPaperSizes: a4
4.9 +%%EndComments
4.10 +/lb { setlinewidth setrgbcolor newpath moveto
4.11 + 4 2 roll 1 index 1 index curveto stroke } bind def
4.12 +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
4.13 +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
4.14 +/sq { newpath 2 index 1 index add 2 index 2 index add moveto
4.15 + 2 index 1 index sub 2 index 2 index add lineto
4.16 + 2 index 1 index sub 2 index 2 index sub lineto
4.17 + 2 index 1 index add 2 index 2 index sub lineto
4.18 + closepath pop pop pop} bind def
4.19 +/di { newpath 2 index 1 index add 2 index moveto
4.20 + 2 index 2 index 2 index add lineto
4.21 + 2 index 1 index sub 2 index lineto
4.22 + 2 index 2 index 2 index sub lineto
4.23 + closepath pop pop pop} bind def
4.24 +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
4.25 + setrgbcolor 1.1 div c fill
4.26 + } bind def
4.27 +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
4.28 + setrgbcolor 1.1 div sq fill
4.29 + } bind def
4.30 +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
4.31 + setrgbcolor 1.1 div di fill
4.32 + } bind def
4.33 +/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
4.34 + newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
4.35 + lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
4.36 + 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
4.37 + 5 index 5 index 5 index c fill
4.38 + setrgbcolor 1.1 div c fill
4.39 + } bind def
4.40 +/nmale {
4.41 + 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
4.42 + newpath 5 index 5 index moveto
4.43 + 5 index 4 index 1 mul 1.5 mul add
4.44 + 5 index 5 index 3 sqrt 1.5 mul mul add
4.45 + 1 index 1 index lineto
4.46 + 1 index 1 index 7 index sub moveto
4.47 + 1 index 1 index lineto
4.48 + exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
4.49 + stroke
4.50 + 5 index 5 index 5 index c fill
4.51 + setrgbcolor 1.1 div c fill
4.52 + } bind def
4.53 +/arrl 1 def
4.54 +/arrw 0.3 def
4.55 +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
4.56 +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
4.57 + /w exch def /len exch def
4.58 + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
4.59 + len w sub arrl sub dx dy lrl
4.60 + arrw dy dx neg lrl
4.61 + dx arrl w add mul dy w 2 div arrw add mul sub
4.62 + dy arrl w add mul dx w 2 div arrw add mul add rlineto
4.63 + dx arrl w add mul neg dy w 2 div arrw add mul sub
4.64 + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
4.65 + arrw dy dx neg lrl
4.66 + len w sub arrl sub neg dx dy lrl
4.67 + closepath fill } bind def
4.68 +/cshow { 2 index 2 index moveto dup stringwidth pop
4.69 + neg 2 div fosi .35 mul neg rmoveto show pop pop} def
4.70 +
4.71 +gsave
4.72 +15 138.307 translate
4.73 +12.7843 dup scale
4.74 +90 rotate
4.75 +0.608112 -43.6081 translate
4.76 +%Edges:
4.77 +gsave
4.78 +9 31 9.5 30.5 10 30 0 0 0 0.091217 lb
4.79 +9 31 5.5 34.5 2 38 0 0 0 0.091217 lb
4.80 +9 31 25.5 16 42 1 0 0 0 0.091217 lb
4.81 +3 40 23 20.5 43 1 0 0 0 0.091217 lb
4.82 +3 40 22.5 20.5 42 1 0 0 0 0.091217 lb
4.83 +3 40 2.5 40.5 2 41 0 0 0 0.091217 lb
4.84 +13 25 10.5 24.5 8 24 0 0 0 0.091217 lb
4.85 +13 25 12 27 11 29 0 0 0 0.091217 lb
4.86 +3 4 2.5 3 2 2 0 0 0 0.091217 lb
4.87 +3 4 4.5 3 6 2 0 0 0 0.091217 lb
4.88 +6 25 7 24.5 8 24 0 0 0 0.091217 lb
4.89 +6 25 6 24.5 6 24 0 0 0 0.091217 lb
4.90 +34 2 33.5 2 33 2 0 0 0 0.091217 lb
4.91 +34 2 35 2 36 2 0 0 0 0.091217 lb
4.92 +6 8 16 9 26 10 0 0 0 0.091217 lb
4.93 +6 8 6 10.5 6 13 0 0 0 0.091217 lb
4.94 +6 8 6 7.5 6 7 0 0 0 0.091217 lb
4.95 +26 10 27.5 8.5 29 7 0 0 0 0.091217 lb
4.96 +26 10 27.5 9 29 8 0 0 0 0.091217 lb
4.97 +10 30 10.5 29.5 11 29 0 0 0 0.091217 lb
4.98 +8 24 7 23.5 6 23 0 0 0 0.091217 lb
4.99 +8 24 8 24.5 8 25 0 0 0 0.091217 lb
4.100 +33 2 32.5 2 32 2 0 0 0 0.091217 lb
4.101 +29 7 17.5 7 6 7 0 0 0 0.091217 lb
4.102 +2 2 1.5 22 1 42 0 0 0 0.091217 lb
4.103 +2 2 3.5 2 5 2 0 0 0 0.091217 lb
4.104 +21 15 13.5 14.5 6 14 0 0 0 0.091217 lb
4.105 +21 15 21 15.5 21 16 0 0 0 0.091217 lb
4.106 +1 42 0.5 42.5 0 43 0 0 0 0.091217 lb
4.107 +1 42 1.5 41.5 2 41 0 0 0 0.091217 lb
4.108 +6 15 6 15.5 6 16 0 0 0 0.091217 lb
4.109 +6 15 6 14.5 6 14 0 0 0 0.091217 lb
4.110 +43 1 22 0.5 1 0 0 0 0 0.091217 lb
4.111 +31 2 18.5 2 6 2 0 0 0 0.091217 lb
4.112 +31 2 31.5 2 32 2 0 0 0 0.091217 lb
4.113 +6 24 6 23.5 6 23 0 0 0 0.091217 lb
4.114 +6 16 6 16.5 6 17 0 0 0 0.091217 lb
4.115 +6 23 6 20 6 17 0 0 0 0.091217 lb
4.116 +6 2 5.5 2 5 2 0 0 0 0.091217 lb
4.117 +6 2 6 4.5 6 7 0 0 0 0.091217 lb
4.118 +0 43 0.5 21.5 1 0 0 0 0 0.091217 lb
4.119 +1 1 19.5 1.5 38 2 0 0 0 0.091217 lb
4.120 +1 1 1 0.5 1 0 0 0 0 0.091217 lb
4.121 +2 38 5.5 31.5 9 25 0 0 0 0.091217 lb
4.122 +25 13 15.5 13 6 13 0 0 0 0.091217 lb
4.123 +25 13 15.5 13.5 6 14 0 0 0 0.091217 lb
4.124 +8 25 8.5 25 9 25 0 0 0 0.091217 lb
4.125 +11 29 24.5 15.5 38 2 0 0 0 0.091217 lb
4.126 +6 17 11.5 18 17 19 0 0 0 0.091217 lb
4.127 +16 23 26.5 12.5 37 2 0 0 0 0.091217 lb
4.128 +16 23 18.5 19.5 21 16 0 0 0 0.091217 lb
4.129 +36 2 36.5 2 37 2 0 0 0 0.091217 lb
4.130 +36 2 32.5 5 29 8 0 0 0 0.091217 lb
4.131 +6 13 6 13.5 6 14 0 0 0 0.091217 lb
4.132 +37 2 37.5 2 38 2 0 0 0 0.091217 lb
4.133 +21 16 19 17.5 17 19 0 0 0 0.091217 lb
4.134 +grestore
4.135 +%Nodes:
4.136 +gsave
4.137 +29 8 0.304556 1 1 1 nc
4.138 +2 41 0.304556 1 1 1 nc
4.139 +6 7 0.304556 1 1 1 nc
4.140 +5 2 0.304556 1 1 1 nc
4.141 +17 19 0.304556 1 1 1 nc
4.142 +21 16 0.304556 1 1 1 nc
4.143 +1 0 0.304556 1 1 1 nc
4.144 +9 25 0.304556 1 1 1 nc
4.145 +6 14 0.304556 1 1 1 nc
4.146 +42 1 0.304556 1 1 1 nc
4.147 +38 2 0.304556 1 1 1 nc
4.148 +37 2 0.304556 1 1 1 nc
4.149 +6 13 0.304556 1 1 1 nc
4.150 +36 2 0.304556 1 1 1 nc
4.151 +16 23 0.304556 1 1 1 nc
4.152 +6 17 0.304556 1 1 1 nc
4.153 +11 29 0.304556 1 1 1 nc
4.154 +8 25 0.304556 1 1 1 nc
4.155 +32 2 0.304556 1 1 1 nc
4.156 +25 13 0.304556 1 1 1 nc
4.157 +2 38 0.304556 1 1 1 nc
4.158 +1 1 0.304556 1 1 1 nc
4.159 +0 43 0.304556 1 1 1 nc
4.160 +6 2 0.304556 1 1 1 nc
4.161 +6 23 0.304556 1 1 1 nc
4.162 +6 16 0.304556 1 1 1 nc
4.163 +6 24 0.304556 1 1 1 nc
4.164 +31 2 0.304556 1 1 1 nc
4.165 +43 1 0.304556 1 1 1 nc
4.166 +6 15 0.304556 1 1 1 nc
4.167 +1 42 0.304556 1 1 1 nc
4.168 +21 15 0.304556 1 1 1 nc
4.169 +2 2 0.304556 1 1 1 nc
4.170 +29 7 0.304556 1 1 1 nc
4.171 +33 2 0.304556 1 1 1 nc
4.172 +8 24 0.304556 1 1 1 nc
4.173 +10 30 0.304556 1 1 1 nc
4.174 +26 10 0.304556 1 1 1 nc
4.175 +6 8 0.304556 1 1 1 nc
4.176 +34 2 0.304556 1 1 1 nc
4.177 +6 25 0.304556 1 1 1 nc
4.178 +3 4 0.304556 1 1 1 nc
4.179 +13 25 0.304556 1 1 1 nc
4.180 +3 40 0.304556 1 1 1 nc
4.181 +9 31 0.304556 1 1 1 nc
4.182 +grestore
4.183 +grestore
4.184 +showpage
5.1 --- a/lemon/bellman_ford.h Wed Feb 10 19:05:20 2010 +0100
5.2 +++ b/lemon/bellman_ford.h Fri Feb 12 22:24:26 2010 +0100
5.3 @@ -171,6 +171,11 @@
5.4 /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
5.5 /// the lengths of the arcs. The default map type is
5.6 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
5.7 + /// \tparam TR The traits class that defines various types used by the
5.8 + /// algorithm. By default, it is \ref BellmanFordDefaultTraits
5.9 + /// "BellmanFordDefaultTraits<GR, LEN>".
5.10 + /// In most cases, this parameter should not be set directly,
5.11 + /// consider to use the named template parameters instead.
5.12 #ifdef DOXYGEN
5.13 template <typename GR, typename LEN, typename TR>
5.14 #else
5.15 @@ -933,6 +938,9 @@
5.16 ///
5.17 /// This class should only be used through the \ref bellmanFord()
5.18 /// function, which makes it easier to use the algorithm.
5.19 + ///
5.20 + /// \tparam TR The traits class that defines various types used by the
5.21 + /// algorithm.
5.22 template<class TR>
5.23 class BellmanFordWizard : public TR {
5.24 typedef TR Base;
6.1 --- a/lemon/bfs.h Wed Feb 10 19:05:20 2010 +0100
6.2 +++ b/lemon/bfs.h Fri Feb 12 22:24:26 2010 +0100
6.3 @@ -121,6 +121,11 @@
6.4 ///
6.5 ///\tparam GR The type of the digraph the algorithm runs on.
6.6 ///The default type is \ref ListDigraph.
6.7 + ///\tparam TR The traits class that defines various types used by the
6.8 + ///algorithm. By default, it is \ref BfsDefaultTraits
6.9 + ///"BfsDefaultTraits<GR>".
6.10 + ///In most cases, this parameter should not be set directly,
6.11 + ///consider to use the named template parameters instead.
6.12 #ifdef DOXYGEN
6.13 template <typename GR,
6.14 typename TR>
6.15 @@ -957,6 +962,9 @@
6.16 ///
6.17 /// This class should only be used through the \ref bfs() function,
6.18 /// which makes it easier to use the algorithm.
6.19 + ///
6.20 + /// \tparam TR The traits class that defines various types used by the
6.21 + /// algorithm.
6.22 template<class TR>
6.23 class BfsWizard : public TR
6.24 {
6.25 @@ -1295,11 +1303,11 @@
6.26 /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
6.27 /// does not observe the BFS events. If you want to observe the BFS
6.28 /// events, you should implement your own visitor class.
6.29 - /// \tparam TR Traits class to set various data types used by the
6.30 - /// algorithm. The default traits class is
6.31 - /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
6.32 - /// See \ref BfsVisitDefaultTraits for the documentation of
6.33 - /// a BFS visit traits class.
6.34 + /// \tparam TR The traits class that defines various types used by the
6.35 + /// algorithm. By default, it is \ref BfsVisitDefaultTraits
6.36 + /// "BfsVisitDefaultTraits<GR>".
6.37 + /// In most cases, this parameter should not be set directly,
6.38 + /// consider to use the named template parameters instead.
6.39 #ifdef DOXYGEN
6.40 template <typename GR, typename VS, typename TR>
6.41 #else
7.1 --- a/lemon/capacity_scaling.h Wed Feb 10 19:05:20 2010 +0100
7.2 +++ b/lemon/capacity_scaling.h Fri Feb 12 22:24:26 2010 +0100
7.3 @@ -77,9 +77,14 @@
7.4 ///
7.5 /// \tparam GR The digraph type the algorithm runs on.
7.6 /// \tparam V The number type used for flow amounts, capacity bounds
7.7 - /// and supply values in the algorithm. By default it is \c int.
7.8 + /// and supply values in the algorithm. By default, it is \c int.
7.9 /// \tparam C The number type used for costs and potentials in the
7.10 - /// algorithm. By default it is the same as \c V.
7.11 + /// algorithm. By default, it is the same as \c V.
7.12 + /// \tparam TR The traits class that defines various types used by the
7.13 + /// algorithm. By default, it is \ref CapacityScalingDefaultTraits
7.14 + /// "CapacityScalingDefaultTraits<GR, V, C>".
7.15 + /// In most cases, this parameter should not be set directly,
7.16 + /// consider to use the named template parameters instead.
7.17 ///
7.18 /// \warning Both number types must be signed and all input data must
7.19 /// be integer.
8.1 --- a/lemon/circulation.h Wed Feb 10 19:05:20 2010 +0100
8.2 +++ b/lemon/circulation.h Fri Feb 12 22:24:26 2010 +0100
8.3 @@ -173,6 +173,11 @@
8.4 The default map type is \c LM.
8.5 \tparam SM The type of the supply map. The default map type is
8.6 \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
8.7 + \tparam TR The traits class that defines various types used by the
8.8 + algorithm. By default, it is \ref CirculationDefaultTraits
8.9 + "CirculationDefaultTraits<GR, LM, UM, SM>".
8.10 + In most cases, this parameter should not be set directly,
8.11 + consider to use the named template parameters instead.
8.12 */
8.13 #ifdef DOXYGEN
8.14 template< typename GR,
9.1 --- a/lemon/cost_scaling.h Wed Feb 10 19:05:20 2010 +0100
9.2 +++ b/lemon/cost_scaling.h Fri Feb 12 22:24:26 2010 +0100
9.3 @@ -104,9 +104,14 @@
9.4 ///
9.5 /// \tparam GR The digraph type the algorithm runs on.
9.6 /// \tparam V The number type used for flow amounts, capacity bounds
9.7 - /// and supply values in the algorithm. By default it is \c int.
9.8 + /// and supply values in the algorithm. By default, it is \c int.
9.9 /// \tparam C The number type used for costs and potentials in the
9.10 - /// algorithm. By default it is the same as \c V.
9.11 + /// algorithm. By default, it is the same as \c V.
9.12 + /// \tparam TR The traits class that defines various types used by the
9.13 + /// algorithm. By default, it is \ref CostScalingDefaultTraits
9.14 + /// "CostScalingDefaultTraits<GR, V, C>".
9.15 + /// In most cases, this parameter should not be set directly,
9.16 + /// consider to use the named template parameters instead.
9.17 ///
9.18 /// \warning Both number types must be signed and all input data must
9.19 /// be integer.
9.20 @@ -136,8 +141,7 @@
9.21 /// \brief The large cost type
9.22 ///
9.23 /// The large cost type used for internal computations.
9.24 - /// Using the \ref CostScalingDefaultTraits "default traits class",
9.25 - /// it is \c long \c long if the \c Cost type is integer,
9.26 + /// By default, it is \c long \c long if the \c Cost type is integer,
9.27 /// otherwise it is \c double.
9.28 typedef typename TR::LargeCost LargeCost;
9.29
10.1 --- a/lemon/dfs.h Wed Feb 10 19:05:20 2010 +0100
10.2 +++ b/lemon/dfs.h Fri Feb 12 22:24:26 2010 +0100
10.3 @@ -121,6 +121,11 @@
10.4 ///
10.5 ///\tparam GR The type of the digraph the algorithm runs on.
10.6 ///The default type is \ref ListDigraph.
10.7 + ///\tparam TR The traits class that defines various types used by the
10.8 + ///algorithm. By default, it is \ref DfsDefaultTraits
10.9 + ///"DfsDefaultTraits<GR>".
10.10 + ///In most cases, this parameter should not be set directly,
10.11 + ///consider to use the named template parameters instead.
10.12 #ifdef DOXYGEN
10.13 template <typename GR,
10.14 typename TR>
10.15 @@ -887,6 +892,9 @@
10.16 ///
10.17 /// This class should only be used through the \ref dfs() function,
10.18 /// which makes it easier to use the algorithm.
10.19 + ///
10.20 + /// \tparam TR The traits class that defines various types used by the
10.21 + /// algorithm.
10.22 template<class TR>
10.23 class DfsWizard : public TR
10.24 {
10.25 @@ -1237,11 +1245,11 @@
10.26 /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
10.27 /// does not observe the DFS events. If you want to observe the DFS
10.28 /// events, you should implement your own visitor class.
10.29 - /// \tparam TR Traits class to set various data types used by the
10.30 - /// algorithm. The default traits class is
10.31 - /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
10.32 - /// See \ref DfsVisitDefaultTraits for the documentation of
10.33 - /// a DFS visit traits class.
10.34 + /// \tparam TR The traits class that defines various types used by the
10.35 + /// algorithm. By default, it is \ref DfsVisitDefaultTraits
10.36 + /// "DfsVisitDefaultTraits<GR>".
10.37 + /// In most cases, this parameter should not be set directly,
10.38 + /// consider to use the named template parameters instead.
10.39 #ifdef DOXYGEN
10.40 template <typename GR, typename VS, typename TR>
10.41 #else
11.1 --- a/lemon/dijkstra.h Wed Feb 10 19:05:20 2010 +0100
11.2 +++ b/lemon/dijkstra.h Fri Feb 12 22:24:26 2010 +0100
11.3 @@ -192,6 +192,11 @@
11.4 ///relatively time consuming process to compute the arc lengths if
11.5 ///it is necessary. The default map type is \ref
11.6 ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
11.7 + ///\tparam TR The traits class that defines various types used by the
11.8 + ///algorithm. By default, it is \ref DijkstraDefaultTraits
11.9 + ///"DijkstraDefaultTraits<GR, LEN>".
11.10 + ///In most cases, this parameter should not be set directly,
11.11 + ///consider to use the named template parameters instead.
11.12 #ifdef DOXYGEN
11.13 template <typename GR, typename LEN, typename TR>
11.14 #else
11.15 @@ -1092,6 +1097,9 @@
11.16 ///
11.17 /// This class should only be used through the \ref dijkstra() function,
11.18 /// which makes it easier to use the algorithm.
11.19 + ///
11.20 + /// \tparam TR The traits class that defines various types used by the
11.21 + /// algorithm.
11.22 template<class TR>
11.23 class DijkstraWizard : public TR
11.24 {
12.1 --- a/lemon/hartmann_orlin.h Wed Feb 10 19:05:20 2010 +0100
12.2 +++ b/lemon/hartmann_orlin.h Fri Feb 12 22:24:26 2010 +0100
12.3 @@ -106,6 +106,11 @@
12.4 /// \tparam GR The type of the digraph the algorithm runs on.
12.5 /// \tparam LEN The type of the length map. The default
12.6 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
12.7 + /// \tparam TR The traits class that defines various types used by the
12.8 + /// algorithm. By default, it is \ref HartmannOrlinDefaultTraits
12.9 + /// "HartmannOrlinDefaultTraits<GR, LEN>".
12.10 + /// In most cases, this parameter should not be set directly,
12.11 + /// consider to use the named template parameters instead.
12.12 #ifdef DOXYGEN
12.13 template <typename GR, typename LEN, typename TR>
12.14 #else
12.15 @@ -127,8 +132,7 @@
12.16 /// \brief The large value type
12.17 ///
12.18 /// The large value type used for internal computations.
12.19 - /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
12.20 - /// it is \c long \c long if the \c Value type is integer,
12.21 + /// By default, it is \c long \c long if the \c Value type is integer,
12.22 /// otherwise it is \c double.
12.23 typedef typename TR::LargeValue LargeValue;
12.24
13.1 --- a/lemon/howard.h Wed Feb 10 19:05:20 2010 +0100
13.2 +++ b/lemon/howard.h Fri Feb 12 22:24:26 2010 +0100
13.3 @@ -106,6 +106,11 @@
13.4 /// \tparam GR The type of the digraph the algorithm runs on.
13.5 /// \tparam LEN The type of the length map. The default
13.6 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
13.7 + /// \tparam TR The traits class that defines various types used by the
13.8 + /// algorithm. By default, it is \ref HowardDefaultTraits
13.9 + /// "HowardDefaultTraits<GR, LEN>".
13.10 + /// In most cases, this parameter should not be set directly,
13.11 + /// consider to use the named template parameters instead.
13.12 #ifdef DOXYGEN
13.13 template <typename GR, typename LEN, typename TR>
13.14 #else
13.15 @@ -127,8 +132,7 @@
13.16 /// \brief The large value type
13.17 ///
13.18 /// The large value type used for internal computations.
13.19 - /// Using the \ref HowardDefaultTraits "default traits class",
13.20 - /// it is \c long \c long if the \c Value type is integer,
13.21 + /// By default, it is \c long \c long if the \c Value type is integer,
13.22 /// otherwise it is \c double.
13.23 typedef typename TR::LargeValue LargeValue;
13.24
14.1 --- a/lemon/karp.h Wed Feb 10 19:05:20 2010 +0100
14.2 +++ b/lemon/karp.h Fri Feb 12 22:24:26 2010 +0100
14.3 @@ -104,6 +104,11 @@
14.4 /// \tparam GR The type of the digraph the algorithm runs on.
14.5 /// \tparam LEN The type of the length map. The default
14.6 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
14.7 + /// \tparam TR The traits class that defines various types used by the
14.8 + /// algorithm. By default, it is \ref KarpDefaultTraits
14.9 + /// "KarpDefaultTraits<GR, LEN>".
14.10 + /// In most cases, this parameter should not be set directly,
14.11 + /// consider to use the named template parameters instead.
14.12 #ifdef DOXYGEN
14.13 template <typename GR, typename LEN, typename TR>
14.14 #else
14.15 @@ -125,8 +130,7 @@
14.16 /// \brief The large value type
14.17 ///
14.18 /// The large value type used for internal computations.
14.19 - /// Using the \ref KarpDefaultTraits "default traits class",
14.20 - /// it is \c long \c long if the \c Value type is integer,
14.21 + /// By default, it is \c long \c long if the \c Value type is integer,
14.22 /// otherwise it is \c double.
14.23 typedef typename TR::LargeValue LargeValue;
14.24
15.1 --- a/lemon/min_cost_arborescence.h Wed Feb 10 19:05:20 2010 +0100
15.2 +++ b/lemon/min_cost_arborescence.h Fri Feb 12 22:24:26 2010 +0100
15.3 @@ -112,17 +112,18 @@
15.4 /// relatively time consuming process to compute the arc costs if
15.5 /// it is necessary. The default map type is \ref
15.6 /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
15.7 - /// \param TR Traits class to set various data types used
15.8 - /// by the algorithm. The default traits class is
15.9 - /// \ref MinCostArborescenceDefaultTraits
15.10 + /// \tparam TR The traits class that defines various types used by the
15.11 + /// algorithm. By default, it is \ref MinCostArborescenceDefaultTraits
15.12 /// "MinCostArborescenceDefaultTraits<GR, CM>".
15.13 + /// In most cases, this parameter should not be set directly,
15.14 + /// consider to use the named template parameters instead.
15.15 #ifndef DOXYGEN
15.16 template <typename GR,
15.17 typename CM = typename GR::template ArcMap<int>,
15.18 typename TR =
15.19 MinCostArborescenceDefaultTraits<GR, CM> >
15.20 #else
15.21 - template <typename GR, typename CM, typedef TR>
15.22 + template <typename GR, typename CM, typename TR>
15.23 #endif
15.24 class MinCostArborescence {
15.25 public:
16.1 --- a/lemon/planarity.h Wed Feb 10 19:05:20 2010 +0100
16.2 +++ b/lemon/planarity.h Fri Feb 12 22:24:26 2010 +0100
16.3 @@ -518,9 +518,9 @@
16.4 /// \brief Planarity checking of an undirected simple graph
16.5 ///
16.6 /// This function implements the Boyer-Myrvold algorithm for
16.7 - /// planarity checking of an undirected graph. It is a simplified
16.8 + /// planarity checking of an undirected simple graph. It is a simplified
16.9 /// version of the PlanarEmbedding algorithm class because neither
16.10 - /// the embedding nor the kuratowski subdivisons are not computed.
16.11 + /// the embedding nor the Kuratowski subdivisons are computed.
16.12 template <typename GR>
16.13 bool checkPlanarity(const GR& graph) {
16.14 _planarity_bits::PlanarityChecking<GR> pc(graph);
16.15 @@ -532,16 +532,17 @@
16.16 /// \brief Planar embedding of an undirected simple graph
16.17 ///
16.18 /// This class implements the Boyer-Myrvold algorithm for planar
16.19 - /// embedding of an undirected graph. The planar embedding is an
16.20 + /// embedding of an undirected simple graph. The planar embedding is an
16.21 /// ordering of the outgoing edges of the nodes, which is a possible
16.22 /// configuration to draw the graph in the plane. If there is not
16.23 - /// such ordering then the graph contains a \f$ K_5 \f$ (full graph
16.24 - /// with 5 nodes) or a \f$ K_{3,3} \f$ (complete bipartite graph on
16.25 - /// 3 ANode and 3 BNode) subdivision.
16.26 + /// such ordering then the graph contains a K<sub>5</sub> (full graph
16.27 + /// with 5 nodes) or a K<sub>3,3</sub> (complete bipartite graph on
16.28 + /// 3 Red and 3 Blue nodes) subdivision.
16.29 ///
16.30 /// The current implementation calculates either an embedding or a
16.31 - /// Kuratowski subdivision. The running time of the algorithm is
16.32 - /// \f$ O(n) \f$.
16.33 + /// Kuratowski subdivision. The running time of the algorithm is O(n).
16.34 + ///
16.35 + /// \see PlanarDrawing, checkPlanarity()
16.36 template <typename Graph>
16.37 class PlanarEmbedding {
16.38 private:
16.39 @@ -591,22 +592,26 @@
16.40
16.41 public:
16.42
16.43 - /// \brief The map for store of embedding
16.44 + /// \brief The map type for storing the embedding
16.45 + ///
16.46 + /// The map type for storing the embedding.
16.47 + /// \see embeddingMap()
16.48 typedef typename Graph::template ArcMap<Arc> EmbeddingMap;
16.49
16.50 /// \brief Constructor
16.51 ///
16.52 - /// \note The graph should be simple, i.e. parallel and loop arc
16.53 - /// free.
16.54 + /// Constructor.
16.55 + /// \pre The graph must be simple, i.e. it should not
16.56 + /// contain parallel or loop arcs.
16.57 PlanarEmbedding(const Graph& graph)
16.58 : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}
16.59
16.60 - /// \brief Runs the algorithm.
16.61 + /// \brief Run the algorithm.
16.62 ///
16.63 - /// Runs the algorithm.
16.64 - /// \param kuratowski If the parameter is false, then the
16.65 + /// This function runs the algorithm.
16.66 + /// \param kuratowski If this parameter is set to \c false, then the
16.67 /// algorithm does not compute a Kuratowski subdivision.
16.68 - ///\return %True when the graph is planar.
16.69 + /// \return \c true if the graph is planar.
16.70 bool run(bool kuratowski = true) {
16.71 typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
16.72
16.73 @@ -699,30 +704,32 @@
16.74 return true;
16.75 }
16.76
16.77 - /// \brief Gives back the successor of an arc
16.78 + /// \brief Give back the successor of an arc
16.79 ///
16.80 - /// Gives back the successor of an arc. This function makes
16.81 + /// This function gives back the successor of an arc. It makes
16.82 /// possible to query the cyclic order of the outgoing arcs from
16.83 /// a node.
16.84 Arc next(const Arc& arc) const {
16.85 return _embedding[arc];
16.86 }
16.87
16.88 - /// \brief Gives back the calculated embedding map
16.89 + /// \brief Give back the calculated embedding map
16.90 ///
16.91 - /// The returned map contains the successor of each arc in the
16.92 - /// graph.
16.93 + /// This function gives back the calculated embedding map, which
16.94 + /// contains the successor of each arc in the cyclic order of the
16.95 + /// outgoing arcs of its source node.
16.96 const EmbeddingMap& embeddingMap() const {
16.97 return _embedding;
16.98 }
16.99
16.100 - /// \brief Gives back true if the undirected arc is in the
16.101 - /// kuratowski subdivision
16.102 + /// \brief Give back \c true if the given edge is in the Kuratowski
16.103 + /// subdivision
16.104 ///
16.105 - /// Gives back true if the undirected arc is in the kuratowski
16.106 - /// subdivision
16.107 - /// \note The \c run() had to be called with true value.
16.108 - bool kuratowski(const Edge& edge) {
16.109 + /// This function gives back \c true if the given edge is in the found
16.110 + /// Kuratowski subdivision.
16.111 + /// \pre The \c run() function must be called with \c true parameter
16.112 + /// before using this function.
16.113 + bool kuratowski(const Edge& edge) const {
16.114 return _kuratowski[edge];
16.115 }
16.116
16.117 @@ -2059,29 +2066,32 @@
16.118 /// \brief Schnyder's planar drawing algorithm
16.119 ///
16.120 /// The planar drawing algorithm calculates positions for the nodes
16.121 - /// in the plane which coordinates satisfy that if the arcs are
16.122 - /// represented with straight lines then they will not intersect
16.123 + /// in the plane. These coordinates satisfy that if the edges are
16.124 + /// represented with straight lines, then they will not intersect
16.125 /// each other.
16.126 ///
16.127 - /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid,
16.128 - /// i.e. each node will be located in the \c [0,n-2]x[0,n-2] square.
16.129 + /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid,
16.130 + /// i.e. each node will be located in the \c [0..n-2]x[0..n-2] square.
16.131 /// The time complexity of the algorithm is O(n).
16.132 + ///
16.133 + /// \see PlanarEmbedding
16.134 template <typename Graph>
16.135 class PlanarDrawing {
16.136 public:
16.137
16.138 TEMPLATE_GRAPH_TYPEDEFS(Graph);
16.139
16.140 - /// \brief The point type for store coordinates
16.141 + /// \brief The point type for storing coordinates
16.142 typedef dim2::Point<int> Point;
16.143 - /// \brief The map type for store coordinates
16.144 + /// \brief The map type for storing the coordinates of the nodes
16.145 typedef typename Graph::template NodeMap<Point> PointMap;
16.146
16.147
16.148 /// \brief Constructor
16.149 ///
16.150 /// Constructor
16.151 - /// \pre The graph should be simple, i.e. loop and parallel arc free.
16.152 + /// \pre The graph must be simple, i.e. it should not
16.153 + /// contain parallel or loop arcs.
16.154 PlanarDrawing(const Graph& graph)
16.155 : _graph(graph), _point_map(graph) {}
16.156
16.157 @@ -2366,10 +2376,10 @@
16.158
16.159 public:
16.160
16.161 - /// \brief Calculates the node positions
16.162 + /// \brief Calculate the node positions
16.163 ///
16.164 - /// This function calculates the node positions.
16.165 - /// \return %True if the graph is planar.
16.166 + /// This function calculates the node positions on the plane.
16.167 + /// \return \c true if the graph is planar.
16.168 bool run() {
16.169 PlanarEmbedding<Graph> pe(_graph);
16.170 if (!pe.run()) return false;
16.171 @@ -2378,12 +2388,13 @@
16.172 return true;
16.173 }
16.174
16.175 - /// \brief Calculates the node positions according to a
16.176 + /// \brief Calculate the node positions according to a
16.177 /// combinatorical embedding
16.178 ///
16.179 - /// This function calculates the node locations. The \c embedding
16.180 - /// parameter should contain a valid combinatorical embedding, i.e.
16.181 - /// a valid cyclic order of the arcs.
16.182 + /// This function calculates the node positions on the plane.
16.183 + /// The given \c embedding map should contain a valid combinatorical
16.184 + /// embedding, i.e. a valid cyclic order of the arcs.
16.185 + /// It can be computed using PlanarEmbedding.
16.186 template <typename EmbeddingMap>
16.187 void run(const EmbeddingMap& embedding) {
16.188 typedef SmartEdgeSet<Graph> AuxGraph;
16.189 @@ -2423,14 +2434,15 @@
16.190
16.191 /// \brief The coordinate of the given node
16.192 ///
16.193 - /// The coordinate of the given node.
16.194 + /// This function returns the coordinate of the given node.
16.195 Point operator[](const Node& node) const {
16.196 return _point_map[node];
16.197 }
16.198
16.199 - /// \brief Returns the grid embedding in a \e NodeMap.
16.200 + /// \brief Return the grid embedding in a node map
16.201 ///
16.202 - /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> .
16.203 + /// This function returns the grid embedding in a node map of
16.204 + /// \c dim2::Point<int> coordinates.
16.205 const PointMap& coords() const {
16.206 return _point_map;
16.207 }
16.208 @@ -2470,23 +2482,22 @@
16.209 /// \brief Coloring planar graphs
16.210 ///
16.211 /// The graph coloring problem is the coloring of the graph nodes
16.212 - /// that there are not adjacent nodes with the same color. The
16.213 - /// planar graphs can be always colored with four colors, it is
16.214 - /// proved by Appel and Haken and their proofs provide a quadratic
16.215 + /// so that there are no adjacent nodes with the same color. The
16.216 + /// planar graphs can always be colored with four colors, which is
16.217 + /// proved by Appel and Haken. Their proofs provide a quadratic
16.218 /// time algorithm for four coloring, but it could not be used to
16.219 - /// implement efficient algorithm. The five and six coloring can be
16.220 - /// made in linear time, but in this class the five coloring has
16.221 + /// implement an efficient algorithm. The five and six coloring can be
16.222 + /// made in linear time, but in this class, the five coloring has
16.223 /// quadratic worst case time complexity. The two coloring (if
16.224 /// possible) is solvable with a graph search algorithm and it is
16.225 /// implemented in \ref bipartitePartitions() function in LEMON. To
16.226 - /// decide whether the planar graph is three colorable is
16.227 - /// NP-complete.
16.228 + /// decide whether a planar graph is three colorable is NP-complete.
16.229 ///
16.230 /// This class contains member functions for calculate colorings
16.231 /// with five and six colors. The six coloring algorithm is a simple
16.232 /// greedy coloring on the backward minimum outgoing order of nodes.
16.233 - /// This order can be computed as in each phase the node with least
16.234 - /// outgoing arcs to unprocessed nodes is chosen. This order
16.235 + /// This order can be computed by selecting the node with least
16.236 + /// outgoing arcs to unprocessed nodes in each phase. This order
16.237 /// guarantees that when a node is chosen for coloring it has at
16.238 /// most five already colored adjacents. The five coloring algorithm
16.239 /// use the same method, but if the greedy approach fails to color
16.240 @@ -2499,15 +2510,19 @@
16.241
16.242 TEMPLATE_GRAPH_TYPEDEFS(Graph);
16.243
16.244 - /// \brief The map type for store color indexes
16.245 + /// \brief The map type for storing color indices
16.246 typedef typename Graph::template NodeMap<int> IndexMap;
16.247 - /// \brief The map type for store colors
16.248 + /// \brief The map type for storing colors
16.249 + ///
16.250 + /// The map type for storing colors.
16.251 + /// \see Palette, Color
16.252 typedef ComposeMap<Palette, IndexMap> ColorMap;
16.253
16.254 /// \brief Constructor
16.255 ///
16.256 - /// Constructor
16.257 - /// \pre The graph should be simple, i.e. loop and parallel arc free.
16.258 + /// Constructor.
16.259 + /// \pre The graph must be simple, i.e. it should not
16.260 + /// contain parallel or loop arcs.
16.261 PlanarColoring(const Graph& graph)
16.262 : _graph(graph), _color_map(graph), _palette(0) {
16.263 _palette.add(Color(1,0,0));
16.264 @@ -2518,47 +2533,47 @@
16.265 _palette.add(Color(0,1,1));
16.266 }
16.267
16.268 - /// \brief Returns the \e NodeMap of color indexes
16.269 + /// \brief Return the node map of color indices
16.270 ///
16.271 - /// Returns the \e NodeMap of color indexes. The values are in the
16.272 - /// range \c [0..4] or \c [0..5] according to the coloring method.
16.273 + /// This function returns the node map of color indices. The values are
16.274 + /// in the range \c [0..4] or \c [0..5] according to the coloring method.
16.275 IndexMap colorIndexMap() const {
16.276 return _color_map;
16.277 }
16.278
16.279 - /// \brief Returns the \e NodeMap of colors
16.280 + /// \brief Return the node map of colors
16.281 ///
16.282 - /// Returns the \e NodeMap of colors. The values are five or six
16.283 - /// distinct \ref lemon::Color "colors".
16.284 + /// This function returns the node map of colors. The values are among
16.285 + /// five or six distinct \ref lemon::Color "colors".
16.286 ColorMap colorMap() const {
16.287 return composeMap(_palette, _color_map);
16.288 }
16.289
16.290 - /// \brief Returns the color index of the node
16.291 + /// \brief Return the color index of the node
16.292 ///
16.293 - /// Returns the color index of the node. The values are in the
16.294 - /// range \c [0..4] or \c [0..5] according to the coloring method.
16.295 + /// This function returns the color index of the given node. The value is
16.296 + /// in the range \c [0..4] or \c [0..5] according to the coloring method.
16.297 int colorIndex(const Node& node) const {
16.298 return _color_map[node];
16.299 }
16.300
16.301 - /// \brief Returns the color of the node
16.302 + /// \brief Return the color of the node
16.303 ///
16.304 - /// Returns the color of the node. The values are five or six
16.305 - /// distinct \ref lemon::Color "colors".
16.306 + /// This function returns the color of the given node. The value is among
16.307 + /// five or six distinct \ref lemon::Color "colors".
16.308 Color color(const Node& node) const {
16.309 return _palette[_color_map[node]];
16.310 }
16.311
16.312
16.313 - /// \brief Calculates a coloring with at most six colors
16.314 + /// \brief Calculate a coloring with at most six colors
16.315 ///
16.316 /// This function calculates a coloring with at most six colors. The time
16.317 /// complexity of this variant is linear in the size of the graph.
16.318 - /// \return %True when the algorithm could color the graph with six color.
16.319 - /// If the algorithm fails, then the graph could not be planar.
16.320 - /// \note This function can return true if the graph is not
16.321 - /// planar but it can be colored with 6 colors.
16.322 + /// \return \c true if the algorithm could color the graph with six colors.
16.323 + /// If the algorithm fails, then the graph is not planar.
16.324 + /// \note This function can return \c true if the graph is not
16.325 + /// planar, but it can be colored with at most six colors.
16.326 bool runSixColoring() {
16.327
16.328 typename Graph::template NodeMap<int> heap_index(_graph, -1);
16.329 @@ -2660,11 +2675,14 @@
16.330
16.331 public:
16.332
16.333 - /// \brief Calculates a coloring with at most five colors
16.334 + /// \brief Calculate a coloring with at most five colors
16.335 ///
16.336 /// This function calculates a coloring with at most five
16.337 /// colors. The worst case time complexity of this variant is
16.338 /// quadratic in the size of the graph.
16.339 + /// \param embedding This map should contain a valid combinatorical
16.340 + /// embedding, i.e. a valid cyclic order of the arcs.
16.341 + /// It can be computed using PlanarEmbedding.
16.342 template <typename EmbeddingMap>
16.343 void runFiveColoring(const EmbeddingMap& embedding) {
16.344
16.345 @@ -2711,12 +2729,12 @@
16.346 }
16.347 }
16.348
16.349 - /// \brief Calculates a coloring with at most five colors
16.350 + /// \brief Calculate a coloring with at most five colors
16.351 ///
16.352 /// This function calculates a coloring with at most five
16.353 /// colors. The worst case time complexity of this variant is
16.354 /// quadratic in the size of the graph.
16.355 - /// \return %True when the graph is planar.
16.356 + /// \return \c true if the graph is planar.
16.357 bool runFiveColoring() {
16.358 PlanarEmbedding<Graph> pe(_graph);
16.359 if (!pe.run()) return false;
17.1 --- a/lemon/preflow.h Wed Feb 10 19:05:20 2010 +0100
17.2 +++ b/lemon/preflow.h Fri Feb 12 22:24:26 2010 +0100
17.3 @@ -119,6 +119,11 @@
17.4 /// \tparam GR The type of the digraph the algorithm runs on.
17.5 /// \tparam CAP The type of the capacity map. The default map
17.6 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
17.7 + /// \tparam TR The traits class that defines various types used by the
17.8 + /// algorithm. By default, it is \ref PreflowDefaultTraits
17.9 + /// "PreflowDefaultTraits<GR, CAP>".
17.10 + /// In most cases, this parameter should not be set directly,
17.11 + /// consider to use the named template parameters instead.
17.12 #ifdef DOXYGEN
17.13 template <typename GR, typename CAP, typename TR>
17.14 #else