RhodeCode

SET(COIN_ROOT_DIR "" CACHE PATH "COIN root directory")

FIND_PATH(COIN_INCLUDE_DIR coin/CoinUtilsConfig.h

  HINTS ${COIN_ROOT_DIR}/include

)

FIND_LIBRARY(COIN_CBC_LIBRARY

  NAMES Cbc libCbc

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY

  NAMES CbcSolver libCbcSolver

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_CGL_LIBRARY

  NAMES Cgl libCgl

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_CLP_LIBRARY

  NAMES Clp libClp

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY

  NAMES CoinUtils libCoinUtils

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_OSI_LIBRARY

  NAMES Osi libOsi

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_OSI_CBC_LIBRARY

  NAMES OsiCbc libOsiCbc

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_OSI_CLP_LIBRARY

  NAMES OsiClp libOsiClp

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_OSI_VOL_LIBRARY

  NAMES OsiVol libOsiVol

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_VOL_LIBRARY

  NAMES Vol libVol

  HINTS ${COIN_ROOT_DIR}/lib

)

INCLUDE(FindPackageHandleStandardArgs)

FIND_PACKAGE_HANDLE_STANDARD_ARGS(COIN DEFAULT_MSG

  COIN_INCLUDE_DIR

  COIN_CBC_LIBRARY

  COIN_CBC_SOLVER_LIBRARY

  COIN_CGL_LIBRARY

  COIN_CLP_LIBRARY

  COIN_COIN_UTILS_LIBRARY

  COIN_OSI_LIBRARY

  COIN_OSI_CBC_LIBRARY

  COIN_OSI_CLP_LIBRARY

)

IF(COIN_FOUND)

  SET(COIN_INCLUDE_DIRS ${COIN_INCLUDE_DIR})

  SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY}")

  SET(COIN_CBC_LIBRARIES ${COIN_LIBRARIES})

ENDIF(COIN_FOUND)

MARK_AS_ADVANCED(

  COIN_INCLUDE_DIR

  COIN_CBC_LIBRARY

  COIN_CBC_SOLVER_LIBRARY

  COIN_CGL_LIBRARY

  COIN_CLP_LIBRARY

  COIN_COIN_UTILS_LIBRARY

  COIN_OSI_LIBRARY

  COIN_OSI_CBC_LIBRARY

  COIN_OSI_CLP_LIBRARY

  COIN_OSI_VOL_LIBRARY

  COIN_VOL_LIBRARY

)

IF(COIN_FOUND)

  SET(LEMON_HAVE_LP TRUE)

  SET(LEMON_HAVE_MIP TRUE)

  SET(LEMON_HAVE_CLP TRUE)

  SET(LEMON_HAVE_CBC TRUE)

ENDIF(COIN_FOUND)

INCLUDE_DIRECTORIES(

  ${PROJECT_SOURCE_DIR}

  ${PROJECT_BINARY_DIR}

)

LINK_DIRECTORIES(

  ${PROJECT_BINARY_DIR}/lemon

)

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

  bellman_ford_test

  bfs_test

  circulation_test

  connectivity_test

  counter_test

  dfs_test

  digraph_test

  dijkstra_test

  dim_test

  edge_set_test

  error_test

  euler_test

  fractional_matching_test

  gomory_hu_test

  graph_copy_test

  graph_test

  graph_utils_test

  hao_orlin_test

  heap_test

  kruskal_test

  maps_test

  matching_test

  min_cost_arborescence_test

  min_cost_flow_test

  min_mean_cycle_test

  path_test

  planarity_test

  preflow_test

  radix_sort_test

  random_test

  suurballe_test

  time_measure_test

  unionfind_test

)

IF(LEMON_HAVE_LP)

  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")

    ADD_EXECUTABLE(lp_test lp_test.cc)

  ELSE()

    ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc)

  ENDIF()

  SET(LP_TEST_LIBS lemon)

  IF(LEMON_HAVE_GLPK)

    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${GLPK_LIBRARIES})

  ENDIF()

  IF(LEMON_HAVE_CPLEX)

    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES})

  ENDIF()

  IF(LEMON_HAVE_CLP)

    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES})

  ENDIF()

  TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})

  ADD_TEST(lp_test lp_test)

  IF(WIN32 AND LEMON_HAVE_GLPK)

    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)

    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)

    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD

      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}

      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}

      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}

    )

  ENDIF()

  IF(WIN32 AND LEMON_HAVE_CPLEX)

    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)

    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}

    )

  ENDIF()

ENDIF()

IF(LEMON_HAVE_MIP)

  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")

    ADD_EXECUTABLE(mip_test mip_test.cc)

  ELSE()

    ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc)

  ENDIF()

  SET(MIP_TEST_LIBS lemon)

  IF(LEMON_HAVE_GLPK)

    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${GLPK_LIBRARIES})

  ENDIF()

  IF(LEMON_HAVE_CPLEX)

    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${CPLEX_LIBRARIES})

  ENDIF()

  IF(LEMON_HAVE_CBC)

    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${COIN_CBC_LIBRARIES})

  ENDIF()

  TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})

  ADD_TEST(mip_test mip_test)

  IF(WIN32 AND LEMON_HAVE_GLPK)

    GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)

    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)

    ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD

      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}

      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}

      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}

    )

  ENDIF()

  IF(WIN32 AND LEMON_HAVE_CPLEX)

    GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)

    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}

    )

  ENDIF()

ENDIF()

FOREACH(TEST_NAME ${TESTS})

  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")

    ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)

  ELSE()

    ADD_EXECUTABLE(${TEST_NAME} EXCLUDE_FROM_ALL ${TEST_NAME}.cc)

  ENDIF()

  TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)

    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()

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#include <iostream>

#include <fstream>

#include <string>

#include <vector>

#include <lemon/concept_check.h>

#include <lemon/concepts/heap.h>

#include <lemon/smart_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/dijkstra.h>

#include <lemon/maps.h>

#include <lemon/bin_heap.h>

#include <lemon/quad_heap.h>

#include <lemon/dheap.h>

#include <lemon/fib_heap.h>

#include <lemon/pairing_heap.h>

#include <lemon/radix_heap.h>

#include <lemon/binomial_heap.h>

#include <lemon/bucket_heap.h>

#include "test_tools.h"

using namespace lemon;

using namespace lemon::concepts;

typedef ListDigraph Digraph;

DIGRAPH_TYPEDEFS(Digraph);

char test_lgf[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "2\n"

  "3\n"

  "4\n"

  "5\n"

  "6\n"

  "7\n"

  "8\n"

  "9\n"

  "@arcs\n"

  "                label   capacity\n"

  "0       5       0       94\n"

  "3       9       1       11\n"

  "8       7       2       83\n"

  "1       2       3       94\n"

  "5       7       4       35\n"

  "7       4       5       84\n"

  "9       5       6       38\n"

  "0       4       7       96\n"

  "6       7       8       6\n"

  "3       1       9       27\n"

  "5       2       10      77\n"

  "5       6       11      69\n"

  "6       5       12      41\n"

  "4       6       13      70\n"

  "3       2       14      45\n"

  "7       9       15      93\n"

  "5       9       16      50\n"

  "9       0       17      94\n"

  "9       6       18      67\n"

  "0       9       19      86\n"

  "@attributes\n"

  "source 3\n";

int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};

int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};

int test_len = sizeof(test_seq) / sizeof(test_seq[0]);

template <typename Heap>

void heapSortTest() {

  RangeMap<int> map(test_len, -1);

  Heap heap(map);

  std::vector<int> v(test_len);

  for (int i = 0; i < test_len; ++i) {

    v[i] = test_seq[i];

    heap.push(i, v[i]);

  }

  std::sort(v.begin(), v.end());

  for (int i = 0; i < test_len; ++i) {

    check(v[i] == heap.prio(), "Wrong order in heap sort.");

    heap.pop();

  }

}

template <typename Heap>

void heapIncreaseTest() {

  RangeMap<int> map(test_len, -1);

  Heap heap(map);

  std::vector<int> v(test_len);

  for (int i = 0; i < test_len; ++i) {

    v[i] = test_seq[i];

    heap.push(i, v[i]);

  }

  for (int i = 0; i < test_len; ++i) {

    v[i] += test_inc[i];

    heap.increase(i, v[i]);

  }

  std::sort(v.begin(), v.end());

  for (int i = 0; i < test_len; ++i) {

    check(v[i] == heap.prio(), "Wrong order in heap increase test.");

    heap.pop();

  }

}

template <typename Heap>

void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,

                      Node source) {

  typename Dijkstra<Digraph, IntArcMap>::template SetStandardHeap<Heap>::

    Create dijkstra(digraph, length);

  dijkstra.run(source);

  for(ArcIt a(digraph); a != INVALID; ++a) {

    Node s = digraph.source(a);

    Node t = digraph.target(a);

    if (dijkstra.reached(s)) {

      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],

             "Error in shortest path tree.");

    }

  }

  for(NodeIt n(digraph); n != INVALID; ++n) {

    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {

      Arc a = dijkstra.predArc(n);

      Node s = digraph.source(a);

      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],

             "Error in shortest path tree.");

    }

  }

}

int main() {

  typedef int Item;

  typedef int Prio;

  typedef RangeMap<int> ItemIntMap;

  Digraph digraph;

  IntArcMap length(digraph);

  Node source;

  std::istringstream input(test_lgf);

  digraphReader(digraph, input).

    arcMap("capacity", length).

    node("source", source).

    run();

  // BinHeap

  {

    typedef BinHeap<Prio, ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef BinHeap<Prio, IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  }

  // QuadHeap

  {

    typedef QuadHeap<Prio, ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef QuadHeap<Prio, IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  }

  // DHeap

  {

    typedef DHeap<Prio, ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef DHeap<Prio, IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  }

  // FibHeap

  {

    typedef FibHeap<Prio, ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef FibHeap<Prio, IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  }

  // PairingHeap

  {

    typedef PairingHeap<Prio, ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef PairingHeap<Prio, IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  }

  // RadixHeap

  {

    typedef RadixHeap<ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef RadixHeap<IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  }

  // BinomialHeap

  {

    typedef BinomialHeap<Prio, ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  }

  // BucketHeap, SimpleBucketHeap

  {

    typedef BucketHeap<ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef BucketHeap<IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

    typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;

    heapSortTest<SimpleIntHeap>();

  }

  return 0;

}