1.1 --- a/doc/CMakeLists.txt Sat Jan 08 21:59:56 2011 +0100
1.2 +++ b/doc/CMakeLists.txt Sat Jan 08 22:49:09 2011 +0100
1.3 @@ -31,6 +31,7 @@
1.4 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
1.5 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
1.6 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
1.7 + COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps
1.8 COMMAND ${CMAKE_COMMAND} -E remove_directory html
1.9 COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
1.10 COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
2.1 --- a/doc/Makefile.am Sat Jan 08 21:59:56 2011 +0100
2.2 +++ b/doc/Makefile.am Sat Jan 08 22:49:09 2011 +0100
2.3 @@ -30,7 +30,8 @@
2.4 matching.eps \
2.5 node_biconnected_components.eps \
2.6 planar.eps \
2.7 - strongly_connected_components.eps
2.8 + strongly_connected_components.eps \
2.9 + tsp.eps
2.10
2.11 DOC_EPS_IMAGES = \
2.12 $(DOC_EPS_IMAGES18) \
3.1 --- a/doc/groups.dox Sat Jan 08 21:59:56 2011 +0100
3.2 +++ b/doc/groups.dox Sat Jan 08 22:49:09 2011 +0100
3.3 @@ -549,6 +549,31 @@
3.4 \image html planar.png
3.5 \image latex planar.eps "Plane graph" width=\textwidth
3.6 */
3.7 +
3.8 +/**
3.9 +@defgroup tsp Traveling Salesman Problem
3.10 +@ingroup algs
3.11 +\brief Algorithms for the symmetric traveling salesman problem
3.12 +
3.13 +This group contains basic heuristic algorithms for the the symmetric
3.14 +\e traveling \e salesman \e problem (TSP).
3.15 +Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
3.16 +the problem is to find a shortest possible tour that visits each node exactly
3.17 +once (i.e. the minimum cost Hamiltonian cycle).
3.18 +
3.19 +These TSP algorithms should be used with a
3.20 +metric cost function. Otherwise, they could yield worse results.
3.21 +
3.22 +LEMON provides five well-known heuristics for solving symmetric TSP:
3.23 + - \ref NearestNeighborTsp Neareast neighbor algorithm
3.24 + - \ref GreedyTsp Greedy algorithm
3.25 + - \ref InsertionTsp Insertion heuristic (with four selection methods)
3.26 + - \ref ChristofidesTsp Christofides algorithm
3.27 + - \ref Opt2Tsp 2-opt algorithm
3.28 +
3.29 +\image html tsp.png
3.30 +\image latex tsp.eps "Traveling salesman problem" width=\textwidth
3.31 +*/
3.32
3.33 /**
3.34 @defgroup approx_algs Approximation Algorithms
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/doc/images/tsp.eps Sat Jan 08 22:49:09 2011 +0100
4.3 @@ -0,0 +1,229 @@
4.4 +%!PS-Adobe-2.0 EPSF-2.0
4.5 +%%Creator: LEMON, graphToEps()
4.6 +%%CreationDate: Tue Jun 15 00:58:57 2010
4.7 +%%BoundingBox: 31 41 649 709
4.8 +%%EndComments
4.9 +/lb { setlinewidth setrgbcolor newpath moveto
4.10 + 4 2 roll 1 index 1 index curveto stroke } bind def
4.11 +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
4.12 +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
4.13 +/sq { newpath 2 index 1 index add 2 index 2 index add moveto
4.14 + 2 index 1 index sub 2 index 2 index add lineto
4.15 + 2 index 1 index sub 2 index 2 index sub lineto
4.16 + 2 index 1 index add 2 index 2 index sub lineto
4.17 + closepath pop pop pop} bind def
4.18 +/di { newpath 2 index 1 index add 2 index moveto
4.19 + 2 index 2 index 2 index add lineto
4.20 + 2 index 1 index sub 2 index lineto
4.21 + 2 index 2 index 2 index sub lineto
4.22 + closepath pop pop pop} bind def
4.23 +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
4.24 + setrgbcolor 1.1 div c fill
4.25 + } bind def
4.26 +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
4.27 + setrgbcolor 1.1 div sq fill
4.28 + } bind def
4.29 +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
4.30 + setrgbcolor 1.1 div di fill
4.31 + } bind def
4.32 +/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
4.33 + newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
4.34 + lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
4.35 + 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
4.36 + 5 index 5 index 5 index c fill
4.37 + setrgbcolor 1.1 div c fill
4.38 + } bind def
4.39 +/nmale {
4.40 + 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
4.41 + newpath 5 index 5 index moveto
4.42 + 5 index 4 index 1 mul 1.5 mul add
4.43 + 5 index 5 index 3 sqrt 1.5 mul mul add
4.44 + 1 index 1 index lineto
4.45 + 1 index 1 index 7 index sub moveto
4.46 + 1 index 1 index lineto
4.47 + exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
4.48 + stroke
4.49 + 5 index 5 index 5 index c fill
4.50 + setrgbcolor 1.1 div c fill
4.51 + } bind def
4.52 +/arrl 1 def
4.53 +/arrw 0.3 def
4.54 +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
4.55 +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
4.56 + /w exch def /len exch def
4.57 + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
4.58 + len w sub arrl sub dx dy lrl
4.59 + arrw dy dx neg lrl
4.60 + dx arrl w add mul dy w 2 div arrw add mul sub
4.61 + dy arrl w add mul dx w 2 div arrw add mul add rlineto
4.62 + dx arrl w add mul neg dy w 2 div arrw add mul sub
4.63 + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
4.64 + arrw dy dx neg lrl
4.65 + len w sub arrl sub neg dx dy lrl
4.66 + closepath fill } bind def
4.67 +/cshow { 2 index 2 index moveto dup stringwidth pop
4.68 + neg 2 div fosi .35 mul neg rmoveto show pop pop} def
4.69 +
4.70 +gsave
4.71 +10 dup scale
4.72 +%Arcs:
4.73 +gsave
4.74 +27 68 37 69 0 0 1 0.513798 l
4.75 +37 69 27 68 0 0 1 0.513798 l
4.76 +8 52 5 64 0 0 1 0.513798 l
4.77 +5 64 8 52 0 0 1 0.513798 l
4.78 +16 57 25 55 0 0 1 0.513798 l
4.79 +25 55 16 57 0 0 1 0.513798 l
4.80 +43 67 37 69 0 0 1 0.513798 l
4.81 +37 69 43 67 0 0 1 0.513798 l
4.82 +42 57 43 67 0 0 1 0.513798 l
4.83 +43 67 42 57 0 0 1 0.513798 l
4.84 +62 42 61 33 0 0 1 0.513798 l
4.85 +61 33 62 42 0 0 1 0.513798 l
4.86 +62 42 58 48 0 0 1 0.513798 l
4.87 +58 48 62 42 0 0 1 0.513798 l
4.88 +58 27 61 33 0 0 1 0.513798 l
4.89 +61 33 58 27 0 0 1 0.513798 l
4.90 +57 58 62 63 0 0 1 0.513798 l
4.91 +62 63 57 58 0 0 1 0.513798 l
4.92 +13 13 21 10 0 0 1 0.513798 l
4.93 +21 10 13 13 0 0 1 0.513798 l
4.94 +13 13 5 6 0 0 1 0.513798 l
4.95 +5 6 13 13 0 0 1 0.513798 l
4.96 +17 33 7 38 0 0 1 0.513798 l
4.97 +7 38 17 33 0 0 1 0.513798 l
4.98 +46 10 59 15 0 0 1 0.513798 l
4.99 +59 15 46 10 0 0 1 0.513798 l
4.100 +46 10 39 10 0 0 1 0.513798 l
4.101 +39 10 46 10 0 0 1 0.513798 l
4.102 +27 23 21 10 0 0 1 0.513798 l
4.103 +21 10 27 23 0 0 1 0.513798 l
4.104 +52 41 56 37 0 0 1 0.513798 l
4.105 +56 37 52 41 0 0 1 0.513798 l
4.106 +62 63 63 69 0 0 1 0.513798 l
4.107 +63 69 62 63 0 0 1 0.513798 l
4.108 +36 16 39 10 0 0 1 0.513798 l
4.109 +39 10 36 16 0 0 1 0.513798 l
4.110 +36 16 30 15 0 0 1 0.513798 l
4.111 +30 15 36 16 0 0 1 0.513798 l
4.112 +12 42 7 38 0 0 1 0.513798 l
4.113 +7 38 12 42 0 0 1 0.513798 l
4.114 +12 42 8 52 0 0 1 0.513798 l
4.115 +8 52 12 42 0 0 1 0.513798 l
4.116 +32 22 30 15 0 0 1 0.513798 l
4.117 +30 15 32 22 0 0 1 0.513798 l
4.118 +5 25 10 17 0 0 1 0.513798 l
4.119 +10 17 5 25 0 0 1 0.513798 l
4.120 +5 25 17 33 0 0 1 0.513798 l
4.121 +17 33 5 25 0 0 1 0.513798 l
4.122 +45 35 48 28 0 0 1 0.513798 l
4.123 +48 28 45 35 0 0 1 0.513798 l
4.124 +31 32 25 32 0 0 1 0.513798 l
4.125 +25 32 31 32 0 0 1 0.513798 l
4.126 +31 32 32 39 0 0 1 0.513798 l
4.127 +32 39 31 32 0 0 1 0.513798 l
4.128 +42 41 38 46 0 0 1 0.513798 l
4.129 +38 46 42 41 0 0 1 0.513798 l
4.130 +42 41 52 41 0 0 1 0.513798 l
4.131 +52 41 42 41 0 0 1 0.513798 l
4.132 +5 6 10 17 0 0 1 0.513798 l
4.133 +10 17 5 6 0 0 1 0.513798 l
4.134 +51 21 59 15 0 0 1 0.513798 l
4.135 +59 15 51 21 0 0 1 0.513798 l
4.136 +51 21 58 27 0 0 1 0.513798 l
4.137 +58 27 51 21 0 0 1 0.513798 l
4.138 +52 33 56 37 0 0 1 0.513798 l
4.139 +56 37 52 33 0 0 1 0.513798 l
4.140 +52 33 48 28 0 0 1 0.513798 l
4.141 +48 28 52 33 0 0 1 0.513798 l
4.142 +31 62 25 55 0 0 1 0.513798 l
4.143 +25 55 31 62 0 0 1 0.513798 l
4.144 +31 62 27 68 0 0 1 0.513798 l
4.145 +27 68 31 62 0 0 1 0.513798 l
4.146 +17 63 5 64 0 0 1 0.513798 l
4.147 +5 64 17 63 0 0 1 0.513798 l
4.148 +17 63 16 57 0 0 1 0.513798 l
4.149 +16 57 17 63 0 0 1 0.513798 l
4.150 +21 47 30 40 0 0 1 0.513798 l
4.151 +30 40 21 47 0 0 1 0.513798 l
4.152 +21 47 30 48 0 0 1 0.513798 l
4.153 +30 48 21 47 0 0 1 0.513798 l
4.154 +40 30 45 35 0 0 1 0.513798 l
4.155 +45 35 40 30 0 0 1 0.513798 l
4.156 +40 30 32 22 0 0 1 0.513798 l
4.157 +32 22 40 30 0 0 1 0.513798 l
4.158 +32 39 30 40 0 0 1 0.513798 l
4.159 +30 40 32 39 0 0 1 0.513798 l
4.160 +20 26 25 32 0 0 1 0.513798 l
4.161 +25 32 20 26 0 0 1 0.513798 l
4.162 +20 26 27 23 0 0 1 0.513798 l
4.163 +27 23 20 26 0 0 1 0.513798 l
4.164 +52 64 63 69 0 0 1 0.513798 l
4.165 +63 69 52 64 0 0 1 0.513798 l
4.166 +52 64 42 57 0 0 1 0.513798 l
4.167 +42 57 52 64 0 0 1 0.513798 l
4.168 +49 49 58 48 0 0 1 0.513798 l
4.169 +58 48 49 49 0 0 1 0.513798 l
4.170 +49 49 57 58 0 0 1 0.513798 l
4.171 +57 58 49 49 0 0 1 0.513798 l
4.172 +37 52 38 46 0 0 1 0.513798 l
4.173 +38 46 37 52 0 0 1 0.513798 l
4.174 +37 52 30 48 0 0 1 0.513798 l
4.175 +30 48 37 52 0 0 1 0.513798 l
4.176 +grestore
4.177 +%Nodes:
4.178 +gsave
4.179 +30 40 0.856329 1 1 1 nc
4.180 +56 37 0.856329 1 1 1 nc
4.181 +48 28 0.856329 1 1 1 nc
4.182 +25 55 0.856329 1 1 1 nc
4.183 +25 32 0.856329 1 1 1 nc
4.184 +32 39 0.856329 1 1 1 nc
4.185 +39 10 0.856329 1 1 1 nc
4.186 +30 15 0.856329 1 1 1 nc
4.187 +5 64 0.856329 1 1 1 nc
4.188 +21 10 0.856329 1 1 1 nc
4.189 +10 17 0.856329 1 1 1 nc
4.190 +5 6 0.856329 1 1 1 nc
4.191 +59 15 0.856329 1 1 1 nc
4.192 +45 35 0.856329 1 1 1 nc
4.193 +32 22 0.856329 1 1 1 nc
4.194 +63 69 0.856329 1 1 1 nc
4.195 +62 63 0.856329 1 1 1 nc
4.196 +61 33 0.856329 1 1 1 nc
4.197 +46 10 0.856329 1 1 1 nc
4.198 +38 46 0.856329 1 1 1 nc
4.199 +37 69 0.856329 1 1 1 nc
4.200 +58 27 0.856329 1 1 1 nc
4.201 +58 48 0.856329 1 1 1 nc
4.202 +43 67 0.856329 1 1 1 nc
4.203 +30 48 0.856329 1 1 1 nc
4.204 +27 68 0.856329 1 1 1 nc
4.205 +7 38 0.856329 1 1 1 nc
4.206 +8 52 0.856329 1 1 1 nc
4.207 +16 57 0.856329 1 1 1 nc
4.208 +42 57 0.856329 1 1 1 nc
4.209 +62 42 0.856329 1 1 1 nc
4.210 +57 58 0.856329 1 1 1 nc
4.211 +13 13 0.856329 1 1 1 nc
4.212 +17 33 0.856329 1 1 1 nc
4.213 +27 23 0.856329 1 1 1 nc
4.214 +52 41 0.856329 1 1 1 nc
4.215 +36 16 0.856329 1 1 1 nc
4.216 +12 42 0.856329 1 1 1 nc
4.217 +5 25 0.856329 1 1 1 nc
4.218 +31 32 0.856329 1 1 1 nc
4.219 +42 41 0.856329 1 1 1 nc
4.220 +51 21 0.856329 1 1 1 nc
4.221 +52 33 0.856329 1 1 1 nc
4.222 +31 62 0.856329 1 1 1 nc
4.223 +17 63 0.856329 1 1 1 nc
4.224 +21 47 0.856329 1 1 1 nc
4.225 +40 30 0.856329 1 1 1 nc
4.226 +20 26 0.856329 1 1 1 nc
4.227 +52 64 0.856329 1 1 1 nc
4.228 +49 49 0.856329 1 1 1 nc
4.229 +37 52 0.856329 1 1 1 nc
4.230 +grestore
4.231 +grestore
4.232 +showpage