RhodeCode

CMAKE_MINIMUM_REQUIRED(VERSION 2.6)

IF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)

  INCLUDE(${CMAKE_SOURCE_DIR}/cmake/version.cmake)

ELSE(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)

  SET(PROJECT_NAME "LEMON")

  SET(PROJECT_VERSION "hg-tip" CACHE STRING "LEMON version string.")

ENDIF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)

PROJECT(${PROJECT_NAME})

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)

IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})

  ADD_SUBDIRECTORY(demo)

  ADD_SUBDIRECTORY(tools)

  ADD_SUBDIRECTORY(doc)

  ADD_SUBDIRECTORY(test)

ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})

IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})

  IF(WIN32)

    SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})

    SET(CPACK_PACKAGE_VENDOR "EGRES")

    SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY

      "LEMON - Library of Efficient Models and Optimization in Networks")

    SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")

    SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})

    SET(CPACK_PACKAGE_INSTALL_DIRECTORY

SET(GLPK_REGKEY "[HKEY_LOCAL_MACHINE\\SOFTWARE\\GnuWin32\\Glpk;InstallPath]")

GET_FILENAME_COMPONENT(GLPK_ROOT_PATH ${GLPK_REGKEY} ABSOLUTE)

FIND_PATH(GLPK_INCLUDE_DIR

  glpk.h

  PATHS ${GLPK_REGKEY}/include)

FIND_LIBRARY(GLPK_LIBRARY

  NAMES glpk

  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)

INCLUDE_DIRECTORIES(

  ${PROJECT_SOURCE_DIR}

  ${PROJECT_BINARY_DIR}

)

CONFIGURE_FILE(

  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake

  ${CMAKE_CURRENT_BINARY_DIR}/config.h

)

SET(LEMON_SOURCES

  arg_parser.cc

  base.cc

  color.cc

  lp_base.cc

  lp_skeleton.cc

  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)

INSTALL(

  DIRECTORY . bits concepts

  DESTINATION include/lemon

  COMPONENT headers

  FILES_MATCHING PATTERN "*.h")

/* -*- 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_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 {

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

  ///

  /// Default traits class of Circulation class.

  ///

  /// \tparam GR Type of the digraph the algorithm runs on.

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

  /// \tparam UM The type of the upper bound (capacity) map.

  /// \tparam SM The type of the supply map.

  template <typename GR, typename LM,

            typename UM, typename SM>

  struct CirculationDefaultTraits {

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

    typedef GR Digraph;

    /// \brief The type of the lower bound map.

    ///

    /// \param max_level The maximum level of the elevator.

    static Elevator* createElevator(const Digraph& digraph, int max_level) {

      return new Elevator(digraph, max_level);

    }

    /// \brief The tolerance used by the algorithm

    ///

    /// The tolerance used by the algorithm to handle inexact computation.

    typedef lemon::Tolerance<Flow> Tolerance;

  };

  /**

     \brief Push-relabel algorithm for the network circulation problem.

     \ingroup max_flow

     This class implements a push-relabel algorithm for the \e network

     \e circulation problem.

     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]

     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be

     zero or negative in order to have a feasible solution (since the sum

     of the expressions on the left-hand side of the inequalities is zero).

     It means that the total demand must be greater or equal to the total

     supply and all the supplies have to be carried out from the supply nodes,

     but there could be demands that are not satisfied.

     If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand

     constraints have to be satisfied with equality, i.e. all demands

     have to be satisfied and all supplies have to be used.

     If you need the opposite inequalities in the supply/demand constraints

     (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>".

     \tparam UM The type of the upper bound (capacity) map.

     The default map type is \c LM.

     \tparam SM The type of the supply map. The default map type is

     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".

  */

#ifdef DOXYGEN

template< typename GR,

          typename LM,

          typename UM,

          typename SM,

          typename TR >

#else

template< typename GR,

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

          typename UM = LM,

          typename SM = typename GR::template NodeMap<typename UM::Value>,

          typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >

#endif

    /// Constructor.

    /// The constructor of the class.

    ///

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

    /// \param lower The lower bounds for the flow values on the arcs.

    /// \param upper The upper bounds (capacities) for the flow values 

    /// on the arcs.

    /// \param supply The signed supply values of the nodes.

    Circulation(const Digraph &graph, const LowerMap &lower,

                const UpperMap &upper, const SupplyMap &supply)

      : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),

        _flow(NULL), _local_flow(false), _level(NULL), _local_level(false),

        _excess(NULL) {}

    /// Destructor.

    ~Circulation() {

      destroyStructures();

    }

  private:

    void createStructures() {

      _node_num = _el = countNodes(_g);

      if (!_flow) {

        _flow = Traits::createFlowMap(_g);

        _local_flow = true;

      }

      if (!_level) {

        _level = Traits::createElevator(_g, _node_num);

        _local_level = true;

      }

      if (!_excess) {

        _excess = new ExcessMap(_g);

      }

    }

    void destroyStructures() {

      if (_local_flow) {

        delete _flow;

      }

      if (_local_level) {

        delete _level;

      }

      if (_excess) {

        delete _excess;

      }

    }

  public:

    /// Sets the lower bound map.

    /// Sets the lower bound map.

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

    Circulation& lowerMap(const LowerMap& map) {

      _lo = ↦

      return *this;

    }

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

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

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

      _up = ↦

      return *this;

    }

    /// Sets the supply map.

    /// Sets the supply map.

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

    Circulation& supplyMap(const SupplyMap& map) {

      _supply = ↦

      return *this;

    }

    /// \brief Sets the flow map.

    ///

    /// Sets the flow map.

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

    /// \ref init(), an instance will be allocated automatically.

    /// The destructor deallocates this automatically allocated map,

    /// of course.

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

    Circulation& flowMap(FlowMap& map) {

      if (_local_flow) {

        delete _flow;

      return *this;

    }

    /// \brief Returns a const reference to the tolerance.

    ///

    /// Returns a const reference to the tolerance.

    const Tolerance& tolerance() const {

      return tolerance;

    }

    /// \name Execution Control

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

    /// If you need more control on the initial solution or the execution,

    /// first you have to call one of the \ref init() functions, then

    /// the \ref start() function.

    ///@{

    /// 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];

      }

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

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

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

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

      }

      // global relabeling tested, but in general case it provides

      // worse performance for random digraphs

      _level->initStart();

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

        _level->initAddItem(n);

      _level->initFinish();

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

        if(_tol.positive((*_excess)[n]))

          _level->activate(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);

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

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

        }

      }

      _level->initStart();

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

        _level->initAddItem(n);

      _level->initFinish();

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

        if(_tol.positive((*_excess)[n]))

          _level->activate(n);

    }

    ///Executes the algorithm

    ///This function executes the algorithm.

    ///

    ///Check if the found flow is a feasible circulation,

    ///

    bool checkFlow() const {

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

        if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;

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

        {

          Flow dif=-(*_supply)[n];

          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];

          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];

          if(_tol.negative(dif)) return false;

        }

      return true;

    }

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

    ///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);

    }

    /// @}

  };

}

#endif

#cmakedefine HAVE_LONG_LONG 1

#cmakedefine HAVE_LP 1

#cmakedefine HAVE_MIP 1

#cmakedefine HAVE_GLPK 1

 *

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

#define LEMON_SUURBALLE_H

///\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 {

  /// \addtogroup shortest_path

  /// @{

  /// \brief Algorithm for finding arc-disjoint paths between two nodes

  /// 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);

    typedef ConstMap<Arc, int> ConstArcMap;

    typedef typename GR::template NodeMap<Arc> PredMap;

  public:

    /// 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:

      // The digraph the algorithm runs on

      const Digraph &_graph;

      // The main maps

      const FlowMap &_flow;

      const LengthMap &_length;

      PotentialMap &_potential;

      // The distance map

      PotentialMap _dist;

      // The pred arc map

      PredMap &_pred;

      // The processed (i.e. permanently labeled) nodes

      std::vector<Node> _proc_nodes;

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

        heap.push(_s, 0);

        _pred[_s] = INVALID;

        _proc_nodes.clear();

        // Process nodes

        while (!heap.empty() && heap.top() != _t) {

          Node u = heap.top(), v;

          Length d = heap.prio() + _potential[u], nd;

          _dist[u] = heap.prio();

          heap.pop();

          _proc_nodes.push_back(u);

          // Traverse outgoing arcs

          for (OutArcIt e(_graph, u); e != INVALID; ++e) {

            if (_flow[e] == 0) {

              v = _graph.target(e);

              switch(heap.state(v)) {

              case Heap::PRE_HEAP:

    PotentialMap *_potential;

    bool _local_potential;

    // The source node

    Node _source;

    // The target node

    Node _target;

    // Container to store the found paths

    std::vector< SimplePath<Digraph> > paths;

    int _path_num;

    // The pred arc map

    PredMap _pred;

    // Implementation of the Dijkstra algorithm for finding augmenting

    // shortest paths in the residual network

    ResidualDijkstra *_dijkstra;

  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;

      }

      _flow = ↦

      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;

      }

      _potential = ↦

      return *this;

    }

    /// \name Execution Control

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

    /// function.

    /// \n

    /// If you only need the flow that is the union of the found

    /// arc-disjoint paths, you may call init() and findFlow().

    /// @{

    /// \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;

        // Set the flow along the found shortest path

        Node u = _target;

        Arc e;

        while ((e = _pred[u]) != INVALID) {

          if (u == _graph.target(e)) {

            (*_flow)[e] = 1;

            u = _graph.source(e);

          } else {

            (*_flow)[e] = 0;

            u = _graph.target(e);

          }

        }

      }

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

        Node n = _source;

        while (n != _target) {

          OutArcIt e(_graph, n);

          for ( ; res_flow[e] == 0; ++e) ;

          n = _graph.target(e);

          paths[i].addBack(e);

          res_flow[e] = 0;

        }

      }

    }

    /// @}

    /// \name Query Functions

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

    /// functions.

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

    /// @{