Doc group for TSP algorithms (#386)
authorPeter Kovacs <kpeter@inf.elte.hu>
Sat, 08 Jan 2011 22:49:09 +0100
changeset 103262ba43576f85
parent 1031 ae0b056593a7
child 1033 9a51db038228
Doc group for TSP algorithms (#386)
doc/CMakeLists.txt
doc/Makefile.am
doc/groups.dox
doc/images/tsp.eps
     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