COIN-OR::LEMON - Graph Library

Changeset 1206:a2d142bb5d3c in lemon


Ignore:
Timestamp:
03/01/13 17:59:08 (7 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:
6 edited

Legend:

Unmodified
Added
Removed
  • doc/CMakeLists.txt

    r1135 r1206  
    4747    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
    4848    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     49    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps
    4950    COMMAND ${CMAKE_COMMAND} -E remove_directory html
    5051    COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
  • doc/CMakeLists.txt

    r1200 r1206  
    1111  @ONLY
    1212)
     13
     14CONFIGURE_FILE(
     15  ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in
     16  ${PROJECT_BINARY_DIR}/doc/mainpage.dox
     17  @ONLY
     18)
     19
     20# Copy doc from source (if exists)
     21IF(EXISTS ${CMAKE_CURRENT_SOURCE_DIR}/html AND
     22    NOT EXISTS ${CMAKE_CURRENT_BINARY_DIR}/html/index.html)
     23  MESSAGE(STATUS "Copy doc from source tree")
     24  EXECUTE_PROCESS(
     25    COMMAND cmake -E copy_directory ${CMAKE_CURRENT_SOURCE_DIR}/html ${CMAKE_CURRENT_BINARY_DIR}/html
     26    )
     27ENDIF()
    1328
    1429IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
  • doc/groups.dox

    r1165 r1206  
    559559\image latex planar.eps "Plane graph" width=\textwidth
    560560*/
     561 
     562/**
     563@defgroup tsp Traveling Salesman Problem
     564@ingroup algs
     565\brief Algorithms for the symmetric traveling salesman problem
     566
     567This group contains basic heuristic algorithms for the the symmetric
     568\e traveling \e salesman \e problem (TSP).
     569Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
     570the problem is to find a shortest possible tour that visits each node exactly
     571once (i.e. the minimum cost Hamiltonian cycle).
     572
     573These TSP algorithms are intended to be used with a \e metric \e cost
     574\e function, i.e. the edge costs should satisfy the triangle inequality.
     575Otherwise the algorithms could yield worse results.
     576
     577LEMON provides five well-known heuristics for solving symmetric TSP:
     578 - \ref NearestNeighborTsp Neareast neighbor algorithm
     579 - \ref GreedyTsp Greedy algorithm
     580 - \ref InsertionTsp Insertion heuristic (with four selection methods)
     581 - \ref ChristofidesTsp Christofides algorithm
     582 - \ref Opt2Tsp 2-opt algorithm
     583
     584\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
     585solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
     586
     587\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
     588approximation factor: 3/2.
     589
     590\ref Opt2Tsp usually provides the best results in practice, but
     591it is the slowest method. It can also be used to improve given tours,
     592for example, the results of other algorithms.
     593
     594\image html tsp.png
     595\image latex tsp.eps "Traveling salesman problem" width=\textwidth
     596*/
    561597
    562598/**
  • doc/groups.dox

    r1204 r1206  
    407407   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
    408408
    409 In general NetworkSimplex is the most efficient implementation,
    410 but in special cases other algorithms could be faster.
     409In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
     410implementations.
     411\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
     412several thousands of nodes) and on dense graphs, while \ref CostScaling is
     413typically more efficient on large graphs (e.g. hundreds of thousands of
     414nodes or above), especially if they are sparse.
     415However, other algorithms could be faster in special cases.
    411416For example, if the total supply and/or capacities are rather small,
    412 CapacityScaling is usually the fastest algorithm (without effective scaling).
     417\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
     418
     419These classes are intended to be used with integer-valued input data
     420(capacities, supply values, and costs), except for \ref CapacityScaling,
     421which is capable of handling real-valued arc costs (other numerical
     422data are required to be integer).
    413423*/
    414424
     
    449459
    450460This group contains the algorithms for finding minimum mean cycles
    451 \ref clrs01algorithms, \ref amo93networkflows.
     461\ref amo93networkflows, \ref karp78characterization.
    452462
    453463The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     
    465475
    466476LEMON contains three algorithms for solving the minimum mean cycle problem:
    467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
    468   \ref dasdan98minmeancycle.
     477- \ref KarpMmc Karp's original algorithm \ref karp78characterization.
    469478- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    470   version of Karp's algorithm \ref dasdan98minmeancycle.
     479  version of Karp's algorithm \ref hartmann93finding.
    471480- \ref HowardMmc Howard's policy iteration algorithm
    472   \ref dasdan98minmeancycle.
    473 
    474 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
     481  \ref dasdan98minmeancycle, \ref dasdan04experimental.
     482
     483In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
    475484most efficient one, though the best known theoretical bound on its running
    476485time is exponential.
     
    540549
    541550/**
    542 @defgroup planar Planarity Embedding and Drawing
     551@defgroup planar Planar Embedding and Drawing
    543552@ingroup algs
    544553\brief Algorithms for planarity checking, embedding and drawing
  • test/CMakeLists.txt

    r1198 r1206  
    5353  suurballe_test
    5454  time_measure_test
     55  tsp_test
    5556  unionfind_test
    5657)
  • test/CMakeLists.txt

    r1203 r1206  
    88)
    99
     10SET(TEST_WITH_VALGRIND "NO" CACHE STRING
     11  "Run the test with valgrind (YES/NO).")
     12SET(VALGRIND_FLAGS "" CACHE STRING "Valgrind flags used by the tests.")
     13
    1014SET(TESTS
    1115  adaptors_test
     16  arc_look_up_test
    1217  bellman_ford_test
    1318  bfs_test
     19  bpgraph_test
    1420  circulation_test
    1521  connectivity_test
     
    3036  heap_test
    3137  kruskal_test
     38  lgf_reader_writer_test
     39  lgf_test
    3240  maps_test
    3341  matching_test
     
    7078  TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
    7179  ADD_TEST(lp_test lp_test)
     80  ADD_DEPENDENCIES(check lp_test)
    7281
    7382  IF(WIN32 AND LEMON_HAVE_GLPK)
     
    8594    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
    8695    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
    87       COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
     96      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex.dll ${TARGET_PATH}
    8897    )
    8998  ENDIF()
     
    111120  TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})
    112121  ADD_TEST(mip_test mip_test)
     122  ADD_DEPENDENCIES(check mip_test)
    113123
    114124  IF(WIN32 AND LEMON_HAVE_GLPK)
     
    126136    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
    127137    ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
    128       COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
     138      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex.dll ${TARGET_PATH}
    129139    )
    130140  ENDIF()
     
    138148  ENDIF()
    139149  TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
    140   ADD_TEST(${TEST_NAME} ${TEST_NAME})
     150    IF(TEST_WITH_VALGRIND)
     151      ADD_TEST(${TEST_NAME}
     152        valgrind --error-exitcode=1 ${VALGRIND_FLAGS}
     153        ${CMAKE_CURRENT_BINARY_DIR}/${TEST_NAME} )
     154    ELSE()
     155      ADD_TEST(${TEST_NAME} ${TEST_NAME})
     156    ENDIF()
    141157  ADD_DEPENDENCIES(check ${TEST_NAME})
    142158ENDFOREACH()
Note: See TracChangeset for help on using the changeset viewer.