RhodeCode

SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)

INCLUDE(FindDoxygen)

INCLUDE(FindGhostscript)

FIND_PACKAGE(GLPK 4.33)

ADD_DEFINITIONS(-DHAVE_CONFIG_H)

IF(MSVC)

  SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4250 /wd4355 /wd4800 /wd4996")

# Suppressed warnings:

# C4250: 'class1' : inherits 'class2::member' via dominance

# C4355: 'this' : used in base member initializer list

# C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)

# C4996: 'function': was declared deprecated

ENDIF(MSVC)

INCLUDE(CheckTypeSize)

CHECK_TYPE_SIZE("long long" LONG_LONG)

ENABLE_TESTING()

ADD_SUBDIRECTORY(lemon)

  PATHS ${GLPK_REGKEY}/lib)

INCLUDE(FindPackageHandleStandardArgs)

FIND_PACKAGE_HANDLE_STANDARD_ARGS(GLPK DEFAULT_MSG GLPK_LIBRARY GLPK_INCLUDE_DIR)

IF(GLPK_FOUND)

  SET(GLPK_LIBRARIES ${GLPK_LIBRARY})

  SET(GLPK_BIN_DIR ${GLPK_ROOT_PATH}/bin)

ENDIF(GLPK_FOUND)

MARK_AS_ADVANCED(GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_BIN_DIR)

  random.cc

  bits/windows.cc

)

IF(HAVE_GLPK)

  SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)

  IF(WIN32)

    INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)

    INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)

    INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)

  ENDIF(WIN32)

ENDIF(HAVE_GLPK)

ADD_LIBRARY(lemon ${LEMON_SOURCES})

INSTALL(

  TARGETS lemon

  ARCHIVE DESTINATION lib

  COMPONENT library)

#ifndef LEMON_CIRCULATION_H

#define LEMON_CIRCULATION_H

#include <lemon/tolerance.h>

#include <lemon/elevator.h>

///\ingroup max_flow

///\file

///\brief Push-relabel algorithm for finding a feasible circulation.

///

namespace lemon {

     It is to find a feasible circulation when lower and upper bounds

     are given for the flow values on the arcs and lower bounds are

     given for the difference between the outgoing and incoming flow

     at the nodes.

     The exact formulation of this problem is the following.

     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$

     denotes the signed supply values of the nodes.

     If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$

     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with

     \f$-sup(u)\f$ demand.

     solution of the following problem.

     \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)

     \geq sup(u) \quad \forall u\in V, \f]

     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]

     (i.e. the total demand is less than the total supply and all the demands

     have to be satisfied while there could be supplies that are not used),

     then you could easily transform the problem to the above form by reversing

     the direction of the arcs and taking the negative of the supply values

     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).

     Note that this algorithm also provides a feasible solution for the

     \ref min_cost_flow "minimum cost flow problem".

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

     \tparam LM The type of the lower bound map. The default

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

      destroyStructures();

    }

  private:

    void createStructures() {

      _node_num = _el = countNodes(_g);

      if (!_flow) {

        _flow = Traits::createFlowMap(_g);

        _local_flow = true;

    }

    /// Sets the upper bound (capacity) map.

    /// Sets the upper bound (capacity) map.

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

      _up = ↦

      return *this;

    }

    /// Sets the supply map.

    /// Initializes the internal data structures.

    /// Initializes the internal data structures and sets all flow values

    /// to the lower bound.

    void init()

    {

      createStructures();

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

        (*_excess)[n] = (*_supply)[n];

      }

    /// Initializes the internal data structures using a greedy approach.

    /// Initializes the internal data structures using a greedy approach

    /// to construct the initial solution.

    void greedyInit()

    {

      createStructures();

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

        (*_excess)[n] = (*_supply)[n];

      }

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

          _flow->set(e, (*_up)[e]);

          (*_excess)[_g.target(e)] += (*_up)[e];

          (*_excess)[_g.source(e)] -= (*_up)[e];

          _flow->set(e, (*_lo)[e]);

          (*_excess)[_g.target(e)] += (*_lo)[e];

          (*_excess)[_g.source(e)] -= (*_lo)[e];

        } else {

          Flow fc = -(*_excess)[_g.target(e)];

          _flow->set(e, fc);

    ///Check whether or not the last execution provides a barrier.

    ///\sa barrier()

    ///\sa barrierMap()

    bool checkBarrier() const

    {

      Flow delta=0;

      for(NodeIt n(_g);n!=INVALID;++n)

        if(barrier(n))

          delta-=(*_supply)[n];

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

        {

          Node s=_g.source(e);

          Node t=_g.target(e);

          else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];

        }

      return _tol.negative(delta);

    }

    /// @}

#cmakedefine HAVE_LONG_LONG 1

#cmakedefine HAVE_LP 1

#cmakedefine HAVE_MIP 1

#cmakedefine HAVE_GLPK 1

///\ingroup shortest_path

///\file

///\brief An algorithm for finding arc-disjoint paths between two

/// nodes having minimum total length.

#include <vector>

#include <lemon/bin_heap.h>

#include <lemon/path.h>

#include <lemon/list_graph.h>

#include <lemon/maps.h>

namespace lemon {

  /// having minimum total length.

  ///

  /// \ref lemon::Suurballe "Suurballe" implements an algorithm for

  /// finding arc-disjoint paths having minimum total length (cost)

  /// from a given source node to a given target node in a digraph.

  ///

  ///

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

  ///

  /// \warning Length values should be \e non-negative \e integers.

  ///

  /// \note For finding node-disjoint paths this algorithm can be used

#ifdef DOXYGEN

  template <typename GR, typename LEN>

#else

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

#endif

  class Suurballe

  {

    TEMPLATE_DIGRAPH_TYPEDEFS(GR);

    /// The type of the digraph the algorithm runs on.

    typedef GR Digraph;

    /// The type of the length map.

    typedef LEN LengthMap;

    /// The type of the lengths.

    typedef typename LengthMap::Value Length;

    /// The type of the flow map.

    typedef typename Digraph::template ArcMap<int> FlowMap;

    /// The type of the potential map.

    typedef typename Digraph::template NodeMap<Length> PotentialMap;

    /// The type of the path structures.

  private:

    class ResidualDijkstra

    {

      typedef typename Digraph::template NodeMap<int> HeapCrossRef;

      typedef BinHeap<Length, HeapCrossRef> Heap;

    private:

      Node _s;

      Node _t;

    public:

      /// Constructor.

                        const FlowMap &flow,

                        const LengthMap &length,

                        PotentialMap &potential,

                        PredMap &pred,

                        Node s, Node t ) :

      /// \brief Run the algorithm. It returns \c true if a path is found

      /// from the source node to the target node.

      bool run() {

        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);

        Heap heap(heap_cross_ref);

  public:

    /// \brief Constructor.

    ///

    /// Constructor.

    ///

    /// \param length The length (cost) values of the arcs.

    /// Destructor.

    ~Suurballe() {

      if (_local_flow) delete _flow;

      if (_local_potential) delete _potential;

      delete _dijkstra;

    }

    /// \brief Set the flow map.

    ///

    /// This function sets the flow map.

    ///

    ///

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

    Suurballe& flowMap(FlowMap &map) {

      if (_local_flow) {

        delete _flow;

        _local_flow = false;

      return *this;

    }

    /// \brief Set the potential map.

    ///

    /// This function sets the potential map.

    ///

    ///

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

    Suurballe& potentialMap(PotentialMap &map) {

      if (_local_potential) {

        delete _potential;

        _local_potential = false;

    /// @{

    /// \brief Run the algorithm.

    ///

    /// This function runs the algorithm.

    ///

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

    ///

    /// \return \c k if there are at least \c k arc-disjoint paths from

    /// \c s to \c t in the digraph. Otherwise it returns the number of

    /// arc-disjoint paths found.

    ///

    /// \code

    ///   s.findPaths();

    /// \endcode

      findPaths();

      return _path_num;

    }

    /// \brief Initialize the algorithm.

    ///

    /// This function initializes the algorithm.

      // Initialize maps

      if (!_flow) {

        _flow = new FlowMap(_graph);

        _local_flow = true;

      }

      if (!_potential) {

        _potential = new PotentialMap(_graph);

        _local_potential = true;

      }

      for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;

      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;

    }

    ///

    /// This function executes the successive shortest path algorithm to

    /// arc-disjoint paths.

    ///

    /// \return \c k if there are at least \c k arc-disjoint paths from

    ///

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

      // Find shortest paths

      _path_num = 0;

      while (_path_num < k) {

        // Run Dijkstra

        if (!_dijkstra->run()) break;

        ++_path_num;

      }

      return _path_num;

    }

    /// \brief Compute the paths from the flow.

    ///

    ///

    /// \pre \ref init() and \ref findFlow() must be called before using

    /// this function.

    void findPaths() {

      FlowMap res_flow(_graph);

      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];

      paths.clear();

      paths.resize(_path_num);

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

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

    /// functions.

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

    /// @{

    /// found flow.

    ///

    /// the flow that is the union of the found arc-disjoint paths.

    ///

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

    /// this function.

    const FlowMap& flowMap() const {

      return *_flow;

    }

    /// \brief Return the potential of the given node.

    ///

    /// This function returns the potential of the given node.

    ///

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

    /// this function.

    Length potential(const Node& node) const {

      return (*_potential)[node];

    }

    ///

    ///

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

    /// this function.

    }

    /// \brief Return the number of the found paths.

    ///

    /// This function returns the number of the found paths.

    ///

    }

    /// \brief Return a const reference to the specified path.

    ///

    /// This function returns a const reference to the specified path.

    ///

    /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.

    ///

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

    /// this function.

    Path path(int i) const {

      return paths[i];

INCLUDE_DIRECTORIES(

  ${PROJECT_SOURCE_DIR}

  ${PROJECT_BINARY_DIR}

)

LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)

SET(TESTS

  adaptors_test

  bfs_test

  circulation_test

  suurballe_test

  time_measure_test

  unionfind_test)

IF(HAVE_LP)

  ADD_EXECUTABLE(lp_test lp_test.cc)

  IF(HAVE_GLPK)

  ENDIF(HAVE_GLPK)

  ADD_TEST(lp_test lp_test)

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

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

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

    )

  ENDIF(WIN32 AND HAVE_GLPK)

ENDIF(HAVE_LP)

IF(HAVE_MIP)

  ADD_EXECUTABLE(mip_test mip_test.cc)

  IF(HAVE_GLPK)

  ENDIF(HAVE_GLPK)

  ADD_TEST(mip_test mip_test)

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

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

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

    )

  ENDIF(WIN32 AND HAVE_GLPK)

ENDIF(HAVE_MIP)

FOREACH(TEST_NAME ${TESTS})

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

  TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)

  ADD_TEST(${TEST_NAME} ${TEST_NAME})

#include <iostream>

#include <lemon/list_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/path.h>

#include <lemon/suurballe.h>

#include "test_tools.h"

using namespace lemon;

char test_lgf[] =

  "@nodes\n"

  "@arcs\n"

  "@attributes\n"

  "source  1\n"

  "target 12\n"

  "@end\n";

// Check the feasibility of the flow

template <typename Digraph, typename FlowMap>

bool checkFlow( const Digraph& gr, const FlowMap& flow,

                typename Digraph::Node s, typename Digraph::Node t,

                int value )

{

// Check a path

template <typename Digraph, typename Path>

bool checkPath( const Digraph& gr, const Path& path,

                typename Digraph::Node s, typename Digraph::Node t)

{

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  Node n = s;

  for (int i = 0; i < path.length(); ++i) {

    if (gr.source(path.nth(i)) != n) return false;

    n = gr.target(path.nth(i));

  }

{

  DIGRAPH_TYPEDEFS(ListDigraph);

  // Read the test digraph

  ListDigraph digraph;

  ListDigraph::ArcMap<int> length(digraph);

  std::istringstream input(test_lgf);

  DigraphReader<ListDigraph>(digraph, input).