RhodeCode

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

FIND_PATH(COIN_INCLUDE_DIR coin/CoinUtilsConfig.h

  PATHS ${COIN_ROOT_DIR}/include)

FIND_LIBRARY(COIN_CBC_LIBRARY libCbc

  PATHS ${COIN_ROOT_DIR}/lib)

FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY libCbcSolver

  PATHS ${COIN_ROOT_DIR}/lib)

FIND_LIBRARY(COIN_CGL_LIBRARY libCgl

  PATHS ${COIN_ROOT_DIR}/lib)

FIND_LIBRARY(COIN_CLP_LIBRARY libClp

  PATHS ${COIN_ROOT_DIR}/lib)

FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY libCoinUtils

  PATHS ${COIN_ROOT_DIR}/lib)

FIND_LIBRARY(COIN_OSI_LIBRARY libOsi

  PATHS ${COIN_ROOT_DIR}/lib)

FIND_LIBRARY(COIN_OSI_CBC_LIBRARY libOsiCbc

  PATHS ${COIN_ROOT_DIR}/lib)

FIND_LIBRARY(COIN_OSI_CLP_LIBRARY libOsiClp

  PATHS ${COIN_ROOT_DIR}/lib)

FIND_LIBRARY(COIN_OSI_VOL_LIBRARY libOsiVol

  PATHS ${COIN_ROOT_DIR}/lib)

FIND_LIBRARY(COIN_VOL_LIBRARY libVol

  PATHS ${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

  COIN_OSI_VOL_LIBRARY

  COIN_VOL_LIBRARY

)

IF(COIN_FOUND)

  SET(COIN_INCLUDE_DIRS ${COIN_INCLUDE_DIR})

  SET(COIN_LIBRARIES "${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}")

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

  SET(HAVE_MIP TRUE)

  SET(HAVE_CLP TRUE)

  SET(HAVE_CBC TRUE)

ENDIF(COIN_FOUND)

FIND_PATH(CPLEX_INCLUDE_DIR

  ilcplex/cplex.h

  PATHS "C:/ILOG/CPLEX91/include")

FIND_LIBRARY(CPLEX_LIBRARY

  NAMES cplex91

  PATHS "C:/ILOG/CPLEX91/lib/msvc7/stat_mda")

INCLUDE(FindPackageHandleStandardArgs)

FIND_PACKAGE_HANDLE_STANDARD_ARGS(CPLEX DEFAULT_MSG CPLEX_LIBRARY CPLEX_INCLUDE_DIR)

FIND_PATH(CPLEX_BIN_DIR

  cplex91.dll

  PATHS "C:/ILOG/CPLEX91/bin/x86_win32")

IF(CPLEX_FOUND)

  SET(CPLEX_INCLUDE_DIRS ${CPLEX_INCLUDE_DIR})

  SET(CPLEX_LIBRARIES ${CPLEX_LIBRARY})

ENDIF(CPLEX_FOUND)

MARK_AS_ADVANCED(CPLEX_LIBRARY CPLEX_INCLUDE_DIR CPLEX_BIN_DIR)

IF(CPLEX_FOUND)

  SET(HAVE_LP TRUE)

  SET(HAVE_MIP TRUE)

  SET(HAVE_CPLEX TRUE)

ENDIF(CPLEX_FOUND)

FIND_PACKAGE(CPLEX)

FIND_PACKAGE(COIN)

  SET(GLPK_INCLUDE_DIRS ${GLPK_INCLUDE_DIR})

IF(GLPK_FOUND)

  SET(HAVE_LP TRUE)

  SET(HAVE_MIP TRUE)

  SET(HAVE_GLPK TRUE)

ENDIF(GLPK_FOUND)

  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS})

IF(HAVE_CPLEX)

  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)

  INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})

ENDIF(HAVE_CPLEX)

IF(HAVE_CLP)

  SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)

  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})

ENDIF(HAVE_CLP)

IF(HAVE_CBC)

  SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)

  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})

ENDIF(HAVE_CBC)

#include <limits>

     Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$

     \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and

     upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$

     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$

     This algorithm either calculates a feasible circulation, or provides

     a \ref barrier() "barrier", which prooves that a feasible soultion

     cannot exist.

    bool checkBoundMaps() {

      for (ArcIt e(_g);e!=INVALID;++e) {

        if (_tol.less((*_up)[e], (*_lo)[e])) return false;

      }

      return true;

    }

    Circulation& upperMap(const UpperMap& map) {

      LEMON_DEBUG(checkBoundMaps(),

        "Upper bounds must be greater or equal to the lower bounds");

      LEMON_DEBUG(checkBoundMaps(),

        "Upper bounds must be greater or equal to the lower bounds");

        if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) {

        } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) {

      Flow inf_cap = std::numeric_limits<Flow>::has_infinity ?

        std::numeric_limits<Flow>::infinity() :

        std::numeric_limits<Flow>::max();

          if(barrier(s)&&!barrier(t)) {

            if (_tol.less(inf_cap - (*_up)[e], delta)) return false;

            delta+=(*_up)[e];

          }

#cmakedefine HAVE_CPLEX 1

#cmakedefine HAVE_CLP 1

#cmakedefine HAVE_CBC 1

#include <limits>

  /// Note that this problem is a special case of the \ref min_cost_flow

  /// "minimum cost flow problem". This implementation is actually an

  /// efficient specialized version of the \ref CapacityScaling

  /// "Successive Shortest Path" algorithm directly for this problem.

  /// Therefore this class provides query functions for flow values and

  /// node potentials (the dual solution) just like the minimum cost flow

  /// algorithms.

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

  /// The default value is <tt>GR::ArcMap<int></tt>.

  /// along with the \ref SplitNodes adaptor.

  template < typename GR,

#ifdef DOXYGEN

    /// The type of the flow map.

    typedef GR::ArcMap<int> FlowMap;

    /// The type of the potential map.

    typedef GR::NodeMap<Length> PotentialMap;

#else

#endif

    typedef SimplePath<GR> Path;

    // ResidualDijkstra is a special implementation of the

    // Dijkstra algorithm for finding shortest paths in the

    // residual network with respect to the reduced arc lengths

    // and modifying the node potentials according to the

    // distance of the nodes.

      ResidualDijkstra( const Digraph &graph,

        _graph(graph), _flow(flow), _length(length), _potential(potential),

        _dist(graph), _pred(pred), _s(s), _t(t) {}

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

    Suurballe( const Digraph &graph,

               const LengthMap &length ) :

      _graph(graph), _length(length), _flow(0), _local_flow(false),

      _potential(0), _local_potential(false), _pred(graph)

    {

      LEMON_ASSERT(std::numeric_limits<Length>::is_integer,

        "The length type of Suurballe must be integer");

    }

    /// If it is not used before calling \ref run() or \ref init(),

    /// an instance will be allocated automatically. The destructor

    /// deallocates this automatically allocated map, of course.

    /// The found flow contains only 0 and 1 values, since it is the

    /// union of the found arc-disjoint paths.

    /// If it is not used before calling \ref run() or \ref init(),

    /// an instance will be allocated automatically. The destructor

    /// deallocates this automatically allocated map, of course.

    /// The node potentials provide the dual solution of the underlying

    /// \ref min_cost_flow "minimum cost flow problem".

    /// \param s The source node.

    /// \param t The target node.

    /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is

    /// just a shortcut of the following code.

    ///   s.init(s);

    ///   s.findFlow(t, k);

    int run(const Node& s, const Node& t, int k = 2) {

      init(s);

      findFlow(t, k);

    ///

    /// \param s The source node.

    void init(const Node& s) {

      _source = s;

    /// \brief Execute the algorithm to find an optimal flow.

    /// find a minimum cost flow, which is the union of \c k (or less)

    /// \param t The target node.

    /// \param k The number of paths to be found.

    ///

    /// the source node to the given node \c t in the digraph.

    /// Otherwise it returns the number of arc-disjoint paths found.

    int findFlow(const Node& t, int k = 2) {

      _target = t;

      _dijkstra =

        new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred,

                              _source, _target );

    /// This function computes the paths from the found minimum cost flow,

    /// which is the union of some arc-disjoint paths.

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

    ///

    /// This function returns the total length of the found paths, i.e.

    /// the total cost of the found flow.

    /// The complexity of the function is O(e).

    ///

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

    /// this function.

    Length totalLength() const {

      Length c = 0;

      for (ArcIt e(_graph); e != INVALID; ++e)

        c += (*_flow)[e] * _length[e];

      return c;

    }

    /// \brief Return the flow value on the given arc.

    ///

    /// This function returns the flow value on the given arc.

    /// It is \c 1 if the arc is involved in one of the found arc-disjoint

    /// paths, otherwise it is \c 0.

    ///

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

    /// this function.

    int flow(const Arc& arc) const {

      return (*_flow)[arc];

    }

    /// \brief Return a const reference to an arc map storing the

    /// This function returns a const reference to an arc map storing

    /// The node potentials provide the dual solution of the

    /// underlying \ref min_cost_flow "minimum cost flow problem".

    /// \brief Return a const reference to a node map storing the

    /// found potentials (the dual solution).

    /// This function returns a const reference to a node map storing

    /// the found potentials that provide the dual solution of the

    /// underlying \ref min_cost_flow "minimum cost flow problem".

    const PotentialMap& potentialMap() const {

      return *_potential;

    /// \param i The function returns the <tt>i</tt>-th path.

  SET(LP_TEST_LIBS lemon)

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

  IF(HAVE_CPLEX)

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

  ENDIF(HAVE_CPLEX)

  IF(HAVE_CLP)

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

  ENDIF(HAVE_CLP)

  TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})

  IF(WIN32 AND 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 -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}

    )

  ENDIF(WIN32 AND HAVE_CPLEX)

  SET(MIP_TEST_LIBS lemon)

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

  IF(HAVE_CPLEX)

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

  ENDIF(HAVE_CPLEX)

  IF(HAVE_CBC)

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

  ENDIF(HAVE_CBC)

  TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})

  IF(WIN32 AND 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 -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}

    )

  ENDIF(WIN32 AND HAVE_CPLEX)

#include <lemon/concepts/digraph.h>

  "label\n"

  "1\n"

  "2\n"

  "3\n"

  "4\n"

  "5\n"

  "6\n"

  "7\n"

  "8\n"

  "9\n"

  "10\n"

  "11\n"

  "12\n"

  "      length\n"

  " 1  2  70\n"

  " 1  3 150\n"

  " 1  4  80\n"

  " 2  8  80\n"

  " 3  5 140\n"

  " 4  6  60\n"

  " 4  7  80\n"

  " 4  8 110\n"

  " 5  7  60\n"

  " 5 11 120\n"

  " 6  3   0\n"

  " 6  9 140\n"

  " 6 10  90\n"

  " 7  1  30\n"

  " 8 12  60\n"

  " 9 12  50\n"

  "10 12  70\n"

  "10  2 100\n"

  "10  7  60\n"

  "11 10  20\n"

  "12 11  30\n"

// Check the interface of Suurballe

void checkSuurballeCompile()

{

  typedef int VType;

  typedef concepts::Digraph Digraph;

  typedef Digraph::Node Node;

  typedef Digraph::Arc Arc;

  typedef concepts::ReadMap<Arc, VType> LengthMap;

  typedef Suurballe<Digraph, LengthMap> SuurballeType;

  Digraph g;

  Node n;

  Arc e;

  LengthMap len;

  SuurballeType::FlowMap flow(g);

  SuurballeType::PotentialMap pi(g);

  SuurballeType suurb_test(g, len);

  const SuurballeType& const_suurb_test = suurb_test;

  suurb_test

    .flowMap(flow)

    .potentialMap(pi);

  int k;

  k = suurb_test.run(n, n);

  k = suurb_test.run(n, n, k);

  suurb_test.init(n);

  k = suurb_test.findFlow(n);

  k = suurb_test.findFlow(n, k);

  suurb_test.findPaths();

  int f;

  VType c;

  c = const_suurb_test.totalLength();

  f = const_suurb_test.flow(e);

  const SuurballeType::FlowMap& fm =

    const_suurb_test.flowMap();

  c = const_suurb_test.potential(n);

  const SuurballeType::PotentialMap& pm =

    const_suurb_test.potentialMap();

  k = const_suurb_test.pathNum();

  Path<Digraph> p = const_suurb_test.path(k);

  ignore_unused_variable_warning(fm);

  ignore_unused_variable_warning(pm);

}

  Node s, t;

    arcMap("length", length).

    node("source", s).

    node("target", t).

    Suurballe<ListDigraph> suurballe(digraph, length);

    check(suurballe.run(s, t) == 2, "Wrong number of paths");

    check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),

      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");

    Suurballe<ListDigraph> suurballe(digraph, length);

    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");

    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),

      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");

    Suurballe<ListDigraph> suurballe(digraph, length);

    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");

    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),

      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");

      Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);

      int k=sur.run(a,b,2);

        Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);

        int k=sur.run(pi->a,pi->b,2);