RhodeCode

/* -*- C++ -*-

 *

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

 *

 * Copyright (C) 2003-2008

 * 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.

 *

 */

#ifndef LEMON_MIN_MEAN_CYCLE_H

#define LEMON_MIN_MEAN_CYCLE_H

/// \ingroup shortest_path

///

/// \file

/// \brief Howard's algorithm for finding a minimum mean cycle.

#include <vector>

#include <lemon/core.h>

#include <lemon/path.h>

#include <lemon/tolerance.h>

#include <lemon/connectivity.h>

namespace lemon {

  /// \brief Default traits class of MinMeanCycle class.

  ///

  /// Default traits class of MinMeanCycle class.

  /// \tparam GR The type of the digraph.

  /// \tparam LEN The type of the length map.

  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.

#ifdef DOXYGEN

  template <typename GR, typename LEN>

#else

  template <typename GR, typename LEN,

    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>

#endif

  struct MinMeanCycleDefaultTraits

  {

    /// The type of the digraph

    typedef GR Digraph;

    /// The type of the length map

    typedef LEN LengthMap;

    /// The type of the arc lengths

    typedef typename LengthMap::Value Value;

    /// \brief The large value type used for internal computations

    ///

    /// The large value type used for internal computations.

    /// It is \c long \c long if the \c Value type is integer,

    /// otherwise it is \c double.

    /// \c Value must be convertible to \c LargeValue.

    typedef double LargeValue;

    /// The tolerance type used for internal computations

    typedef lemon::Tolerance<LargeValue> Tolerance;

    /// \brief The path type of the found cycles

    ///

    /// The path type of the found cycles.

    /// It must conform to the \ref lemon::concepts::Path "Path" concept

    /// and it must have an \c addBack() function.

    typedef lemon::Path<Digraph> Path;

  };

  // Default traits class for integer value types

  template <typename GR, typename LEN>

  struct MinMeanCycleDefaultTraits<GR, LEN, true>

  {

    typedef GR Digraph;

    typedef LEN LengthMap;

    typedef typename LengthMap::Value Value;

#ifdef LEMON_HAVE_LONG_LONG

    typedef long long LargeValue;

#else

    typedef long LargeValue;

#endif

    typedef lemon::Tolerance<LargeValue> Tolerance;

    typedef lemon::Path<Digraph> Path;

  };

  /// \addtogroup shortest_path

  /// @{

  /// \brief Implementation of Howard's algorithm for finding a minimum

  /// mean cycle.

  ///

  /// \ref MinMeanCycle implements Howard's algorithm for finding a

  /// directed cycle of minimum mean length (cost) in a digraph.

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam LEN The type of the length map. The default

  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template < typename GR,

             typename LEN = typename GR::template ArcMap<int>,

             typename TR = MinMeanCycleDefaultTraits<GR, LEN> >

#endif

  class MinMeanCycle

  {

  public:

    /// The type of the digraph

    typedef typename TR::Digraph Digraph;

    /// The type of the length map

    typedef typename TR::LengthMap LengthMap;

    /// The type of the arc lengths

    typedef typename TR::Value Value;

    /// \brief The large value type

    ///

    /// The large value type used for internal computations.

    /// Using the \ref MinMeanCycleDefaultTraits "default traits class",

    /// it is \c long \c long if the \c Value type is integer,

    /// otherwise it is \c double.

    typedef typename TR::LargeValue LargeValue;

    /// The tolerance type

    typedef typename TR::Tolerance Tolerance;

    /// \brief The path type of the found cycles

    ///

    /// The path type of the found cycles.

    /// Using the \ref MinMeanCycleDefaultTraits "default traits class",

    /// it is \ref lemon::Path "Path<Digraph>".

    typedef typename TR::Path Path;

    /// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    // The digraph the algorithm runs on

    const Digraph &_gr;

    // The length of the arcs

    const LengthMap &_length;

    // Data for the found cycles

    bool _curr_found, _best_found;

    LargeValue _curr_length, _best_length;

    int _curr_size, _best_size;

    Node _curr_node, _best_node;

    Path *_cycle_path;

    bool _local_path;

    // Internal data used by the algorithm

    typename Digraph::template NodeMap<Arc> _policy;

    typename Digraph::template NodeMap<bool> _reached;

    typename Digraph::template NodeMap<int> _level;

    typename Digraph::template NodeMap<LargeValue> _dist;

    // Data for storing the strongly connected components

    int _comp_num;

    typename Digraph::template NodeMap<int> _comp;

    std::vector<std::vector<Node> > _comp_nodes;

    std::vector<Node>* _nodes;

    typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;

    // Queue used for BFS search

    std::vector<Node> _queue;

    int _qfront, _qback;

    Tolerance _tolerance;

  public:

    /// \name Named Template Parameters

    /// @{

    template <typename T>

    struct SetLargeValueTraits : public Traits {

      typedef T LargeValue;

      typedef lemon::Tolerance<T> Tolerance;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c LargeValue type.

    ///

    /// \ref named-templ-param "Named parameter" for setting \c LargeValue

    /// type. It is used for internal computations in the algorithm.

    template <typename T>

    struct SetLargeValue

      : public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {

      typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;

    };

    template <typename T>

    struct SetPathTraits : public Traits {

      typedef T Path;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c %Path type.

    ///

    /// \ref named-templ-param "Named parameter" for setting the \c %Path

    /// type of the found cycles.

    /// It must conform to the \ref lemon::concepts::Path "Path" concept

    /// and it must have an \c addBack() function.

    template <typename T>

    struct SetPath

      : public MinMeanCycle<GR, LEN, SetPathTraits<T> > {

      typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;

    };

    /// @}

  public:

    /// \brief Constructor.

    ///

    /// The constructor of the class.

    ///

    /// \param digraph The digraph the algorithm runs on.

    /// \param length The lengths (costs) of the arcs.

    MinMeanCycle( const Digraph &digraph,

                  const LengthMap &length ) :

      _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),

      _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),

      _comp(digraph), _in_arcs(digraph)

    {}

    /// Destructor.

    ~MinMeanCycle() {

      if (_local_path) delete _cycle_path;

    }

    /// \brief Set the path structure for storing the found cycle.

    ///

    /// This function sets an external path structure for storing the

    /// found cycle.

    ///

    /// If you don't call this function before calling \ref run() or

    /// \ref findMinMean(), it will allocate a local \ref Path "path"

    /// structure. The destuctor deallocates this automatically

    /// allocated object, of course.

    ///

    /// \note The algorithm calls only the \ref lemon::Path::addBack()

    /// "addBack()" function of the given path structure.

    ///

    /// \return <tt>(*this)</tt>

    MinMeanCycle& cycle(Path &path) {

      if (_local_path) {

        delete _cycle_path;

        _local_path = false;

      }

      _cycle_path = &path;

      return *this;

    }

    /// \name Execution control

    /// The simplest way to execute the algorithm is to call the \ref run()

    /// function.\n

    /// If you only need the minimum mean length, you may call

    /// \ref findMinMean().

    /// @{

    /// \brief Run the algorithm.

    ///

    /// This function runs the algorithm.

    /// It can be called more than once (e.g. if the underlying digraph

    /// and/or the arc lengths have been modified).

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    ///

    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.

    /// \code

    ///   return mmc.findMinMean() && mmc.findCycle();

    /// \endcode

    bool run() {

      return findMinMean() && findCycle();

    }

    /// \brief Find the minimum cycle mean.

    ///

    /// This function finds the minimum mean length of the directed

    /// cycles in the digraph.

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    bool findMinMean() {

      // Initialize and find strongly connected components

      init();

      findComponents();

      // Find the minimum cycle mean in the components

      for (int comp = 0; comp < _comp_num; ++comp) {

        // Find the minimum mean cycle in the current component

        if (!buildPolicyGraph(comp)) continue;

        while (true) {

          findPolicyCycle();

          if (!computeNodeDistances()) break;

        }

        // Update the best cycle (global minimum mean cycle)

        if ( !_best_found || (_curr_found &&

             _curr_length * _best_size < _best_length * _curr_size) ) {

          _best_found = true;

          _best_length = _curr_length;

          _best_size = _curr_size;

          _best_node = _curr_node;

        }

      }

      return _best_found;

    }

    /// \brief Find a minimum mean directed cycle.

    ///

    /// This function finds a directed cycle of minimum mean length

    /// in the digraph using the data computed by findMinMean().

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    ///

    /// \pre \ref findMinMean() must be called before using this function.

    bool findCycle() {

      if (!_best_found) return false;

      _cycle_path->addBack(_policy[_best_node]);

      for ( Node v = _best_node;

            (v = _gr.target(_policy[v])) != _best_node; ) {

        _cycle_path->addBack(_policy[v]);

      }

      return true;

    }

    /// @}

    /// \name Query Functions

    /// The results of the algorithm can be obtained using these

    /// functions.\n

    /// The algorithm should be executed before using them.

    /// @{

    /// \brief Return the total length of the found cycle.

    ///

    /// This function returns the total length of the found cycle.

    ///

    /// \pre \ref run() or \ref findMinMean() must be called before

    /// using this function.

    LargeValue cycleLength() const {

      return _best_length;

    }

    /// \brief Return the number of arcs on the found cycle.

    ///

    /// This function returns the number of arcs on the found cycle.

    ///

    /// \pre \ref run() or \ref findMinMean() must be called before

    /// using this function.

    int cycleArcNum() const {

      return _best_size;

    }

    /// \brief Return the mean length of the found cycle.

    ///

    /// This function returns the mean length of the found cycle.

    ///

    /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the

    /// following code.

    /// \code

    ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();

    /// \endcode

    ///

    /// \pre \ref run() or \ref findMinMean() must be called before

    /// using this function.

    double cycleMean() const {

      return static_cast<double>(_best_length) / _best_size;

    }

    /// \brief Return the found cycle.

    ///

    /// This function returns a const reference to the path structure

    /// storing the found cycle.

    ///

    /// \pre \ref run() or \ref findCycle() must be called before using

    /// this function.

    const Path& cycle() const {

      return *_cycle_path;

    }

    ///@}

  private:

    // Initialize

    void init() {

      if (!_cycle_path) {

        _local_path = true;

        _cycle_path = new Path;

      }

      _queue.resize(countNodes(_gr));

      _best_found = false;

      _best_length = 0;

      _best_size = 1;

      _cycle_path->clear();

    }

    // Find strongly connected components and initialize _comp_nodes

INCLUDE_DIRECTORIES(

  ${PROJECT_SOURCE_DIR}

  ${PROJECT_BINARY_DIR}

)

LINK_DIRECTORIES(

  ${PROJECT_BINARY_DIR}/lemon

)

SET(TESTS

  adaptors_test

  bfs_test

  circulation_test

  connectivity_test

  counter_test

  dfs_test

  digraph_test

  dijkstra_test

  dim_test

  edge_set_test

  error_test

  euler_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

  path_test

  preflow_test

  radix_sort_test

  random_test

  suurballe_test

  time_measure_test

  unionfind_test

)

IF(LEMON_HAVE_LP)

  ADD_EXECUTABLE(lp_test lp_test.cc)

  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)

  ADD_EXECUTABLE(mip_test mip_test.cc)

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

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

  TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)

  ADD_TEST(${TEST_NAME} ${TEST_NAME})

ENDFOREACH()

EXTRA_DIST += \

	test/CMakeLists.txt

noinst_HEADERS += \

	test/graph_test.h \

	test/test_tools.h

check_PROGRAMS += \

	test/adaptors_test \

	test/bfs_test \

	test/circulation_test \

	test/connectivity_test \

	test/counter_test \

	test/dfs_test \

	test/digraph_test \

	test/dijkstra_test \

	test/dim_test \

	test/edge_set_test \

	test/error_test \

	test/euler_test \

	test/gomory_hu_test \

	test/graph_copy_test \

	test/graph_test \

	test/graph_utils_test \

	test/hao_orlin_test \

	test/heap_test \

	test/kruskal_test \

	test/maps_test \

	test/matching_test \

	test/min_cost_arborescence_test \

	test/min_cost_flow_test \

	test/path_test \

	test/preflow_test \

	test/radix_sort_test \

	test/random_test \

	test/suurballe_test \

	test/test_tools_fail \

	test/test_tools_pass \

	test/time_measure_test \

	test/unionfind_test

test_test_tools_pass_DEPENDENCIES = demo

if HAVE_LP

check_PROGRAMS += test/lp_test

endif HAVE_LP

if HAVE_MIP

check_PROGRAMS += test/mip_test

endif HAVE_MIP

TESTS += $(check_PROGRAMS)

XFAIL_TESTS += test/test_tools_fail$(EXEEXT)

test_adaptors_test_SOURCES = test/adaptors_test.cc

test_bfs_test_SOURCES = test/bfs_test.cc

test_circulation_test_SOURCES = test/circulation_test.cc

test_counter_test_SOURCES = test/counter_test.cc

test_connectivity_test_SOURCES = test/connectivity_test.cc

test_dfs_test_SOURCES = test/dfs_test.cc

test_digraph_test_SOURCES = test/digraph_test.cc

test_dijkstra_test_SOURCES = test/dijkstra_test.cc

test_dim_test_SOURCES = test/dim_test.cc

test_edge_set_test_SOURCES = test/edge_set_test.cc

test_error_test_SOURCES = test/error_test.cc

test_euler_test_SOURCES = test/euler_test.cc

test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc

test_graph_copy_test_SOURCES = test/graph_copy_test.cc

test_graph_test_SOURCES = test/graph_test.cc

test_graph_utils_test_SOURCES = test/graph_utils_test.cc

test_heap_test_SOURCES = test/heap_test.cc

test_kruskal_test_SOURCES = test/kruskal_test.cc

test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc

test_lp_test_SOURCES = test/lp_test.cc

test_maps_test_SOURCES = test/maps_test.cc

test_mip_test_SOURCES = test/mip_test.cc

test_matching_test_SOURCES = test/matching_test.cc

test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc

test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc

test_path_test_SOURCES = test/path_test.cc

test_preflow_test_SOURCES = test/preflow_test.cc

test_radix_sort_test_SOURCES = test/radix_sort_test.cc

test_suurballe_test_SOURCES = test/suurballe_test.cc

test_random_test_SOURCES = test/random_test.cc

test_test_tools_fail_SOURCES = test/test_tools_fail.cc

test_test_tools_pass_SOURCES = test/test_tools_pass.cc

test_time_measure_test_SOURCES = test/time_measure_test.cc

test_unionfind_test_SOURCES = test/unionfind_test.cc

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

 *

 */

#ifndef LEMON_TEST_TEST_TOOLS_H

#define LEMON_TEST_TEST_TOOLS_H

///\ingroup misc

///\file

///\brief Some utilities to write test programs.

#include <iostream>

#include <stdlib.h>

///If \c rc is fail, writes an error message and exits.

///If \c rc is fail, writes an error message and exits.

///The error message contains the file name and the line number of the

///source code in a standard from, which makes it possible to go there

///using good source browsers like e.g. \c emacs.

///

///For example

///\code check(0==1,"This is obviously false.");\endcode will

///print something like this (and then exits).

///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim

#endif