COIN-OR::LEMON - Graph Library

Ignore:
Files:
7 added
3 deleted
146 edited

Legend:

Unmodified
Added
Removed
  • CMakeLists.txt

    r1185 r1264  
    6262FIND_PACKAGE(Doxygen)
    6363FIND_PACKAGE(Ghostscript)
    64 FIND_PACKAGE(GLPK 4.33)
    65 FIND_PACKAGE(CPLEX)
    66 FIND_PACKAGE(COIN)
     64
     65SET(LEMON_ENABLE_GLPK YES CACHE STRING "Enable GLPK solver backend.")
     66SET(LEMON_ENABLE_ILOG YES CACHE STRING "Enable ILOG (CPLEX) solver backend.")
     67SET(LEMON_ENABLE_COIN YES CACHE STRING "Enable COIN solver backend.")
     68SET(LEMON_ENABLE_SOPLEX YES CACHE STRING "Enable SoPlex solver backend.")
     69
     70IF(LEMON_ENABLE_GLPK)
     71  FIND_PACKAGE(GLPK 4.33)
     72ENDIF(LEMON_ENABLE_GLPK)
     73IF(LEMON_ENABLE_ILOG)
     74  FIND_PACKAGE(ILOG)
     75ENDIF(LEMON_ENABLE_ILOG)
     76IF(LEMON_ENABLE_COIN)
     77  FIND_PACKAGE(COIN)
     78ENDIF(LEMON_ENABLE_COIN)
     79IF(LEMON_ENABLE_SOPLEX)
     80  FIND_PACKAGE(SOPLEX)
     81ENDIF(LEMON_ENABLE_SOPLEX)
     82
     83IF(GLPK_FOUND)
     84  SET(LEMON_HAVE_LP TRUE)
     85  SET(LEMON_HAVE_MIP TRUE)
     86  SET(LEMON_HAVE_GLPK TRUE)
     87ENDIF(GLPK_FOUND)
     88IF(ILOG_FOUND)
     89  SET(LEMON_HAVE_LP TRUE)
     90  SET(LEMON_HAVE_MIP TRUE)
     91  SET(LEMON_HAVE_CPLEX TRUE)
     92ENDIF(ILOG_FOUND)
     93IF(COIN_FOUND)
     94  SET(LEMON_HAVE_LP TRUE)
     95  SET(LEMON_HAVE_MIP TRUE)
     96  SET(LEMON_HAVE_CLP TRUE)
     97  SET(LEMON_HAVE_CBC TRUE)
     98ENDIF(COIN_FOUND)
     99IF(SOPLEX_FOUND)
     100  SET(LEMON_HAVE_LP TRUE)
     101  SET(LEMON_HAVE_SOPLEX TRUE)
     102ENDIF(SOPLEX_FOUND)
     103
     104IF(ILOG_FOUND)
     105  SET(DEFAULT_LP "CPLEX")
     106  SET(DEFAULT_MIP "CPLEX")
     107ELSEIF(COIN_FOUND)
     108  SET(DEFAULT_LP "CLP")
     109  SET(DEFAULT_MIP "CBC")
     110ELSEIF(GLPK_FOUND)
     111  SET(DEFAULT_LP "GLPK")
     112  SET(DEFAULT_MIP "GLPK")
     113ELSEIF(SOPLEX_FOUND)
     114  SET(DEFAULT_LP "SOPLEX")
     115ENDIF()
     116
     117IF(NOT LEMON_DEFAULT_LP OR
     118    (NOT ILOG_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CPLEX")) OR
     119    (NOT COIN_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CLP")) OR
     120    (NOT GLPK_FOUND AND (LEMON_DEFAULT_LP STREQUAL "GLPK")) OR
     121    (NOT SOPLEX_FOUND AND (LEMON_DEFAULT_LP STREQUAL "SOPLEX")))
     122  SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
     123    "Default LP solver backend (GLPK, CPLEX, CLP or SOPLEX)" FORCE)
     124ENDIF()
     125IF(NOT LEMON_DEFAULT_MIP OR
     126    (NOT ILOG_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CPLEX")) OR
     127    (NOT COIN_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CBC")) OR
     128    (NOT GLPK_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "GLPK")))
     129  SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
     130    "Default MIP solver backend (GLPK, CPLEX or CBC)" FORCE)
     131ENDIF()
     132
    67133
    68134IF(DEFINED ENV{LEMON_CXX_WARNING})
  • INSTALL

    r1208 r1233  
    135135
    136136 
     137-DLEMON_ENABLE_GLPK=NO
     138-DLEMON_ENABLE_COIN=NO
     139-DLEMON_ENABLE_ILOG=NO
     140
     141  Enable optional third party libraries. They are all enabled by default.
     142
     143-DLEMON_DEFAULT_LP=GLPK
     144
     145  Sets the default LP solver backend. The supported values are
     146  CPLEX, CLP and GLPK. By default, it is set to the first one which
     147  is enabled and succesfully discovered.
     148
     149-DLEMON_DEFAULT_MIP=GLPK
     150
     151  Sets the default MIP solver backend. The supported values are
     152  CPLEX, CBC and GLPK. By default, it is set to the first one which
     153  is enabled and succesfully discovered.
     154
    137155-DGLPK_ROOT_DIR=DIRECTORY
    138156-DCOIN_ROOT_DIR=DIRECTORY
    139 -DCPLEX_ROOT_DIR=DIRECTORY
     157-DILOG_ROOT_DIR=DIRECTORY
    140158
    141   Install root directory prefixes of optional third party libraries.
     159  Root directory prefixes of optional third party libraries.
    142160
    143161Makefile Variables
  • NEWS

    r962 r1281  
     12013-08-10 Version 1.3 released
     2
     3        This is major feature release
     4
     5        * New data structures
     6
     7          #69 : Bipartite graph concepts and implementations
     8
     9        * New algorithms
     10
     11          #177: Port Edmonds-Karp algorithm
     12          #380, #405: Heuristic algorithm for the max clique problem
     13          #386: Heuristic algorithms for symmetric TSP
     14          ----: Nagamochi-Ibaraki algorithm [5087694945e4]
     15          #397, #56: Max. cardinality search
     16
     17        * Other new features
     18
     19          #223: Thread safe graph and graph map implementations
     20          #442: Different TimeStamp print formats
     21          #457: File export functionality to LpBase
     22          #362: Bidirectional iterator support for radixSort()
     23
     24        * Implementation improvements
     25
     26          ----: Network Simplex
     27                #391: Better update process, pivot rule and arc mixing
     28                #435: Improved Altering List pivot rule
     29          #417: Various fine tunings in CostScaling
     30          #438: Optional iteration limit in HowardMmc
     31          #436: Ensure strongly polynomial running time for CycleCanceling
     32                while keeping the same performance
     33          ----: Make the CBC interface be compatible with latest CBC releases
     34                [ee581a0ecfbf]
     35
     36        * CMAKE has become the default build environment (#434)
     37
     38          ----: Autotool support has been dropped
     39          ----: Improved LP/MIP configuration
     40                #465: Enable/disable options for LP/MIP backends
     41                #446: Better CPLEX discovery
     42                #460: Add cmake config to find SoPlex
     43          ----: Allow CPACK configuration on all platforms
     44          #390: Add 'Maintainer' CMAKE build type
     45          #388: Add 'check' target.
     46          #401: Add contrib dir
     47          #389: Better version string setting in CMAKE
     48          #433: Support shared library build   
     49          #416: Support testing with valgrind
     50 
     51        * Doc improvements
     52
     53          #395: SOURCE_BROWSER Doxygen switch is configurable from CMAKE
     54                update-external-tags CMAKE target
     55          #455: Optionally use MathJax for rendering the math formulae
     56          #402, #437, #459, #456, #463: Various doc improvements
     57
     58        * Bugfixes (compared to release 1.2):
     59
     60          #432: Add missing doc/template.h and doc/references.bib to release
     61                tarball
     62          ----: Intel C++ compatibility fixes
     63          #441: Fix buggy reinitialization in _solver_bits::VarIndex::clear()
     64          #444: Bugfix in path copy constructors and assignment operators
     65          #447: Bugfix in AllArcLookUp<>
     66          #448: Bugfix in adaptor_test.cc
     67          #449: Fix clang compilation warnings and errors
     68          #440: Fix a bug + remove redundant typedefs in dimacs-solver
     69          #453: Avoid GCC 4.7 compiler warnings
     70          #445: Fix missing initialization in CplexEnv::CplexEnv()
     71          #428: Add missing lemon/lemon.pc.cmake to the release tarball
     72          #393: Create and install lemon.pc
     73          #429: Fix VS warnings
     74          #430: Fix LpBase::Constr two-side limit bug
     75          #392: Bug fix in Dfs::start(s,t)
     76          #414: Fix wrong initialization in Preflow
     77          #418: Better Win CodeBlock/MinGW support
     78          #419: Build environment improvements
     79                - Build of mip_test and lp_test precede the running of the tests
     80                - Also search for coin libs under ${COIN_ROOT_DIR}/lib/coin
     81                - Do not look for COIN_VOL libraries
     82          #382: Allow lgf file without Arc maps
     83          #417: Bug fix in CostScaling
     84          #366: Fix Pred[Matrix]MapPath::empty()
     85          #371: Bug fix in (di)graphCopy()
     86                The target graph is cleared before adding nodes and arcs/edges.
     87          #364: Add missing UndirectedTags
     88          #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
     89          #372: Fix a critical bug in preflow
     90          #461: Bugfix in assert.h
     91          #470: Fix compilation issues related to various gcc versions
     92          #446: Fix #define indicating CPLEX availability
     93          #294: Add explicit namespace to
     94                ignore_unused_variable_warning() usages
     95          #420: Bugfix in IterableValueMap
     96          #439: Bugfix in biNodeConnected()
     97
     98
    1992010-03-19 Version 1.2 released
    2100
  • cmake/FindCOIN.cmake

    r1120 r1232  
    109109  COIN_BZ2_LIBRARY
    110110)
    111 
    112 IF(COIN_FOUND)
    113   SET(LEMON_HAVE_LP TRUE)
    114   SET(LEMON_HAVE_MIP TRUE)
    115   SET(LEMON_HAVE_CLP TRUE)
    116   SET(LEMON_HAVE_CBC TRUE)
    117 ENDIF(COIN_FOUND)
  • cmake/FindGLPK.cmake

    r685 r1232  
    5454
    5555MARK_AS_ADVANCED(GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_BIN_DIR)
    56 
    57 IF(GLPK_FOUND)
    58   SET(LEMON_HAVE_LP TRUE)
    59   SET(LEMON_HAVE_MIP TRUE)
    60   SET(LEMON_HAVE_GLPK TRUE)
    61 ENDIF(GLPK_FOUND)
  • doc/CMakeLists.txt

    r1209 r1251  
    77SET(LEMON_DOC_USE_MATHJAX "NO" CACHE STRING "Use MathJax to display math formulae (YES/NO).")
    88SET(LEMON_DOC_MATHJAX_RELPATH "http://www.mathjax.org/mathjax" CACHE STRING "MathJax library location.")
     9
     10SET(LEMON_DOC_LIBSTDC++_URL
     11  "http://gcc.gnu.org/onlinedocs/gcc-4.7.3/libstdc++/api"
     12  CACHE STRING "GCC libstdc++ doxygen doc url.")
     13
    914
    1015CONFIGURE_FILE(
     
    3540    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
    3641    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
    37     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
    38     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
    39     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
    40     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
    41     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
    42     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
    43     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
    44     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
    45     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
    46     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
    47     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
    48     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
    49     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
    50     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
    51     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps
     42    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r20 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
     43    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/adaptors2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/adaptors2.eps
     44    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
     45    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     46    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
     47    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
     48    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
     49    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
     50    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
     51    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r40 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
     52    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps
     53    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
     54    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
     55    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
     56    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
     57    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
    5258    COMMAND ${CMAKE_COMMAND} -E remove_directory html
    53     COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
    5459    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    5560    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     
    7681IF(WGET_FOUND)
    7782ADD_CUSTOM_TARGET(update-external-tags
    78   COMMAND ${WGET_EXECUTABLE} -N http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
     83  COMMAND ${WGET_EXECUTABLE} -N ${LEMON_DOC_LIBSTDC++_URL}/libstdc++.tag
    7984  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
    8085  )
  • doc/Doxyfile.in

    r1208 r1251  
    7878FILE_VERSION_FILTER    =
    7979LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
     80CITE_BIB_FILES         = "@abs_top_srcdir@/doc/references.bib"
    8081#---------------------------------------------------------------------------
    8182# configuration options related to warning and progress messages
     
    99100                         "@abs_top_srcdir@/tools" \
    100101                         "@abs_top_srcdir@/test/test_tools.h" \
    101                          "@abs_top_builddir@/doc/mainpage.dox" \
    102                          "@abs_top_builddir@/doc/references.dox"
     102                         "@abs_top_builddir@/doc/mainpage.dox"
    103103INPUT_ENCODING         = UTF-8
    104104FILE_PATTERNS          = *.h \
     
    254254# Configuration::additions related to external references
    255255#---------------------------------------------------------------------------
    256 TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
     256TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = @LEMON_DOC_LIBSTDC++_URL@"
    257257GENERATE_TAGFILE       = html/lemon.tag
    258258ALLEXTERNALS           = NO
  • doc/DoxygenLayout.xml

    r1036 r1251  
    1818      <tab type="globals" visible="yes" title="" intro=""/>
    1919    </tab>
    20     <tab type="dirs" visible="yes" title="" intro=""/>
    2120    <tab type="examples" visible="yes" title="" intro=""/>
    2221    <tab type="pages" visible="yes" title="" intro=""/>
  • doc/coding_style.dox

    r1023 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/dirs.dox

    r1031 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/groups.dox

    r1206 r1271  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    113113detailed documentation of particular adaptors.
    114114
     115Since the adaptor classes conform to the \ref graph_concepts "graph concepts",
     116an adaptor can even be applied to another one.
     117The following image illustrates a situation when a \ref SubDigraph adaptor
     118is applied on a digraph and \ref Undirector is applied on the subgraph.
     119
     120\image html adaptors2.png
     121\image latex adaptors2.eps "Using graph adaptors" width=\textwidth
     122
    115123The behavior of graph adaptors can be very different. Some of them keep
    116124capabilities of the original graph while in other cases this would be
     
    310318This group contains the common graph search algorithms, namely
    311319\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
    312 \ref clrs01algorithms.
     320\cite clrs01algorithms.
    313321*/
    314322
     
    319327
    320328This group contains the algorithms for finding shortest paths in digraphs
    321 \ref clrs01algorithms.
     329\cite clrs01algorithms.
    322330
    323331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    341349
    342350This group contains the algorithms for finding minimum cost spanning
    343 trees and arborescences \ref clrs01algorithms.
     351trees and arborescences \cite clrs01algorithms.
    344352*/
    345353
     
    350358
    351359This group contains the algorithms for finding maximum flows and
    352 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
     360feasible circulations \cite clrs01algorithms, \cite amo93networkflows.
    353361
    354362The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    366374LEMON contains several algorithms for solving maximum flow problems:
    367375- \ref EdmondsKarp Edmonds-Karp algorithm
    368   \ref edmondskarp72theoretical.
     376  \cite edmondskarp72theoretical.
    369377- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
    370   \ref goldberg88newapproach.
     378  \cite goldberg88newapproach.
    371379- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
    372   \ref dinic70algorithm, \ref sleator83dynamic.
     380  \cite dinic70algorithm, \cite sleator83dynamic.
    373381- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
    374   \ref goldberg88newapproach, \ref sleator83dynamic.
     382  \cite goldberg88newapproach, \cite sleator83dynamic.
    375383
    376384In most cases the \ref Preflow algorithm provides the
     
    392400
    393401This group contains the algorithms for finding minimum cost flows and
    394 circulations \ref amo93networkflows. For more information about this
    395 problem and its dual solution, see \ref min_cost_flow
     402circulations \cite amo93networkflows. For more information about this
     403problem and its dual solution, see: \ref min_cost_flow
    396404"Minimum Cost Flow Problem".
    397405
    398406LEMON contains several algorithms for this problem.
    399407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    400    pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     408   pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex.
    401409 - \ref CostScaling Cost Scaling algorithm based on push/augment and
    402    relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
    403    \ref bunnagel98efficient.
     410   relabel operations \cite goldberg90approximation, \cite goldberg97efficient,
     411   \cite bunnagel98efficient.
    404412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
    405    shortest path method \ref edmondskarp72theoretical.
     413   shortest path method \cite edmondskarp72theoretical.
    406414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
    407    strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
     415   strongly polynomial \cite klein67primal, \cite goldberg89cyclecanceling.
    408416
    409417In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
     
    415423However, other algorithms could be faster in special cases.
    416424For example, if the total supply and/or capacities are rather small,
    417 \ref CapacityScaling is usually the fastest algorithm (without effective scaling).
     425\ref CapacityScaling is usually the fastest algorithm
     426(without effective scaling).
    418427
    419428These classes are intended to be used with integer-valued input data
     
    421430which is capable of handling real-valued arc costs (other numerical
    422431data are required to be integer).
     432
     433For more details about these implementations and for a comprehensive
     434experimental study, see the paper \cite KiralyKovacs12MCF.
     435It also compares these codes to other publicly available
     436minimum cost flow solvers.
    423437*/
    424438
     
    459473
    460474This group contains the algorithms for finding minimum mean cycles
    461 \ref amo93networkflows, \ref karp78characterization.
     475\cite amo93networkflows, \cite karp78characterization.
    462476
    463477The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     
    475489
    476490LEMON contains three algorithms for solving the minimum mean cycle problem:
    477 - \ref KarpMmc Karp's original algorithm \ref karp78characterization.
     491- \ref KarpMmc Karp's original algorithm \cite karp78characterization.
    478492- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    479   version of Karp's algorithm \ref hartmann93finding.
     493  version of Karp's algorithm \cite hartmann93finding.
    480494- \ref HowardMmc Howard's policy iteration algorithm
    481   \ref dasdan98minmeancycle, \ref dasdan04experimental.
     495  \cite dasdan98minmeancycle, \cite dasdan04experimental.
    482496
    483497In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
     
    485499time is exponential.
    486500Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
    487 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
    488 typically faster due to the applied early termination scheme.
     501run in time O(nm) and use space O(n<sup>2</sup>+m).
    489502*/
    490503
     
    559572\image latex planar.eps "Plane graph" width=\textwidth
    560573*/
    561  
     574
    562575/**
    563576@defgroup tsp Traveling Salesman Problem
     
    636649high-level interface.
    637650
    638 The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
    639 \ref cplex, \ref soplex.
     651The currently supported solvers are \cite glpk, \cite clp, \cite cbc,
     652\cite cplex, \cite soplex.
    640653*/
    641654
     
    724737This group contains general \c EPS drawing methods and special
    725738graph exporting tools.
     739
     740\image html graph_to_eps.png
    726741*/
    727742
  • doc/images/bipartite_partitions.eps

    r634 r1213  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Tue Nov 15 16:51:43 2005
     3%%CreationDate: Fri Mar  8 00:18:43 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 2 lb
    57 513.857 -446.322 575.52 -315.655 637.183 -184.989 0 0 0 2 lb
    58 393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 2 lb
    59 393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 2 lb
    60 393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 2 lb
    61 869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 2 lb
    62 869.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 2 lb
    63 -82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 2 lb
    64 -663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 2 lb
    65 -663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 2 lb
    66 -1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 2 lb
    67 -1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 2 lb
    68 -1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 2 lb
    69 -1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 2 lb
    70 -880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 2 lb
    71 -499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 2 lb
    72 -499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 2 lb
    73 -499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 2 lb
    74 79.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 2 lb
    75 637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 2 lb
    76 205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 2 lb
    77 399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 2 lb
    78 399.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 2 lb
    79 -842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 2 lb
    80 -842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 2 lb
    81 -860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 2 lb
    82 -211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 2 lb
    83 -99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 2 lb
    84 -99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 2 lb
    85 120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 2 lb
     56513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 7.00153 lb
     57513.857 -446.322 575.52 -315.656 637.183 -184.989 0 0 0 7.00153 lb
     58393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 7.00153 lb
     59393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 7.00153 lb
     60393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 7.00153 lb
     61869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 7.00153 lb
     62869.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 7.00153 lb
     63-82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 7.00153 lb
     64-663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 7.00153 lb
     65-663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 7.00153 lb
     66-1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 7.00153 lb
     67-1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 7.00153 lb
     68-1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 7.00153 lb
     69-1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 7.00153 lb
     70-880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 7.00153 lb
     71-499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 7.00153 lb
     72-499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 7.00153 lb
     73-499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 7.00153 lb
     7479.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 7.00153 lb
     75637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 7.00153 lb
     76205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 7.00153 lb
     77399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 7.00153 lb
     78399.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 7.00153 lb
     79-842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 7.00153 lb
     80-842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 7.00153 lb
     81-860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 7.00153 lb
     82-211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 7.00153 lb
     83-99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 7.00153 lb
     84-99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 7.00153 lb
     85120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 7.00153 lb
    8686grestore
    8787%Nodes:
    8888gsave
    89 -274 -131 20 1 0 0 nc
    90 -607.82 -246.651 20 1 0 0 nc
    91 -484.494 328.869 20 0 0 1 nc
    92 108.644 334.741 20 0 0 1 nc
    93 120.389 -129.198 20 0 0 1 nc
    94 -99.8351 99.8351 20 1 0 0 nc
    95 -211.415 -452.194 20 1 0 0 nc
    96 -860.344 -29.3633 20 0 0 1 nc
    97 -842.726 243.715 20 0 0 1 nc
    98 399.34 88.0898 20 1 0 0 nc
    99 205.543 -322.996 20 1 0 0 nc
    100 637.183 -184.989 20 0 0 1 nc
    101 79.2808 -528.539 20 0 0 1 nc
    102 -499.175 -499.175 20 0 0 1 nc
    103 -880.898 -528.539 20 0 0 1 nc
    104 -1177.47 -234.906 20 1 0 0 nc
    105 -1077.63 161.498 20 1 0 0 nc
    106 -663.61 546.157 20 1 0 0 nc
    107 -82.2171 593.138 20 0 0 1 nc
    108 596.074 302.442 20 0 0 1 nc
    109 869.153 52.8539 20 1 0 0 nc
    110 393.468 566.711 20 1 0 0 nc
    111 513.857 -446.322 20 1 0 0 nc
     89-274 -131 23.3384 1 0 0 nc
     90-607.82 -246.651 23.3384 1 0 0 nc
     91-484.494 328.869 23.3384 0 0 1 nc
     92108.644 334.741 23.3384 0 0 1 nc
     93120.389 -129.198 23.3384 0 0 1 nc
     94-99.8351 99.8351 23.3384 1 0 0 nc
     95-211.415 -452.194 23.3384 1 0 0 nc
     96-860.344 -29.3633 23.3384 0 0 1 nc
     97-842.726 243.715 23.3384 0 0 1 nc
     98399.34 88.0898 23.3384 1 0 0 nc
     99205.543 -322.996 23.3384 1 0 0 nc
     100637.183 -184.989 23.3384 0 0 1 nc
     10179.2808 -528.539 23.3384 0 0 1 nc
     102-499.175 -499.175 23.3384 0 0 1 nc
     103-880.898 -528.539 23.3384 0 0 1 nc
     104-1177.47 -234.906 23.3384 1 0 0 nc
     105-1077.63 161.498 23.3384 1 0 0 nc
     106-663.61 546.157 23.3384 1 0 0 nc
     107-82.2171 593.138 23.3384 0 0 1 nc
     108596.074 302.442 23.3384 0 0 1 nc
     109869.153 52.8539 23.3384 1 0 0 nc
     110393.468 566.711 23.3384 1 0 0 nc
     111513.857 -446.322 23.3384 1 0 0 nc
    112112grestore
    113113grestore
  • doc/images/connected_components.eps

    r634 r1213  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Nov  4 13:47:12 2005
     3%%CreationDate: Fri Mar  8 00:18:43 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 574.035 177.301 622.149 225.748 670.264 274.195 0 0 0 2 lb
    57 694.579 115.483 682.421 194.839 670.264 274.195 0 0 0 2 lb
    58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 2 lb
    59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 2 lb
    60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 2 lb
    61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 2 lb
    62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 2 lb
    63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 2 lb
    64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 2 lb
    65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 2 lb
    66 366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 2 lb
    67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 2 lb
    68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 2 lb
    69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 0 2 lb
    70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0 0 2 lb
    71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0 2 lb
    72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0 2 lb
    73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0 2 lb
    74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 2 lb
    75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 2 lb
    76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 0 2 lb
    77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0 0 0 2 lb
    78 422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 2 lb
    79 422.945 521.129 376.371 417.911 329.797 314.692 0 0 0 2 lb
    80 422.945 521.129 474.554 276.928 526.164 32.7279 0 0 0 2 lb
    81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 0 2 lb
    82 329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 0 2 lb
    83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 0 2 lb
    84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 2 lb
    85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 2 lb
    86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 2 lb
    87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 2 lb
    88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 0 0 0 2 lb
    89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 0 2 lb
    90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 0 2 lb
    91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 0 2 lb
    92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 0 2 lb
    93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 0 2 lb
    94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 0 2 lb
    95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 0 2 lb
    96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 0 2 lb
    97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 0 2 lb
    98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 0 2 lb
    99 -262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 0 2 lb
    100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 0 2 lb
    101 -180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 0 2 lb
    102 -180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 0 2 lb
    103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 0 2 lb
    104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 0 2 lb
    105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 0 2 lb
    106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 0 2 lb
    107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 0 2 lb
    108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 0 2 lb
    109 -689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 0 2 lb
    110 -689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 0 2 lb
     56574.035 177.301 622.149 225.748 670.264 274.195 0 0 0 6.25356 lb
     57694.579 115.483 682.421 194.839 670.264 274.195 0 0 0 6.25356 lb
     58280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 6.25356 lb
     59280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 6.25356 lb
     60212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 6.25356 lb
     61286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 6.25356 lb
     62286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 6.25356 lb
     63438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 6.25356 lb
     64438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 6.25356 lb
     65397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 6.25356 lb
     66366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 6.25356 lb
     67271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 6.25356 lb
     68271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 6.25356 lb
     69277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 0 6.25356 lb
     70-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0 0 6.25356 lb
     71-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0 6.25356 lb
     72-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0 6.25356 lb
     73-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0 6.25356 lb
     74906.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 6.25356 lb
     75906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 6.25356 lb
     76986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 0 6.25356 lb
     77-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0 0 0 6.25356 lb
     78422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 6.25356 lb
     79422.945 521.129 376.371 417.911 329.797 314.692 0 0 0 6.25356 lb
     80422.945 521.129 474.554 276.928 526.164 32.7279 0 0 0 6.25356 lb
     81-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 0 6.25356 lb
     82329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 0 6.25356 lb
     83-67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 0 6.25356 lb
     84762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 6.25356 lb
     85762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 6.25356 lb
     86526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 6.25356 lb
     87730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 6.25356 lb
     88415.393 -289.516 173.71 -318.468 -67.9734 -347.42 0 0 0 6.25356 lb
     89-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 0 6.25356 lb
     90-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 0 6.25356 lb
     91-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 0 6.25356 lb
     92-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 0 6.25356 lb
     93-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 0 6.25356 lb
     94-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 0 6.25356 lb
     95-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 0 6.25356 lb
     96-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 0 6.25356 lb
     97116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 0 6.25356 lb
     98-262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 0 6.25356 lb
     99-262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 0 6.25356 lb
     100-13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 0 6.25356 lb
     101-180.397 245.045 -113.509 338.465 -132.697 451.748 0 0 0 6.25356 lb
     102-180.397 245.045 -199.585 358.328 -132.697 451.748 0 0 0 6.25356 lb
     103-416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 0 6.25356 lb
     104-416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 0 6.25356 lb
     105-132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 0 6.25356 lb
     106670.264 274.195 629.188 409.347 588.113 544.499 0 0 0 6.25356 lb
     107670.264 274.195 797.466 341.771 924.667 409.347 0 0 0 6.25356 lb
     108588.113 544.499 756.39 476.923 924.667 409.347 0 0 0 6.25356 lb
     109-689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 0 6.25356 lb
     110-689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 0 6.25356 lb
    111111grestore
    112112%Nodes:
    113113gsave
    114 -567.302 43.6423 20 0 0 0 nc
    115 -689.204 -237.261 20 0 0 0 nc
    116 924.667 409.347 20 1 0 0 nc
    117 588.113 544.499 20 1 0 0 nc
    118 670.264 274.195 20 1 0 0 nc
    119 -371.2 568.349 20 0 1 0 nc
    120 -132.697 451.748 20 0 1 0 nc
    121 -416.25 345.746 20 0 1 0 nc
    122 -180.397 245.045 20 0 1 0 nc
    123 -13.4452 133.743 20 0 1 0 nc
    124 -262.548 107.243 20 0 1 0 nc
    125 201.208 38.3422 20 0 1 0 nc
    126 116.407 -173.66 20 0 1 0 nc
    127 -26.6953 -19.9585 20 0 1 0 nc
    128 -539.894 -262.64 20 0 0 1 nc
    129 -323.543 -433.964 20 0 0 1 nc
    130 -309.657 -57.9033 20 0 0 1 nc
    131 -67.9734 -347.42 20 0 0 1 nc
    132 415.393 -289.516 20 0 0 1 nc
    133 730.084 -307.139 20 0 0 1 nc
    134 526.164 32.7279 20 0 0 1 nc
    135 762.812 -17.6227 20 0 0 1 nc
    136 -67.9734 319.727 20 0 0 1 nc
    137 329.797 314.692 20 0 0 1 nc
    138 -5.03507 561.41 20 0 0 1 nc
    139 422.945 521.129 20 0 0 1 nc
    140 -470.779 158.605 20 0 0 1 nc
    141 986.873 -115.807 20 0 0 1 nc
    142 906.312 201.403 20 0 0 1 nc
    143 -767.847 113.289 20 0 0 1 nc
    144 -579.033 445.603 20 0 0 1 nc
    145 -840.856 -246.718 20 0 0 1 nc
    146 206.221 -205.967 20 1 1 0 nc
    147 277.311 -252.33 20 1 1 0 nc
    148 271.13 -175.058 20 1 1 0 nc
    149 366.947 -110.15 20 1 1 0 nc
    150 397.855 -196.694 20 1 1 0 nc
    151 438.037 -88.514 20 1 1 0 nc
    152 286.584 -48.3327 20 1 1 0 nc
    153 212.403 -23.6057 20 1 1 0 nc
    154 280.402 10.3938 20 1 1 0 nc
    155 694.579 115.483 20 1 0 0 nc
    156 574.035 177.301 20 1 0 0 nc
     114-567.302 43.6423 20.8452 0 0 0 nc
     115-689.204 -237.261 20.8452 0 0 0 nc
     116924.667 409.347 20.8452 1 0 0 nc
     117588.113 544.499 20.8452 1 0 0 nc
     118670.264 274.195 20.8452 1 0 0 nc
     119-371.2 568.349 20.8452 0 1 0 nc
     120-132.697 451.748 20.8452 0 1 0 nc
     121-416.25 345.746 20.8452 0 1 0 nc
     122-180.397 245.045 20.8452 0 1 0 nc
     123-13.4452 133.743 20.8452 0 1 0 nc
     124-262.548 107.243 20.8452 0 1 0 nc
     125201.208 38.3422 20.8452 0 1 0 nc
     126116.407 -173.66 20.8452 0 1 0 nc
     127-26.6953 -19.9585 20.8452 0 1 0 nc
     128-539.894 -262.64 20.8452 0 0 1 nc
     129-323.543 -433.964 20.8452 0 0 1 nc
     130-309.657 -57.9033 20.8452 0 0 1 nc
     131-67.9734 -347.42 20.8452 0 0 1 nc
     132415.393 -289.516 20.8452 0 0 1 nc
     133730.084 -307.139 20.8452 0 0 1 nc
     134526.164 32.7279 20.8452 0 0 1 nc
     135762.812 -17.6227 20.8452 0 0 1 nc
     136-67.9734 319.727 20.8452 0 0 1 nc
     137329.797 314.692 20.8452 0 0 1 nc
     138-5.03507 561.41 20.8452 0 0 1 nc
     139422.945 521.129 20.8452 0 0 1 nc
     140-470.779 158.605 20.8452 0 0 1 nc
     141986.873 -115.807 20.8452 0 0 1 nc
     142906.312 201.403 20.8452 0 0 1 nc
     143-767.847 113.289 20.8452 0 0 1 nc
     144-579.033 445.603 20.8452 0 0 1 nc
     145-840.856 -246.718 20.8452 0 0 1 nc
     146206.221 -205.967 20.8452 1 1 0 nc
     147277.311 -252.33 20.8452 1 1 0 nc
     148271.13 -175.058 20.8452 1 1 0 nc
     149366.947 -110.15 20.8452 1 1 0 nc
     150397.855 -196.694 20.8452 1 1 0 nc
     151438.037 -88.514 20.8452 1 1 0 nc
     152286.584 -48.3327 20.8452 1 1 0 nc
     153212.403 -23.6057 20.8452 1 1 0 nc
     154280.402 10.3938 20.8452 1 1 0 nc
     155694.579 115.483 20.8452 1 0 0 nc
     156574.035 177.301 20.8452 1 0 0 nc
    157157grestore
    158158grestore
  • doc/images/edge_biconnected_components.eps

    r634 r1213  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Nov  4 13:47:12 2005
     3%%CreationDate: Fri Mar  8 00:18:43 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 574.035 177.301 622.149 225.748 670.264 274.195 1 0 0 2 lb
    57 694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 2 lb
    58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 2 lb
    59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 2 lb
    60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 2 lb
    61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 2 lb
    62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 2 lb
    63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 2 lb
    64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 2 lb
    65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 2 lb
    66 366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 2 lb
    67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 2 lb
    68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 2 lb
    69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 2 lb
    70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 2 lb
    71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 2 lb
    72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 2 lb
    73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 2 lb
    74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 2 lb
    75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 2 lb
    76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 2 lb
    77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 2 lb
    78 422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 2 lb
    79 422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 2 lb
    80 422.945 521.129 474.554 276.928 526.164 32.7279 0 0 1 2 lb
    81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 2 lb
    82 329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 2 lb
    83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 2 lb
    84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 2 lb
    85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 2 lb
    86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 2 lb
    87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 2 lb
    88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 2 lb
    89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 2 lb
    90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 2 lb
    91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 2 lb
    92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 2 lb
    93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 2 lb
    94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 2 lb
    95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 2 lb
    96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 2 lb
    97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 2 lb
    98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 2 lb
    99 -262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 2 lb
    100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 2 lb
    101 -180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 1 2 lb
    102 -180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 1 2 lb
    103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 2 lb
    104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 2 lb
    105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 2 lb
    106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 2 lb
    107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 2 lb
    108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 2 lb
    109 -689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 1 2 lb
    110 -689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 1 2 lb
     56574.035 177.301 622.149 225.748 670.264 274.195 1 0 0 6.25356 lb
     57694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 6.25356 lb
     58280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 6.25356 lb
     59280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 6.25356 lb
     60212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 6.25356 lb
     61286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 6.25356 lb
     62286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 6.25356 lb
     63438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 6.25356 lb
     64438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 6.25356 lb
     65397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 6.25356 lb
     66366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 6.25356 lb
     67271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 6.25356 lb
     68271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 6.25356 lb
     69277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 6.25356 lb
     70-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 6.25356 lb
     71-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 6.25356 lb
     72-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 6.25356 lb
     73-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 6.25356 lb
     74906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 6.25356 lb
     75906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 6.25356 lb
     76986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 6.25356 lb
     77-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 6.25356 lb
     78422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 6.25356 lb
     79422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 6.25356 lb
     80422.945 521.129 474.554 276.928 526.164 32.7279 0 0 1 6.25356 lb
     81-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 6.25356 lb
     82329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 6.25356 lb
     83-67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 6.25356 lb
     84762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 6.25356 lb
     85762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 6.25356 lb
     86526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 6.25356 lb
     87730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 6.25356 lb
     88415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 6.25356 lb
     89-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 6.25356 lb
     90-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 6.25356 lb
     91-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 6.25356 lb
     92-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 6.25356 lb
     93-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 6.25356 lb
     94-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 6.25356 lb
     95-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 6.25356 lb
     96-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 6.25356 lb
     97116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 6.25356 lb
     98-262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 6.25356 lb
     99-262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 6.25356 lb
     100-13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 6.25356 lb
     101-180.397 245.045 -113.509 338.465 -132.697 451.748 0 0 1 6.25356 lb
     102-180.397 245.045 -199.585 358.328 -132.697 451.748 0 0 1 6.25356 lb
     103-416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 6.25356 lb
     104-416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 6.25356 lb
     105-132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 6.25356 lb
     106670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 6.25356 lb
     107670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 6.25356 lb
     108588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 6.25356 lb
     109-689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 1 6.25356 lb
     110-689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 1 6.25356 lb
    111111grestore
    112112%Nodes:
    113113gsave
    114 -567.302 43.6423 20 0 0 0 nc
    115 -689.204 -237.261 20 0 0 0 nc
    116 924.667 409.347 20 0 0 1 nc
    117 588.113 544.499 20 0 0 1 nc
    118 670.264 274.195 20 0 0 1 nc
    119 -371.2 568.349 20 1 1 0 nc
    120 -132.697 451.748 20 1 1 0 nc
    121 -416.25 345.746 20 1 1 0 nc
    122 -180.397 245.045 20 1 1 0 nc
    123 -13.4452 133.743 20 1 1 0 nc
    124 -262.548 107.243 20 1 1 0 nc
    125 201.208 38.3422 20 1 1 0 nc
    126 116.407 -173.66 20 1 1 0 nc
    127 -26.6953 -19.9585 20 1 1 0 nc
    128 -539.894 -262.64 20 0 0.5 0 nc
    129 -323.543 -433.964 20 0 0.5 0 nc
    130 -309.657 -57.9033 20 0 0.5 0 nc
    131 -67.9734 -347.42 20 0 0.5 0 nc
    132 415.393 -289.516 20 0.5 0 0 nc
    133 730.084 -307.139 20 0.5 0 0 nc
    134 526.164 32.7279 20 0.5 0 0 nc
    135 762.812 -17.6227 20 0.5 0 0 nc
    136 -67.9734 319.727 20 0.5 0 0 nc
    137 329.797 314.692 20 0.5 0 0 nc
    138 -5.03507 561.41 20 0.5 0 0 nc
    139 422.945 521.129 20 0.5 0 0 nc
    140 -470.779 158.605 20 0 1 1 nc
    141 986.873 -115.807 20 0.5 0 0 nc
    142 906.312 201.403 20 0.5 0 0 nc
    143 -767.847 113.289 20 0 1 1 nc
    144 -579.033 445.603 20 0 1 1 nc
    145 -840.856 -246.718 20 1 0 1 nc
    146 206.221 -205.967 20 0 0 0.5 nc
    147 277.311 -252.33 20 0 0 0.5 nc
    148 271.13 -175.058 20 0 0 0.5 nc
    149 366.947 -110.15 20 0 0 0.5 nc
    150 397.855 -196.694 20 0 0 0.5 nc
    151 438.037 -88.514 20 0 0 0.5 nc
    152 286.584 -48.3327 20 0 0 0.5 nc
    153 212.403 -23.6057 20 0 0 0.5 nc
    154 280.402 10.3938 20 0 0 0.5 nc
    155 694.579 115.483 20 1 0 0 nc
    156 574.035 177.301 20 0 1 0 nc
     114-567.302 43.6423 20.8452 0 0 0 nc
     115-689.204 -237.261 20.8452 0 0 0 nc
     116924.667 409.347 20.8452 0 0 1 nc
     117588.113 544.499 20.8452 0 0 1 nc
     118670.264 274.195 20.8452 0 0 1 nc
     119-371.2 568.349 20.8452 1 1 0 nc
     120-132.697 451.748 20.8452 1 1 0 nc
     121-416.25 345.746 20.8452 1 1 0 nc
     122-180.397 245.045 20.8452 1 1 0 nc
     123-13.4452 133.743 20.8452 1 1 0 nc
     124-262.548 107.243 20.8452 1 1 0 nc
     125201.208 38.3422 20.8452 1 1 0 nc
     126116.407 -173.66 20.8452 1 1 0 nc
     127-26.6953 -19.9585 20.8452 1 1 0 nc
     128-539.894 -262.64 20.8452 0 0.5 0 nc
     129-323.543 -433.964 20.8452 0 0.5 0 nc
     130-309.657 -57.9033 20.8452 0 0.5 0 nc
     131-67.9734 -347.42 20.8452 0 0.5 0 nc
     132415.393 -289.516 20.8452 0.5 0 0 nc
     133730.084 -307.139 20.8452 0.5 0 0 nc
     134526.164 32.7279 20.8452 0.5 0 0 nc
     135762.812 -17.6227 20.8452 0.5 0 0 nc
     136-67.9734 319.727 20.8452 0.5 0 0 nc
     137329.797 314.692 20.8452 0.5 0 0 nc
     138-5.03507 561.41 20.8452 0.5 0 0 nc
     139422.945 521.129 20.8452 0.5 0 0 nc
     140-470.779 158.605 20.8452 0 1 1 nc
     141986.873 -115.807 20.8452 0.5 0 0 nc
     142906.312 201.403 20.8452 0.5 0 0 nc
     143-767.847 113.289 20.8452 0 1 1 nc
     144-579.033 445.603 20.8452 0 1 1 nc
     145-840.856 -246.718 20.8452 1 0 1 nc
     146206.221 -205.967 20.8452 0 0 0.5 nc
     147277.311 -252.33 20.8452 0 0 0.5 nc
     148271.13 -175.058 20.8452 0 0 0.5 nc
     149366.947 -110.15 20.8452 0 0 0.5 nc
     150397.855 -196.694 20.8452 0 0 0.5 nc
     151438.037 -88.514 20.8452 0 0 0.5 nc
     152286.584 -48.3327 20.8452 0 0 0.5 nc
     153212.403 -23.6057 20.8452 0 0 0.5 nc
     154280.402 10.3938 20.8452 0 0 0.5 nc
     155694.579 115.483 20.8452 1 0 0 nc
     156574.035 177.301 20.8452 0 1 0 nc
    157157grestore
    158158grestore
  • doc/images/node_biconnected_components.eps

    r634 r1213  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Nov  4 13:47:12 2005
     3%%CreationDate: Fri Mar  8 00:18:43 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 574.035 177.301 622.149 225.748 670.264 274.195 0 1 0 5 lb
    57 694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 5 lb
    58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 5 lb
    59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 5 lb
    60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 5 lb
    61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 5 lb
    62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 5 lb
    63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 5 lb
    64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 5 lb
    65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 5 lb
    66 366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 5 lb
    67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 5 lb
    68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 5 lb
    69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 5 lb
    70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 5 lb
    71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 5 lb
    72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 5 lb
    73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 5 lb
    74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 5 lb
    75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 5 lb
    76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 5 lb
    77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 5 lb
    78 422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 5 lb
    79 422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 5 lb
    80 422.945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 5 lb
    81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 5 lb
    82 329.797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 5 lb
    83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 5 lb
    84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 5 lb
    85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 5 lb
    86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 5 lb
    87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 5 lb
    88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 5 lb
    89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 5 lb
    90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 5 lb
    91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 5 lb
    92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 5 lb
    93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 5 lb
    94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 5 lb
    95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 5 lb
    96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 5 lb
    97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 5 lb
    98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 5 lb
    99 -262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 5 lb
    100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 5 lb
    101 -180.397 245.045 -140.307 344.649 -132.697 451.748 0 1 1 5 lb
    102 -180.397 245.045 -172.787 352.144 -132.697 451.748 0 1 1 5 lb
    103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 5 lb
    104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 5 lb
    105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 5 lb
    106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 5 lb
    107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 5 lb
    108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 5 lb
    109 -689.204 -237.261 -612.964 -103.444 -567.302 43.6423 0 0 0 5 lb
    110 -689.204 -237.261 -643.542 -90.1744 -567.302 43.6423 0 0 0 5 lb
     56574.035 177.301 622.149 225.748 670.264 274.195 0 1 0 6.25356 lb
     57694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 6.25356 lb
     58280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 6.25356 lb
     59280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 6.25356 lb
     60212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 6.25356 lb
     61286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 6.25356 lb
     62286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 6.25356 lb
     63438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 6.25356 lb
     64438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 6.25356 lb
     65397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 6.25356 lb
     66366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 6.25356 lb
     67271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 6.25356 lb
     68271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 6.25356 lb
     69277.311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 6.25356 lb
     70-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 6.25356 lb
     71-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 6.25356 lb
     72-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 6.25356 lb
     73-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 6.25356 lb
     74906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 6.25356 lb
     75906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 6.25356 lb
     76986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 6.25356 lb
     77-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 6.25356 lb
     78422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 6.25356 lb
     79422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 6.25356 lb
     80422.945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 6.25356 lb
     81-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 6.25356 lb
     82329.797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 6.25356 lb
     83-67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 6.25356 lb
     84762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 6.25356 lb
     85762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 6.25356 lb
     86526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 6.25356 lb
     87730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 6.25356 lb
     88415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 6.25356 lb
     89-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 6.25356 lb
     90-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 6.25356 lb
     91-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 6.25356 lb
     92-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 6.25356 lb
     93-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 6.25356 lb
     94-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 6.25356 lb
     95-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 6.25356 lb
     96-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 6.25356 lb
     97116.407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 6.25356 lb
     98-262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 6.25356 lb
     99-262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 6.25356 lb
     100-13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 6.25356 lb
     101-180.397 245.045 -113.509 338.465 -132.697 451.748 0 1 1 6.25356 lb
     102-180.397 245.045 -199.585 358.328 -132.697 451.748 0 1 1 6.25356 lb
     103-416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 6.25356 lb
     104-416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 6.25356 lb
     105-132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 6.25356 lb
     106670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 6.25356 lb
     107670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 6.25356 lb
     108588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 6.25356 lb
     109-689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 0 6.25356 lb
     110-689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 0 6.25356 lb
    111111grestore
    112112%Nodes:
    113113gsave
    114 -567.302 43.6423 20 0 0 1 nc
    115 -689.204 -237.261 20 0 0 1 nc
    116 924.667 409.347 20 0 0 1 nc
    117 588.113 544.499 20 0 0 1 nc
    118 670.264 274.195 20 1 0 0 nc
    119 -371.2 568.349 20 0 0 1 nc
    120 -132.697 451.748 20 1 0 0 nc
    121 -416.25 345.746 20 0 0 1 nc
    122 -180.397 245.045 20 1 0 0 nc
    123 -13.4452 133.743 20 0 0 1 nc
    124 -262.548 107.243 20 0 0 1 nc
    125 201.208 38.3422 20 0 0 1 nc
    126 116.407 -173.66 20 0 0 1 nc
    127 -26.6953 -19.9585 20 1 0 0 nc
    128 -539.894 -262.64 20 0 0 1 nc
    129 -323.543 -433.964 20 0 0 1 nc
    130 -309.657 -57.9033 20 1 0 0 nc
    131 -67.9734 -347.42 20 1 0 0 nc
    132 415.393 -289.516 20 1 0 0 nc
    133 730.084 -307.139 20 0 0 1 nc
    134 526.164 32.7279 20 1 0 0 nc
    135 762.812 -17.6227 20 1 0 0 nc
    136 -67.9734 319.727 20 0 0 1 nc
    137 329.797 314.692 20 0 0 1 nc
    138 -5.03507 561.41 20 0 0 1 nc
    139 422.945 521.129 20 0 0 1 nc
    140 -470.779 158.605 20 1 0 0 nc
    141 986.873 -115.807 20 0 0 1 nc
    142 906.312 201.403 20 0 0 1 nc
    143 -767.847 113.289 20 1 0 0 nc
    144 -579.033 445.603 20 0 0 1 nc
    145 -840.856 -246.718 20 0 0 1 nc
    146 206.221 -205.967 20 0 0 1 nc
    147 277.311 -252.33 20 0 0 1 nc
    148 271.13 -175.058 20 1 0 0 nc
    149 366.947 -110.15 20 1 0 0 nc
    150 397.855 -196.694 20 0 0 1 nc
    151 438.037 -88.514 20 0 0 1 nc
    152 286.584 -48.3327 20 1 0 0 nc
    153 212.403 -23.6057 20 0 0 1 nc
    154 280.402 10.3938 20 0 0 1 nc
    155 694.579 115.483 20 0 0 1 nc
    156 574.035 177.301 20 0 0 1 nc
     114-567.302 43.6423 20.8452 0 0 1 nc
     115-689.204 -237.261 20.8452 0 0 1 nc
     116924.667 409.347 20.8452 0 0 1 nc
     117588.113 544.499 20.8452 0 0 1 nc
     118670.264 274.195 20.8452 1 0 0 nc
     119-371.2 568.349 20.8452 0 0 1 nc
     120-132.697 451.748 20.8452 1 0 0 nc
     121-416.25 345.746 20.8452 0 0 1 nc
     122-180.397 245.045 20.8452 1 0 0 nc
     123-13.4452 133.743 20.8452 0 0 1 nc
     124-262.548 107.243 20.8452 0 0 1 nc
     125201.208 38.3422 20.8452 0 0 1 nc
     126116.407 -173.66 20.8452 0 0 1 nc
     127-26.6953 -19.9585 20.8452 1 0 0 nc
     128-539.894 -262.64 20.8452 0 0 1 nc
     129-323.543 -433.964 20.8452 0 0 1 nc
     130-309.657 -57.9033 20.8452 1 0 0 nc
     131-67.9734 -347.42 20.8452 1 0 0 nc
     132415.393 -289.516 20.8452 1 0 0 nc
     133730.084 -307.139 20.8452 0 0 1 nc
     134526.164 32.7279 20.8452 1 0 0 nc
     135762.812 -17.6227 20.8452 1 0 0 nc
     136-67.9734 319.727 20.8452 0 0 1 nc
     137329.797 314.692 20.8452 0 0 1 nc
     138-5.03507 561.41 20.8452 0 0 1 nc
     139422.945 521.129 20.8452 0 0 1 nc
     140-470.779 158.605 20.8452 1 0 0 nc
     141986.873 -115.807 20.8452 0 0 1 nc
     142906.312 201.403 20.8452 0 0 1 nc
     143-767.847 113.289 20.8452 1 0 0 nc
     144-579.033 445.603 20.8452 0 0 1 nc
     145-840.856 -246.718 20.8452 0 0 1 nc
     146206.221 -205.967 20.8452 0 0 1 nc
     147277.311 -252.33 20.8452 0 0 1 nc
     148271.13 -175.058 20.8452 1 0 0 nc
     149366.947 -110.15 20.8452 1 0 0 nc
     150397.855 -196.694 20.8452 0 0 1 nc
     151438.037 -88.514 20.8452 0 0 1 nc
     152286.584 -48.3327 20.8452 1 0 0 nc
     153212.403 -23.6057 20.8452 0 0 1 nc
     154280.402 10.3938 20.8452 0 0 1 nc
     155694.579 115.483 20.8452 0 0 1 nc
     156574.035 177.301 20.8452 0 0 1 nc
    157157grestore
    158158grestore
  • doc/images/strongly_connected_components.eps

    r634 r1213  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Nov  4 13:47:12 2005
     3%%CreationDate: Fri Mar  8 00:22:15 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 2 setlinewidth 0 0 1 setrgbcolor newpath
     564.56973 setlinewidth 0 0 1 setrgbcolor newpath
    5757218.178 27.2723 moveto
    58 192.373 -40.1551 188.622 -49.9556 169.228 -100.631 curveto stroke
    59 newpath 164.939 -111.838 moveto 165.492 -99.2013 lineto 172.964 -102.061 lineto closepath fill
    60 2 setlinewidth 0 0 1 setrgbcolor newpath
     58195.849 -31.0725 190.033 -46.2697 176.306 -82.1369 curveto stroke
     59newpath 163.235 -116.291 moveto 165.206 -77.8889 lineto 187.405 -86.3849 lineto closepath fill
     604.56973 setlinewidth 0 0 1 setrgbcolor newpath
    616144.8044 15.5841 moveto
    62 119.293 20.6059 129.775 21.3125 186.25 25.1199 curveto stroke
    63 newpath 198.223 25.927 moveto 186.519 21.1289 lineto 185.981 29.1108 lineto closepath fill
    64 2 setlinewidth 1 0 0 setrgbcolor newpath
     62109.705 19.9594 126.016 21.0591 166.493 23.7879 curveto stroke
     63newpath 202.98 26.2477 moveto 167.292 11.9299 lineto 165.694 35.6458 lineto closepath fill
     644.56973 setlinewidth 1 0 0 setrgbcolor newpath
    6565218.178 27.2723 moveto
    66 285.395 -87.4449 290.763 -96.6058 348.102 -194.464 curveto stroke
    67 newpath 354.169 -204.818 moveto 344.651 -196.487 lineto 351.554 -192.442 lineto closepath fill
    68 2 setlinewidth 0 0 1 setrgbcolor newpath
     66281.264 -80.3935 289.87 -95.0808 338.092 -177.379 curveto stroke
     67newpath 356.579 -208.932 moveto 327.837 -183.388 lineto 348.346 -171.371 lineto closepath fill
     684.56973 setlinewidth 0 0 1 setrgbcolor newpath
    6969157.79 -130.517 moveto
    70 108.71 -67.0521 102.27 -58.7243 64.3804 -9.72954 curveto stroke
    71 newpath 57.0394 -0.236898 moveto 67.5446 -7.28254 lineto 61.2162 -12.1765 lineto closepath fill
    72 2 setlinewidth 1 0 0 setrgbcolor newpath
     70114.446 -74.4692 104.358 -61.4239 76.4943 -25.394 curveto stroke
     71newpath 54.1228 3.53455 moveto 85.8959 -18.1234 lineto 67.0928 -32.6646 lineto closepath fill
     724.56973 setlinewidth 1 0 0 setrgbcolor newpath
    7373-105.193 -261.035 moveto
    74 -35.6576 -132.801 -30.5923 -123.459 29.5506 -12.5464 curveto stroke
    75 newpath 35.2708 -1.99743 moveto 33.0669 -14.4531 lineto 26.0343 -10.6397 lineto closepath fill
    76 2 setlinewidth 0 0 1 setrgbcolor newpath
     74-39.4801 -139.85 -31.344 -124.846 20.1113 -29.9539 curveto stroke
     75newpath 37.5434 2.19358 moveto 30.559 -35.6192 lineto 9.66361 -24.2886 lineto closepath fill
     764.56973 setlinewidth 0 0 1 setrgbcolor newpath
    7777-465.576 -42.8564 moveto
    78 -559.078 -25.5413 -569.47 -23.6169 -644.498 -9.72286 curveto stroke
    79 newpath -656.297 -7.5378 moveto -643.77 -5.78973 lineto -645.226 -13.656 lineto closepath fill
    80 2 setlinewidth 0 0 1 setrgbcolor newpath
     78-550.335 -27.1603 -566.8 -24.1113 -625.027 -13.3286 curveto stroke
     79newpath -660.985 -6.66971 moveto -622.863 -1.64245 lineto -627.191 -25.0148 lineto closepath fill
     804.56973 setlinewidth 0 0 1 setrgbcolor newpath
    8181-574.666 -153.893 moveto
    82 -528.842 -107.252 -521.515 -99.794 -488.002 -65.683 curveto stroke
    83 newpath -479.592 -57.123 moveto -485.149 -68.4863 lineto -490.856 -62.8797 lineto closepath fill
    84 2 setlinewidth 1 0 0 setrgbcolor newpath
     82-535.911 -114.447 -524.692 -103.027 -501.88 -79.8085 curveto stroke
     83newpath -476.251 -53.7222 moveto -493.402 -88.1377 lineto -510.358 -71.4793 lineto closepath fill
     844.56973 setlinewidth 1 0 0 setrgbcolor newpath
    8585-490.901 120.777 moveto
    86 -480.122 51.1328 -478.519 40.7713 -470.47 -11.2329 curveto stroke
    87 newpath -468.635 -23.0917 moveto -474.423 -11.8447 lineto -466.517 -10.6212 lineto closepath fill
    88 2 setlinewidth 0 0 1 setrgbcolor newpath
     86-481.623 60.8277 -479.143 44.8049 -473.499 8.33636 curveto stroke
     87newpath -467.906 -27.8032 moveto -485.244 6.51862 lineto -461.754 10.1541 lineto closepath fill
     884.56973 setlinewidth 0 0 1 setrgbcolor newpath
    8989-675.963 -3.89604 moveto
    90 -632.116 -68.8235 -626.228 -77.5422 -592.575 -127.374 curveto stroke
    91 newpath -585.859 -137.319 moveto -595.89 -129.612 lineto -589.26 -125.135 lineto closepath fill
    92 2 setlinewidth 0 0 1 setrgbcolor newpath
     90-637.405 -60.9909 -628.201 -74.6206 -603.658 -110.963 curveto stroke
     91newpath -583.191 -141.27 moveto -613.507 -117.615 lineto -593.808 -104.312 lineto closepath fill
     924.56973 setlinewidth 0 0 1 setrgbcolor newpath
    9393-490.901 120.777 moveto
    94 -435.445 215.844 -430.107 224.995 -384.3 303.522 curveto stroke
    95 newpath -378.253 313.887 moveto -380.845 301.507 lineto -387.755 305.537 lineto closepath fill
    96 2 setlinewidth 0 0 1 setrgbcolor newpath
     94-439.75 208.465 -431.238 223.057 -394.278 286.417 curveto stroke
     95newpath -375.851 318.006 moveto -384.012 280.429 lineto -404.543 292.406 lineto closepath fill
     964.56973 setlinewidth 0 0 1 setrgbcolor newpath
    9797-266.879 114.933 moveto
    98 -367.067 117.547 -377.642 117.822 -458.912 119.943 curveto stroke
    99 newpath -470.908 120.255 moveto -458.807 123.941 lineto -459.016 115.944 lineto closepath fill
    100 2 setlinewidth 0 0 1 setrgbcolor newpath
     98-358.311 117.318 -375.109 117.756 -439.117 119.426 curveto stroke
     99newpath -475.674 120.38 moveto -438.807 131.307 lineto -439.426 107.545 lineto closepath fill
     1004.56973 setlinewidth 0 0 1 setrgbcolor newpath
    101101-368.176 331.163 moveto
    102 -322.511 233.685 -318.018 224.095 -280.454 143.911 curveto stroke
    103 newpath -275.364 133.044 moveto -284.076 142.214 lineto -276.832 145.608 lineto closepath fill
    104 2 setlinewidth 1 0 0 setrgbcolor newpath
     102-326.156 241.466 -318.997 226.186 -288.855 161.843 curveto stroke
     103newpath -273.341 128.727 moveto -299.617 156.801 lineto -278.092 166.885 lineto closepath fill
     1044.56973 setlinewidth 1 0 0 setrgbcolor newpath
    105105-266.879 114.933 moveto
    106 -224.004 235.52 -220.448 245.52 -184.094 347.765 curveto stroke
    107 newpath -180.074 359.072 moveto -180.325 346.425 lineto -187.863 349.105 lineto closepath fill
    108 2 setlinewidth 0 0 1 setrgbcolor newpath
     106-226.764 227.755 -221.069 243.774 -190.728 329.107 curveto stroke
     107newpath -178.477 363.564 moveto -179.53 325.126 lineto -201.926 333.089 lineto closepath fill
     1084.56973 setlinewidth 0 0 1 setrgbcolor newpath
    109109-251.294 -335.059 moveto
    110 -189.25 -303.624 -179.902 -298.887 -133.738 -275.498 curveto stroke
    111 newpath -123.034 -270.074 moveto -131.93 -279.066 lineto -135.546 -271.93 lineto closepath fill
    112 2 setlinewidth 0 0 1 setrgbcolor newpath
     110-198.044 -308.079 -183.61 -300.766 -151.402 -284.448 curveto stroke
     111newpath -118.781 -267.92 moveto -146.031 -295.049 lineto -156.774 -273.846 lineto closepath fill
     1124.56973 setlinewidth 0 0 1 setrgbcolor newpath
    113113-389.604 -136.361 moveto
    114 -327.15 -226.083 -321.098 -234.777 -269.576 -308.795 curveto stroke
    115 newpath -262.72 -318.644 moveto -272.859 -311.081 lineto -266.293 -306.51 lineto closepath fill
    116 2 setlinewidth 1 0 0 setrgbcolor newpath
     114-332.039 -219.059 -322.392 -232.919 -280.889 -292.543 curveto stroke
     115newpath -259.996 -322.557 moveto -290.643 -299.333 lineto -271.134 -285.753 lineto closepath fill
     1164.56973 setlinewidth 1 0 0 setrgbcolor newpath
    1171175.84406 175.322 moveto
    118 -76.0754 267.926 -83.1051 275.873 -152.172 353.948 curveto stroke
    119 newpath -160.122 362.936 moveto -149.176 356.598 lineto -155.168 351.298 lineto closepath fill
    120 2 setlinewidth 0 0 1 setrgbcolor newpath
     118-70.5724 261.706 -81.8227 274.423 -139.051 339.116 curveto stroke
     119newpath -163.281 366.507 moveto -130.149 346.991 lineto -147.953 331.242 lineto closepath fill
     1204.56973 setlinewidth 0 0 1 setrgbcolor newpath
    121121169.478 311.683 moveto
    122 96.8003 251.119 88.6819 244.353 30.4273 195.808 curveto stroke
    123 newpath 21.2086 188.126 moveto 27.8666 198.881 lineto 32.988 192.735 lineto closepath fill
    124 2 setlinewidth 0 0 1 setrgbcolor newpath
     122103.641 256.819 90.7821 246.103 45.6398 208.485 curveto stroke
     123newpath 17.546 185.074 moveto 38.0313 217.615 lineto 53.2483 199.355 lineto closepath fill
     1244.56973 setlinewidth 0 0 1 setrgbcolor newpath
    125125342.851 111.037 moveto
    126 263.766 202.563 256.831 210.589 190.4 287.47 curveto stroke
    127 newpath 182.554 296.55 moveto 193.427 290.085 lineto 187.373 284.855 lineto closepath fill
    128 2 setlinewidth 0 0 1 setrgbcolor newpath
     126269.224 196.246 258.132 209.083 203.347 272.486 curveto stroke
     127newpath 179.437 300.157 moveto 212.34 280.257 lineto 194.354 264.716 lineto closepath fill
     1284.56973 setlinewidth 0 0 1 setrgbcolor newpath
    1291295.84406 175.322 moveto
    130 163.16 145.314 173.605 143.321 311.418 117.033 curveto stroke
    131 newpath 323.205 114.784 moveto 310.668 113.104 lineto 312.167 120.962 lineto closepath fill
    132 2 setlinewidth 0 0 1 setrgbcolor newpath
     130155.419 146.79 172.221 143.585 291.966 120.743 curveto stroke
     131newpath 327.888 113.891 moveto 289.739 109.069 lineto 294.193 132.418 lineto closepath fill
     1324.56973 setlinewidth 0 0 1 setrgbcolor newpath
    133133342.851 111.037 moveto
    134 497.255 2.58683 505.964 -3.53033 643.932 -100.436 curveto stroke
    135 newpath 653.752 -107.334 moveto 641.633 -103.71 lineto 646.231 -97.163 lineto closepath fill
    136 2 setlinewidth 0 0 1 setrgbcolor newpath
     134490.978 6.99574 505.015 -2.86383 627.727 -89.0547 curveto stroke
     135newpath 657.653 -110.074 moveto 620.896 -98.7802 lineto 634.558 -79.3291 lineto closepath fill
     1364.56973 setlinewidth 0 0 1 setrgbcolor newpath
    137137364.28 -222.074 moveto
    138 354.298 -66.9063 353.616 -56.2971 344.905 79.1029 curveto stroke
    139 newpath 344.135 91.0781 moveto 348.897 79.3597 lineto 340.914 78.8461 lineto closepath fill
    140 2 setlinewidth 0 0 1 setrgbcolor newpath
     138354.807 -74.8128 353.709 -57.7536 346.177 59.3416 curveto stroke
     139newpath 343.829 95.836 moveto 358.037 60.1045 lineto 334.316 58.5786 lineto closepath fill
     1404.56973 setlinewidth 0 0 1 setrgbcolor newpath
    141141670.118 -118.829 moveto
    142 528.037 -166.793 517.967 -170.192 394.599 -211.839 curveto stroke
    143 newpath 383.229 -215.677 moveto 393.32 -208.049 lineto 395.878 -215.629 lineto closepath fill
    144 2 setlinewidth 1 0 0 setrgbcolor newpath
     142535.595 -164.241 519.412 -169.704 413.361 -205.505 curveto stroke
     143newpath 378.712 -217.202 moveto 409.559 -194.245 lineto 417.162 -216.766 lineto closepath fill
     1444.56973 setlinewidth 1 0 0 setrgbcolor newpath
    145145-105.193 -261.035 moveto
    146 118.401 -242.479 129.015 -241.598 332.39 -224.721 curveto stroke
    147 newpath 344.348 -223.728 moveto 332.72 -228.707 lineto 332.059 -220.734 lineto closepath fill
    148 2 setlinewidth 0 0 1 setrgbcolor newpath
     146110.939 -243.099 128.069 -241.677 312.655 -226.358 curveto stroke
     147newpath 349.1 -223.334 moveto 313.638 -238.202 lineto 311.672 -214.514 lineto closepath fill
     1484.56973 setlinewidth 0 0 1 setrgbcolor newpath
    149149-105.193 -261.035 moveto
    150 -160.867 -161.176 -166.028 -151.918 -212.336 -68.858 curveto stroke
    151 newpath -218.179 -58.3769 moveto -208.842 -66.9102 lineto -215.829 -70.8058 lineto closepath fill
    152 2 setlinewidth 0 0 1 setrgbcolor newpath
     150-156.746 -168.566 -164.987 -153.784 -202.693 -86.1539 curveto stroke
     151newpath -220.5 -54.2129 moveto -192.312 -80.3665 lineto -213.073 -91.9413 lineto closepath fill
     1524.56973 setlinewidth 0 0 1 setrgbcolor newpath
    153153-227.918 -40.9084 moveto
    154 -298.35 -82.4884 -307.42 -87.8432 -362.048 -120.093 curveto stroke
    155 newpath -372.381 -126.193 moveto -364.081 -116.648 lineto -360.014 -123.537 lineto closepath fill
     154-290.327 -77.7521 -304.558 -86.1532 -344.995 -110.026 curveto stroke
     155newpath -376.487 -128.617 moveto -351.037 -99.7914 lineto -338.953 -120.26 lineto closepath fill
    156156grestore
    157157%Nodes:
    158158gsave
    159 -389.604 -136.361 20 0 1 0 nc
    160 -227.918 -40.9084 20 0 1 0 nc
    161 -105.193 -261.035 20 0 1 0 nc
    162 364.28 -222.074 20 1 1 0 nc
    163 670.118 -118.829 20 1 1 0 nc
    164 342.851 111.037 20 1 1 0 nc
    165 5.84406 175.322 20 1 1 0 nc
    166 169.478 311.683 20 1 1 0 nc
    167 -173.374 377.916 20 1 0 1 nc
    168 -251.294 -335.059 20 0 1 0 nc
    169 -266.879 114.933 20 0 0 0 nc
    170 -368.176 331.163 20 0 0 0 nc
    171 -490.901 120.777 20 0 0 0 nc
    172 -574.666 -153.893 20 1 0 0 nc
    173 -675.963 -3.89604 20 1 0 0 nc
    174 -465.576 -42.8564 20 1 0 0 nc
    175 44.8044 15.5841 20 0 0 1 nc
    176 157.79 -130.517 20 0 0 1 nc
    177 218.178 27.2723 20 0 0 1 nc
     159-389.604 -136.361 15.2324 0 1 0 nc
     160-227.918 -40.9084 15.2324 0 1 0 nc
     161-105.193 -261.035 15.2324 0 1 0 nc
     162364.28 -222.074 15.2324 1 1 0 nc
     163670.118 -118.829 15.2324 1 1 0 nc
     164342.851 111.037 15.2324 1 1 0 nc
     1655.84406 175.322 15.2324 1 1 0 nc
     166169.478 311.683 15.2324 1 1 0 nc
     167-173.374 377.916 15.2324 1 0 1 nc
     168-251.294 -335.059 15.2324 0 1 0 nc
     169-266.879 114.933 15.2324 0 0 0 nc
     170-368.176 331.163 15.2324 0 0 0 nc
     171-490.901 120.777 15.2324 0 0 0 nc
     172-574.666 -153.893 15.2324 1 0 0 nc
     173-675.963 -3.89604 15.2324 1 0 0 nc
     174-465.576 -42.8564 15.2324 1 0 0 nc
     17544.8044 15.5841 15.2324 0 0 1 nc
     176157.79 -130.517 15.2324 0 0 1 nc
     177218.178 27.2723 15.2324 0 0 1 nc
    178178grestore
    179179grestore
  • doc/lgf.dox

    r1192 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6565
    6666The \e LGF files can also contain bipartite graphs, in this case a
    67 \c @red_nodes and a \c @blue_nodes sections describe the node set of the
     67\c \@red_nodes and a \c \@blue_nodes sections describe the node set of the
    6868graph. If a map is in both of these sections, then it can be used as a
    6969regular node map.
  • doc/mainpage.dox.in

    r1039 r1221  
    2626It is a C++ template library providing efficient implementations of common
    2727data structures and algorithms with focus on combinatorial optimization
    28 tasks connected mainly with graphs and networks.
     28tasks connected mainly with graphs and networks \cite DezsoJuttnerKovacs11Lemon.
    2929
    3030<b>
     
    3838The project is maintained by the
    3939<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
    40 Combinatorial Optimization</a> \ref egres
     40Combinatorial Optimization</a> \cite egres
    4141at the Operations Research Department of the
    4242<a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,
    4343Budapest, Hungary.
    4444LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
    45 initiative \ref coinor.
     45initiative \cite coinor.
    4646
    4747\section howtoread How to Read the Documentation
  • doc/min_cost_flow.dox

    r1164 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2727minimum total cost from a set of supply nodes to a set of demand nodes
    2828in a network with capacity constraints (lower and upper bounds)
    29 and arc costs \ref amo93networkflows.
     29and arc costs \cite amo93networkflows.
    3030
    3131Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
  • doc/references.bib

    r1164 r1219  
    2020                  {O}perations {R}esearch},
    2121  url =          {http://www.coin-or.org/}
     22}
     23
     24
     25%%%%% Papers related to LEMON %%%%%
     26
     27@article{DezsoJuttnerKovacs11Lemon,
     28  author =       {B. Dezs{\H o} and A. J\"uttner and P. Kov\'acs},
     29  title =        {{LEMON} -- an open source {C++} graph template library},
     30  journal =      {Electronic Notes in Theoretical Computer Science},
     31  volume =       {264},
     32  pages =        {23--45},
     33  year =         {2011},
     34  note =         {Proc. 2nd Workshop on Generative Technologies}
     35}
     36
     37@article{KiralyKovacs12MCF,
     38  author =       {Z. Kir\'aly and P. Kov\'acs},
     39  title =        {Efficient implementations of minimum-cost flow algorithms},
     40  journal =      {Acta Universitatis Sapientiae, Informatica},
     41  year =         {2012},
     42  volume =       {4},
     43  pages =        {67--118}
    2244}
    2345
  • lemon/CMakeLists.txt

    r1133 r1264  
    3737IF(LEMON_HAVE_CPLEX)
    3838  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
    39   INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
     39  INCLUDE_DIRECTORIES(${ILOG_INCLUDE_DIRS})
    4040ENDIF()
    4141
     
    4848  SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
    4949  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
     50ENDIF()
     51
     52IF(LEMON_HAVE_SOPLEX)
     53  SET(LEMON_SOURCES ${LEMON_SOURCES} soplex.cc)
     54  INCLUDE_DIRECTORIES(${SOPLEX_INCLUDE_DIRS})
    5055ENDIF()
    5156
  • lemon/adaptors.h

    r1159 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/assert.h

    r463 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    200200                             ::lemon::_assert_bits::cstringify(msg),    \
    201201                             #exp), 0)))
    202 #    if LEMON_ENABLE_DEBUG
     202#    if defined LEMON_ENABLE_DEBUG
    203203#      define LEMON_DEBUG(exp, msg)                                     \
    204204         (static_cast<void> (!!(exp) ? 0 : (                            \
  • lemon/base.cc

    r554 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2222#include<lemon/tolerance.h>
    2323#include<lemon/core.h>
     24#include<lemon/time_measure.h>
    2425namespace lemon {
    2526
     
    3233#endif
    3334
     35  TimeStamp::Format TimeStamp::_format = TimeStamp::NORMAL;
     36
    3437} //namespace lemon
  • lemon/bellman_ford.h

    r960 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    150150  /// This class provides an efficient implementation of the Bellman-Ford
    151151  /// algorithm. The maximum time complexity of the algorithm is
    152   /// <tt>O(ne)</tt>.
     152  /// <tt>O(nm)</tt>.
    153153  ///
    154154  /// The Bellman-Ford algorithm solves the single-source shortest path
     
    201201    /// The type of the paths.
    202202    typedef PredMapPath<Digraph, PredMap> Path;
    203     ///\brief The \ref BellmanFordDefaultOperationTraits
     203    ///\brief The \ref lemon::BellmanFordDefaultOperationTraits
    204204    /// "operation traits class" of the algorithm.
    205205    typedef typename TR::OperationTraits OperationTraits;
    206206
    207     ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
     207    ///\brief The \ref lemon::BellmanFordDefaultTraits "traits class"
     208    ///of the algorithm.
    208209    typedef TR Traits;
    209210
  • lemon/bfs.h

    r1127 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    153153    typedef PredMapPath<Digraph, PredMap> Path;
    154154
    155     ///The \ref BfsDefaultTraits "traits class" of the algorithm.
     155    ///The \ref lemon::BfsDefaultTraits "traits class" of the algorithm.
    156156    typedef TR Traits;
    157157
  • lemon/bin_heap.h

    r758 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/alteration_notifier.h

    r1131 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/array_map.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/bezier.h

    r1157 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/default_map.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/edge_set_extender.h

    r1161 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/graph_adaptor_extender.h

    r965 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/graph_extender.h

    r1195 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    844844
    845845    typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
    846     typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier; 
     846    typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;
    847847    typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;
    848848    typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;
  • lemon/bits/lock.h

    r1131 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2012
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3434    public:
    3535      Lock() {
    36         pthread_mutex_init(&_lock, 0);
     36        pthread_mutex_init(&_lock, 0);
    3737      }
    3838      ~Lock() {
    39         pthread_mutex_destroy(&_lock);
     39        pthread_mutex_destroy(&_lock);
    4040      }
    4141      void lock() {
    42         pthread_mutex_lock(&_lock);
     42        pthread_mutex_lock(&_lock);
    4343      }
    4444      void unlock() {
    45         pthread_mutex_unlock(&_lock);
     45        pthread_mutex_unlock(&_lock);
    4646      }
    4747
     
    5858      void lock() {}
    5959      void unlock() {}
    60     };   
     60    };
    6161#endif
    6262  }
  • lemon/bits/map_extender.h

    r867 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/path_dump.h

    r973 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/solver_bits.h

    r1142 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/traits.h

    r1194 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/windows.cc

    r1163 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    141141#endif
    142142    }
    143    
     143
    144144    WinLock::~WinLock() {
    145145#ifdef WIN32
  • lemon/bits/windows.h

    r1131 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/capacity_scaling.h

    r1297 r1298  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6767  /// \ref CapacityScaling implements the capacity scaling version
    6868  /// of the successive shortest path algorithm for finding a
    69   /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
    70   /// \ref edmondskarp72theoretical. It is an efficient dual
    71   /// solution method.
     69  /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows,
     70  /// \cite edmondskarp72theoretical. It is an efficient dual
     71  /// solution method, which runs in polynomial time
     72  /// \f$O(m\log U (n+m)\log n)\f$, where <i>U</i> denotes the maximum
     73  /// of node supply and arc capacity values.
    7274  ///
    7375  /// This algorithm is typically slower than \ref CostScaling and
     
    117119    typedef typename TR::Heap Heap;
    118120
    119     /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
     121    /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class"
     122    /// of the algorithm
    120123    typedef TR Traits;
    121124
     
    643646    ///
    644647    /// This function returns the total cost of the found flow.
    645     /// Its complexity is O(e).
     648    /// Its complexity is O(m).
    646649    ///
    647650    /// \note The return type of the function can be specified as a
     
    835838      return OPTIMAL;
    836839    }
    837    
     840
    838841    // Check if the upper bound is greater than or equal to the lower bound
    839842    // on each forward arc.
  • lemon/cbc.cc

    r1161 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/cbc.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
    19 // -*- C++ -*-
    2019#ifndef LEMON_CBC_H
    2120#define LEMON_CBC_H
  • lemon/christofides_tsp.h

    r1205 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3131
    3232namespace lemon {
    33  
     33
    3434  /// \ingroup tsp
    3535  ///
     
    109109          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
    110110        }
    111        
     111
    112112        // Compute min. cost spanning tree
    113113        std::vector<Edge> tree;
    114114        kruskal(_gr, _cost, std::back_inserter(tree));
    115        
     115
    116116        FullGraph::NodeMap<int> deg(_gr, 0);
    117117        for (int i = 0; i != int(tree.size()); ++i) {
     
    126126          if (deg[u] % 2 == 1) odd_nodes.push_back(u);
    127127        }
    128  
     128
    129129        SmartGraph sgr;
    130130        SmartGraph::EdgeMap<Cost> scost(sgr);
     
    140140          }
    141141        }
    142        
     142
    143143        // Compute min. cost perfect matching
    144144        MaxWeightedPerfectMatching<SmartGraph, SmartGraph::EdgeMap<Cost> >
    145145          mwpm(sgr, scost);
    146146        mwpm.run();
    147        
     147
    148148        for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) {
    149149          if (mwpm.matching(e)) {
     
    152152          }
    153153        }
    154        
    155         // Join the spanning tree and the matching       
     154
     155        // Join the spanning tree and the matching
    156156        sgr.clear();
    157157        for (int i = 0; i != _gr.nodeNum(); ++i) {
     
    183183
    184184      /// @}
    185      
     185
    186186      /// \name Query Functions
    187187      /// @{
    188      
     188
    189189      /// \brief The total cost of the found tour.
    190190      ///
     
    195195        return _sum;
    196196      }
    197      
     197
    198198      /// \brief Returns a const reference to the node sequence of the
    199199      /// found tour.
     
    228228        std::copy(_path.begin(), _path.end(), out);
    229229      }
    230      
     230
    231231      /// \brief Gives back the found tour as a path.
    232232      ///
    233233      /// This function copies the found tour as a list of arcs/edges into
    234       /// the given \ref concept::Path "path structure".
     234      /// the given \ref lemon::concepts::Path "path structure".
    235235      ///
    236236      /// \pre run() must be called before using this function.
     
    245245        }
    246246      }
    247      
     247
    248248      /// @}
    249      
     249
    250250  };
    251251
  • lemon/circulation.h

    r1159 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    196196  public:
    197197
    198     ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
     198    /// \brief The \ref lemon::CirculationDefaultTraits "traits class"
     199    /// of the algorithm.
    199200    typedef TR Traits;
    200201    ///The type of the digraph the algorithm runs on.
  • lemon/clp.cc

    r1142 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/clp.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/concept_check.h

    r1157 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    5959#if !defined(NDEBUG)
    6060    void (Concept::*x)() = & Concept::constraints;
    61     ignore_unused_variable_warning(x);
     61    ::lemon::ignore_unused_variable_warning(x);
    6262#endif
    6363  }
     
    6969    typedef typename Concept::template Constraints<Type> ConceptCheck;
    7070    void (ConceptCheck::*x)() = & ConceptCheck::constraints;
    71     ignore_unused_variable_warning(x);
     71    ::lemon::ignore_unused_variable_warning(x);
    7272#endif
    7373  }
  • lemon/concepts/bpgraph.h

    r1196 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    524524        /// Sets the iterator to the first arc of the given graph.
    525525        ///
    526         explicit ArcIt(const BpGraph &g) { ignore_unused_variable_warning(g); }
     526        explicit ArcIt(const BpGraph &g)
     527        {
     528          ::lemon::ignore_unused_variable_warning(g);
     529        }
    527530        /// Sets the iterator to the given arc.
    528531
     
    570573        ///
    571574        OutArcIt(const BpGraph& n, const Node& g) {
    572           ignore_unused_variable_warning(n);
    573           ignore_unused_variable_warning(g);
     575          ::lemon::ignore_unused_variable_warning(n);
     576          ::lemon::ignore_unused_variable_warning(g);
    574577        }
    575578        /// Sets the iterator to the given arc.
     
    618621        ///
    619622        InArcIt(const BpGraph& g, const Node& n) {
    620           ignore_unused_variable_warning(n);
    621           ignore_unused_variable_warning(g);
     623          ::lemon::ignore_unused_variable_warning(n);
     624          ::lemon::ignore_unused_variable_warning(g);
    622625        }
    623626        /// Sets the iterator to the given arc.
     
    802805
    803806      /// \brief Gives back the red end node of the edge.
    804       /// 
     807      ///
    805808      /// Gives back the red end node of the edge.
    806809      RedNode redNode(const Edge&) const { return RedNode(); }
    807810
    808811      /// \brief Gives back the blue end node of the edge.
    809       /// 
     812      ///
    810813      /// Gives back the blue end node of the edge.
    811814      BlueNode blueNode(const Edge&) const { return BlueNode(); }
     
    9981001      /// \brief The base node of the iterator.
    9991002      ///
    1000       /// Returns the base node of the given incomming arc iterator
     1003      /// Returns the base node of the given incoming arc iterator
    10011004      /// (i.e. the target node of the corresponding arc).
    10021005      Node baseNode(InArcIt) const { return INVALID; }
     
    10041007      /// \brief The running node of the iterator.
    10051008      ///
    1006       /// Returns the running node of the given incomming arc iterator
     1009      /// Returns the running node of the given incoming arc iterator
    10071010      /// (i.e. the source node of the corresponding arc).
    10081011      Node runningNode(InArcIt) const { return INVALID; }
  • lemon/concepts/digraph.h

    r956 r1271  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    313313        /// Sets the iterator to the first arc of the given digraph.
    314314        ///
    315         explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
     315        explicit ArcIt(const Digraph& g) {
     316          ::lemon::ignore_unused_variable_warning(g);
     317        }
    316318        /// Sets the iterator to the given arc.
    317319
     
    410412      /// \brief The base node of the iterator.
    411413      ///
    412       /// Returns the base node of the given incomming arc iterator
     414      /// Returns the base node of the given incoming arc iterator
    413415      /// (i.e. the target node of the corresponding arc).
    414416      Node baseNode(InArcIt) const { return INVALID; }
     
    416418      /// \brief The running node of the iterator.
    417419      ///
    418       /// Returns the running node of the given incomming arc iterator
     420      /// Returns the running node of the given incoming arc iterator
    419421      /// (i.e. the source node of the corresponding arc).
    420422      Node runningNode(InArcIt) const { return INVALID; }
  • lemon/concepts/graph.h

    r1186 r1271  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    397397        /// Sets the iterator to the first arc of the given graph.
    398398        ///
    399         explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
     399        explicit ArcIt(const Graph &g) {
     400          ::lemon::ignore_unused_variable_warning(g);
     401        }
    400402        /// Sets the iterator to the given arc.
    401403
     
    443445        ///
    444446        OutArcIt(const Graph& n, const Node& g) {
    445           ignore_unused_variable_warning(n);
    446           ignore_unused_variable_warning(g);
     447          ::lemon::ignore_unused_variable_warning(n);
     448          ::lemon::ignore_unused_variable_warning(g);
    447449        }
    448450        /// Sets the iterator to the given arc.
     
    491493        ///
    492494        InArcIt(const Graph& g, const Node& n) {
    493           ignore_unused_variable_warning(n);
    494           ignore_unused_variable_warning(g);
     495          ::lemon::ignore_unused_variable_warning(n);
     496          ::lemon::ignore_unused_variable_warning(g);
    495497        }
    496498        /// Sets the iterator to the given arc.
     
    758760      /// \brief The base node of the iterator.
    759761      ///
    760       /// Returns the base node of the given incomming arc iterator
     762      /// Returns the base node of the given incoming arc iterator
    761763      /// (i.e. the target node of the corresponding arc).
    762764      Node baseNode(InArcIt) const { return INVALID; }
     
    764766      /// \brief The running node of the iterator.
    765767      ///
    766       /// Returns the running node of the given incomming arc iterator
     768      /// Returns the running node of the given incoming arc iterator
    767769      /// (i.e. the source node of the corresponding arc).
    768770      Node runningNode(InArcIt) const { return INVALID; }
  • lemon/concepts/graph_components.h

    r1196 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    109109
    110110          bool b;
    111           ignore_unused_variable_warning(b);
     111          ::lemon::ignore_unused_variable_warning(b);
    112112
    113113          b = (ia == ib) && (ia != ib);
     
    290290            ue = e;
    291291            bool d = graph.direction(e);
    292             ignore_unused_variable_warning(d);
     292            ::lemon::ignore_unused_variable_warning(d);
    293293          }
    294294        }
     
    392392
    393393      /// \brief Gives back the red end node of the edge.
    394       /// 
     394      ///
    395395      /// Gives back the red end node of the edge.
    396396      RedNode redNode(const Edge&) const { return RedNode(); }
    397397
    398398      /// \brief Gives back the blue end node of the edge.
    399       /// 
     399      ///
    400400      /// Gives back the blue end node of the edge.
    401401      BlueNode blueNode(const Edge&) const { return BlueNode(); }
     
    457457            rn = bpgraph.asRedNode(rnan);
    458458            bn = bpgraph.asBlueNode(bnan);
    459             ignore_unused_variable_warning(b);
     459            ::lemon::ignore_unused_variable_warning(b);
    460460          }
    461461        }
     
    535535
    536536          nid = digraph.maxNodeId();
    537           ignore_unused_variable_warning(nid);
     537          ::lemon::ignore_unused_variable_warning(nid);
    538538          eid = digraph.maxArcId();
    539           ignore_unused_variable_warning(eid);
     539          ::lemon::ignore_unused_variable_warning(eid);
    540540        }
    541541
     
    590590          edge = graph.edgeFromId(ueid);
    591591          ueid = graph.maxEdgeId();
    592           ignore_unused_variable_warning(ueid);
     592          ::lemon::ignore_unused_variable_warning(ueid);
    593593        }
    594594
     
    654654          rid = bpgraph.maxRedId();
    655655          bid = bpgraph.maxBlueId();
    656           ignore_unused_variable_warning(rid);
    657           ignore_unused_variable_warning(bid);
     656          ::lemon::ignore_unused_variable_warning(rid);
     657          ::lemon::ignore_unused_variable_warning(bid);
    658658        }
    659659
     
    727727          _GraphItemIt it3 = it1;
    728728          _GraphItemIt it4 = INVALID;
    729           ignore_unused_variable_warning(it3);
    730           ignore_unused_variable_warning(it4);
     729          ::lemon::ignore_unused_variable_warning(it3);
     730          ::lemon::ignore_unused_variable_warning(it4);
    731731
    732732          it2 = ++it1;
     
    818818          _GraphIncIt it3 = it1;
    819819          _GraphIncIt it4 = INVALID;
    820           ignore_unused_variable_warning(it3);
    821           ignore_unused_variable_warning(it4);
     820          ::lemon::ignore_unused_variable_warning(it3);
     821          ::lemon::ignore_unused_variable_warning(it4);
    822822
    823823          it2 = ++it1;
     
    876876      void next(Arc&) const {}
    877877
    878       /// \brief Return the first arc incomming to the given node.
    879       ///
    880       /// This function gives back the first arc incomming to the
     878      /// \brief Return the first arc incoming to the given node.
     879      ///
     880      /// This function gives back the first arc incoming to the
    881881      /// given node.
    882882      void firstIn(Arc&, const Node&) const {}
    883883
    884       /// \brief Return the next arc incomming to the given node.
    885       ///
    886       /// This function gives back the next arc incomming to the
     884      /// \brief Return the next arc incoming to the given node.
     885      ///
     886      /// This function gives back the next arc incoming to the
    887887      /// given node.
    888888      void nextIn(Arc&) const {}
     
    10011001            n = digraph.baseNode(oait);
    10021002            n = digraph.runningNode(oait);
    1003             ignore_unused_variable_warning(n);
     1003            ::lemon::ignore_unused_variable_warning(n);
    10041004          }
    10051005        }
     
    11511151      typedef typename Base::Arc Arc;
    11521152      typedef typename Base::Edge Edge;
    1153      
     1153
    11541154      typedef IterableBpGraphComponent BpGraph;
    11551155
     
    12111211          typename _BpGraph::RedNode rn(INVALID);
    12121212          bpgraph.first(rn);
    1213           bpgraph.next(rn); 
     1213          bpgraph.next(rn);
    12141214          typename _BpGraph::BlueNode bn(INVALID);
    12151215          bpgraph.first(bn);
     
    12781278            = digraph.notifier(typename _Digraph::Arc());
    12791279
    1280           ignore_unused_variable_warning(nn);
    1281           ignore_unused_variable_warning(en);
     1280          ::lemon::ignore_unused_variable_warning(nn);
     1281          ::lemon::ignore_unused_variable_warning(en);
    12821282        }
    12831283
     
    13261326          typename _Graph::EdgeNotifier& uen
    13271327            = graph.notifier(typename _Graph::Edge());
    1328           ignore_unused_variable_warning(uen);
     1328          ::lemon::ignore_unused_variable_warning(uen);
    13291329        }
    13301330
     
    13881388          typename _BpGraph::BlueNodeNotifier& bnn
    13891389            = bpgraph.notifier(typename _BpGraph::BlueNode());
    1390           ignore_unused_variable_warning(rnn);
    1391           ignore_unused_variable_warning(bnn);
     1390          ::lemon::ignore_unused_variable_warning(rnn);
     1391          ::lemon::ignore_unused_variable_warning(bnn);
    13921392        }
    13931393
     
    14621462          // m3 = cmap;
    14631463
    1464           ignore_unused_variable_warning(m1);
    1465           ignore_unused_variable_warning(m2);
    1466           // ignore_unused_variable_warning(m3);
     1464          ::lemon::ignore_unused_variable_warning(m1);
     1465          ::lemon::ignore_unused_variable_warning(m2);
     1466          // ::lemon::ignore_unused_variable_warning(m3);
    14671467        }
    14681468
  • lemon/concepts/heap.h

    r1127 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    261261          item=Item();
    262262          prio=Prio();
    263           ignore_unused_variable_warning(item);
    264           ignore_unused_variable_warning(prio);
     263          ::lemon::ignore_unused_variable_warning(item);
     264          ::lemon::ignore_unused_variable_warning(prio);
    265265
    266266          OwnItem own_item;
     
    269269          own_item=Item();
    270270          own_prio=Prio();
    271           ignore_unused_variable_warning(own_item);
    272           ignore_unused_variable_warning(own_prio);
    273           ignore_unused_variable_warning(own_state);
     271          ::lemon::ignore_unused_variable_warning(own_item);
     272          ::lemon::ignore_unused_variable_warning(own_prio);
     273          ::lemon::ignore_unused_variable_warning(own_state);
    274274
    275275          _Heap heap1(map);
    276276          _Heap heap2 = heap1;
    277           ignore_unused_variable_warning(heap1);
    278           ignore_unused_variable_warning(heap2);
     277          ::lemon::ignore_unused_variable_warning(heap1);
     278          ::lemon::ignore_unused_variable_warning(heap2);
    279279
    280280          int s = heap.size();
    281           ignore_unused_variable_warning(s);
     281          ::lemon::ignore_unused_variable_warning(s);
    282282          bool e = heap.empty();
    283           ignore_unused_variable_warning(e);
     283          ::lemon::ignore_unused_variable_warning(e);
    284284
    285285          prio = heap.prio();
  • lemon/concepts/maps.h

    r1157 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6161          own_val = m[own_key];
    6262
    63           ignore_unused_variable_warning(key);
    64           ignore_unused_variable_warning(val);
    65           ignore_unused_variable_warning(own_key);
    66           ignore_unused_variable_warning(own_val);
     63          ::lemon::ignore_unused_variable_warning(key);
     64          ::lemon::ignore_unused_variable_warning(val);
     65          ::lemon::ignore_unused_variable_warning(own_key);
     66          ::lemon::ignore_unused_variable_warning(own_val);
    6767        }
    6868        const Key& key;
     
    101101          m.set(own_key, own_val);
    102102
    103           ignore_unused_variable_warning(key);
    104           ignore_unused_variable_warning(val);
    105           ignore_unused_variable_warning(own_key);
    106           ignore_unused_variable_warning(own_val);
     103          ::lemon::ignore_unused_variable_warning(key);
     104          ::lemon::ignore_unused_variable_warning(val);
     105          ::lemon::ignore_unused_variable_warning(own_key);
     106          ::lemon::ignore_unused_variable_warning(own_val);
    107107        }
    108108        const Key& key;
  • lemon/concepts/path.h

    r1127 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7676      template <typename CPath>
    7777      Path& operator=(const CPath& cpath) {
    78         ignore_unused_variable_warning(cpath);
     78        ::lemon::ignore_unused_variable_warning(cpath);
    7979        return *this;
    8080      }
     
    136136          e = (i < ii);
    137137
    138           ignore_unused_variable_warning(l);
    139           ignore_unused_variable_warning(pp);
    140           ignore_unused_variable_warning(e);
    141           ignore_unused_variable_warning(id);
    142           ignore_unused_variable_warning(ii);
    143           ignore_unused_variable_warning(ed);
     138          ::lemon::ignore_unused_variable_warning(l);
     139          ::lemon::ignore_unused_variable_warning(pp);
     140          ::lemon::ignore_unused_variable_warning(e);
     141          ::lemon::ignore_unused_variable_warning(id);
     142          ::lemon::ignore_unused_variable_warning(ii);
     143          ::lemon::ignore_unused_variable_warning(ed);
    144144        }
    145145      };
     
    163163          e = (i != INVALID);
    164164
    165           ignore_unused_variable_warning(l);
    166           ignore_unused_variable_warning(e);
    167           ignore_unused_variable_warning(id);
    168           ignore_unused_variable_warning(ed);
     165          ::lemon::ignore_unused_variable_warning(l);
     166          ::lemon::ignore_unused_variable_warning(e);
     167          ::lemon::ignore_unused_variable_warning(id);
     168          ::lemon::ignore_unused_variable_warning(ed);
    169169        }
    170170        _Path& p;
     
    189189          e = (i != INVALID);
    190190
    191           ignore_unused_variable_warning(l);
    192           ignore_unused_variable_warning(e);
    193           ignore_unused_variable_warning(id);
    194           ignore_unused_variable_warning(ed);
     191          ::lemon::ignore_unused_variable_warning(l);
     192          ::lemon::ignore_unused_variable_warning(e);
     193          ::lemon::ignore_unused_variable_warning(id);
     194          ::lemon::ignore_unused_variable_warning(ed);
    195195        }
    196196        _Path& p;
  • lemon/config.h.in

    r1133 r1264  
    55#cmakedefine LEMON_HAVE_GLPK 1
    66#cmakedefine LEMON_HAVE_CPLEX 1
     7#cmakedefine LEMON_HAVE_SOPLEX 1
    78#cmakedefine LEMON_HAVE_CLP 1
    89#cmakedefine LEMON_HAVE_CBC 1
     10#cmakedefine LEMON_DEFAULT_LP @LEMON_DEFAULT_LP@
     11#cmakedefine LEMON_DEFAULT_MIP @LEMON_DEFAULT_MIP@
    912#cmakedefine LEMON_USE_PTHREAD 1
    1013#cmakedefine LEMON_USE_WIN32_THREADS 1
  • lemon/connectivity.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    746746  ///
    747747  /// This function checks whether the given undirected graph is
    748   /// bi-node-connected, i.e. any two edges are on same circle.
     748  /// bi-node-connected, i.e. a connected graph without articulation
     749  /// node.
    749750  ///
    750751  /// \return \c true if the graph bi-node-connected.
    751   /// \note By definition, the empty graph is bi-node-connected.
     752  ///
     753  /// \note By definition,
     754  /// \li a graph consisting of zero or one node is bi-node-connected,
     755  /// \li a graph consisting of two isolated nodes
     756  /// is \e not bi-node-connected and
     757  /// \li a graph consisting of two nodes connected by an edge
     758  /// is bi-node-connected.
    752759  ///
    753760  /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
    754761  template <typename Graph>
    755762  bool biNodeConnected(const Graph& graph) {
     763    bool hasNonIsolated = false, hasIsolated = false;
     764    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
     765      if (typename Graph::OutArcIt(graph, n) == INVALID) {
     766        if (hasIsolated || hasNonIsolated) {
     767          return false;
     768        } else {
     769          hasIsolated = true;
     770        }
     771      } else {
     772        if (hasIsolated) {
     773          return false;
     774        } else {
     775          hasNonIsolated = true;
     776        }
     777      }
     778    }
    756779    return countBiNodeConnectedComponents(graph) <= 1;
    757780  }
  • lemon/core.h

    r1195 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3636#ifdef _MSC_VER
    3737#pragma warning( disable : 4250 4355 4503 4800 4996 )
     38#endif
     39
     40#ifdef __GNUC__
     41#define GCC_VERSION (__GNUC__ * 10000                   \
     42                     + __GNUC_MINOR__ * 100             \
     43                     + __GNUC_PATCHLEVEL__)
     44#endif
     45
     46#if GCC_VERSION >= 40800
     47// Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8
     48#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
    3849#endif
    3950
     
    244255
    245256  namespace _graph_utils_bits {
    246    
     257
    247258    template <typename Graph, typename Enable = void>
    248259    struct CountRedNodesSelector {
     
    254265    template <typename Graph>
    255266    struct CountRedNodesSelector<
    256       Graph, typename 
    257       enable_if<typename Graph::NodeNumTag, void>::type> 
     267      Graph, typename
     268      enable_if<typename Graph::NodeNumTag, void>::type>
    258269    {
    259270      static int count(const Graph &g) {
    260271        return g.redNum();
    261272      }
    262     };   
     273    };
    263274  }
    264275
     
    269280  /// graph structures it is specialized to run in O(1).
    270281  ///
    271   /// If the graph contains a \e redNum() member function and a 
     282  /// If the graph contains a \e redNum() member function and a
    272283  /// \e NodeNumTag tag then this function calls directly the member
    273284  /// function to query the cardinality of the node set.
     
    278289
    279290  namespace _graph_utils_bits {
    280    
     291
    281292    template <typename Graph, typename Enable = void>
    282293    struct CountBlueNodesSelector {
     
    288299    template <typename Graph>
    289300    struct CountBlueNodesSelector<
    290       Graph, typename 
    291       enable_if<typename Graph::NodeNumTag, void>::type> 
     301      Graph, typename
     302      enable_if<typename Graph::NodeNumTag, void>::type>
    292303    {
    293304      static int count(const Graph &g) {
    294305        return g.blueNum();
    295306      }
    296     };   
     307    };
    297308  }
    298309
     
    303314  /// graph structures it is specialized to run in O(1).
    304315  ///
    305   /// If the graph contains a \e blueNum() member function and a 
     316  /// If the graph contains a \e blueNum() member function and a
    306317  /// \e NodeNumTag tag then this function calls directly the member
    307318  /// function to query the cardinality of the node set.
     
    18551866    /// The Digraph type
    18561867    typedef GR Digraph;
    1857    
     1868
    18581869  protected:
    18591870
  • lemon/cost_scaling.h

    r1297 r1298  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9292  /// \ref CostScaling implements a cost scaling algorithm that performs
    9393  /// push/augment and relabel operations for finding a \ref min_cost_flow
    94   /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
    95   /// \ref goldberg97efficient, \ref bunnagel98efficient.
     94  /// "minimum cost flow" \cite amo93networkflows,
     95  /// \cite goldberg90approximation,
     96  /// \cite goldberg97efficient, \cite bunnagel98efficient.
    9697  /// It is a highly efficient primal-dual solution method, which
    9798  /// can be viewed as the generalization of the \ref Preflow
    9899  /// "preflow push-relabel" algorithm for the maximum flow problem.
     100  /// It is a polynomial algorithm, its running time complexity is
     101  /// \f$O(n^2m\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
    99102  ///
    100103  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
     
    151154    typedef typename TR::LargeCost LargeCost;
    152155
    153     /// The \ref CostScalingDefaultTraits "traits class" of the algorithm
     156    /// \brief The \ref lemon::CostScalingDefaultTraits "traits class"
     157    /// of the algorithm
    154158    typedef TR Traits;
    155159
     
    211215    typedef std::vector<LargeCost> LargeCostVector;
    212216    typedef std::vector<char> BoolVector;
    213     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
     217    // Note: vector<char> is used instead of vector<bool>
     218    // for efficiency reasons
    214219
    215220  private:
     
    667672    ///
    668673    /// This function returns the total cost of the found flow.
    669     /// Its complexity is O(e).
     674    /// Its complexity is O(m).
    670675    ///
    671676    /// \note The return type of the function can be specified as a
     
    901906      return OPTIMAL;
    902907    }
    903    
     908
    904909    // Check if the upper bound is greater than or equal to the lower bound
    905910    // on each forward arc.
     
    12821287          _buckets[r] = _bucket_next[u];
    12831288
    1284           // Search the incomming arcs of u
     1289          // Search the incoming arcs of u
    12851290          LargeCost pi_u = _pi[u];
    12861291          int last_out = _first_out[u+1];
  • lemon/cplex.cc

    r1183 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    492492                   _message_enabled ? CPX_ON : CPX_OFF);
    493493  }
     494
     495  void CplexBase::_write(std::string file, std::string format) const
     496  {
     497    if(format == "MPS" || format == "LP")
     498      CPXwriteprob(cplexEnv(), cplexLp(), file.c_str(), format.c_str());
     499    else if(format == "SOL")
     500      CPXsolwrite(cplexEnv(), cplexLp(), file.c_str());
     501    else throw UnsupportedFormatError(format);
     502  }
     503
     504
    494505
    495506  // CplexLp members
  • lemon/cplex.h

    r793 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    151151    bool _message_enabled;
    152152
     153    void _write(std::string file, std::string format) const;
     154
    153155  public:
    154156
     
    171173    const cpxlp* cplexLp() const { return _prob; }
    172174
     175#ifdef DOXYGEN
     176    /// Write the problem or the solution to a file in the given format
     177
     178    /// This function writes the problem or the solution
     179    /// to a file in the given format.
     180    /// Trying to write in an unsupported format will trigger
     181    /// \ref lemon::LpBase::UnsupportedFormatError "UnsupportedFormatError".
     182    /// \param file The file path
     183    /// \param format The output file format.
     184    /// Supportted formats are "MPS", "LP" and "SOL".
     185    void write(std::string file, std::string format = "MPS") const {}
     186#endif
     187
    173188  };
    174189
  • lemon/cycle_canceling.h

    r1297 r1298  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4848  /// \ref CycleCanceling implements three different cycle-canceling
    4949  /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
    50   /// \ref amo93networkflows, \ref klein67primal,
    51   /// \ref goldberg89cyclecanceling.
     50  /// \cite amo93networkflows, \cite klein67primal,
     51  /// \cite goldberg89cyclecanceling.
    5252  /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
    5353  /// "Cancel-and-Tighten" algorithm, thus it is the default method.
    54   /// It runs in strongly polynomial time, but in practice, it is typically
    55   /// orders of magnitude slower than the scaling algorithms and
    56   /// \ref NetworkSimplex.
     54  /// It runs in strongly polynomial time \f$O(n^2 m^2 \log n)\f$,
     55  /// but in practice, it is typically orders of magnitude slower than
     56  /// the scaling algorithms and \ref NetworkSimplex.
    5757  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    5858  ///
     
    132132      /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
    133133      /// well-known strongly polynomial method
    134       /// \ref goldberg89cyclecanceling. It improves along a
     134      /// \cite goldberg89cyclecanceling. It improves along a
    135135      /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
    136       /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
     136      /// Its running time complexity is \f$O(n^2 m^3 \log n)\f$.
    137137      MINIMUM_MEAN_CYCLE_CANCELING,
    138138      /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
    139139      /// improved version of the previous method
    140       /// \ref goldberg89cyclecanceling.
     140      /// \cite goldberg89cyclecanceling.
    141141      /// It is faster both in theory and in practice, its running time
    142       /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
     142      /// complexity is \f$O(n^2 m^2 \log n)\f$.
    143143      CANCEL_AND_TIGHTEN
    144144    };
     
    576576    ///
    577577    /// This function returns the total cost of the found flow.
    578     /// Its complexity is O(e).
     578    /// Its complexity is O(m).
    579579    ///
    580580    /// \note The return type of the function can be specified as a
     
    783783      return OPTIMAL;
    784784    }
    785    
     785
    786786    // Check if the upper bound is greater than or equal to the lower bound
    787787    // on each forward arc.
     
    960960      buildResidualNetwork();
    961961      while (true) {
    962        
     962
    963963        typename HwMmc::TerminationCause hw_tc =
    964964            hw_mmc.findCycleMean(hw_iter_limit);
     
    976976          hw_mmc.findCycle();
    977977        }
    978        
     978
    979979        // Compute delta value
    980980        Value delta = INF;
  • lemon/dfs.h

    r1161 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    153153    typedef PredMapPath<Digraph, PredMap> Path;
    154154
    155     ///The \ref DfsDefaultTraits "traits class" of the algorithm.
     155    ///The \ref lemon::DfsDefaultTraits "traits class" of the algorithm.
    156156    typedef TR Traits;
    157157
  • lemon/dijkstra.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    228228    ///The heap type used by the algorithm.
    229229    typedef typename TR::Heap Heap;
    230     ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
    231     ///of the algorithm.
     230    /// \brief The \ref lemon::DijkstraDefaultOperationTraits
     231    /// "operation traits class" of the algorithm.
    232232    typedef typename TR::OperationTraits OperationTraits;
    233233
    234     ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
     234    ///The \ref lemon::DijkstraDefaultTraits "traits class" of the algorithm.
    235235    typedef TR Traits;
    236236
  • lemon/dimacs.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/edge_set.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/euler.h

    r1023 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/fractional_matching.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    124124  public:
    125125
    126     /// \brief The \ref MaxFractionalMatchingDefaultTraits "traits
    127     /// class" of the algorithm.
     126    /// \brief The \ref lemon::MaxFractionalMatchingDefaultTraits
     127    /// "traits class" of the algorithm.
    128128    typedef TR Traits;
    129129    /// The type of the graph the algorithm runs on.
  • lemon/full_graph.h

    r1193 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    875875    static int id(Arc e) { return e._id; }
    876876    static int id(Edge e) { return e._id; }
    877    
     877
    878878    static Node nodeFromId(int id) { return Node(id);}
    879879    static Arc arcFromId(int id) { return Arc(id);}
     
    905905      return n._id - _red_num;
    906906    }
    907        
     907
    908908    void clear() {
    909909      _red_num = 0; _blue_num = 0;
     
    911911    }
    912912
    913     Edge edge(const Node& u, const Node& v) const { 
     913    Edge edge(const Node& u, const Node& v) const {
    914914      if (u._id < _red_num) {
    915915        if (v._id < _red_num) {
     
    927927    }
    928928
    929     Arc arc(const Node& u, const Node& v) const { 
     929    Arc arc(const Node& u, const Node& v) const {
    930930      if (u._id < _red_num) {
    931931        if (v._id < _red_num) {
  • lemon/glpk.cc

    r1142 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    581581      break;
    582582    }
     583  }
     584
     585  void GlpkBase::_write(std::string file, std::string format) const
     586  {
     587    if(format == "MPS")
     588      glp_write_mps(lp, GLP_MPS_FILE, 0, file.c_str());
     589    else if(format == "LP")
     590      glp_write_lp(lp, 0, file.c_str());
     591    else throw UnsupportedFormatError(format);
    583592  }
    584593
     
    9991008  const char* GlpkMip::_solverName() const { return "GlpkMip"; }
    10001009
     1010
     1011
    10011012} //END OF NAMESPACE LEMON
  • lemon/glpk.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    116116    virtual void _messageLevel(MessageLevel level);
    117117
     118    virtual void _write(std::string file, std::string format) const;
     119
    118120  private:
    119121
     
    145147    int lpxCol(Col c) const { return cols(id(c)); }
    146148
     149#ifdef DOXYGEN
     150    /// Write the problem or the solution to a file in the given format
     151
     152    /// This function writes the problem or the solution
     153    /// to a file in the given format.
     154    /// Trying to write in an unsupported format will trigger
     155    /// \ref LpBase::UnsupportedFormatError.
     156    /// \param file The file path
     157    /// \param format The output file format.
     158    /// Supportted formats are "MPS" and "LP".
     159    void write(std::string file, std::string format = "MPS") const {}
     160#endif
     161
    147162  };
    148163
  • lemon/gomory_hu.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4747  ///
    4848  /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
    49   /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
     49  /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{m})\f$ overall
    5050  /// time complexity. It calculates a rooted Gomory-Hu tree.
    5151  /// The structure of the tree and the edge weights can be
  • lemon/graph_to_eps.h

    r1159 r1291  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    223223  using T::_copyright;
    224224
    225   using typename T::NodeTextColorType;
    226225  using T::CUST_COL;
    227226  using T::DIST_COL;
  • lemon/greedy_tsp.h

    r1205 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6868      Cost _sum;
    6969      std::vector<Node> _path;
    70      
     70
    7171    private:
    72    
     72
    7373      // Functor class to compare edges by their costs
    7474      class EdgeComp {
     
    229229      ///
    230230      /// This function copies the found tour as a list of arcs/edges into
    231       /// the given \ref concept::Path "path structure".
     231      /// the given \ref lemon::concepts::Path "path structure".
    232232      ///
    233233      /// \pre run() must be called before using this function.
  • lemon/grosso_locatelli_pullan_mc.h

    r1022 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4141  /// \ref GrossoLocatelliPullanMc implements the iterated local search
    4242  /// algorithm of Grosso, Locatelli, and Pullan for solving the \e maximum
    43   /// \e clique \e problem \ref grosso08maxclique.
     43  /// \e clique \e problem \cite grosso08maxclique.
    4444  /// It is to find the largest complete subgraph (\e clique) in an
    4545  /// undirected graph, i.e., the largest set of nodes where each
     
    121121    BoolMatrix _gr;
    122122    int _n;
    123    
     123
    124124    // Search options
    125125    bool _delta_based_restart;
    126126    int _restart_delta_limit;
    127  
     127
    128128    // Search limits
    129129    int _iteration_limit;
     
    443443    /// \name Execution Control
    444444    /// The \ref run() function can be used to execute the algorithm.\n
    445     /// The functions \ref iterationLimit(int), \ref stepLimit(int), and 
     445    /// The functions \ref iterationLimit(int), \ref stepLimit(int), and
    446446    /// \ref sizeLimit(int) can be used to specify various limits for the
    447447    /// search process.
    448    
     448
    449449    /// @{
    450    
     450
    451451    /// \brief Sets the maximum number of iterations.
    452452    ///
     
    460460    /// likely finds larger cliques. For smaller values, the algorithm is
    461461    /// faster but probably gives worse results.
    462     /// 
     462    ///
    463463    /// The default value is \c 1000.
    464464    /// \c -1 means that number of iterations is not limited.
     
    475475      return *this;
    476476    }
    477    
     477
    478478    /// \brief Sets the maximum number of search steps.
    479479    ///
     
    487487    /// likely finds larger cliques. For smaller values, the algorithm is
    488488    /// faster but probably gives worse results.
    489     /// 
     489    ///
    490490    /// The default value is \c -1, which means that number of steps
    491491    /// is not limited explicitly. However, the number of iterations is
     
    503503      return *this;
    504504    }
    505    
     505
    506506    /// \brief Sets the desired clique size.
    507507    ///
     
    509509    /// limit. If a clique of this size (or a larger one) is found, then the
    510510    /// algorithm terminates.
    511     /// 
     511    ///
    512512    /// This function is especially useful if you know an exact upper bound
    513     /// for the size of the cliques in the graph or if any clique above 
     513    /// for the size of the cliques in the graph or if any clique above
    514514    /// a certain size limit is sufficient for your application.
    515     /// 
     515    ///
    516516    /// The default value is \c -1, which means that the size limit is set to
    517517    /// the number of nodes in the graph.
     
    525525      return *this;
    526526    }
    527    
     527
    528528    /// \brief The maximum number of iterations.
    529529    ///
     
    535535      return _iteration_limit;
    536536    }
    537    
     537
    538538    /// \brief The maximum number of search steps.
    539539    ///
     
    545545      return _step_limit;
    546546    }
    547    
     547
    548548    /// \brief The desired clique size.
    549549    ///
     
    584584    /// \name Query Functions
    585585    /// The results of the algorithm can be obtained using these functions.\n
    586     /// The run() function must be called before using them. 
     586    /// The run() function must be called before using them.
    587587
    588588    /// @{
     
    677677
    678678  private:
    679  
     679
    680680    // Initialize search options and limits
    681681    void initOptions() {
     
    683683      _delta_based_restart = true;
    684684      _restart_delta_limit = 4;
    685      
     685
    686686      // Search limits
    687687      _iteration_limit = 1000;
  • lemon/hao_orlin.h

    r1019 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/hartmann_orlin_mmc.h

    r1164 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9999  /// This class implements the Hartmann-Orlin algorithm for finding
    100100  /// a directed cycle of minimum mean cost in a digraph
    101   /// \ref hartmann93finding, \ref dasdan98minmeancycle.
    102   /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
    103   /// it applies an efficient early termination scheme.
    104   /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
     101  /// \cite hartmann93finding, \cite dasdan98minmeancycle.
     102  /// This method is based on \ref KarpMmc "Karp"'s original algorithm, but
     103  /// applies an early termination scheme. It makes the algorithm
     104  /// significantly faster for some problem instances, but slower for others.
     105  /// The algorithm runs in time O(nm) and uses space O(n<sup>2</sup>+m).
    105106  ///
    106107  /// \tparam GR The type of the digraph the algorithm runs on.
     
    143144    ///
    144145    /// The path type of the found cycles.
    145     /// Using the \ref HartmannOrlinMmcDefaultTraits "default traits class",
     146    /// Using the \ref lemon::HartmannOrlinMmcDefaultTraits
     147    /// "default traits class",
    146148    /// it is \ref lemon::Path "Path<Digraph>".
    147149    typedef typename TR::Path Path;
    148150
    149     /// The \ref HartmannOrlinMmcDefaultTraits "traits class" of the algorithm
     151    /// \brief The
     152    /// \ref lemon::HartmannOrlinMmcDefaultTraits "traits class"
     153    /// of the algorithm
    150154    typedef TR Traits;
    151155
     
    275279    ///
    276280    /// If you don't call this function before calling \ref run() or
    277     /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    278     /// structure. The destuctor deallocates this automatically
     281    /// \ref findCycleMean(), a local \ref Path "path" structure
     282    /// will be allocated. The destuctor deallocates this automatically
    279283    /// allocated object, of course.
    280284    ///
  • lemon/howard_mmc.h

    r1178 r1271  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9999  /// This class implements Howard's policy iteration algorithm for finding
    100100  /// a directed cycle of minimum mean cost in a digraph
    101   /// \ref dasdan98minmeancycle, \ref dasdan04experimental.
     101  /// \cite dasdan98minmeancycle, \cite dasdan04experimental.
    102102  /// This class provides the most efficient algorithm for the
    103103  /// minimum mean cycle problem, though the best known theoretical
     
    143143    ///
    144144    /// The path type of the found cycles.
    145     /// Using the \ref HowardMmcDefaultTraits "default traits class",
     145    /// Using the \ref lemon::HowardMmcDefaultTraits "default traits class",
    146146    /// it is \ref lemon::Path "Path<Digraph>".
    147147    typedef typename TR::Path Path;
    148148
    149     /// The \ref HowardMmcDefaultTraits "traits class" of the algorithm
     149    /// The \ref lemon::HowardMmcDefaultTraits "traits class" of the algorithm
    150150    typedef TR Traits;
    151151
     
    156156    /// these values.
    157157    enum TerminationCause {
    158      
     158
    159159      /// No directed cycle can be found in the digraph.
    160160      NO_CYCLE = 0,
    161    
     161
    162162      /// Optimal solution (minimum cycle mean) is found.
    163163      OPTIMAL = 1,
     
    283283    ///
    284284    /// If you don't call this function before calling \ref run() or
    285     /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    286     /// structure. The destuctor deallocates this automatically
     285    /// \ref findCycleMean(), a local \ref Path "path" structure
     286    /// will be allocated. The destuctor deallocates this automatically
    287287    /// allocated object, of course.
    288288    ///
     
    357357    ///
    358358    /// \param limit  The maximum allowed number of iterations during
    359     /// the search process. Its default value implies that the algorithm 
     359    /// the search process. Its default value implies that the algorithm
    360360    /// runs until it finds the exact optimal solution.
    361361    ///
    362362    /// \return The termination cause of the search process.
    363     /// For more information, see \ref TerminationCause.
    364     TerminationCause findCycleMean(int limit = std::numeric_limits<int>::max()) {
     363    /// For more information, see \ref TerminationCause.
     364    TerminationCause findCycleMean(int limit =
     365                                   std::numeric_limits<int>::max()) {
    365366      // Initialize and find strongly connected components
    366367      init();
     
    390391          _best_node = _curr_node;
    391392        }
    392        
     393
    393394        if (iter_limit_reached) break;
    394395      }
  • lemon/insertion_tsp.h

    r1205 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    226226      ///
    227227      /// This function copies the found tour as a list of arcs/edges into
    228       /// the given \ref concept::Path "path structure".
     228      /// the given \ref lemon::concepts::Path "path structure".
    229229      ///
    230230      /// \pre run() must be called before using this function.
     
    361361              Node u = _notused[i];
    362362              Cost min_cost = costDiff(_tour.back(), _tour.front(), u);
    363               int min_pos = 0;             
     363              int min_pos = 0;
    364364              for (unsigned int j=1; j<_tour.size(); ++j) {
    365365                Cost curr_cost = costDiff(_tour[j-1], _tour[j], u);
     
    391391            _notused[min_node] = _notused.back();
    392392            _notused.pop_back();
    393            
     393
    394394            // Insert the selected node into the tour
    395395            const int ipos = _ins_pos[sn];
     
    406406              Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u);
    407407              Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u);
    408              
     408
    409409              if (nc1 <= curr_cost || nc2 <= curr_cost) {
    410410                // A new position is better than the old one
     
    421421                  // The minimum should be found again
    422422                  curr_cost = costDiff(_tour.back(), _tour.front(), u);
    423                   curr_pos = 0;             
     423                  curr_pos = 0;
    424424                  for (unsigned int j=1; j<_tour.size(); ++j) {
    425425                    Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u);
     
    434434                }
    435435              }
    436              
     436
    437437              _ins_cost[u] = curr_cost;
    438438              _ins_pos[u] = curr_pos;
  • lemon/karp_mmc.h

    r1164 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9999  /// This class implements Karp's algorithm for finding a directed
    100100  /// cycle of minimum mean cost in a digraph
    101   /// \ref karp78characterization, \ref dasdan98minmeancycle.
    102   /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
     101  /// \cite karp78characterization, \cite dasdan98minmeancycle.
     102  /// It runs in time O(nm) and uses space O(n<sup>2</sup>+m).
    103103  ///
    104104  /// \tparam GR The type of the digraph the algorithm runs on.
     
    141141    ///
    142142    /// The path type of the found cycles.
    143     /// Using the \ref KarpMmcDefaultTraits "default traits class",
     143    /// Using the \ref lemon::KarpMmcDefaultTraits "default traits class",
    144144    /// it is \ref lemon::Path "Path<Digraph>".
    145145    typedef typename TR::Path Path;
    146146
    147     /// The \ref KarpMmcDefaultTraits "traits class" of the algorithm
     147    /// The \ref lemon::KarpMmcDefaultTraits "traits class" of the algorithm
    148148    typedef TR Traits;
    149149
     
    271271    ///
    272272    /// If you don't call this function before calling \ref run() or
    273     /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    274     /// structure. The destuctor deallocates this automatically
     273    /// \ref findCycleMean(), a local \ref Path "path" structure
     274    /// will be allocated. The destuctor deallocates this automatically
    275275    /// allocated object, of course.
    276276    ///
  • lemon/kruskal.h

    r1025 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/lgf_reader.h

    r1198 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    12311231  /// \ingroup lemon_io
    12321232  ///
    1233   /// \brief Return a \ref DigraphReader class
    1234   ///
    1235   /// This function just returns a \ref DigraphReader class.
     1233  /// \brief Return a \ref lemon::DigraphReader "DigraphReader" class
     1234  ///
     1235  /// This function just returns a \ref lemon::DigraphReader
     1236  /// "DigraphReader" class.
    12361237  ///
    12371238  /// With this function a digraph can be read from an
     
    12531254  ///\endcode
    12541255  ///
    1255   /// For a complete documentation, please see the \ref DigraphReader
     1256  /// For a complete documentation, please see the
     1257  /// \ref lemon::DigraphReader "DigraphReader"
    12561258  /// class documentation.
    1257   /// \warning Don't forget to put the \ref DigraphReader::run() "run()"
     1259  /// \warning Don't forget to put the \ref lemon::DigraphReader::run() "run()"
    12581260  /// to the end of the parameter list.
    12591261  /// \relates DigraphReader
     
    21092111  /// \ingroup lemon_io
    21102112  ///
    2111   /// \brief Return a \ref GraphReader class
    2112   ///
    2113   /// This function just returns a \ref GraphReader class.
     2113  /// \brief Return a \ref lemon::GraphReader "GraphReader" class
     2114  ///
     2115  /// This function just returns a \ref lemon::GraphReader "GraphReader" class.
    21142116  ///
    21152117  /// With this function a graph can be read from an
     
    21272129  ///\endcode
    21282130  ///
    2129   /// For a complete documentation, please see the \ref GraphReader
     2131  /// For a complete documentation, please see the
     2132  /// \ref lemon::GraphReader "GraphReader"
    21302133  /// class documentation.
    2131   /// \warning Don't forget to put the \ref GraphReader::run() "run()"
     2134  /// \warning Don't forget to put the \ref lemon::GraphReader::run() "run()"
    21322135  /// to the end of the parameter list.
    21332136  /// \relates GraphReader
     
    26362639        _red_node_index.insert(std::make_pair(converter(map[n]), n));
    26372640      }
    2638       for (BlueNodeIt n(_graph); n != INVALID; ++n) {     
     2641      for (BlueNodeIt n(_graph); n != INVALID; ++n) {
    26392642        _blue_node_index.insert(std::make_pair(converter(map[n]), n));
    26402643      }
     
    31753178  /// \ingroup lemon_io
    31763179  ///
    3177   /// \brief Return a \ref BpGraphReader class
    3178   ///
    3179   /// This function just returns a \ref BpGraphReader class.
     3180  /// \brief Return a \ref lemon::BpGraphReader "BpGraphReader" class
     3181  ///
     3182  /// This function just returns a \ref lemon::BpGraphReader
     3183  /// "BpGraphReader" class.
    31803184  ///
    31813185  /// With this function a graph can be read from an
     
    31933197  ///\endcode
    31943198  ///
    3195   /// For a complete documentation, please see the \ref BpGraphReader
     3199  /// For a complete documentation, please see the
     3200  /// \ref lemon::BpGraphReader "BpGraphReader"
    31963201  /// class documentation.
    3197   /// \warning Don't forget to put the \ref BpGraphReader::run() "run()"
     3202  /// \warning Don't forget to put the \ref lemon::BpGraphReader::run() "run()"
    31983203  /// to the end of the parameter list.
    31993204  /// \relates BpGraphReader
  • lemon/lgf_writer.h

    r1198 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    186186      ValueStorage(const Value& value, const Converter& converter = Converter())
    187187        : _value(value), _converter(converter) {}
    188      
     188
    189189      virtual std::string get() {
    190190        return _converter(_value);
     
    945945  /// \ingroup lemon_io
    946946  ///
    947   /// \brief Return a \ref DigraphWriter class
    948   ///
    949   /// This function just returns a \ref DigraphWriter class.
     947  /// \brief Return a \ref lemon::DigraphWriter "DigraphWriter" class
     948  ///
     949  /// This function just returns a \ref lemon::DigraphWriter
     950  /// "DigraphWriter" class.
    950951  ///
    951952  /// With this function a digraph can be write to a file or output
     
    968969  ///\endcode
    969970  ///
    970   /// For a complete documentation, please see the \ref DigraphWriter
     971  /// For a complete documentation, please see the
     972  /// \ref lemon::DigraphWriter "DigraphWriter"
    971973  /// class documentation.
    972   /// \warning Don't forget to put the \ref DigraphWriter::run() "run()"
     974  /// \warning Don't forget to put the \ref lemon::DigraphWriter::run() "run()"
    973975  /// to the end of the parameter list.
    974976  /// \relates DigraphWriter
     
    15841586  /// \ingroup lemon_io
    15851587  ///
    1586   /// \brief Return a \ref GraphWriter class
    1587   ///
    1588   /// This function just returns a \ref GraphWriter class.
     1588  /// \brief Return a \ref lemon::GraphWriter "GraphWriter" class
     1589  ///
     1590  /// This function just returns a \ref lemon::GraphWriter "GraphWriter" class.
    15891591  ///
    15901592  /// With this function a graph can be write to a file or output
     
    16031605  ///\endcode
    16041606  ///
    1605   /// For a complete documentation, please see the \ref GraphWriter
     1607  /// For a complete documentation, please see the
     1608  /// \ref lemon::GraphWriter "GraphWriter"
    16061609  /// class documentation.
    1607   /// \warning Don't forget to put the \ref GraphWriter::run() "run()"
     1610  /// \warning Don't forget to put the \ref lemon::GraphWriter::run() "run()"
    16081611  /// to the end of the parameter list.
    16091612  /// \relates GraphWriter
     
    24022405  /// \ingroup lemon_io
    24032406  ///
    2404   /// \brief Return a \ref BpGraphWriter class
    2405   ///
    2406   /// This function just returns a \ref BpGraphWriter class.
     2407  /// \brief Return a \ref lemon::BpGraphWriter "BpGraphWriter" class
     2408  ///
     2409  /// This function just returns a \ref lemon::BpGraphWriter
     2410  /// "BpGraphWriter" class.
    24072411  ///
    24082412  /// With this function a bipartite graph can be write to a file or output
     
    24212425  ///\endcode
    24222426  ///
    2423   /// For a complete documentation, please see the \ref BpGraphWriter
     2427  /// For a complete documentation, please see the
     2428  /// \ref lemon::BpGraphWriter "BpGraphWriter"
    24242429  /// class documentation.
    2425   /// \warning Don't forget to put the \ref BpGraphWriter::run() "run()"
     2430  /// \warning Don't forget to put the \ref lemon::BpGraphWriter::run() "run()"
    24262431  /// to the end of the parameter list.
    24272432  /// \relates BpGraphWriter
  • lemon/list_graph.h

    r1193 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    446446    ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
    447447    ///invalidated for the outgoing arcs of node \c v and \c InArcIt
    448     ///iterators are invalidated for the incomming arcs of \c v.
     448    ///iterators are invalidated for the incoming arcs of \c v.
    449449    ///Moreover all iterators referencing node \c v or the removed
    450450    ///loops are also invalidated. Other iterators remain valid.
     
    17661766    void next(BlueNode& node) const {
    17671767      node.id = nodes[node.id].partition_next;
    1768     }   
     1768    }
    17691769
    17701770    void first(Arc& e) const {
  • lemon/lp.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6060  ///\ingroup lp_group
    6161  ///
    62   ///Currently, the possible values are \c GLPK or \c CPLEX
     62  ///Currently, the possible values are \c GLPK, \c CPLEX or \c CBC
    6363#define LEMON_DEFAULT_MIP SOLVER
    6464  ///The default MIP solver.
     
    6767  ///\ingroup lp_group
    6868  ///
    69   ///Currently, it is either \c GlpkMip or \c CplexMip
     69  ///Currently, it is either \c GlpkMip, \c CplexMip , \c CbcMip
    7070  typedef GlpkMip Mip;
    7171#else
    72 #ifdef LEMON_HAVE_GLPK
    73 # define LEMON_DEFAULT_LP GLPK
     72#if LEMON_DEFAULT_LP == GLPK
    7473  typedef GlpkLp Lp;
    75 # define LEMON_DEFAULT_MIP GLPK
    76   typedef GlpkMip Mip;
    77 #elif LEMON_HAVE_CPLEX
    78 # define LEMON_DEFAULT_LP CPLEX
     74#elif LEMON_DEFAULT_LP == CPLEX
    7975  typedef CplexLp Lp;
    80 # define LEMON_DEFAULT_MIP CPLEX
     76#elif LEMON_DEFAULT_LP == SOPLEX
     77  typedef SoplexLp Lp;
     78#elif LEMON_DEFAULT_LP == CLP
     79  typedef ClpLp Lp;
     80#endif
     81#if LEMON_DEFAULT_MIP == GLPK
     82  typedef GlpkLp Mip;
     83#elif LEMON_DEFAULT_MIP == CPLEX
    8184  typedef CplexMip Mip;
    82 #elif LEMON_HAVE_SOPLEX
    83 # define DEFAULT_LP SOPLEX
    84   typedef SoplexLp Lp;
    85 #elif LEMON_HAVE_CLP
    86 # define DEFAULT_LP CLP
    87   typedef ClpLp Lp;
     85#elif LEMON_DEFAULT_MIP == CBC
     86  typedef CbcMip Mip;
    8887#endif
    8988#endif
  • lemon/lp_base.cc

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/lp_base.h

    r1143 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    10081008  public:
    10091009
     1010    ///Unsupported file format exception
     1011    class UnsupportedFormatError : public Exception
     1012    {
     1013      std::string _format;
     1014      mutable std::string _what;
     1015    public:
     1016      explicit UnsupportedFormatError(std::string format) throw()
     1017        : _format(format) { }
     1018      virtual ~UnsupportedFormatError() throw() {}
     1019      virtual const char* what() const throw() {
     1020        try {
     1021          _what.clear();
     1022          std::ostringstream oss;
     1023          oss << "lemon::UnsupportedFormatError: " << _format;
     1024          _what = oss.str();
     1025        }
     1026        catch (...) {}
     1027        if (!_what.empty()) return _what.c_str();
     1028        else return "lemon::UnsupportedFormatError";
     1029      }
     1030    };
     1031
     1032  protected:
     1033    virtual void _write(std::string, std::string format) const
     1034    {
     1035      throw UnsupportedFormatError(format);
     1036    }
     1037
     1038  public:
     1039
    10101040    /// Virtual destructor
    10111041    virtual ~LpBase() {}
     
    15561586    void min() { _setSense(MIN); }
    15571587
    1558     ///Clears the problem
     1588    ///Clear the problem
    15591589    void clear() { _clear(); rows.clear(); cols.clear(); }
    15601590
    1561     /// Sets the message level of the solver
     1591    /// Set the message level of the solver
    15621592    void messageLevel(MessageLevel level) { _messageLevel(level); }
     1593
     1594    /// Write the problem to a file in the given format
     1595
     1596    /// This function writes the problem to a file in the given format.
     1597    /// Different solver backends may support different formats.
     1598    /// Trying to write in an unsupported format will trigger
     1599    /// \ref UnsupportedFormatError. For the supported formats,
     1600    /// visit the documentation of the base class of the related backends
     1601    /// (\ref CplexBase, \ref GlpkBase etc.)
     1602    /// \param file The file path
     1603    /// \param format The output file format.
     1604    void write(std::string file, std::string format = "MPS") const
     1605    {
     1606      _write(file.c_str(),format.c_str());
     1607    }
    15631608
    15641609    ///@}
  • lemon/lp_skeleton.cc

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9292  void SkeletonSolverBase::_messageLevel(MessageLevel) {}
    9393
     94  void SkeletonSolverBase::_write(std::string, std::string) const {}
     95
    9496  LpSkeleton::SolveExitStatus LpSkeleton::_solve() { return SOLVED; }
    9597
  • lemon/lp_skeleton.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    145145    ///\e
    146146    virtual void _messageLevel(MessageLevel);
     147
     148    ///\e
     149    virtual void _write(std::string file, std::string format) const;
     150
    147151  };
    148152
     
    223227    ///\e
    224228    virtual const char* _solverName() const;
     229
    225230  };
    226231
  • lemon/maps.h

    r1057 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/matching.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/math.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6666    }
    6767
     68  ///Round a value to its closest integer
     69  inline double round(double r) {
     70    return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);
     71  }
     72
    6873  /// @}
    6974
    7075} //namespace lemon
    7176
    72 #endif //LEMON_TOLERANCE_H
     77#endif //LEMON_MATH_H
  • lemon/max_cardinality_search.h

    r1129 r1271  
    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-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2222
    2323/// \ingroup search
    24 /// \file 
     24/// \file
    2525/// \brief Maximum cardinality search in undirected digraphs.
    2626
     
    4242  template <typename GR, typename CAP>
    4343  struct MaxCardinalitySearchDefaultTraits {
    44     /// The digraph type the algorithm runs on. 
     44    /// The digraph type the algorithm runs on.
    4545    typedef GR Digraph;
    4646
     
    5151
    5252      static CapacityMap *createCapacityMap(const Digraph& g) {
    53         return new CapacityMap(g);
     53        return new CapacityMap(g);
    5454      }
    5555    };
     
    6161
    6262      static CapacityMap *createCapacityMap(const Digraph&) {
    63         return new CapacityMap;
     63        return new CapacityMap;
    6464      }
    6565    };
     
    9191    /// \brief Instantiates a HeapCrossRef.
    9292    ///
    93     /// This function instantiates a \ref HeapCrossRef. 
    94     /// \param digraph is the digraph, to which we would like to define the 
     93    /// This function instantiates a \ref HeapCrossRef.
     94    /// \param digraph is the digraph, to which we would like to define the
    9595    /// HeapCrossRef.
    9696    static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {
    9797      return new HeapCrossRef(digraph);
    9898    }
    99    
     99
    100100    template <typename CapacityMap>
    101101    struct HeapSelector {
    102102      template <typename Value, typename Ref>
    103       struct Selector { 
     103      struct Selector {
    104104        typedef BinHeap<Value, Ref, std::greater<Value> > Heap;
    105105      };
     
    129129    /// \brief Instantiates a Heap.
    130130    ///
    131     /// This function instantiates a \ref Heap. 
     131    /// This function instantiates a \ref Heap.
    132132    /// \param crossref The cross reference of the heap.
    133133    static Heap *createHeap(HeapCrossRef& crossref) {
     
    144144    /// \brief Instantiates a ProcessedMap.
    145145    ///
    146     /// This function instantiates a \ref ProcessedMap. 
     146    /// This function instantiates a \ref ProcessedMap.
    147147    /// \param digraph is the digraph, to which
    148148    /// we would like to define the \ref ProcessedMap
     
    157157
    158158    /// \brief The type of the map that stores the cardinalities of the nodes.
    159     /// 
     159    ///
    160160    /// The type of the map that stores the cardinalities of the nodes.
    161161    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
     
    164164    /// \brief Instantiates a CardinalityMap.
    165165    ///
    166     /// This function instantiates a \ref CardinalityMap. 
    167     /// \param digraph is the digraph, to which we would like to define the \ref
    168     /// CardinalityMap
     166    /// This function instantiates a \ref CardinalityMap.
     167    /// \param digraph is the digraph, to which we would like to
     168    /// define the \ref CardinalityMap
    169169    static CardinalityMap *createCardinalityMap(const Digraph &digraph) {
    170170      return new CardinalityMap(digraph);
     
    173173
    174174  };
    175  
     175
    176176  /// \ingroup search
    177177  ///
    178178  /// \brief Maximum Cardinality Search algorithm class.
    179179  ///
    180   /// This class provides an efficient implementation of Maximum Cardinality 
    181   /// Search algorithm. The maximum cardinality search first chooses any 
     180  /// This class provides an efficient implementation of Maximum Cardinality
     181  /// Search algorithm. The maximum cardinality search first chooses any
    182182  /// node of the digraph. Then every time it chooses one unprocessed node
    183   /// with maximum cardinality, i.e the sum of capacities on out arcs to the nodes
     183  /// with maximum cardinality, i.e the sum of capacities on out arcs
     184  /// to the nodes
    184185  /// which were previusly processed.
    185186  /// If there is a cut in the digraph the algorithm should choose
     
    187188
    188189  /// The arc capacities are passed to the algorithm using a
    189   /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
     190  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
    190191  /// kind of capacity.
    191192  ///
    192   /// The type of the capacity is determined by the \ref 
     193  /// The type of the capacity is determined by the \ref
    193194  /// concepts::ReadMap::Value "Value" of the capacity map.
    194195  ///
     
    197198  ///
    198199  /// \param GR The digraph type the algorithm runs on. The value of
    199   /// Digraph is not used directly by the search algorithm, it 
     200  /// Digraph is not used directly by the search algorithm, it
    200201  /// is only passed to \ref MaxCardinalitySearchDefaultTraits.
    201   /// \param CAP This read-only ArcMap determines the capacities of 
     202  /// \param CAP This read-only ArcMap determines the capacities of
    202203  /// the arcs. It is read once for each arc, so the map may involve in
    203204  /// relatively time consuming process to compute the arc capacity if
    204205  /// it is necessary. The default map type is \ref
    205206  /// ConstMap "ConstMap<concepts::Digraph::Arc, Const<int,1> >". The value
    206   /// of CapacityMap is not used directly by search algorithm, it is only 
    207   /// passed to \ref MaxCardinalitySearchDefaultTraits. 
    208   /// \param TR Traits class to set various data types used by the 
    209   /// algorithm.  The default traits class is 
    210   /// \ref MaxCardinalitySearchDefaultTraits 
    211   /// "MaxCardinalitySearchDefaultTraits<GR, CAP>". 
    212   /// See \ref MaxCardinalitySearchDefaultTraits 
     207  /// of CapacityMap is not used directly by search algorithm, it is only
     208  /// passed to \ref MaxCardinalitySearchDefaultTraits.
     209  /// \param TR Traits class to set various data types used by the
     210  /// algorithm.  The default traits class is
     211  /// \ref MaxCardinalitySearchDefaultTraits
     212  /// "MaxCardinalitySearchDefaultTraits<GR, CAP>".
     213  /// See \ref MaxCardinalitySearchDefaultTraits
    213214  /// for the documentation of a MaxCardinalitySearch traits class.
    214215
     
    216217  template <typename GR, typename CAP, typename TR>
    217218#else
    218   template <typename GR, typename CAP = 
    219             ConstMap<typename GR::Arc, Const<int,1> >,
    220             typename TR =
     219  template <typename GR, typename CAP =
     220            ConstMap<typename GR::Arc, Const<int,1> >,
     221            typename TR =
    221222            MaxCardinalitySearchDefaultTraits<GR, CAP> >
    222223#endif
     
    227228    ///The type of the underlying digraph.
    228229    typedef typename Traits::Digraph Digraph;
    229    
     230
    230231    ///The type of the capacity of the arcs.
    231232    typedef typename Traits::CapacityMap::Value Value;
     
    267268
    268269    typedef MaxCardinalitySearch Create;
    269  
     270
    270271    ///\name Named template parameters
    271272
     
    276277      typedef T CapacityMap;
    277278      static CapacityMap *createCapacityMap(const Digraph &) {
    278         LEMON_ASSERT(false,"Uninitialized parameter.");
    279         return 0;
    280       }
    281     };
    282     /// \brief \ref named-templ-param "Named parameter" for setting 
     279               LEMON_ASSERT(false,"Uninitialized parameter.");
     280        return 0;
     281      }
     282    };
     283    /// \brief \ref named-templ-param "Named parameter" for setting
    283284    /// CapacityMap type
    284285    ///
     
    286287    /// for the algorithm.
    287288    template <class T>
    288     struct SetCapacityMap 
    289       : public MaxCardinalitySearch<Digraph, CapacityMap, 
    290                                     DefCapacityMapTraits<T> > { 
    291       typedef MaxCardinalitySearch<Digraph, CapacityMap, 
     289    struct SetCapacityMap
     290      : public MaxCardinalitySearch<Digraph, CapacityMap,
     291                                    DefCapacityMapTraits<T> > {
     292      typedef MaxCardinalitySearch<Digraph, CapacityMap,
    292293                                   DefCapacityMapTraits<T> > Create;
    293294    };
     
    296297    struct DefCardinalityMapTraits : public Traits {
    297298      typedef T CardinalityMap;
    298       static CardinalityMap *createCardinalityMap(const Digraph &) 
     299      static CardinalityMap *createCardinalityMap(const Digraph &)
    299300      {
    300         LEMON_ASSERT(false,"Uninitialized parameter.");
    301         return 0;
    302       }
    303     };
    304     /// \brief \ref named-templ-param "Named parameter" for setting 
     301        LEMON_ASSERT(false,"Uninitialized parameter.");
     302        return 0;
     303      }
     304    };
     305    /// \brief \ref named-templ-param "Named parameter" for setting
    305306    /// CardinalityMap type
    306307    ///
    307     /// \ref named-templ-param "Named parameter" for setting CardinalityMap 
     308    /// \ref named-templ-param "Named parameter" for setting CardinalityMap
    308309    /// type for the algorithm.
    309310    template <class T>
    310     struct SetCardinalityMap 
    311       : public MaxCardinalitySearch<Digraph, CapacityMap, 
    312                                     DefCardinalityMapTraits<T> > { 
    313       typedef MaxCardinalitySearch<Digraph, CapacityMap, 
     311    struct SetCardinalityMap
     312      : public MaxCardinalitySearch<Digraph, CapacityMap,
     313                                    DefCardinalityMapTraits<T> > {
     314      typedef MaxCardinalitySearch<Digraph, CapacityMap,
    314315                                   DefCardinalityMapTraits<T> > Create;
    315316    };
    316    
     317
    317318    template <class T>
    318319    struct DefProcessedMapTraits : public Traits {
    319320      typedef T ProcessedMap;
    320321      static ProcessedMap *createProcessedMap(const Digraph &) {
    321         LEMON_ASSERT(false,"Uninitialized parameter.");
    322         return 0;
    323       }
    324     };
    325     /// \brief \ref named-templ-param "Named parameter" for setting 
     322               LEMON_ASSERT(false,"Uninitialized parameter.");
     323        return 0;
     324      }
     325    };
     326    /// \brief \ref named-templ-param "Named parameter" for setting
    326327    /// ProcessedMap type
    327328    ///
     
    329330    /// for the algorithm.
    330331    template <class T>
    331     struct SetProcessedMap 
    332       : public MaxCardinalitySearch<Digraph, CapacityMap, 
    333                                     DefProcessedMapTraits<T> > { 
    334       typedef MaxCardinalitySearch<Digraph, CapacityMap, 
     332    struct SetProcessedMap
     333      : public MaxCardinalitySearch<Digraph, CapacityMap,
     334                                    DefProcessedMapTraits<T> > {
     335      typedef MaxCardinalitySearch<Digraph, CapacityMap,
    335336                                   DefProcessedMapTraits<T> > Create;
    336337    };
    337    
     338
    338339    template <class H, class CR>
    339340    struct DefHeapTraits : public Traits {
     
    341342      typedef H Heap;
    342343      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
    343         LEMON_ASSERT(false,"Uninitialized parameter.");
    344         return 0;
     344             LEMON_ASSERT(false,"Uninitialized parameter.");
     345        return 0;
    345346      }
    346347      static Heap *createHeap(HeapCrossRef &) {
    347         LEMON_ASSERT(false,"Uninitialized parameter.");
    348         return 0;
    349       }
    350     };
    351     /// \brief \ref named-templ-param "Named parameter" for setting heap 
     348               LEMON_ASSERT(false,"Uninitialized parameter.");
     349        return 0;
     350      }
     351    };
     352    /// \brief \ref named-templ-param "Named parameter" for setting heap
    352353    /// and cross reference type
    353354    ///
    354     /// \ref named-templ-param "Named parameter" for setting heap and cross 
     355    /// \ref named-templ-param "Named parameter" for setting heap and cross
    355356    /// reference type for the algorithm.
    356357    template <class H, class CR = typename Digraph::template NodeMap<int> >
    357358    struct SetHeap
    358       : public MaxCardinalitySearch<Digraph, CapacityMap, 
    359                                     DefHeapTraits<H, CR> > { 
    360       typedef MaxCardinalitySearch< Digraph, CapacityMap, 
     359      : public MaxCardinalitySearch<Digraph, CapacityMap,
     360                                    DefHeapTraits<H, CR> > {
     361      typedef MaxCardinalitySearch< Digraph, CapacityMap,
    361362                                    DefHeapTraits<H, CR> > Create;
    362363    };
     
    367368      typedef H Heap;
    368369      static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {
    369         return new HeapCrossRef(digraph);
     370        return new HeapCrossRef(digraph);
    370371      }
    371372      static Heap *createHeap(HeapCrossRef &crossref) {
    372         return new Heap(crossref);
    373       }
    374     };
    375 
    376     /// \brief \ref named-templ-param "Named parameter" for setting heap and 
     373        return new Heap(crossref);
     374      }
     375    };
     376
     377    /// \brief \ref named-templ-param "Named parameter" for setting heap and
    377378    /// cross reference type with automatic allocation
    378379    ///
    379     /// \ref named-templ-param "Named parameter" for setting heap and cross 
    380     /// reference type. It can allocate the heap and the cross reference 
    381     /// object if the cross reference's constructor waits for the digraph as 
     380    /// \ref named-templ-param "Named parameter" for setting heap and cross
     381    /// reference type. It can allocate the heap and the cross reference
     382    /// object if the cross reference's constructor waits for the digraph as
    382383    /// parameter and the heap's constructor waits for the cross reference.
    383384    template <class H, class CR = typename Digraph::template NodeMap<int> >
    384385    struct SetStandardHeap
    385       : public MaxCardinalitySearch<Digraph, CapacityMap, 
    386                                     DefStandardHeapTraits<H, CR> > { 
    387       typedef MaxCardinalitySearch<Digraph, CapacityMap, 
    388                                    DefStandardHeapTraits<H, CR> > 
     386      : public MaxCardinalitySearch<Digraph, CapacityMap,
     387                                    DefStandardHeapTraits<H, CR> > {
     388      typedef MaxCardinalitySearch<Digraph, CapacityMap,
     389                                   DefStandardHeapTraits<H, CR> >
    389390      Create;
    390391    };
    391    
     392
    392393    ///@}
    393394
     
    397398    MaxCardinalitySearch() {}
    398399
    399   public:     
    400    
     400  public:
     401
    401402    /// \brief Constructor.
    402403    ///
     
    404405    ///\param capacity the capacity map used by the algorithm.
    405406    MaxCardinalitySearch(const Digraph& digraph,
    406                         const CapacityMap& capacity) :
     407                        const CapacityMap& capacity) :
    407408      _graph(&digraph),
    408409      _capacity(&capacity), local_capacity(false),
     
    442443    MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
    443444      if (local_capacity) {
    444         delete _capacity;
    445         local_capacity=false;
     445        delete _capacity;
     446        local_capacity=false;
    446447      }
    447448      _capacity=&m;
     
    457458    }
    458459
    459     /// \brief Sets the map storing the cardinalities calculated by the 
     460    /// \brief Sets the map storing the cardinalities calculated by the
    460461    /// algorithm.
    461462    ///
     
    467468    MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
    468469      if(local_cardinality) {
    469         delete _cardinality;
    470         local_cardinality=false;
     470        delete _cardinality;
     471        local_cardinality=false;
    471472      }
    472473      _cardinality = &m;
     
    481482    /// automatically allocated map, of course.
    482483    /// \return <tt> (*this) </tt>
    483     MaxCardinalitySearch &processedMap(ProcessedMap &m) 
     484    MaxCardinalitySearch &processedMap(ProcessedMap &m)
    484485    {
    485486      if(local_processed) {
    486         delete _processed;
    487         local_processed=false;
     487        delete _processed;
     488        local_processed=false;
    488489      }
    489490      _processed = &m;
     
    508509    MaxCardinalitySearch &heap(Heap& hp, HeapCrossRef &cr) {
    509510      if(local_heap_cross_ref) {
    510         delete _heap_cross_ref;
    511         local_heap_cross_ref = false;
     511        delete _heap_cross_ref;
     512        local_heap_cross_ref = false;
    512513      }
    513514      _heap_cross_ref = &cr;
    514515      if(local_heap) {
    515         delete _heap;
    516         local_heap = false;
     516        delete _heap;
     517        local_heap = false;
    517518      }
    518519      _heap = &hp;
     
    545546    void create_maps() {
    546547      if(!_capacity) {
    547         local_capacity = true;
    548         _capacity = Traits::createCapacityMap(*_graph);
     548        local_capacity = true;
     549        _capacity = Traits::createCapacityMap(*_graph);
    549550      }
    550551      if(!_cardinality) {
    551         local_cardinality = true;
    552         _cardinality = Traits::createCardinalityMap(*_graph);
     552        local_cardinality = true;
     553        _cardinality = Traits::createCardinalityMap(*_graph);
    553554      }
    554555      if(!_processed) {
    555         local_processed = true;
    556         _processed = Traits::createProcessedMap(*_graph);
     556        local_processed = true;
     557        _processed = Traits::createProcessedMap(*_graph);
    557558      }
    558559      if (!_heap_cross_ref) {
    559         local_heap_cross_ref = true;
    560         _heap_cross_ref = Traits::createHeapCrossRef(*_graph);
     560        local_heap_cross_ref = true;
     561        _heap_cross_ref = Traits::createHeapCrossRef(*_graph);
    561562      }
    562563      if (!_heap) {
    563         local_heap = true;
    564         _heap = Traits::createHeap(*_heap_cross_ref);
    565       }
    566     }
    567    
     564        local_heap = true;
     565        _heap = Traits::createHeap(*_heap_cross_ref);
     566      }
     567    }
     568
    568569    void finalizeNodeData(Node node, Value capacity) {
    569570      _processed->set(node, true);
     
    590591      _heap->clear();
    591592      for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
    592         _processed->set(it, false);
    593         _heap_cross_ref->set(it, Heap::PRE_HEAP);
    594       }
    595     }
    596    
     593        _processed->set(it, false);
     594        _heap_cross_ref->set(it, Heap::PRE_HEAP);
     595      }
     596    }
     597
    597598    /// \brief Adds a new source node.
    598     /// 
     599    ///
    599600    /// Adds a new source node to the priority heap.
    600601    ///
     
    602603    void addSource(Node source, Value capacity = 0) {
    603604      if(_heap->state(source) == Heap::PRE_HEAP) {
    604         _heap->push(source, capacity);
    605       } 
    606     }
    607    
     605        _heap->push(source, capacity);
     606      }
     607    }
     608
    608609    /// \brief Processes the next node in the priority heap
    609610    ///
     
    614615    /// \warning The priority heap must not be empty!
    615616    Node processNextNode() {
    616       Node node = _heap->top(); 
     617      Node node = _heap->top();
    617618      finalizeNodeData(node, _heap->prio());
    618619      _heap->pop();
    619      
     620
    620621      for (InArcIt it(*_graph, node); it != INVALID; ++it) {
    621         Node source = _graph->source(it);
    622         switch (_heap->state(source)) {
    623         case Heap::PRE_HEAP:
    624           _heap->push(source, (*_capacity)[it]);
    625           break;
    626         case Heap::IN_HEAP:
    627           _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
    628           break;
    629         case Heap::POST_HEAP:
    630           break;
    631         }
     622        Node source = _graph->source(it);
     623        switch (_heap->state(source)) {
     624        case Heap::PRE_HEAP:
     625          _heap->push(source, (*_capacity)[it]);
     626          break;
     627        case Heap::IN_HEAP:
     628          _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
     629          break;
     630        case Heap::POST_HEAP:
     631          break;
     632        }
    632633      }
    633634      return node;
     
    638639    /// Next node to be processed.
    639640    ///
    640     /// \return The next node to be processed or INVALID if the 
     641    /// \return The next node to be processed or INVALID if the
    641642    /// priority heap is empty.
    642     Node nextNode() { 
     643    Node nextNode() {
    643644      return !_heap->empty() ? _heap->top() : INVALID;
    644645    }
    645  
     646
    646647    /// \brief Returns \c false if there are nodes
    647648    /// to be processed in the priority heap
     
    650651    /// to be processed in the priority heap
    651652    bool emptyQueue() { return _heap->empty(); }
    652     /// \brief Returns the number of the nodes to be processed 
     653    /// \brief Returns the number of the nodes to be processed
    653654    /// in the priority heap
    654655    ///
    655656    /// Returns the number of the nodes to be processed in the priority heap
    656657    int emptySize() { return _heap->size(); }
    657    
     658
    658659    /// \brief Executes the algorithm.
    659660    ///
     
    663664    /// with addSource() before using this function.
    664665    ///
    665     /// This method runs the Maximum Cardinality Search algorithm from the 
     666    /// This method runs the Maximum Cardinality Search algorithm from the
    666667    /// source node(s).
    667668    void start() {
    668669      while ( !_heap->empty() ) processNextNode();
    669670    }
    670    
     671
    671672    /// \brief Executes the algorithm until \c dest is reached.
    672673    ///
     
    676677    /// with addSource() before using this function.
    677678    ///
    678     /// This method runs the %MaxCardinalitySearch algorithm from the source 
     679    /// This method runs the %MaxCardinalitySearch algorithm from the source
    679680    /// nodes.
    680681    void start(Node dest) {
     
    682683      if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
    683684    }
    684    
     685
    685686    /// \brief Executes the algorithm until a condition is met.
    686687    ///
     
    697698      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
    698699    }
    699    
     700
    700701    /// \brief Runs the maximum cardinality search algorithm from node \c s.
    701702    ///
    702     /// This method runs the %MaxCardinalitySearch algorithm from a root 
     703    /// This method runs the %MaxCardinalitySearch algorithm from a root
    703704    /// node \c s.
    704705    ///
     
    715716    }
    716717
    717     /// \brief Runs the maximum cardinality search algorithm for the 
     718    /// \brief Runs the maximum cardinality search algorithm for the
    718719    /// whole digraph.
    719720    ///
    720     /// This method runs the %MaxCardinalitySearch algorithm from all 
     721    /// This method runs the %MaxCardinalitySearch algorithm from all
    721722    /// unprocessed node of the digraph.
    722723    ///
     
    740741      }
    741742    }
    742    
     743
    743744    ///@}
    744745
    745746    /// \name Query Functions
    746     /// The results of the maximum cardinality search algorithm can be 
     747    /// The results of the maximum cardinality search algorithm can be
    747748    /// obtained using these functions.
    748749    /// \n
    749     /// Before the use of these functions, either run() or start() must be 
     750    /// Before the use of these functions, either run() or start() must be
    750751    /// called.
    751    
     752
    752753    ///@{
    753754
     
    768769    /// \brief Returns a reference to the NodeMap of cardinalities.
    769770    ///
    770     /// Returns a reference to the NodeMap of cardinalities. \pre \ref run() 
     771    /// Returns a reference to the NodeMap of cardinalities. \pre \ref run()
    771772    /// must be called before using this function.
    772773    const CardinalityMap &cardinalityMap() const { return *_cardinality;}
    773  
     774
    774775    /// \brief Checks if a node is reachable from the root.
    775776    ///
     
    785786    /// \pre \ref run() must be called before using this function.
    786787    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
    787    
     788
    788789    ///@}
    789790  };
  • lemon/min_cost_arborescence.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    102102  /// the minimum cost subgraph that is the union of arborescences with the
    103103  /// given sources and spans all the nodes which are reachable from the
    104   /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
     104  /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+m).
    105105  ///
    106106  /// The algorithm also provides an optimal dual solution, therefore
     
    129129  public:
    130130
    131     /// \brief The \ref MinCostArborescenceDefaultTraits "traits class"
     131    /// \brief The \ref lemon::MinCostArborescenceDefaultTraits "traits class"
    132132    /// of the algorithm.
    133133    typedef TR Traits;
  • lemon/nagamochi_ibaraki.h

    r1130 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    304304    //This is here to avoid a gcc-3.3 compilation error.
    305305    //It should never be called.
    306     NagamochiIbaraki() {} 
    307    
     306    NagamochiIbaraki() {}
     307
    308308  public:
    309309
     
    415415        for (typename Graph::OutArcIt a(_graph, n); a != INVALID; ++a) {
    416416          typename Graph::Node m = _graph.target(a);
    417          
     417
    418418          if (!(n < m)) continue;
    419419
    420420          (*_nodes)[n].sum += (*_capacity)[a];
    421421          (*_nodes)[m].sum += (*_capacity)[a];
    422          
     422
    423423          int c = (*_nodes)[m].curr_arc;
    424424          if (c != -1 && _arcs[c ^ 1].target == n) {
     
    426426          } else {
    427427            _edges[index].capacity = (*_capacity)[a];
    428            
     428
    429429            _arcs[index << 1].prev = -1;
    430430            if ((*_nodes)[n].first_arc != -1) {
     
    436436
    437437            (*_nodes)[m].curr_arc = (index << 1);
    438            
     438
    439439            _arcs[(index << 1) | 1].prev = -1;
    440440            if ((*_nodes)[m].first_arc != -1) {
     
    444444            (*_nodes)[m].first_arc = ((index << 1) | 1);
    445445            _arcs[(index << 1) | 1].target = n;
    446            
     446
    447447            ++index;
    448448          }
     
    453453      _min_cut = std::numeric_limits<Value>::max();
    454454
    455       for (typename Graph::Node n = _first_node; 
     455      for (typename Graph::Node n = _first_node;
    456456           n != INVALID; n = (*_nodes)[n].next) {
    457457        if ((*_nodes)[n].sum < _min_cut) {
     
    478478
    479479      _heap->clear();
    480       for (typename Graph::Node n = _first_node; 
     480      for (typename Graph::Node n = _first_node;
    481481           n != INVALID; n = (*_nodes)[n].next) {
    482482        (*_heap_cross_ref)[n] = Heap::PRE_HEAP;
     
    498498        for (int a = (*_nodes)[n].first_arc; a != -1; a = _arcs[a].next) {
    499499          switch (_heap->state(_arcs[a].target)) {
    500           case Heap::PRE_HEAP: 
     500          case Heap::PRE_HEAP:
    501501            {
    502502              Value nv = _edges[a >> 1].capacity;
     
    564564            if (!merged) {
    565565              for (int b = (*_nodes)[n].first_arc; b != -1; b = _arcs[b].next) {
    566                 (*_nodes)[_arcs[b].target].curr_arc = b;         
     566                (*_nodes)[_arcs[b].target].curr_arc = b;
    567567              }
    568568              merged = true;
     
    574574              if ((b ^ a) == 1) continue;
    575575              typename Graph::Node o = _arcs[b].target;
    576               int c = (*_nodes)[o].curr_arc; 
     576              int c = (*_nodes)[o].curr_arc;
    577577              if (c != -1 && _arcs[c ^ 1].target == n) {
    578578                _edges[c >> 1].capacity += _edges[b >> 1].capacity;
     
    607607            } else {
    608608              (*_nodes)[n].first_arc = _arcs[a].next;
    609             }           
     609            }
    610610            if (_arcs[a].next != -1) {
    611611              _arcs[_arcs[a].next].prev = _arcs[a].prev;
     
    615615            (*_next_rep)[(*_nodes)[n].last_rep] = m;
    616616            (*_nodes)[n].last_rep = (*_nodes)[m].last_rep;
    617            
     617
    618618            if ((*_nodes)[m].prev != INVALID) {
    619619              (*_nodes)[(*_nodes)[m].prev].next = (*_nodes)[m].next;
  • lemon/nearest_neighbor_tsp.h

    r1205 r1294  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    116116            for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
    117117              if (!used[_gr.runningNode(e)] &&
    118                   (_cost[e] < _cost[min_edge1] || min_edge1 == INVALID)) {
     118                  (min_edge1 == INVALID || _cost[e] < _cost[min_edge1])) {
    119119                min_edge1 = e;
    120120              }
     
    125125            for (IncEdgeIt e(_gr, n2); e != INVALID; ++e) {
    126126              if (!used[_gr.runningNode(e)] &&
    127                   (_cost[e] < _cost[min_edge2] || min_edge2 == INVALID)) {
     127                  (min_edge2 == INVALID||_cost[e] < _cost[min_edge2])) {
    128128                min_edge2 = e;
    129129              }
     
    216216      ///
    217217      /// This function copies the found tour as a list of arcs/edges into
    218       /// the given \ref concept::Path "path structure".
     218      /// the given \ref lemon::concepts::Path "path structure".
    219219      ///
    220220      /// \pre run() must be called before using this function.
  • lemon/network_simplex.h

    r1297 r1298  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).