COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
2 added
9 edited

Legend:

Unmodified
Added
Removed

  • CMakeLists.txt

    r599 r668  
    1515INCLUDE(FindGhostscript)
    1616FIND_PACKAGE(GLPK 4.33)
     17FIND_PACKAGE(CPLEX)
     18FIND_PACKAGE(COIN)
    1719
    1820ADD_DEFINITIONS(-DHAVE_CONFIG_H)
    … …  
    2628# C4996: 'function': was declared deprecated
    2729ENDIF(MSVC)
    28 
    29 IF(GLPK_FOUND)
    30   SET(HAVE_LP TRUE)
    31   SET(HAVE_MIP TRUE)
    32   SET(HAVE_GLPK TRUE)
    33 ENDIF(GLPK_FOUND)
    3430
    3531INCLUDE(CheckTypeSize)

  • cmake/FindGLPK.cmake

    r496 r666  
    1414
    1515IF(GLPK_FOUND)
     16  SET(GLPK_INCLUDE_DIRS ${GLPK_INCLUDE_DIR})
    1617  SET(GLPK_LIBRARIES ${GLPK_LIBRARY})
    1718  SET(GLPK_BIN_DIR ${GLPK_ROOT_PATH}/bin)
    … …  
    1920
    2021MARK_AS_ADVANCED(GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_BIN_DIR)
     22
     23IF(GLPK_FOUND)
     24  SET(HAVE_LP TRUE)
     25  SET(HAVE_MIP TRUE)
     26  SET(HAVE_GLPK TRUE)
     27ENDIF(GLPK_FOUND)

  • lemon/CMakeLists.txt

    r596 r668  
    2121IF(HAVE_GLPK)
    2222  SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
    23   INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
     23  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS})
    2424  IF(WIN32)
    2525    INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
    … …  
    2828  ENDIF(WIN32)
    2929ENDIF(HAVE_GLPK)
     30
     31IF(HAVE_CPLEX)
     32  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
     33  INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
     34ENDIF(HAVE_CPLEX)
     35
     36IF(HAVE_CLP)
     37  SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
     38  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
     39ENDIF(HAVE_CLP)
     40
     41IF(HAVE_CBC)
     42  SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
     43  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
     44ENDIF(HAVE_CBC)
    3045
    3146ADD_LIBRARY(lemon ${LEMON_SOURCES})

  • lemon/circulation.h

    r658 r669  
    2222#include <lemon/tolerance.h>
    2323#include <lemon/elevator.h>
     24#include <limits>
    2425
    2526///\ingroup max_flow
    … …  
    120121
    121122     The exact formulation of this problem is the following.
    122      Let \f$G=(V,A)\f$ be a digraph,
    123      \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and
    124      upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$
     123     Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$
     124     \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and
     125     upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$
    125126     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
    126127     denotes the signed supply values of the nodes.
    … …  
    128129     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
    129130     \f$-sup(u)\f$ demand.
    130      A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
     131     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$
    131132     solution of the following problem.
    132133
    … …  
    151152     the direction of the arcs and taking the negative of the supply values
    152153     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
     154
     155     This algorithm either calculates a feasible circulation, or provides
     156     a \ref barrier() "barrier", which prooves that a feasible soultion
     157     cannot exist.
    153158
    154159     Note that this algorithm also provides a feasible solution for the
    … …  
    338343  private:
    339344
     345    bool checkBoundMaps() {
     346      for (ArcIt e(_g);e!=INVALID;++e) {
     347        if (_tol.less((*_up)[e], (*_lo)[e])) return false;
     348      }
     349      return true;
     350    }
     351
    340352    void createStructures() {
    341353      _node_num = _el = countNodes(_g);
    … …  
    381393    /// Sets the upper bound (capacity) map.
    382394    /// \return <tt>(*this)</tt>
    383     Circulation& upperMap(const LowerMap& map) {
     395    Circulation& upperMap(const UpperMap& map) {
    384396      _up = &map;
    385397      return *this;
    … …  
    468480    void init()
    469481    {
     482      LEMON_DEBUG(checkBoundMaps(),
     483        "Upper bounds must be greater or equal to the lower bounds");
     484
    470485      createStructures();
    471486
    … …  
    497512    void greedyInit()
    498513    {
     514      LEMON_DEBUG(checkBoundMaps(),
     515        "Upper bounds must be greater or equal to the lower bounds");
     516
    499517      createStructures();
    500518
    … …  
    504522
    505523      for (ArcIt e(_g);e!=INVALID;++e) {
    506         if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
     524        if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) {
    507525          _flow->set(e, (*_up)[e]);
    508526          (*_excess)[_g.target(e)] += (*_up)[e];
    509527          (*_excess)[_g.source(e)] -= (*_up)[e];
    510         } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
     528        } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) {
    511529          _flow->set(e, (*_lo)[e]);
    512530          (*_excess)[_g.target(e)] += (*_lo)[e];
    … …  
    749767    {
    750768      Flow delta=0;
     769      Flow inf_cap = std::numeric_limits<Flow>::has_infinity ?
     770        std::numeric_limits<Flow>::infinity() :
     771        std::numeric_limits<Flow>::max();
    751772      for(NodeIt n(_g);n!=INVALID;++n)
    752773        if(barrier(n))
    … …  
    756777          Node s=_g.source(e);
    757778          Node t=_g.target(e);
    758           if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];
     779          if(barrier(s)&&!barrier(t)) {
     780            if (_tol.less(inf_cap - (*_up)[e], delta)) return false;
     781            delta+=(*_up)[e];
     782          }
    759783          else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];
    760784        }

  • lemon/config.h.cmake

    r564 r668  
    33#cmakedefine HAVE_MIP 1
    44#cmakedefine HAVE_GLPK 1
     5#cmakedefine HAVE_CPLEX 1
     6#cmakedefine HAVE_CLP 1
     7#cmakedefine HAVE_CBC 1

  • lemon/suurballe.h

    r631 r670  
    2626
    2727#include <vector>
     28#include <limits>
    2829#include <lemon/bin_heap.h>
    2930#include <lemon/path.h>
    … …  
    4344  /// from a given source node to a given target node in a digraph.
    4445  ///
    45   /// In fact, this implementation is the specialization of the
    46   /// \ref CapacityScaling "successive shortest path" algorithm.
     46  /// Note that this problem is a special case of the \ref min_cost_flow
     47  /// "minimum cost flow problem". This implementation is actually an
     48  /// efficient specialized version of the \ref CapacityScaling
     49  /// "Successive Shortest Path" algorithm directly for this problem.
     50  /// Therefore this class provides query functions for flow values and
     51  /// node potentials (the dual solution) just like the minimum cost flow
     52  /// algorithms.
    4753  ///
    4854  /// \tparam GR The digraph type the algorithm runs on.
    49   /// The default value is \c ListDigraph.
    50   /// \tparam LEN The type of the length (cost) map.
    51   /// The default value is <tt>Digraph::ArcMap<int></tt>.
     55  /// \tparam LEN The type of the length map.
     56  /// The default value is <tt>GR::ArcMap<int></tt>.
    5257  ///
    5358  /// \warning Length values should be \e non-negative \e integers.
    5459  ///
    5560  /// \note For finding node-disjoint paths this algorithm can be used
    56   /// with \ref SplitNodes.
     61  /// along with the \ref SplitNodes adaptor.
    5762#ifdef DOXYGEN
    5863  template <typename GR, typename LEN>
    5964#else
    60   template < typename GR = ListDigraph,
     65  template < typename GR,
    6166             typename LEN = typename GR::template ArcMap<int> >
    6267#endif
    … …  
    7681    /// The type of the lengths.
    7782    typedef typename LengthMap::Value Length;
     83#ifdef DOXYGEN
     84    /// The type of the flow map.
     85    typedef GR::ArcMap<int> FlowMap;
     86    /// The type of the potential map.
     87    typedef GR::NodeMap<Length> PotentialMap;
     88#else
    7889    /// The type of the flow map.
    7990    typedef typename Digraph::template ArcMap<int> FlowMap;
    8091    /// The type of the potential map.
    8192    typedef typename Digraph::template NodeMap<Length> PotentialMap;
     93#endif
     94
    8295    /// The type of the path structures.
    83     typedef SimplePath<Digraph> Path;
     96    typedef SimplePath<GR> Path;
    8497
    8598  private:
    8699
    87     /// \brief Special implementation of the Dijkstra algorithm
    88     /// for finding shortest paths in the residual network.
    89     ///
    90     /// \ref ResidualDijkstra is a special implementation of the
    91     /// \ref Dijkstra algorithm for finding shortest paths in the
    92     /// residual network of the digraph with respect to the reduced arc
    93     /// lengths and modifying the node potentials according to the
    94     /// distance of the nodes.
     100    // ResidualDijkstra is a special implementation of the
     101    // Dijkstra algorithm for finding shortest paths in the
     102    // residual network with respect to the reduced arc lengths
     103    // and modifying the node potentials according to the
     104    // distance of the nodes.
    95105    class ResidualDijkstra
    96106    {
    … …  
    121131
    122132      /// Constructor.
    123       ResidualDijkstra( const Digraph &digraph,
     133      ResidualDijkstra( const Digraph &graph,
    124134                        const FlowMap &flow,
    125135                        const LengthMap &length,
    … …  
    127137                        PredMap &pred,
    128138                        Node s, Node t ) :
    129         _graph(digraph), _flow(flow), _length(length), _potential(potential),
    130         _dist(digraph), _pred(pred), _s(s), _t(t) {}
     139        _graph(graph), _flow(flow), _length(length), _potential(potential),
     140        _dist(graph), _pred(pred), _s(s), _t(t) {}
    131141
    132142      /// \brief Run the algorithm. It returns \c true if a path is found
    … …  
    237247    /// Constructor.
    238248    ///
    239     /// \param digraph The digraph the algorithm runs on.
     249    /// \param graph The digraph the algorithm runs on.
    240250    /// \param length The length (cost) values of the arcs.
    241     /// \param s The source node.
    242     /// \param t The target node.
    243     Suurballe( const Digraph &digraph,
    244                const LengthMap &length,
    245                Node s, Node t ) :
    246       _graph(digraph), _length(length), _flow(0), _local_flow(false),
    247       _potential(0), _local_potential(false), _source(s), _target(t),
    248       _pred(digraph) {}
     251    Suurballe( const Digraph &graph,
     252               const LengthMap &length ) :
     253      _graph(graph), _length(length), _flow(0), _local_flow(false),
     254      _potential(0), _local_potential(false), _pred(graph)
     255    {
     256      LEMON_ASSERT(std::numeric_limits<Length>::is_integer,
     257        "The length type of Suurballe must be integer");
     258    }
    249259
    250260    /// Destructor.
    … …  
    258268    ///
    259269    /// This function sets the flow map.
    260     ///
    261     /// The found flow contains only 0 and 1 values. It is the union of
    262     /// the found arc-disjoint paths.
     270    /// If it is not used before calling \ref run() or \ref init(),
     271    /// an instance will be allocated automatically. The destructor
     272    /// deallocates this automatically allocated map, of course.
     273    ///
     274    /// The found flow contains only 0 and 1 values, since it is the
     275    /// union of the found arc-disjoint paths.
    263276    ///
    264277    /// \return <tt>(*this)</tt>
    … …  
    275288    ///
    276289    /// This function sets the potential map.
    277     ///
    278     /// The potentials provide the dual solution of the underlying
    279     /// minimum cost flow problem.
     290    /// If it is not used before calling \ref run() or \ref init(),
     291    /// an instance will be allocated automatically. The destructor
     292    /// deallocates this automatically allocated map, of course.
     293    ///
     294    /// The node potentials provide the dual solution of the underlying
     295    /// \ref min_cost_flow "minimum cost flow problem".
    280296    ///
    281297    /// \return <tt>(*this)</tt>
    … …  
    302318    /// This function runs the algorithm.
    303319    ///
     320    /// \param s The source node.
     321    /// \param t The target node.
    304322    /// \param k The number of paths to be found.
    305323    ///
    … …  
    308326    /// arc-disjoint paths found.
    309327    ///
    310     /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
    311     /// shortcut of the following code.
     328    /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is
     329    /// just a shortcut of the following code.
    312330    /// \code
    313     ///   s.init();
    314     ///   s.findFlow(k);
     331    ///   s.init(s);
     332    ///   s.findFlow(t, k);
    315333    ///   s.findPaths();
    316334    /// \endcode
    317     int run(int k = 2) {
    318       init();
    319       findFlow(k);
     335    int run(const Node& s, const Node& t, int k = 2) {
     336      init(s);
     337      findFlow(t, k);
    320338      findPaths();
    321339      return _path_num;
    … …  
    325343    ///
    326344    /// This function initializes the algorithm.
    327     void init() {
     345    ///
     346    /// \param s The source node.
     347    void init(const Node& s) {
     348      _source = s;
     349
    328350      // Initialize maps
    329351      if (!_flow) {
    … …  
    337359      for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
    338360      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
    339 
    340       _dijkstra = new ResidualDijkstra( _graph, *_flow, _length,
    341                                         *_potential, _pred,
    342                                         _source, _target );
    343     }
    344 
    345     /// \brief Execute the successive shortest path algorithm to find
    346     /// an optimal flow.
     361    }
     362
     363    /// \brief Execute the algorithm to find an optimal flow.
    347364    ///
    348365    /// This function executes the successive shortest path algorithm to
    349     /// find a minimum cost flow, which is the union of \c k or less
     366    /// find a minimum cost flow, which is the union of \c k (or less)
    350367    /// arc-disjoint paths.
    351368    ///
     369    /// \param t The target node.
     370    /// \param k The number of paths to be found.
     371    ///
    352372    /// \return \c k if there are at least \c k arc-disjoint paths from
    353     /// \c s to \c t in the digraph. Otherwise it returns the number of
    354     /// arc-disjoint paths found.
     373    /// the source node to the given node \c t in the digraph.
     374    /// Otherwise it returns the number of arc-disjoint paths found.
    355375    ///
    356376    /// \pre \ref init() must be called before using this function.
    357     int findFlow(int k = 2) {
     377    int findFlow(const Node& t, int k = 2) {
     378      _target = t;
     379      _dijkstra =
     380        new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred,
     381                              _source, _target );
     382
    358383      // Find shortest paths
    359384      _path_num = 0;
    … …  
    381406    /// \brief Compute the paths from the flow.
    382407    ///
    383     /// This function computes the paths from the flow.
     408    /// This function computes the paths from the found minimum cost flow,
     409    /// which is the union of some arc-disjoint paths.
    384410    ///
    385411    /// \pre \ref init() and \ref findFlow() must be called before using
    386412    /// this function.
    387413    void findPaths() {
    388       // Create the residual flow map (the union of the paths not found
    389       // so far)
    390414      FlowMap res_flow(_graph);
    391415      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
    … …  
    414438    /// @{
    415439
    416     /// \brief Return a const reference to the arc map storing the
    417     /// found flow.
    418     ///
    419     /// This function returns a const reference to the arc map storing
    420     /// the flow that is the union of the found arc-disjoint paths.
    421     ///
    422     /// \pre \ref run() or \ref findFlow() must be called before using
    423     /// this function.
    424     const FlowMap& flowMap() const {
    425       return *_flow;
    426     }
    427 
    428     /// \brief Return a const reference to the node map storing the
    429     /// found potentials (the dual solution).
    430     ///
    431     /// This function returns a const reference to the node map storing
    432     /// the found potentials that provide the dual solution of the
    433     /// underlying minimum cost flow problem.
    434     ///
    435     /// \pre \ref run() or \ref findFlow() must be called before using
    436     /// this function.
    437     const PotentialMap& potentialMap() const {
    438       return *_potential;
    439     }
    440 
    441     /// \brief Return the flow on the given arc.
    442     ///
    443     /// This function returns the flow on the given arc.
    444     /// It is \c 1 if the arc is involved in one of the found paths,
    445     /// otherwise it is \c 0.
    446     ///
    447     /// \pre \ref run() or \ref findFlow() must be called before using
    448     /// this function.
    449     int flow(const Arc& arc) const {
    450       return (*_flow)[arc];
    451     }
    452 
    453     /// \brief Return the potential of the given node.
    454     ///
    455     /// This function returns the potential of the given node.
    456     ///
    457     /// \pre \ref run() or \ref findFlow() must be called before using
    458     /// this function.
    459     Length potential(const Node& node) const {
    460       return (*_potential)[node];
    461     }
    462 
    463     /// \brief Return the total length (cost) of the found paths (flow).
    464     ///
    465     /// This function returns the total length (cost) of the found paths
    466     /// (flow). The complexity of the function is O(e).
     440    /// \brief Return the total length of the found paths.
     441    ///
     442    /// This function returns the total length of the found paths, i.e.
     443    /// the total cost of the found flow.
     444    /// The complexity of the function is O(e).
    467445    ///
    468446    /// \pre \ref run() or \ref findFlow() must be called before using
    … …  
    475453    }
    476454
     455    /// \brief Return the flow value on the given arc.
     456    ///
     457    /// This function returns the flow value on the given arc.
     458    /// It is \c 1 if the arc is involved in one of the found arc-disjoint
     459    /// paths, otherwise it is \c 0.
     460    ///
     461    /// \pre \ref run() or \ref findFlow() must be called before using
     462    /// this function.
     463    int flow(const Arc& arc) const {
     464      return (*_flow)[arc];
     465    }
     466
     467    /// \brief Return a const reference to an arc map storing the
     468    /// found flow.
     469    ///
     470    /// This function returns a const reference to an arc map storing
     471    /// the flow that is the union of the found arc-disjoint paths.
     472    ///
     473    /// \pre \ref run() or \ref findFlow() must be called before using
     474    /// this function.
     475    const FlowMap& flowMap() const {
     476      return *_flow;
     477    }
     478
     479    /// \brief Return the potential of the given node.
     480    ///
     481    /// This function returns the potential of the given node.
     482    /// The node potentials provide the dual solution of the
     483    /// underlying \ref min_cost_flow "minimum cost flow problem".
     484    ///
     485    /// \pre \ref run() or \ref findFlow() must be called before using
     486    /// this function.
     487    Length potential(const Node& node) const {
     488      return (*_potential)[node];
     489    }
     490
     491    /// \brief Return a const reference to a node map storing the
     492    /// found potentials (the dual solution).
     493    ///
     494    /// This function returns a const reference to a node map storing
     495    /// the found potentials that provide the dual solution of the
     496    /// underlying \ref min_cost_flow "minimum cost flow problem".
     497    ///
     498    /// \pre \ref run() or \ref findFlow() must be called before using
     499    /// this function.
     500    const PotentialMap& potentialMap() const {
     501      return *_potential;
     502    }
     503
    477504    /// \brief Return the number of the found paths.
    478505    ///
    … …  
    489516    /// This function returns a const reference to the specified path.
    490517    ///
    491     /// \param i The function returns the \c i-th path.
     518    /// \param i The function returns the <tt>i</tt>-th path.
    492519    /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
    493520    ///

  • test/CMakeLists.txt

    r658 r668  
    33  ${PROJECT_BINARY_DIR}
    44)
    5 
    6 IF(HAVE_GLPK)
    7   INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
    8 ENDIF(HAVE_GLPK)
    95
    106LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
    … …  
    4339IF(HAVE_LP)
    4440  ADD_EXECUTABLE(lp_test lp_test.cc)
     41  SET(LP_TEST_LIBS lemon)
    4542  IF(HAVE_GLPK)
    46     TARGET_LINK_LIBRARIES(lp_test lemon ${GLPK_LIBRARIES})
     43    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${GLPK_LIBRARIES})
    4744  ENDIF(HAVE_GLPK)
     45  IF(HAVE_CPLEX)
     46    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES})
     47  ENDIF(HAVE_CPLEX)
     48  IF(HAVE_CLP)
     49    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES})
     50  ENDIF(HAVE_CLP)
     51  TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
    4852  ADD_TEST(lp_test lp_test)
    4953
    … …  
    5761    )
    5862  ENDIF(WIN32 AND HAVE_GLPK)
     63  IF(WIN32 AND HAVE_CPLEX)
     64    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
     65    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
     66    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
     67      COMMAND cmake -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
     68    )
     69  ENDIF(WIN32 AND HAVE_CPLEX)
    5970ENDIF(HAVE_LP)
    6071
    6172IF(HAVE_MIP)
    6273  ADD_EXECUTABLE(mip_test mip_test.cc)
     74  SET(MIP_TEST_LIBS lemon)
    6375  IF(HAVE_GLPK)
    64     TARGET_LINK_LIBRARIES(mip_test lemon ${GLPK_LIBRARIES})
     76    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${GLPK_LIBRARIES})
    6577  ENDIF(HAVE_GLPK)
     78  IF(HAVE_CPLEX)
     79    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${CPLEX_LIBRARIES})
     80  ENDIF(HAVE_CPLEX)
     81  IF(HAVE_CBC)
     82    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${COIN_CBC_LIBRARIES})
     83  ENDIF(HAVE_CBC)
     84  TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})
    6685  ADD_TEST(mip_test mip_test)
    6786
    … …  
    7594    )
    7695  ENDIF(WIN32 AND HAVE_GLPK)
     96  IF(WIN32 AND HAVE_CPLEX)
     97    GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
     98    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
     99    ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
     100      COMMAND cmake -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
     101    )
     102  ENDIF(WIN32 AND HAVE_CPLEX)
    77103ENDIF(HAVE_MIP)
    78104

  • test/suurballe_test.cc

    r463 r670  
    2323#include <lemon/path.h>
    2424#include <lemon/suurballe.h>
     25#include <lemon/concepts/digraph.h>
    2526
    2627#include "test_tools.h"
    … …  
    3031char test_lgf[] =
    3132  "@nodes\n"
    32   "label supply1 supply2 supply3\n"
    33   "1     0        20      27\n"
    34   "2     0       -4        0\n"
    35   "3     0        0        0\n"
    36   "4     0        0        0\n"
    37   "5     0        9        0\n"
    38   "6     0       -6        0\n"
    39   "7     0        0        0\n"
    40   "8     0        0        0\n"
    41   "9     0        3        0\n"
    42   "10    0       -2        0\n"
    43   "11    0        0        0\n"
    44   "12    0       -20     -27\n"
     33  "label\n"
     34  "1\n"
     35  "2\n"
     36  "3\n"
     37  "4\n"
     38  "5\n"
     39  "6\n"
     40  "7\n"
     41  "8\n"
     42  "9\n"
     43  "10\n"
     44  "11\n"
     45  "12\n"
    4546  "@arcs\n"
    46   "      cost capacity lower1 lower2\n"
    47   " 1  2  70  11       0      8\n"
    48   " 1  3 150   3       0      1\n"
    49   " 1  4  80  15       0      2\n"
    50   " 2  8  80  12       0      0\n"
    51   " 3  5 140   5       0      3\n"
    52   " 4  6  60  10       0      1\n"
    53   " 4  7  80   2       0      0\n"
    54   " 4  8 110   3       0      0\n"
    55   " 5  7  60  14       0      0\n"
    56   " 5 11 120  12       0      0\n"
    57   " 6  3   0   3       0      0\n"
    58   " 6  9 140   4       0      0\n"
    59   " 6 10  90   8       0      0\n"
    60   " 7  1  30   5       0      0\n"
    61   " 8 12  60  16       0      4\n"
    62   " 9 12  50   6       0      0\n"
    63   "10 12  70  13       0      5\n"
    64   "10  2 100   7       0      0\n"
    65   "10  7  60  10       0      0\n"
    66   "11 10  20  14       0      6\n"
    67   "12 11  30  10       0      0\n"
     47  "      length\n"
     48  " 1  2  70\n"
     49  " 1  3 150\n"
     50  " 1  4  80\n"
     51  " 2  8  80\n"
     52  " 3  5 140\n"
     53  " 4  6  60\n"
     54  " 4  7  80\n"
     55  " 4  8 110\n"
     56  " 5  7  60\n"
     57  " 5 11 120\n"
     58  " 6  3   0\n"
     59  " 6  9 140\n"
     60  " 6 10  90\n"
     61  " 7  1  30\n"
     62  " 8 12  60\n"
     63  " 9 12  50\n"
     64  "10 12  70\n"
     65  "10  2 100\n"
     66  "10  7  60\n"
     67  "11 10  20\n"
     68  "12 11  30\n"
    6869  "@attributes\n"
    6970  "source  1\n"
    7071  "target 12\n"
    7172  "@end\n";
     73
     74// Check the interface of Suurballe
     75void checkSuurballeCompile()
     76{
     77  typedef int VType;
     78  typedef concepts::Digraph Digraph;
     79
     80  typedef Digraph::Node Node;
     81  typedef Digraph::Arc Arc;
     82  typedef concepts::ReadMap<Arc, VType> LengthMap;
     83 
     84  typedef Suurballe<Digraph, LengthMap> SuurballeType;
     85
     86  Digraph g;
     87  Node n;
     88  Arc e;
     89  LengthMap len;
     90  SuurballeType::FlowMap flow(g);
     91  SuurballeType::PotentialMap pi(g);
     92
     93  SuurballeType suurb_test(g, len);
     94  const SuurballeType& const_suurb_test = suurb_test;
     95
     96  suurb_test
     97    .flowMap(flow)
     98    .potentialMap(pi);
     99
     100  int k;
     101  k = suurb_test.run(n, n);
     102  k = suurb_test.run(n, n, k);
     103  suurb_test.init(n);
     104  k = suurb_test.findFlow(n);
     105  k = suurb_test.findFlow(n, k);
     106  suurb_test.findPaths();
     107 
     108  int f;
     109  VType c;
     110  c = const_suurb_test.totalLength();
     111  f = const_suurb_test.flow(e);
     112  const SuurballeType::FlowMap& fm =
     113    const_suurb_test.flowMap();
     114  c = const_suurb_test.potential(n);
     115  const SuurballeType::PotentialMap& pm =
     116    const_suurb_test.potentialMap();
     117  k = const_suurb_test.pathNum();
     118  Path<Digraph> p = const_suurb_test.path(k);
     119 
     120  ignore_unused_variable_warning(fm);
     121  ignore_unused_variable_warning(pm);
     122}
    72123
    73124// Check the feasibility of the flow
    … …  
    119170                typename Digraph::Node s, typename Digraph::Node t)
    120171{
    121   // Check the "Complementary Slackness" optimality condition
    122172  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    123173  Node n = s;
    … …  
    137187  ListDigraph digraph;
    138188  ListDigraph::ArcMap<int> length(digraph);
    139   Node source, target;
     189  Node s, t;
    140190
    141191  std::istringstream input(test_lgf);
    142192  DigraphReader<ListDigraph>(digraph, input).
    143     arcMap("cost", length).
    144     node("source", source).
    145     node("target", target).
     193    arcMap("length", length).
     194    node("source", s).
     195    node("target", t).
    146196    run();
    147197
    148198  // Find 2 paths
    149199  {
    150     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
    151     check(suurballe.run(2) == 2, "Wrong number of paths");
    152     check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
     200    Suurballe<ListDigraph> suurballe(digraph, length);
     201    check(suurballe.run(s, t) == 2, "Wrong number of paths");
     202    check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
    153203          "The flow is not feasible");
    154204    check(suurballe.totalLength() == 510, "The flow is not optimal");
    … …  
    157207          "Wrong potentials");
    158208    for (int i = 0; i < suurballe.pathNum(); ++i)
    159       check(checkPath(digraph, suurballe.path(i), source, target),
    160             "Wrong path");
     209      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    161210  }
    162211
    163212  // Find 3 paths
    164213  {
    165     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
    166     check(suurballe.run(3) == 3, "Wrong number of paths");
    167     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
     214    Suurballe<ListDigraph> suurballe(digraph, length);
     215    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
     216    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
    168217          "The flow is not feasible");
    169218    check(suurballe.totalLength() == 1040, "The flow is not optimal");
    … …  
    172221          "Wrong potentials");
    173222    for (int i = 0; i < suurballe.pathNum(); ++i)
    174       check(checkPath(digraph, suurballe.path(i), source, target),
    175             "Wrong path");
     223      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    176224  }
    177225
    178226  // Find 5 paths (only 3 can be found)
    179227  {
    180     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
    181     check(suurballe.run(5) == 3, "Wrong number of paths");
    182     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
     228    Suurballe<ListDigraph> suurballe(digraph, length);
     229    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
     230    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
    183231          "The flow is not feasible");
    184232    check(suurballe.totalLength() == 1040, "The flow is not optimal");
    … …  
    187235          "Wrong potentials");
    188236    for (int i = 0; i < suurballe.pathNum(); ++i)
    189       check(checkPath(digraph, suurballe.path(i), source, target),
    190             "Wrong path");
     237      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    191238  }
    192239

  • tools/lgf-gen.cc

    r663 r670  
    481481      g.erase(*ei);
    482482      ConstMap<Arc,int> cegy(1);
    483       Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy,a,b);
    484       int k=sur.run(2);
     483      Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);
     484      int k=sur.run(a,b,2);
    485485      if(k<2 || sur.totalLength()>d)
    486486        g.addEdge(a,b);
    … …  
    512512      if(e==INVALID) {
    513513        ConstMap<Arc,int> cegy(1);
    514         Suurballe<ListGraph,ConstMap<Arc,int> >
    515           sur(g,cegy,pi->a,pi->b);
    516         int k=sur.run(2);
     514        Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);
     515        int k=sur.run(pi->a,pi->b,2);
    517516        if(k<2 || sur.totalLength()>d)
    518517          {
Note: See TracChangeset for help on using the changeset viewer.