COIN-OR::LEMON - Graph Library

Ignore:
Files:
3 added
65 edited

Legend:

Unmodified
Added
Removed
  • CMakeLists.txt

    r1264 r1346  
    1 CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
     1CMAKE_MINIMUM_REQUIRED(VERSION 2.8)
     2
     3IF(POLICY CMP0048)
     4  CMAKE_POLICY(SET CMP0048 OLD)
     5ENDIF(POLICY CMP0048)
     6
     7IF(POLICY CMP0043)
     8  CMAKE_POLICY(SET CMP0043 OLD)
     9ENDIF(POLICY CMP0043)
     10
     11IF(POLICY CMP0026)
     12  #This is for copying the dll's needed by glpk (in lp_test and mip_test)
     13  CMAKE_POLICY(SET CMP0026 OLD)
     14ENDIF(POLICY CMP0026)
    215
    316SET(PROJECT_NAME "LEMON")
     
    6376FIND_PACKAGE(Ghostscript)
    6477
     78IF(WIN32)
     79  SET(LEMON_WIN32 TRUE)
     80ENDIF(WIN32)
     81
    6582SET(LEMON_ENABLE_GLPK YES CACHE STRING "Enable GLPK solver backend.")
    6683SET(LEMON_ENABLE_ILOG YES CACHE STRING "Enable ILOG (CPLEX) solver backend.")
     
    122139  SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
    123140    "Default LP solver backend (GLPK, CPLEX, CLP or SOPLEX)" FORCE)
     141ELSE()
     142  SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
     143    "Default LP solver backend (GLPK, CPLEX, CLP or SOPLEX)")
    124144ENDIF()
    125145IF(NOT LEMON_DEFAULT_MIP OR
     
    129149  SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
    130150    "Default MIP solver backend (GLPK, CPLEX or CBC)" FORCE)
     151ELSE()
     152  SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
     153    "Default MIP solver backend (GLPK, CPLEX or CBC)")
    131154ENDIF()
    132155
     
    141164  ELSEIF(MSVC)
    142165    # This part is unnecessary 'casue the same is set by the lemon/core.h.
    143     # Still keep it as an example.
    144     SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")
     166    # Still kept as an example.
     167
     168    # SET(CXX_WARNING "/wd4250 /wd4267 /wd4355 /wd4503 /wd4800 /wd4996")
     169
    145170    # Suppressed warnings:
    146171    # C4250: 'class1' : inherits 'class2::member' via dominance
     172    # C4267: conversion from 'size_t' to 'type', possible loss of data
    147173    # C4355: 'this' : used in base member initializer list
    148174    # C4503: 'function' : decorated name length exceeded, name was truncated
     
    159185
    160186IF(MSVC)
     187  SET(CMAKE_CXX_FLAGS "/bigobj ${CMAKE_CXX_FLAGS}")
    161188  SET( CMAKE_CXX_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
    162189    "Flags used by the C++ compiler during maintainer builds."
     
    181208    )
    182209  SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
    183     "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
     210    "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING
    184211    "Flags used for linking binaries during maintainer builds."
    185212    )
    186213  SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
    187     "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
     214    "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING
    188215    "Flags used by the shared libraries linker during maintainer builds."
    189216    )
     
    212239    FORCE )
    213240
     241SET_DIRECTORY_PROPERTIES(PROPERTIES
     242  COMPILE_DEFINITIONS_DEBUG "LEMON_ENABLE_DEBUG"
     243  COMPILE_DEFINITIONS_MAINTAINER "LEMON_ENABLE_DEBUG"
     244)
    214245
    215246INCLUDE(CheckTypeSize)
     
    240271
    241272ENABLE_TESTING()
     273
     274
     275INCLUDE(CheckCXXCompilerFlag)
     276CHECK_CXX_COMPILER_FLAG("-std=c++11" LEMON_CXX11)
     277IF(LEMON_CXX11)
     278  SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
     279ENDIF()
     280
    242281
    243282IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
  • 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/FindILOG.cmake

    r1232 r1331  
    6363  ${ILOG_CPLEX_ROOT_DIR}/lib/x86_debian4.0_4.1/static_pic
    6464  ${ILOG_CPLEX_ROOT_DIR}/lib/x86-64_debian4.0_4.1/static_pic
     65  ${ILOG_CPLEX_ROOT_DIR}/lib/x86_linux/static_pic
     66  ${ILOG_CPLEX_ROOT_DIR}/lib/x86-64_linux/static_pic
    6567  ${ILOG_CPLEX_ROOT_DIR}/lib/${ILOG_WIN_COMPILER}/stat_mda
    6668  NO_DEFAULT_PATH
     
    7375  ${ILOG_CONCERT_ROOT_DIR}/lib/x86_debian4.0_4.1/static_pic
    7476  ${ILOG_CONCERT_ROOT_DIR}/lib/x86-64_debian4.0_4.1/static_pic
     77  ${ILOG_CONCERT_ROOT_DIR}/lib/x86_linux/static_pic
     78  ${ILOG_CONCERT_ROOT_DIR}/lib/x86-64_linux/static_pic
    7579  ${ILOG_CONCERT_ROOT_DIR}/lib/${ILOG_WIN_COMPILER}/stat_mda
    7680  NO_DEFAULT_PATH
  • doc/Doxyfile.in

    r1251 r1354  
    2020STRIP_FROM_PATH        = "@abs_top_srcdir@"
    2121STRIP_FROM_INC_PATH    = "@abs_top_srcdir@"
    22 SHORT_NAMES            = YES
     22SHORT_NAMES            = NO
    2323JAVADOC_AUTOBRIEF      = NO
    2424QT_AUTOBRIEF           = NO
     
    4040SUBGROUPING            = YES
    4141TYPEDEF_HIDES_STRUCT   = NO
    42 SYMBOL_CACHE_SIZE      = 0
    4342#---------------------------------------------------------------------------
    4443# Build related configuration options
     
    7372MAX_INITIALIZER_LINES  = 5
    7473SHOW_USED_FILES        = NO
    75 SHOW_DIRECTORIES       = YES
    7674SHOW_FILES             = YES
    7775SHOW_NAMESPACES        = YES
     
    151149HTML_COLORSTYLE_GAMMA  = 80
    152150HTML_TIMESTAMP         = YES
    153 HTML_ALIGN_MEMBERS     = YES
    154151HTML_DYNAMIC_SECTIONS  = YES
    155152GENERATE_DOCSET        = NO
     
    178175ENUM_VALUES_PER_LINE   = 4
    179176GENERATE_TREEVIEW      = NO
    180 USE_INLINE_TREES       = NO
    181177TREEVIEW_WIDTH         = 250
    182178EXT_LINKS_IN_WINDOW    = NO
     
    225221GENERATE_XML           = NO
    226222XML_OUTPUT             = xml
    227 XML_SCHEMA             =
    228 XML_DTD                =
    229223XML_PROGRAMLISTING     = YES
    230224#---------------------------------------------------------------------------
     
    267261HAVE_DOT               = YES
    268262DOT_NUM_THREADS        = 0
    269 DOT_FONTNAME           = FreeSans
     263DOT_FONTNAME           =
    270264DOT_FONTSIZE           = 10
    271265DOT_FONTPATH           =
  • doc/groups.dox

    r1271 r1366  
    562562
    563563/**
     564@defgroup graph_isomorphism Graph Isomorphism
     565@ingroup algs
     566\brief Algorithms for testing (sub)graph isomorphism
     567
     568This group contains algorithms for finding isomorph copies of a
     569given graph in another one, or simply check whether two graphs are isomorphic.
     570
     571The formal definition of subgraph isomorphism is as follows.
     572
     573We are given two graphs, \f$G_1=(V_1,E_1)\f$ and \f$G_2=(V_2,E_2)\f$. A
     574function \f$f:V_1\longrightarrow V_2\f$ is called \e mapping or \e
     575embedding if \f$f(u)\neq f(v)\f$ whenever \f$u\neq v\f$.
     576
     577The standard <em>Subgraph Isomorphism Problem (SIP)</em> looks for a
     578mapping with the property that whenever \f$(u,v)\in E_1\f$, then
     579\f$(f(u),f(v))\in E_2\f$.
     580
     581In case of <em>Induced Subgraph Isomorphism Problem (ISIP)</em> one
     582also requires that if \f$(u,v)\not\in E_1\f$, then \f$(f(u),f(v))\not\in
     583E_2\f$
     584
     585In addition, the graph nodes may be \e labeled, i.e. we are given two
     586node labelings \f$l_1:V_1\longrightarrow L\f$ and \f$l_2:V_2\longrightarrow
     587L\f$ and we require that \f$l_1(u)=l_2(f(u))\f$ holds for all nodes \f$u \in
     588G_1\f$.
     589
     590*/
     591
     592/**
    564593@defgroup planar Planar Embedding and Drawing
    565594@ingroup algs
  • doc/named-param.dox

    r463 r1351  
    2626function parameters by name also when you call the function. It is
    2727especially comfortable in case of a function having tons of parameters
    28 with natural default values. Sadly, C++ lack this amenity.
     28with natural default values. Sadly, C++ lacks this amenity.
    2929
    3030However, with a crafty trick and with some little
  • doc/references.bib

    r1219 r1367  
    355355  pages =        {587--612}
    356356}
     357
     358@article{cordella2004sub,
     359  author =       {Cordella, Luigi P. and Foggia, Pasquale and Sansone,
     360                  Carlo and Vento, Mario},
     361  title =        {A (sub)graph isomorphism algorithm for matching
     362                  large graphs},
     363  journal =      {IEEE Transactions on Pattern Analysis and Machine
     364                  Intelligence},
     365  volume =       26,
     366  number =       10,
     367  pages =        {1367--1372},
     368  year =         2004
     369}
  • lemon/CMakeLists.txt

    r1264 r1315  
    5656
    5757ADD_LIBRARY(lemon ${LEMON_SOURCES})
     58
     59TARGET_LINK_LIBRARIES(lemon
     60  ${GLPK_LIBRARIES} ${COIN_LIBRARIES} ${ILOG_LIBRARIES} ${SOPLEX_LIBRARIES}
     61  )
     62
    5863IF(UNIX)
    59   SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon)
     64  SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon VERSION ${LEMON_VERSION} SOVERSION ${LEMON_VERSION})
    6065ENDIF()
    6166
  • lemon/arg_parser.h

    r959 r1327  
    2727#include <sstream>
    2828#include <algorithm>
     29#include <lemon/core.h>
    2930#include <lemon/assert.h>
    3031
  • lemon/bellman_ford.h

    r1270 r1337  
    3030#include <lemon/maps.h>
    3131#include <lemon/path.h>
     32#include <lemon/bits/stl_iterators.h>
    3233
    3334#include <limits>
     
    690691      int _index;
    691692    };
     693
     694    /// \brief Gets the collection of the active nodes.
     695    ///
     696    /// This function can be used for iterating on the active nodes of the
     697    /// Bellman-Ford algorithm after the last phase.
     698    /// These nodes should be checked in the next phase to
     699    /// find augmenting arcs outgoing from them.
     700    /// It returns a wrapped ActiveIt, which looks
     701    /// like an STL container (by having begin() and end())
     702    /// which you can use in range-based for loops, STL algorithms, etc.
     703    LemonRangeWrapper1<ActiveIt, BellmanFord>
     704    activeNodes() const {
     705      return LemonRangeWrapper1<ActiveIt, BellmanFord>(*this);
     706    }
     707
    692708
    693709    /// \name Query Functions
  • lemon/bits/edge_set_extender.h

    r1270 r1337  
    114114    };
    115115
     116    LemonRangeWrapper1<NodeIt, Digraph> nodes() const {
     117      return LemonRangeWrapper1<NodeIt, Digraph>(*this);
     118    }
    116119
    117120    class ArcIt : public Arc {
     
    137140    };
    138141
     142    LemonRangeWrapper1<ArcIt, Digraph> arcs() const {
     143      return LemonRangeWrapper1<ArcIt, Digraph>(*this);
     144    }
    139145
    140146    class OutArcIt : public Arc {
     
    161167    };
    162168
     169    LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {
     170      return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);
     171    }
    163172
    164173    class InArcIt : public Arc {
     
    184193
    185194    };
     195
     196    LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {
     197      return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);
     198    }
    186199
    187200    // \brief Base node of the iterator
     
    373386    };
    374387
     388    LemonRangeWrapper1<NodeIt, Graph> nodes() const {
     389      return LemonRangeWrapper1<NodeIt, Graph>(*this);
     390    }
    375391
    376392    class ArcIt : public Arc {
     
    396412    };
    397413
     414    LemonRangeWrapper1<ArcIt, Graph> arcs() const {
     415      return LemonRangeWrapper1<ArcIt, Graph>(*this);
     416    }
    398417
    399418    class OutArcIt : public Arc {
     
    420439    };
    421440
     441    LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {
     442      return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);
     443    }
    422444
    423445    class InArcIt : public Arc {
     
    444466    };
    445467
     468    LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {
     469      return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);
     470    }
    446471
    447472    class EdgeIt : public Parent::Edge {
     
    466491
    467492    };
     493
     494    LemonRangeWrapper1<EdgeIt, Graph> edges() const {
     495      return LemonRangeWrapper1<EdgeIt, Graph>(*this);
     496    }
    468497
    469498    class IncEdgeIt : public Parent::Edge {
     
    491520      }
    492521    };
     522
     523    LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {
     524      return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);
     525    }
    493526
    494527    // \brief Base node of the iterator
  • lemon/bits/graph_adaptor_extender.h

    r1270 r1337  
    8686    };
    8787
     88    LemonRangeWrapper1<NodeIt, Adaptor> nodes() const {
     89      return LemonRangeWrapper1<NodeIt, Adaptor>(*this);
     90    }
    8891
    8992    class ArcIt : public Arc {
     
    108111
    109112    };
     113
     114    LemonRangeWrapper1<ArcIt, Adaptor> arcs() const {
     115      return LemonRangeWrapper1<ArcIt, Adaptor>(*this);
     116    }
    110117
    111118
     
    133140    };
    134141
     142    LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {
     143      return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);
     144    }
     145
    135146
    136147    class InArcIt : public Arc {
     
    156167
    157168    };
     169
     170    LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {
     171      return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);
     172    }
    158173
    159174    Node baseNode(const OutArcIt &e) const {
     
    255270    };
    256271
     272    LemonRangeWrapper1<NodeIt, Adaptor> nodes() const {
     273      return LemonRangeWrapper1<NodeIt, Adaptor>(*this);
     274    }
     275
    257276
    258277    class ArcIt : public Arc {
     
    277296
    278297    };
     298
     299    LemonRangeWrapper1<ArcIt, Adaptor> arcs() const {
     300      return LemonRangeWrapper1<ArcIt, Adaptor>(*this);
     301    }
    279302
    280303
     
    302325    };
    303326
     327    LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {
     328      return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);
     329    }
     330
    304331
    305332    class InArcIt : public Arc {
     
    326353    };
    327354
     355    LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {
     356      return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);
     357    }
     358
    328359    class EdgeIt : public Parent::Edge {
    329360      const Adaptor* _adaptor;
     
    347378
    348379    };
     380
     381    LemonRangeWrapper1<EdgeIt, Adaptor> edges() const {
     382      return LemonRangeWrapper1<EdgeIt, Adaptor>(*this);
     383    }
     384
    349385
    350386    class IncEdgeIt : public Edge {
     
    373409    };
    374410
     411    LemonRangeWrapper2<IncEdgeIt, Adaptor, Node> incEdges(const Node& u) const {
     412      return LemonRangeWrapper2<IncEdgeIt, Adaptor, Node>(*this, u);
     413    }
     414
     415
    375416    Node baseNode(const OutArcIt &a) const {
    376417      return Parent::source(a);
  • lemon/bits/graph_extender.h

    r1270 r1336  
    2828#include <lemon/concepts/maps.h>
    2929
     30#include <lemon/bits/stl_iterators.h>
     31
    3032//\ingroup graphbits
    3133//\file
     
    117119    };
    118120
     121    LemonRangeWrapper1<NodeIt, Digraph> nodes() const {
     122      return LemonRangeWrapper1<NodeIt, Digraph>(*this);
     123    }
     124
    119125
    120126    class ArcIt : public Arc {
     
    139145
    140146    };
     147
     148    LemonRangeWrapper1<ArcIt, Digraph> arcs() const {
     149      return LemonRangeWrapper1<ArcIt, Digraph>(*this);
     150    }
    141151
    142152
     
    164174    };
    165175
     176    LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {
     177      return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);
     178    }
     179
    166180
    167181    class InArcIt : public Arc {
     
    187201
    188202    };
     203
     204    LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {
     205      return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);
     206    }
    189207
    190208    // \brief Base node of the iterator
     
    437455    };
    438456
     457    LemonRangeWrapper1<NodeIt, Graph> nodes() const {
     458      return LemonRangeWrapper1<NodeIt, Graph>(*this);
     459    }
     460
    439461
    440462    class ArcIt : public Arc {
     
    459481
    460482    };
     483
     484    LemonRangeWrapper1<ArcIt, Graph> arcs() const {
     485      return LemonRangeWrapper1<ArcIt, Graph>(*this);
     486    }
    461487
    462488
     
    484510    };
    485511
     512    LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {
     513      return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);
     514    }
     515
    486516
    487517    class InArcIt : public Arc {
     
    508538    };
    509539
     540    LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {
     541      return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);
     542    }
     543
    510544
    511545    class EdgeIt : public Parent::Edge {
     
    530564
    531565    };
     566
     567    LemonRangeWrapper1<EdgeIt, Graph> edges() const {
     568      return LemonRangeWrapper1<EdgeIt, Graph>(*this);
     569    }
     570
    532571
    533572    class IncEdgeIt : public Parent::Edge {
     
    555594      }
    556595    };
     596
     597    LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {
     598      return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);
     599    }
     600
    557601
    558602    // \brief Base node of the iterator
     
    904948    };
    905949
     950    LemonRangeWrapper1<NodeIt, BpGraph> nodes() const {
     951      return LemonRangeWrapper1<NodeIt, BpGraph>(*this);
     952    }
     953
     954
    906955    class RedNodeIt : public RedNode {
    907956      const BpGraph* _graph;
     
    926975    };
    927976
     977    LemonRangeWrapper1<RedNodeIt, BpGraph> redNodes() const {
     978      return LemonRangeWrapper1<RedNodeIt, BpGraph>(*this);
     979    }
     980
     981
    928982    class BlueNodeIt : public BlueNode {
    929983      const BpGraph* _graph;
     
    9481002    };
    9491003
     1004    LemonRangeWrapper1<BlueNodeIt, BpGraph> blueNodes() const {
     1005      return LemonRangeWrapper1<BlueNodeIt, BpGraph>(*this);
     1006    }
     1007
     1008
    9501009
    9511010    class ArcIt : public Arc {
     
    9701029
    9711030    };
     1031
     1032    LemonRangeWrapper1<ArcIt, BpGraph> arcs() const {
     1033      return LemonRangeWrapper1<ArcIt, BpGraph>(*this);
     1034    }
    9721035
    9731036
     
    9951058    };
    9961059
     1060    LemonRangeWrapper2<OutArcIt, BpGraph, Node> outArcs(const Node& u) const {
     1061      return LemonRangeWrapper2<OutArcIt, BpGraph, Node>(*this, u);
     1062    }
     1063
    9971064
    9981065    class InArcIt : public Arc {
     
    10191086    };
    10201087
     1088    LemonRangeWrapper2<InArcIt, BpGraph, Node> inArcs(const Node& u) const {
     1089      return LemonRangeWrapper2<InArcIt, BpGraph, Node>(*this, u);
     1090    }
     1091
    10211092
    10221093    class EdgeIt : public Parent::Edge {
     
    10411112
    10421113    };
     1114
     1115    LemonRangeWrapper1<EdgeIt, BpGraph> edges() const {
     1116      return LemonRangeWrapper1<EdgeIt, BpGraph>(*this);
     1117    }
     1118
    10431119
    10441120    class IncEdgeIt : public Parent::Edge {
     
    10661142      }
    10671143    };
     1144
     1145    LemonRangeWrapper2<IncEdgeIt, BpGraph, Node> incEdges(const Node& u) const {
     1146      return LemonRangeWrapper2<IncEdgeIt, BpGraph, Node>(*this, u);
     1147    }
     1148
    10681149
    10691150    // \brief Base node of the iterator
  • lemon/bits/path_dump.h

    r1270 r1338  
    6262      }
    6363
    64       operator const typename Digraph::Arc() const {
     64      operator typename Digraph::Arc() const {
    6565        return path->predMap[current];
    6666      }
  • lemon/bits/windows.cc

    r1270 r1341  
    2222#include<lemon/bits/windows.h>
    2323
    24 #ifdef WIN32
     24#if defined(LEMON_WIN32) && defined(__GNUC__)
     25#pragma GCC diagnostic ignored "-Wold-style-cast"
     26#endif
     27
     28#ifdef LEMON_WIN32
    2529#ifndef WIN32_LEAN_AND_MEAN
    2630#define WIN32_LEAN_AND_MEAN
     
    4145#include <unistd.h>
    4246#include <ctime>
    43 #ifndef WIN32
     47#ifndef LEMON_WIN32
    4448#include <sys/times.h>
    4549#endif
     
    5660                         double &cutime, double &cstime)
    5761    {
    58 #ifdef WIN32
     62#ifdef LEMON_WIN32
    5963      static const double ch = 4294967296.0e-7;
    6064      static const double cl = 1.0e-7;
     
    9599    {
    96100      std::ostringstream os;
    97 #ifdef WIN32
     101#ifdef LEMON_WIN32
    98102      SYSTEMTIME time;
    99103      GetSystemTime(&time);
    100104      char buf1[11], buf2[9], buf3[5];
    101           if (GetDateFormat(MY_LOCALE, 0, &time,
     105      if (GetDateFormat(MY_LOCALE, 0, &time,
    102106                        ("ddd MMM dd"), buf1, 11) &&
    103107          GetTimeFormat(MY_LOCALE, 0, &time,
     
    121125    int getWinRndSeed()
    122126    {
    123 #ifdef WIN32
     127#ifdef LEMON_WIN32
    124128      FILETIME time;
    125129      GetSystemTimeAsFileTime(&time);
     
    133137
    134138    WinLock::WinLock() {
    135 #ifdef WIN32
     139#ifdef LEMON_WIN32
    136140      CRITICAL_SECTION *lock = new CRITICAL_SECTION;
    137141      InitializeCriticalSection(lock);
     
    143147
    144148    WinLock::~WinLock() {
    145 #ifdef WIN32
     149#ifdef LEMON_WIN32
    146150      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
    147151      DeleteCriticalSection(lock);
     
    151155
    152156    void WinLock::lock() {
    153 #ifdef WIN32
     157#ifdef LEMON_WIN32
    154158      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
    155159      EnterCriticalSection(lock);
     
    158162
    159163    void WinLock::unlock() {
    160 #ifdef WIN32
     164#ifdef LEMON_WIN32
    161165      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
    162166      LeaveCriticalSection(lock);
  • lemon/bits/windows.h

    r1270 r1340  
    2020#define LEMON_BITS_WINDOWS_H
    2121
     22#include <lemon/config.h>
    2223#include <string>
    2324
     
    3536      ~WinLock();
    3637      void lock();
    37       void unlock();
     38      void unlock();\
    3839    private:
    3940      void *_repr;
  • lemon/capacity_scaling.h

    r1270 r1363  
    2828#include <limits>
    2929#include <lemon/core.h>
     30#include <lemon/maps.h>
    3031#include <lemon/bin_heap.h>
    3132
     
    164165
    165166    // Parameters of the problem
    166     bool _have_lower;
     167    bool _has_lower;
    167168    Value _sum_supply;
    168169
     
    357358    template <typename LowerMap>
    358359    CapacityScaling& lowerMap(const LowerMap& map) {
    359       _have_lower = true;
     360      _has_lower = true;
    360361      for (ArcIt a(_graph); a != INVALID; ++a) {
    361362        _lower[_arc_idf[a]] = map[a];
    362         _lower[_arc_idb[a]] = map[a];
    363363      }
    364364      return *this;
     
    544544        _cost[j] = _forward[j] ? 1 : -1;
    545545      }
    546       _have_lower = false;
     546      _has_lower = false;
    547547      return *this;
    548548    }
     
    755755      const Value MAX = std::numeric_limits<Value>::max();
    756756      int last_out;
    757       if (_have_lower) {
     757      if (_has_lower) {
    758758        for (int i = 0; i != _root; ++i) {
    759759          last_out = _first_out[i+1];
     
    840840    }
    841841
    842     // Check if the upper bound is greater or equal to the lower bound
    843     // on each arc.
     842    // Check if the upper bound is greater than or equal to the lower bound
     843    // on each forward arc.
    844844    bool checkBoundMaps() {
    845845      for (int j = 0; j != _res_arc_num; ++j) {
    846         if (_upper[j] < _lower[j]) return false;
     846        if (_forward[j] && _upper[j] < _lower[j]) return false;
    847847      }
    848848      return true;
     
    858858
    859859      // Handle non-zero lower bounds
    860       if (_have_lower) {
     860      if (_has_lower) {
    861861        int limit = _first_out[_root];
    862862        for (int j = 0; j != limit; ++j) {
    863           if (!_forward[j]) _res_cap[j] += _lower[j];
     863          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    864864        }
    865865      }
  • lemon/cbc.cc

    r1270 r1336  
    112112
    113113  void CbcMip::_eraseColId(int i) {
    114     cols.eraseIndex(i);
     114    _cols.eraseIndex(i);
    115115  }
    116116
    117117  void CbcMip::_eraseRowId(int i) {
    118     rows.eraseIndex(i);
     118    _rows.eraseIndex(i);
    119119  }
    120120
  • lemon/clp.cc

    r1270 r1336  
    3030  ClpLp::ClpLp(const ClpLp& other) {
    3131    _prob = new ClpSimplex(*other._prob);
    32     rows = other.rows;
    33     cols = other.cols;
     32    _rows = other._rows;
     33    _cols = other._cols;
    3434    _init_temporals();
    3535    messageLevel(MESSAGE_NOTHING);
     
    104104
    105105  void ClpLp::_eraseColId(int i) {
    106     cols.eraseIndex(i);
    107     cols.shiftIndices(i);
     106    _cols.eraseIndex(i);
     107    _cols.shiftIndices(i);
    108108  }
    109109
    110110  void ClpLp::_eraseRowId(int i) {
    111     rows.eraseIndex(i);
    112     rows.shiftIndices(i);
     111    _rows.eraseIndex(i);
     112    _rows.shiftIndices(i);
    113113  }
    114114
  • lemon/clp.h

    r1270 r1336  
    152152
    153153    ///Returns the constraint identifier understood by CLP.
    154     int clpRow(Row r) const { return rows(id(r)); }
     154    int clpRow(Row r) const { return _rows(id(r)); }
    155155
    156156    ///Returns the variable identifier understood by CLP.
    157     int clpCol(Col c) const { return cols(id(c)); }
     157    int clpCol(Col c) const { return _cols(id(c)); }
    158158
    159159  };
  • lemon/concepts/bpgraph.h

    r1270 r1336  
    2828#include <lemon/concept_check.h>
    2929#include <lemon/core.h>
     30#include <lemon/bits/stl_iterators.h>
    3031
    3132namespace lemon {
     
    222223      };
    223224
     225      /// \brief Gets the collection of the red nodes of the graph.
     226      ///
     227      /// This function can be used for iterating on
     228      /// the red nodes of the graph. It returns a wrapped RedNodeIt,
     229      /// which looks like an STL container (by having begin() and end())
     230      /// which you can use in range-based for loops, stl algorithms, etc.
     231      /// For example if g is a BpGraph, you can write:
     232      ///\code
     233      /// for(auto v: g.redNodes())
     234      ///   doSomething(v);
     235      ///\endcode
     236      LemonRangeWrapper1<RedNodeIt, BpGraph> redNodes() const {
     237        return LemonRangeWrapper1<RedNodeIt, BpGraph>(*this);
     238      }
     239
     240
    224241      /// Iterator class for the blue nodes.
    225242
     
    265282      };
    266283
     284      /// \brief Gets the collection of the blue nodes of the graph.
     285      ///
     286      /// This function can be used for iterating on
     287      /// the blue nodes of the graph. It returns a wrapped BlueNodeIt,
     288      /// which looks like an STL container (by having begin() and end())
     289      /// which you can use in range-based for loops, stl algorithms, etc.
     290      /// For example if g is a BpGraph, you can write:
     291      ///\code
     292      /// for(auto v: g.blueNodes())
     293      ///   doSomething(v);
     294      ///\endcode
     295      LemonRangeWrapper1<BlueNodeIt, BpGraph> blueNodes() const {
     296        return LemonRangeWrapper1<BlueNodeIt, BpGraph>(*this);
     297      }
     298
     299
    267300      /// Iterator class for the nodes.
    268301
     
    307340        NodeIt& operator++() { return *this; }
    308341      };
     342
     343      /// \brief Gets the collection of the nodes of the graph.
     344      ///
     345      /// This function can be used for iterating on
     346      /// the nodes of the graph. It returns a wrapped NodeIt,
     347      /// which looks like an STL container (by having begin() and end())
     348      /// which you can use in range-based for loops, stl algorithms, etc.
     349      /// For example if g is a BpGraph, you can write:
     350      ///\code
     351      /// for(auto v: g.nodes())
     352      ///   doSomething(v);
     353      ///\endcode
     354      LemonRangeWrapper1<NodeIt, BpGraph> nodes() const {
     355        return LemonRangeWrapper1<NodeIt, BpGraph>(*this);
     356      }
     357
    309358
    310359
     
    395444        EdgeIt& operator++() { return *this; }
    396445      };
     446
     447      /// \brief Gets the collection of the edges of the graph.
     448      ///
     449      /// This function can be used for iterating on the
     450      /// edges of the graph. It returns a wrapped
     451      /// EdgeIt, which looks like an STL container
     452      /// (by having begin() and end()) which you can use in range-based
     453      /// for loops, stl algorithms, etc.
     454      /// For example if g is a BpGraph, you can write:
     455      ///\code
     456      /// for(auto e: g.edges())
     457      ///   doSomething(e);
     458      ///\endcode
     459      LemonRangeWrapper1<EdgeIt, BpGraph> edges() const {
     460        return LemonRangeWrapper1<EdgeIt, BpGraph>(*this);
     461      }
     462
    397463
    398464      /// Iterator class for the incident edges of a node.
     
    444510      };
    445511
     512      /// \brief Gets the collection of the incident edges
     513      ///  of a certain node of the graph.
     514      ///
     515      /// This function can be used for iterating on the
     516      /// incident undirected edges of a certain node of the graph.
     517      /// It returns a wrapped
     518      /// IncEdgeIt, which looks like an STL container
     519      /// (by having begin() and end()) which you can use in range-based
     520      /// for loops, stl algorithms, etc.
     521      /// For example if g is a BpGraph and u is a Node, you can write:
     522      ///\code
     523      /// for(auto e: g.incEdges(u))
     524      ///   doSomething(e);
     525      ///\endcode
     526      LemonRangeWrapper2<IncEdgeIt, BpGraph, Node> incEdges(const Node& u) const {
     527        return LemonRangeWrapper2<IncEdgeIt, BpGraph, Node>(*this, u);
     528      }
     529
     530
    446531      /// The arc type of the graph
    447532
     
    540625      };
    541626
     627      /// \brief Gets the collection of the directed arcs of the graph.
     628      ///
     629      /// This function can be used for iterating on the
     630      /// arcs of the graph. It returns a wrapped
     631      /// ArcIt, which looks like an STL container
     632      /// (by having begin() and end()) which you can use in range-based
     633      /// for loops, stl algorithms, etc.
     634      /// For example if g is a BpGraph you can write:
     635      ///\code
     636      /// for(auto a: g.arcs())
     637      ///   doSomething(a);
     638      ///\endcode
     639      LemonRangeWrapper1<ArcIt, BpGraph> arcs() const {
     640        return LemonRangeWrapper1<ArcIt, BpGraph>(*this);
     641      }
     642
     643
    542644      /// Iterator class for the outgoing arcs of a node.
    543645
     
    588690      };
    589691
     692      /// \brief Gets the collection of the outgoing directed arcs of a
     693      /// certain node of the graph.
     694      ///
     695      /// This function can be used for iterating on the
     696      /// outgoing arcs of a certain node of the graph. It returns a wrapped
     697      /// OutArcIt, which looks like an STL container
     698      /// (by having begin() and end()) which you can use in range-based
     699      /// for loops, stl algorithms, etc.
     700      /// For example if g is a BpGraph and u is a Node, you can write:
     701      ///\code
     702      /// for(auto a: g.outArcs(u))
     703      ///   doSomething(a);
     704      ///\endcode
     705      LemonRangeWrapper2<OutArcIt, BpGraph, Node> outArcs(const Node& u) const {
     706        return LemonRangeWrapper2<OutArcIt, BpGraph, Node>(*this, u);
     707      }
     708
     709
    590710      /// Iterator class for the incoming arcs of a node.
    591711
     
    635755        InArcIt& operator++() { return *this; }
    636756      };
     757
     758      /// \brief Gets the collection of the incoming directed arcs of a
     759      /// certain node of the graph.
     760      ///
     761      /// This function can be used for iterating on the
     762      /// incoming arcs of a certain node of the graph. It returns a wrapped
     763      /// InArcIt, which looks like an STL container
     764      /// (by having begin() and end()) which you can use in range-based
     765      /// for loops, stl algorithms, etc.
     766      /// For example if g is a BpGraph and u is a Node, you can write:
     767      ///\code
     768      /// for(auto a: g.inArcs(u))
     769      ///   doSomething(a);
     770      ///\endcode
     771      LemonRangeWrapper2<InArcIt, BpGraph, Node> inArcs(const Node& u) const {
     772        return LemonRangeWrapper2<InArcIt, BpGraph, Node>(*this, u);
     773      }
     774
    637775
    638776      /// \brief Standard graph map type for the nodes.
  • lemon/concepts/digraph.h

    r1271 r1336  
    2828#include <lemon/concept_check.h>
    2929#include <lemon/concepts/graph_components.h>
     30#include <lemon/bits/stl_iterators.h>
    3031
    3132namespace lemon {
     
    148149      };
    149150
     151      /// \brief Gets the collection of the nodes of the digraph.
     152      ///
     153      /// This function can be used for iterating on
     154      /// the nodes of the digraph. It returns a wrapped NodeIt, which looks
     155      /// like an STL container (by having begin() and end())
     156      /// which you can use in range-based for loops, STL algorithms, etc.
     157      /// For example you can write:
     158      ///\code
     159      /// ListDigraph g;
     160      /// for(auto v: g.nodes())
     161      ///   doSomething(v);
     162      ///
     163      /// //Using an STL algorithm:
     164      /// copy(g.nodes().begin(), g.nodes().end(), vect.begin());
     165      ///\endcode
     166      LemonRangeWrapper1<NodeIt, Digraph> nodes() const {
     167        return LemonRangeWrapper1<NodeIt, Digraph>(*this);
     168      }
     169
    150170
    151171      /// The arc type of the digraph
     
    238258      };
    239259
     260      /// \brief Gets the collection of the outgoing arcs of a certain node
     261      /// of the digraph.
     262      ///
     263      /// This function can be used for iterating on the
     264      /// outgoing arcs of a certain node of the digraph. It returns a wrapped
     265      /// OutArcIt, which looks like an STL container
     266      /// (by having begin() and end()) which you can use in range-based
     267      /// for loops, STL algorithms, etc.
     268      /// For example if g is a Digraph and u is a node, you can write:
     269      ///\code
     270      /// for(auto a: g.outArcs(u))
     271      ///   doSomething(a);
     272      ///
     273      /// //Using an STL algorithm:
     274      /// copy(g.outArcs(u).begin(), g.outArcs(u).end(), vect.begin());
     275      ///\endcode
     276      LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {
     277        return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);
     278      }
     279
     280
    240281      /// Iterator class for the incoming arcs of a node.
    241282
     
    283324      };
    284325
     326      /// \brief Gets the collection of the incoming arcs of a certain node
     327      /// of the digraph.
     328      ///
     329      /// This function can be used for iterating on the
     330      /// incoming arcs of a certain node of the digraph. It returns a wrapped
     331      /// InArcIt, which looks like an STL container
     332      /// (by having begin() and end()) which you can use in range-based
     333      /// for loops, STL algorithms, etc.
     334      /// For example if g is a Digraph and u is a node, you can write:
     335      ///\code
     336      /// for(auto a: g.inArcs(u))
     337      ///   doSomething(a);
     338      ///
     339      /// //Using an STL algorithm:
     340      /// copy(g.inArcs(u).begin(), g.inArcs(u).end(), vect.begin());
     341      ///\endcode
     342      LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {
     343        return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);
     344      }
     345
     346
    285347      /// Iterator class for the arcs.
    286348
     
    327389        ArcIt& operator++() { return *this; }
    328390      };
     391
     392      /// \brief Gets the collection of the arcs of the digraph.
     393      ///
     394      /// This function can be used for iterating on the
     395      /// arcs of the digraph. It returns a wrapped
     396      /// ArcIt, which looks like an STL container
     397      /// (by having begin() and end()) which you can use in range-based
     398      /// for loops, STL algorithms, etc.
     399      /// For example you can write:
     400      ///\code
     401      /// ListDigraph g;
     402      /// for(auto a: g.arcs())
     403      ///   doSomething(a);
     404      ///
     405      /// //Using an STL algorithm:
     406      /// copy(g.arcs().begin(), g.arcs().end(), vect.begin());
     407      ///\endcode
     408      LemonRangeWrapper1<ArcIt, Digraph> arcs() const {
     409        return LemonRangeWrapper1<ArcIt, Digraph>(*this);
     410      }
     411
    329412
    330413      /// \brief The source node of the arc.
  • lemon/concepts/graph.h

    r1271 r1336  
    2828#include <lemon/concept_check.h>
    2929#include <lemon/core.h>
     30#include <lemon/bits/stl_iterators.h>
    3031
    3132namespace lemon {
     
    181182      };
    182183
     184      /// \brief Gets the collection of the nodes of the graph.
     185      ///
     186      /// This function can be used for iterating on
     187      /// the nodes of the graph. It returns a wrapped NodeIt, which looks
     188      /// like an STL container (by having begin() and end())
     189      /// which you can use in range-based for loops, STL algorithms, etc.
     190      /// For example you can write:
     191      ///\code
     192      /// ListGraph g;
     193      /// for(auto v: g.nodes())
     194      ///   doSomething(v);
     195      ///
     196      /// //Using an STL algorithm:
     197      /// copy(g.nodes().begin(), g.nodes().end(), vect.begin());
     198      ///\endcode
     199      LemonRangeWrapper1<NodeIt, Graph> nodes() const {
     200        return LemonRangeWrapper1<NodeIt, Graph>(*this);
     201      }
     202
    183203
    184204      /// The edge type of the graph
     
    268288        EdgeIt& operator++() { return *this; }
    269289      };
     290
     291      /// \brief Gets the collection of the edges of the graph.
     292      ///
     293      /// This function can be used for iterating on the
     294      /// edges of the graph. It returns a wrapped
     295      /// EdgeIt, which looks like an STL container
     296      /// (by having begin() and end()) which you can use in range-based
     297      /// for loops, STL algorithms, etc.
     298      /// For example you can write:
     299      ///\code
     300      /// ListGraph g;
     301      /// for(auto e: g.edges())
     302      ///   doSomething(e);
     303      ///
     304      /// //Using an STL algorithm:
     305      /// copy(g.edges().begin(), g.edges().end(), vect.begin());
     306      ///\endcode
     307      LemonRangeWrapper1<EdgeIt, Graph> edges() const {
     308        return LemonRangeWrapper1<EdgeIt, Graph>(*this);
     309      }
     310
    270311
    271312      /// Iterator class for the incident edges of a node.
     
    317358      };
    318359
     360      /// \brief Gets the collection of the incident undirected edges
     361      ///  of a certain node of the graph.
     362      ///
     363      /// This function can be used for iterating on the
     364      /// incident undirected edges of a certain node of the graph.
     365      /// It returns a wrapped
     366      /// IncEdgeIt, which looks like an STL container
     367      /// (by having begin() and end()) which you can use in range-based
     368      /// for loops, STL algorithms, etc.
     369      /// For example if g is a Graph and u is a Node, you can write:
     370      ///\code
     371      /// for(auto e: g.incEdges(u))
     372      ///   doSomething(e);
     373      ///
     374      /// //Using an STL algorithm:
     375      /// copy(g.incEdges(u).begin(), g.incEdges(u).end(), vect.begin());
     376      ///\endcode
     377      LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {
     378        return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);
     379      }
     380
     381
    319382      /// The arc type of the graph
    320383
     
    411474        ArcIt& operator++() { return *this; }
    412475      };
     476
     477      /// \brief Gets the collection of the directed arcs of the graph.
     478      ///
     479      /// This function can be used for iterating on the
     480      /// arcs of the graph. It returns a wrapped
     481      /// ArcIt, which looks like an STL container
     482      /// (by having begin() and end()) which you can use in range-based
     483      /// for loops, STL algorithms, etc.
     484      /// For example you can write:
     485      ///\code
     486      /// ListGraph g;
     487      /// for(auto a: g.arcs())
     488      ///   doSomething(a);
     489      ///
     490      /// //Using an STL algorithm:
     491      /// copy(g.arcs().begin(), g.arcs().end(), vect.begin());
     492      ///\endcode
     493      LemonRangeWrapper1<ArcIt, Graph> arcs() const {
     494        return LemonRangeWrapper1<ArcIt, Graph>(*this);
     495      }
     496
    413497
    414498      /// Iterator class for the outgoing arcs of a node.
     
    460544      };
    461545
     546      /// \brief Gets the collection of the outgoing directed arcs of a
     547      /// certain node of the graph.
     548      ///
     549      /// This function can be used for iterating on the
     550      /// outgoing arcs of a certain node of the graph. It returns a wrapped
     551      /// OutArcIt, which looks like an STL container
     552      /// (by having begin() and end()) which you can use in range-based
     553      /// for loops, STL algorithms, etc.
     554      /// For example if g is a Graph and u is a Node, you can write:
     555      ///\code
     556      /// for(auto a: g.outArcs(u))
     557      ///   doSomething(a);
     558      ///
     559      /// //Using an STL algorithm:
     560      /// copy(g.outArcs(u).begin(), g.outArcs(u).end(), vect.begin());
     561      ///\endcode
     562      LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {
     563        return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);
     564      }
     565
     566
    462567      /// Iterator class for the incoming arcs of a node.
    463568
     
    507612        InArcIt& operator++() { return *this; }
    508613      };
     614
     615      /// \brief Gets the collection of the incoming directed arcs of
     616      /// a certain node of the graph.
     617      ///
     618      /// This function can be used for iterating on the
     619      /// incoming directed arcs of a certain node of the graph. It returns
     620      /// a wrapped InArcIt, which looks like an STL container
     621      /// (by having begin() and end()) which you can use in range-based
     622      /// for loops, STL algorithms, etc.
     623      /// For example if g is a Graph and u is a Node, you can write:
     624      ///\code
     625      /// for(auto a: g.inArcs(u))
     626      ///   doSomething(a);
     627      ///
     628      /// //Using an STL algorithm:
     629      /// copy(g.inArcs(u).begin(), g.inArcs(u).end(), vect.begin());
     630      ///\endcode
     631      LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {
     632        return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);
     633      }
    509634
    510635      /// \brief Standard graph map type for the nodes.
  • lemon/concepts/path.h

    r1270 r1336  
    2727#include <lemon/core.h>
    2828#include <lemon/concept_check.h>
     29#include <lemon/bits/stl_iterators.h>
    2930
    3031namespace lemon {
     
    116117      };
    117118
     119      /// \brief Gets the collection of the arcs of the path.
     120      ///
     121      /// This function can be used for iterating on the
     122      /// arcs of the path. It returns a wrapped
     123      /// ArcIt, which looks like an STL container
     124      /// (by having begin() and end()) which you can use in range-based
     125      /// for loops, STL algorithms, etc.
     126      /// For example you can write:
     127      ///\code
     128      /// for(auto a: p.arcs())
     129      ///   doSomething(a);
     130      ///\endcode
     131      LemonRangeWrapper1<ArcIt, Path> arcs() const {
     132        return LemonRangeWrapper1<ArcIt, Path>(*this);
     133      }
     134
     135
    118136      template <typename _Path>
    119137      struct Constraints {
     
    264282
    265283      };
     284
     285      /// \brief Gets the collection of the arcs of the path.
     286      ///
     287      /// This function can be used for iterating on the
     288      /// arcs of the path. It returns a wrapped
     289      /// ArcIt, which looks like an STL container
     290      /// (by having begin() and end()) which you can use in range-based
     291      /// for loops, STL algorithms, etc.
     292      /// For example you can write:
     293      ///\code
     294      /// for(auto a: p.arcs())
     295      ///   doSomething(a);
     296      ///\endcode
     297      LemonRangeWrapper1<ArcIt, PathDumper> arcs() const {
     298        return LemonRangeWrapper1<ArcIt, PathDumper>(*this);
     299      }
     300
    266301
    267302      /// \brief LEMON style iterator for enumerating the arcs of a path
     
    294329      };
    295330
     331      /// \brief Gets the collection of the arcs of the path
     332      /// in reverse direction.
     333      ///
     334      /// This function can be used for iterating on the
     335      /// arcs of the path in reverse direction. It returns a wrapped
     336      /// RevArcIt, which looks like an STL container
     337      /// (by having begin() and end()) which you can use in range-based
     338      /// for loops, STL algorithms, etc.
     339      /// For example you can write:
     340      ///\code
     341      /// for(auto a: p.revArcs())
     342      ///   doSomething(a);
     343      ///\endcode
     344      LemonRangeWrapper1<RevArcIt, PathDumper> revArcs() const {
     345        return LemonRangeWrapper1<RevArcIt, PathDumper>(*this);
     346      }
     347
     348
    296349      template <typename _Path>
    297350      struct Constraints {
  • lemon/config.h.in

    r1264 r1343  
     1#ifndef LEMON_CONFIG_H
     2#define LEMON_CONFIG_H
     3
    14#define LEMON_VERSION "@PROJECT_VERSION@"
    25#cmakedefine LEMON_HAVE_LONG_LONG 1
     6
     7#cmakedefine LEMON_CXX11 1
     8
     9#cmakedefine LEMON_WIN32 1
     10
    311#cmakedefine LEMON_HAVE_LP 1
    412#cmakedefine LEMON_HAVE_MIP 1
     
    816#cmakedefine LEMON_HAVE_CLP 1
    917#cmakedefine LEMON_HAVE_CBC 1
    10 #cmakedefine LEMON_DEFAULT_LP @LEMON_DEFAULT_LP@
    11 #cmakedefine LEMON_DEFAULT_MIP @LEMON_DEFAULT_MIP@
     18
     19#define LEMON_CPLEX_ 1
     20#define LEMON_CLP_ 2
     21#define LEMON_GLPK_ 3
     22#define LEMON_SOPLEX_ 4
     23#define LEMON_CBC_ 5
     24
     25#cmakedefine LEMON_DEFAULT_LP LEMON_@LEMON_DEFAULT_LP@_
     26#cmakedefine LEMON_DEFAULT_MIP LEMON_@LEMON_DEFAULT_MIP@_
     27
    1228#cmakedefine LEMON_USE_PTHREAD 1
    1329#cmakedefine LEMON_USE_WIN32_THREADS 1
     30
     31#endif
  • lemon/core.h

    r1270 r1341  
    2020#define LEMON_CORE_H
    2121
    22 #include <vector>
    23 #include <algorithm>
    24 
    25 #include <lemon/config.h>
    26 #include <lemon/bits/enable_if.h>
    27 #include <lemon/bits/traits.h>
    28 #include <lemon/assert.h>
    29 
    30 // Disable the following warnings when compiling with MSVC:
    31 // C4250: 'class1' : inherits 'class2::member' via dominance
    32 // C4355: 'this' : used in base member initializer list
    33 // C4503: 'function' : decorated name length exceeded, name was truncated
    34 // C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
    35 // C4996: 'function': was declared deprecated
    36 #ifdef _MSC_VER
    37 #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"
    49 #endif
    50 
    5122///\file
    5223///\brief LEMON core utilities.
     
    5526///It is automatically included by all graph types, therefore it usually
    5627///do not have to be included directly.
     28
     29// Disable the following warnings when compiling with MSVC:
     30// C4250: 'class1' : inherits 'class2::member' via dominance
     31// C4267: conversion from 'size_t' to 'type', possible loss of data
     32// C4355: 'this' : used in base member initializer list
     33// C4503: 'function' : decorated name length exceeded, name was truncated
     34// C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
     35// C4996: 'function': was declared deprecated
     36#ifdef _MSC_VER
     37#pragma warning( disable : 4250 4267 4355 4503 4800 4996 )
     38#endif
     39
     40#if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)
     41// Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8
     42#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
     43#endif
     44
     45#include <vector>
     46#include <algorithm>
     47
     48#include <lemon/config.h>
     49#include <lemon/bits/enable_if.h>
     50#include <lemon/bits/traits.h>
     51#include <lemon/assert.h>
     52
     53
    5754
    5855namespace lemon {
  • lemon/cost_scaling.h

    r1271 r1298  
    257257
    258258    // Parameters of the problem
    259     bool _have_lower;
     259    bool _has_lower;
    260260    Value _sum_supply;
    261261    int _sup_node_num;
     
    373373    template <typename LowerMap>
    374374    CostScaling& lowerMap(const LowerMap& map) {
    375       _have_lower = true;
     375      _has_lower = true;
    376376      for (ArcIt a(_graph); a != INVALID; ++a) {
    377377        _lower[_arc_idf[a]] = map[a];
    378         _lower[_arc_idb[a]] = map[a];
    379378      }
    380379      return *this;
     
    569568        _scost[_reverse[j]] = 0;
    570569      }
    571       _have_lower = false;
     570      _has_lower = false;
    572571      return *this;
    573572    }
     
    781780      const Value MAX = std::numeric_limits<Value>::max();
    782781      int last_out;
    783       if (_have_lower) {
     782      if (_has_lower) {
    784783        for (int i = 0; i != _root; ++i) {
    785784          last_out = _first_out[i+1];
     
    838837        sup[n] = _supply[_node_id[n]];
    839838      }
    840       if (_have_lower) {
     839      if (_has_lower) {
    841840        for (ArcIt a(_graph); a != INVALID; ++a) {
    842841          int j = _arc_idf[a];
     
    908907    }
    909908
    910     // Check if the upper bound is greater or equal to the lower bound
    911     // on each arc.
     909    // Check if the upper bound is greater than or equal to the lower bound
     910    // on each forward arc.
    912911    bool checkBoundMaps() {
    913912      for (int j = 0; j != _res_arc_num; ++j) {
    914         if (_upper[j] < _lower[j]) return false;
     913        if (_forward[j] && _upper[j] < _lower[j]) return false;
    915914      }
    916915      return true;
     
    992991
    993992      // Handle non-zero lower bounds
    994       if (_have_lower) {
     993      if (_has_lower) {
    995994        int limit = _first_out[_root];
    996995        for (int j = 0; j != limit; ++j) {
    997           if (!_forward[j]) _res_cap[j] += _lower[j];
     996          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    998997        }
    999998      }
  • lemon/counter.h

    r833 r1327  
    2222#include <string>
    2323#include <iostream>
     24
     25#include <lemon/core.h>
    2426
    2527///\ingroup timecount
  • lemon/cplex.cc

    r1270 r1349  
    3838  }
    3939
     40  void CplexEnv::incCnt()
     41  {
     42    _cnt_lock->lock();
     43    ++(*_cnt);
     44    _cnt_lock->unlock();
     45  }
     46
     47  void CplexEnv::decCnt()
     48  {
     49    _cnt_lock->lock();
     50    --(*_cnt);
     51    if (*_cnt == 0) {
     52      delete _cnt;
     53      _cnt_lock->unlock();
     54      delete _cnt_lock;
     55      CPXcloseCPLEX(&_env);
     56    }
     57    else _cnt_lock->unlock();
     58  }
     59 
    4060  CplexEnv::CplexEnv() {
    4161    int status;
     62    _env = CPXopenCPLEX(&status);
     63    if (_env == 0)
     64      throw LicenseError(status);
    4265    _cnt = new int;
    4366    (*_cnt) = 1;
    44     _env = CPXopenCPLEX(&status);
    45     if (_env == 0) {
    46       delete _cnt;
    47       _cnt = 0;
    48       throw LicenseError(status);
    49     }
     67    _cnt_lock = new bits::Lock;
    5068  }
    5169
     
    5371    _env = other._env;
    5472    _cnt = other._cnt;
    55     ++(*_cnt);
     73    _cnt_lock = other._cnt_lock;
     74    incCnt();
    5675  }
    5776
    5877  CplexEnv& CplexEnv::operator=(const CplexEnv& other) {
     78    decCnt();
    5979    _env = other._env;
    6080    _cnt = other._cnt;
    61     ++(*_cnt);
     81    _cnt_lock = other._cnt_lock;
     82    incCnt();
    6283    return *this;
    6384  }
    6485
    6586  CplexEnv::~CplexEnv() {
    66     --(*_cnt);
    67     if (*_cnt == 0) {
    68       delete _cnt;
    69       CPXcloseCPLEX(&_env);
    70     }
     87    decCnt();
    7188  }
    7289
     
    88105    int status;
    89106    _prob = CPXcloneprob(cplexEnv(), cplex._prob, &status);
    90     rows = cplex.rows;
    91     cols = cplex.cols;
     107    _rows = cplex._rows;
     108    _cols = cplex._cols;
    92109    messageLevel(MESSAGE_NOTHING);
    93110  }
     
    116133                         ExprIterator e, Value ub) {
    117134    int i = CPXgetnumrows(cplexEnv(), _prob);
     135
     136    int rmatbeg = 0;
     137   
     138    std::vector<int> indices;
     139    std::vector<Value> values;
     140
     141    for(ExprIterator it=b; it!=e; ++it) {
     142      indices.push_back(it->first);
     143      values.push_back(it->second);
     144    }
     145
    118146    if (lb == -INF) {
    119147      const char s = 'L';
    120       CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
     148      CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &ub, &s,
     149                 &rmatbeg, &indices.front(), &values.front(), 0, 0);
    121150    } else if (ub == INF) {
    122151      const char s = 'G';
    123       CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
     152      CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &lb, &s,
     153                 &rmatbeg, &indices.front(), &values.front(), 0, 0);
    124154    } else if (lb == ub){
    125155      const char s = 'E';
    126       CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
     156      CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &lb, &s,
     157                 &rmatbeg, &indices.front(), &values.front(), 0, 0);
    127158    } else {
    128159      const char s = 'R';
    129160      double len = ub - lb;
    130       CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
    131     }
    132 
    133     std::vector<int> indices;
    134     std::vector<int> rowlist;
    135     std::vector<Value> values;
    136 
    137     for(ExprIterator it=b; it!=e; ++it) {
    138       indices.push_back(it->first);
    139       values.push_back(it->second);
    140       rowlist.push_back(i);
    141     }
    142 
    143     CPXchgcoeflist(cplexEnv(), _prob, values.size(),
    144                    &rowlist.front(), &indices.front(), &values.front());
    145 
     161      CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &ub, &s,
     162                 &rmatbeg, &indices.front(), &values.front(), 0, 0);
     163      CPXchgrngval(cplexEnv(), _prob, 1, &i, &len);
     164    }
     165   
    146166    return i;
    147167  }
     
    156176
    157177  void CplexBase::_eraseColId(int i) {
    158     cols.eraseIndex(i);
    159     cols.shiftIndices(i);
     178    _cols.eraseIndex(i);
     179    _cols.shiftIndices(i);
    160180  }
    161181  void CplexBase::_eraseRowId(int i) {
    162     rows.eraseIndex(i);
    163     rows.shiftIndices(i);
     182    _rows.eraseIndex(i);
     183    _rows.shiftIndices(i);
    164184  }
    165185
  • lemon/cplex.h

    r1270 r1347  
    2424
    2525#include <lemon/lp_base.h>
     26#include <lemon/bits/lock.h>
    2627
    2728struct cpxenv;
     
    4142    cpxenv* _env;
    4243    mutable int* _cnt;
    43 
     44    mutable bits::Lock* _cnt_lock;
     45
     46    void incCnt();
     47    void decCnt();
     48   
    4449  public:
    4550
  • lemon/cycle_canceling.h

    r1270 r1298  
    196196
    197197    // Parameters of the problem
    198     bool _have_lower;
     198    bool _has_lower;
    199199    Value _sum_supply;
    200200
     
    279279    template <typename LowerMap>
    280280    CycleCanceling& lowerMap(const LowerMap& map) {
    281       _have_lower = true;
     281      _has_lower = true;
    282282      for (ArcIt a(_graph); a != INVALID; ++a) {
    283283        _lower[_arc_idf[a]] = map[a];
    284         _lower[_arc_idb[a]] = map[a];
    285284      }
    286285      return *this;
     
    472471        _cost[_reverse[j]] = 0;
    473472      }
    474       _have_lower = false;
     473      _has_lower = false;
    475474      return *this;
    476475    }
     
    685684      const Value MAX = std::numeric_limits<Value>::max();
    686685      int last_out;
    687       if (_have_lower) {
     686      if (_has_lower) {
    688687        for (int i = 0; i != _root; ++i) {
    689688          last_out = _first_out[i+1];
     
    728727        sup[n] = _supply[_node_id[n]];
    729728      }
    730       if (_have_lower) {
     729      if (_has_lower) {
    731730        for (ArcIt a(_graph); a != INVALID; ++a) {
    732731          int j = _arc_idf[a];
     
    785784    }
    786785
    787     // Check if the upper bound is greater or equal to the lower bound
    788     // on each arc.
     786    // Check if the upper bound is greater than or equal to the lower bound
     787    // on each forward arc.
    789788    bool checkBoundMaps() {
    790789      for (int j = 0; j != _res_arc_num; ++j) {
    791         if (_upper[j] < _lower[j]) return false;
     790        if (_forward[j] && _upper[j] < _lower[j]) return false;
    792791      }
    793792      return true;
     
    836835
    837836      // Handle non-zero lower bounds
    838       if (_have_lower) {
     837      if (_has_lower) {
    839838        int limit = _first_out[_root];
    840839        for (int j = 0; j != limit; ++j) {
    841           if (!_forward[j]) _res_cap[j] += _lower[j];
     840          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    842841        }
    843842      }
  • lemon/dim2.h

    r761 r1311  
    2121
    2222#include <iostream>
     23#include <algorithm>
    2324
    2425///\ingroup geomdat
  • lemon/dimacs.h

    r1270 r1375  
    2626#include <lemon/maps.h>
    2727#include <lemon/error.h>
     28
    2829/// \ingroup dimacs_group
    2930/// \file
     
    123124  ///
    124125  /// If the file type was previously evaluated by dimacsType(), then
    125   /// the descriptor struct should be given by the \c dest parameter.
     126  /// the descriptor struct should be given by the \c desc parameter.
    126127  template <typename Digraph, typename LowerMap,
    127128            typename CapacityMap, typename CostMap,
     
    277278  ///
    278279  /// If the file type was previously evaluated by dimacsType(), then
    279   /// the descriptor struct should be given by the \c dest parameter.
     280  /// the descriptor struct should be given by the \c desc parameter.
    280281  template<typename Digraph, typename CapacityMap>
    281282  void readDimacsMax(std::istream& is,
     
    304305  ///
    305306  /// If the file type was previously evaluated by dimacsType(), then
    306   /// the descriptor struct should be given by the \c dest parameter.
     307  /// the descriptor struct should be given by the \c desc parameter.
    307308  template<typename Digraph, typename LengthMap>
    308309  void readDimacsSp(std::istream& is,
     
    335336  ///
    336337  /// If the file type was previously evaluated by dimacsType(), then
    337   /// the descriptor struct should be given by the \c dest parameter.
     338  /// the descriptor struct should be given by the \c desc parameter.
    338339  template<typename Digraph, typename CapacityMap>
    339340  void readDimacsCap(std::istream& is,
     
    344345    typename Digraph::Node u,v;
    345346    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
    346     if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
     347    if(desc.type!=DimacsDescriptor::MAX && desc.type!=DimacsDescriptor::SP)
    347348      throw FormatError("Problem type mismatch");
    348349    _readDimacs(is, g, capacity, u, v, infty, desc);
     
    375376  ///
    376377  /// If the file type was previously evaluated by dimacsType(), then
    377   /// the descriptor struct should be given by the \c dest parameter.
     378  /// the descriptor struct should be given by the \c desc parameter.
    378379  template<typename Graph>
    379380  void readDimacsMat(std::istream& is, Graph &g,
  • lemon/elevator.h

    r628 r1328  
    168168    int onLevel(int l) const
    169169    {
    170       return _first[l+1]-_first[l];
     170      return static_cast<int>(_first[l+1]-_first[l]);
    171171    }
    172172    ///Return true if level \c l is empty.
     
    178178    int aboveLevel(int l) const
    179179    {
    180       return _first[_max_level+1]-_first[l+1];
     180      return static_cast<int>(_first[_max_level+1]-_first[l+1]);
    181181    }
    182182    ///Return the number of active items on level \c l.
    183183    int activesOnLevel(int l) const
    184184    {
    185       return _last_active[l]-_first[l]+1;
     185      return static_cast<int>(_last_active[l]-_first[l]+1);
    186186    }
    187187    ///Return true if there is no active item on level \c l.
  • lemon/glpk.cc

    r1270 r1336  
    3939    glp_copy_prob(lp, other.lp, GLP_ON);
    4040    glp_create_index(lp);
    41     rows = other.rows;
    42     cols = other.cols;
     41    _rows = other._rows;
     42    _cols = other._cols;
    4343    messageLevel(MESSAGE_NOTHING);
    4444  }
     
    109109
    110110  void GlpkBase::_eraseColId(int i) {
    111     cols.eraseIndex(i);
    112     cols.shiftIndices(i);
     111    _cols.eraseIndex(i);
     112    _cols.shiftIndices(i);
    113113  }
    114114
    115115  void GlpkBase::_eraseRowId(int i) {
    116     rows.eraseIndex(i);
    117     rows.shiftIndices(i);
     116    _rows.eraseIndex(i);
     117    _rows.shiftIndices(i);
    118118  }
    119119
  • lemon/glpk.h

    r1270 r1336  
    142142
    143143    ///Returns the constraint identifier understood by GLPK.
    144     int lpxRow(Row r) const { return rows(id(r)); }
     144    int lpxRow(Row r) const { return _rows(id(r)); }
    145145
    146146    ///Returns the variable identifier understood by GLPK.
    147     int lpxCol(Col c) const { return cols(id(c)); }
     147    int lpxCol(Col c) const { return _cols(id(c)); }
    148148
    149149#ifdef DOXYGEN
  • lemon/graph_to_eps.h

    r1270 r1340  
    2626#include<vector>
    2727
    28 #ifndef WIN32
     28#ifndef LEMON_WIN32
    2929#include<sys/time.h>
    3030#include<ctime>
     
    223223  using T::_copyright;
    224224
    225   using T::NodeTextColorType;
    226225  using T::CUST_COL;
    227226  using T::DIST_COL;
     
    676675    {
    677676      os << "%%CreationDate: ";
    678 #ifndef WIN32
     677#ifndef LEMON_WIN32
    679678      timeval tv;
    680679      gettimeofday(&tv, 0);
  • lemon/lgf_reader.h

    r1270 r1377  
    452452  ///
    453453  ///\code
    454   /// DigraphReader<DGR>(digraph, std::cin).
    455   ///   nodeMap("coordinates", coord_map).
    456   ///   arcMap("capacity", cap_map).
    457   ///   node("source", src).
    458   ///   node("target", trg).
    459   ///   attribute("caption", caption).
    460   ///   run();
     454  /// DigraphReader<DGR>(digraph, std::cin)
     455  ///   .nodeMap("coordinates", coord_map)
     456  ///   .arcMap("capacity", cap_map)
     457  ///   .node("source", src)
     458  ///   .node("target", trg)
     459  ///   .attribute("caption", caption)
     460  ///   .run();
    461461  ///\endcode
    462462  ///
     
    12451245  ///\code
    12461246  ///ListDigraph digraph;
    1247   ///ListDigraph::ArcMap<int> cm(digraph);
     1247  ///ListDigraph::ArcMap<int> cap(digraph);
    12481248  ///ListDigraph::Node src, trg;
    1249   ///digraphReader(digraph, std::cin).
    1250   ///  arcMap("capacity", cap).
    1251   ///  node("source", src).
    1252   ///  node("target", trg).
    1253   ///  run();
     1249  ///digraphReader(digraph, std::cin)
     1250  ///  .arcMap("capacity", cap)
     1251  ///  .node("source", src)
     1252  ///  .node("target", trg)
     1253  ///  .run();
    12541254  ///\endcode
    12551255  ///
     
    21242124  ///ListGraph graph;
    21252125  ///ListGraph::EdgeMap<int> weight(graph);
    2126   ///graphReader(graph, std::cin).
    2127   ///  edgeMap("weight", weight).
    2128   ///  run();
     2126  ///graphReader(graph, std::cin)
     2127  ///  .edgeMap("weight", weight)
     2128  ///  .run();
    21292129  ///\endcode
    21302130  ///
     
    31923192  ///ListBpGraph graph;
    31933193  ///ListBpGraph::EdgeMap<int> weight(graph);
    3194   ///bpGraphReader(graph, std::cin).
    3195   ///  edgeMap("weight", weight).
    3196   ///  run();
     3194  ///bpGraphReader(graph, std::cin)
     3195  ///  .edgeMap("weight", weight)
     3196  ///  .run();
    31973197  ///\endcode
    31983198  ///
  • lemon/lgf_writer.h

    r1270 r1377  
    409409  ///
    410410  ///\code
    411   /// DigraphWriter<DGR>(digraph, std::cout).
    412   ///   nodeMap("coordinates", coord_map).
    413   ///   nodeMap("size", size).
    414   ///   nodeMap("title", title).
    415   ///   arcMap("capacity", cap_map).
    416   ///   node("source", src).
    417   ///   node("target", trg).
    418   ///   attribute("caption", caption).
    419   ///   run();
     411  /// DigraphWriter<DGR>(digraph, std::cout)
     412  ///   .nodeMap("coordinates", coord_map)
     413  ///   .nodeMap("size", size)
     414  ///   .nodeMap("title", title)
     415  ///   .arcMap("capacity", cap_map)
     416  ///   .node("source", src)
     417  ///   .node("target", trg)
     418  ///   .attribute("caption", caption)
     419  ///   .run();
    420420  ///\endcode
    421421  ///
     
    962962  ///ListDigraph::Node src, trg;
    963963  ///  // Setting the capacity map and source and target nodes
    964   ///digraphWriter(digraph, std::cout).
    965   ///  arcMap("capacity", cap).
    966   ///  node("source", src).
    967   ///  node("target", trg).
    968   ///  run();
     964  ///digraphWriter(digraph, std::cout)
     965  ///  .arcMap("capacity", cap)
     966  ///  .node("source", src)
     967  ///  .node("target", trg)
     968  ///  .run();
    969969  ///\endcode
    970970  ///
     
    16001600  ///ListGraph::EdgeMap<int> weight(graph);
    16011601  ///  // Setting the weight map
    1602   ///graphWriter(graph, std::cout).
    1603   ///  edgeMap("weight", weight).
    1604   ///  run();
     1602  ///graphWriter(graph, std::cout)
     1603  ///  .edgeMap("weight", weight)
     1604  ///  .run();
    16051605  ///\endcode
    16061606  ///
     
    24202420  ///ListBpGraph::EdgeMap<int> weight(graph);
    24212421  ///  // Setting the weight map
    2422   ///bpGraphWriter(graph, std::cout).
    2423   ///  edgeMap("weight", weight).
    2424   ///  run();
     2422  ///bpGraphWriter(graph, std::cout)
     2423  ///  .edgeMap("weight", weight)
     2424  ///  .run();
    24252425  ///\endcode
    24262426  ///
  • lemon/list_graph.h

    r1270 r1359  
    4949    };
    5050
    51     std::vector<NodeT> nodes;
     51    std::vector<NodeT> _nodes;
    5252
    5353    int first_node;
     
    5555    int first_free_node;
    5656
    57     std::vector<ArcT> arcs;
     57    std::vector<ArcT> _arcs;
    5858
    5959    int first_free_arc;
     
    9898
    9999    ListDigraphBase()
    100       : nodes(), first_node(-1),
    101         first_free_node(-1), arcs(), first_free_arc(-1) {}
    102 
    103 
    104     int maxNodeId() const { return nodes.size()-1; }
    105     int maxArcId() const { return arcs.size()-1; }
    106 
    107     Node source(Arc e) const { return Node(arcs[e.id].source); }
    108     Node target(Arc e) const { return Node(arcs[e.id].target); }
     100      : _nodes(), first_node(-1),
     101        first_free_node(-1), _arcs(), first_free_arc(-1) {}
     102
     103
     104    int maxNodeId() const { return _nodes.size()-1; }
     105    int maxArcId() const { return _arcs.size()-1; }
     106
     107    Node source(Arc e) const { return Node(_arcs[e.id].source); }
     108    Node target(Arc e) const { return Node(_arcs[e.id].target); }
    109109
    110110
     
    114114
    115115    void next(Node& node) const {
    116       node.id = nodes[node.id].next;
     116      node.id = _nodes[node.id].next;
    117117    }
    118118
     
    121121      int n;
    122122      for(n = first_node;
    123           n != -1 && nodes[n].first_out == -1;
    124           n = nodes[n].next) {}
    125       arc.id = (n == -1) ? -1 : nodes[n].first_out;
     123          n != -1 && _nodes[n].first_out == -1;
     124          n = _nodes[n].next) {}
     125      arc.id = (n == -1) ? -1 : _nodes[n].first_out;
    126126    }
    127127
    128128    void next(Arc& arc) const {
    129       if (arcs[arc.id].next_out != -1) {
    130         arc.id = arcs[arc.id].next_out;
     129      if (_arcs[arc.id].next_out != -1) {
     130        arc.id = _arcs[arc.id].next_out;
    131131      } else {
    132132        int n;
    133         for(n = nodes[arcs[arc.id].source].next;
    134             n != -1 && nodes[n].first_out == -1;
    135             n = nodes[n].next) {}
    136         arc.id = (n == -1) ? -1 : nodes[n].first_out;
     133        for(n = _nodes[_arcs[arc.id].source].next;
     134            n != -1 && _nodes[n].first_out == -1;
     135            n = _nodes[n].next) {}
     136        arc.id = (n == -1) ? -1 : _nodes[n].first_out;
    137137      }
    138138    }
    139139
    140140    void firstOut(Arc &e, const Node& v) const {
    141       e.id = nodes[v.id].first_out;
     141      e.id = _nodes[v.id].first_out;
    142142    }
    143143    void nextOut(Arc &e) const {
    144       e.id=arcs[e.id].next_out;
     144      e.id=_arcs[e.id].next_out;
    145145    }
    146146
    147147    void firstIn(Arc &e, const Node& v) const {
    148       e.id = nodes[v.id].first_in;
     148      e.id = _nodes[v.id].first_in;
    149149    }
    150150    void nextIn(Arc &e) const {
    151       e.id=arcs[e.id].next_in;
     151      e.id=_arcs[e.id].next_in;
    152152    }
    153153
     
    160160
    161161    bool valid(Node n) const {
    162       return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
    163         nodes[n.id].prev != -2;
     162      return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
     163        _nodes[n.id].prev != -2;
    164164    }
    165165
    166166    bool valid(Arc a) const {
    167       return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
    168         arcs[a.id].prev_in != -2;
     167      return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
     168        _arcs[a.id].prev_in != -2;
    169169    }
    170170
     
    173173
    174174      if(first_free_node==-1) {
    175         n = nodes.size();
    176         nodes.push_back(NodeT());
     175        n = _nodes.size();
     176        _nodes.push_back(NodeT());
    177177      } else {
    178178        n = first_free_node;
    179         first_free_node = nodes[n].next;
    180       }
    181 
    182       nodes[n].next = first_node;
    183       if(first_node != -1) nodes[first_node].prev = n;
     179        first_free_node = _nodes[n].next;
     180      }
     181
     182      _nodes[n].next = first_node;
     183      if(first_node != -1) _nodes[first_node].prev = n;
    184184      first_node = n;
    185       nodes[n].prev = -1;
    186 
    187       nodes[n].first_in = nodes[n].first_out = -1;
     185      _nodes[n].prev = -1;
     186
     187      _nodes[n].first_in = _nodes[n].first_out = -1;
    188188
    189189      return Node(n);
     
    194194
    195195      if (first_free_arc == -1) {
    196         n = arcs.size();
    197         arcs.push_back(ArcT());
     196        n = _arcs.size();
     197        _arcs.push_back(ArcT());
    198198      } else {
    199199        n = first_free_arc;
    200         first_free_arc = arcs[n].next_in;
    201       }
    202 
    203       arcs[n].source = u.id;
    204       arcs[n].target = v.id;
    205 
    206       arcs[n].next_out = nodes[u.id].first_out;
    207       if(nodes[u.id].first_out != -1) {
    208         arcs[nodes[u.id].first_out].prev_out = n;
    209       }
    210 
    211       arcs[n].next_in = nodes[v.id].first_in;
    212       if(nodes[v.id].first_in != -1) {
    213         arcs[nodes[v.id].first_in].prev_in = n;
    214       }
    215 
    216       arcs[n].prev_in = arcs[n].prev_out = -1;
    217 
    218       nodes[u.id].first_out = nodes[v.id].first_in = n;
     200        first_free_arc = _arcs[n].next_in;
     201      }
     202
     203      _arcs[n].source = u.id;
     204      _arcs[n].target = v.id;
     205
     206      _arcs[n].next_out = _nodes[u.id].first_out;
     207      if(_nodes[u.id].first_out != -1) {
     208        _arcs[_nodes[u.id].first_out].prev_out = n;
     209      }
     210
     211      _arcs[n].next_in = _nodes[v.id].first_in;
     212      if(_nodes[v.id].first_in != -1) {
     213        _arcs[_nodes[v.id].first_in].prev_in = n;
     214      }
     215
     216      _arcs[n].prev_in = _arcs[n].prev_out = -1;
     217
     218      _nodes[u.id].first_out = _nodes[v.id].first_in = n;
    219219
    220220      return Arc(n);
     
    224224      int n = node.id;
    225225
    226       if(nodes[n].next != -1) {
    227         nodes[nodes[n].next].prev = nodes[n].prev;
    228       }
    229 
    230       if(nodes[n].prev != -1) {
    231         nodes[nodes[n].prev].next = nodes[n].next;
    232       } else {
    233         first_node = nodes[n].next;
    234       }
    235 
    236       nodes[n].next = first_free_node;
     226      if(_nodes[n].next != -1) {
     227        _nodes[_nodes[n].next].prev = _nodes[n].prev;
     228      }
     229
     230      if(_nodes[n].prev != -1) {
     231        _nodes[_nodes[n].prev].next = _nodes[n].next;
     232      } else {
     233        first_node = _nodes[n].next;
     234      }
     235
     236      _nodes[n].next = first_free_node;
    237237      first_free_node = n;
    238       nodes[n].prev = -2;
     238      _nodes[n].prev = -2;
    239239
    240240    }
     
    243243      int n = arc.id;
    244244
    245       if(arcs[n].next_in!=-1) {
    246         arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
    247       }
    248 
    249       if(arcs[n].prev_in!=-1) {
    250         arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
    251       } else {
    252         nodes[arcs[n].target].first_in = arcs[n].next_in;
    253       }
    254 
    255 
    256       if(arcs[n].next_out!=-1) {
    257         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
    258       }
    259 
    260       if(arcs[n].prev_out!=-1) {
    261         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
    262       } else {
    263         nodes[arcs[n].source].first_out = arcs[n].next_out;
    264       }
    265 
    266       arcs[n].next_in = first_free_arc;
     245      if(_arcs[n].next_in!=-1) {
     246        _arcs[_arcs[n].next_in].prev_in = _arcs[n].prev_in;
     247      }
     248
     249      if(_arcs[n].prev_in!=-1) {
     250        _arcs[_arcs[n].prev_in].next_in = _arcs[n].next_in;
     251      } else {
     252        _nodes[_arcs[n].target].first_in = _arcs[n].next_in;
     253      }
     254
     255
     256      if(_arcs[n].next_out!=-1) {
     257        _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;
     258      }
     259
     260      if(_arcs[n].prev_out!=-1) {
     261        _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;
     262      } else {
     263        _nodes[_arcs[n].source].first_out = _arcs[n].next_out;
     264      }
     265
     266      _arcs[n].next_in = first_free_arc;
    267267      first_free_arc = n;
    268       arcs[n].prev_in = -2;
     268      _arcs[n].prev_in = -2;
    269269    }
    270270
    271271    void clear() {
    272       arcs.clear();
    273       nodes.clear();
     272      _arcs.clear();
     273      _nodes.clear();
    274274      first_node = first_free_node = first_free_arc = -1;
    275275    }
     
    278278    void changeTarget(Arc e, Node n)
    279279    {
    280       if(arcs[e.id].next_in != -1)
    281         arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
    282       if(arcs[e.id].prev_in != -1)
    283         arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
    284       else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
    285       if (nodes[n.id].first_in != -1) {
    286         arcs[nodes[n.id].first_in].prev_in = e.id;
    287       }
    288       arcs[e.id].target = n.id;
    289       arcs[e.id].prev_in = -1;
    290       arcs[e.id].next_in = nodes[n.id].first_in;
    291       nodes[n.id].first_in = e.id;
     280      if(_arcs[e.id].next_in != -1)
     281        _arcs[_arcs[e.id].next_in].prev_in = _arcs[e.id].prev_in;
     282      if(_arcs[e.id].prev_in != -1)
     283        _arcs[_arcs[e.id].prev_in].next_in = _arcs[e.id].next_in;
     284      else _nodes[_arcs[e.id].target].first_in = _arcs[e.id].next_in;
     285      if (_nodes[n.id].first_in != -1) {
     286        _arcs[_nodes[n.id].first_in].prev_in = e.id;
     287      }
     288      _arcs[e.id].target = n.id;
     289      _arcs[e.id].prev_in = -1;
     290      _arcs[e.id].next_in = _nodes[n.id].first_in;
     291      _nodes[n.id].first_in = e.id;
    292292    }
    293293    void changeSource(Arc e, Node n)
    294294    {
    295       if(arcs[e.id].next_out != -1)
    296         arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
    297       if(arcs[e.id].prev_out != -1)
    298         arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
    299       else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
    300       if (nodes[n.id].first_out != -1) {
    301         arcs[nodes[n.id].first_out].prev_out = e.id;
    302       }
    303       arcs[e.id].source = n.id;
    304       arcs[e.id].prev_out = -1;
    305       arcs[e.id].next_out = nodes[n.id].first_out;
    306       nodes[n.id].first_out = e.id;
     295      if(_arcs[e.id].next_out != -1)
     296        _arcs[_arcs[e.id].next_out].prev_out = _arcs[e.id].prev_out;
     297      if(_arcs[e.id].prev_out != -1)
     298        _arcs[_arcs[e.id].prev_out].next_out = _arcs[e.id].next_out;
     299      else _nodes[_arcs[e.id].source].first_out = _arcs[e.id].next_out;
     300      if (_nodes[n.id].first_out != -1) {
     301        _arcs[_nodes[n.id].first_out].prev_out = e.id;
     302      }
     303      _arcs[e.id].source = n.id;
     304      _arcs[e.id].prev_out = -1;
     305      _arcs[e.id].next_out = _nodes[n.id].first_out;
     306      _nodes[n.id].first_out = e.id;
    307307    }
    308308
     
    487487    Node split(Node n, bool connect = true) {
    488488      Node b = addNode();
    489       nodes[b.id].first_out=nodes[n.id].first_out;
    490       nodes[n.id].first_out=-1;
    491       for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
    492         arcs[i].source=b.id;
     489      _nodes[b.id].first_out=_nodes[n.id].first_out;
     490      _nodes[n.id].first_out=-1;
     491      for(int i=_nodes[b.id].first_out; i!=-1; i=_arcs[i].next_out) {
     492        _arcs[i].source=b.id;
    493493      }
    494494      if (connect) addArc(n,b);
     
    533533    /// to build the digraph.
    534534    /// \sa reserveArc()
    535     void reserveNode(int n) { nodes.reserve(n); };
     535    void reserveNode(int n) { _nodes.reserve(n); };
    536536
    537537    /// Reserve memory for arcs.
     
    543543    /// to build the digraph.
    544544    /// \sa reserveNode()
    545     void reserveArc(int m) { arcs.reserve(m); };
     545    void reserveArc(int m) { _arcs.reserve(m); };
    546546
    547547    /// \brief Class to make a snapshot of the digraph and restore
     
    583583        }
    584584        virtual void add(const std::vector<Node>& nodes) {
    585           for (int i = nodes.size() - 1; i >= 0; ++i) {
     585          for (int i = nodes.size() - 1; i >= 0; --i) {
    586586            snapshot.addNode(nodes[i]);
    587587          }
     
    633633        }
    634634        virtual void add(const std::vector<Arc>& arcs) {
    635           for (int i = arcs.size() - 1; i >= 0; ++i) {
     635          for (int i = arcs.size() - 1; i >= 0; --i) {
    636636            snapshot.addArc(arcs[i]);
    637637          }
     
    804804    };
    805805
    806     std::vector<NodeT> nodes;
     806    std::vector<NodeT> _nodes;
    807807
    808808    int first_node;
     
    810810    int first_free_node;
    811811
    812     std::vector<ArcT> arcs;
     812    std::vector<ArcT> _arcs;
    813813
    814814    int first_free_arc;
     
    868868
    869869    ListGraphBase()
    870       : nodes(), first_node(-1),
    871         first_free_node(-1), arcs(), first_free_arc(-1) {}
    872 
    873 
    874     int maxNodeId() const { return nodes.size()-1; }
    875     int maxEdgeId() const { return arcs.size() / 2 - 1; }
    876     int maxArcId() const { return arcs.size()-1; }
    877 
    878     Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
    879     Node target(Arc e) const { return Node(arcs[e.id].target); }
    880 
    881     Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
    882     Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
     870      : _nodes(), first_node(-1),
     871        first_free_node(-1), _arcs(), first_free_arc(-1) {}
     872
     873
     874    int maxNodeId() const { return _nodes.size()-1; }
     875    int maxEdgeId() const { return _arcs.size() / 2 - 1; }
     876    int maxArcId() const { return _arcs.size()-1; }
     877
     878    Node source(Arc e) const { return Node(_arcs[e.id ^ 1].target); }
     879    Node target(Arc e) const { return Node(_arcs[e.id].target); }
     880
     881    Node u(Edge e) const { return Node(_arcs[2 * e.id].target); }
     882    Node v(Edge e) const { return Node(_arcs[2 * e.id + 1].target); }
    883883
    884884    static bool direction(Arc e) {
     
    895895
    896896    void next(Node& node) const {
    897       node.id = nodes[node.id].next;
     897      node.id = _nodes[node.id].next;
    898898    }
    899899
    900900    void first(Arc& e) const {
    901901      int n = first_node;
    902       while (n != -1 && nodes[n].first_out == -1) {
    903         n = nodes[n].next;
    904       }
    905       e.id = (n == -1) ? -1 : nodes[n].first_out;
     902      while (n != -1 && _nodes[n].first_out == -1) {
     903        n = _nodes[n].next;
     904      }
     905      e.id = (n == -1) ? -1 : _nodes[n].first_out;
    906906    }
    907907
    908908    void next(Arc& e) const {
    909       if (arcs[e.id].next_out != -1) {
    910         e.id = arcs[e.id].next_out;
    911       } else {
    912         int n = nodes[arcs[e.id ^ 1].target].next;
    913         while(n != -1 && nodes[n].first_out == -1) {
    914           n = nodes[n].next;
    915         }
    916         e.id = (n == -1) ? -1 : nodes[n].first_out;
     909      if (_arcs[e.id].next_out != -1) {
     910        e.id = _arcs[e.id].next_out;
     911      } else {
     912        int n = _nodes[_arcs[e.id ^ 1].target].next;
     913        while(n != -1 && _nodes[n].first_out == -1) {
     914          n = _nodes[n].next;
     915        }
     916        e.id = (n == -1) ? -1 : _nodes[n].first_out;
    917917      }
    918918    }
     
    921921      int n = first_node;
    922922      while (n != -1) {
    923         e.id = nodes[n].first_out;
     923        e.id = _nodes[n].first_out;
    924924        while ((e.id & 1) != 1) {
    925           e.id = arcs[e.id].next_out;
     925          e.id = _arcs[e.id].next_out;
    926926        }
    927927        if (e.id != -1) {
     
    929929          return;
    930930        }
    931         n = nodes[n].next;
     931        n = _nodes[n].next;
    932932      }
    933933      e.id = -1;
     
    935935
    936936    void next(Edge& e) const {
    937       int n = arcs[e.id * 2].target;
    938       e.id = arcs[(e.id * 2) | 1].next_out;
     937      int n = _arcs[e.id * 2].target;
     938      e.id = _arcs[(e.id * 2) | 1].next_out;
    939939      while ((e.id & 1) != 1) {
    940         e.id = arcs[e.id].next_out;
     940        e.id = _arcs[e.id].next_out;
    941941      }
    942942      if (e.id != -1) {
     
    944944        return;
    945945      }
    946       n = nodes[n].next;
     946      n = _nodes[n].next;
    947947      while (n != -1) {
    948         e.id = nodes[n].first_out;
     948        e.id = _nodes[n].first_out;
    949949        while ((e.id & 1) != 1) {
    950           e.id = arcs[e.id].next_out;
     950          e.id = _arcs[e.id].next_out;
    951951        }
    952952        if (e.id != -1) {
     
    954954          return;
    955955        }
    956         n = nodes[n].next;
     956        n = _nodes[n].next;
    957957      }
    958958      e.id = -1;
     
    960960
    961961    void firstOut(Arc &e, const Node& v) const {
    962       e.id = nodes[v.id].first_out;
     962      e.id = _nodes[v.id].first_out;
    963963    }
    964964    void nextOut(Arc &e) const {
    965       e.id = arcs[e.id].next_out;
     965      e.id = _arcs[e.id].next_out;
    966966    }
    967967
    968968    void firstIn(Arc &e, const Node& v) const {
    969       e.id = ((nodes[v.id].first_out) ^ 1);
     969      e.id = ((_nodes[v.id].first_out) ^ 1);
    970970      if (e.id == -2) e.id = -1;
    971971    }
    972972    void nextIn(Arc &e) const {
    973       e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
     973      e.id = ((_arcs[e.id ^ 1].next_out) ^ 1);
    974974      if (e.id == -2) e.id = -1;
    975975    }
    976976
    977977    void firstInc(Edge &e, bool& d, const Node& v) const {
    978       int a = nodes[v.id].first_out;
     978      int a = _nodes[v.id].first_out;
    979979      if (a != -1 ) {
    980980        e.id = a / 2;
     
    986986    }
    987987    void nextInc(Edge &e, bool& d) const {
    988       int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
     988      int a = (_arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
    989989      if (a != -1 ) {
    990990        e.id = a / 2;
     
    10051005
    10061006    bool valid(Node n) const {
    1007       return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
    1008         nodes[n.id].prev != -2;
     1007      return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
     1008        _nodes[n.id].prev != -2;
    10091009    }
    10101010
    10111011    bool valid(Arc a) const {
    1012       return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
    1013         arcs[a.id].prev_out != -2;
     1012      return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
     1013        _arcs[a.id].prev_out != -2;
    10141014    }
    10151015
    10161016    bool valid(Edge e) const {
    1017       return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
    1018         arcs[2 * e.id].prev_out != -2;
     1017      return e.id >= 0 && 2 * e.id < static_cast<int>(_arcs.size()) &&
     1018        _arcs[2 * e.id].prev_out != -2;
    10191019    }
    10201020
     
    10231023
    10241024      if(first_free_node==-1) {
    1025         n = nodes.size();
    1026         nodes.push_back(NodeT());
     1025        n = _nodes.size();
     1026        _nodes.push_back(NodeT());
    10271027      } else {
    10281028        n = first_free_node;
    1029         first_free_node = nodes[n].next;
    1030       }
    1031 
    1032       nodes[n].next = first_node;
    1033       if (first_node != -1) nodes[first_node].prev = n;
     1029        first_free_node = _nodes[n].next;
     1030      }
     1031
     1032      _nodes[n].next = first_node;
     1033      if (first_node != -1) _nodes[first_node].prev = n;
    10341034      first_node = n;
    1035       nodes[n].prev = -1;
    1036 
    1037       nodes[n].first_out = -1;
     1035      _nodes[n].prev = -1;
     1036
     1037      _nodes[n].first_out = -1;
    10381038
    10391039      return Node(n);
     
    10441044
    10451045      if (first_free_arc == -1) {
    1046         n = arcs.size();
    1047         arcs.push_back(ArcT());
    1048         arcs.push_back(ArcT());
     1046        n = _arcs.size();
     1047        _arcs.push_back(ArcT());
     1048        _arcs.push_back(ArcT());
    10491049      } else {
    10501050        n = first_free_arc;
    1051         first_free_arc = arcs[n].next_out;
    1052       }
    1053 
    1054       arcs[n].target = u.id;
    1055       arcs[n | 1].target = v.id;
    1056 
    1057       arcs[n].next_out = nodes[v.id].first_out;
    1058       if (nodes[v.id].first_out != -1) {
    1059         arcs[nodes[v.id].first_out].prev_out = n;
    1060       }
    1061       arcs[n].prev_out = -1;
    1062       nodes[v.id].first_out = n;
    1063 
    1064       arcs[n | 1].next_out = nodes[u.id].first_out;
    1065       if (nodes[u.id].first_out != -1) {
    1066         arcs[nodes[u.id].first_out].prev_out = (n | 1);
    1067       }
    1068       arcs[n | 1].prev_out = -1;
    1069       nodes[u.id].first_out = (n | 1);
     1051        first_free_arc = _arcs[n].next_out;
     1052      }
     1053
     1054      _arcs[n].target = u.id;
     1055      _arcs[n | 1].target = v.id;
     1056
     1057      _arcs[n].next_out = _nodes[v.id].first_out;
     1058      if (_nodes[v.id].first_out != -1) {
     1059        _arcs[_nodes[v.id].first_out].prev_out = n;
     1060      }
     1061      _arcs[n].prev_out = -1;
     1062      _nodes[v.id].first_out = n;
     1063
     1064      _arcs[n | 1].next_out = _nodes[u.id].first_out;
     1065      if (_nodes[u.id].first_out != -1) {
     1066        _arcs[_nodes[u.id].first_out].prev_out = (n | 1);
     1067      }
     1068      _arcs[n | 1].prev_out = -1;
     1069      _nodes[u.id].first_out = (n | 1);
    10701070
    10711071      return Edge(n / 2);
     
    10751075      int n = node.id;
    10761076
    1077       if(nodes[n].next != -1) {
    1078         nodes[nodes[n].next].prev = nodes[n].prev;
    1079       }
    1080 
    1081       if(nodes[n].prev != -1) {
    1082         nodes[nodes[n].prev].next = nodes[n].next;
    1083       } else {
    1084         first_node = nodes[n].next;
    1085       }
    1086 
    1087       nodes[n].next = first_free_node;
     1077      if(_nodes[n].next != -1) {
     1078        _nodes[_nodes[n].next].prev = _nodes[n].prev;
     1079      }
     1080
     1081      if(_nodes[n].prev != -1) {
     1082        _nodes[_nodes[n].prev].next = _nodes[n].next;
     1083      } else {
     1084        first_node = _nodes[n].next;
     1085      }
     1086
     1087      _nodes[n].next = first_free_node;
    10881088      first_free_node = n;
    1089       nodes[n].prev = -2;
     1089      _nodes[n].prev = -2;
    10901090    }
    10911091
     
    10931093      int n = edge.id * 2;
    10941094
    1095       if (arcs[n].next_out != -1) {
    1096         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
    1097       }
    1098 
    1099       if (arcs[n].prev_out != -1) {
    1100         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
    1101       } else {
    1102         nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
    1103       }
    1104 
    1105       if (arcs[n | 1].next_out != -1) {
    1106         arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
    1107       }
    1108 
    1109       if (arcs[n | 1].prev_out != -1) {
    1110         arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
    1111       } else {
    1112         nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
    1113       }
    1114 
    1115       arcs[n].next_out = first_free_arc;
     1095      if (_arcs[n].next_out != -1) {
     1096        _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;
     1097      }
     1098
     1099      if (_arcs[n].prev_out != -1) {
     1100        _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;
     1101      } else {
     1102        _nodes[_arcs[n | 1].target].first_out = _arcs[n].next_out;
     1103      }
     1104
     1105      if (_arcs[n | 1].next_out != -1) {
     1106        _arcs[_arcs[n | 1].next_out].prev_out = _arcs[n | 1].prev_out;
     1107      }
     1108
     1109      if (_arcs[n | 1].prev_out != -1) {
     1110        _arcs[_arcs[n | 1].prev_out].next_out = _arcs[n | 1].next_out;
     1111      } else {
     1112        _nodes[_arcs[n].target].first_out = _arcs[n | 1].next_out;
     1113      }
     1114
     1115      _arcs[n].next_out = first_free_arc;
    11161116      first_free_arc = n;
    1117       arcs[n].prev_out = -2;
    1118       arcs[n | 1].prev_out = -2;
     1117      _arcs[n].prev_out = -2;
     1118      _arcs[n | 1].prev_out = -2;
    11191119
    11201120    }
    11211121
    11221122    void clear() {
    1123       arcs.clear();
    1124       nodes.clear();
     1123      _arcs.clear();
     1124      _nodes.clear();
    11251125      first_node = first_free_node = first_free_arc = -1;
    11261126    }
     
    11291129
    11301130    void changeV(Edge e, Node n) {
    1131       if(arcs[2 * e.id].next_out != -1) {
    1132         arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
    1133       }
    1134       if(arcs[2 * e.id].prev_out != -1) {
    1135         arcs[arcs[2 * e.id].prev_out].next_out =
    1136           arcs[2 * e.id].next_out;
    1137       } else {
    1138         nodes[arcs[(2 * e.id) | 1].target].first_out =
    1139           arcs[2 * e.id].next_out;
    1140       }
    1141 
    1142       if (nodes[n.id].first_out != -1) {
    1143         arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
    1144       }
    1145       arcs[(2 * e.id) | 1].target = n.id;
    1146       arcs[2 * e.id].prev_out = -1;
    1147       arcs[2 * e.id].next_out = nodes[n.id].first_out;
    1148       nodes[n.id].first_out = 2 * e.id;
     1131      if(_arcs[2 * e.id].next_out != -1) {
     1132        _arcs[_arcs[2 * e.id].next_out].prev_out = _arcs[2 * e.id].prev_out;
     1133      }
     1134      if(_arcs[2 * e.id].prev_out != -1) {
     1135        _arcs[_arcs[2 * e.id].prev_out].next_out =
     1136          _arcs[2 * e.id].next_out;
     1137      } else {
     1138        _nodes[_arcs[(2 * e.id) | 1].target].first_out =
     1139          _arcs[2 * e.id].next_out;
     1140      }
     1141
     1142      if (_nodes[n.id].first_out != -1) {
     1143        _arcs[_nodes[n.id].first_out].prev_out = 2 * e.id;
     1144      }
     1145      _arcs[(2 * e.id) | 1].target = n.id;
     1146      _arcs[2 * e.id].prev_out = -1;
     1147      _arcs[2 * e.id].next_out = _nodes[n.id].first_out;
     1148      _nodes[n.id].first_out = 2 * e.id;
    11491149    }
    11501150
    11511151    void changeU(Edge e, Node n) {
    1152       if(arcs[(2 * e.id) | 1].next_out != -1) {
    1153         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
    1154           arcs[(2 * e.id) | 1].prev_out;
    1155       }
    1156       if(arcs[(2 * e.id) | 1].prev_out != -1) {
    1157         arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
    1158           arcs[(2 * e.id) | 1].next_out;
    1159       } else {
    1160         nodes[arcs[2 * e.id].target].first_out =
    1161           arcs[(2 * e.id) | 1].next_out;
    1162       }
    1163 
    1164       if (nodes[n.id].first_out != -1) {
    1165         arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
    1166       }
    1167       arcs[2 * e.id].target = n.id;
    1168       arcs[(2 * e.id) | 1].prev_out = -1;
    1169       arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
    1170       nodes[n.id].first_out = ((2 * e.id) | 1);
     1152      if(_arcs[(2 * e.id) | 1].next_out != -1) {
     1153        _arcs[_arcs[(2 * e.id) | 1].next_out].prev_out =
     1154          _arcs[(2 * e.id) | 1].prev_out;
     1155      }
     1156      if(_arcs[(2 * e.id) | 1].prev_out != -1) {
     1157        _arcs[_arcs[(2 * e.id) | 1].prev_out].next_out =
     1158          _arcs[(2 * e.id) | 1].next_out;
     1159      } else {
     1160        _nodes[_arcs[2 * e.id].target].first_out =
     1161          _arcs[(2 * e.id) | 1].next_out;
     1162      }
     1163
     1164      if (_nodes[n.id].first_out != -1) {
     1165        _arcs[_nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
     1166      }
     1167      _arcs[2 * e.id].target = n.id;
     1168      _arcs[(2 * e.id) | 1].prev_out = -1;
     1169      _arcs[(2 * e.id) | 1].next_out = _nodes[n.id].first_out;
     1170      _nodes[n.id].first_out = ((2 * e.id) | 1);
    11711171    }
    11721172
     
    12101210    ListGraph() {}
    12111211
    1212     typedef Parent::OutArcIt IncEdgeIt;
     1212    typedef Parent::IncEdgeIt IncEdgeIt;
    12131213
    12141214    /// \brief Add a new node to the graph.
     
    13451345    /// to build the graph.
    13461346    /// \sa reserveEdge()
    1347     void reserveNode(int n) { nodes.reserve(n); };
     1347    void reserveNode(int n) { _nodes.reserve(n); };
    13481348
    13491349    /// Reserve memory for edges.
     
    13551355    /// to build the graph.
    13561356    /// \sa reserveNode()
    1357     void reserveEdge(int m) { arcs.reserve(2 * m); };
     1357    void reserveEdge(int m) { _arcs.reserve(2 * m); };
    13581358
    13591359    /// \brief Class to make a snapshot of the graph and restore
     
    13951395        }
    13961396        virtual void add(const std::vector<Node>& nodes) {
    1397           for (int i = nodes.size() - 1; i >= 0; ++i) {
     1397          for (int i = nodes.size() - 1; i >= 0; --i) {
    13981398            snapshot.addNode(nodes[i]);
    13991399          }
     
    14451445        }
    14461446        virtual void add(const std::vector<Edge>& edges) {
    1447           for (int i = edges.size() - 1; i >= 0; ++i) {
     1447          for (int i = edges.size() - 1; i >= 0; --i) {
    14481448            snapshot.addEdge(edges[i]);
    14491449          }
     
    16181618    };
    16191619
    1620     std::vector<NodeT> nodes;
     1620    std::vector<NodeT> _nodes;
    16211621
    16221622    int first_node, first_red, first_blue;
     
    16251625    int first_free_red, first_free_blue;
    16261626
    1627     std::vector<ArcT> arcs;
     1627    std::vector<ArcT> _arcs;
    16281628
    16291629    int first_free_arc;
     
    17071707
    17081708    ListBpGraphBase()
    1709       : nodes(), first_node(-1),
     1709      : _nodes(), first_node(-1),
    17101710        first_red(-1), first_blue(-1),
    17111711        max_red(-1), max_blue(-1),
    17121712        first_free_red(-1), first_free_blue(-1),
    1713         arcs(), first_free_arc(-1) {}
    1714 
    1715 
    1716     bool red(Node n) const { return nodes[n.id].red; }
    1717     bool blue(Node n) const { return !nodes[n.id].red; }
     1713        _arcs(), first_free_arc(-1) {}
     1714
     1715
     1716    bool red(Node n) const { return _nodes[n.id].red; }
     1717    bool blue(Node n) const { return !_nodes[n.id].red; }
    17181718
    17191719    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
    17201720    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
    17211721
    1722     int maxNodeId() const { return nodes.size()-1; }
     1722    int maxNodeId() const { return _nodes.size()-1; }
    17231723    int maxRedId() const { return max_red; }
    17241724    int maxBlueId() const { return max_blue; }
    1725     int maxEdgeId() const { return arcs.size() / 2 - 1; }
    1726     int maxArcId() const { return arcs.size()-1; }
    1727 
    1728     Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
    1729     Node target(Arc e) const { return Node(arcs[e.id].target); }
     1725    int maxEdgeId() const { return _arcs.size() / 2 - 1; }
     1726    int maxArcId() const { return _arcs.size()-1; }
     1727
     1728    Node source(Arc e) const { return Node(_arcs[e.id ^ 1].target); }
     1729    Node target(Arc e) const { return Node(_arcs[e.id].target); }
    17301730
    17311731    RedNode redNode(Edge e) const {
    1732       return RedNode(arcs[2 * e.id].target);
     1732      return RedNode(_arcs[2 * e.id].target);
    17331733    }
    17341734    BlueNode blueNode(Edge e) const {
    1735       return BlueNode(arcs[2 * e.id + 1].target);
     1735      return BlueNode(_arcs[2 * e.id + 1].target);
    17361736    }
    17371737
     
    17491749
    17501750    void next(Node& node) const {
    1751       node.id = nodes[node.id].next;
     1751      node.id = _nodes[node.id].next;
    17521752    }
    17531753
     
    17571757
    17581758    void next(RedNode& node) const {
    1759       node.id = nodes[node.id].partition_next;
     1759      node.id = _nodes[node.id].partition_next;
    17601760    }
    17611761
     
    17651765
    17661766    void next(BlueNode& node) const {
    1767       node.id = nodes[node.id].partition_next;
     1767      node.id = _nodes[node.id].partition_next;
    17681768    }
    17691769
    17701770    void first(Arc& e) const {
    17711771      int n = first_node;
    1772       while (n != -1 && nodes[n].first_out == -1) {
    1773         n = nodes[n].next;
    1774       }
    1775       e.id = (n == -1) ? -1 : nodes[n].first_out;
     1772      while (n != -1 && _nodes[n].first_out == -1) {
     1773        n = _nodes[n].next;
     1774      }
     1775      e.id = (n == -1) ? -1 : _nodes[n].first_out;
    17761776    }
    17771777
    17781778    void next(Arc& e) const {
    1779       if (arcs[e.id].next_out != -1) {
    1780         e.id = arcs[e.id].next_out;
    1781       } else {
    1782         int n = nodes[arcs[e.id ^ 1].target].next;
    1783         while(n != -1 && nodes[n].first_out == -1) {
    1784           n = nodes[n].next;
    1785         }
    1786         e.id = (n == -1) ? -1 : nodes[n].first_out;
     1779      if (_arcs[e.id].next_out != -1) {
     1780        e.id = _arcs[e.id].next_out;
     1781      } else {
     1782        int n = _nodes[_arcs[e.id ^ 1].target].next;
     1783        while(n != -1 && _nodes[n].first_out == -1) {
     1784          n = _nodes[n].next;
     1785        }
     1786        e.id = (n == -1) ? -1 : _nodes[n].first_out;
    17871787      }
    17881788    }
     
    17911791      int n = first_node;
    17921792      while (n != -1) {
    1793         e.id = nodes[n].first_out;
     1793        e.id = _nodes[n].first_out;
    17941794        while ((e.id & 1) != 1) {
    1795           e.id = arcs[e.id].next_out;
     1795          e.id = _arcs[e.id].next_out;
    17961796        }
    17971797        if (e.id != -1) {
     
    17991799          return;
    18001800        }
    1801         n = nodes[n].next;
     1801        n = _nodes[n].next;
    18021802      }
    18031803      e.id = -1;
     
    18051805
    18061806    void next(Edge& e) const {
    1807       int n = arcs[e.id * 2].target;
    1808       e.id = arcs[(e.id * 2) | 1].next_out;
     1807      int n = _arcs[e.id * 2].target;
     1808      e.id = _arcs[(e.id * 2) | 1].next_out;
    18091809      while ((e.id & 1) != 1) {
    1810         e.id = arcs[e.id].next_out;
     1810        e.id = _arcs[e.id].next_out;
    18111811      }
    18121812      if (e.id != -1) {
     
    18141814        return;
    18151815      }
    1816       n = nodes[n].next;
     1816      n = _nodes[n].next;
    18171817      while (n != -1) {
    1818         e.id = nodes[n].first_out;
     1818        e.id = _nodes[n].first_out;
    18191819        while ((e.id & 1) != 1) {
    1820           e.id = arcs[e.id].next_out;
     1820          e.id = _arcs[e.id].next_out;
    18211821        }
    18221822        if (e.id != -1) {
     
    18241824          return;
    18251825        }
    1826         n = nodes[n].next;
     1826        n = _nodes[n].next;
    18271827      }
    18281828      e.id = -1;
     
    18301830
    18311831    void firstOut(Arc &e, const Node& v) const {
    1832       e.id = nodes[v.id].first_out;
     1832      e.id = _nodes[v.id].first_out;
    18331833    }
    18341834    void nextOut(Arc &e) const {
    1835       e.id = arcs[e.id].next_out;
     1835      e.id = _arcs[e.id].next_out;
    18361836    }
    18371837
    18381838    void firstIn(Arc &e, const Node& v) const {
    1839       e.id = ((nodes[v.id].first_out) ^ 1);
     1839      e.id = ((_nodes[v.id].first_out) ^ 1);
    18401840      if (e.id == -2) e.id = -1;
    18411841    }
    18421842    void nextIn(Arc &e) const {
    1843       e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
     1843      e.id = ((_arcs[e.id ^ 1].next_out) ^ 1);
    18441844      if (e.id == -2) e.id = -1;
    18451845    }
    18461846
    18471847    void firstInc(Edge &e, bool& d, const Node& v) const {
    1848       int a = nodes[v.id].first_out;
     1848      int a = _nodes[v.id].first_out;
    18491849      if (a != -1 ) {
    18501850        e.id = a / 2;
     
    18561856    }
    18571857    void nextInc(Edge &e, bool& d) const {
    1858       int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
     1858      int a = (_arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
    18591859      if (a != -1 ) {
    18601860        e.id = a / 2;
     
    18671867
    18681868    static int id(Node v) { return v.id; }
    1869     int id(RedNode v) const { return nodes[v.id].partition_index; }
    1870     int id(BlueNode v) const { return nodes[v.id].partition_index; }
     1869    int id(RedNode v) const { return _nodes[v.id].partition_index; }
     1870    int id(BlueNode v) const { return _nodes[v.id].partition_index; }
    18711871    static int id(Arc e) { return e.id; }
    18721872    static int id(Edge e) { return e.id; }
     
    18771877
    18781878    bool valid(Node n) const {
    1879       return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
    1880         nodes[n.id].prev != -2;
     1879      return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
     1880        _nodes[n.id].prev != -2;
    18811881    }
    18821882
    18831883    bool valid(Arc a) const {
    1884       return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
    1885         arcs[a.id].prev_out != -2;
     1884      return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
     1885        _arcs[a.id].prev_out != -2;
    18861886    }
    18871887
    18881888    bool valid(Edge e) const {
    1889       return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
    1890         arcs[2 * e.id].prev_out != -2;
     1889      return e.id >= 0 && 2 * e.id < static_cast<int>(_arcs.size()) &&
     1890        _arcs[2 * e.id].prev_out != -2;
    18911891    }
    18921892
     
    18951895
    18961896      if(first_free_red==-1) {
    1897         n = nodes.size();
    1898         nodes.push_back(NodeT());
    1899         nodes[n].partition_index = ++max_red;
    1900         nodes[n].red = true;
     1897        n = _nodes.size();
     1898        _nodes.push_back(NodeT());
     1899        _nodes[n].partition_index = ++max_red;
     1900        _nodes[n].red = true;
    19011901      } else {
    19021902        n = first_free_red;
    1903         first_free_red = nodes[n].next;
    1904       }
    1905 
    1906       nodes[n].next = first_node;
    1907       if (first_node != -1) nodes[first_node].prev = n;
     1903        first_free_red = _nodes[n].next;
     1904      }
     1905
     1906      _nodes[n].next = first_node;
     1907      if (first_node != -1) _nodes[first_node].prev = n;
    19081908      first_node = n;
    1909       nodes[n].prev = -1;
    1910 
    1911       nodes[n].partition_next = first_red;
    1912       if (first_red != -1) nodes[first_red].partition_prev = n;
     1909      _nodes[n].prev = -1;
     1910
     1911      _nodes[n].partition_next = first_red;
     1912      if (first_red != -1) _nodes[first_red].partition_prev = n;
    19131913      first_red = n;
    1914       nodes[n].partition_prev = -1;
    1915 
    1916       nodes[n].first_out = -1;
     1914      _nodes[n].partition_prev = -1;
     1915
     1916      _nodes[n].first_out = -1;
    19171917
    19181918      return RedNode(n);
     
    19231923
    19241924      if(first_free_blue==-1) {
    1925         n = nodes.size();
    1926         nodes.push_back(NodeT());
    1927         nodes[n].partition_index = ++max_blue;
    1928         nodes[n].red = false;
     1925        n = _nodes.size();
     1926        _nodes.push_back(NodeT());
     1927        _nodes[n].partition_index = ++max_blue;
     1928        _nodes[n].red = false;
    19291929      } else {
    19301930        n = first_free_blue;
    1931         first_free_blue = nodes[n].next;
    1932       }
    1933 
    1934       nodes[n].next = first_node;
    1935       if (first_node != -1) nodes[first_node].prev = n;
     1931        first_free_blue = _nodes[n].next;
     1932      }
     1933
     1934      _nodes[n].next = first_node;
     1935      if (first_node != -1) _nodes[first_node].prev = n;
    19361936      first_node = n;
    1937       nodes[n].prev = -1;
    1938 
    1939       nodes[n].partition_next = first_blue;
    1940       if (first_blue != -1) nodes[first_blue].partition_prev = n;
     1937      _nodes[n].prev = -1;
     1938
     1939      _nodes[n].partition_next = first_blue;
     1940      if (first_blue != -1) _nodes[first_blue].partition_prev = n;
    19411941      first_blue = n;
    1942       nodes[n].partition_prev = -1;
    1943 
    1944       nodes[n].first_out = -1;
     1942      _nodes[n].partition_prev = -1;
     1943
     1944      _nodes[n].first_out = -1;
    19451945
    19461946      return BlueNode(n);
     
    19511951
    19521952      if (first_free_arc == -1) {
    1953         n = arcs.size();
    1954         arcs.push_back(ArcT());
    1955         arcs.push_back(ArcT());
     1953        n = _arcs.size();
     1954        _arcs.push_back(ArcT());
     1955        _arcs.push_back(ArcT());
    19561956      } else {
    19571957        n = first_free_arc;
    1958         first_free_arc = arcs[n].next_out;
    1959       }
    1960 
    1961       arcs[n].target = u.id;
    1962       arcs[n | 1].target = v.id;
    1963 
    1964       arcs[n].next_out = nodes[v.id].first_out;
    1965       if (nodes[v.id].first_out != -1) {
    1966         arcs[nodes[v.id].first_out].prev_out = n;
    1967       }
    1968       arcs[n].prev_out = -1;
    1969       nodes[v.id].first_out = n;
    1970 
    1971       arcs[n | 1].next_out = nodes[u.id].first_out;
    1972       if (nodes[u.id].first_out != -1) {
    1973         arcs[nodes[u.id].first_out].prev_out = (n | 1);
    1974       }
    1975       arcs[n | 1].prev_out = -1;
    1976       nodes[u.id].first_out = (n | 1);
     1958        first_free_arc = _arcs[n].next_out;
     1959      }
     1960
     1961      _arcs[n].target = u.id;
     1962      _arcs[n | 1].target = v.id;
     1963
     1964      _arcs[n].next_out = _nodes[v.id].first_out;
     1965      if (_nodes[v.id].first_out != -1) {
     1966        _arcs[_nodes[v.id].first_out].prev_out = n;
     1967      }
     1968      _arcs[n].prev_out = -1;
     1969      _nodes[v.id].first_out = n;
     1970
     1971      _arcs[n | 1].next_out = _nodes[u.id].first_out;
     1972      if (_nodes[u.id].first_out != -1) {
     1973        _arcs[_nodes[u.id].first_out].prev_out = (n | 1);
     1974      }
     1975      _arcs[n | 1].prev_out = -1;
     1976      _nodes[u.id].first_out = (n | 1);
    19771977
    19781978      return Edge(n / 2);
     
    19821982      int n = node.id;
    19831983
    1984       if(nodes[n].next != -1) {
    1985         nodes[nodes[n].next].prev = nodes[n].prev;
    1986       }
    1987 
    1988       if(nodes[n].prev != -1) {
    1989         nodes[nodes[n].prev].next = nodes[n].next;
    1990       } else {
    1991         first_node = nodes[n].next;
    1992       }
    1993 
    1994       if (nodes[n].partition_next != -1) {
    1995         nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev;
    1996       }
    1997 
    1998       if (nodes[n].partition_prev != -1) {
    1999         nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next;
    2000       } else {
    2001         if (nodes[n].red) {
    2002           first_red = nodes[n].partition_next;
     1984      if(_nodes[n].next != -1) {
     1985        _nodes[_nodes[n].next].prev = _nodes[n].prev;
     1986      }
     1987
     1988      if(_nodes[n].prev != -1) {
     1989        _nodes[_nodes[n].prev].next = _nodes[n].next;
     1990      } else {
     1991        first_node = _nodes[n].next;
     1992      }
     1993
     1994      if (_nodes[n].partition_next != -1) {
     1995        _nodes[_nodes[n].partition_next].partition_prev = _nodes[n].partition_prev;
     1996      }
     1997
     1998      if (_nodes[n].partition_prev != -1) {
     1999        _nodes[_nodes[n].partition_prev].partition_next = _nodes[n].partition_next;
     2000      } else {
     2001        if (_nodes[n].red) {
     2002          first_red = _nodes[n].partition_next;
    20032003        } else {
    2004           first_blue = nodes[n].partition_next;
    2005         }
    2006       }
    2007 
    2008       if (nodes[n].red) {
    2009         nodes[n].next = first_free_red;
     2004          first_blue = _nodes[n].partition_next;
     2005        }
     2006      }
     2007
     2008      if (_nodes[n].red) {
     2009        _nodes[n].next = first_free_red;
    20102010        first_free_red = n;
    20112011      } else {
    2012         nodes[n].next = first_free_blue;
     2012        _nodes[n].next = first_free_blue;
    20132013        first_free_blue = n;
    20142014      }
    2015       nodes[n].prev = -2;
     2015      _nodes[n].prev = -2;
    20162016    }
    20172017
     
    20192019      int n = edge.id * 2;
    20202020
    2021       if (arcs[n].next_out != -1) {
    2022         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
    2023       }
    2024 
    2025       if (arcs[n].prev_out != -1) {
    2026         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
    2027       } else {
    2028         nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
    2029       }
    2030 
    2031       if (arcs[n | 1].next_out != -1) {
    2032         arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
    2033       }
    2034 
    2035       if (arcs[n | 1].prev_out != -1) {
    2036         arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
    2037       } else {
    2038         nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
    2039       }
    2040 
    2041       arcs[n].next_out = first_free_arc;
     2021      if (_arcs[n].next_out != -1) {
     2022        _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;
     2023      }
     2024
     2025      if (_arcs[n].prev_out != -1) {
     2026        _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;
     2027      } else {
     2028        _nodes[_arcs[n | 1].target].first_out = _arcs[n].next_out;
     2029      }
     2030
     2031      if (_arcs[n | 1].next_out != -1) {
     2032        _arcs[_arcs[n | 1].next_out].prev_out = _arcs[n | 1].prev_out;
     2033      }
     2034
     2035      if (_arcs[n | 1].prev_out != -1) {
     2036        _arcs[_arcs[n | 1].prev_out].next_out = _arcs[n | 1].next_out;
     2037      } else {
     2038        _nodes[_arcs[n].target].first_out = _arcs[n | 1].next_out;
     2039      }
     2040
     2041      _arcs[n].next_out = first_free_arc;
    20422042      first_free_arc = n;
    2043       arcs[n].prev_out = -2;
    2044       arcs[n | 1].prev_out = -2;
     2043      _arcs[n].prev_out = -2;
     2044      _arcs[n | 1].prev_out = -2;
    20452045
    20462046    }
    20472047
    20482048    void clear() {
    2049       arcs.clear();
    2050       nodes.clear();
     2049      _arcs.clear();
     2050      _nodes.clear();
    20512051      first_node = first_free_arc = first_red = first_blue =
    20522052        max_red = max_blue = first_free_red = first_free_blue = -1;
     
    20562056
    20572057    void changeRed(Edge e, RedNode n) {
    2058       if(arcs[(2 * e.id) | 1].next_out != -1) {
    2059         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
    2060           arcs[(2 * e.id) | 1].prev_out;
    2061       }
    2062       if(arcs[(2 * e.id) | 1].prev_out != -1) {
    2063         arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
    2064           arcs[(2 * e.id) | 1].next_out;
    2065       } else {
    2066         nodes[arcs[2 * e.id].target].first_out =
    2067           arcs[(2 * e.id) | 1].next_out;
    2068       }
    2069 
    2070       if (nodes[n.id].first_out != -1) {
    2071         arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
    2072       }
    2073       arcs[2 * e.id].target = n.id;
    2074       arcs[(2 * e.id) | 1].prev_out = -1;
    2075       arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
    2076       nodes[n.id].first_out = ((2 * e.id) | 1);
     2058      if(_arcs[(2 * e.id) | 1].next_out != -1) {
     2059        _arcs[_arcs[(2 * e.id) | 1].next_out].prev_out =
     2060          _arcs[(2 * e.id) | 1].prev_out;
     2061      }
     2062      if(_arcs[(2 * e.id) | 1].prev_out != -1) {
     2063        _arcs[_arcs[(2 * e.id) | 1].prev_out].next_out =
     2064          _arcs[(2 * e.id) | 1].next_out;
     2065      } else {
     2066        _nodes[_arcs[2 * e.id].target].first_out =
     2067          _arcs[(2 * e.id) | 1].next_out;
     2068      }
     2069
     2070      if (_nodes[n.id].first_out != -1) {
     2071        _arcs[_nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
     2072      }
     2073      _arcs[2 * e.id].target = n.id;
     2074      _arcs[(2 * e.id) | 1].prev_out = -1;
     2075      _arcs[(2 * e.id) | 1].next_out = _nodes[n.id].first_out;
     2076      _nodes[n.id].first_out = ((2 * e.id) | 1);
    20772077    }
    20782078
    20792079    void changeBlue(Edge e, BlueNode n) {
    2080        if(arcs[2 * e.id].next_out != -1) {
    2081         arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
    2082       }
    2083       if(arcs[2 * e.id].prev_out != -1) {
    2084         arcs[arcs[2 * e.id].prev_out].next_out =
    2085           arcs[2 * e.id].next_out;
    2086       } else {
    2087         nodes[arcs[(2 * e.id) | 1].target].first_out =
    2088           arcs[2 * e.id].next_out;
    2089       }
    2090 
    2091       if (nodes[n.id].first_out != -1) {
    2092         arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
    2093       }
    2094       arcs[(2 * e.id) | 1].target = n.id;
    2095       arcs[2 * e.id].prev_out = -1;
    2096       arcs[2 * e.id].next_out = nodes[n.id].first_out;
    2097       nodes[n.id].first_out = 2 * e.id;
     2080       if(_arcs[2 * e.id].next_out != -1) {
     2081        _arcs[_arcs[2 * e.id].next_out].prev_out = _arcs[2 * e.id].prev_out;
     2082      }
     2083      if(_arcs[2 * e.id].prev_out != -1) {
     2084        _arcs[_arcs[2 * e.id].prev_out].next_out =
     2085          _arcs[2 * e.id].next_out;
     2086      } else {
     2087        _nodes[_arcs[(2 * e.id) | 1].target].first_out =
     2088          _arcs[2 * e.id].next_out;
     2089      }
     2090
     2091      if (_nodes[n.id].first_out != -1) {
     2092        _arcs[_nodes[n.id].first_out].prev_out = 2 * e.id;
     2093      }
     2094      _arcs[(2 * e.id) | 1].target = n.id;
     2095      _arcs[2 * e.id].prev_out = -1;
     2096      _arcs[2 * e.id].next_out = _nodes[n.id].first_out;
     2097      _nodes[n.id].first_out = 2 * e.id;
    20982098    }
    20992099
     
    21372137    ListBpGraph() {}
    21382138
    2139     typedef Parent::OutArcIt IncEdgeIt;
     2139    typedef Parent::IncEdgeIt IncEdgeIt;
    21402140
    21412141    /// \brief Add a new red node to the graph.
     
    22502250    /// to build the graph.
    22512251    /// \sa reserveEdge()
    2252     void reserveNode(int n) { nodes.reserve(n); };
     2252    void reserveNode(int n) { _nodes.reserve(n); };
    22532253
    22542254    /// Reserve memory for edges.
     
    22602260    /// to build the graph.
    22612261    /// \sa reserveNode()
    2262     void reserveEdge(int m) { arcs.reserve(2 * m); };
     2262    void reserveEdge(int m) { _arcs.reserve(2 * m); };
    22632263
    22642264    /// \brief Class to make a snapshot of the graph and restore
     
    23002300        }
    23012301        virtual void add(const std::vector<Node>& nodes) {
    2302           for (int i = nodes.size() - 1; i >= 0; ++i) {
     2302          for (int i = nodes.size() - 1; i >= 0; --i) {
    23032303            snapshot.addNode(nodes[i]);
    23042304          }
     
    23502350        }
    23512351        virtual void add(const std::vector<Edge>& edges) {
    2352           for (int i = edges.size() - 1; i >= 0; ++i) {
     2352          for (int i = edges.size() - 1; i >= 0; --i) {
    23532353            snapshot.addEdge(edges[i]);
    23542354          }
  • lemon/lp.h

    r1270 r1340  
    2323
    2424
    25 #ifdef LEMON_HAVE_GLPK
     25#if LEMON_DEFAULT_LP == LEMON_GLPK_ || LEMON_DEFAULT_MIP == LEMON_GLPK_
    2626#include <lemon/glpk.h>
    27 #elif LEMON_HAVE_CPLEX
     27#endif
     28#if LEMON_DEFAULT_LP == LEMON_CPLEX_ || LEMON_DEFAULT_MIP == LEMON_CPLEX_
    2829#include <lemon/cplex.h>
    29 #elif LEMON_HAVE_SOPLEX
     30#endif
     31#if LEMON_DEFAULT_LP == LEMON_SOPLEX_
    3032#include <lemon/soplex.h>
    31 #elif LEMON_HAVE_CLP
     33#endif
     34#if LEMON_DEFAULT_LP == LEMON_CLP_
    3235#include <lemon/clp.h>
     36#endif
     37#if LEMON_DEFAULT_MIP == LEMON_CBC_
     38#include <lemon/cbc.h>
    3339#endif
    3440
     
    4450  ///\ingroup lp_group
    4551  ///
    46   ///Currently, the possible values are \c GLPK, \c CPLEX,
    47   ///\c SOPLEX or \c CLP
     52  ///Currently, the possible values are \c LEMON_GLPK_, \c LEMON_CPLEX_,
     53  ///\c LEMON_SOPLEX_ or \c LEMON_CLP_
    4854#define LEMON_DEFAULT_LP SOLVER
    4955  ///The default LP solver
     
    6066  ///\ingroup lp_group
    6167  ///
    62   ///Currently, the possible values are \c GLPK, \c CPLEX or \c CBC
     68  ///Currently, the possible values are \c LEMON_GLPK_, \c LEMON_CPLEX_
     69  ///or \c LEMON_CBC_
    6370#define LEMON_DEFAULT_MIP SOLVER
    6471  ///The default MIP solver.
     
    7077  typedef GlpkMip Mip;
    7178#else
    72 #if LEMON_DEFAULT_LP == GLPK
     79#if LEMON_DEFAULT_LP == LEMON_GLPK_
    7380  typedef GlpkLp Lp;
    74 #elif LEMON_DEFAULT_LP == CPLEX
     81#elif LEMON_DEFAULT_LP == LEMON_CPLEX_
    7582  typedef CplexLp Lp;
    76 #elif LEMON_DEFAULT_LP == SOPLEX
     83#elif LEMON_DEFAULT_LP == LEMON_SOPLEX_
    7784  typedef SoplexLp Lp;
    78 #elif LEMON_DEFAULT_LP == CLP
     85#elif LEMON_DEFAULT_LP == LEMON_CLP_
    7986  typedef ClpLp Lp;
    8087#endif
    81 #if LEMON_DEFAULT_MIP == GLPK
    82   typedef GlpkLp Mip;
    83 #elif LEMON_DEFAULT_MIP == CPLEX
     88#if LEMON_DEFAULT_MIP == LEMON_GLPK_
     89  typedef GlpkMip Mip;
     90#elif LEMON_DEFAULT_MIP == LEMON_CPLEX_
    8491  typedef CplexMip Mip;
    85 #elif LEMON_DEFAULT_MIP == CBC
     92#elif LEMON_DEFAULT_MIP == LEMON_CBC_
    8693  typedef CbcMip Mip;
    8794#endif
  • lemon/lp_base.h

    r1270 r1353  
    3232#include<lemon/bits/solver_bits.h>
    3333
     34#include<lemon/bits/stl_iterators.h>
     35
    3436///\file
    3537///\brief The interface of the LP solver interface.
     
    4648  protected:
    4749
    48     _solver_bits::VarIndex rows;
    49     _solver_bits::VarIndex cols;
     50    _solver_bits::VarIndex _rows;
     51    _solver_bits::VarIndex _cols;
    5052
    5153  public:
     
    167169      ColIt(const LpBase &solver) : _solver(&solver)
    168170      {
    169         _solver->cols.firstItem(_id);
     171        _solver->_cols.firstItem(_id);
    170172      }
    171173      /// Invalid constructor \& conversion
     
    180182      ColIt &operator++()
    181183      {
    182         _solver->cols.nextItem(_id);
     184        _solver->_cols.nextItem(_id);
    183185        return *this;
    184186      }
    185187    };
     188
     189    /// \brief Gets the collection of the columns of the LP problem.
     190    ///
     191    /// This function can be used for iterating on
     192    /// the columns of the LP problem. It returns a wrapped ColIt, which looks
     193    /// like an STL container (by having begin() and end())
     194    /// which you can use in range-based for loops, STL algorithms, etc.
     195    /// For example you can write:
     196    ///\code
     197    /// for(auto c: lp.cols())
     198    ///   doSomething(c);
     199    ///\endcode
     200    LemonRangeWrapper1<ColIt, LpBase> cols() {
     201      return LemonRangeWrapper1<ColIt, LpBase>(*this);
     202    }
     203
    186204
    187205    /// \brief Returns the ID of the column.
     
    262280      RowIt(const LpBase &solver) : _solver(&solver)
    263281      {
    264         _solver->rows.firstItem(_id);
     282        _solver->_rows.firstItem(_id);
    265283      }
    266284      /// Invalid constructor \& conversion
     
    275293      RowIt &operator++()
    276294      {
    277         _solver->rows.nextItem(_id);
     295        _solver->_rows.nextItem(_id);
    278296        return *this;
    279297      }
    280298    };
     299   
     300    /// \brief Gets the collection of the rows of the LP problem.
     301    ///
     302    /// This function can be used for iterating on
     303    /// the rows of the LP problem. It returns a wrapped RowIt, which looks
     304    /// like an STL container (by having begin() and end())
     305    /// which you can use in range-based for loops, STL algorithms, etc.
     306    /// For example you can write:
     307    ///\code
     308    /// for(auto c: lp.rows())
     309    ///   doSomething(c);
     310    ///\endcode
     311    LemonRangeWrapper1<RowIt, LpBase> rows() {
     312      return LemonRangeWrapper1<RowIt, LpBase>(*this);
     313    }
     314   
    281315
    282316    /// \brief Returns the ID of the row.
     
    626660    ///This data structure represents a column of the matrix,
    627661    ///thas is it strores a linear expression of the dual variables
    628     ///(\ref Row "Row"s).
     662    ///(\ref LpBase::Row "Row"s).
    629663    ///
    630664    ///There are several ways to access and modify the contents of this
     
    643677    ///(This code computes the sum of all coefficients).
    644678    ///- Numbers (<tt>double</tt>'s)
    645     ///and variables (\ref Row "Row"s) directly convert to an
     679    ///and variables (\ref LpBase::Row "Row"s) directly convert to an
    646680    ///\ref DualExpr and the usual linear operations are defined, so
    647681    ///\code
     
    935969    //Abstract virtual functions
    936970
    937     virtual int _addColId(int col) { return cols.addIndex(col); }
    938     virtual int _addRowId(int row) { return rows.addIndex(row); }
    939 
    940     virtual void _eraseColId(int col) { cols.eraseIndex(col); }
    941     virtual void _eraseRowId(int row) { rows.eraseIndex(row); }
     971    virtual int _addColId(int col) { return _cols.addIndex(col); }
     972    virtual int _addRowId(int row) { return _rows.addIndex(row); }
     973
     974    virtual void _eraseColId(int col) { _cols.eraseIndex(col); }
     975    virtual void _eraseRowId(int row) { _rows.eraseIndex(row); }
    942976
    943977    virtual int _addCol() = 0;
     
    10041038    Value obj_const_comp;
    10051039
    1006     LpBase() : rows(), cols(), obj_const_comp(0) {}
     1040    LpBase() : _rows(), _cols(), obj_const_comp(0) {}
    10071041
    10081042  public:
     
    11161150    void col(Col c, const DualExpr &e) {
    11171151      e.simplify();
    1118       _setColCoeffs(cols(id(c)), ExprIterator(e.comps.begin(), rows),
    1119                     ExprIterator(e.comps.end(), rows));
     1152      _setColCoeffs(_cols(id(c)), ExprIterator(e.comps.begin(), _rows),
     1153                    ExprIterator(e.comps.end(), _rows));
    11201154    }
    11211155
     
    11261160    DualExpr col(Col c) const {
    11271161      DualExpr e;
    1128       _getColCoeffs(cols(id(c)), InsertIterator(e.comps, rows));
     1162      _getColCoeffs(_cols(id(c)), InsertIterator(e.comps, _rows));
    11291163      return e;
    11301164    }
     
    11551189    ///\param t can be
    11561190    ///- a standard STL compatible iterable container with
    1157     ///\ref Row as its \c values_type like
     1191    ///\ref LpBase::Row "Row" as its \c values_type like
    11581192    ///\code
    11591193    ///std::vector<LpBase::Row>
     
    11611195    ///\endcode
    11621196    ///- a standard STL compatible iterable container with
    1163     ///\ref Row as its \c mapped_type like
     1197    ///\ref LpBase::Row "Row" as its \c mapped_type like
    11641198    ///\code
    11651199    ///std::map<AnyType,LpBase::Row>
     
    12131247    void row(Row r, Value l, const Expr &e, Value u) {
    12141248      e.simplify();
    1215       _setRowCoeffs(rows(id(r)), ExprIterator(e.comps.begin(), cols),
    1216                     ExprIterator(e.comps.end(), cols));
    1217       _setRowLowerBound(rows(id(r)),l - *e);
    1218       _setRowUpperBound(rows(id(r)),u - *e);
     1249      _setRowCoeffs(_rows(id(r)), ExprIterator(e.comps.begin(), _cols),
     1250                    ExprIterator(e.comps.end(), _cols));
     1251      _setRowLowerBound(_rows(id(r)),l - *e);
     1252      _setRowUpperBound(_rows(id(r)),u - *e);
    12191253    }
    12201254
     
    12351269    Expr row(Row r) const {
    12361270      Expr e;
    1237       _getRowCoeffs(rows(id(r)), InsertIterator(e.comps, cols));
     1271      _getRowCoeffs(_rows(id(r)), InsertIterator(e.comps, _cols));
    12381272      return e;
    12391273    }
     
    12481282      Row r;
    12491283      e.simplify();
    1250       r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols),
    1251                                 ExprIterator(e.comps.end(), cols), u - *e));
     1284      r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), _cols),
     1285                                ExprIterator(e.comps.end(), _cols), u - *e));
    12521286      return r;
    12531287    }
     
    12611295      c.expr().simplify();
    12621296      r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF,
    1263                                 ExprIterator(c.expr().comps.begin(), cols),
    1264                                 ExprIterator(c.expr().comps.end(), cols),
     1297                                ExprIterator(c.expr().comps.begin(), _cols),
     1298                                ExprIterator(c.expr().comps.end(), _cols),
    12651299                                c.upperBounded()?c.upperBound()-*c.expr():INF));
    12661300      return r;
     
    12701304    ///\param c is the column to be deleted
    12711305    void erase(Col c) {
    1272       _eraseCol(cols(id(c)));
    1273       _eraseColId(cols(id(c)));
     1306      _eraseCol(_cols(id(c)));
     1307      _eraseColId(_cols(id(c)));
    12741308    }
    12751309    ///Erase a row (i.e a constraint) from the LP
     
    12771311    ///\param r is the row to be deleted
    12781312    void erase(Row r) {
    1279       _eraseRow(rows(id(r)));
    1280       _eraseRowId(rows(id(r)));
     1313      _eraseRow(_rows(id(r)));
     1314      _eraseRowId(_rows(id(r)));
    12811315    }
    12821316
     
    12871321    std::string colName(Col c) const {
    12881322      std::string name;
    1289       _getColName(cols(id(c)), name);
     1323      _getColName(_cols(id(c)), name);
    12901324      return name;
    12911325    }
     
    12961330    ///\param name The name to be given
    12971331    void colName(Col c, const std::string& name) {
    1298       _setColName(cols(id(c)), name);
     1332      _setColName(_cols(id(c)), name);
    12991333    }
    13001334
     
    13051339    Col colByName(const std::string& name) const {
    13061340      int k = _colByName(name);
    1307       return k != -1 ? Col(cols[k]) : Col(INVALID);
     1341      return k != -1 ? Col(_cols[k]) : Col(INVALID);
    13081342    }
    13091343
     
    13141348    std::string rowName(Row r) const {
    13151349      std::string name;
    1316       _getRowName(rows(id(r)), name);
     1350      _getRowName(_rows(id(r)), name);
    13171351      return name;
    13181352    }
     
    13231357    ///\param name The name to be given
    13241358    void rowName(Row r, const std::string& name) {
    1325       _setRowName(rows(id(r)), name);
     1359      _setRowName(_rows(id(r)), name);
    13261360    }
    13271361
     
    13321366    Row rowByName(const std::string& name) const {
    13331367      int k = _rowByName(name);
    1334       return k != -1 ? Row(rows[k]) : Row(INVALID);
     1368      return k != -1 ? Row(_rows[k]) : Row(INVALID);
    13351369    }
    13361370
     
    13411375    ///\param val is the new value of the coefficient
    13421376    void coeff(Row r, Col c, Value val) {
    1343       _setCoeff(rows(id(r)),cols(id(c)), val);
     1377      _setCoeff(_rows(id(r)),_cols(id(c)), val);
    13441378    }
    13451379
     
    13501384    ///\return the corresponding coefficient
    13511385    Value coeff(Row r, Col c) const {
    1352       return _getCoeff(rows(id(r)),cols(id(c)));
     1386      return _getCoeff(_rows(id(r)),_cols(id(c)));
    13531387    }
    13541388
     
    13591393    /// Value or -\ref INF.
    13601394    void colLowerBound(Col c, Value value) {
    1361       _setColLowerBound(cols(id(c)),value);
     1395      _setColLowerBound(_cols(id(c)),value);
    13621396    }
    13631397
     
    13681402    ///\return The lower bound for column \c c
    13691403    Value colLowerBound(Col c) const {
    1370       return _getColLowerBound(cols(id(c)));
     1404      return _getColLowerBound(_cols(id(c)));
    13711405    }
    13721406
     
    14141448    /// Value or \ref INF.
    14151449    void colUpperBound(Col c, Value value) {
    1416       _setColUpperBound(cols(id(c)),value);
     1450      _setColUpperBound(_cols(id(c)),value);
    14171451    };
    14181452
     
    14231457    /// \return The upper bound for column \c c
    14241458    Value colUpperBound(Col c) const {
    1425       return _getColUpperBound(cols(id(c)));
     1459      return _getColUpperBound(_cols(id(c)));
    14261460    }
    14271461
     
    14701504    /// Value, -\ref INF or \ref INF.
    14711505    void colBounds(Col c, Value lower, Value upper) {
    1472       _setColLowerBound(cols(id(c)),lower);
    1473       _setColUpperBound(cols(id(c)),upper);
     1506      _setColLowerBound(_cols(id(c)),lower);
     1507      _setColUpperBound(_cols(id(c)),upper);
    14741508    }
    14751509
     
    15161550    /// Value or -\ref INF.
    15171551    void rowLowerBound(Row r, Value value) {
    1518       _setRowLowerBound(rows(id(r)),value);
     1552      _setRowLowerBound(_rows(id(r)),value);
    15191553    }
    15201554
     
    15251559    ///\return The lower bound for row \c r
    15261560    Value rowLowerBound(Row r) const {
    1527       return _getRowLowerBound(rows(id(r)));
     1561      return _getRowLowerBound(_rows(id(r)));
    15281562    }
    15291563
     
    15341568    /// Value or -\ref INF.
    15351569    void rowUpperBound(Row r, Value value) {
    1536       _setRowUpperBound(rows(id(r)),value);
     1570      _setRowUpperBound(_rows(id(r)),value);
    15371571    }
    15381572
     
    15431577    ///\return The upper bound for row \c r
    15441578    Value rowUpperBound(Row r) const {
    1545       return _getRowUpperBound(rows(id(r)));
     1579      return _getRowUpperBound(_rows(id(r)));
    15461580    }
    15471581
    15481582    ///Set an element of the objective function
    1549     void objCoeff(Col c, Value v) {_setObjCoeff(cols(id(c)),v); };
     1583    void objCoeff(Col c, Value v) {_setObjCoeff(_cols(id(c)),v); };
    15501584
    15511585    ///Get an element of the objective function
    1552     Value objCoeff(Col c) const { return _getObjCoeff(cols(id(c))); };
     1586    Value objCoeff(Col c) const { return _getObjCoeff(_cols(id(c))); };
    15531587
    15541588    ///Set the objective function
     
    15571591    ///
    15581592    void obj(const Expr& e) {
    1559       _setObjCoeffs(ExprIterator(e.comps.begin(), cols),
    1560                     ExprIterator(e.comps.end(), cols));
     1593      _setObjCoeffs(ExprIterator(e.comps.begin(), _cols),
     1594                    ExprIterator(e.comps.end(), _cols));
    15611595      obj_const_comp = *e;
    15621596    }
     
    15681602    Expr obj() const {
    15691603      Expr e;
    1570       _getObjCoeffs(InsertIterator(e.comps, cols));
     1604      _getObjCoeffs(InsertIterator(e.comps, _cols));
    15711605      *e = obj_const_comp;
    15721606      return e;
     
    15871621
    15881622    ///Clear the problem
    1589     void clear() { _clear(); rows.clear(); cols.clear(); }
     1623    void clear() { _clear(); _rows.clear(); _cols.clear(); }
    15901624
    15911625    /// Set the message level of the solver
     
    19301964    /// Return the primal value of the column.
    19311965    /// \pre The problem is solved.
    1932     Value primal(Col c) const { return _getPrimal(cols(id(c))); }
     1966    Value primal(Col c) const { return _getPrimal(_cols(id(c))); }
    19331967
    19341968    /// Return the primal value of the expression
     
    19571991    /// \note Some solvers does not provide primal ray calculation
    19581992    /// functions.
    1959     Value primalRay(Col c) const { return _getPrimalRay(cols(id(c))); }
     1993    Value primalRay(Col c) const { return _getPrimalRay(_cols(id(c))); }
    19601994
    19611995    /// Return the dual value of the row
     
    19631997    /// Return the dual value of the row.
    19641998    /// \pre The problem is solved.
    1965     Value dual(Row r) const { return _getDual(rows(id(r))); }
     1999    Value dual(Row r) const { return _getDual(_rows(id(r))); }
    19662000
    19672001    /// Return the dual value of the dual expression
     
    19912025    /// \note Some solvers does not provide dual ray calculation
    19922026    /// functions.
    1993     Value dualRay(Row r) const { return _getDualRay(rows(id(r))); }
     2027    Value dualRay(Row r) const { return _getDualRay(_rows(id(r))); }
    19942028
    19952029    /// Return the basis status of the column
    19962030
    19972031    /// \see VarStatus
    1998     VarStatus colStatus(Col c) const { return _getColStatus(cols(id(c))); }
     2032    VarStatus colStatus(Col c) const { return _getColStatus(_cols(id(c))); }
    19992033
    20002034    /// Return the basis status of the row
    20012035
    20022036    /// \see VarStatus
    2003     VarStatus rowStatus(Row r) const { return _getRowStatus(rows(id(r))); }
     2037    VarStatus rowStatus(Row r) const { return _getRowStatus(_rows(id(r))); }
    20042038
    20052039    ///The value of the objective function
     
    20812115    ///
    20822116    void colType(Col c, ColTypes col_type) {
    2083       _setColType(cols(id(c)),col_type);
     2117      _setColType(_cols(id(c)),col_type);
    20842118    }
    20852119
     
    20892123    ///
    20902124    ColTypes colType(Col c) const {
    2091       return _getColType(cols(id(c)));
     2125      return _getColType(_cols(id(c)));
    20922126    }
    20932127    ///@}
     
    21062140    ///  Return the value of the row in the solution.
    21072141    /// \pre The problem is solved.
    2108     Value sol(Col c) const { return _getSol(cols(id(c))); }
     2142    Value sol(Col c) const { return _getSol(_cols(id(c))); }
    21092143
    21102144    /// Return the value of the expression in the solution
  • lemon/maps.h

    r1270 r1336  
    2626
    2727#include <lemon/core.h>
     28#include <lemon/bits/stl_iterators.h>
    2829
    2930///\file
     
    25822583    };
    25832584
     2585    /// \brief STL style iterator for the keys mapped to \c true.
     2586    ///
     2587    /// This is an STL style wrapper for \ref TrueIt.
     2588    /// It can be used in range-based for loops, STL algorithms, etc.
     2589    LemonRangeWrapper1<TrueIt, IterableBoolMap>
     2590    trueKeys() {
     2591      return LemonRangeWrapper1<TrueIt, IterableBoolMap>(*this);
     2592    }
     2593
     2594
    25842595    /// \brief Iterator for the keys mapped to \c false.
    25852596    ///
     
    26202631      const IterableBoolMap* _map;
    26212632    };
     2633
     2634    /// \brief STL style iterator for the keys mapped to \c false.
     2635    ///
     2636    /// This is an STL style wrapper for \ref FalseIt.
     2637    /// It can be used in range-based for loops, STL algorithms, etc.
     2638    LemonRangeWrapper1<FalseIt, IterableBoolMap>
     2639    falseKeys() {
     2640      return LemonRangeWrapper1<FalseIt, IterableBoolMap>(*this);
     2641    }
     2642
    26222643
    26232644    /// \brief Iterator for the keys mapped to a given value.
     
    26642685      const IterableBoolMap* _map;
    26652686    };
     2687
     2688    /// \brief STL style iterator for the keys mapped to a given value.
     2689    ///
     2690    /// This is an STL style wrapper for \ref ItemIt.
     2691    /// It can be used in range-based for loops, STL algorithms, etc.
     2692    LemonRangeWrapper2<ItemIt, IterableBoolMap, bool>
     2693    items(bool value) {
     2694      return LemonRangeWrapper2<ItemIt, IterableBoolMap, bool>(*this, value);
     2695    }
    26662696
    26672697  protected:
     
    30063036    };
    30073037
     3038    /// \brief STL style iterator for the keys with the same value.
     3039    ///
     3040    /// This is an STL style wrapper for \ref ItemIt.
     3041    /// It can be used in range-based for loops, STL algorithms, etc.
     3042    LemonRangeWrapper2<ItemIt, IterableIntMap, int>
     3043    items(int value) {
     3044      return LemonRangeWrapper2<ItemIt, IterableIntMap, int>(*this, value);
     3045    }
     3046
     3047
    30083048  protected:
    30093049
     
    32493289    };
    32503290
     3291    /// \brief STL style iterator for the keys with the same value.
     3292    ///
     3293    /// This is an STL style wrapper for \ref ItemIt.
     3294    /// It can be used in range-based for loops, STL algorithms, etc.
     3295    LemonRangeWrapper2<ItemIt, IterableValueMap, V>
     3296    items(const V& value) {
     3297      return LemonRangeWrapper2<ItemIt, IterableValueMap, V>(*this, value);
     3298    }
     3299
     3300
    32513301  protected:
    32523302
  • lemon/math.h

    r1270 r1311  
    6868  ///Round a value to its closest integer
    6969  inline double round(double r) {
    70     return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);
     70    return (r > 0.0) ? std::floor(r + 0.5) : std::ceil(r - 0.5);
    7171  }
    7272
  • lemon/nearest_neighbor_tsp.h

    r1270 r1294  
    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              }
  • lemon/network_simplex.h

    r1270 r1318  
    199199
    200200    // Parameters of the problem
    201     bool _have_lower;
     201    bool _has_lower;
    202202    SupplyType _stype;
    203203    Value _sum_supply;
     
    683683    template <typename LowerMap>
    684684    NetworkSimplex& lowerMap(const LowerMap& map) {
    685       _have_lower = true;
     685      _has_lower = true;
    686686      for (ArcIt a(_graph); a != INVALID; ++a) {
    687687        _lower[_arc_id[a]] = map[a];
     
    880880        _cost[i] = 1;
    881881      }
    882       _have_lower = false;
     882      _has_lower = false;
    883883      _stype = GEQ;
    884884      return *this;
     
    937937        _node_id[n] = i;
    938938      }
    939       if (_arc_mixing) {
     939      if (_arc_mixing && _node_num > 1) {
    940940        // Store the arcs in a mixed order
    941941        const int skip = std::max(_arc_num / _node_num, 3);
     
    10731073
    10741074      // Remove non-zero lower bounds
    1075       if (_have_lower) {
     1075      if (_has_lower) {
    10761076        for (int i = 0; i != _arc_num; ++i) {
    10771077          Value c = _lower[i];
     
    12361236    }
    12371237
    1238     // Check if the upper bound is greater or equal to the lower bound
     1238    // Check if the upper bound is greater than or equal to the lower bound
    12391239    // on each arc.
    12401240    bool checkBoundMaps() {
     
    16131613
    16141614      // Transform the solution and the supply map to the original form
    1615       if (_have_lower) {
     1615      if (_has_lower) {
    16161616        for (int i = 0; i != _arc_num; ++i) {
    16171617          Value c = _lower[i];
  • lemon/path.h

    r1270 r1336  
    3131#include <lemon/core.h>
    3232#include <lemon/concepts/path.h>
     33#include <lemon/bits/stl_iterators.h>
    3334
    3435namespace lemon {
     
    140141      int idx;
    141142    };
     143
     144    /// \brief Gets the collection of the arcs of the path.
     145    ///
     146    /// This function can be used for iterating on the
     147    /// arcs of the path. It returns a wrapped
     148    /// ArcIt, which looks like an STL container
     149    /// (by having begin() and end()) which you can use in range-based
     150    /// for loops, STL algorithms, etc.
     151    /// For example you can write:
     152    ///\code
     153    /// for(auto a: p.arcs())
     154    ///   doSomething(a);
     155    ///\endcode
     156    LemonRangeWrapper1<ArcIt, Path> arcs() const {
     157      return LemonRangeWrapper1<ArcIt, Path>(*this);
     158    }
     159
    142160
    143161    /// \brief Length of the path.
     
    346364    };
    347365
     366    /// \brief Gets the collection of the arcs of the path.
     367    ///
     368    /// This function can be used for iterating on the
     369    /// arcs of the path. It returns a wrapped
     370    /// ArcIt, which looks like an STL container
     371    /// (by having begin() and end()) which you can use in range-based
     372    /// for loops, STL algorithms, etc.
     373    /// For example you can write:
     374    ///\code
     375    /// for(auto a: p.arcs())
     376    ///   doSomething(a);
     377    ///\endcode
     378    LemonRangeWrapper1<ArcIt, SimplePath> arcs() const {
     379      return LemonRangeWrapper1<ArcIt, SimplePath>(*this);
     380    }
     381
     382
    348383    /// \brief Length of the path.
    349384    int length() const { return data.size(); }
     
    543578      Node *node;
    544579    };
     580
     581    /// \brief Gets the collection of the arcs of the path.
     582    ///
     583    /// This function can be used for iterating on the
     584    /// arcs of the path. It returns a wrapped
     585    /// ArcIt, which looks like an STL container
     586    /// (by having begin() and end()) which you can use in range-based
     587    /// for loops, STL algorithms, etc.
     588    /// For example you can write:
     589    ///\code
     590    /// for(auto a: p.arcs())
     591    ///   doSomething(a);
     592    ///\endcode
     593    LemonRangeWrapper1<ArcIt, ListPath> arcs() const {
     594      return LemonRangeWrapper1<ArcIt, ListPath>(*this);
     595    }
     596
    545597
    546598    /// \brief The n-th arc.
     
    796848    ///
    797849    /// Default constructor
    798     StaticPath() : len(0), arcs(0) {}
     850    StaticPath() : len(0), _arcs(0) {}
    799851
    800852    /// \brief Copy constructor
    801853    ///
    802     StaticPath(const StaticPath& cpath) : arcs(0) {
     854    StaticPath(const StaticPath& cpath) : _arcs(0) {
    803855      pathCopy(cpath, *this);
    804856    }
     
    808860    /// This path can be initialized from any other path type.
    809861    template <typename CPath>
    810     StaticPath(const CPath& cpath) : arcs(0) {
     862    StaticPath(const CPath& cpath) : _arcs(0) {
    811863      pathCopy(cpath, *this);
    812864    }
     
    816868    /// Destructor of the path
    817869    ~StaticPath() {
    818       if (arcs) delete[] arcs;
     870      if (_arcs) delete[] _arcs;
    819871    }
    820872
     
    883935      int idx;
    884936    };
     937   
     938    /// \brief Gets the collection of the arcs of the path.
     939    ///
     940    /// This function can be used for iterating on the
     941    /// arcs of the path. It returns a wrapped
     942    /// ArcIt, which looks like an STL container
     943    /// (by having begin() and end()) which you can use in range-based
     944    /// for loops, STL algorithms, etc.
     945    /// For example you can write:
     946    ///\code
     947    /// for(auto a: p.arcs())
     948    ///   doSomething(a);
     949    ///\endcode
     950    LemonRangeWrapper1<ArcIt, StaticPath> arcs() const {
     951      return LemonRangeWrapper1<ArcIt, StaticPath>(*this);
     952    }
     953   
    885954
    886955    /// \brief The n-th arc.
     
    888957    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    889958    const Arc& nth(int n) const {
    890       return arcs[n];
     959      return _arcs[n];
    891960    }
    892961
     
    905974    void clear() {
    906975      len = 0;
    907       if (arcs) delete[] arcs;
    908       arcs = 0;
     976      if (_arcs) delete[] _arcs;
     977      _arcs = 0;
    909978    }
    910979
    911980    /// \brief The first arc of the path.
    912981    const Arc& front() const {
    913       return arcs[0];
     982      return _arcs[0];
    914983    }
    915984
    916985    /// \brief The last arc of the path.
    917986    const Arc& back() const {
    918       return arcs[len - 1];
     987      return _arcs[len - 1];
    919988    }
    920989
     
    925994    void build(const CPath& path) {
    926995      len = path.length();
    927       arcs = new Arc[len];
     996      _arcs = new Arc[len];
    928997      int index = 0;
    929998      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
    930         arcs[index] = it;
     999        _arcs[index] = it;
    9311000        ++index;
    9321001      }
     
    9361005    void buildRev(const CPath& path) {
    9371006      len = path.length();
    938       arcs = new Arc[len];
     1007      _arcs = new Arc[len];
    9391008      int index = len;
    9401009      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
    9411010        --index;
    942         arcs[index] = it;
     1011        _arcs[index] = it;
    9431012      }
    9441013    }
     
    9461015  private:
    9471016    int len;
    948     Arc* arcs;
     1017    Arc* _arcs;
    9491018  };
    9501019
     
    11581227  };
    11591228
     1229  /// \brief Gets the collection of the nodes of the path.
     1230  ///
     1231  /// This function can be used for iterating on the
     1232  /// nodes of the path. It returns a wrapped
     1233  /// PathNodeIt, which looks like an STL container
     1234  /// (by having begin() and end()) which you can use in range-based
     1235  /// for loops, STL algorithms, etc.
     1236  /// For example you can write:
     1237  ///\code
     1238  /// for(auto u: pathNodes(g,p))
     1239  ///   doSomething(u);
     1240  ///\endcode
     1241  template<typename Path>
     1242  LemonRangeWrapper2<PathNodeIt<Path>, typename Path::Digraph, Path>
     1243      pathNodes(const typename Path::Digraph &g, const Path &p) {
     1244    return
     1245        LemonRangeWrapper2<PathNodeIt<Path>, typename Path::Digraph, Path>(g,p);
     1246  }
     1247
    11601248  ///@}
    11611249
  • lemon/radix_sort.h

    r1270 r1328  
    329329      Allocator allocator;
    330330
    331       int length = std::distance(first, last);
     331      int length = static_cast<int>(std::distance(first, last));
    332332      Key* buffer = allocator.allocate(2 * length);
    333333      try {
  • lemon/random.h

    r631 r1343  
    6363#define LEMON_RANDOM_H
    6464
     65#include <lemon/config.h>
     66
    6567#include <algorithm>
    6668#include <iterator>
     
    7274#include <lemon/dim2.h>
    7375
    74 #ifndef WIN32
     76#ifndef LEMON_WIN32
    7577#include <sys/time.h>
    7678#include <ctime>
     
    200202        initState(init);
    201203
    202         num = length > end - begin ? length : end - begin;
     204        num = static_cast<int>(length > end - begin ? length : end - begin);
    203205        while (num--) {
    204206          curr[0] = (curr[0] ^ ((curr[1] ^ (curr[1] >> (bits - 2))) * mul1))
     
    214216        }
    215217
    216         num = length - 1; cnt = length - (curr - state) - 1;
     218        num = length - 1; cnt = static_cast<int>(length - (curr - state) - 1);
    217219        while (num--) {
    218220          curr[0] = (curr[0] ^ ((curr[1] ^ (curr[1] >> (bits - 2))) * mul2))
     
    250252        current = state + length;
    251253
    252         register Word *curr = state + length - 1;
    253         register long num;
     254        Word *curr = state + length - 1;
     255        long num;
    254256
    255257        num = length - shift;
     
    606608    /// \return Currently always \c true.
    607609    bool seed() {
    608 #ifndef WIN32
     610#ifndef LEMON_WIN32
    609611      if (seedFromFile("/dev/urandom", 0)) return true;
    610612#endif
     
    626628    /// \param offset The offset, from the file read.
    627629    /// \return \c true when the seeding successes.
    628 #ifndef WIN32
     630#ifndef LEMON_WIN32
    629631    bool seedFromFile(const std::string& file = "/dev/urandom", int offset = 0)
    630632#else
     
    648650    /// \return Currently always \c true.
    649651    bool seedFromTime() {
    650 #ifndef WIN32
     652#ifndef LEMON_WIN32
    651653      timeval tv;
    652654      gettimeofday(&tv, 0);
  • lemon/smart_graph.h

    r1270 r1336  
    4848    };
    4949
    50     std::vector<NodeT> nodes;
    51     std::vector<ArcT> arcs;
     50    std::vector<NodeT> _nodes;
     51    std::vector<ArcT> _arcs;
    5252
    5353  public:
     
    6060  public:
    6161
    62     SmartDigraphBase() : nodes(), arcs() { }
     62    SmartDigraphBase() : _nodes(), _arcs() { }
    6363    SmartDigraphBase(const SmartDigraphBase &_g)
    64       : nodes(_g.nodes), arcs(_g.arcs) { }
     64      : _nodes(_g._nodes), _arcs(_g._arcs) { }
    6565
    6666    typedef True NodeNumTag;
    6767    typedef True ArcNumTag;
    6868
    69     int nodeNum() const { return nodes.size(); }
    70     int arcNum() const { return arcs.size(); }
    71 
    72     int maxNodeId() const { return nodes.size()-1; }
    73     int maxArcId() const { return arcs.size()-1; }
     69    int nodeNum() const { return _nodes.size(); }
     70    int arcNum() const { return _arcs.size(); }
     71
     72    int maxNodeId() const { return _nodes.size()-1; }
     73    int maxArcId() const { return _arcs.size()-1; }
    7474
    7575    Node addNode() {
    76       int n = nodes.size();
    77       nodes.push_back(NodeT());
    78       nodes[n].first_in = -1;
    79       nodes[n].first_out = -1;
     76      int n = _nodes.size();
     77      _nodes.push_back(NodeT());
     78      _nodes[n].first_in = -1;
     79      _nodes[n].first_out = -1;
    8080      return Node(n);
    8181    }
    8282
    8383    Arc addArc(Node u, Node v) {
    84       int n = arcs.size();
    85       arcs.push_back(ArcT());
    86       arcs[n].source = u._id;
    87       arcs[n].target = v._id;
    88       arcs[n].next_out = nodes[u._id].first_out;
    89       arcs[n].next_in = nodes[v._id].first_in;
    90       nodes[u._id].first_out = nodes[v._id].first_in = n;
     84      int n = _arcs.size();
     85      _arcs.push_back(ArcT());
     86      _arcs[n].source = u._id;
     87      _arcs[n].target = v._id;
     88      _arcs[n].next_out = _nodes[u._id].first_out;
     89      _arcs[n].next_in = _nodes[v._id].first_in;
     90      _nodes[u._id].first_out = _nodes[v._id].first_in = n;
    9191
    9292      return Arc(n);
     
    9494
    9595    void clear() {
    96       arcs.clear();
    97       nodes.clear();
    98     }
    99 
    100     Node source(Arc a) const { return Node(arcs[a._id].source); }
    101     Node target(Arc a) const { return Node(arcs[a._id].target); }
     96      _arcs.clear();
     97      _nodes.clear();
     98    }
     99
     100    Node source(Arc a) const { return Node(_arcs[a._id].source); }
     101    Node target(Arc a) const { return Node(_arcs[a._id].target); }
    102102
    103103    static int id(Node v) { return v._id; }
     
    108108
    109109    bool valid(Node n) const {
    110       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
     110      return n._id >= 0 && n._id < static_cast<int>(_nodes.size());
    111111    }
    112112    bool valid(Arc a) const {
    113       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
     113      return a._id >= 0 && a._id < static_cast<int>(_arcs.size());
    114114    }
    115115
     
    146146
    147147    void first(Node& node) const {
    148       node._id = nodes.size() - 1;
     148      node._id = _nodes.size() - 1;
    149149    }
    150150
     
    154154
    155155    void first(Arc& arc) const {
    156       arc._id = arcs.size() - 1;
     156      arc._id = _arcs.size() - 1;
    157157    }
    158158
     
    162162
    163163    void firstOut(Arc& arc, const Node& node) const {
    164       arc._id = nodes[node._id].first_out;
     164      arc._id = _nodes[node._id].first_out;
    165165    }
    166166
    167167    void nextOut(Arc& arc) const {
    168       arc._id = arcs[arc._id].next_out;
     168      arc._id = _arcs[arc._id].next_out;
    169169    }
    170170
    171171    void firstIn(Arc& arc, const Node& node) const {
    172       arc._id = nodes[node._id].first_in;
     172      arc._id = _nodes[node._id].first_in;
    173173    }
    174174
    175175    void nextIn(Arc& arc) const {
    176       arc._id = arcs[arc._id].next_in;
     176      arc._id = _arcs[arc._id].next_in;
    177177    }
    178178
     
    267267    {
    268268      Node b = addNode();
    269       nodes[b._id].first_out=nodes[n._id].first_out;
    270       nodes[n._id].first_out=-1;
    271       for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
    272         arcs[i].source=b._id;
     269      _nodes[b._id].first_out=_nodes[n._id].first_out;
     270      _nodes[n._id].first_out=-1;
     271      for(int i=_nodes[b._id].first_out; i!=-1; i=_arcs[i].next_out) {
     272        _arcs[i].source=b._id;
    273273      }
    274274      if(connect) addArc(n,b);
     
    292292    /// to build the digraph.
    293293    /// \sa reserveArc()
    294     void reserveNode(int n) { nodes.reserve(n); };
     294    void reserveNode(int n) { _nodes.reserve(n); };
    295295
    296296    /// Reserve memory for arcs.
     
    302302    /// to build the digraph.
    303303    /// \sa reserveNode()
    304     void reserveArc(int m) { arcs.reserve(m); };
     304    void reserveArc(int m) { _arcs.reserve(m); };
    305305
    306306  public:
     
    312312    void restoreSnapshot(const Snapshot &s)
    313313    {
    314       while(s.arc_num<arcs.size()) {
    315         Arc arc = arcFromId(arcs.size()-1);
     314      while(s.arc_num<_arcs.size()) {
     315        Arc arc = arcFromId(_arcs.size()-1);
    316316        Parent::notifier(Arc()).erase(arc);
    317         nodes[arcs.back().source].first_out=arcs.back().next_out;
    318         nodes[arcs.back().target].first_in=arcs.back().next_in;
    319         arcs.pop_back();
    320       }
    321       while(s.node_num<nodes.size()) {
    322         Node node = nodeFromId(nodes.size()-1);
     317        _nodes[_arcs.back().source].first_out=_arcs.back().next_out;
     318        _nodes[_arcs.back().target].first_in=_arcs.back().next_in;
     319        _arcs.pop_back();
     320      }
     321      while(s.node_num<_nodes.size()) {
     322        Node node = nodeFromId(_nodes.size()-1);
    323323        Parent::notifier(Node()).erase(node);
    324         nodes.pop_back();
     324        _nodes.pop_back();
    325325      }
    326326    }
     
    363363      ///
    364364      Snapshot(SmartDigraph &gr) : _graph(&gr) {
    365         node_num=_graph->nodes.size();
    366         arc_num=_graph->arcs.size();
     365        node_num=_graph->_nodes.size();
     366        arc_num=_graph->_arcs.size();
    367367      }
    368368
     
    374374      void save(SmartDigraph &gr) {
    375375        _graph=&gr;
    376         node_num=_graph->nodes.size();
    377         arc_num=_graph->arcs.size();
     376        node_num=_graph->_nodes.size();
     377        arc_num=_graph->_arcs.size();
    378378      }
    379379
     
    403403    };
    404404
    405     std::vector<NodeT> nodes;
    406     std::vector<ArcT> arcs;
     405    std::vector<NodeT> _nodes;
     406    std::vector<ArcT> _arcs;
    407407
    408408  public:
     
    466466
    467467    SmartGraphBase()
    468       : nodes(), arcs() {}
     468      : _nodes(), _arcs() {}
    469469
    470470    typedef True NodeNumTag;
     
    472472    typedef True ArcNumTag;
    473473
    474     int nodeNum() const { return nodes.size(); }
    475     int edgeNum() const { return arcs.size() / 2; }
    476     int arcNum() const { return arcs.size(); }
    477 
    478     int maxNodeId() const { return nodes.size()-1; }
    479     int maxEdgeId() const { return arcs.size() / 2 - 1; }
    480     int maxArcId() const { return arcs.size()-1; }
    481 
    482     Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); }
    483     Node target(Arc e) const { return Node(arcs[e._id].target); }
    484 
    485     Node u(Edge e) const { return Node(arcs[2 * e._id].target); }
    486     Node v(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
     474    int nodeNum() const { return _nodes.size(); }
     475    int edgeNum() const { return _arcs.size() / 2; }
     476    int arcNum() const { return _arcs.size(); }
     477
     478    int maxNodeId() const { return _nodes.size()-1; }
     479    int maxEdgeId() const { return _arcs.size() / 2 - 1; }
     480    int maxArcId() const { return _arcs.size()-1; }
     481
     482    Node source(Arc e) const { return Node(_arcs[e._id ^ 1].target); }
     483    Node target(Arc e) const { return Node(_arcs[e._id].target); }
     484
     485    Node u(Edge e) const { return Node(_arcs[2 * e._id].target); }
     486    Node v(Edge e) const { return Node(_arcs[2 * e._id + 1].target); }
    487487
    488488    static bool direction(Arc e) {
     
    495495
    496496    void first(Node& node) const {
    497       node._id = nodes.size() - 1;
     497      node._id = _nodes.size() - 1;
    498498    }
    499499
     
    503503
    504504    void first(Arc& arc) const {
    505       arc._id = arcs.size() - 1;
     505      arc._id = _arcs.size() - 1;
    506506    }
    507507
     
    511511
    512512    void first(Edge& arc) const {
    513       arc._id = arcs.size() / 2 - 1;
     513      arc._id = _arcs.size() / 2 - 1;
    514514    }
    515515
     
    519519
    520520    void firstOut(Arc &arc, const Node& v) const {
    521       arc._id = nodes[v._id].first_out;
     521      arc._id = _nodes[v._id].first_out;
    522522    }
    523523    void nextOut(Arc &arc) const {
    524       arc._id = arcs[arc._id].next_out;
     524      arc._id = _arcs[arc._id].next_out;
    525525    }
    526526
    527527    void firstIn(Arc &arc, const Node& v) const {
    528       arc._id = ((nodes[v._id].first_out) ^ 1);
     528      arc._id = ((_nodes[v._id].first_out) ^ 1);
    529529      if (arc._id == -2) arc._id = -1;
    530530    }
    531531    void nextIn(Arc &arc) const {
    532       arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
     532      arc._id = ((_arcs[arc._id ^ 1].next_out) ^ 1);
    533533      if (arc._id == -2) arc._id = -1;
    534534    }
    535535
    536536    void firstInc(Edge &arc, bool& d, const Node& v) const {
    537       int de = nodes[v._id].first_out;
     537      int de = _nodes[v._id].first_out;
    538538      if (de != -1) {
    539539        arc._id = de / 2;
     
    545545    }
    546546    void nextInc(Edge &arc, bool& d) const {
    547       int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
     547      int de = (_arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
    548548      if (de != -1) {
    549549        arc._id = de / 2;
     
    564564
    565565    bool valid(Node n) const {
    566       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
     566      return n._id >= 0 && n._id < static_cast<int>(_nodes.size());
    567567    }
    568568    bool valid(Arc a) const {
    569       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
     569      return a._id >= 0 && a._id < static_cast<int>(_arcs.size());
    570570    }
    571571    bool valid(Edge e) const {
    572       return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
     572      return e._id >= 0 && 2 * e._id < static_cast<int>(_arcs.size());
    573573    }
    574574
    575575    Node addNode() {
    576       int n = nodes.size();
    577       nodes.push_back(NodeT());
    578       nodes[n].first_out = -1;
     576      int n = _nodes.size();
     577      _nodes.push_back(NodeT());
     578      _nodes[n].first_out = -1;
    579579
    580580      return Node(n);
     
    582582
    583583    Edge addEdge(Node u, Node v) {
    584       int n = arcs.size();
    585       arcs.push_back(ArcT());
    586       arcs.push_back(ArcT());
    587 
    588       arcs[n].target = u._id;
    589       arcs[n | 1].target = v._id;
    590 
    591       arcs[n].next_out = nodes[v._id].first_out;
    592       nodes[v._id].first_out = n;
    593 
    594       arcs[n | 1].next_out = nodes[u._id].first_out;
    595       nodes[u._id].first_out = (n | 1);
     584      int n = _arcs.size();
     585      _arcs.push_back(ArcT());
     586      _arcs.push_back(ArcT());
     587
     588      _arcs[n].target = u._id;
     589      _arcs[n | 1].target = v._id;
     590
     591      _arcs[n].next_out = _nodes[v._id].first_out;
     592      _nodes[v._id].first_out = n;
     593
     594      _arcs[n | 1].next_out = _nodes[u._id].first_out;
     595      _nodes[u._id].first_out = (n | 1);
    596596
    597597      return Edge(n / 2);
     
    599599
    600600    void clear() {
    601       arcs.clear();
    602       nodes.clear();
     601      _arcs.clear();
     602      _nodes.clear();
    603603    }
    604604
     
    702702    /// to build the graph.
    703703    /// \sa reserveEdge()
    704     void reserveNode(int n) { nodes.reserve(n); };
     704    void reserveNode(int n) { _nodes.reserve(n); };
    705705
    706706    /// Reserve memory for edges.
     
    712712    /// to build the graph.
    713713    /// \sa reserveNode()
    714     void reserveEdge(int m) { arcs.reserve(2 * m); };
     714    void reserveEdge(int m) { _arcs.reserve(2 * m); };
    715715
    716716  public:
     
    723723    {
    724724      s._graph = this;
    725       s.node_num = nodes.size();
    726       s.arc_num = arcs.size();
     725      s.node_num = _nodes.size();
     726      s.arc_num = _arcs.size();
    727727    }
    728728
    729729    void restoreSnapshot(const Snapshot &s)
    730730    {
    731       while(s.arc_num<arcs.size()) {
    732         int n=arcs.size()-1;
     731      while(s.arc_num<_arcs.size()) {
     732        int n=_arcs.size()-1;
    733733        Edge arc=edgeFromId(n/2);
    734734        Parent::notifier(Edge()).erase(arc);
     
    737737        dir.push_back(arcFromId(n-1));
    738738        Parent::notifier(Arc()).erase(dir);
    739         nodes[arcs[n-1].target].first_out=arcs[n].next_out;
    740         nodes[arcs[n].target].first_out=arcs[n-1].next_out;
    741         arcs.pop_back();
    742         arcs.pop_back();
    743       }
    744       while(s.node_num<nodes.size()) {
    745         int n=nodes.size()-1;
     739        _nodes[_arcs[n-1].target].first_out=_arcs[n].next_out;
     740        _nodes[_arcs[n].target].first_out=_arcs[n-1].next_out;
     741        _arcs.pop_back();
     742        _arcs.pop_back();
     743      }
     744      while(s.node_num<_nodes.size()) {
     745        int n=_nodes.size()-1;
    746746        Node node = nodeFromId(n);
    747747        Parent::notifier(Node()).erase(node);
    748         nodes.pop_back();
     748        _nodes.pop_back();
    749749      }
    750750    }
     
    826826    };
    827827
    828     std::vector<NodeT> nodes;
    829     std::vector<ArcT> arcs;
     828    std::vector<NodeT> _nodes;
     829    std::vector<ArcT> _arcs;
    830830
    831831    int first_red, first_blue;
     
    916916
    917917    SmartBpGraphBase()
    918       : nodes(), arcs(), first_red(-1), first_blue(-1),
     918      : _nodes(), _arcs(), first_red(-1), first_blue(-1),
    919919        max_red(-1), max_blue(-1) {}
    920920
     
    923923    typedef True ArcNumTag;
    924924
    925     int nodeNum() const { return nodes.size(); }
     925    int nodeNum() const { return _nodes.size(); }
    926926    int redNum() const { return max_red + 1; }
    927927    int blueNum() const { return max_blue + 1; }
    928     int edgeNum() const { return arcs.size() / 2; }
    929     int arcNum() const { return arcs.size(); }
    930 
    931     int maxNodeId() const { return nodes.size()-1; }
     928    int edgeNum() const { return _arcs.size() / 2; }
     929    int arcNum() const { return _arcs.size(); }
     930
     931    int maxNodeId() const { return _nodes.size()-1; }
    932932    int maxRedId() const { return max_red; }
    933933    int maxBlueId() const { return max_blue; }
    934     int maxEdgeId() const { return arcs.size() / 2 - 1; }
    935     int maxArcId() const { return arcs.size()-1; }
    936 
    937     bool red(Node n) const { return nodes[n._id].red; }
    938     bool blue(Node n) const { return !nodes[n._id].red; }
     934    int maxEdgeId() const { return _arcs.size() / 2 - 1; }
     935    int maxArcId() const { return _arcs.size()-1; }
     936
     937    bool red(Node n) const { return _nodes[n._id].red; }
     938    bool blue(Node n) const { return !_nodes[n._id].red; }
    939939
    940940    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
    941941    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
    942942
    943     Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
    944     Node target(Arc a) const { return Node(arcs[a._id].target); }
     943    Node source(Arc a) const { return Node(_arcs[a._id ^ 1].target); }
     944    Node target(Arc a) const { return Node(_arcs[a._id].target); }
    945945
    946946    RedNode redNode(Edge e) const {
    947       return RedNode(arcs[2 * e._id].target);
     947      return RedNode(_arcs[2 * e._id].target);
    948948    }
    949949    BlueNode blueNode(Edge e) const {
    950       return BlueNode(arcs[2 * e._id + 1].target);
     950      return BlueNode(_arcs[2 * e._id + 1].target);
    951951    }
    952952
     
    960960
    961961    void first(Node& node) const {
    962       node._id = nodes.size() - 1;
     962      node._id = _nodes.size() - 1;
    963963    }
    964964
     
    972972
    973973    void next(RedNode& node) const {
    974       node._id = nodes[node._id].partition_next;
     974      node._id = _nodes[node._id].partition_next;
    975975    }
    976976
     
    980980
    981981    void next(BlueNode& node) const {
    982       node._id = nodes[node._id].partition_next;
     982      node._id = _nodes[node._id].partition_next;
    983983    }
    984984
    985985    void first(Arc& arc) const {
    986       arc._id = arcs.size() - 1;
     986      arc._id = _arcs.size() - 1;
    987987    }
    988988
     
    992992
    993993    void first(Edge& arc) const {
    994       arc._id = arcs.size() / 2 - 1;
     994      arc._id = _arcs.size() / 2 - 1;
    995995    }
    996996
     
    10001000
    10011001    void firstOut(Arc &arc, const Node& v) const {
    1002       arc._id = nodes[v._id].first_out;
     1002      arc._id = _nodes[v._id].first_out;
    10031003    }
    10041004    void nextOut(Arc &arc) const {
    1005       arc._id = arcs[arc._id].next_out;
     1005      arc._id = _arcs[arc._id].next_out;
    10061006    }
    10071007
    10081008    void firstIn(Arc &arc, const Node& v) const {
    1009       arc._id = ((nodes[v._id].first_out) ^ 1);
     1009      arc._id = ((_nodes[v._id].first_out) ^ 1);
    10101010      if (arc._id == -2) arc._id = -1;
    10111011    }
    10121012    void nextIn(Arc &arc) const {
    1013       arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
     1013      arc._id = ((_arcs[arc._id ^ 1].next_out) ^ 1);
    10141014      if (arc._id == -2) arc._id = -1;
    10151015    }
    10161016
    10171017    void firstInc(Edge &arc, bool& d, const Node& v) const {
    1018       int de = nodes[v._id].first_out;
     1018      int de = _nodes[v._id].first_out;
    10191019      if (de != -1) {
    10201020        arc._id = de / 2;
     
    10261026    }
    10271027    void nextInc(Edge &arc, bool& d) const {
    1028       int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
     1028      int de = (_arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
    10291029      if (de != -1) {
    10301030        arc._id = de / 2;
     
    10371037
    10381038    static int id(Node v) { return v._id; }
    1039     int id(RedNode v) const { return nodes[v._id].partition_index; }
    1040     int id(BlueNode v) const { return nodes[v._id].partition_index; }
     1039    int id(RedNode v) const { return _nodes[v._id].partition_index; }
     1040    int id(BlueNode v) const { return _nodes[v._id].partition_index; }
    10411041    static int id(Arc e) { return e._id; }
    10421042    static int id(Edge e) { return e._id; }
     
    10471047
    10481048    bool valid(Node n) const {
    1049       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
     1049      return n._id >= 0 && n._id < static_cast<int>(_nodes.size());
    10501050    }
    10511051    bool valid(Arc a) const {
    1052       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
     1052      return a._id >= 0 && a._id < static_cast<int>(_arcs.size());
    10531053    }
    10541054    bool valid(Edge e) const {
    1055       return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
     1055      return e._id >= 0 && 2 * e._id < static_cast<int>(_arcs.size());
    10561056    }
    10571057
    10581058    RedNode addRedNode() {
    1059       int n = nodes.size();
    1060       nodes.push_back(NodeT());
    1061       nodes[n].first_out = -1;
    1062       nodes[n].red = true;
    1063       nodes[n].partition_index = ++max_red;
    1064       nodes[n].partition_next = first_red;
     1059      int n = _nodes.size();
     1060      _nodes.push_back(NodeT());
     1061      _nodes[n].first_out = -1;
     1062      _nodes[n].red = true;
     1063      _nodes[n].partition_index = ++max_red;
     1064      _nodes[n].partition_next = first_red;
    10651065      first_red = n;
    10661066
     
    10691069
    10701070    BlueNode addBlueNode() {
    1071       int n = nodes.size();
    1072       nodes.push_back(NodeT());
    1073       nodes[n].first_out = -1;
    1074       nodes[n].red = false;
    1075       nodes[n].partition_index = ++max_blue;
    1076       nodes[n].partition_next = first_blue;
     1071      int n = _nodes.size();
     1072      _nodes.push_back(NodeT());
     1073      _nodes[n].first_out = -1;
     1074      _nodes[n].red = false;
     1075      _nodes[n].partition_index = ++max_blue;
     1076      _nodes[n].partition_next = first_blue;
    10771077      first_blue = n;
    10781078
     
    10811081
    10821082    Edge addEdge(RedNode u, BlueNode v) {
    1083       int n = arcs.size();
    1084       arcs.push_back(ArcT());
    1085       arcs.push_back(ArcT());
    1086 
    1087       arcs[n].target = u._id;
    1088       arcs[n | 1].target = v._id;
    1089 
    1090       arcs[n].next_out = nodes[v._id].first_out;
    1091       nodes[v._id].first_out = n;
    1092 
    1093       arcs[n | 1].next_out = nodes[u._id].first_out;
    1094       nodes[u._id].first_out = (n | 1);
     1083      int n = _arcs.size();
     1084      _arcs.push_back(ArcT());
     1085      _arcs.push_back(ArcT());
     1086
     1087      _arcs[n].target = u._id;
     1088      _arcs[n | 1].target = v._id;
     1089
     1090      _arcs[n].next_out = _nodes[v._id].first_out;
     1091      _nodes[v._id].first_out = n;
     1092
     1093      _arcs[n | 1].next_out = _nodes[u._id].first_out;
     1094      _nodes[u._id].first_out = (n | 1);
    10951095
    10961096      return Edge(n / 2);
     
    10981098
    10991099    void clear() {
    1100       arcs.clear();
    1101       nodes.clear();
     1100      _arcs.clear();
     1101      _nodes.clear();
    11021102      first_red = -1;
    11031103      first_blue = -1;
     
    12141214    /// to build the graph.
    12151215    /// \sa reserveEdge()
    1216     void reserveNode(int n) { nodes.reserve(n); };
     1216    void reserveNode(int n) { _nodes.reserve(n); };
    12171217
    12181218    /// Reserve memory for edges.
     
    12241224    /// to build the graph.
    12251225    /// \sa reserveNode()
    1226     void reserveEdge(int m) { arcs.reserve(2 * m); };
     1226    void reserveEdge(int m) { _arcs.reserve(2 * m); };
    12271227
    12281228  public:
     
    12351235    {
    12361236      s._graph = this;
    1237       s.node_num = nodes.size();
    1238       s.arc_num = arcs.size();
     1237      s.node_num = _nodes.size();
     1238      s.arc_num = _arcs.size();
    12391239    }
    12401240
    12411241    void restoreSnapshot(const Snapshot &s)
    12421242    {
    1243       while(s.arc_num<arcs.size()) {
    1244         int n=arcs.size()-1;
     1243      while(s.arc_num<_arcs.size()) {
     1244        int n=_arcs.size()-1;
    12451245        Edge arc=edgeFromId(n/2);
    12461246        Parent::notifier(Edge()).erase(arc);
     
    12491249        dir.push_back(arcFromId(n-1));
    12501250        Parent::notifier(Arc()).erase(dir);
    1251