# HG changeset patch # User Peter Kovacs # Date 1294523349 -3600 # Node ID 62ba43576f85fa7947524d8aba59ac0bc2622919 # Parent ae0b056593a78cd4c06c43c14ae81abb2e3f4bb2 Doc group for TSP algorithms (#386) diff -r ae0b056593a7 -r 62ba43576f85 doc/CMakeLists.txt --- a/doc/CMakeLists.txt Sat Jan 08 21:59:56 2011 +0100 +++ b/doc/CMakeLists.txt Sat Jan 08 22:49:09 2011 +0100 @@ -31,6 +31,7 @@ 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 ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.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 COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile diff -r ae0b056593a7 -r 62ba43576f85 doc/Makefile.am --- a/doc/Makefile.am Sat Jan 08 21:59:56 2011 +0100 +++ b/doc/Makefile.am Sat Jan 08 22:49:09 2011 +0100 @@ -30,7 +30,8 @@ matching.eps \ node_biconnected_components.eps \ planar.eps \ - strongly_connected_components.eps + strongly_connected_components.eps \ + tsp.eps DOC_EPS_IMAGES = \ $(DOC_EPS_IMAGES18) \ diff -r ae0b056593a7 -r 62ba43576f85 doc/groups.dox --- a/doc/groups.dox Sat Jan 08 21:59:56 2011 +0100 +++ b/doc/groups.dox Sat Jan 08 22:49:09 2011 +0100 @@ -549,6 +549,31 @@ \image html planar.png \image latex planar.eps "Plane graph" width=\textwidth */ + +/** +@defgroup tsp Traveling Salesman Problem +@ingroup algs +\brief Algorithms for the symmetric traveling salesman problem + +This group contains basic heuristic algorithms for the the symmetric +\e traveling \e salesman \e problem (TSP). +Given an \ref FullGraph "undirected full graph" with a cost map on its edges, +the problem is to find a shortest possible tour that visits each node exactly +once (i.e. the minimum cost Hamiltonian cycle). + +These TSP algorithms should be used with a +metric cost function. Otherwise, they could yield worse results. + +LEMON provides five well-known heuristics for solving symmetric TSP: + - \ref NearestNeighborTsp Neareast neighbor algorithm + - \ref GreedyTsp Greedy algorithm + - \ref InsertionTsp Insertion heuristic (with four selection methods) + - \ref ChristofidesTsp Christofides algorithm + - \ref Opt2Tsp 2-opt algorithm + +\image html tsp.png +\image latex tsp.eps "Traveling salesman problem" width=\textwidth +*/ /** @defgroup approx_algs Approximation Algorithms diff -r ae0b056593a7 -r 62ba43576f85 doc/images/tsp.eps --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/images/tsp.eps Sat Jan 08 22:49:09 2011 +0100 @@ -0,0 +1,229 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Creator: LEMON, graphToEps() +%%CreationDate: Tue Jun 15 00:58:57 2010 +%%BoundingBox: 31 41 649 709 +%%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 +10 dup scale +%Arcs: +gsave +27 68 37 69 0 0 1 0.513798 l +37 69 27 68 0 0 1 0.513798 l +8 52 5 64 0 0 1 0.513798 l +5 64 8 52 0 0 1 0.513798 l +16 57 25 55 0 0 1 0.513798 l +25 55 16 57 0 0 1 0.513798 l +43 67 37 69 0 0 1 0.513798 l +37 69 43 67 0 0 1 0.513798 l +42 57 43 67 0 0 1 0.513798 l +43 67 42 57 0 0 1 0.513798 l +62 42 61 33 0 0 1 0.513798 l +61 33 62 42 0 0 1 0.513798 l +62 42 58 48 0 0 1 0.513798 l +58 48 62 42 0 0 1 0.513798 l +58 27 61 33 0 0 1 0.513798 l +61 33 58 27 0 0 1 0.513798 l +57 58 62 63 0 0 1 0.513798 l +62 63 57 58 0 0 1 0.513798 l +13 13 21 10 0 0 1 0.513798 l +21 10 13 13 0 0 1 0.513798 l +13 13 5 6 0 0 1 0.513798 l +5 6 13 13 0 0 1 0.513798 l +17 33 7 38 0 0 1 0.513798 l +7 38 17 33 0 0 1 0.513798 l +46 10 59 15 0 0 1 0.513798 l +59 15 46 10 0 0 1 0.513798 l +46 10 39 10 0 0 1 0.513798 l +39 10 46 10 0 0 1 0.513798 l +27 23 21 10 0 0 1 0.513798 l +21 10 27 23 0 0 1 0.513798 l +52 41 56 37 0 0 1 0.513798 l +56 37 52 41 0 0 1 0.513798 l +62 63 63 69 0 0 1 0.513798 l +63 69 62 63 0 0 1 0.513798 l +36 16 39 10 0 0 1 0.513798 l +39 10 36 16 0 0 1 0.513798 l +36 16 30 15 0 0 1 0.513798 l +30 15 36 16 0 0 1 0.513798 l +12 42 7 38 0 0 1 0.513798 l +7 38 12 42 0 0 1 0.513798 l +12 42 8 52 0 0 1 0.513798 l +8 52 12 42 0 0 1 0.513798 l +32 22 30 15 0 0 1 0.513798 l +30 15 32 22 0 0 1 0.513798 l +5 25 10 17 0 0 1 0.513798 l +10 17 5 25 0 0 1 0.513798 l +5 25 17 33 0 0 1 0.513798 l +17 33 5 25 0 0 1 0.513798 l +45 35 48 28 0 0 1 0.513798 l +48 28 45 35 0 0 1 0.513798 l +31 32 25 32 0 0 1 0.513798 l +25 32 31 32 0 0 1 0.513798 l +31 32 32 39 0 0 1 0.513798 l +32 39 31 32 0 0 1 0.513798 l +42 41 38 46 0 0 1 0.513798 l +38 46 42 41 0 0 1 0.513798 l +42 41 52 41 0 0 1 0.513798 l +52 41 42 41 0 0 1 0.513798 l +5 6 10 17 0 0 1 0.513798 l +10 17 5 6 0 0 1 0.513798 l +51 21 59 15 0 0 1 0.513798 l +59 15 51 21 0 0 1 0.513798 l +51 21 58 27 0 0 1 0.513798 l +58 27 51 21 0 0 1 0.513798 l +52 33 56 37 0 0 1 0.513798 l +56 37 52 33 0 0 1 0.513798 l +52 33 48 28 0 0 1 0.513798 l +48 28 52 33 0 0 1 0.513798 l +31 62 25 55 0 0 1 0.513798 l +25 55 31 62 0 0 1 0.513798 l +31 62 27 68 0 0 1 0.513798 l +27 68 31 62 0 0 1 0.513798 l +17 63 5 64 0 0 1 0.513798 l +5 64 17 63 0 0 1 0.513798 l +17 63 16 57 0 0 1 0.513798 l +16 57 17 63 0 0 1 0.513798 l +21 47 30 40 0 0 1 0.513798 l +30 40 21 47 0 0 1 0.513798 l +21 47 30 48 0 0 1 0.513798 l +30 48 21 47 0 0 1 0.513798 l +40 30 45 35 0 0 1 0.513798 l +45 35 40 30 0 0 1 0.513798 l +40 30 32 22 0 0 1 0.513798 l +32 22 40 30 0 0 1 0.513798 l +32 39 30 40 0 0 1 0.513798 l +30 40 32 39 0 0 1 0.513798 l +20 26 25 32 0 0 1 0.513798 l +25 32 20 26 0 0 1 0.513798 l +20 26 27 23 0 0 1 0.513798 l +27 23 20 26 0 0 1 0.513798 l +52 64 63 69 0 0 1 0.513798 l +63 69 52 64 0 0 1 0.513798 l +52 64 42 57 0 0 1 0.513798 l +42 57 52 64 0 0 1 0.513798 l +49 49 58 48 0 0 1 0.513798 l +58 48 49 49 0 0 1 0.513798 l +49 49 57 58 0 0 1 0.513798 l +57 58 49 49 0 0 1 0.513798 l +37 52 38 46 0 0 1 0.513798 l +38 46 37 52 0 0 1 0.513798 l +37 52 30 48 0 0 1 0.513798 l +30 48 37 52 0 0 1 0.513798 l +grestore +%Nodes: +gsave +30 40 0.856329 1 1 1 nc +56 37 0.856329 1 1 1 nc +48 28 0.856329 1 1 1 nc +25 55 0.856329 1 1 1 nc +25 32 0.856329 1 1 1 nc +32 39 0.856329 1 1 1 nc +39 10 0.856329 1 1 1 nc +30 15 0.856329 1 1 1 nc +5 64 0.856329 1 1 1 nc +21 10 0.856329 1 1 1 nc +10 17 0.856329 1 1 1 nc +5 6 0.856329 1 1 1 nc +59 15 0.856329 1 1 1 nc +45 35 0.856329 1 1 1 nc +32 22 0.856329 1 1 1 nc +63 69 0.856329 1 1 1 nc +62 63 0.856329 1 1 1 nc +61 33 0.856329 1 1 1 nc +46 10 0.856329 1 1 1 nc +38 46 0.856329 1 1 1 nc +37 69 0.856329 1 1 1 nc +58 27 0.856329 1 1 1 nc +58 48 0.856329 1 1 1 nc +43 67 0.856329 1 1 1 nc +30 48 0.856329 1 1 1 nc +27 68 0.856329 1 1 1 nc +7 38 0.856329 1 1 1 nc +8 52 0.856329 1 1 1 nc +16 57 0.856329 1 1 1 nc +42 57 0.856329 1 1 1 nc +62 42 0.856329 1 1 1 nc +57 58 0.856329 1 1 1 nc +13 13 0.856329 1 1 1 nc +17 33 0.856329 1 1 1 nc +27 23 0.856329 1 1 1 nc +52 41 0.856329 1 1 1 nc +36 16 0.856329 1 1 1 nc +12 42 0.856329 1 1 1 nc +5 25 0.856329 1 1 1 nc +31 32 0.856329 1 1 1 nc +42 41 0.856329 1 1 1 nc +51 21 0.856329 1 1 1 nc +52 33 0.856329 1 1 1 nc +31 62 0.856329 1 1 1 nc +17 63 0.856329 1 1 1 nc +21 47 0.856329 1 1 1 nc +40 30 0.856329 1 1 1 nc +20 26 0.856329 1 1 1 nc +52 64 0.856329 1 1 1 nc +49 49 0.856329 1 1 1 nc +37 52 0.856329 1 1 1 nc +grestore +grestore +showpage