COIN-OR::LEMON - Graph Library

Changeset 942:2b6bffe0e7e8 in lemon-1.2


Ignore:
Timestamp:
12/20/11 18:15:14 (12 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
941:7c4ba7daaf5f (diff), 915:633956ca9421 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge

Files:
38 edited

Legend:

Unmodified
Added
Removed
  • CMakeLists.txt

    r744 r942  
    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)
     
    39118
    40119ENABLE_TESTING()
     120
     121IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     122  ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
     123ELSE()
     124  ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})
     125ENDIF()
    41126
    42127ADD_SUBDIRECTORY(lemon)
     
    65150ENDIF()
    66151
    67 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
     152IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    68153  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    69154  SET(CPACK_PACKAGE_VENDOR "EGRES")
  • CMakeLists.txt

    r913 r942  
    115115SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
    116116
     117INCLUDE(FindPythonInterp)
     118
    117119ENABLE_TESTING()
    118120
  • configure.ac

    r793 r908  
    115115dnl Add dependencies on files generated by configure.
    116116AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
    117   ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
     117  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/doc/mainpage.dox.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
    118118
    119119AC_CONFIG_FILES([
     
    122122cmake/version.cmake
    123123doc/Doxyfile
     124doc/mainpage.dox
    124125lemon/lemon.pc
    125126])
  • configure.ac

    r907 r908  
    4242
    4343AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
     44AC_CHECK_PROG([python_found],[python],[yes],[no])
    4445AC_CHECK_PROG([gs_found],[gs],[yes],[no])
    4546
     
    8283fi
    8384AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
     85
     86dnl Support for running test cases using valgrind.
     87use_valgrind=no
     88AC_ARG_ENABLE([valgrind],
     89AS_HELP_STRING([--enable-valgrind], [use valgrind when running tests]),
     90              [use_valgrind=yes])
     91
     92if [[ "$use_valgrind" = "yes" ]]; then
     93  AC_CHECK_PROG(HAVE_VALGRIND, valgrind, yes, no)
     94
     95  if [[ "$HAVE_VALGRIND" = "no" ]]; then
     96    AC_MSG_ERROR([Valgrind not found in PATH.])
     97  fi
     98fi
     99AM_CONDITIONAL(USE_VALGRIND, [test "$use_valgrind" = "yes"])
    84100
    85101dnl Checks for header files.
     
    129145echo
    130146echo Build additional tools........ : $enable_tools
     147echo Use valgrind for tests........ : $use_valgrind
    131148echo
    132149echo The packace will be installed in
  • doc/CMakeLists.txt

    r865 r942  
    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)
     
    5361
    5462ENDIF()
     63
     64IF(WGET_FOUND)
     65ADD_CUSTOM_TARGET(update-external-tags
     66  COMMAND ${CMAKE_COMMAND} -E make_directory dl
     67  # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl
     68  COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
     69  COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag
     70  COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag
     71  COMMAND ${CMAKE_COMMAND} -E remove_directory dl
     72  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     73  )
     74ENDIF()
  • doc/CMakeLists.txt

    r907 r942  
    1818)
    1919
    20 IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
     20IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
    2121  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
    2222  SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
     
    2929    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
    3030    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
     31    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
    3132    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
    3233    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
     
    3536    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
    3637    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
     38    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
    3739    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
    3840    COMMAND ${CMAKE_COMMAND} -E remove_directory html
     41    COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
    3942    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    4043    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
  • doc/Doxyfile.in

    r756 r942  
    1 # Doxyfile 1.5.9
     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
     
    3032OPTIMIZE_FOR_FORTRAN   = NO
    3133OPTIMIZE_OUTPUT_VHDL   = NO
     34EXTENSION_MAPPING      =
    3235BUILTIN_STL_SUPPORT    = YES
    3336CPP_CLI_SUPPORT        = NO
     
    5558HIDE_SCOPE_NAMES       = YES
    5659SHOW_INCLUDE_FILES     = YES
     60FORCE_LOCAL_INCLUDES   = NO
    5761INLINE_INFO            = YES
    5862SORT_MEMBER_DOCS       = NO
    5963SORT_BRIEF_DOCS        = NO
     64SORT_MEMBERS_CTORS_1ST = NO
    6065SORT_GROUP_NAMES       = NO
    6166SORT_BY_SCOPE_NAME     = NO
     67STRICT_PROTO_MATCHING  = NO
    6268GENERATE_TODOLIST      = YES
    6369GENERATE_TESTLIST      = YES
     
    7177SHOW_NAMESPACES        = YES
    7278FILE_VERSION_FILTER    =
    73 LAYOUT_FILE            = DoxygenLayout.xml
     79LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
    7480#---------------------------------------------------------------------------
    7581# configuration options related to warning and progress messages
     
    9298                         "@abs_top_srcdir@/tools" \
    9399                         "@abs_top_srcdir@/test/test_tools.h" \
     100                         "@abs_top_builddir@/doc/mainpage.dox" \
    94101                         "@abs_top_builddir@/doc/references.dox"
    95102INPUT_ENCODING         = UTF-8
     
    112119FILTER_PATTERNS        =
    113120FILTER_SOURCE_FILES    = NO
     121FILTER_SOURCE_PATTERNS =
    114122#---------------------------------------------------------------------------
    115123# configuration options related to source browsing
    116124#---------------------------------------------------------------------------
    117 SOURCE_BROWSER         = NO
     125SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
    118126INLINE_SOURCES         = NO
    119127STRIP_CODE_COMMENTS    = YES
     
    138146HTML_FOOTER            =
    139147HTML_STYLESHEET        =
     148HTML_COLORSTYLE_HUE    = 220
     149HTML_COLORSTYLE_SAT    = 100
     150HTML_COLORSTYLE_GAMMA  = 80
     151HTML_TIMESTAMP         = YES
    140152HTML_ALIGN_MEMBERS     = YES
    141 HTML_DYNAMIC_SECTIONS  = NO
     153HTML_DYNAMIC_SECTIONS  = YES
    142154GENERATE_DOCSET        = NO
    143155DOCSET_FEEDNAME        = "Doxygen generated docs"
    144156DOCSET_BUNDLE_ID       = org.doxygen.Project
     157DOCSET_PUBLISHER_ID    = org.doxygen.Publisher
     158DOCSET_PUBLISHER_NAME  = Publisher
    145159GENERATE_HTMLHELP      = NO
    146160CHM_FILE               =
     
    154168QHP_NAMESPACE          = org.doxygen.Project
    155169QHP_VIRTUAL_FOLDER     = doc
     170QHP_CUST_FILTER_NAME   =
     171QHP_CUST_FILTER_ATTRS  =
     172QHP_SECT_FILTER_ATTRS  =
    156173QHG_LOCATION           =
     174GENERATE_ECLIPSEHELP   = NO
     175ECLIPSE_DOC_ID         = org.doxygen.Project
    157176DISABLE_INDEX          = NO
    158177ENUM_VALUES_PER_LINE   = 4
    159178GENERATE_TREEVIEW      = NO
     179USE_INLINE_TREES       = NO
    160180TREEVIEW_WIDTH         = 250
     181EXT_LINKS_IN_WINDOW    = NO
    161182FORMULA_FONTSIZE       = 10
     183FORMULA_TRANSPARENT    = YES
     184USE_MATHJAX            = NO
     185MATHJAX_RELPATH        = http://www.mathjax.org/mathjax
     186SEARCHENGINE           = YES
     187SERVER_BASED_SEARCH    = NO
    162188#---------------------------------------------------------------------------
    163189# configuration options related to the LaTeX output
     
    176202LATEX_BATCHMODE        = NO
    177203LATEX_HIDE_INDICES     = NO
     204LATEX_SOURCE_CODE      = NO
    178205#---------------------------------------------------------------------------
    179206# configuration options related to the RTF output
     
    224251SKIP_FUNCTION_MACROS   = YES
    225252#---------------------------------------------------------------------------
    226 # Options related to the search engine   
    227 #---------------------------------------------------------------------------
    228 TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
     253# Configuration::additions related to external references
     254#---------------------------------------------------------------------------
     255TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
    229256GENERATE_TAGFILE       = html/lemon.tag
    230257ALLEXTERNALS           = NO
     
    238265HIDE_UNDOC_RELATIONS   = YES
    239266HAVE_DOT               = YES
     267DOT_NUM_THREADS        = 0
    240268DOT_FONTNAME           = FreeSans
    241269DOT_FONTSIZE           = 10
     
    255283DOT_PATH               =
    256284DOTFILE_DIRS           =
     285MSCFILE_DIRS           =
    257286DOT_GRAPH_MAX_NODES    = 50
    258287MAX_DOT_GRAPH_DEPTH    = 0
     
    261290GENERATE_LEGEND        = YES
    262291DOT_CLEANUP            = YES
    263 #---------------------------------------------------------------------------
    264 # Configuration::additions related to the search engine   
    265 #---------------------------------------------------------------------------
    266 SEARCHENGINE           = NO
  • doc/Doxyfile.in

    r907 r942  
    9898                         "@abs_top_srcdir@/tools" \
    9999                         "@abs_top_srcdir@/test/test_tools.h" \
    100                          "@abs_top_builddir@/doc/mainpage.dox"
     100                         "@abs_top_builddir@/doc/mainpage.dox" \
     101                         "@abs_top_builddir@/doc/references.dox"
    101102INPUT_ENCODING         = UTF-8
    102103FILE_PATTERNS          = *.h \
  • doc/mainpage.dox.in

    r907 r908  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2222\section intro Introduction
    2323
    24 \subsection whatis What is LEMON
    25 
    26 LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
    27 and <b>O</b>ptimization in <b>N</b>etworks.
    28 It is a C++ template
    29 library aimed at combinatorial optimization tasks which
    30 often involve in working
    31 with graphs.
     24<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
     25and <b>O</b>ptimization in <b>N</b>etworks</i>.
     26It is a C++ template library providing efficient implementations of common
     27data structures and algorithms with focus on combinatorial optimization
     28tasks connected mainly with graphs and networks.
    3229
    3330<b>
     
    3936</b>
    4037
    41 \subsection howtoread How to read the documentation
     38The project is maintained by the
     39<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
     40Combinatorial Optimization</a> \ref egres
     41at the Operations Research Department of the
     42<a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,
     43Budapest, Hungary.
     44LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
     45initiative \ref coinor.
     46
     47\section howtoread How to Read the Documentation
    4248
    4349If you would like to get to know the library, see
    4450<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
     51
     52If you are interested in starting to use the library, see the <a class="el"
     53href="http://lemon.cs.elte.hu/trac/lemon/wiki/InstallGuide/">Installation
     54Guide</a>.
    4555
    4656If you know what you are looking for, then try to find it under the
  • lemon/Makefile.am

    r874 r942  
    11EXTRA_DIST += \
    22        lemon/lemon.pc.in \
     3        lemon/lemon.pc.cmake \
    34        lemon/CMakeLists.txt \
    45        lemon/config.h.cmake
  • lemon/Makefile.am

    r941 r942  
    5959        lemon/arg_parser.h \
    6060        lemon/assert.h \
     61        lemon/bellman_ford.h \
    6162        lemon/bfs.h \
    6263        lemon/bin_heap.h \
     64        lemon/binomial_heap.h \
    6365        lemon/bucket_heap.h \
     66        lemon/capacity_scaling.h \
    6467        lemon/cbc.h \
    6568        lemon/circulation.h \
     
    6871        lemon/concept_check.h \
    6972        lemon/connectivity.h \
     73        lemon/core.h \
     74        lemon/cost_scaling.h \
    7075        lemon/counter.h \
    71         lemon/core.h \
    7276        lemon/cplex.h \
     77        lemon/cycle_canceling.h \
    7378        lemon/dfs.h \
     79        lemon/dheap.h \
    7480        lemon/dijkstra.h \
    7581        lemon/dim2.h \
     
    8086        lemon/euler.h \
    8187        lemon/fib_heap.h \
     88        lemon/fractional_matching.h \
    8289        lemon/full_graph.h \
    8390        lemon/glpk.h \
     
    8592        lemon/graph_to_eps.h \
    8693        lemon/grid_graph.h \
     94        lemon/hartmann_orlin_mmc.h \
     95        lemon/howard_mmc.h \
    8796        lemon/hypercube_graph.h \
     97        lemon/karp_mmc.h \
    8898        lemon/kruskal.h \
    8999        lemon/hao_orlin.h \
     
    100110        lemon/nauty_reader.h \
    101111        lemon/network_simplex.h \
     112        lemon/pairing_heap.h \
    102113        lemon/path.h \
     114        lemon/planarity.h \
    103115        lemon/preflow.h \
     116        lemon/quad_heap.h \
    104117        lemon/radix_heap.h \
    105118        lemon/radix_sort.h \
     
    107120        lemon/smart_graph.h \
    108121        lemon/soplex.h \
     122        lemon/static_graph.h \
    109123        lemon/suurballe.h \
    110124        lemon/time_measure.h \
  • lemon/bits/edge_set_extender.h

    r877 r942  
    281281    typedef EdgeSetExtender Graph;
    282282
     283    typedef True UndirectedTag;
     284
    283285    typedef typename Parent::Node Node;
    284286    typedef typename Parent::Arc Arc;
  • lemon/bits/edge_set_extender.h

    r940 r942  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6464    Node oppositeNode(const Node &n, const Arc &e) const {
    6565      if (n == Parent::source(e))
    66         return Parent::target(e);
     66        return Parent::target(e);
    6767      else if(n==Parent::target(e))
    68         return Parent::source(e);
     68        return Parent::source(e);
    6969      else
    70         return INVALID;
     70        return INVALID;
    7171    }
    7272
     
    9292    // Iterable extensions
    9393
    94     class NodeIt : public Node { 
     94    class NodeIt : public Node {
    9595      const Digraph* digraph;
    9696    public:
     
    101101
    102102      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
    103         _graph.first(static_cast<Node&>(*this));
    104       }
    105 
    106       NodeIt(const Digraph& _graph, const Node& node) 
    107         : Node(node), digraph(&_graph) {}
    108 
    109       NodeIt& operator++() { 
    110         digraph->next(*this);
    111         return *this;
    112       }
    113 
    114     };
    115 
    116 
    117     class ArcIt : public Arc { 
     103        _graph.first(static_cast<Node&>(*this));
     104      }
     105
     106      NodeIt(const Digraph& _graph, const Node& node)
     107        : Node(node), digraph(&_graph) {}
     108
     109      NodeIt& operator++() {
     110        digraph->next(*this);
     111        return *this;
     112      }
     113
     114    };
     115
     116
     117    class ArcIt : public Arc {
    118118      const Digraph* digraph;
    119119    public:
     
    124124
    125125      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
    126         _graph.first(static_cast<Arc&>(*this));
    127       }
    128 
    129       ArcIt(const Digraph& _graph, const Arc& e) : 
    130         Arc(e), digraph(&_graph) { }
    131 
    132       ArcIt& operator++() { 
    133         digraph->next(*this);
    134         return *this;
    135       }
    136 
    137     };
    138 
    139 
    140     class OutArcIt : public Arc { 
     126        _graph.first(static_cast<Arc&>(*this));
     127      }
     128
     129      ArcIt(const Digraph& _graph, const Arc& e) :
     130        Arc(e), digraph(&_graph) { }
     131
     132      ArcIt& operator++() {
     133        digraph->next(*this);
     134        return *this;
     135      }
     136
     137    };
     138
     139
     140    class OutArcIt : public Arc {
    141141      const Digraph* digraph;
    142142    public:
     
    146146      OutArcIt(Invalid i) : Arc(i) { }
    147147
    148       OutArcIt(const Digraph& _graph, const Node& node) 
    149         : digraph(&_graph) {
    150         _graph.firstOut(*this, node);
    151       }
    152 
    153       OutArcIt(const Digraph& _graph, const Arc& arc) 
    154         : Arc(arc), digraph(&_graph) {}
    155 
    156       OutArcIt& operator++() { 
    157         digraph->nextOut(*this);
    158         return *this;
    159       }
    160 
    161     };
    162 
    163 
    164     class InArcIt : public Arc { 
     148      OutArcIt(const Digraph& _graph, const Node& node)
     149        : digraph(&_graph) {
     150        _graph.firstOut(*this, node);
     151      }
     152
     153      OutArcIt(const Digraph& _graph, const Arc& arc)
     154        : Arc(arc), digraph(&_graph) {}
     155
     156      OutArcIt& operator++() {
     157        digraph->nextOut(*this);
     158        return *this;
     159      }
     160
     161    };
     162
     163
     164    class InArcIt : public Arc {
    165165      const Digraph* digraph;
    166166    public:
     
    170170      InArcIt(Invalid i) : Arc(i) { }
    171171
    172       InArcIt(const Digraph& _graph, const Node& node) 
    173         : digraph(&_graph) {
    174         _graph.firstIn(*this, node);
    175       }
    176 
    177       InArcIt(const Digraph& _graph, const Arc& arc) : 
    178         Arc(arc), digraph(&_graph) {}
    179 
    180       InArcIt& operator++() { 
    181         digraph->nextIn(*this);
    182         return *this;
     172      InArcIt(const Digraph& _graph, const Node& node)
     173        : digraph(&_graph) {
     174        _graph.firstIn(*this, node);
     175      }
     176
     177      InArcIt(const Digraph& _graph, const Arc& arc) :
     178        Arc(arc), digraph(&_graph) {}
     179
     180      InArcIt& operator++() {
     181        digraph->nextIn(*this);
     182        return *this;
    183183      }
    184184
     
    216216
    217217    // Mappable extension
    218    
     218
    219219    template <typename _Value>
    220     class ArcMap 
     220    class ArcMap
    221221      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    222222      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    223223
    224224    public:
    225       explicit ArcMap(const Digraph& _g) 
    226         : Parent(_g) {}
    227       ArcMap(const Digraph& _g, const _Value& _v) 
    228         : Parent(_g, _v) {}
     225      explicit ArcMap(const Digraph& _g)
     226        : Parent(_g) {}
     227      ArcMap(const Digraph& _g, const _Value& _v)
     228        : Parent(_g, _v) {}
    229229
    230230      ArcMap& operator=(const ArcMap& cmap) {
    231         return operator=<ArcMap>(cmap);
     231        return operator=<ArcMap>(cmap);
    232232      }
    233233
     
    235235      ArcMap& operator=(const CMap& cmap) {
    236236        Parent::operator=(cmap);
    237         return *this;
     237        return *this;
    238238      }
    239239
     
    248248      return arc;
    249249    }
    250    
     250
    251251    void clear() {
    252252      notifier(Arc()).clear();
     
    313313    Node oppositeNode(const Node &n, const Edge &e) const {
    314314      if( n == Parent::u(e))
    315         return Parent::v(e);
     315        return Parent::v(e);
    316316      else if( n == Parent::v(e))
    317         return Parent::u(e);
     317        return Parent::u(e);
    318318      else
    319         return INVALID;
     319        return INVALID;
    320320    }
    321321
     
    341341
    342342    using Parent::notifier;
    343    
     343
    344344    ArcNotifier& notifier(Arc) const {
    345345      return arc_notifier;
     
    351351
    352352
    353     class NodeIt : public Node { 
     353    class NodeIt : public Node {
    354354      const Graph* graph;
    355355    public:
     
    360360
    361361      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
    362         _graph.first(static_cast<Node&>(*this));
    363       }
    364 
    365       NodeIt(const Graph& _graph, const Node& node) 
    366         : Node(node), graph(&_graph) {}
    367 
    368       NodeIt& operator++() { 
    369         graph->next(*this);
    370         return *this;
    371       }
    372 
    373     };
    374 
    375 
    376     class ArcIt : public Arc { 
     362        _graph.first(static_cast<Node&>(*this));
     363      }
     364
     365      NodeIt(const Graph& _graph, const Node& node)
     366        : Node(node), graph(&_graph) {}
     367
     368      NodeIt& operator++() {
     369        graph->next(*this);
     370        return *this;
     371      }
     372
     373    };
     374
     375
     376    class ArcIt : public Arc {
    377377      const Graph* graph;
    378378    public:
     
    383383
    384384      explicit ArcIt(const Graph& _graph) : graph(&_graph) {
    385         _graph.first(static_cast<Arc&>(*this));
    386       }
    387 
    388       ArcIt(const Graph& _graph, const Arc& e) : 
    389         Arc(e), graph(&_graph) { }
    390 
    391       ArcIt& operator++() { 
    392         graph->next(*this);
    393         return *this;
    394       }
    395 
    396     };
    397 
    398 
    399     class OutArcIt : public Arc { 
     385        _graph.first(static_cast<Arc&>(*this));
     386      }
     387
     388      ArcIt(const Graph& _graph, const Arc& e) :
     389        Arc(e), graph(&_graph) { }
     390
     391      ArcIt& operator++() {
     392        graph->next(*this);
     393        return *this;
     394      }
     395
     396    };
     397
     398
     399    class OutArcIt : public Arc {
    400400      const Graph* graph;
    401401    public:
     
    405405      OutArcIt(Invalid i) : Arc(i) { }
    406406
    407       OutArcIt(const Graph& _graph, const Node& node) 
    408         : graph(&_graph) {
    409         _graph.firstOut(*this, node);
    410       }
    411 
    412       OutArcIt(const Graph& _graph, const Arc& arc) 
    413         : Arc(arc), graph(&_graph) {}
    414 
    415       OutArcIt& operator++() { 
    416         graph->nextOut(*this);
    417         return *this;
    418       }
    419 
    420     };
    421 
    422 
    423     class InArcIt : public Arc { 
     407      OutArcIt(const Graph& _graph, const Node& node)
     408        : graph(&_graph) {
     409        _graph.firstOut(*this, node);
     410      }
     411
     412      OutArcIt(const Graph& _graph, const Arc& arc)
     413        : Arc(arc), graph(&_graph) {}
     414
     415      OutArcIt& operator++() {
     416        graph->nextOut(*this);
     417        return *this;
     418      }
     419
     420    };
     421
     422
     423    class InArcIt : public Arc {
    424424      const Graph* graph;
    425425    public:
     
    429429      InArcIt(Invalid i) : Arc(i) { }
    430430
    431       InArcIt(const Graph& _graph, const Node& node) 
    432         : graph(&_graph) {
    433         _graph.firstIn(*this, node);
    434       }
    435 
    436       InArcIt(const Graph& _graph, const Arc& arc) : 
    437         Arc(arc), graph(&_graph) {}
    438 
    439       InArcIt& operator++() { 
    440         graph->nextIn(*this);
    441         return *this;
    442       }
    443 
    444     };
    445 
    446 
    447     class EdgeIt : public Parent::Edge { 
     431      InArcIt(const Graph& _graph, const Node& node)
     432        : graph(&_graph) {
     433        _graph.firstIn(*this, node);
     434      }
     435
     436      InArcIt(const Graph& _graph, const Arc& arc) :
     437        Arc(arc), graph(&_graph) {}
     438
     439      InArcIt& operator++() {
     440        graph->nextIn(*this);
     441        return *this;
     442      }
     443
     444    };
     445
     446
     447    class EdgeIt : public Parent::Edge {
    448448      const Graph* graph;
    449449    public:
     
    454454
    455455      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
    456         _graph.first(static_cast<Edge&>(*this));
    457       }
    458 
    459       EdgeIt(const Graph& _graph, const Edge& e) : 
    460         Edge(e), graph(&_graph) { }
    461 
    462       EdgeIt& operator++() { 
    463         graph->next(*this);
    464         return *this;
     456        _graph.first(static_cast<Edge&>(*this));
     457      }
     458
     459      EdgeIt(const Graph& _graph, const Edge& e) :
     460        Edge(e), graph(&_graph) { }
     461
     462      EdgeIt& operator++() {
     463        graph->next(*this);
     464        return *this;
    465465      }
    466466
     
    478478
    479479      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
    480         _graph.firstInc(*this, direction, n);
     480        _graph.firstInc(*this, direction, n);
    481481      }
    482482
    483483      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
    484         : graph(&_graph), Edge(ue) {
    485         direction = (_graph.source(ue) == n);
     484        : graph(&_graph), Edge(ue) {
     485        direction = (_graph.source(ue) == n);
    486486      }
    487487
    488488      IncEdgeIt& operator++() {
    489         graph->nextInc(*this, direction);
    490         return *this;
     489        graph->nextInc(*this, direction);
     490        return *this;
    491491      }
    492492    };
     
    535535
    536536    template <typename _Value>
    537     class ArcMap 
     537    class ArcMap
    538538      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    539539      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    540540
    541541    public:
    542       explicit ArcMap(const Graph& _g) 
    543         : Parent(_g) {}
    544       ArcMap(const Graph& _g, const _Value& _v) 
    545         : Parent(_g, _v) {}
     542      explicit ArcMap(const Graph& _g)
     543        : Parent(_g) {}
     544      ArcMap(const Graph& _g, const _Value& _v)
     545        : Parent(_g, _v) {}
    546546
    547547      ArcMap& operator=(const ArcMap& cmap) {
    548         return operator=<ArcMap>(cmap);
     548        return operator=<ArcMap>(cmap);
    549549      }
    550550
     
    552552      ArcMap& operator=(const CMap& cmap) {
    553553        Parent::operator=(cmap);
    554         return *this;
     554        return *this;
    555555      }
    556556
     
    559559
    560560    template <typename _Value>
    561     class EdgeMap 
     561    class EdgeMap
    562562      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    563563      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    564564
    565565    public:
    566       explicit EdgeMap(const Graph& _g) 
    567         : Parent(_g) {}
    568 
    569       EdgeMap(const Graph& _g, const _Value& _v) 
    570         : Parent(_g, _v) {}
     566      explicit EdgeMap(const Graph& _g)
     567        : Parent(_g) {}
     568
     569      EdgeMap(const Graph& _g, const _Value& _v)
     570        : Parent(_g, _v) {}
    571571
    572572      EdgeMap& operator=(const EdgeMap& cmap) {
    573         return operator=<EdgeMap>(cmap);
     573        return operator=<EdgeMap>(cmap);
    574574      }
    575575
     
    577577      EdgeMap& operator=(const CMap& cmap) {
    578578        Parent::operator=(cmap);
    579         return *this;
     579        return *this;
    580580      }
    581581
     
    594594      return edge;
    595595    }
    596    
     596
    597597    void clear() {
    598598      notifier(Arc()).clear();
     
    620620      arc_notifier.clear();
    621621    }
    622    
     622
    623623  };
    624624
  • lemon/bits/windows.cc

    r877 r914  
    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/bits/windows.cc

    r913 r914  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9999      GetSystemTime(&time);
    100100      char buf1[11], buf2[9], buf3[5];
    101           if (GetDateFormat(MY_LOCALE, 0, &time,
     101          if (GetDateFormat(MY_LOCALE, 0, &time,
    102102                        ("ddd MMM dd"), buf1, 11) &&
    103103          GetTimeFormat(MY_LOCALE, 0, &time,
  • lemon/core.h

    r877 r942  
    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/core.h

    r937 r942  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    12421242  protected:
    12431243
    1244     class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
     1244    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
     1245    {
    12451246      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
    12461247
     
    12811282    };
    12821283
    1283   protected: 
     1284  protected:
    12841285
    12851286    const Digraph &_g;
  • lemon/dfs.h

    r877 r942  
    566566    void start(Node t)
    567567    {
    568       while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
     568      while ( !emptyQueue() && !(*_reached)[t] )
    569569        processNextArc();
    570570    }
     
    15131513    /// with addSource() before using this function.
    15141514    void start(Node t) {
    1515       while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
     1515      while ( !emptyQueue() && !(*_reached)[t] )
    15161516        processNextArc();
    15171517    }
  • lemon/dfs.h

    r937 r942  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the %DFS paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    5252    ///Instantiates a \c PredMap.
     
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    65     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     65    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     66    ///By default, it is a NullMap.
    6667    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6768    ///Instantiates a \c ProcessedMap.
     
    8283
    8384    ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to
     86    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8587    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8688    ///Instantiates a \c ReachedMap.
     
    9799
    98100    ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     101    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    100102    typedef typename Digraph::template NodeMap<int> DistMap;
    101103    ///Instantiates a \c DistMap.
     
    121123  ///\tparam GR The type of the digraph the algorithm runs on.
    122124  ///The default type is \ref ListDigraph.
     125  ///\tparam TR The traits class that defines various types used by the
     126  ///algorithm. By default, it is \ref DfsDefaultTraits
     127  ///"DfsDefaultTraits<GR>".
     128  ///In most cases, this parameter should not be set directly,
     129  ///consider to use the named template parameters instead.
    123130#ifdef DOXYGEN
    124131  template <typename GR,
     
    225232    ///\ref named-templ-param "Named parameter" for setting
    226233    ///\c PredMap type.
    227     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     234    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    228235    template <class T>
    229236    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     
    245252    ///\ref named-templ-param "Named parameter" for setting
    246253    ///\c DistMap type.
    247     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     254    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    248255    template <class T>
    249256    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     
    265272    ///\ref named-templ-param "Named parameter" for setting
    266273    ///\c ReachedMap type.
    267     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     274    ///It must conform to
     275    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    268276    template <class T>
    269277    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     
    285293    ///\ref named-templ-param "Named parameter" for setting
    286294    ///\c ProcessedMap type.
    287     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     295    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    288296    template <class T>
    289297    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     
    412420    ///The simplest way to execute the DFS algorithm is to use one of the
    413421    ///member functions called \ref run(Node) "run()".\n
    414     ///If you need more control on the execution, first you have to call
    415     ///\ref init(), then you can add a source node with \ref addSource()
     422    ///If you need better control on the execution, you have to call
     423    ///\ref init() first, then you can add a source node with \ref addSource()
    416424    ///and perform the actual computation with \ref start().
    417425    ///This procedure can be repeated if there are nodes that have not
     
    633641    ///Runs the algorithm to visit all nodes in the digraph.
    634642
    635     ///This method runs the %DFS algorithm in order to compute the
    636     ///%DFS path to each node.
    637     ///
    638     ///The algorithm computes
    639     ///- the %DFS tree (forest),
    640     ///- the distance of each node from the root(s) in the %DFS tree.
     643    ///This method runs the %DFS algorithm in order to visit all nodes
     644    ///in the digraph.
    641645    ///
    642646    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
     
    670674    ///@{
    671675
    672     ///The DFS path to a node.
    673 
    674     ///Returns the DFS path to a node.
     676    ///The DFS path to the given node.
     677
     678    ///Returns the DFS path to the given node from the root(s).
    675679    ///
    676680    ///\warning \c t should be reached from the root(s).
     
    680684    Path path(Node t) const { return Path(*G, *_pred, t); }
    681685
    682     ///The distance of a node from the root(s).
    683 
    684     ///Returns the distance of a node from the root(s).
     686    ///The distance of the given node from the root(s).
     687
     688    ///Returns the distance of the given node from the root(s).
    685689    ///
    686690    ///\warning If node \c v is not reached from the root(s), then
     
    691695    int dist(Node v) const { return (*_dist)[v]; }
    692696
    693     ///Returns the 'previous arc' of the %DFS tree for a node.
     697    ///Returns the 'previous arc' of the %DFS tree for the given node.
    694698
    695699    ///This function returns the 'previous arc' of the %DFS tree for the
     
    699703    ///
    700704    ///The %DFS tree used here is equal to the %DFS tree used in
    701     ///\ref predNode().
     705    ///\ref predNode() and \ref predMap().
    702706    ///
    703707    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    705709    Arc predArc(Node v) const { return (*_pred)[v];}
    706710
    707     ///Returns the 'previous node' of the %DFS tree.
     711    ///Returns the 'previous node' of the %DFS tree for the given node.
    708712
    709713    ///This function returns the 'previous node' of the %DFS
    710714    ///tree for the node \c v, i.e. it returns the last but one node
    711     ///from a %DFS path from a root to \c v. It is \c INVALID
     715    ///of a %DFS path from a root to \c v. It is \c INVALID
    712716    ///if \c v is not reached from the root(s) or if \c v is a root.
    713717    ///
    714718    ///The %DFS tree used here is equal to the %DFS tree used in
    715     ///\ref predArc().
     719    ///\ref predArc() and \ref predMap().
    716720    ///
    717721    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    734738    ///
    735739    ///Returns a const reference to the node map that stores the predecessor
    736     ///arcs, which form the DFS tree.
     740    ///arcs, which form the DFS tree (forest).
    737741    ///
    738742    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    740744    const PredMap &predMap() const { return *_pred;}
    741745
    742     ///Checks if a node is reached from the root(s).
     746    ///Checks if the given node. node is reached from the root(s).
    743747
    744748    ///Returns \c true if \c v is reached from the root(s).
     
    766770    ///The type of the map that stores the predecessor
    767771    ///arcs of the %DFS paths.
    768     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     772    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    769773    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    770774    ///Instantiates a PredMap.
     
    781785
    782786    ///The type of the map that indicates which nodes are processed.
    783     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    784     ///By default it is a NullMap.
     787    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     788    ///By default, it is a NullMap.
    785789    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    786790    ///Instantiates a ProcessedMap.
     
    801805
    802806    ///The type of the map that indicates which nodes are reached.
    803     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     807    ///It must conform to
     808    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    804809    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    805810    ///Instantiates a ReachedMap.
     
    816821
    817822    ///The type of the map that stores the distances of the nodes.
    818     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     823    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    819824    typedef typename Digraph::template NodeMap<int> DistMap;
    820825    ///Instantiates a DistMap.
     
    831836
    832837    ///The type of the DFS paths.
    833     ///It must meet the \ref concepts::Path "Path" concept.
     838    ///It must conform to the \ref concepts::Path "Path" concept.
    834839    typedef lemon::Path<Digraph> Path;
    835840  };
     
    837842  /// Default traits class used by DfsWizard
    838843
    839   /// To make it easier to use Dfs algorithm
    840   /// we have created a wizard class.
    841   /// This \ref DfsWizard class needs default traits,
    842   /// as well as the \ref Dfs class.
    843   /// The \ref DfsWizardBase is a class to be the default traits of the
    844   /// \ref DfsWizard class.
     844  /// Default traits class used by DfsWizard.
     845  /// \tparam GR The type of the digraph.
    845846  template<class GR>
    846847  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
     
    870871    /// Constructor.
    871872
    872     /// This constructor does not require parameters, therefore it initiates
     873    /// This constructor does not require parameters, it initiates
    873874    /// all of the attributes to \c 0.
    874875    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    895896  /// This class should only be used through the \ref dfs() function,
    896897  /// which makes it easier to use the algorithm.
     898  ///
     899  /// \tparam TR The traits class that defines various types used by the
     900  /// algorithm.
    897901  template<class TR>
    898902  class DfsWizard : public TR
     
    900904    typedef TR Base;
    901905
    902     ///The type of the digraph the algorithm runs on.
    903906    typedef typename TR::Digraph Digraph;
    904907
     
    908911    typedef typename Digraph::OutArcIt OutArcIt;
    909912
    910     ///\brief The type of the map that stores the predecessor
    911     ///arcs of the DFS paths.
    912913    typedef typename TR::PredMap PredMap;
    913     ///\brief The type of the map that stores the distances of the nodes.
    914914    typedef typename TR::DistMap DistMap;
    915     ///\brief The type of the map that indicates which nodes are reached.
    916915    typedef typename TR::ReachedMap ReachedMap;
    917     ///\brief The type of the map that indicates which nodes are processed.
    918916    typedef typename TR::ProcessedMap ProcessedMap;
    919     ///The type of the DFS paths
    920917    typedef typename TR::Path Path;
    921918
     
    987984    ///Runs DFS algorithm to visit all nodes in the digraph.
    988985
    989     ///This method runs DFS algorithm in order to compute
    990     ///the DFS path to each node.
     986    ///This method runs DFS algorithm in order to visit all nodes
     987    ///in the digraph.
    991988    void run()
    992989    {
     
    1000997      SetPredMapBase(const TR &b) : TR(b) {}
    1001998    };
    1002     ///\brief \ref named-func-param "Named parameter"
    1003     ///for setting PredMap object.
    1004     ///
    1005     ///\ref named-func-param "Named parameter"
    1006     ///for setting PredMap object.
     999
     1000    ///\brief \ref named-templ-param "Named parameter" for setting
     1001    ///the predecessor map.
     1002    ///
     1003    ///\ref named-templ-param "Named parameter" function for setting
     1004    ///the map that stores the predecessor arcs of the nodes.
    10071005    template<class T>
    10081006    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10181016      SetReachedMapBase(const TR &b) : TR(b) {}
    10191017    };
    1020     ///\brief \ref named-func-param "Named parameter"
    1021     ///for setting ReachedMap object.
    1022     ///
    1023     /// \ref named-func-param "Named parameter"
    1024     ///for setting ReachedMap object.
     1018
     1019    ///\brief \ref named-templ-param "Named parameter" for setting
     1020    ///the reached map.
     1021    ///
     1022    ///\ref named-templ-param "Named parameter" function for setting
     1023    ///the map that indicates which nodes are reached.
    10251024    template<class T>
    10261025    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    10361035      SetDistMapBase(const TR &b) : TR(b) {}
    10371036    };
    1038     ///\brief \ref named-func-param "Named parameter"
    1039     ///for setting DistMap object.
    1040     ///
    1041     /// \ref named-func-param "Named parameter"
    1042     ///for setting DistMap object.
     1037
     1038    ///\brief \ref named-templ-param "Named parameter" for setting
     1039    ///the distance map.
     1040    ///
     1041    ///\ref named-templ-param "Named parameter" function for setting
     1042    ///the map that stores the distances of the nodes calculated
     1043    ///by the algorithm.
    10431044    template<class T>
    10441045    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    10541055      SetProcessedMapBase(const TR &b) : TR(b) {}
    10551056    };
    1056     ///\brief \ref named-func-param "Named parameter"
    1057     ///for setting ProcessedMap object.
    1058     ///
    1059     /// \ref named-func-param "Named parameter"
    1060     ///for setting ProcessedMap object.
     1057
     1058    ///\brief \ref named-func-param "Named parameter" for setting
     1059    ///the processed map.
     1060    ///
     1061    ///\ref named-templ-param "Named parameter" function for setting
     1062    ///the map that indicates which nodes are processed.
    10611063    template<class T>
    10621064    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12091211    ///
    12101212    /// The type of the map that indicates which nodes are reached.
    1211     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1213    /// It must conform to the
     1214    /// \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12121215    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12131216
     
    12471250  /// does not observe the DFS events. If you want to observe the DFS
    12481251  /// events, you should implement your own visitor class.
    1249   /// \tparam TR Traits class to set various data types used by the
    1250   /// algorithm. The default traits class is
    1251   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
    1252   /// See \ref DfsVisitDefaultTraits for the documentation of
    1253   /// a DFS visit traits class.
     1252  /// \tparam TR The traits class that defines various types used by the
     1253  /// algorithm. By default, it is \ref DfsVisitDefaultTraits
     1254  /// "DfsVisitDefaultTraits<GR>".
     1255  /// In most cases, this parameter should not be set directly,
     1256  /// consider to use the named template parameters instead.
    12541257#ifdef DOXYGEN
    12551258  template <typename GR, typename VS, typename TR>
     
    13701373    /// The simplest way to execute the DFS algorithm is to use one of the
    13711374    /// member functions called \ref run(Node) "run()".\n
    1372     /// If you need more control on the execution, first you have to call
    1373     /// \ref init(), then you can add a source node with \ref addSource()
     1375    /// If you need better control on the execution, you have to call
     1376    /// \ref init() first, then you can add a source node with \ref addSource()
    13741377    /// and perform the actual computation with \ref start().
    13751378    /// This procedure can be repeated if there are nodes that have not
     
    15841587    /// \brief Runs the algorithm to visit all nodes in the digraph.
    15851588
    1586     /// This method runs the %DFS algorithm in order to
    1587     /// compute the %DFS path to each node.
    1588     ///
    1589     /// The algorithm computes
    1590     /// - the %DFS tree (forest),
    1591     /// - the distance of each node from the root(s) in the %DFS tree.
     1589    /// This method runs the %DFS algorithm in order to visit all nodes
     1590    /// in the digraph.
    15921591    ///
    15931592    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
     
    16211620    ///@{
    16221621
    1623     /// \brief Checks if a node is reached from the root(s).
     1622    /// \brief Checks if the given node is reached from the root(s).
    16241623    ///
    16251624    /// Returns \c true if \c v is reached from the root(s).
  • lemon/graph_to_eps.h

    r937 r942  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    143143  ///\param gr  Reference to the graph to be printed.
    144144  ///\param ost Reference to the output stream.
    145   ///By default it is <tt>std::cout</tt>.
     145  ///By default, it is <tt>std::cout</tt>.
    146146  ///\param pros If it is \c true, then the \c ostream referenced by \c os
    147147  ///will be explicitly deallocated by the destructor.
     
    513513  ///Turn on/off pre-scaling
    514514
    515   ///By default graphToEps() rescales the whole image in order to avoid
     515  ///By default, graphToEps() rescales the whole image in order to avoid
    516516  ///very big or very small bounding boxes.
    517517  ///
     
    11151115///\param g Reference to the graph to be printed.
    11161116///\param os Reference to the output stream.
    1117 ///By default it is <tt>std::cout</tt>.
     1117///By default, it is <tt>std::cout</tt>.
    11181118///
    11191119///This function also has a lot of
     
    11271127///\endcode
    11281128///
    1129 ///For more detailed examples see the \ref graph_to_eps_demo.cc demo file.
     1129///For more detailed examples, see the \ref graph_to_eps_demo.cc demo file.
    11301130///
    11311131///\warning Don't forget to put the \ref GraphToEps::run() "run()"
  • lemon/lgf_reader.h

    r877 r942  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     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/lgf_reader.h

    r937 r942  
    428428  ///\endcode
    429429  ///
    430   /// By default the reader uses the first section in the file of the
     430  /// By default, the reader uses the first section in the file of the
    431431  /// proper type. If a section has an optional name, then it can be
    432432  /// selected for reading by giving an optional name parameter to the
     
    563563    friend DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is);
    564564    template <typename TDGR>
    565     friend DigraphReader<TDGR> digraphReader(TDGR& digraph, 
     565    friend DigraphReader<TDGR> digraphReader(TDGR& digraph,
    566566                                             const std::string& fn);
    567567    template <typename TDGR>
     
    11951195
    11961196  };
    1197  
     1197
    11981198  /// \ingroup lemon_io
    11991199  ///
     
    12021202  /// This function just returns a \ref DigraphReader class.
    12031203  ///
    1204   /// With this function a digraph can be read from an 
     1204  /// With this function a digraph can be read from an
    12051205  /// \ref lgf-format "LGF" file or input stream with several maps and
    12061206  /// attributes. For example, there is network flow problem on a
     
    12571257  template <typename GR>
    12581258  class GraphReader;
    1259  
     1259
    12601260  template <typename TGR>
    12611261  GraphReader<TGR> graphReader(TGR& graph, std::istream& is = std::cin);
     
    13941394    friend GraphReader<TGR> graphReader(TGR& graph, std::istream& is);
    13951395    template <typename TGR>
    1396     friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn); 
     1396    friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
    13971397    template <typename TGR>
    13981398    friend GraphReader<TGR> graphReader(TGR& graph, const char *fn);
     
    20782078  /// \brief Return a \ref GraphReader class
    20792079  ///
    2080   /// This function just returns a \ref GraphReader class. 
    2081   ///
    2082   /// With this function a graph can be read from an 
     2080  /// This function just returns a \ref GraphReader class.
     2081  ///
     2082  /// With this function a graph can be read from an
    20832083  /// \ref lgf-format "LGF" file or input stream with several maps and
    20842084  /// attributes. For example, there is weighted matching problem on a
     
    22362236    /// whitespaces are trimmed from each processed string.
    22372237    ///
    2238     /// For example let's see a section, which contain several
     2238    /// For example, let's see a section, which contain several
    22392239    /// integers, which should be inserted into a vector.
    22402240    ///\code
  • lemon/lp_base.h

    r877 r933  
    16191619  inline LpBase::Constr operator<=(const LpBase::Expr &e,
    16201620                                   const LpBase::Expr &f) {
    1621     return LpBase::Constr(0, f - e, LpBase::INF);
     1621    return LpBase::Constr(0, f - e, LpBase::NaN);
    16221622  }
    16231623
     
    16371637  inline LpBase::Constr operator<=(const LpBase::Expr &e,
    16381638                                   const LpBase::Value &f) {
    1639     return LpBase::Constr(- LpBase::INF, e, f);
     1639    return LpBase::Constr(LpBase::NaN, e, f);
    16401640  }
    16411641
     
    16461646  inline LpBase::Constr operator>=(const LpBase::Expr &e,
    16471647                                   const LpBase::Expr &f) {
    1648     return LpBase::Constr(0, e - f, LpBase::INF);
     1648    return LpBase::Constr(0, e - f, LpBase::NaN);
    16491649  }
    16501650
     
    16661666  inline LpBase::Constr operator>=(const LpBase::Expr &e,
    16671667                                   const LpBase::Value &f) {
    1668     return LpBase::Constr(f, e, LpBase::INF);
     1668    return LpBase::Constr(f, e, LpBase::NaN);
    16691669  }
    16701670
  • lemon/lp_base.h

    r932 r933  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8383      MESSAGE_VERBOSE
    8484    };
    85    
     85
    8686
    8787    ///The floating point type used by the solver
     
    115115      typedef True LpCol;
    116116      /// Default constructor
    117      
     117
    118118      /// \warning The default constructor sets the Col to an
    119119      /// undefined value.
    120120      Col() {}
    121121      /// Invalid constructor \& conversion.
    122      
     122
    123123      /// This constructor initializes the Col to be invalid.
    124       /// \sa Invalid for more details.     
     124      /// \sa Invalid for more details.
    125125      Col(const Invalid&) : _id(-1) {}
    126126      /// Equality operator
     
    147147    ///Iterator for iterate over the columns of an LP problem
    148148
    149     /// Its usage is quite simple, for example you can count the number
     149    /// Its usage is quite simple, for example, you can count the number
    150150    /// of columns in an LP \c lp:
    151151    ///\code
     
    157157    public:
    158158      /// Default constructor
    159      
     159
    160160      /// \warning The default constructor sets the iterator
    161161      /// to an undefined value.
    162162      ColIt() {}
    163163      /// Sets the iterator to the first Col
    164      
     164
    165165      /// Sets the iterator to the first Col.
    166166      ///
     
    170170      }
    171171      /// Invalid constructor \& conversion
    172      
     172
    173173      /// Initialize the iterator to be invalid.
    174174      /// \sa Invalid for more details.
    175175      ColIt(const Invalid&) : Col(INVALID) {}
    176176      /// Next column
    177      
     177
    178178      /// Assign the iterator to the next column.
    179179      ///
     
    210210      typedef True LpRow;
    211211      /// Default constructor
    212      
     212
    213213      /// \warning The default constructor sets the Row to an
    214214      /// undefined value.
    215215      Row() {}
    216216      /// Invalid constructor \& conversion.
    217      
     217
    218218      /// This constructor initializes the Row to be invalid.
    219       /// \sa Invalid for more details.     
     219      /// \sa Invalid for more details.
    220220      Row(const Invalid&) : _id(-1) {}
    221221      /// Equality operator
     
    225225      bool operator==(Row r) const  {return _id == r._id;}
    226226      /// Inequality operator
    227      
     227
    228228      /// \sa operator==(Row r)
    229229      ///
     
    242242    ///Iterator for iterate over the rows of an LP problem
    243243
    244     /// Its usage is quite simple, for example you can count the number
     244    /// Its usage is quite simple, for example, you can count the number
    245245    /// of rows in an LP \c lp:
    246246    ///\code
     
    252252    public:
    253253      /// Default constructor
    254      
     254
    255255      /// \warning The default constructor sets the iterator
    256256      /// to an undefined value.
    257257      RowIt() {}
    258258      /// Sets the iterator to the first Row
    259      
     259
    260260      /// Sets the iterator to the first Row.
    261261      ///
     
    265265      }
    266266      /// Invalid constructor \& conversion
    267      
     267
    268268      /// Initialize the iterator to be invalid.
    269269      /// \sa Invalid for more details.
    270270      RowIt(const Invalid&) : Row(INVALID) {}
    271271      /// Next row
    272      
     272
    273273      /// Assign the iterator to the next row.
    274274      ///
     
    348348      typedef True SolverExpr;
    349349      /// Default constructor
    350      
     350
    351351      /// Construct an empty expression, the coefficients and
    352352      /// the constant component are initialized to zero.
     
    449449
    450450      ///Iterator over the expression
    451      
    452       ///The iterator iterates over the terms of the expression. 
    453       /// 
     451
     452      ///The iterator iterates over the terms of the expression.
     453      ///
    454454      ///\code
    455455      ///double s=0;
     
    465465
    466466        /// Sets the iterator to the first term
    467        
     467
    468468        /// Sets the iterator to the first term of the expression.
    469469        ///
     
    482482        const Value& operator*() const { return _it->second; }
    483483        /// Next term
    484        
     484
    485485        /// Assign the iterator to the next term.
    486486        ///
     
    494494
    495495      /// Const iterator over the expression
    496      
    497       ///The iterator iterates over the terms of the expression. 
    498       /// 
     496
     497      ///The iterator iterates over the terms of the expression.
     498      ///
    499499      ///\code
    500500      ///double s=0;
     
    510510
    511511        /// Sets the iterator to the first term
    512        
     512
    513513        /// Sets the iterator to the first term of the expression.
    514514        ///
     
    525525
    526526        /// Next term
    527        
     527
    528528        /// Assign the iterator to the next term.
    529529        ///
     
    674674      typedef True SolverExpr;
    675675      /// Default constructor
    676      
     676
    677677      /// Construct an empty expression, the coefficients are
    678678      /// initialized to zero.
     
    709709      }
    710710      /// \brief Removes the coefficients which's absolute value does
    711       /// not exceed \c epsilon. 
     711      /// not exceed \c epsilon.
    712712      void simplify(Value epsilon = 0.0) {
    713713        std::map<int, Value>::iterator it=comps.begin();
     
    758758
    759759      ///Iterator over the expression
    760      
    761       ///The iterator iterates over the terms of the expression. 
    762       /// 
     760
     761      ///The iterator iterates over the terms of the expression.
     762      ///
    763763      ///\code
    764764      ///double s=0;
     
    774774
    775775        /// Sets the iterator to the first term
    776        
     776
    777777        /// Sets the iterator to the first term of the expression.
    778778        ///
     
    792792
    793793        /// Next term
    794        
     794
    795795        /// Assign the iterator to the next term.
    796796        ///
     
    804804
    805805      ///Iterator over the expression
    806      
    807       ///The iterator iterates over the terms of the expression. 
    808       /// 
     806
     807      ///The iterator iterates over the terms of the expression.
     808      ///
    809809      ///\code
    810810      ///double s=0;
     
    820820
    821821        /// Sets the iterator to the first term
    822        
     822
    823823        /// Sets the iterator to the first term of the expression.
    824824        ///
     
    835835
    836836        /// Next term
    837        
     837
    838838        /// Assign the iterator to the next term.
    839839        ///
     
    943943    virtual int _addCol() = 0;
    944944    virtual int _addRow() = 0;
     945
     946    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
     947      int row = _addRow();
     948      _setRowCoeffs(row, b, e);
     949      _setRowLowerBound(row, l);
     950      _setRowUpperBound(row, u);
     951      return row;
     952    }
    945953
    946954    virtual void _eraseCol(int col) = 0;
     
    12081216    ///\return The created row.
    12091217    Row addRow(Value l,const Expr &e, Value u) {
    1210       Row r=addRow();
    1211       row(r,l,e,u);
     1218      Row r;
     1219      e.simplify();
     1220      r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols),
     1221                                ExprIterator(e.comps.end(), cols), u - *e));
    12121222      return r;
    12131223    }
     
    12181228    ///\return The created row.
    12191229    Row addRow(const Constr &c) {
    1220       Row r=addRow();
    1221       row(r,c);
     1230      Row r;
     1231      c.expr().simplify();
     1232      r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF,
     1233                                ExprIterator(c.expr().comps.begin(), cols),
     1234                                ExprIterator(c.expr().comps.end(), cols),
     1235                                c.upperBounded()?c.upperBound()-*c.expr():INF));
    12221236      return r;
    12231237    }
     
    18041818    enum VarStatus {
    18051819      /// The variable is in the basis
    1806       BASIC, 
     1820      BASIC,
    18071821      /// The variable is free, but not basic
    18081822      FREE,
    1809       /// The variable has active lower bound 
     1823      /// The variable has active lower bound
    18101824      LOWER,
    18111825      /// The variable has active upper bound
     
    18861900    }
    18871901    /// Returns a component of the primal ray
    1888    
     1902
    18891903    /// The primal ray is solution of the modified primal problem,
    18901904    /// where we change each finite bound to 0, and we looking for a
     
    19201934
    19211935    /// Returns a component of the dual ray
    1922    
     1936
    19231937    /// The dual ray is solution of the modified primal problem, where
    19241938    /// we change each finite bound to 0 (i.e. the objective function
     
    20622076    }
    20632077    ///The value of the objective function
    2064    
     2078
    20652079    ///\return
    20662080    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
  • lemon/network_simplex.h

    r877 r892  
    10781078        ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;
    10791079      } else {
    1080         ART_COST = std::numeric_limits<Cost>::min();
     1080        ART_COST = 0;
    10811081        for (int i = 0; i != _arc_num; ++i) {
    10821082          if (_cost[i] > ART_COST) ART_COST = _cost[i];
     
    15901590      if (_sum_supply == 0) {
    15911591        if (_stype == GEQ) {
    1592           Cost max_pot = std::numeric_limits<Cost>::min();
     1592          Cost max_pot = -std::numeric_limits<Cost>::max();
    15931593          for (int i = 0; i != _node_num; ++i) {
    15941594            if (_pi[i] > max_pot) max_pot = _pi[i];
  • lemon/network_simplex.h

    r891 r892  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4141  ///
    4242  /// \ref NetworkSimplex implements the primal Network Simplex algorithm
    43   /// for finding a \ref min_cost_flow "minimum cost flow".
    44   /// This algorithm is a specialized version of the linear programming
    45   /// simplex method directly for the minimum cost flow problem.
    46   /// It is one of the most efficient solution methods.
     43  /// for finding a \ref min_cost_flow "minimum cost flow"
     44  /// \ref amo93networkflows, \ref dantzig63linearprog,
     45  /// \ref kellyoneill91netsimplex.
     46  /// This algorithm is a highly efficient specialized version of the
     47  /// linear programming simplex method directly for the minimum cost
     48  /// flow problem.
    4749  ///
    48   /// In general this class is the fastest implementation available
    49   /// in LEMON for the minimum cost flow problem.
    50   /// Moreover it supports both directions of the supply/demand inequality
    51   /// constraints. For more information see \ref SupplyType.
     50  /// In general, %NetworkSimplex is the fastest implementation available
     51  /// in LEMON for this problem.
     52  /// Moreover, it supports both directions of the supply/demand inequality
     53  /// constraints. For more information, see \ref SupplyType.
    5254  ///
    5355  /// Most of the parameters of the problem (except for the digraph)
     
    5759  ///
    5860  /// \tparam GR The digraph type the algorithm runs on.
    59   /// \tparam V The value type used for flow amounts, capacity bounds
    60   /// and supply values in the algorithm. By default it is \c int.
    61   /// \tparam C The value type used for costs and potentials in the
    62   /// algorithm. By default it is the same as \c V.
     61  /// \tparam V The number type used for flow amounts, capacity bounds
     62  /// and supply values in the algorithm. By default, it is \c int.
     63  /// \tparam C The number type used for costs and potentials in the
     64  /// algorithm. By default, it is the same as \c V.
    6365  ///
    64   /// \warning Both value types must be signed and all input data must
     66  /// \warning Both number types must be signed and all input data must
    6567  /// be integer.
    6668  ///
    6769  /// \note %NetworkSimplex provides five different pivot rule
    6870  /// implementations, from which the most efficient one is used
    69   /// by default. For more information see \ref PivotRule.
     71  /// by default. For more information, see \ref PivotRule.
    7072  template <typename GR, typename V = int, typename C = V>
    7173  class NetworkSimplex
     
    9698      UNBOUNDED
    9799    };
    98    
     100
    99101    /// \brief Constants for selecting the type of the supply constraints.
    100102    ///
     
    114116      LEQ
    115117    };
    116    
     118
    117119    /// \brief Constants for selecting the pivot rule.
    118120    ///
     
    123125    /// implementations that significantly affect the running time
    124126    /// of the algorithm.
    125     /// By default \ref BLOCK_SEARCH "Block Search" is used, which
     127    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
    126128    /// proved to be the most efficient and the most robust on various
    127     /// test inputs according to our benchmark tests.
    128     /// However another pivot rule can be selected using the \ref run()
     129    /// test inputs.
     130    /// However, another pivot rule can be selected using the \ref run()
    129131    /// function with the proper parameter.
    130132    enum PivotRule {
    131133
    132       /// The First Eligible pivot rule.
     134      /// The \e First \e Eligible pivot rule.
    133135      /// The next eligible arc is selected in a wraparound fashion
    134136      /// in every iteration.
    135137      FIRST_ELIGIBLE,
    136138
    137       /// The Best Eligible pivot rule.
     139      /// The \e Best \e Eligible pivot rule.
    138140      /// The best eligible arc is selected in every iteration.
    139141      BEST_ELIGIBLE,
    140142
    141       /// The Block Search pivot rule.
     143      /// The \e Block \e Search pivot rule.
    142144      /// A specified number of arcs are examined in every iteration
    143145      /// in a wraparound fashion and the best eligible arc is selected
     
    145147      BLOCK_SEARCH,
    146148
    147       /// The Candidate List pivot rule.
     149      /// The \e Candidate \e List pivot rule.
    148150      /// In a major iteration a candidate list is built from eligible arcs
    149151      /// in a wraparound fashion and in the following minor iterations
     
    151153      CANDIDATE_LIST,
    152154
    153       /// The Altering Candidate List pivot rule.
     155      /// The \e Altering \e Candidate \e List pivot rule.
    154156      /// It is a modified version of the Candidate List method.
    155157      /// It keeps only the several best eligible arcs from the former
     
    157159      ALTERING_LIST
    158160    };
    159    
     161
    160162  private:
    161163
    162164    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    163165
    164     typedef std::vector<Arc> ArcVector;
    165     typedef std::vector<Node> NodeVector;
    166166    typedef std::vector<int> IntVector;
    167     typedef std::vector<bool> BoolVector;
    168167    typedef std::vector<Value> ValueVector;
    169168    typedef std::vector<Cost> CostVector;
     169    typedef std::vector<char> BoolVector;
     170    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    170171
    171172    // State constants for arcs
    172     enum ArcStateEnum {
     173    enum ArcState {
    173174      STATE_UPPER = -1,
    174175      STATE_TREE  =  0,
    175176      STATE_LOWER =  1
    176177    };
     178
     179    typedef std::vector<signed char> StateVector;
     180    // Note: vector<signed char> is used instead of vector<ArcState> for
     181    // efficiency reasons
    177182
    178183  private:
     
    195200    IntVector _source;
    196201    IntVector _target;
     202    bool _arc_mixing;
    197203
    198204    // Node and arc data
     
    214220    IntVector _dirty_revs;
    215221    BoolVector _forward;
    216     IntVector _state;
     222    StateVector _state;
    217223    int _root;
    218224
     
    223229    Value delta;
    224230
     231    const Value MAX;
     232
    225233  public:
    226  
     234
    227235    /// \brief Constant for infinite upper bounds (capacities).
    228236    ///
     
    243251      const IntVector  &_target;
    244252      const CostVector &_cost;
    245       const IntVector &_state;
     253      const StateVector &_state;
    246254      const CostVector &_pi;
    247255      int &_in_arc;
     
    264272      bool findEnteringArc() {
    265273        Cost c;
    266         for (int e = _next_arc; e < _search_arc_num; ++e) {
     274        for (int e = _next_arc; e != _search_arc_num; ++e) {
    267275          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    268276          if (c < 0) {
     
    272280          }
    273281        }
    274         for (int e = 0; e < _next_arc; ++e) {
     282        for (int e = 0; e != _next_arc; ++e) {
    275283          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    276284          if (c < 0) {
     
    295303      const IntVector  &_target;
    296304      const CostVector &_cost;
    297       const IntVector &_state;
     305      const StateVector &_state;
    298306      const CostVector &_pi;
    299307      int &_in_arc;
     
    312320      bool findEnteringArc() {
    313321        Cost c, min = 0;
    314         for (int e = 0; e < _search_arc_num; ++e) {
     322        for (int e = 0; e != _search_arc_num; ++e) {
    315323          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    316324          if (c < min) {
     
    334342      const IntVector  &_target;
    335343      const CostVector &_cost;
    336       const IntVector &_state;
     344      const StateVector &_state;
    337345      const CostVector &_pi;
    338346      int &_in_arc;
     
    353361      {
    354362        // The main parameters of the pivot rule
    355         const double BLOCK_SIZE_FACTOR = 0.5;
     363        const double BLOCK_SIZE_FACTOR = 1.0;
    356364        const int MIN_BLOCK_SIZE = 10;
    357365
     
    365373        Cost c, min = 0;
    366374        int cnt = _block_size;
    367         int e, min_arc = _next_arc;
    368         for (e = _next_arc; e < _search_arc_num; ++e) {
     375        int e;
     376        for (e = _next_arc; e != _search_arc_num; ++e) {
    369377          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    370378          if (c < min) {
    371379            min = c;
    372             min_arc = e;
     380            _in_arc = e;
    373381          }
    374382          if (--cnt == 0) {
    375             if (min < 0) break;
     383            if (min < 0) goto search_end;
    376384            cnt = _block_size;
    377385          }
    378386        }
    379         if (min == 0 || cnt > 0) {
    380           for (e = 0; e < _next_arc; ++e) {
    381             c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    382             if (c < min) {
    383               min = c;
    384               min_arc = e;
    385             }
    386             if (--cnt == 0) {
    387               if (min < 0) break;
    388               cnt = _block_size;
    389             }
     387        for (e = 0; e != _next_arc; ++e) {
     388          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     389          if (c < min) {
     390            min = c;
     391            _in_arc = e;
     392          }
     393          if (--cnt == 0) {
     394            if (min < 0) goto search_end;
     395            cnt = _block_size;
    390396          }
    391397        }
    392398        if (min >= 0) return false;
    393         _in_arc = min_arc;
     399
     400      search_end:
    394401        _next_arc = e;
    395402        return true;
     
    408415      const IntVector  &_target;
    409416      const CostVector &_cost;
    410       const IntVector &_state;
     417      const StateVector &_state;
    411418      const CostVector &_pi;
    412419      int &_in_arc;
     
    429436      {
    430437        // The main parameters of the pivot rule
    431         const double LIST_LENGTH_FACTOR = 1.0;
     438        const double LIST_LENGTH_FACTOR = 0.25;
    432439        const int MIN_LIST_LENGTH = 10;
    433440        const double MINOR_LIMIT_FACTOR = 0.1;
     
    446453      bool findEnteringArc() {
    447454        Cost min, c;
    448         int e, min_arc = _next_arc;
     455        int e;
    449456        if (_curr_length > 0 && _minor_count < _minor_limit) {
    450457          // Minor iteration: select the best eligible arc from the
     
    457464            if (c < min) {
    458465              min = c;
    459               min_arc = e;
     466              _in_arc = e;
    460467            }
    461             if (c >= 0) {
     468            else if (c >= 0) {
    462469              _candidates[i--] = _candidates[--_curr_length];
    463470            }
    464471          }
    465           if (min < 0) {
    466             _in_arc = min_arc;
    467             return true;
    468           }
     472          if (min < 0) return true;
    469473        }
    470474
     
    472476        min = 0;
    473477        _curr_length = 0;
    474         for (e = _next_arc; e < _search_arc_num; ++e) {
     478        for (e = _next_arc; e != _search_arc_num; ++e) {
    475479          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    476480          if (c < 0) {
     
    478482            if (c < min) {
    479483              min = c;
    480               min_arc = e;
     484              _in_arc = e;
    481485            }
    482             if (_curr_length == _list_length) break;
    483           }
    484         }
    485         if (_curr_length < _list_length) {
    486           for (e = 0; e < _next_arc; ++e) {
    487             c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    488             if (c < 0) {
    489               _candidates[_curr_length++] = e;
    490               if (c < min) {
    491                 min = c;
    492                 min_arc = e;
    493               }
    494               if (_curr_length == _list_length) break;
     486            if (_curr_length == _list_length) goto search_end;
     487          }
     488        }
     489        for (e = 0; e != _next_arc; ++e) {
     490          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     491          if (c < 0) {
     492            _candidates[_curr_length++] = e;
     493            if (c < min) {
     494              min = c;
     495              _in_arc = e;
    495496            }
     497            if (_curr_length == _list_length) goto search_end;
    496498          }
    497499        }
    498500        if (_curr_length == 0) return false;
     501
     502      search_end:
    499503        _minor_count = 1;
    500         _in_arc = min_arc;
    501504        _next_arc = e;
    502505        return true;
     
    515518      const IntVector  &_target;
    516519      const CostVector &_cost;
    517       const IntVector &_state;
     520      const StateVector &_state;
    518521      const CostVector &_pi;
    519522      int &_in_arc;
     
    550553      {
    551554        // The main parameters of the pivot rule
    552         const double BLOCK_SIZE_FACTOR = 1.5;
     555        const double BLOCK_SIZE_FACTOR = 1.0;
    553556        const int MIN_BLOCK_SIZE = 10;
    554557        const double HEAD_LENGTH_FACTOR = 0.1;
     
    568571        // Check the current candidate list
    569572        int e;
    570         for (int i = 0; i < _curr_length; ++i) {
     573        for (int i = 0; i != _curr_length; ++i) {
    571574          e = _candidates[i];
    572575          _cand_cost[e] = _state[e] *
     
    579582        // Extend the list
    580583        int cnt = _block_size;
    581         int last_arc = 0;
    582584        int limit = _head_length;
    583585
    584         for (int e = _next_arc; e < _search_arc_num; ++e) {
     586        for (e = _next_arc; e != _search_arc_num; ++e) {
    585587          _cand_cost[e] = _state[e] *
    586588            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    587589          if (_cand_cost[e] < 0) {
    588590            _candidates[_curr_length++] = e;
    589             last_arc = e;
    590591          }
    591592          if (--cnt == 0) {
    592             if (_curr_length > limit) break;
     593            if (_curr_length > limit) goto search_end;
    593594            limit = 0;
    594595            cnt = _block_size;
    595596          }
    596597        }
    597         if (_curr_length <= limit) {
    598           for (int e = 0; e < _next_arc; ++e) {
    599             _cand_cost[e] = _state[e] *
    600               (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    601             if (_cand_cost[e] < 0) {
    602               _candidates[_curr_length++] = e;
    603               last_arc = e;
    604             }
    605             if (--cnt == 0) {
    606               if (_curr_length > limit) break;
    607               limit = 0;
    608               cnt = _block_size;
    609             }
     598        for (e = 0; e != _next_arc; ++e) {
     599          _cand_cost[e] = _state[e] *
     600            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     601          if (_cand_cost[e] < 0) {
     602            _candidates[_curr_length++] = e;
     603          }
     604          if (--cnt == 0) {
     605            if (_curr_length > limit) goto search_end;
     606            limit = 0;
     607            cnt = _block_size;
    610608          }
    611609        }
    612610        if (_curr_length == 0) return false;
    613         _next_arc = last_arc + 1;
     611
     612      search_end:
    614613
    615614        // Make heap of the candidate list (approximating a partial sort)
     
    619618        // Pop the first element of the heap
    620619        _in_arc = _candidates[0];
     620        _next_arc = e;
    621621        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    622622                  _sort_func );
     
    634634    ///
    635635    /// \param graph The digraph the algorithm runs on.
    636     NetworkSimplex(const GR& graph) :
     636    /// \param arc_mixing Indicate if the arcs have to be stored in a
     637    /// mixed order in the internal data structure.
     638    /// In special cases, it could lead to better overall performance,
     639    /// but it is usually slower. Therefore it is disabled by default.
     640    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
    637641      _graph(graph), _node_id(graph), _arc_id(graph),
     642      _arc_mixing(arc_mixing),
     643      MAX(std::numeric_limits<Value>::max()),
    638644      INF(std::numeric_limits<Value>::has_infinity ?
    639           std::numeric_limits<Value>::infinity() :
    640           std::numeric_limits<Value>::max())
     645          std::numeric_limits<Value>::infinity() : MAX)
    641646    {
    642       // Check the value types
     647      // Check the number types
    643648      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
    644649        "The flow type of NetworkSimplex must be signed");
    645650      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
    646651        "The cost type of NetworkSimplex must be signed");
    647        
     652
     653      // Reset data structures
     654      reset();
     655    }
     656
     657    /// \name Parameters
     658    /// The parameters of the algorithm can be specified using these
     659    /// functions.
     660
     661    /// @{
     662
     663    /// \brief Set the lower bounds on the arcs.
     664    ///
     665    /// This function sets the lower bounds on the arcs.
     666    /// If it is not used before calling \ref run(), the lower bounds
     667    /// will be set to zero on all arcs.
     668    ///
     669    /// \param map An arc map storing the lower bounds.
     670    /// Its \c Value type must be convertible to the \c Value type
     671    /// of the algorithm.
     672    ///
     673    /// \return <tt>(*this)</tt>
     674    template <typename LowerMap>
     675    NetworkSimplex& lowerMap(const LowerMap& map) {
     676      _have_lower = true;
     677      for (ArcIt a(_graph); a != INVALID; ++a) {
     678        _lower[_arc_id[a]] = map[a];
     679      }
     680      return *this;
     681    }
     682
     683    /// \brief Set the upper bounds (capacities) on the arcs.
     684    ///
     685    /// This function sets the upper bounds (capacities) on the arcs.
     686    /// If it is not used before calling \ref run(), the upper bounds
     687    /// will be set to \ref INF on all arcs (i.e. the flow value will be
     688    /// unbounded from above).
     689    ///
     690    /// \param map An arc map storing the upper bounds.
     691    /// Its \c Value type must be convertible to the \c Value type
     692    /// of the algorithm.
     693    ///
     694    /// \return <tt>(*this)</tt>
     695    template<typename UpperMap>
     696    NetworkSimplex& upperMap(const UpperMap& map) {
     697      for (ArcIt a(_graph); a != INVALID; ++a) {
     698        _upper[_arc_id[a]] = map[a];
     699      }
     700      return *this;
     701    }
     702
     703    /// \brief Set the costs of the arcs.
     704    ///
     705    /// This function sets the costs of the arcs.
     706    /// If it is not used before calling \ref run(), the costs
     707    /// will be set to \c 1 on all arcs.
     708    ///
     709    /// \param map An arc map storing the costs.
     710    /// Its \c Value type must be convertible to the \c Cost type
     711    /// of the algorithm.
     712    ///
     713    /// \return <tt>(*this)</tt>
     714    template<typename CostMap>
     715    NetworkSimplex& costMap(const CostMap& map) {
     716      for (ArcIt a(_graph); a != INVALID; ++a) {
     717        _cost[_arc_id[a]] = map[a];
     718      }
     719      return *this;
     720    }
     721
     722    /// \brief Set the supply values of the nodes.
     723    ///
     724    /// This function sets the supply values of the nodes.
     725    /// If neither this function nor \ref stSupply() is used before
     726    /// calling \ref run(), the supply of each node will be set to zero.
     727    ///
     728    /// \param map A node map storing the supply values.
     729    /// Its \c Value type must be convertible to the \c Value type
     730    /// of the algorithm.
     731    ///
     732    /// \return <tt>(*this)</tt>
     733    template<typename SupplyMap>
     734    NetworkSimplex& supplyMap(const SupplyMap& map) {
     735      for (NodeIt n(_graph); n != INVALID; ++n) {
     736        _supply[_node_id[n]] = map[n];
     737      }
     738      return *this;
     739    }
     740
     741    /// \brief Set single source and target nodes and a supply value.
     742    ///
     743    /// This function sets a single source node and a single target node
     744    /// and the required flow value.
     745    /// If neither this function nor \ref supplyMap() is used before
     746    /// calling \ref run(), the supply of each node will be set to zero.
     747    ///
     748    /// Using this function has the same effect as using \ref supplyMap()
     749    /// with such a map in which \c k is assigned to \c s, \c -k is
     750    /// assigned to \c t and all other nodes have zero supply value.
     751    ///
     752    /// \param s The source node.
     753    /// \param t The target node.
     754    /// \param k The required amount of flow from node \c s to node \c t
     755    /// (i.e. the supply of \c s and the demand of \c t).
     756    ///
     757    /// \return <tt>(*this)</tt>
     758    NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
     759      for (int i = 0; i != _node_num; ++i) {
     760        _supply[i] = 0;
     761      }
     762      _supply[_node_id[s]] =  k;
     763      _supply[_node_id[t]] = -k;
     764      return *this;
     765    }
     766
     767    /// \brief Set the type of the supply constraints.
     768    ///
     769    /// This function sets the type of the supply/demand constraints.
     770    /// If it is not used before calling \ref run(), the \ref GEQ supply
     771    /// type will be used.
     772    ///
     773    /// For more information, see \ref SupplyType.
     774    ///
     775    /// \return <tt>(*this)</tt>
     776    NetworkSimplex& supplyType(SupplyType supply_type) {
     777      _stype = supply_type;
     778      return *this;
     779    }
     780
     781    /// @}
     782
     783    /// \name Execution Control
     784    /// The algorithm can be executed using \ref run().
     785
     786    /// @{
     787
     788    /// \brief Run the algorithm.
     789    ///
     790    /// This function runs the algorithm.
     791    /// The paramters can be specified using functions \ref lowerMap(),
     792    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
     793    /// \ref supplyType().
     794    /// For example,
     795    /// \code
     796    ///   NetworkSimplex<ListDigraph> ns(graph);
     797    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
     798    ///     .supplyMap(sup).run();
     799    /// \endcode
     800    ///
     801    /// This function can be called more than once. All the given parameters
     802    /// are kept for the next call, unless \ref resetParams() or \ref reset()
     803    /// is used, thus only the modified parameters have to be set again.
     804    /// If the underlying digraph was also modified after the construction
     805    /// of the class (or the last \ref reset() call), then the \ref reset()
     806    /// function must be called.
     807    ///
     808    /// \param pivot_rule The pivot rule that will be used during the
     809    /// algorithm. For more information, see \ref PivotRule.
     810    ///
     811    /// \return \c INFEASIBLE if no feasible flow exists,
     812    /// \n \c OPTIMAL if the problem has optimal solution
     813    /// (i.e. it is feasible and bounded), and the algorithm has found
     814    /// optimal flow and node potentials (primal and dual solutions),
     815    /// \n \c UNBOUNDED if the objective function of the problem is
     816    /// unbounded, i.e. there is a directed cycle having negative total
     817    /// cost and infinite upper bound.
     818    ///
     819    /// \see ProblemType, PivotRule
     820    /// \see resetParams(), reset()
     821    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
     822      if (!init()) return INFEASIBLE;
     823      return start(pivot_rule);
     824    }
     825
     826    /// \brief Reset all the parameters that have been given before.
     827    ///
     828    /// This function resets all the paramaters that have been given
     829    /// before using functions \ref lowerMap(), \ref upperMap(),
     830    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
     831    ///
     832    /// It is useful for multiple \ref run() calls. Basically, all the given
     833    /// parameters are kept for the next \ref run() call, unless
     834    /// \ref resetParams() or \ref reset() is used.
     835    /// If the underlying digraph was also modified after the construction
     836    /// of the class or the last \ref reset() call, then the \ref reset()
     837    /// function must be used, otherwise \ref resetParams() is sufficient.
     838    ///
     839    /// For example,
     840    /// \code
     841    ///   NetworkSimplex<ListDigraph> ns(graph);
     842    ///
     843    ///   // First run
     844    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
     845    ///     .supplyMap(sup).run();
     846    ///
     847    ///   // Run again with modified cost map (resetParams() is not called,
     848    ///   // so only the cost map have to be set again)
     849    ///   cost[e] += 100;
     850    ///   ns.costMap(cost).run();
     851    ///
     852    ///   // Run again from scratch using resetParams()
     853    ///   // (the lower bounds will be set to zero on all arcs)
     854    ///   ns.resetParams();
     855    ///   ns.upperMap(capacity).costMap(cost)
     856    ///     .supplyMap(sup).run();
     857    /// \endcode
     858    ///
     859    /// \return <tt>(*this)</tt>
     860    ///
     861    /// \see reset(), run()
     862    NetworkSimplex& resetParams() {
     863      for (int i = 0; i != _node_num; ++i) {
     864        _supply[i] = 0;
     865      }
     866      for (int i = 0; i != _arc_num; ++i) {
     867        _lower[i] = 0;
     868        _upper[i] = INF;
     869        _cost[i] = 1;
     870      }
     871      _have_lower = false;
     872      _stype = GEQ;
     873      return *this;
     874    }
     875
     876    /// \brief Reset the internal data structures and all the parameters
     877    /// that have been given before.
     878    ///
     879    /// This function resets the internal data structures and all the
     880    /// paramaters that have been given before using functions \ref lowerMap(),
     881    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
     882    /// \ref supplyType().
     883    ///
     884    /// It is useful for multiple \ref run() calls. Basically, all the given
     885    /// parameters are kept for the next \ref run() call, unless
     886    /// \ref resetParams() or \ref reset() is used.
     887    /// If the underlying digraph was also modified after the construction
     888    /// of the class or the last \ref reset() call, then the \ref reset()
     889    /// function must be used, otherwise \ref resetParams() is sufficient.
     890    ///
     891    /// See \ref resetParams() for examples.
     892    ///
     893    /// \return <tt>(*this)</tt>
     894    ///
     895    /// \see resetParams(), run()
     896    NetworkSimplex& reset() {
    648897      // Resize vectors
    649898      _node_num = countNodes(_graph);
     
    672921      _state.resize(max_arc_num);
    673922
    674       // Copy the graph (store the arcs in a mixed order)
     923      // Copy the graph
    675924      int i = 0;
    676925      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    677926        _node_id[n] = i;
    678927      }
    679       int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    680       i = 0;
    681       for (ArcIt a(_graph); a != INVALID; ++a) {
    682         _arc_id[a] = i;
    683         _source[i] = _node_id[_graph.source(a)];
    684         _target[i] = _node_id[_graph.target(a)];
    685         if ((i += k) >= _arc_num) i = (i % k) + 1;
    686       }
    687      
    688       // Initialize maps
    689       for (int i = 0; i != _node_num; ++i) {
    690         _supply[i] = 0;
    691       }
    692       for (int i = 0; i != _arc_num; ++i) {
    693         _lower[i] = 0;
    694         _upper[i] = INF;
    695         _cost[i] = 1;
    696       }
    697       _have_lower = false;
    698       _stype = GEQ;
    699     }
    700 
    701     /// \name Parameters
    702     /// The parameters of the algorithm can be specified using these
    703     /// functions.
    704 
    705     /// @{
    706 
    707     /// \brief Set the lower bounds on the arcs.
    708     ///
    709     /// This function sets the lower bounds on the arcs.
    710     /// If it is not used before calling \ref run(), the lower bounds
    711     /// will be set to zero on all arcs.
    712     ///
    713     /// \param map An arc map storing the lower bounds.
    714     /// Its \c Value type must be convertible to the \c Value type
    715     /// of the algorithm.
    716     ///
    717     /// \return <tt>(*this)</tt>
    718     template <typename LowerMap>
    719     NetworkSimplex& lowerMap(const LowerMap& map) {
    720       _have_lower = true;
    721       for (ArcIt a(_graph); a != INVALID; ++a) {
    722         _lower[_arc_id[a]] = map[a];
    723       }
    724       return *this;
    725     }
    726 
    727     /// \brief Set the upper bounds (capacities) on the arcs.
    728     ///
    729     /// This function sets the upper bounds (capacities) on the arcs.
    730     /// If it is not used before calling \ref run(), the upper bounds
    731     /// will be set to \ref INF on all arcs (i.e. the flow value will be
    732     /// unbounded from above on each arc).
    733     ///
    734     /// \param map An arc map storing the upper bounds.
    735     /// Its \c Value type must be convertible to the \c Value type
    736     /// of the algorithm.
    737     ///
    738     /// \return <tt>(*this)</tt>
    739     template<typename UpperMap>
    740     NetworkSimplex& upperMap(const UpperMap& map) {
    741       for (ArcIt a(_graph); a != INVALID; ++a) {
    742         _upper[_arc_id[a]] = map[a];
    743       }
    744       return *this;
    745     }
    746 
    747     /// \brief Set the costs of the arcs.
    748     ///
    749     /// This function sets the costs of the arcs.
    750     /// If it is not used before calling \ref run(), the costs
    751     /// will be set to \c 1 on all arcs.
    752     ///
    753     /// \param map An arc map storing the costs.
    754     /// Its \c Value type must be convertible to the \c Cost type
    755     /// of the algorithm.
    756     ///
    757     /// \return <tt>(*this)</tt>
    758     template<typename CostMap>
    759     NetworkSimplex& costMap(const CostMap& map) {
    760       for (ArcIt a(_graph); a != INVALID; ++a) {
    761         _cost[_arc_id[a]] = map[a];
    762       }
    763       return *this;
    764     }
    765 
    766     /// \brief Set the supply values of the nodes.
    767     ///
    768     /// This function sets the supply values of the nodes.
    769     /// If neither this function nor \ref stSupply() is used before
    770     /// calling \ref run(), the supply of each node will be set to zero.
    771     /// (It makes sense only if non-zero lower bounds are given.)
    772     ///
    773     /// \param map A node map storing the supply values.
    774     /// Its \c Value type must be convertible to the \c Value type
    775     /// of the algorithm.
    776     ///
    777     /// \return <tt>(*this)</tt>
    778     template<typename SupplyMap>
    779     NetworkSimplex& supplyMap(const SupplyMap& map) {
    780       for (NodeIt n(_graph); n != INVALID; ++n) {
    781         _supply[_node_id[n]] = map[n];
    782       }
    783       return *this;
    784     }
    785 
    786     /// \brief Set single source and target nodes and a supply value.
    787     ///
    788     /// This function sets a single source node and a single target node
    789     /// and the required flow value.
    790     /// If neither this function nor \ref supplyMap() is used before
    791     /// calling \ref run(), the supply of each node will be set to zero.
    792     /// (It makes sense only if non-zero lower bounds are given.)
    793     ///
    794     /// Using this function has the same effect as using \ref supplyMap()
    795     /// with such a map in which \c k is assigned to \c s, \c -k is
    796     /// assigned to \c t and all other nodes have zero supply value.
    797     ///
    798     /// \param s The source node.
    799     /// \param t The target node.
    800     /// \param k The required amount of flow from node \c s to node \c t
    801     /// (i.e. the supply of \c s and the demand of \c t).
    802     ///
    803     /// \return <tt>(*this)</tt>
    804     NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
    805       for (int i = 0; i != _node_num; ++i) {
    806         _supply[i] = 0;
    807       }
    808       _supply[_node_id[s]] =  k;
    809       _supply[_node_id[t]] = -k;
    810       return *this;
    811     }
    812    
    813     /// \brief Set the type of the supply constraints.
    814     ///
    815     /// This function sets the type of the supply/demand constraints.
    816     /// If it is not used before calling \ref run(), the \ref GEQ supply
    817     /// type will be used.
    818     ///
    819     /// For more information see \ref SupplyType.
    820     ///
    821     /// \return <tt>(*this)</tt>
    822     NetworkSimplex& supplyType(SupplyType supply_type) {
    823       _stype = supply_type;
    824       return *this;
    825     }
    826 
    827     /// @}
    828 
    829     /// \name Execution Control
    830     /// The algorithm can be executed using \ref run().
    831 
    832     /// @{
    833 
    834     /// \brief Run the algorithm.
    835     ///
    836     /// This function runs the algorithm.
    837     /// The paramters can be specified using functions \ref lowerMap(),
    838     /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
    839     /// \ref supplyType().
    840     /// For example,
    841     /// \code
    842     ///   NetworkSimplex<ListDigraph> ns(graph);
    843     ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
    844     ///     .supplyMap(sup).run();
    845     /// \endcode
    846     ///
    847     /// This function can be called more than once. All the parameters
    848     /// that have been given are kept for the next call, unless
    849     /// \ref reset() is called, thus only the modified parameters
    850     /// have to be set again. See \ref reset() for examples.
    851     /// However the underlying digraph must not be modified after this
    852     /// class have been constructed, since it copies and extends the graph.
    853     ///
    854     /// \param pivot_rule The pivot rule that will be used during the
    855     /// algorithm. For more information see \ref PivotRule.
    856     ///
    857     /// \return \c INFEASIBLE if no feasible flow exists,
    858     /// \n \c OPTIMAL if the problem has optimal solution
    859     /// (i.e. it is feasible and bounded), and the algorithm has found
    860     /// optimal flow and node potentials (primal and dual solutions),
    861     /// \n \c UNBOUNDED if the objective function of the problem is
    862     /// unbounded, i.e. there is a directed cycle having negative total
    863     /// cost and infinite upper bound.
    864     ///
    865     /// \see ProblemType, PivotRule
    866     ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
    867       if (!init()) return INFEASIBLE;
    868       return start(pivot_rule);
    869     }
    870 
    871     /// \brief Reset all the parameters that have been given before.
    872     ///
    873     /// This function resets all the paramaters that have been given
    874     /// before using functions \ref lowerMap(), \ref upperMap(),
    875     /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
    876     ///
    877     /// It is useful for multiple run() calls. If this function is not
    878     /// used, all the parameters given before are kept for the next
    879     /// \ref run() call.
    880     /// However the underlying digraph must not be modified after this
    881     /// class have been constructed, since it copies and extends the graph.
    882     ///
    883     /// For example,
    884     /// \code
    885     ///   NetworkSimplex<ListDigraph> ns(graph);
    886     ///
    887     ///   // First run
    888     ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
    889     ///     .supplyMap(sup).run();
    890     ///
    891     ///   // Run again with modified cost map (reset() is not called,
    892     ///   // so only the cost map have to be set again)
    893     ///   cost[e] += 100;
    894     ///   ns.costMap(cost).run();
    895     ///
    896     ///   // Run again from scratch using reset()
    897     ///   // (the lower bounds will be set to zero on all arcs)
    898     ///   ns.reset();
    899     ///   ns.upperMap(capacity).costMap(cost)
    900     ///     .supplyMap(sup).run();
    901     /// \endcode
    902     ///
    903     /// \return <tt>(*this)</tt>
    904     NetworkSimplex& reset() {
    905       for (int i = 0; i != _node_num; ++i) {
    906         _supply[i] = 0;
    907       }
    908       for (int i = 0; i != _arc_num; ++i) {
    909         _lower[i] = 0;
    910         _upper[i] = INF;
    911         _cost[i] = 1;
    912       }
    913       _have_lower = false;
    914       _stype = GEQ;
     928      if (_arc_mixing) {
     929        // Store the arcs in a mixed order
     930        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     931        int i = 0, j = 0;
     932        for (ArcIt a(_graph); a != INVALID; ++a) {
     933          _arc_id[a] = i;
     934          _source[i] = _node_id[_graph.source(a)];
     935          _target[i] = _node_id[_graph.target(a)];
     936          if ((i += k) >= _arc_num) i = ++j;
     937        }
     938      } else {
     939        // Store the arcs in the original order
     940        int i = 0;
     941        for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
     942          _arc_id[a] = i;
     943          _source[i] = _node_id[_graph.source(a)];
     944          _target[i] = _node_id[_graph.target(a)];
     945        }
     946      }
     947
     948      // Reset parameters
     949      resetParams();
    915950      return *this;
    916951    }
     
    10251060          Value c = _lower[i];
    10261061          if (c >= 0) {
    1027             _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
     1062            _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;
    10281063          } else {
    1029             _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
     1064            _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;
    10301065          }
    10311066          _supply[_source[i]] -= c;
     
    10551090        _state[i] = STATE_LOWER;
    10561091      }
    1057      
     1092
    10581093      // Set data for the artificial root node
    10591094      _root = _node_num;
     
    12191254        e = _pred[u];
    12201255        d = _forward[u] ?
    1221           _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);
     1256          _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
    12221257        if (d < delta) {
    12231258          delta = d;
     
    12291264      for (int u = second; u != join; u = _parent[u]) {
    12301265        e = _pred[u];
    1231         d = _forward[u] ? 
    1232           (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
     1266        d = _forward[u] ?
     1267          (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
    12331268        if (d <= delta) {
    12341269          delta = d;
     
    13311366
    13321367      // Update _rev_thread using the new _thread values
    1333       for (int i = 0; i < int(_dirty_revs.size()); ++i) {
     1368      for (int i = 0; i != int(_dirty_revs.size()); ++i) {
    13341369        u = _dirty_revs[i];
    13351370        _rev_thread[_thread[u]] = u;
     
    14011436        _pi[u] += sigma;
    14021437      }
     1438    }
     1439
     1440    // Heuristic initial pivots
     1441    bool initialPivots() {
     1442      Value curr, total = 0;
     1443      std::vector<Node> supply_nodes, demand_nodes;
     1444      for (NodeIt u(_graph); u != INVALID; ++u) {
     1445        curr = _supply[_node_id[u]];
     1446        if (curr > 0) {
     1447          total += curr;
     1448          supply_nodes.push_back(u);
     1449        }
     1450        else if (curr < 0) {
     1451          demand_nodes.push_back(u);
     1452        }
     1453      }
     1454      if (_sum_supply > 0) total -= _sum_supply;
     1455      if (total <= 0) return true;
     1456
     1457      IntVector arc_vector;
     1458      if (_sum_supply >= 0) {
     1459        if (supply_nodes.size() == 1 && demand_nodes.size() == 1) {
     1460          // Perform a reverse graph search from the sink to the source
     1461          typename GR::template NodeMap<bool> reached(_graph, false);
     1462          Node s = supply_nodes[0], t = demand_nodes[0];
     1463          std::vector<Node> stack;
     1464          reached[t] = true;
     1465          stack.push_back(t);
     1466          while (!stack.empty()) {
     1467            Node u, v = stack.back();
     1468            stack.pop_back();
     1469            if (v == s) break;
     1470            for (InArcIt a(_graph, v); a != INVALID; ++a) {
     1471              if (reached[u = _graph.source(a)]) continue;
     1472              int j = _arc_id[a];
     1473              if (_cap[j] >= total) {
     1474                arc_vector.push_back(j);
     1475                reached[u] = true;
     1476                stack.push_back(u);
     1477              }
     1478            }
     1479          }
     1480        } else {
     1481          // Find the min. cost incomming arc for each demand node
     1482          for (int i = 0; i != int(demand_nodes.size()); ++i) {
     1483            Node v = demand_nodes[i];
     1484            Cost c, min_cost = std::numeric_limits<Cost>::max();
     1485            Arc min_arc = INVALID;
     1486            for (InArcIt a(_graph, v); a != INVALID; ++a) {
     1487              c = _cost[_arc_id[a]];
     1488              if (c < min_cost) {
     1489                min_cost = c;
     1490                min_arc = a;
     1491              }
     1492            }
     1493            if (min_arc != INVALID) {
     1494              arc_vector.push_back(_arc_id[min_arc]);
     1495            }
     1496          }
     1497        }
     1498      } else {
     1499        // Find the min. cost outgoing arc for each supply node
     1500        for (int i = 0; i != int(supply_nodes.size()); ++i) {
     1501          Node u = supply_nodes[i];
     1502          Cost c, min_cost = std::numeric_limits<Cost>::max();
     1503          Arc min_arc = INVALID;
     1504          for (OutArcIt a(_graph, u); a != INVALID; ++a) {
     1505            c = _cost[_arc_id[a]];
     1506            if (c < min_cost) {
     1507              min_cost = c;
     1508              min_arc = a;
     1509            }
     1510          }
     1511          if (min_arc != INVALID) {
     1512            arc_vector.push_back(_arc_id[min_arc]);
     1513          }
     1514        }
     1515      }
     1516
     1517      // Perform heuristic initial pivots
     1518      for (int i = 0; i != int(arc_vector.size()); ++i) {
     1519        in_arc = arc_vector[i];
     1520        if (_state[in_arc] * (_cost[in_arc] + _pi[_source[in_arc]] -
     1521            _pi[_target[in_arc]]) >= 0) continue;
     1522        findJoinNode();
     1523        bool change = findLeavingArc();
     1524        if (delta >= MAX) return false;
     1525        changeFlow(change);
     1526        if (change) {
     1527          updateTreeStructure();
     1528          updatePotential();
     1529        }
     1530      }
     1531      return true;
    14031532    }
    14041533
     
    14251554      PivotRuleImpl pivot(*this);
    14261555
     1556      // Perform heuristic initial pivots
     1557      if (!initialPivots()) return UNBOUNDED;
     1558
    14271559      // Execute the Network Simplex algorithm
    14281560      while (pivot.findEnteringArc()) {
    14291561        findJoinNode();
    14301562        bool change = findLeavingArc();
    1431         if (delta >= INF) return UNBOUNDED;
     1563        if (delta >= MAX) return UNBOUNDED;
    14321564        changeFlow(change);
    14331565        if (change) {
     
    14361568        }
    14371569      }
    1438      
     1570
    14391571      // Check feasibility
    14401572      for (int e = _search_arc_num; e != _all_arc_num; ++e) {
     
    14531585        }
    14541586      }
    1455      
     1587
    14561588      // Shift potentials to meet the requirements of the GEQ/LEQ type
    14571589      // optimality conditions
  • lemon/preflow.h

    r877 r942  
    544544          _flow->set(e, (*_capacity)[e]);
    545545          (*_excess)[u] += rem;
    546           if (u != _target && !_level->active(u)) {
    547             _level->activate(u);
    548           }
    549546        }
    550547      }
     
    556553          _flow->set(e, 0);
    557554          (*_excess)[v] += rem;
    558           if (v != _target && !_level->active(v)) {
    559             _level->activate(v);
    560           }
    561         }
    562       }
     555        }
     556      }
     557      for (NodeIt n(_graph); n != INVALID; ++n)
     558        if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))
     559          _level->activate(n);
     560         
    563561      return true;
    564562    }
     
    577575      _phase = true;
    578576
    579       Node n = _level->highestActive();
    580       int level = _level->highestActiveLevel();
    581       while (n != INVALID) {
     577      while (true) {
    582578        int num = _node_num;
    583579
    584         while (num > 0 && n != INVALID) {
     580        Node n = INVALID;
     581        int level = -1;
     582
     583        while (num > 0) {
     584          n = _level->highestActive();
     585          if (n == INVALID) goto first_phase_done;
     586          level = _level->highestActiveLevel();
     587          --num;
     588         
    585589          Value excess = (*_excess)[n];
    586590          int new_level = _level->maxLevel();
     
    648652            _level->deactivate(n);
    649653          }
    650 
    651           n = _level->highestActive();
    652           level = _level->highestActiveLevel();
     654        }
     655
     656        num = _node_num * 20;
     657        while (num > 0) {
     658          while (level >= 0 && _level->activeFree(level)) {
     659            --level;
     660          }
     661          if (level == -1) {
     662            n = _level->highestActive();
     663            level = _level->highestActiveLevel();
     664            if (n == INVALID) goto first_phase_done;
     665          } else {
     666            n = _level->activeOn(level);
     667          }
    653668          --num;
    654         }
    655 
    656         num = _node_num * 20;
    657         while (num > 0 && n != INVALID) {
     669
    658670          Value excess = (*_excess)[n];
    659671          int new_level = _level->maxLevel();
     
    721733            _level->deactivate(n);
    722734          }
    723 
    724           while (level >= 0 && _level->activeFree(level)) {
    725             --level;
    726           }
    727           if (level == -1) {
    728             n = _level->highestActive();
    729             level = _level->highestActiveLevel();
    730           } else {
    731             n = _level->activeOn(level);
    732           }
    733           --num;
    734         }
    735       }
     735        }
     736      }
     737    first_phase_done:;
    736738    }
    737739
  • lemon/preflow.h

    r901 r942  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    5353    /// The type of the map that stores the flow values.
    5454    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     55#ifdef DOXYGEN
     56    typedef GR::ArcMap<Value> FlowMap;
     57#else
    5558    typedef typename Digraph::template ArcMap<Value> FlowMap;
     59#endif
    5660
    5761    /// \brief Instantiates a FlowMap.
     
    6872    /// The elevator type used by Preflow algorithm.
    6973    ///
    70     /// \sa Elevator
    71     /// \sa LinkedElevator
    72     typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
     74    /// \sa Elevator, LinkedElevator
     75#ifdef DOXYGEN
     76    typedef lemon::Elevator<GR, GR::Node> Elevator;
     77#else
     78    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
     79#endif
    7380
    7481    /// \brief Instantiates an Elevator.
     
    96103  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    97104  /// \e push-relabel algorithm producing a \ref max_flow
    98   /// "flow of maximum value" in a digraph.
     105  /// "flow of maximum value" in a digraph \ref clrs01algorithms,
     106  /// \ref amo93networkflows, \ref goldberg88newapproach.
    99107  /// The preflow algorithms are the fastest known maximum
    100   /// flow algorithms. The current implementation use a mixture of the
     108  /// flow algorithms. The current implementation uses a mixture of the
    101109  /// \e "highest label" and the \e "bound decrease" heuristics.
    102110  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
     
    106114  /// second phase constructs a feasible maximum flow on each arc.
    107115  ///
     116  /// \warning This implementation cannot handle infinite or very large
     117  /// capacities (e.g. the maximum value of \c CAP::Value).
     118  ///
    108119  /// \tparam GR The type of the digraph the algorithm runs on.
    109120  /// \tparam CAP The type of the capacity map. The default map
    110121  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
     122  /// \tparam TR The traits class that defines various types used by the
     123  /// algorithm. By default, it is \ref PreflowDefaultTraits
     124  /// "PreflowDefaultTraits<GR, CAP>".
     125  /// In most cases, this parameter should not be set directly,
     126  /// consider to use the named template parameters instead.
    111127#ifdef DOXYGEN
    112128  template <typename GR, typename CAP, typename TR>
     
    258274    /// able to automatically created by the algorithm (i.e. the
    259275    /// digraph and the maximum level should be passed to it).
    260     /// However an external elevator object could also be passed to the
     276    /// However, an external elevator object could also be passed to the
    261277    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
    262278    /// before calling \ref run() or \ref init().
     
    372388    }
    373389
    374     /// \brief Sets the tolerance used by algorithm.
    375     ///
    376     /// Sets the tolerance used by algorithm.
     390    /// \brief Sets the tolerance used by the algorithm.
     391    ///
     392    /// Sets the tolerance object used by the algorithm.
     393    /// \return <tt>(*this)</tt>
    377394    Preflow& tolerance(const Tolerance& tolerance) {
    378395      _tolerance = tolerance;
     
    382399    /// \brief Returns a const reference to the tolerance.
    383400    ///
    384     /// Returns a const reference to the tolerance.
     401    /// Returns a const reference to the tolerance object used by
     402    /// the algorithm.
    385403    const Tolerance& tolerance() const {
    386404      return _tolerance;
     
    390408    /// The simplest way to execute the preflow algorithm is to use
    391409    /// \ref run() or \ref runMinCut().\n
    392     /// If you need more control on the initial solution or the execution,
    393     /// first you have to call one of the \ref init() functions, then
     410    /// If you need better control on the initial solution or the execution,
     411    /// you have to call one of the \ref init() functions first, then
    394412    /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
    395413
  • test/CMakeLists.txt

    r874 r942  
    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
     
    3034  heap_test
    3135  kruskal_test
     36  lgf_test
    3237  maps_test
    3338  matching_test
     
    4651
    4752IF(LEMON_HAVE_LP)
    48   ADD_EXECUTABLE(lp_test lp_test.cc)
     53  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     54    ADD_EXECUTABLE(lp_test lp_test.cc)
     55  ELSE()
     56    ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc)
     57  ENDIF()
     58
    4959  SET(LP_TEST_LIBS lemon)
    5060
     
    6171  TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
    6272  ADD_TEST(lp_test lp_test)
     73  ADD_DEPENDENCIES(check lp_test)
    6374
    6475  IF(WIN32 AND LEMON_HAVE_GLPK)
     
    8293
    8394IF(LEMON_HAVE_MIP)
    84   ADD_EXECUTABLE(mip_test mip_test.cc)
     95  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     96    ADD_EXECUTABLE(mip_test mip_test.cc)
     97  ELSE()
     98    ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc)
     99  ENDIF()
     100
    85101  SET(MIP_TEST_LIBS lemon)
    86102
     
    97113  TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})
    98114  ADD_TEST(mip_test mip_test)
     115  ADD_DEPENDENCIES(check mip_test)
    99116
    100117  IF(WIN32 AND LEMON_HAVE_GLPK)
     
    118135
    119136FOREACH(TEST_NAME ${TESTS})
    120   ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
     137  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     138    ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
     139  ELSE()
     140    ADD_EXECUTABLE(${TEST_NAME} EXCLUDE_FROM_ALL ${TEST_NAME}.cc)
     141  ENDIF()
    121142  TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
    122   ADD_TEST(${TEST_NAME} ${TEST_NAME})
     143    IF(TEST_WITH_VALGRIND)
     144      ADD_TEST(${TEST_NAME}
     145        valgrind --error-exitcode=1 ${VALGRIND_FLAGS}
     146        ${CMAKE_CURRENT_BINARY_DIR}/${TEST_NAME} )
     147    ELSE()
     148      ADD_TEST(${TEST_NAME} ${TEST_NAME})
     149    ENDIF()
     150  ADD_DEPENDENCIES(check ${TEST_NAME})
    123151ENDFOREACH()
  • test/CMakeLists.txt

    r937 r942  
    1414SET(TESTS
    1515  adaptors_test
     16  bellman_ford_test
    1617  bfs_test
    1718  circulation_test
     
    2526  error_test
    2627  euler_test
     28  fractional_matching_test
    2729  gomory_hu_test
    2830  graph_copy_test
     
    3739  min_cost_arborescence_test
    3840  min_cost_flow_test
     41  min_mean_cycle_test
    3942  path_test
     43  planarity_test
    4044  preflow_test
    4145  radix_sort_test
  • test/Makefile.am

    r874 r942  
    3232        test/heap_test \
    3333        test/kruskal_test \
     34        test/lgf_test \
    3435        test/maps_test \
    3536        test/matching_test \
     
    8182test_kruskal_test_SOURCES = test/kruskal_test.cc
    8283test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
     84test_lgf_test_SOURCES = test/lgf_test.cc
    8385test_lp_test_SOURCES = test/lp_test.cc
    8486test_maps_test_SOURCES = test/maps_test.cc
  • test/Makefile.am

    r937 r942  
     1if USE_VALGRIND
     2TESTS_ENVIRONMENT=$(top_srcdir)/scripts/valgrind-wrapper.sh
     3endif
     4
    15EXTRA_DIST += \
    26        test/CMakeLists.txt
     
    812check_PROGRAMS += \
    913        test/adaptors_test \
     14        test/bellman_ford_test \
    1015        test/bfs_test \
    1116        test/circulation_test \
     
    1924        test/error_test \
    2025        test/euler_test \
     26        test/fractional_matching_test \
    2127        test/gomory_hu_test \
    2228        test/graph_copy_test \
     
    3137        test/min_cost_arborescence_test \
    3238        test/min_cost_flow_test \
     39        test/min_mean_cycle_test \
    3340        test/path_test \
     41        test/planarity_test \
    3442        test/preflow_test \
    3543        test/radix_sort_test \
     
    5462
    5563test_adaptors_test_SOURCES = test/adaptors_test.cc
     64test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
    5665test_bfs_test_SOURCES = test/bfs_test.cc
    5766test_circulation_test_SOURCES = test/circulation_test.cc
     
    6574test_error_test_SOURCES = test/error_test.cc
    6675test_euler_test_SOURCES = test/euler_test.cc
     76test_fractional_matching_test_SOURCES = test/fractional_matching_test.cc
    6777test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
    6878test_graph_copy_test_SOURCES = test/graph_copy_test.cc
     
    7989test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
    8090test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
     91test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
    8192test_path_test_SOURCES = test/path_test.cc
     93test_planarity_test_SOURCES = test/planarity_test.cc
    8294test_preflow_test_SOURCES = test/preflow_test.cc
    8395test_radix_sort_test_SOURCES = test/radix_sort_test.cc
  • test/dfs_test.cc

    r877 r942  
    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/dfs_test.cc

    r937 r942  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8787    b = const_dfs_test.emptyQueue();
    8888    i = const_dfs_test.queueSize();
    89    
     89
    9090    dfs_test.start();
    9191    dfs_test.start(t);
     
    113113    concepts::ReadWriteMap<Node,bool> reached_map;
    114114    concepts::WriteMap<Node,bool> processed_map;
    115    
     115
    116116    dfs_test
    117117      .predMap(pred_map)
     
    130130    b = dfs_test.emptyQueue();
    131131    i = dfs_test.queueSize();
    132    
     132
    133133    dfs_test.start();
    134134    dfs_test.start(t);
  • test/heap_test.cc

    r855 r921  
    273273  }
    274274
     275  {
     276    typedef FibHeap<Prio, ItemIntMap> IntHeap;
     277    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     278    heapSortTest<IntHeap>();
     279    heapIncreaseTest<IntHeap>();
     280
     281    typedef FibHeap<Prio, IntNodeMap > NodeHeap;
     282    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     283    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     284  }
     285
     286  {
     287    typedef RadixHeap<ItemIntMap> IntHeap;
     288    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     289    heapSortTest<IntHeap>();
     290    heapIncreaseTest<IntHeap>();
     291
     292    typedef RadixHeap<IntNodeMap > NodeHeap;
     293    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     294    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     295  }
     296
     297  {
     298    typedef BucketHeap<ItemIntMap> IntHeap;
     299    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     300    heapSortTest<IntHeap>();
     301    heapIncreaseTest<IntHeap>();
     302
     303    typedef BucketHeap<IntNodeMap > NodeHeap;
     304    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     305    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     306  }
     307
     308
    275309  return 0;
    276310}
  • test/heap_test.cc

    r681 r921  
    2626
    2727#include <lemon/smart_graph.h>
    28 
    2928#include <lemon/lgf_reader.h>
    3029#include <lemon/dijkstra.h>
     
    3231
    3332#include <lemon/bin_heap.h>
     33#include <lemon/quad_heap.h>
     34#include <lemon/dheap.h>
    3435#include <lemon/fib_heap.h>
     36#include <lemon/pairing_heap.h>
    3537#include <lemon/radix_heap.h>
     38#include <lemon/binomial_heap.h>
    3639#include <lemon/bucket_heap.h>
    3740
     
    9093void heapSortTest() {
    9194  RangeMap<int> map(test_len, -1);
    92 
    9395  Heap heap(map);
    9496
    9597  std::vector<int> v(test_len);
    96 
    9798  for (int i = 0; i < test_len; ++i) {
    9899    v[i] = test_seq[i];
     
    101102  std::sort(v.begin(), v.end());
    102103  for (int i = 0; i < test_len; ++i) {
    103     check(v[i] == heap.prio() ,"Wrong order in heap sort.");
     104    check(v[i] == heap.prio(), "Wrong order in heap sort.");
    104105    heap.pop();
    105106  }
     
    113114
    114115  std::vector<int> v(test_len);
    115 
    116116  for (int i = 0; i < test_len; ++i) {
    117117    v[i] = test_seq[i];
     
    124124  std::sort(v.begin(), v.end());
    125125  for (int i = 0; i < test_len; ++i) {
    126     check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
     126    check(v[i] == heap.prio(), "Wrong order in heap increase test.");
    127127    heap.pop();
    128128  }
    129129}
    130 
    131 
    132130
    133131template <typename Heap>
     
    145143    if (dijkstra.reached(s)) {
    146144      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
    147              "Error in a shortest path tree!");
     145             "Error in shortest path tree.");
    148146    }
    149147  }
     
    154152      Node s = digraph.source(a);
    155153      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
    156              "Error in a shortest path tree!");
     154             "Error in shortest path tree.");
    157155    }
    158156  }
     
    176174    run();
    177175
     176  // BinHeap
    178177  {
    179178    typedef BinHeap<Prio, ItemIntMap> IntHeap;
     
    185184    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    186185    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     186  }
     187
     188  // QuadHeap
     189  {
     190    typedef QuadHeap<Prio, ItemIntMap> IntHeap;
     191    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     192    heapSortTest<IntHeap>();
     193    heapIncreaseTest<IntHeap>();
     194
     195    typedef QuadHeap<Prio, IntNodeMap > NodeHeap;
     196    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     197    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     198  }
     199
     200  // DHeap
     201  {
     202    typedef DHeap<Prio, ItemIntMap> IntHeap;
     203    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     204    heapSortTest<IntHeap>();
     205    heapIncreaseTest<IntHeap>();
     206
     207    typedef DHeap<Prio, IntNodeMap > NodeHeap;
     208    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     209    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     210  }
     211
     212  // FibHeap
     213  {
     214    typedef FibHeap<Prio, ItemIntMap> IntHeap;
     215    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     216    heapSortTest<IntHeap>();
     217    heapIncreaseTest<IntHeap>();
     218
     219    typedef FibHeap<Prio, IntNodeMap > NodeHeap;
     220    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     221    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     222  }
     223
     224  // PairingHeap
     225  {
     226    typedef PairingHeap<Prio, ItemIntMap> IntHeap;
     227    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     228    heapSortTest<IntHeap>();
     229    heapIncreaseTest<IntHeap>();
     230
     231    typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
     232    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     233    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     234  }
     235
     236  // RadixHeap
     237  {
     238    typedef RadixHeap<ItemIntMap> IntHeap;
     239    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     240    heapSortTest<IntHeap>();
     241    heapIncreaseTest<IntHeap>();
     242
     243    typedef RadixHeap<IntNodeMap > NodeHeap;
     244    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     245    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     246  }
     247
     248  // BinomialHeap
     249  {
     250    typedef BinomialHeap<Prio, ItemIntMap> IntHeap;
     251    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     252    heapSortTest<IntHeap>();
     253    heapIncreaseTest<IntHeap>();
     254
     255    typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;
     256    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     257    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     258  }
     259
     260  // BucketHeap, SimpleBucketHeap
     261  {
     262    typedef BucketHeap<ItemIntMap> IntHeap;
     263    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     264    heapSortTest<IntHeap>();
     265    heapIncreaseTest<IntHeap>();
     266
     267    typedef BucketHeap<IntNodeMap > NodeHeap;
     268    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     269    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     270
     271    typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
     272    heapSortTest<SimpleIntHeap>();
    187273  }
    188274
  • test/preflow_test.cc

    r877 r902  
    157157}
    158158
     159void initFlowTest()
     160{
     161  DIGRAPH_TYPEDEFS(SmartDigraph);
     162 
     163  SmartDigraph g;
     164  SmartDigraph::ArcMap<int> cap(g),iflow(g);
     165  Node s=g.addNode(); Node t=g.addNode();
     166  Node n1=g.addNode(); Node n2=g.addNode();
     167  Arc a;
     168  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
     169  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
     170  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
     171
     172  Preflow<SmartDigraph> pre(g,cap,s,t);
     173  pre.init(iflow);
     174  pre.startFirstPhase();
     175  check(pre.flowValue() == 10, "The incorrect max flow value.");
     176  check(pre.minCut(s), "Wrong min cut (Node s).");
     177  check(pre.minCut(n1), "Wrong min cut (Node n1).");
     178  check(!pre.minCut(n2), "Wrong min cut (Node n2).");
     179  check(!pre.minCut(t), "Wrong min cut (Node t).");
     180}
     181
     182
    159183int main() {
    160184
     
    247271        "The max flow value or the three min cut values are incorrect.");
    248272
     273  initFlowTest();
     274 
    249275  return 0;
    250276}
  • test/preflow_test.cc

    r901 r902  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9696  const PreflowType& const_preflow_test = preflow_test;
    9797
     98  const PreflowType::Elevator& elev = const_preflow_test.elevator();
     99  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
     100  PreflowType::Tolerance tol = const_preflow_test.tolerance();
     101  preflow_test.tolerance(tol);
     102
    98103  preflow_test
    99104    .capacityMap(cap)
     
    114119  b = const_preflow_test.minCut(n);
    115120  const_preflow_test.minCutMap(cut);
    116  
     121
    117122  ignore_unused_variable_warning(fm);
    118123}
Note: See TracChangeset for help on using the changeset viewer.