Changeset 1206:a2d142bb5d3c in lemon

Timestamp:

03/01/13 17:59:08 (11 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Parents:

1198:4936be66d2f5 (diff), 1205:d3dcc49e6403 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Phase:

public

Message:

Merge #386

Files:

• doc/CMakeLists.txt (modified) (1 diff)
• doc/CMakeLists.txt (modified) (1 diff)
• doc/groups.dox (modified) (1 diff)
• doc/groups.dox (modified) (4 diffs)
• test/CMakeLists.txt (modified) (1 diff)
• test/CMakeLists.txt (modified) (7 diffs)

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/CMakeLists.txt

@@ -11 +11 @@
   @ONLY
 )
+
+CONFIGURE_FILE(
+  ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in
+  ${PROJECT_BINARY_DIR}/doc/mainpage.dox
+  @ONLY
+)
+
+# Copy doc from source (if exists)
+IF(EXISTS ${CMAKE_CURRENT_SOURCE_DIR}/html AND 
+    NOT EXISTS ${CMAKE_CURRENT_BINARY_DIR}/html/index.html)
+  MESSAGE(STATUS "Copy doc from source tree")
+  EXECUTE_PROCESS(
+    COMMAND cmake -E copy_directory ${CMAKE_CURRENT_SOURCE_DIR}/html ${CMAKE_CURRENT_BINARY_DIR}/html
+    )
+ENDIF()
 
 IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)

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
+*/
 
 /**

doc/groups.dox

@@ -407 +407 @@
    strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
 
-In general NetworkSimplex is the most efficient implementation,
-but in special cases other algorithms could be faster.
+In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
+implementations.
+\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
+several thousands of nodes) and on dense graphs, while \ref CostScaling is
+typically more efficient on large graphs (e.g. hundreds of thousands of
+nodes or above), especially if they are sparse.
+However, other algorithms could be faster in special cases.
 For example, if the total supply and/or capacities are rather small,
-CapacityScaling is usually the fastest algorithm (without effective scaling).
+\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
+
+These classes are intended to be used with integer-valued input data
+(capacities, supply values, and costs), except for \ref CapacityScaling,
+which is capable of handling real-valued arc costs (other numerical
+data are required to be integer).
 */
 
@@ -449 +459 @@
 
 This group contains the algorithms for finding minimum mean cycles
-\ref clrs01algorithms, \ref amo93networkflows.
+\ref amo93networkflows, \ref karp78characterization.
 
 The \e minimum \e mean \e cycle \e problem is to find a directed cycle
@@ -465 +475 @@
 
 LEMON contains three algorithms for solving the minimum mean cycle problem:
-- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
-  \ref dasdan98minmeancycle.
+- \ref KarpMmc Karp's original algorithm \ref karp78characterization.
 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
-  version of Karp's algorithm \ref dasdan98minmeancycle.
+  version of Karp's algorithm \ref hartmann93finding.
 - \ref HowardMmc Howard's policy iteration algorithm
-  \ref dasdan98minmeancycle.
-
-In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
+  \ref dasdan98minmeancycle, \ref dasdan04experimental.
+
+In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
 most efficient one, though the best known theoretical bound on its running
 time is exponential.
@@ -540 +549 @@
 
 /**
-@defgroup planar Planarity Embedding and Drawing
+@defgroup planar Planar Embedding and Drawing
 @ingroup algs
 \brief Algorithms for planarity checking, embedding and drawing

test/CMakeLists.txt

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

test/CMakeLists.txt

@@ -8 +8 @@
 )
 
+SET(TEST_WITH_VALGRIND "NO" CACHE STRING
+  "Run the test with valgrind (YES/NO).")
+SET(VALGRIND_FLAGS "" CACHE STRING "Valgrind flags used by the tests.")
+
 SET(TESTS
   adaptors_test
+  arc_look_up_test
   bellman_ford_test
   bfs_test
+  bpgraph_test
   circulation_test
   connectivity_test
@@ -30 +36 @@
   heap_test
   kruskal_test
+  lgf_reader_writer_test
+  lgf_test
   maps_test
   matching_test
@@ -70 +78 @@
   TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
   ADD_TEST(lp_test lp_test)
+  ADD_DEPENDENCIES(check lp_test)
 
   IF(WIN32 AND LEMON_HAVE_GLPK)
@@ -85 +94 @@
     GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
     ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
-      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
+      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex.dll ${TARGET_PATH}
     )
   ENDIF()
@@ -111 +120 @@
   TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})
   ADD_TEST(mip_test mip_test)
+  ADD_DEPENDENCIES(check mip_test)
 
   IF(WIN32 AND LEMON_HAVE_GLPK)
@@ -126 +136 @@
     GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
     ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
-      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
+      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex.dll ${TARGET_PATH}
     )
   ENDIF()
@@ -138 +148 @@
   ENDIF()
   TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
-  ADD_TEST(${TEST_NAME} ${TEST_NAME})
+    IF(TEST_WITH_VALGRIND)
+      ADD_TEST(${TEST_NAME}
+        valgrind --error-exitcode=1 ${VALGRIND_FLAGS}
+        ${CMAKE_CURRENT_BINARY_DIR}/${TEST_NAME} )
+    ELSE()
+      ADD_TEST(${TEST_NAME} ${TEST_NAME})
+    ENDIF()
   ADD_DEPENDENCIES(check ${TEST_NAME})
 ENDFOREACH()