Changes in / [1030:4936be66d2f5:1038:a2d142bb5d3c] in lemon-main

Files:

• doc/CMakeLists.txt (modified) (1 diff)
• doc/groups.dox (modified) (1 diff)
• doc/images/tsp.eps (added)
• lemon/christofides_tsp.h (added)
• lemon/greedy_tsp.h (added)
• lemon/insertion_tsp.h (added)
• lemon/nearest_neighbor_tsp.h (added)
• lemon/opt2_tsp.h (added)
• test/CMakeLists.txt (modified) (1 diff)
• test/tsp_test.cc (added)

doc/CMakeLists.txt

@@ -47 +47 @@
     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

doc/groups.dox

@@ -559 +559 @@
 \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 are intended to be used with a \e metric \e cost
+\e function, i.e. the edge costs should satisfy the triangle inequality.
+Otherwise the algorithms 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
+
+\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
+solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
+
+\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
+approximation factor: 3/2.
+
+\ref Opt2Tsp usually provides the best results in practice, but
+it is the slowest method. It can also be used to improve given tours,
+for example, the results of other algorithms.
+
+\image html tsp.png
+\image latex tsp.eps "Traveling salesman problem" width=\textwidth
+*/
 
 /**

test/CMakeLists.txt

@@ -53 +53 @@
   suurballe_test
   time_measure_test
+  tsp_test
   unionfind_test
 )