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

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

IF(GLPK_FOUND)

  SET(HAVE_LP TRUE)

  SET(HAVE_MIP TRUE)

  SET(HAVE_GLPK TRUE)

ENDIF(GLPK_FOUND)

INCLUDE(CheckTypeSize)

CHECK_TYPE_SIZE("long long" LONG_LONG)

ENABLE_TESTING()

ADD_SUBDIRECTORY(lemon)

copyright/license.

Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi

Kutatocsoport (Egervary Combinatorial Optimization Research Group,

EGRES).

Permission is hereby granted, free of charge, to any person or organization

obtaining a copy of the software and accompanying documentation covered by

this license (the "Software") to use, reproduce, display, distribute,

execute, and transmit the Software, and to prepare derivative works of the

Software, and to permit third-parties to whom the Software is furnished to

do so, all subject to the following:

The copyright notices in the Software and this entire statement, including

the above license grant, this restriction and the following disclaimer,

must be included in all copies of the Software, in whole or in part, and

all derivative works of the Software, unless such copies or derivative

works are solely in the form of machine-executable object code generated by

a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT

SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE

FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,

ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER

DEALINGS IN THE SOFTWARE.

2008-10-13 Version 1.0 released

	This is the first stable release of LEMON. Compared to the 0.x

	release series, it features a considerably smaller but more

	matured set of tools. The API has also completely revised and

	changed in several places.

	* The major name changes compared to the 0.x series (see the

          Migration Guide in the doc for more details)

          * Graph -> Digraph, UGraph -> Graph

          * Edge -> Arc, UEdge -> Edge

	  * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)

INCLUDE_DIRECTORIES(

)

SET(DEMOS

  arg_parser_demo

  graph_to_eps_demo

  lgf_demo)

FOREACH(DEMO_NAME ${DEMOS})

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

  TARGET_LINK_LIBRARIES(${DEMO_NAME} lemon)

ENDFOREACH(DEMO_NAME)

SET(PACKAGE_NAME ${PROJECT_NAME})

SET(PACKAGE_VERSION ${PROJECT_VERSION})

CONFIGURE_FILE(

  @ONLY)

IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)

  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)

  IF(UNIX)

    ADD_CUSTOM_TARGET(html

      COMMAND rm -rf gen-images

      COMMAND mkdir gen-images

      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps

      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps

      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps

      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps

INCLUDE_DIRECTORIES(

)

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

lemon_libemon_la_SOURCES = \

	lemon/arg_parser.cc \

	lemon/base.cc \

	lemon/color.cc \

	lemon/lp_base.cc \

	lemon/lp_skeleton.cc \

        lemon/random.cc \

	lemon/bits/windows.cc

lemon_libemon_la_CXXFLAGS = \

	$(GLPK_CFLAGS) \

	$(CPLEX_CFLAGS) \

	$(SOPLEX_CXXFLAGS) \

	$(CLP_CXXFLAGS)

lemon_libemon_la_LDFLAGS = \

	$(GLPK_LIBS) \

	$(CPLEX_LIBS) \

	$(SOPLEX_LIBS) \

	$(CLP_LIBS)

if HAVE_GLPK

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

  void CplexBase::_clear() {

    CPXfreeprob(cplexEnv(),&_prob);

    int status;

    _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");

    rows.clear();

    cols.clear();

  }

  // CplexLp members

  CplexLp::CplexLp()

  CplexLp::CplexLp(const CplexEnv& env)

  CplexLp::CplexLp(const CplexLp& other)

  CplexLp::~CplexLp() {}

  CplexLp* CplexLp::newSolver() const { return new CplexLp; }

  CplexLp* CplexLp::cloneSolver() const {return new CplexLp(*this); }

  const char* CplexLp::_solverName() const { return "CplexLp"; }

  void CplexLp::_clear_temporals() {

    _col_status.clear();

    _row_status.clear();

    _primal_ray.clear();

    case CPX_UNBOUNDED:

      return INFEASIBLE;

    default:

      return UNDEFINED; //Everything else comes here

      //FIXME error

    }

#endif

  }

  // CplexMip members

  CplexMip::CplexMip()

#if CPX_VERSION < 800

    CPXchgprobtype(cplexEnv(),  _prob, CPXPROB_MIP);

#else

    CPXchgprobtype(cplexEnv(),  _prob, CPXPROB_MILP);

#endif

  }

  CplexMip::CplexMip(const CplexEnv& env)

#if CPX_VERSION < 800

    CPXchgprobtype(cplexEnv(),  _prob, CPXPROB_MIP);

#else

    CPXchgprobtype(cplexEnv(),  _prob, CPXPROB_MILP);

#endif

  }

  CplexMip::CplexMip(const CplexMip& other)

  CplexMip::~CplexMip() {}

  CplexMip* CplexMip::newSolver() const { return new CplexMip; }

  CplexMip* CplexMip::cloneSolver() const {return new CplexMip(*this); }

  const char* CplexMip::_solverName() const { return "CplexMip"; }

  void CplexMip::_setColType(int i, CplexMip::ColTypes col_type) {

    // Note If a variable is to be changed to binary, a call to CPXchgbds

    // should also be made to change the bounds to 0 and 1.

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

    /// Destructor

    virtual ~CplexEnv();

  protected:

    cpxenv* cplexEnv() { return _env; }

    const cpxenv* cplexEnv() const { return _env; }

  };

  /// \brief Base interface for the CPLEX LP and MIP solver

  ///

  /// This class implements the common interface of the CPLEX LP and

  /// \ingroup lp_group

  class CplexBase : virtual public LpBase {

  protected:

    CplexEnv _env;

    cpxlp* _prob;

    CplexBase();

    CplexBase(const CplexEnv&);

    CplexBase(const CplexBase &);

    virtual ~CplexBase();

  ///\ingroup lp_group

  class CplexMip : public MipSolver, public CplexBase {

  public:

    /// \e

    CplexMip();

    /// \e

    CplexMip(const CplexEnv&);

    /// \e

    CplexMip(const CplexMip&);

    /// \e

    virtual ~CplexMip();

  protected:

    virtual const char* _solverName() const;

    virtual ColTypes _getColType(int col) const;

    virtual void _setColType(int col, ColTypes col_type);

    virtual SolveExitStatus _solve();

    virtual ProblemType _getType() const;

    virtual Value _getSol(int i) const;

    virtual Value _getSolValue() const;

  };

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

    cols.clear();

  }

  void GlpkBase::freeEnv() {

    glp_free_env();

  }

  GlpkBase::FreeEnvHelper GlpkBase::freeEnvHelper;

  // GlpkLp members

  GlpkLp::GlpkLp()

    messageLevel(MESSAGE_NO_OUTPUT);

  }

  GlpkLp::GlpkLp(const GlpkLp& other)

    messageLevel(MESSAGE_NO_OUTPUT);

  }

  GlpkLp* GlpkLp::newSolver() const { return new GlpkLp; }

  GlpkLp* GlpkLp::cloneSolver() const { return new GlpkLp(*this); }

  const char* GlpkLp::_solverName() const { return "GlpkLp"; }

  void GlpkLp::_clear_temporals() {

    _primal_ray.clear();

    _dual_ray.clear();

  }

  void GlpkLp::presolver(bool b) {

    lpx_set_int_parm(lp, LPX_K_PRESOL, b ? 1 : 0);

  }

  void GlpkLp::messageLevel(MessageLevel m) {

    _message_level = m;

  }

  // GlpkMip members

  GlpkMip::GlpkMip()

    messageLevel(MESSAGE_NO_OUTPUT);

  }

  GlpkMip::GlpkMip(const GlpkMip& other)

    messageLevel(MESSAGE_NO_OUTPUT);

  }

  void GlpkMip::_setColType(int i, GlpkMip::ColTypes col_type) {

    switch (col_type) {

    case INTEGER:

      glp_set_col_kind(lp, i, GLP_IV);

      break;

    case REAL:

      glp_set_col_kind(lp, i, GLP_CV);

      break;

    }

    then

	((++CHANGED_FILES))

    fi

    if [ $WARNED == YES ]

    then

	((++WARNED_FILES))

    fi

}

function check_action() {

    if [ "$3" == 'tabs' ]

    then

    elif [ "$3" == 'trailing spaces' ]

    then

        PATTERN='\ +$'

    else

        PATTERN='*'

    fi

    if ! diff -q $1 $2 >/dev/null

    then

        if [ "$PATTERN" == '*' ]

        then

            diff $1 $2 | grep '^[0-9]' | sed "s|^\(.*\)c.*$|$2:\1: check failed: $3|g" |

INCLUDE_DIRECTORIES(

)

IF(HAVE_GLPK)

  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})

ENDIF(HAVE_GLPK)

SET(TESTS

  adaptors_test

  bfs_test

  circulation_test

  counter_test

  dfs_test

  digraph_test

  dijkstra_test

  dim_test

  edge_set_test

  error_test

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

 *

 */

#include <lemon/counter.h>

#include <vector>

using namespace lemon;

template <typename T>

void bubbleSort(std::vector<T>& v) {

      }

    }

  }

}

template <typename T>

void insertionSort(std::vector<T>& v) {

    }

  }

}

template <typename MyCounter>

}

void init(std::vector<int>& v) {

  v[0] = 10; v[1] = 60; v[2] = 20; v[3] = 90; v[4] = 100;

  v[5] = 80; v[6] = 40; v[7] = 30; v[8] = 50; v[9] = 70;

}

int main()

{

  std::vector<int> x(10);

  init(x); bubbleSort(x);

  init(x); insertionSort(x);

  return 0;

}

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

  solveAndCheck(lp, LpSolver::UNBOUNDED, expected_opt);

  //Infeasibilty

  lp.addRow(x1+x2 <=-2);

  solveAndCheck(lp, LpSolver::INFEASIBLE, expected_opt);

}

template<class LP>

void cloneTest()

{

  //Test for clone/new

  LP* lp = new LP();

  LP* lpnew = lp->newSolver();

  LP* lpclone = lp->cloneSolver();

  delete lp;

  delete lpnew;

  delete lpclone;

}

int main()

{

  LpSkeleton lp_skel;

  lpTest(lp_skel);

    GlpkLp lp_glpk1,lp_glpk2;

    lpTest(lp_glpk1);

    aTest(lp_glpk2);

    cloneTest<GlpkLp>();

  }

#endif

#ifdef HAVE_CPLEX

  try {

    CplexLp lp_cplex1,lp_cplex2;

    lpTest(lp_cplex1);

    aTest(lp_cplex2);

  } catch (CplexEnv::LicenseError& error) {

#ifdef LEMON_FORCE_CPLEX_CHECK

    check(false, error.what());

#else

    std::cerr << error.what() << std::endl;

    std::cerr << "Cplex license check failed, lp check skipped" << std::endl;

#endif

  }

#endif

#ifdef HAVE_SOPLEX

  {

    SoplexLp lp_soplex1,lp_soplex2;

    lpTest(lp_soplex1);

    aTest(lp_soplex2);

    cloneTest<SoplexLp>();

  }

#endif

#ifdef HAVE_CLP

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

  //Restrict both to integer

  mip.colType(x1,MipSolver::INTEGER);

  expected_opt=0;

  solveAndCheck(mip, MipSolver::OPTIMAL, expected_opt);

}

template<class MIP>

void cloneTest()

{

  MIP* mip = new MIP();

  MIP* mipnew = mip->newSolver();

  MIP* mipclone = mip->cloneSolver();

  delete mip;

  delete mipnew;

  delete mipclone;

}

int main()

{

#ifdef HAVE_GLPK

  {

    GlpkMip mip1;

    aTest(mip1);

    cloneTest<GlpkMip>();

  }

#endif

#ifdef HAVE_CPLEX

  try {

    CplexMip mip2;

    aTest(mip2);

  } catch (CplexEnv::LicenseError& error) {

#ifdef LEMON_FORCE_CPLEX_CHECK

    check(false, error.what());

#else

    std::cerr << error.what() << std::endl;

    std::cerr << "Cplex license check failed, lp check skipped" << std::endl;

#endif

  }

#endif

  return 0;

}

void g()

{

  static Timer T;

  for(int i=0;i<1000;i++)

    TimeStamp x(T);

}

int main()

{

  Timer T;

  unsigned int n;

  std::cout << T << " (" << n << " time queries)\n";

  TimeStamp full;

  TimeStamp t;

  std::cout << t << " (" << n << " tests)\n";

  std::cout << "Total: " << full << "\n";

  std::cout << t << " (" << n << " tests)\n";

  std::cout << "Total: " << full << "\n";

  return 0;

}

INCLUDE_DIRECTORIES(

)

ADD_EXECUTABLE(lgf-gen lgf-gen.cc)

TARGET_LINK_LIBRARIES(lgf-gen lemon)

ADD_EXECUTABLE(dimacs-to-lgf dimacs-to-lgf.cc)

TARGET_LINK_LIBRARIES(dimacs-to-lgf lemon)

ADD_EXECUTABLE(dimacs-solver dimacs-solver.cc)

TARGET_LINK_LIBRARIES(dimacs-solver lemon)

INSTALL(

  TARGETS lgf-gen dimacs-to-lgf dimacs-solver

  RUNTIME DESTINATION bin

  COMPONENT bin

)

IF(NOT WIN32)

  INSTALL(

    COMPONENT bin)

ENDIF(NOT WIN32)

    echo Update $i...

    TMP=`mktemp`

    sed -e "s/\<undirected graph\>/_gr_aph_label_/g"\

        -e "s/\<undirected graphs\>/_gr_aph_label_s/g"\

        -e "s/\<undirected edge\>/_ed_ge_label_/g"\

        -e "s/\<undirected edges\>/_ed_ge_label_s/g"\

        -e "s/\<directed graph\>/_digr_aph_label_/g"\

        -e "s/\<directed graphs\>/_digr_aph_label_s/g"\

        -e "s/\<directed edge\>/_ar_c_label_/g"\

        -e "s/\<directed edges\>/_ar_c_label_s/g"\

        -e "s/UGraph/_Gr_aph_label_/g"\

        -e "s/u[Gg]raph/_gr_aph_label_/g"\

        -e "s/\<graph\>/_digr_aph_label_/g"\

        -e "s/\<graphs\>/_digr_aph_label_s/g"\

        -e "s/\([a-z_]\)graph/\1_gr_aph_label_/g"\

        -e "s/Graph/_Digr_aph_label_/g"\