COIN-OR::LEMON - Graph Library

Changes in / [886:ece1f8a3052d:939:71fd280363d5] in lemon-1.2


Ignore:
Files:
6 added
1 deleted
31 edited

Legend:

Unmodified
Added
Removed
  • AUTHORS

    r320 r924  
    2424
    2525Again, please visit the history of the old LEMON repository for more
    26 details: http://lemon.cs.elte.hu/svn/lemon/trunk
     26details: http://lemon.cs.elte.hu/hg/lemon-0.x
  • CMakeLists.txt

    r680 r913  
    33SET(PROJECT_NAME "LEMON")
    44PROJECT(${PROJECT_NAME})
     5
     6INCLUDE(FindPythonInterp)
     7INCLUDE(FindWget)
    58
    69IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
     
    1013ELSE()
    1114  EXECUTE_PROCESS(
     15    COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
     16    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     17    OUTPUT_VARIABLE HG_REVISION_PATH
     18    ERROR_QUIET
     19    OUTPUT_STRIP_TRAILING_WHITESPACE
     20  )
     21  EXECUTE_PROCESS(
    1222    COMMAND hg id -i
    1323    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     
    1727  )
    1828  IF(HG_REVISION STREQUAL "")
    19     SET(HG_REVISION "hg-tip")
     29    SET(HG_REVISION_ID "hg-tip")
     30  ELSE()
     31    IF(HG_REVISION_PATH STREQUAL "")
     32      SET(HG_REVISION_ID ${HG_REVISION})
     33    ELSE()
     34      SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
     35    ENDIF()
    2036  ENDIF()
    21   SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
     37  SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
    2238ENDIF()
    2339
     
    3248FIND_PACKAGE(COIN)
    3349
     50IF(DEFINED ENV{LEMON_CXX_WARNING})
     51  SET(CXX_WARNING $ENV{LEMON_CXX_WARNING})
     52ELSE()
     53  IF(CMAKE_COMPILER_IS_GNUCXX)
     54    SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
     55    SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
     56    SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
     57  ELSEIF(MSVC)
     58    # This part is unnecessary 'casue the same is set by the lemon/core.h.
     59    # Still keep it as an example.
     60    SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")
     61    # Suppressed warnings:
     62    # C4250: 'class1' : inherits 'class2::member' via dominance
     63    # C4355: 'this' : used in base member initializer list
     64    # C4503: 'function' : decorated name length exceeded, name was truncated
     65    # C4800: 'type' : forcing value to bool 'true' or 'false'
     66    #        (performance warning)
     67    # C4996: 'function': was declared deprecated
     68  ELSE()
     69    SET(CXX_WARNING "-Wall -W")
     70  ENDIF()
     71ENDIF()
     72SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.")
     73
     74SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
     75
     76SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb" CACHE STRING
     77    "Flags used by the C++ compiler during maintainer builds."
     78    FORCE )
     79SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING
     80    "Flags used by the C compiler during maintainer builds."
     81    FORCE )
     82SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     83    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
     84    "Flags used for linking binaries during maintainer builds."
     85    FORCE )
     86SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     87    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
     88    "Flags used by the shared libraries linker during maintainer builds."
     89    FORCE )
     90MARK_AS_ADVANCED(
     91    CMAKE_CXX_FLAGS_MAINTAINER
     92    CMAKE_C_FLAGS_MAINTAINER
     93    CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     94    CMAKE_SHARED_LINKER_FLAGS_MAINTAINER )
     95
     96IF(CMAKE_CONFIGURATION_TYPES)
     97  LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer)
     98  LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES)
     99  SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING
     100      "Add the configurations that we need"
     101      FORCE)
     102 endif()
     103
     104IF(NOT CMAKE_BUILD_TYPE)
     105  SET(CMAKE_BUILD_TYPE "Release")
     106ENDIF()
     107
     108SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING
     109    "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer."
     110    FORCE )
     111
     112
    34113INCLUDE(CheckTypeSize)
    35114CHECK_TYPE_SIZE("long long" LONG_LONG)
     
    37116
    38117ENABLE_TESTING()
     118
     119IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     120  ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
     121ELSE()
     122  ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})
     123ENDIF()
    39124
    40125ADD_SUBDIRECTORY(lemon)
     
    63148ENDIF()
    64149
    65 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
     150IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    66151  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    67152  SET(CPACK_PACKAGE_VENDOR "EGRES")
  • cmake/FindCOIN.cmake

    r634 r920  
    66FIND_LIBRARY(COIN_CBC_LIBRARY
    77  NAMES Cbc libCbc
     8  HINTS ${COIN_ROOT_DIR}/lib/coin
    89  HINTS ${COIN_ROOT_DIR}/lib
    910)
    1011FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY
    1112  NAMES CbcSolver libCbcSolver
     13  HINTS ${COIN_ROOT_DIR}/lib/coin
    1214  HINTS ${COIN_ROOT_DIR}/lib
    1315)
    1416FIND_LIBRARY(COIN_CGL_LIBRARY
    1517  NAMES Cgl libCgl
     18  HINTS ${COIN_ROOT_DIR}/lib/coin
    1619  HINTS ${COIN_ROOT_DIR}/lib
    1720)
    1821FIND_LIBRARY(COIN_CLP_LIBRARY
    1922  NAMES Clp libClp
     23  HINTS ${COIN_ROOT_DIR}/lib/coin
    2024  HINTS ${COIN_ROOT_DIR}/lib
    2125)
    2226FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY
    2327  NAMES CoinUtils libCoinUtils
     28  HINTS ${COIN_ROOT_DIR}/lib/coin
    2429  HINTS ${COIN_ROOT_DIR}/lib
    2530)
    2631FIND_LIBRARY(COIN_OSI_LIBRARY
    2732  NAMES Osi libOsi
     33  HINTS ${COIN_ROOT_DIR}/lib/coin
    2834  HINTS ${COIN_ROOT_DIR}/lib
    2935)
    3036FIND_LIBRARY(COIN_OSI_CBC_LIBRARY
    3137  NAMES OsiCbc libOsiCbc
     38  HINTS ${COIN_ROOT_DIR}/lib/coin
    3239  HINTS ${COIN_ROOT_DIR}/lib
    3340)
    3441FIND_LIBRARY(COIN_OSI_CLP_LIBRARY
    3542  NAMES OsiClp libOsiClp
     43  HINTS ${COIN_ROOT_DIR}/lib/coin
    3644  HINTS ${COIN_ROOT_DIR}/lib
    3745)
    3846FIND_LIBRARY(COIN_OSI_VOL_LIBRARY
    3947  NAMES OsiVol libOsiVol
     48  HINTS ${COIN_ROOT_DIR}/lib/coin
    4049  HINTS ${COIN_ROOT_DIR}/lib
    4150)
    4251FIND_LIBRARY(COIN_VOL_LIBRARY
    4352  NAMES Vol libVol
     53  HINTS ${COIN_ROOT_DIR}/lib/coin
    4454  HINTS ${COIN_ROOT_DIR}/lib
    4555)
     
    5666  COIN_OSI_CBC_LIBRARY
    5767  COIN_OSI_CLP_LIBRARY
    58   COIN_OSI_VOL_LIBRARY
    59   COIN_VOL_LIBRARY
     68  # COIN_OSI_VOL_LIBRARY
     69  # COIN_VOL_LIBRARY
    6070)
    6171
    6272IF(COIN_FOUND)
    6373  SET(COIN_INCLUDE_DIRS ${COIN_INCLUDE_DIR})
    64   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}")
     74  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}")
    6575  SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY}")
    6676  SET(COIN_CBC_LIBRARIES ${COIN_LIBRARIES})
  • configure.ac

    r680 r907  
    9999dnl Add dependencies on files generated by configure.
    100100AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
    101   ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
     101  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/doc/mainpage.dox.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
    102102
    103103AC_CONFIG_FILES([
     
    106106cmake/version.cmake
    107107doc/Doxyfile
     108doc/mainpage.dox
    108109lemon/lemon.pc
    109110])
  • doc/CMakeLists.txt

    r679 r907  
    44SET(abs_top_builddir ${PROJECT_BINARY_DIR})
    55
     6SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
     7
    68CONFIGURE_FILE(
    79  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
    810  ${PROJECT_BINARY_DIR}/doc/Doxyfile
     11  @ONLY
     12)
     13
     14CONFIGURE_FILE(
     15  ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in
     16  ${PROJECT_BINARY_DIR}/doc/mainpage.dox
    917  @ONLY
    1018)
     
    5058
    5159ENDIF()
     60
     61IF(WGET_FOUND)
     62ADD_CUSTOM_TARGET(update-external-tags
     63  COMMAND ${CMAKE_COMMAND} -E make_directory dl
     64  # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl
     65  COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
     66  COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag
     67  COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag
     68  COMMAND ${CMAKE_COMMAND} -E remove_directory dl
     69  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     70  )
     71ENDIF()
  • doc/Doxyfile.in

    r367 r907  
    1 # Doxyfile 1.5.7.1
     1# Doxyfile 1.7.3
    22
    33#---------------------------------------------------------------------------
     
    55#---------------------------------------------------------------------------
    66DOXYFILE_ENCODING      = UTF-8
    7 PROJECT_NAME           = @PACKAGE_NAME@
    8 PROJECT_NUMBER         = @PACKAGE_VERSION@
     7PROJECT_NAME           =
     8PROJECT_NUMBER         =
     9PROJECT_BRIEF          =
     10PROJECT_LOGO           =
    911OUTPUT_DIRECTORY       =
    1012CREATE_SUBDIRS         = NO
     
    2224QT_AUTOBRIEF           = NO
    2325MULTILINE_CPP_IS_BRIEF = NO
    24 DETAILS_AT_TOP         = YES
    2526INHERIT_DOCS           = NO
    2627SEPARATE_MEMBER_PAGES  = NO
     
    3132OPTIMIZE_FOR_FORTRAN   = NO
    3233OPTIMIZE_OUTPUT_VHDL   = NO
     34EXTENSION_MAPPING      =
    3335BUILTIN_STL_SUPPORT    = YES
    3436CPP_CLI_SUPPORT        = NO
     
    5658HIDE_SCOPE_NAMES       = YES
    5759SHOW_INCLUDE_FILES     = YES
     60FORCE_LOCAL_INCLUDES   = NO
    5861INLINE_INFO            = YES
    5962SORT_MEMBER_DOCS       = NO
    6063SORT_BRIEF_DOCS        = NO
     64SORT_MEMBERS_CTORS_1ST = NO
    6165SORT_GROUP_NAMES       = NO
    6266SORT_BY_SCOPE_NAME     = NO
     67STRICT_PROTO_MATCHING  = NO
    6368GENERATE_TODOLIST      = YES
    6469GENERATE_TESTLIST      = YES
     
    7277SHOW_NAMESPACES        = YES
    7378FILE_VERSION_FILTER    =
    74 LAYOUT_FILE            = DoxygenLayout.xml
     79LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
    7580#---------------------------------------------------------------------------
    7681# configuration options related to warning and progress messages
     
    9297                         "@abs_top_srcdir@/demo" \
    9398                         "@abs_top_srcdir@/tools" \
    94                          "@abs_top_srcdir@/test/test_tools.h"
     99                         "@abs_top_srcdir@/test/test_tools.h" \
     100                         "@abs_top_builddir@/doc/mainpage.dox"
    95101INPUT_ENCODING         = UTF-8
    96102FILE_PATTERNS          = *.h \
     
    112118FILTER_PATTERNS        =
    113119FILTER_SOURCE_FILES    = NO
     120FILTER_SOURCE_PATTERNS =
    114121#---------------------------------------------------------------------------
    115122# configuration options related to source browsing
    116123#---------------------------------------------------------------------------
    117 SOURCE_BROWSER         = NO
     124SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
    118125INLINE_SOURCES         = NO
    119126STRIP_CODE_COMMENTS    = YES
     
    138145HTML_FOOTER            =
    139146HTML_STYLESHEET        =
     147HTML_COLORSTYLE_HUE    = 220
     148HTML_COLORSTYLE_SAT    = 100
     149HTML_COLORSTYLE_GAMMA  = 80
     150HTML_TIMESTAMP         = YES
    140151HTML_ALIGN_MEMBERS     = YES
    141 HTML_DYNAMIC_SECTIONS  = NO
     152HTML_DYNAMIC_SECTIONS  = YES
    142153GENERATE_DOCSET        = NO
    143154DOCSET_FEEDNAME        = "Doxygen generated docs"
    144155DOCSET_BUNDLE_ID       = org.doxygen.Project
     156DOCSET_PUBLISHER_ID    = org.doxygen.Publisher
     157DOCSET_PUBLISHER_NAME  = Publisher
    145158GENERATE_HTMLHELP      = NO
    146159CHM_FILE               =
     
    154167QHP_NAMESPACE          = org.doxygen.Project
    155168QHP_VIRTUAL_FOLDER     = doc
     169QHP_CUST_FILTER_NAME   =
     170QHP_CUST_FILTER_ATTRS  =
     171QHP_SECT_FILTER_ATTRS  =
    156172QHG_LOCATION           =
     173GENERATE_ECLIPSEHELP   = NO
     174ECLIPSE_DOC_ID         = org.doxygen.Project
    157175DISABLE_INDEX          = NO
    158176ENUM_VALUES_PER_LINE   = 4
    159177GENERATE_TREEVIEW      = NO
     178USE_INLINE_TREES       = NO
    160179TREEVIEW_WIDTH         = 250
     180EXT_LINKS_IN_WINDOW    = NO
    161181FORMULA_FONTSIZE       = 10
     182FORMULA_TRANSPARENT    = YES
     183USE_MATHJAX            = NO
     184MATHJAX_RELPATH        = http://www.mathjax.org/mathjax
     185SEARCHENGINE           = YES
     186SERVER_BASED_SEARCH    = NO
    162187#---------------------------------------------------------------------------
    163188# configuration options related to the LaTeX output
     
    176201LATEX_BATCHMODE        = NO
    177202LATEX_HIDE_INDICES     = NO
     203LATEX_SOURCE_CODE      = NO
    178204#---------------------------------------------------------------------------
    179205# configuration options related to the RTF output
     
    224250SKIP_FUNCTION_MACROS   = YES
    225251#---------------------------------------------------------------------------
    226 # Configuration::additions related to external references   
    227 #---------------------------------------------------------------------------
    228 TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
     252# Configuration::additions related to external references
     253#---------------------------------------------------------------------------
     254TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
    229255GENERATE_TAGFILE       = html/lemon.tag
    230256ALLEXTERNALS           = NO
     
    238264HIDE_UNDOC_RELATIONS   = YES
    239265HAVE_DOT               = YES
     266DOT_NUM_THREADS        = 0
    240267DOT_FONTNAME           = FreeSans
    241268DOT_FONTSIZE           = 10
     
    255282DOT_PATH               =
    256283DOTFILE_DIRS           =
     284MSCFILE_DIRS           =
    257285DOT_GRAPH_MAX_NODES    = 50
    258286MAX_DOT_GRAPH_DEPTH    = 0
     
    261289GENERATE_LEGEND        = YES
    262290DOT_CLEANUP            = YES
    263 #---------------------------------------------------------------------------
    264 # Configuration::additions related to the search engine   
    265 #---------------------------------------------------------------------------
    266 SEARCHENGINE           = NO
  • doc/DoxygenLayout.xml

    r316 r906  
    33  <navindex>
    44    <tab type="mainpage" visible="yes" title=""/>
    5     <tab type="modules" visible="yes" title=""/>
     5    <tab type="modules" visible="yes" title="" intro=""/>
    66    <tab type="classes" visible="yes" title="">
    7       <tab type="classes" visible="yes" title=""/>
    8       <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/> 
    9       <tab type="hierarchy" visible="yes" title=""/>
    10       <tab type="classmembers" visible="yes" title=""/>
     7      <tab type="classes" visible="yes" title="" intro=""/>
     8      <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/>
     9      <tab type="hierarchy" visible="yes" title="" intro=""/>
     10      <tab type="classmembers" visible="yes" title="" intro=""/>
    1111    </tab>
    1212    <tab type="namespaces" visible="yes" title="">
    13       <tab type="namespaces" visible="yes" title=""/>
    14       <tab type="namespacemembers" visible="yes" title=""/>
     13      <tab type="namespaces" visible="yes" title="" intro=""/>
     14      <tab type="namespacemembers" visible="yes" title="" intro=""/>
    1515    </tab>
    1616    <tab type="files" visible="yes" title="">
    17       <tab type="files" visible="yes" title=""/>
    18       <tab type="globals" visible="yes" title=""/>
     17      <tab type="files" visible="yes" title="" intro=""/>
     18      <tab type="globals" visible="yes" title="" intro=""/>
    1919    </tab>
    20     <tab type="dirs" visible="yes" title=""/>
    21     <tab type="examples" visible="yes" title=""/> 
    22     <tab type="pages" visible="yes" title=""/>
     20    <tab type="dirs" visible="yes" title="" intro=""/>
     21    <tab type="examples" visible="yes" title="" intro=""/>
     22    <tab type="pages" visible="yes" title="" intro=""/>
    2323  </navindex>
    2424
  • doc/lgf.dox

    r440 r923  
    6464\endcode
    6565
    66 The \c \@arcs section is very similar to the \c \@nodes section,
    67 it again starts with a header line describing the names of the maps,
    68 but the \c "label" map is not obligatory here. The following lines
    69 describe the arcs. The first two tokens of each line are
    70 the source and the target node of the arc, respectively, then come the map
     66The \c \@arcs section is very similar to the \c \@nodes section, it
     67again starts with a header line describing the names of the maps, but
     68the \c "label" map is not obligatory here. The following lines
     69describe the arcs. The first two tokens of each line are the source
     70and the target node of the arc, respectively, then come the map
    7171values. The source and target tokens must be node labels.
    7272
     
    7979\endcode
    8080
     81If there is no map in the \c \@arcs section at all, then it must be
     82indicated by a sole '-' sign in the first line.
     83
     84\code
     85 @arcs
     86         -
     87 1   2
     88 1   3
     89 2   3
     90\endcode
     91
    8192The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
    8293also store the edge set of an undirected graph. In such case there is
    8394a conventional method for store arc maps in the file, if two columns
    84 has the same caption with \c '+' and \c '-' prefix, then these columns
     95have the same caption with \c '+' and \c '-' prefix, then these columns
    8596can be regarded as the values of an arc map.
    8697
  • lemon/CMakeLists.txt

    r679 r904  
    77  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
    88  ${CMAKE_CURRENT_BINARY_DIR}/config.h
     9)
     10
     11CONFIGURE_FILE(
     12  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
     13  ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
     14  @ONLY
    915)
    1016
     
    6773  COMPONENT headers
    6874)
     75
     76INSTALL(
     77  FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
     78  DESTINATION lib/pkgconfig
     79)
     80
  • lemon/Makefile.am

    r667 r937  
    11EXTRA_DIST += \
    22        lemon/lemon.pc.in \
     3        lemon/lemon.pc.cmake \
    34        lemon/CMakeLists.txt \
    45        lemon/config.h.cmake
     
    6061        lemon/bfs.h \
    6162        lemon/bin_heap.h \
     63        lemon/bucket_heap.h \
    6264        lemon/cbc.h \
    6365        lemon/circulation.h \
     
    7779        lemon/error.h \
    7880        lemon/euler.h \
     81        lemon/fib_heap.h \
    7982        lemon/full_graph.h \
    8083        lemon/glpk.h \
     
    100103        lemon/path.h \
    101104        lemon/preflow.h \
     105        lemon/radix_heap.h \
    102106        lemon/radix_sort.h \
    103107        lemon/random.h \
  • lemon/bin_heap.h

    r584 r683  
    3434  ///\brief A Binary Heap implementation.
    3535  ///
    36   ///This class implements the \e binary \e heap data structure. 
    37   /// 
     36  ///This class implements the \e binary \e heap data structure.
     37  ///
    3838  ///A \e heap is a data structure for storing items with specified values
    3939  ///called \e priorities in such a way that finding the item with minimum
    40   ///priority is efficient. \c Comp specifies the ordering of the priorities.
     40  ///priority is efficient. \c CMP specifies the ordering of the priorities.
    4141  ///In a heap one can change the priority of an item, add or erase an
    4242  ///item, etc.
     
    4545  ///\tparam IM A read and writable item map with int values, used internally
    4646  ///to handle the cross references.
    47   ///\tparam Comp A functor class for the ordering of the priorities.
     47  ///\tparam CMP A functor class for the ordering of the priorities.
    4848  ///The default is \c std::less<PR>.
    4949  ///
    5050  ///\sa FibHeap
    5151  ///\sa Dijkstra
    52   template <typename PR, typename IM, typename Comp = std::less<PR> >
     52  template <typename PR, typename IM, typename CMP = std::less<PR> >
    5353  class BinHeap {
    5454
     
    6363    typedef std::pair<Item,Prio> Pair;
    6464    ///\e
    65     typedef Comp Compare;
     65    typedef CMP Compare;
    6666
    6767    /// \brief Type to represent the items states.
  • lemon/bits/map_extender.h

    r617 r802  
    5050    typedef typename Parent::ConstReference ConstReference;
    5151
     52    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
     53
    5254    class MapIt;
    5355    class ConstMapIt;
     
    8385      typedef typename Map::Value Value;
    8486
    85       MapIt() {}
    86 
    87       MapIt(Invalid i) : Parent(i) { }
    88 
    89       explicit MapIt(Map& _map) : map(_map) {
    90         map.notifier()->first(*this);
     87      MapIt() : map(NULL) {}
     88
     89      MapIt(Invalid i) : Parent(i), map(NULL) {}
     90
     91      explicit MapIt(Map& _map) : map(&_map) {
     92        map->notifier()->first(*this);
    9193      }
    9294
    9395      MapIt(const Map& _map, const Item& item)
     96        : Parent(item), map(&_map) {}
     97
     98      MapIt& operator++() {
     99        map->notifier()->next(*this);
     100        return *this;
     101      }
     102
     103      typename MapTraits<Map>::ConstReturnValue operator*() const {
     104        return (*map)[*this];
     105      }
     106
     107      typename MapTraits<Map>::ReturnValue operator*() {
     108        return (*map)[*this];
     109      }
     110
     111      void set(const Value& value) {
     112        map->set(*this, value);
     113      }
     114
     115    protected:
     116      Map* map;
     117
     118    };
     119
     120    class ConstMapIt : public Item {
     121      typedef Item Parent;
     122
     123    public:
     124
     125      typedef typename Map::Value Value;
     126
     127      ConstMapIt() : map(NULL) {}
     128
     129      ConstMapIt(Invalid i) : Parent(i), map(NULL) {}
     130
     131      explicit ConstMapIt(Map& _map) : map(&_map) {
     132        map->notifier()->first(*this);
     133      }
     134
     135      ConstMapIt(const Map& _map, const Item& item)
    94136        : Parent(item), map(_map) {}
    95137
    96       MapIt& operator++() {
    97         map.notifier()->next(*this);
     138      ConstMapIt& operator++() {
     139        map->notifier()->next(*this);
    98140        return *this;
    99141      }
     
    103145      }
    104146
    105       typename MapTraits<Map>::ReturnValue operator*() {
    106         return map[*this];
    107       }
    108 
    109       void set(const Value& value) {
    110         map.set(*this, value);
    111       }
    112 
    113     protected:
    114       Map& map;
    115 
    116     };
    117 
    118     class ConstMapIt : public Item {
    119       typedef Item Parent;
    120 
    121     public:
    122 
    123       typedef typename Map::Value Value;
    124 
    125       ConstMapIt() {}
    126 
    127       ConstMapIt(Invalid i) : Parent(i) { }
    128 
    129       explicit ConstMapIt(Map& _map) : map(_map) {
    130         map.notifier()->first(*this);
    131       }
    132 
    133       ConstMapIt(const Map& _map, const Item& item)
    134         : Parent(item), map(_map) {}
    135 
    136       ConstMapIt& operator++() {
    137         map.notifier()->next(*this);
    138         return *this;
    139       }
    140 
    141       typename MapTraits<Map>::ConstReturnValue operator*() const {
    142         return map[*this];
    143       }
    144 
    145     protected:
    146       const Map& map;
     147    protected:
     148      const Map* map;
    147149    };
    148150
     
    151153
    152154    public:
    153 
    154       ItemIt() {}
    155 
    156       ItemIt(Invalid i) : Parent(i) { }
    157 
    158       explicit ItemIt(Map& _map) : map(_map) {
    159         map.notifier()->first(*this);
     155      ItemIt() : map(NULL) {}
     156
     157
     158      ItemIt(Invalid i) : Parent(i), map(NULL) {}
     159
     160      explicit ItemIt(Map& _map) : map(&_map) {
     161        map->notifier()->first(*this);
    160162      }
    161163
    162164      ItemIt(const Map& _map, const Item& item)
    163         : Parent(item), map(_map) {}
     165        : Parent(item), map(&_map) {}
    164166
    165167      ItemIt& operator++() {
    166         map.notifier()->next(*this);
    167         return *this;
    168       }
    169 
    170     protected:
    171       const Map& map;
     168        map->notifier()->next(*this);
     169        return *this;
     170      }
     171
     172    protected:
     173      const Map* map;
    172174
    173175    };
     
    192194    typedef typename Parent::ConstReference ConstReference;
    193195
     196    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
     197
    194198    class MapIt;
    195199    class ConstMapIt;
     
    228232      typedef typename Map::Value Value;
    229233
    230       MapIt() {}
    231 
    232       MapIt(Invalid i) : Parent(i) { }
    233 
    234       explicit MapIt(Map& _map) : map(_map) {
    235         map.graph.first(*this);
     234      MapIt() : map(NULL) {}
     235
     236      MapIt(Invalid i) : Parent(i), map(NULL) { }
     237
     238      explicit MapIt(Map& _map) : map(&_map) {
     239        map->graph.first(*this);
    236240      }
    237241
    238242      MapIt(const Map& _map, const Item& item)
    239         : Parent(item), map(_map) {}
     243        : Parent(item), map(&_map) {}
    240244
    241245      MapIt& operator++() {
    242         map.graph.next(*this);
     246        map->graph.next(*this);
    243247        return *this;
    244248      }
    245249
    246250      typename MapTraits<Map>::ConstReturnValue operator*() const {
    247         return map[*this];
     251        return (*map)[*this];
    248252      }
    249253
    250254      typename MapTraits<Map>::ReturnValue operator*() {
    251         return map[*this];
     255        return (*map)[*this];
    252256      }
    253257
    254258      void set(const Value& value) {
    255         map.set(*this, value);
    256       }
    257 
    258     protected:
    259       Map& map;
     259        map->set(*this, value);
     260      }
     261
     262    protected:
     263      Map* map;
    260264
    261265    };
     
    268272      typedef typename Map::Value Value;
    269273
    270       ConstMapIt() {}
    271 
    272       ConstMapIt(Invalid i) : Parent(i) { }
    273 
    274       explicit ConstMapIt(Map& _map) : map(_map) {
    275         map.graph.first(*this);
     274      ConstMapIt() : map(NULL) {}
     275
     276      ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
     277
     278      explicit ConstMapIt(Map& _map) : map(&_map) {
     279        map->graph.first(*this);
    276280      }
    277281
    278282      ConstMapIt(const Map& _map, const Item& item)
    279         : Parent(item), map(_map) {}
     283        : Parent(item), map(&_map) {}
    280284
    281285      ConstMapIt& operator++() {
    282         map.graph.next(*this);
     286        map->graph.next(*this);
    283287        return *this;
    284288      }
    285289
    286290      typename MapTraits<Map>::ConstReturnValue operator*() const {
    287         return map[*this];
    288       }
    289 
    290     protected:
    291       const Map& map;
     291        return (*map)[*this];
     292      }
     293
     294    protected:
     295      const Map* map;
    292296    };
    293297
     
    296300
    297301    public:
    298 
    299       ItemIt() {}
    300 
    301       ItemIt(Invalid i) : Parent(i) { }
    302 
    303       explicit ItemIt(Map& _map) : map(_map) {
    304         map.graph.first(*this);
     302      ItemIt() : map(NULL) {}
     303
     304
     305      ItemIt(Invalid i) : Parent(i), map(NULL) { }
     306
     307      explicit ItemIt(Map& _map) : map(&_map) {
     308        map->graph.first(*this);
    305309      }
    306310
    307311      ItemIt(const Map& _map, const Item& item)
    308         : Parent(item), map(_map) {}
     312        : Parent(item), map(&_map) {}
    309313
    310314      ItemIt& operator++() {
    311         map.graph.next(*this);
    312         return *this;
    313       }
    314 
    315     protected:
    316       const Map& map;
     315        map->graph.next(*this);
     316        return *this;
     317      }
     318
     319    protected:
     320      const Map* map;
    317321
    318322    };
  • lemon/bits/path_dump.h

    r529 r890  
    5050
    5151    bool empty() const {
    52       return predMap[target] != INVALID;
     52      return predMap[target] == INVALID;
    5353    }
    5454
     
    124124
    125125    bool empty() const {
    126       return source != target;
     126      return predMatrixMap(source, target) == INVALID;
    127127    }
    128128
  • lemon/bits/windows.cc

    r483 r913  
    4141#include <unistd.h>
    4242#include <ctime>
     43#ifndef WIN32
    4344#include <sys/times.h>
     45#endif
    4446#include <sys/time.h>
    4547#endif
  • lemon/concepts/maps.h

    r529 r718  
    183183      template<typename _ReferenceMap>
    184184      struct Constraints {
    185         void constraints() {
     185        typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
     186        constraints() {
    186187          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
    187188          ref = m[key];
  • lemon/core.h

    r671 r937  
    395395      static void copy(const From& from, Digraph &to,
    396396                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
     397        to.clear();
    397398        for (typename From::NodeIt it(from); it != INVALID; ++it) {
    398399          nodeRefMap[it] = to.addNode();
     
    422423      static void copy(const From& from, Graph &to,
    423424                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
     425        to.clear();
    424426        for (typename From::NodeIt it(from); it != INVALID; ++it) {
    425427          nodeRefMap[it] = to.addNode();
  • lemon/dfs.h

    r584 r937  
    558558    void start(Node t)
    559559    {
    560       while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
     560      while ( !emptyQueue() && !(*_reached)[t] )
    561561        processNextArc();
    562562    }
     
    15101510    /// with addSource() before using this function.
    15111511    void start(Node t) {
    1512       while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
     1512      while ( !emptyQueue() && !(*_reached)[t] )
    15131513        processNextArc();
    15141514    }
  • lemon/glpk.h

    r650 r832  
    2626#include <lemon/lp_base.h>
    2727
    28 // forward declaration
    29 #if !defined _GLP_PROB && !defined GLP_PROB
    30 #define _GLP_PROB
    31 #define GLP_PROB
    32 typedef struct { double _opaque_prob; } glp_prob;
    33 /* LP/MIP problem object */
    34 #endif
    35 
    3628namespace lemon {
    3729
     30  namespace _solver_bits {
     31    class VoidPtr {
     32    private:
     33      void *_ptr;     
     34    public:
     35      VoidPtr() : _ptr(0) {}
     36
     37      template <typename T>
     38      VoidPtr(T* ptr) : _ptr(reinterpret_cast<void*>(ptr)) {}
     39
     40      template <typename T>
     41      VoidPtr& operator=(T* ptr) {
     42        _ptr = reinterpret_cast<void*>(ptr);
     43        return *this;
     44      }
     45
     46      template <typename T>
     47      operator T*() const { return reinterpret_cast<T*>(_ptr); }
     48    };
     49  }
    3850
    3951  /// \brief Base interface for the GLPK LP and MIP solver
     
    4456  protected:
    4557
    46     typedef glp_prob LPX;
    47     glp_prob* lp;
     58    _solver_bits::VoidPtr lp;
    4859
    4960    GlpkBase();
     
    123134
    124135    ///Pointer to the underlying GLPK data structure.
    125     LPX *lpx() {return lp;}
     136    _solver_bits::VoidPtr lpx() {return lp;}
    126137    ///Const pointer to the underlying GLPK data structure.
    127     const LPX *lpx() const {return lp;}
     138    _solver_bits::VoidPtr lpx() const {return lp;}
    128139
    129140    ///Returns the constraint identifier understood by GLPK.
  • lemon/graph_to_eps.h

    r617 r937  
    685685#else
    686686      os << bits::getWinFormattedDate();
     687      os << std::endl;
    687688#endif
    688689    }
    689     os << std::endl;
    690690
    691691    if (_autoArcWidthScale) {
  • lemon/lgf_reader.h

    r599 r937  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    965965        int index = 0;
    966966        while (_reader_bits::readToken(line, map)) {
     967          if(map == "-") {
     968              if(index!=0)
     969                throw FormatError("'-' is not allowed as a map name");
     970              else if (line >> std::ws >> c)
     971                throw FormatError("Extra character at the end of line");
     972              else break;
     973            }
    967974          if (maps.find(map) != maps.end()) {
    968975            std::ostringstream msg;
     
    18351842        int index = 0;
    18361843        while (_reader_bits::readToken(line, map)) {
     1844          if(map == "-") {
     1845              if(index!=0)
     1846                throw FormatError("'-' is not allowed as a map name");
     1847              else if (line >> std::ws >> c)
     1848                throw FormatError("Extra character at the end of line");
     1849              else break;
     1850            }
    18371851          if (maps.find(map) != maps.end()) {
    18381852            std::ostringstream msg;
  • lemon/lp_base.h

    r584 r932  
    16051605  inline LpBase::Constr operator<=(const LpBase::Expr &e,
    16061606                                   const LpBase::Expr &f) {
    1607     return LpBase::Constr(0, f - e, LpBase::INF);
     1607    return LpBase::Constr(0, f - e, LpBase::NaN);
    16081608  }
    16091609
     
    16231623  inline LpBase::Constr operator<=(const LpBase::Expr &e,
    16241624                                   const LpBase::Value &f) {
    1625     return LpBase::Constr(- LpBase::INF, e, f);
     1625    return LpBase::Constr(LpBase::NaN, e, f);
    16261626  }
    16271627
     
    16321632  inline LpBase::Constr operator>=(const LpBase::Expr &e,
    16331633                                   const LpBase::Expr &f) {
    1634     return LpBase::Constr(0, e - f, LpBase::INF);
     1634    return LpBase::Constr(0, e - f, LpBase::NaN);
    16351635  }
    16361636
     
    16521652  inline LpBase::Constr operator>=(const LpBase::Expr &e,
    16531653                                   const LpBase::Value &f) {
    1654     return LpBase::Constr(f, e, LpBase::INF);
     1654    return LpBase::Constr(f, e, LpBase::NaN);
    16551655  }
    16561656
  • lemon/network_simplex.h

    r663 r891  
    10431043        ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;
    10441044      } else {
    1045         ART_COST = std::numeric_limits<Cost>::min();
     1045        ART_COST = 0;
    10461046        for (int i = 0; i != _arc_num; ++i) {
    10471047          if (_cost[i] > ART_COST) ART_COST = _cost[i];
     
    14581458      if (_sum_supply == 0) {
    14591459        if (_stype == GEQ) {
    1460           Cost max_pot = std::numeric_limits<Cost>::min();
     1460          Cost max_pot = -std::numeric_limits<Cost>::max();
    14611461          for (int i = 0; i != _node_num; ++i) {
    14621462            if (_pi[i] > max_pot) max_pot = _pi[i];
  • lemon/path.h

    r559 r802  
    7171    template <typename CPath>
    7272    Path(const CPath& cpath) {
    73       copyPath(*this, cpath);
     73      pathCopy(cpath, *this);
    7474    }
    7575
     
    7979    template <typename CPath>
    8080    Path& operator=(const CPath& cpath) {
    81       copyPath(*this, cpath);
     81      pathCopy(cpath, *this);
    8282      return *this;
    8383    }
     
    259259    template <typename CPath>
    260260    SimplePath(const CPath& cpath) {
    261       copyPath(*this, cpath);
     261      pathCopy(cpath, *this);
    262262    }
    263263
     
    268268    template <typename CPath>
    269269    SimplePath& operator=(const CPath& cpath) {
    270       copyPath(*this, cpath);
     270      pathCopy(cpath, *this);
    271271      return *this;
    272272    }
     
    438438    template <typename CPath>
    439439    ListPath(const CPath& cpath) : first(0), last(0) {
    440       copyPath(*this, cpath);
     440      pathCopy(cpath, *this);
    441441    }
    442442
     
    454454    template <typename CPath>
    455455    ListPath& operator=(const CPath& cpath) {
    456       copyPath(*this, cpath);
     456      pathCopy(cpath, *this);
    457457      return *this;
    458458    }
     
    764764    template <typename CPath>
    765765    StaticPath(const CPath& cpath) : arcs(0) {
    766       copyPath(*this, cpath);
     766      pathCopy(cpath, *this);
    767767    }
    768768
     
    780780    template <typename CPath>
    781781    StaticPath& operator=(const CPath& cpath) {
    782       copyPath(*this, cpath);
     782      pathCopy(cpath, *this);
    783783      return *this;
    784784    }
     
    929929    };
    930930
    931     template <typename Target, typename Source,
    932               bool buildEnable = BuildTagIndicator<Target>::value>
     931    template <typename From, typename To,
     932              bool buildEnable = BuildTagIndicator<To>::value>
    933933    struct PathCopySelectorForward {
    934       static void copy(Target& target, const Source& source) {
    935         target.clear();
    936         for (typename Source::ArcIt it(source); it != INVALID; ++it) {
    937           target.addBack(it);
     934      static void copy(const From& from, To& to) {
     935        to.clear();
     936        for (typename From::ArcIt it(from); it != INVALID; ++it) {
     937          to.addBack(it);
    938938        }
    939939      }
    940940    };
    941941
    942     template <typename Target, typename Source>
    943     struct PathCopySelectorForward<Target, Source, true> {
    944       static void copy(Target& target, const Source& source) {
    945         target.clear();
    946         target.build(source);
    947       }
    948     };
    949 
    950     template <typename Target, typename Source,
    951               bool buildEnable = BuildTagIndicator<Target>::value>
     942    template <typename From, typename To>
     943    struct PathCopySelectorForward<From, To, true> {
     944      static void copy(const From& from, To& to) {
     945        to.clear();
     946        to.build(from);
     947      }
     948    };
     949
     950    template <typename From, typename To,
     951              bool buildEnable = BuildTagIndicator<To>::value>
    952952    struct PathCopySelectorBackward {
    953       static void copy(Target& target, const Source& source) {
    954         target.clear();
    955         for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
    956           target.addFront(it);
     953      static void copy(const From& from, To& to) {
     954        to.clear();
     955        for (typename From::RevArcIt it(from); it != INVALID; ++it) {
     956          to.addFront(it);
    957957        }
    958958      }
    959959    };
    960960
    961     template <typename Target, typename Source>
    962     struct PathCopySelectorBackward<Target, Source, true> {
    963       static void copy(Target& target, const Source& source) {
    964         target.clear();
    965         target.buildRev(source);
     961    template <typename From, typename To>
     962    struct PathCopySelectorBackward<From, To, true> {
     963      static void copy(const From& from, To& to) {
     964        to.clear();
     965        to.buildRev(from);
    966966      }
    967967    };
    968968
    969969   
    970     template <typename Target, typename Source,
    971               bool revEnable = RevPathTagIndicator<Source>::value>
     970    template <typename From, typename To,
     971              bool revEnable = RevPathTagIndicator<From>::value>
    972972    struct PathCopySelector {
    973       static void copy(Target& target, const Source& source) {
    974         PathCopySelectorForward<Target, Source>::copy(target, source);
     973      static void copy(const From& from, To& to) {
     974        PathCopySelectorForward<From, To>::copy(from, to);
    975975      }     
    976976    };
    977977
    978     template <typename Target, typename Source>
    979     struct PathCopySelector<Target, Source, true> {
    980       static void copy(Target& target, const Source& source) {
    981         PathCopySelectorBackward<Target, Source>::copy(target, source);
     978    template <typename From, typename To>
     979    struct PathCopySelector<From, To, true> {
     980      static void copy(const From& from, To& to) {
     981        PathCopySelectorBackward<From, To>::copy(from, to);
    982982      }     
    983983    };
     
    988988  /// \brief Make a copy of a path.
    989989  ///
    990   ///  This function makes a copy of a path.
    991   template <typename Target, typename Source>
    992   void copyPath(Target& target, const Source& source) {
    993     checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
    994     _path_bits::PathCopySelector<Target, Source>::copy(target, source);
     990  /// This function makes a copy of a path.
     991  template <typename From, typename To>
     992  void pathCopy(const From& from, To& to) {
     993    checkConcept<concepts::PathDumper<typename From::Digraph>, From>();
     994    _path_bits::PathCopySelector<From, To>::copy(from, to);
     995  }
     996
     997  /// \brief Deprecated version of \ref pathCopy().
     998  ///
     999  /// Deprecated version of \ref pathCopy() (only for reverse compatibility).
     1000  template <typename To, typename From>
     1001  void copyPath(To& to, const From& from) {
     1002    pathCopy(from, to);
    9951003  }
    9961004
     
    10161024  /// \brief The source of a path
    10171025  ///
    1018   /// This function returns the source of the given path.
     1026  /// This function returns the source node of the given path.
     1027  /// If the path is empty, then it returns \c INVALID.
    10191028  template <typename Digraph, typename Path>
    10201029  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
    1021     return digraph.source(path.front());
     1030    return path.empty() ? INVALID : digraph.source(path.front());
    10221031  }
    10231032
    10241033  /// \brief The target of a path
    10251034  ///
    1026   /// This function returns the target of the given path.
     1035  /// This function returns the target node of the given path.
     1036  /// If the path is empty, then it returns \c INVALID.
    10271037  template <typename Digraph, typename Path>
    10281038  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
    1029     return digraph.target(path.back());
     1039    return path.empty() ? INVALID : digraph.target(path.back());
    10301040  }
    10311041
  • lemon/preflow.h

    r688 r901  
    526526          _flow->set(e, (*_capacity)[e]);
    527527          (*_excess)[u] += rem;
    528           if (u != _target && !_level->active(u)) {
    529             _level->activate(u);
    530           }
    531528        }
    532529      }
     
    538535          _flow->set(e, 0);
    539536          (*_excess)[v] += rem;
    540           if (v != _target && !_level->active(v)) {
    541             _level->activate(v);
    542           }
    543         }
    544       }
     537        }
     538      }
     539      for (NodeIt n(_graph); n != INVALID; ++n)
     540        if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))
     541          _level->activate(n);
     542         
    545543      return true;
    546544    }
     
    559557      _phase = true;
    560558
    561       Node n = _level->highestActive();
    562       int level = _level->highestActiveLevel();
    563       while (n != INVALID) {
     559      while (true) {
    564560        int num = _node_num;
    565561
    566         while (num > 0 && n != INVALID) {
     562        Node n = INVALID;
     563        int level = -1;
     564
     565        while (num > 0) {
     566          n = _level->highestActive();
     567          if (n == INVALID) goto first_phase_done;
     568          level = _level->highestActiveLevel();
     569          --num;
     570         
    567571          Value excess = (*_excess)[n];
    568572          int new_level = _level->maxLevel();
     
    630634            _level->deactivate(n);
    631635          }
    632 
    633           n = _level->highestActive();
    634           level = _level->highestActiveLevel();
     636        }
     637
     638        num = _node_num * 20;
     639        while (num > 0) {
     640          while (level >= 0 && _level->activeFree(level)) {
     641            --level;
     642          }
     643          if (level == -1) {
     644            n = _level->highestActive();
     645            level = _level->highestActiveLevel();
     646            if (n == INVALID) goto first_phase_done;
     647          } else {
     648            n = _level->activeOn(level);
     649          }
    635650          --num;
    636         }
    637 
    638         num = _node_num * 20;
    639         while (num > 0 && n != INVALID) {
     651
    640652          Value excess = (*_excess)[n];
    641653          int new_level = _level->maxLevel();
     
    703715            _level->deactivate(n);
    704716          }
    705 
    706           while (level >= 0 && _level->activeFree(level)) {
    707             --level;
    708           }
    709           if (level == -1) {
    710             n = _level->highestActive();
    711             level = _level->highestActiveLevel();
    712           } else {
    713             n = _level->activeOn(level);
    714           }
    715           --num;
    716         }
    717       }
     717        }
     718      }
     719    first_phase_done:;
    718720    }
    719721
  • test/CMakeLists.txt

    r679 r937  
    77  ${PROJECT_BINARY_DIR}/lemon
    88)
     9
     10SET(TEST_WITH_VALGRIND "NO" CACHE STRING
     11  "Run the test with valgrind (YES/NO).")
     12SET(VALGRIND_FLAGS "" CACHE STRING "Valgrind flags used by the tests.")
    913
    1014SET(TESTS
     
    2832  heap_test
    2933  kruskal_test
     34  lgf_test
    3035  maps_test
    3136  matching_test
     
    4247
    4348IF(LEMON_HAVE_LP)
    44   ADD_EXECUTABLE(lp_test lp_test.cc)
     49  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     50    ADD_EXECUTABLE(lp_test lp_test.cc)
     51  ELSE()
     52    ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc)
     53  ENDIF()
     54
    4555  SET(LP_TEST_LIBS lemon)
    4656
     
    5767  TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
    5868  ADD_TEST(lp_test lp_test)
     69  ADD_DEPENDENCIES(check lp_test)
    5970
    6071  IF(WIN32 AND LEMON_HAVE_GLPK)
     
    7889
    7990IF(LEMON_HAVE_MIP)
    80   ADD_EXECUTABLE(mip_test mip_test.cc)
     91  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     92    ADD_EXECUTABLE(mip_test mip_test.cc)
     93  ELSE()
     94    ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc)
     95  ENDIF()
     96
    8197  SET(MIP_TEST_LIBS lemon)
    8298
     
    93109  TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})
    94110  ADD_TEST(mip_test mip_test)
     111  ADD_DEPENDENCIES(check mip_test)
    95112
    96113  IF(WIN32 AND LEMON_HAVE_GLPK)
     
    114131
    115132FOREACH(TEST_NAME ${TESTS})
    116   ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
     133  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     134    ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
     135  ELSE()
     136    ADD_EXECUTABLE(${TEST_NAME} EXCLUDE_FROM_ALL ${TEST_NAME}.cc)
     137  ENDIF()
    117138  TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
    118   ADD_TEST(${TEST_NAME} ${TEST_NAME})
     139    IF(TEST_WITH_VALGRIND)
     140      ADD_TEST(${TEST_NAME}
     141        valgrind --error-exitcode=1 ${VALGRIND_FLAGS}
     142        ${CMAKE_CURRENT_BINARY_DIR}/${TEST_NAME} )
     143    ELSE()
     144      ADD_TEST(${TEST_NAME} ${TEST_NAME})
     145    ENDIF()
     146  ADD_DEPENDENCIES(check ${TEST_NAME})
    119147ENDFOREACH()
  • test/Makefile.am

    r649 r937  
    2626        test/heap_test \
    2727        test/kruskal_test \
     28        test/lgf_test \
    2829        test/maps_test \
    2930        test/matching_test \
     
    7172test_kruskal_test_SOURCES = test/kruskal_test.cc
    7273test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
     74test_lgf_test_SOURCES = test/lgf_test.cc
    7375test_lp_test_SOURCES = test/lp_test.cc
    7476test_maps_test_SOURCES = test/maps_test.cc
  • test/dfs_test.cc

    r585 r937  
    5151  "@attributes\n"
    5252  "source 0\n"
    53   "target 5\n";
     53  "target 5\n"
     54  "source1 6\n"
     55  "target1 3\n";
     56
    5457
    5558void checkDfsCompile()
     
    180183  Digraph G;
    181184  Node s, t;
     185  Node s1, t1;
    182186
    183187  std::istringstream input(test_lgf);
     
    185189    node("source", s).
    186190    node("target", t).
     191    node("source1", s1).
     192    node("target1", t1).
    187193    run();
    188194
     
    211217
    212218  {
     219  Dfs<Digraph> dfs(G);
     220  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
     221  }
     222 
     223  {
    213224    NullMap<Node,Arc> myPredMap;
    214225    dfs(G).predMap(myPredMap).run(s);
  • test/graph_copy_test.cc

    r440 r896  
    3030  const int nn = 10;
    3131
     32  // Build a digraph
    3233  SmartDigraph from;
    3334  SmartDigraph::NodeMap<int> fnm(from);
     
    5253  }
    5354
     55  // Test digraph copy
    5456  ListDigraph to;
    5557  ListDigraph::NodeMap<int> tnm(to);
     
    6971    nodeCrossRef(ncr).arcCrossRef(ecr).
    7072    node(fn, tn).arc(fa, ta).run();
     73 
     74  check(countNodes(from) == countNodes(to), "Wrong copy.");
     75  check(countArcs(from) == countArcs(to), "Wrong copy.");
    7176
    7277  for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
     
    9196  check(tn == nr[fn], "Wrong copy.");
    9297  check(ta == er[fa], "Wrong copy.");
     98
     99  // Test repeated copy
     100  digraphCopy(from, to).run();
     101 
     102  check(countNodes(from) == countNodes(to), "Wrong copy.");
     103  check(countArcs(from) == countArcs(to), "Wrong copy.");
    93104}
    94105
     
    96107  const int nn = 10;
    97108
     109  // Build a graph
    98110  SmartGraph from;
    99111  SmartGraph::NodeMap<int> fnm(from);
     
    123135  }
    124136
     137  // Test graph copy
    125138  ListGraph to;
    126139  ListGraph::NodeMap<int> tnm(to);
     
    144157    nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
    145158    node(fn, tn).arc(fa, ta).edge(fe, te).run();
     159
     160  check(countNodes(from) == countNodes(to), "Wrong copy.");
     161  check(countEdges(from) == countEdges(to), "Wrong copy.");
     162  check(countArcs(from) == countArcs(to), "Wrong copy.");
    146163
    147164  for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
     
    181198  check(ta == ar[fa], "Wrong copy.");
    182199  check(te == er[fe], "Wrong copy.");
     200
     201  // Test repeated copy
     202  graphCopy(from, to).run();
     203 
     204  check(countNodes(from) == countNodes(to), "Wrong copy.");
     205  check(countEdges(from) == countEdges(to), "Wrong copy.");
     206  check(countArcs(from) == countArcs(to), "Wrong copy.");
    183207}
    184208
  • test/heap_test.cc

    r440 r681  
    3232
    3333#include <lemon/bin_heap.h>
     34#include <lemon/fib_heap.h>
     35#include <lemon/radix_heap.h>
     36#include <lemon/bucket_heap.h>
    3437
    3538#include "test_tools.h"
     
    184187  }
    185188
     189  {
     190    typedef FibHeap<Prio, ItemIntMap> IntHeap;
     191    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     192    heapSortTest<IntHeap>();
     193    heapIncreaseTest<IntHeap>();
     194
     195    typedef FibHeap<Prio, IntNodeMap > NodeHeap;
     196    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     197    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     198  }
     199
     200  {
     201    typedef RadixHeap<ItemIntMap> IntHeap;
     202    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     203    heapSortTest<IntHeap>();
     204    heapIncreaseTest<IntHeap>();
     205
     206    typedef RadixHeap<IntNodeMap > NodeHeap;
     207    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     208    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     209  }
     210
     211  {
     212    typedef BucketHeap<ItemIntMap> IntHeap;
     213    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     214    heapSortTest<IntHeap>();
     215    heapIncreaseTest<IntHeap>();
     216
     217    typedef BucketHeap<IntNodeMap > NodeHeap;
     218    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     219    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     220  }
     221
     222
    186223  return 0;
    187224}
  • test/lp_test.cc

    r631 r932  
    167167    c = ((2 >= p1) >= 3);
    168168
     169    { //Tests for #430
     170      LP::Col v=lp.addCol();
     171      LP::Constr c = v >= -3;
     172      c = c <= 4;
     173      LP::Constr c2;
     174      c2 = -3 <= v <= 4;
     175    }
     176
    169177    e[x[3]]=2;
    170178    e[x[3]]=4;
  • test/preflow_test.cc

    r585 r901  
    152152}
    153153
     154void initFlowTest()
     155{
     156  DIGRAPH_TYPEDEFS(SmartDigraph);
     157 
     158  SmartDigraph g;
     159  SmartDigraph::ArcMap<int> cap(g),iflow(g);
     160  Node s=g.addNode(); Node t=g.addNode();
     161  Node n1=g.addNode(); Node n2=g.addNode();
     162  Arc a;
     163  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
     164  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
     165  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
     166
     167  Preflow<SmartDigraph> pre(g,cap,s,t);
     168  pre.init(iflow);
     169  pre.startFirstPhase();
     170  check(pre.flowValue() == 10, "The incorrect max flow value.");
     171  check(pre.minCut(s), "Wrong min cut (Node s).");
     172  check(pre.minCut(n1), "Wrong min cut (Node n1).");
     173  check(!pre.minCut(n2), "Wrong min cut (Node n2).");
     174  check(!pre.minCut(t), "Wrong min cut (Node t).");
     175}
     176
     177
    154178int main() {
    155179
     
    242266        "The max flow value or the three min cut values are incorrect.");
    243267
     268  initFlowTest();
     269 
    244270  return 0;
    245271}
Note: See TracChangeset for help on using the changeset viewer.