COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [1149:3ec484b11733:1148:2126945deb6a] in lemon-main


Ignore:
Files:
3 deleted
33 edited

Legend:

Unmodified
Added
Removed

  • CMakeLists.txt

    r1138 r1137  
    44  CMAKE_POLICY(SET CMP0048 OLD)
    55ENDIF(POLICY CMP0048)
    6 
    7 IF(POLICY CMP0043)
    8   CMAKE_POLICY(SET CMP0043 OLD)
    9 ENDIF(POLICY CMP0043)
    106
    117IF(POLICY CMP0026)
    … …  
    239235    FORCE )
    240236
    241 SET_DIRECTORY_PROPERTIES(PROPERTIES
    242   COMPILE_DEFINITIONS_DEBUG "LEMON_ENABLE_DEBUG"
    243   COMPILE_DEFINITIONS_MAINTAINER "LEMON_ENABLE_DEBUG"
    244 )
    245237
    246238INCLUDE(CheckTypeSize)
    … …  
    271263
    272264ENABLE_TESTING()
    273 
    274 
    275 INCLUDE(CheckCXXCompilerFlag)
    276 CHECK_CXX_COMPILER_FLAG("-std=c++11" LEMON_CXX11)
    277 IF(LEMON_CXX11)
    278   SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
    279 ENDIF()
    280 
    281265
    282266IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")

  • doc/Doxyfile.in

    r1145 r1075  
    2020STRIP_FROM_PATH        = "@abs_top_srcdir@"
    2121STRIP_FROM_INC_PATH    = "@abs_top_srcdir@"
    22 SHORT_NAMES            = NO
     22SHORT_NAMES            = YES
    2323JAVADOC_AUTOBRIEF      = NO
    2424QT_AUTOBRIEF           = NO
    … …  
    4040SUBGROUPING            = YES
    4141TYPEDEF_HIDES_STRUCT   = NO
     42SYMBOL_CACHE_SIZE      = 0
    4243#---------------------------------------------------------------------------
    4344# Build related configuration options
    … …  
    7273MAX_INITIALIZER_LINES  = 5
    7374SHOW_USED_FILES        = NO
     75SHOW_DIRECTORIES       = YES
    7476SHOW_FILES             = YES
    7577SHOW_NAMESPACES        = YES
    … …  
    149151HTML_COLORSTYLE_GAMMA  = 80
    150152HTML_TIMESTAMP         = YES
     153HTML_ALIGN_MEMBERS     = YES
    151154HTML_DYNAMIC_SECTIONS  = YES
    152155GENERATE_DOCSET        = NO
    … …  
    175178ENUM_VALUES_PER_LINE   = 4
    176179GENERATE_TREEVIEW      = NO
     180USE_INLINE_TREES       = NO
    177181TREEVIEW_WIDTH         = 250
    178182EXT_LINKS_IN_WINDOW    = NO
    … …  
    221225GENERATE_XML           = NO
    222226XML_OUTPUT             = xml
     227XML_SCHEMA             =
     228XML_DTD                =
    223229XML_PROGRAMLISTING     = YES
    224230#---------------------------------------------------------------------------
    … …  
    261267HAVE_DOT               = YES
    262268DOT_NUM_THREADS        = 0
    263 DOT_FONTNAME           =
     269DOT_FONTNAME           = FreeSans
    264270DOT_FONTSIZE           = 10
    265271DOT_FONTPATH           =

  • doc/groups.dox

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

  • doc/named-param.dox

    r1142 r440  
    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++ lacks this amenity.
     28with natural default values. Sadly, C++ lack this amenity.
    2929
    3030However, with a crafty trick and with some little

  • doc/references.bib

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

  • lemon/bellman_ford.h

    r1131 r1092  
    3030#include <lemon/maps.h>
    3131#include <lemon/path.h>
    32 #include <lemon/bits/stl_iterators.h>
    3332
    3433#include <limits>
    … …  
    691690      int _index;
    692691    };
    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 
    708692
    709693    /// \name Query Functions

  • lemon/bits/edge_set_extender.h

    r1131 r1092  
    114114    };
    115115
    116     LemonRangeWrapper1<NodeIt, Digraph> nodes() const {
    117       return LemonRangeWrapper1<NodeIt, Digraph>(*this);
    118     }
    119116
    120117    class ArcIt : public Arc {
    … …  
    140137    };
    141138
    142     LemonRangeWrapper1<ArcIt, Digraph> arcs() const {
    143       return LemonRangeWrapper1<ArcIt, Digraph>(*this);
    144     }
    145139
    146140    class OutArcIt : public Arc {
    … …  
    167161    };
    168162
    169     LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {
    170       return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);
    171     }
    172163
    173164    class InArcIt : public Arc {
    … …  
    193184
    194185    };
    195 
    196     LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {
    197       return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);
    198     }
    199186
    200187    // \brief Base node of the iterator
    … …  
    386373    };
    387374
    388     LemonRangeWrapper1<NodeIt, Graph> nodes() const {
    389       return LemonRangeWrapper1<NodeIt, Graph>(*this);
    390     }
    391375
    392376    class ArcIt : public Arc {
    … …  
    412396    };
    413397
    414     LemonRangeWrapper1<ArcIt, Graph> arcs() const {
    415       return LemonRangeWrapper1<ArcIt, Graph>(*this);
    416     }
    417398
    418399    class OutArcIt : public Arc {
    … …  
    439420    };
    440421
    441     LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {
    442       return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);
    443     }
    444422
    445423    class InArcIt : public Arc {
    … …  
    466444    };
    467445
    468     LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {
    469       return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);
    470     }
    471446
    472447    class EdgeIt : public Parent::Edge {
    … …  
    491466
    492467    };
    493 
    494     LemonRangeWrapper1<EdgeIt, Graph> edges() const {
    495       return LemonRangeWrapper1<EdgeIt, Graph>(*this);
    496     }
    497468
    498469    class IncEdgeIt : public Parent::Edge {
    … …  
    520491      }
    521492    };
    522 
    523     LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {
    524       return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);
    525     }
    526493
    527494    // \brief Base node of the iterator

  • lemon/bits/graph_adaptor_extender.h

    r1131 r1092  
    8686    };
    8787
    88     LemonRangeWrapper1<NodeIt, Adaptor> nodes() const {
    89       return LemonRangeWrapper1<NodeIt, Adaptor>(*this);
    90     }
    9188
    9289    class ArcIt : public Arc {
    … …  
    111108
    112109    };
    113 
    114     LemonRangeWrapper1<ArcIt, Adaptor> arcs() const {
    115       return LemonRangeWrapper1<ArcIt, Adaptor>(*this);
    116     }
    117110
    118111
    … …  
    140133    };
    141134
    142     LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {
    143       return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);
    144     }
    145 
    146135
    147136    class InArcIt : public Arc {
    … …  
    167156
    168157    };
    169 
    170     LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {
    171       return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);
    172     }
    173158
    174159    Node baseNode(const OutArcIt &e) const {
    … …  
    270255    };
    271256
    272     LemonRangeWrapper1<NodeIt, Adaptor> nodes() const {
    273       return LemonRangeWrapper1<NodeIt, Adaptor>(*this);
    274     }
    275 
    276257
    277258    class ArcIt : public Arc {
    … …  
    296277
    297278    };
    298 
    299     LemonRangeWrapper1<ArcIt, Adaptor> arcs() const {
    300       return LemonRangeWrapper1<ArcIt, Adaptor>(*this);
    301     }
    302279
    303280
    … …  
    325302    };
    326303
    327     LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {
    328       return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);
    329     }
    330 
    331304
    332305    class InArcIt : public Arc {
    … …  
    353326    };
    354327
    355     LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {
    356       return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);
    357     }
    358 
    359328    class EdgeIt : public Parent::Edge {
    360329      const Adaptor* _adaptor;
    … …  
    378347
    379348    };
    380 
    381     LemonRangeWrapper1<EdgeIt, Adaptor> edges() const {
    382       return LemonRangeWrapper1<EdgeIt, Adaptor>(*this);
    383     }
    384 
    385349
    386350    class IncEdgeIt : public Edge {
    … …  
    409373    };
    410374
    411     LemonRangeWrapper2<IncEdgeIt, Adaptor, Node> incEdges(const Node& u) const {
    412       return LemonRangeWrapper2<IncEdgeIt, Adaptor, Node>(*this, u);
    413     }
    414 
    415 
    416375    Node baseNode(const OutArcIt &a) const {
    417376      return Parent::source(a);

  • lemon/bits/graph_extender.h

    r1130 r1092  
    2828#include <lemon/concepts/maps.h>
    2929
    30 #include <lemon/bits/stl_iterators.h>
    31 
    3230//\ingroup graphbits
    3331//\file
    … …  
    119117    };
    120118
    121     LemonRangeWrapper1<NodeIt, Digraph> nodes() const {
    122       return LemonRangeWrapper1<NodeIt, Digraph>(*this);
    123     }
    124 
    125119
    126120    class ArcIt : public Arc {
    … …  
    145139
    146140    };
    147 
    148     LemonRangeWrapper1<ArcIt, Digraph> arcs() const {
    149       return LemonRangeWrapper1<ArcIt, Digraph>(*this);
    150     }
    151141
    152142
    … …  
    174164    };
    175165
    176     LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {
    177       return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);
    178     }
    179 
    180166
    181167    class InArcIt : public Arc {
    … …  
    201187
    202188    };
    203 
    204     LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {
    205       return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);
    206     }
    207189
    208190    // \brief Base node of the iterator
    … …  
    455437    };
    456438
    457     LemonRangeWrapper1<NodeIt, Graph> nodes() const {
    458       return LemonRangeWrapper1<NodeIt, Graph>(*this);
    459     }
    460 
    461439
    462440    class ArcIt : public Arc {
    … …  
    481459
    482460    };
    483 
    484     LemonRangeWrapper1<ArcIt, Graph> arcs() const {
    485       return LemonRangeWrapper1<ArcIt, Graph>(*this);
    486     }
    487461
    488462
    … …  
    510484    };
    511485
    512     LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {
    513       return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);
    514     }
    515 
    516486
    517487    class InArcIt : public Arc {
    … …  
    538508    };
    539509
    540     LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {
    541       return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);
    542     }
    543 
    544510
    545511    class EdgeIt : public Parent::Edge {
    … …  
    564530
    565531    };
    566 
    567     LemonRangeWrapper1<EdgeIt, Graph> edges() const {
    568       return LemonRangeWrapper1<EdgeIt, Graph>(*this);
    569     }
    570 
    571532
    572533    class IncEdgeIt : public Parent::Edge {
    … …  
    594555      }
    595556    };
    596 
    597     LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {
    598       return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);
    599     }
    600 
    601557
    602558    // \brief Base node of the iterator
    … …  
    948904    };
    949905
    950     LemonRangeWrapper1<NodeIt, BpGraph> nodes() const {
    951       return LemonRangeWrapper1<NodeIt, BpGraph>(*this);
    952     }
    953 
    954 
    955906    class RedNodeIt : public RedNode {
    956907      const BpGraph* _graph;
    … …  
    975926    };
    976927
    977     LemonRangeWrapper1<RedNodeIt, BpGraph> redNodes() const {
    978       return LemonRangeWrapper1<RedNodeIt, BpGraph>(*this);
    979     }
    980 
    981 
    982928    class BlueNodeIt : public BlueNode {
    983929      const BpGraph* _graph;
    … …  
    1002948    };
    1003949
    1004     LemonRangeWrapper1<BlueNodeIt, BpGraph> blueNodes() const {
    1005       return LemonRangeWrapper1<BlueNodeIt, BpGraph>(*this);
    1006     }
    1007 
    1008 
    1009950
    1010951    class ArcIt : public Arc {
    … …  
    1029970
    1030971    };
    1031 
    1032     LemonRangeWrapper1<ArcIt, BpGraph> arcs() const {
    1033       return LemonRangeWrapper1<ArcIt, BpGraph>(*this);
    1034     }
    1035972
    1036973
    … …  
    1058995    };
    1059996
    1060     LemonRangeWrapper2<OutArcIt, BpGraph, Node> outArcs(const Node& u) const {
    1061       return LemonRangeWrapper2<OutArcIt, BpGraph, Node>(*this, u);
    1062     }
    1063 
    1064997
    1065998    class InArcIt : public Arc {
    … …  
    10861019    };
    10871020
    1088     LemonRangeWrapper2<InArcIt, BpGraph, Node> inArcs(const Node& u) const {
    1089       return LemonRangeWrapper2<InArcIt, BpGraph, Node>(*this, u);
    1090     }
    1091 
    10921021
    10931022    class EdgeIt : public Parent::Edge {
    … …  
    11121041
    11131042    };
    1114 
    1115     LemonRangeWrapper1<EdgeIt, BpGraph> edges() const {
    1116       return LemonRangeWrapper1<EdgeIt, BpGraph>(*this);
    1117     }
    1118 
    11191043
    11201044    class IncEdgeIt : public Parent::Edge {
    … …  
    11421066      }
    11431067    };
    1144 
    1145     LemonRangeWrapper2<IncEdgeIt, BpGraph, Node> incEdges(const Node& u) const {
    1146       return LemonRangeWrapper2<IncEdgeIt, BpGraph, Node>(*this, u);
    1147     }
    1148 
    11491068
    11501069    // \brief Base node of the iterator

  • lemon/bits/path_dump.h

    r1132 r1092  
    6262      }
    6363
    64       operator typename Digraph::Arc() const {
     64      operator const typename Digraph::Arc() const {
    6565        return path->predMap[current];
    6666      }

  • lemon/cbc.cc

    r1130 r1092  
    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

    r1130 r1092  
    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

    r1130 r1092  
    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

    r1130 r1092  
    2828#include <lemon/concept_check.h>
    2929#include <lemon/core.h>
    30 #include <lemon/bits/stl_iterators.h>
    3130
    3231namespace lemon {
    … …  
    223222      };
    224223
    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 
    241224      /// Iterator class for the blue nodes.
    242225
    … …  
    282265      };
    283266
    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 
    300267      /// Iterator class for the nodes.
    301268
    … …  
    341308      };
    342309
    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 
    358 
    359310
    360311      /// The edge type of the graph
    … …  
    445396      };
    446397
    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 
    463 
    464398      /// Iterator class for the incident edges of a node.
    465399
    … …  
    509443        IncEdgeIt& operator++() { return *this; }
    510444      };
    511 
    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 
    530445
    531446      /// The arc type of the graph
    … …  
    624539        ArcIt& operator++() { return *this; }
    625540      };
    626 
    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 
    643541
    644542      /// Iterator class for the outgoing arcs of a node.
    … …  
    690588      };
    691589
    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 
    710590      /// Iterator class for the incoming arcs of a node.
    711591
    … …  
    756636      };
    757637
    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 
    775 
    776638      /// \brief Standard graph map type for the nodes.
    777639      ///

  • lemon/concepts/digraph.h

    r1130 r1093  
    2828#include <lemon/concept_check.h>
    2929#include <lemon/concepts/graph_components.h>
    30 #include <lemon/bits/stl_iterators.h>
    3130
    3231namespace lemon {
    … …  
    149148      };
    150149
    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 
    170150
    171151      /// The arc type of the digraph
    … …  
    258238      };
    259239
    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 
    281240      /// Iterator class for the incoming arcs of a node.
    282241
    … …  
    324283      };
    325284
    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 
    347285      /// Iterator class for the arcs.
    348286
    … …  
    389327        ArcIt& operator++() { return *this; }
    390328      };
    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 
    412329
    413330      /// \brief The source node of the arc.

  • lemon/concepts/graph.h

    r1130 r1093  
    2828#include <lemon/concept_check.h>
    2929#include <lemon/core.h>
    30 #include <lemon/bits/stl_iterators.h>
    3130
    3231namespace lemon {
    … …  
    182181      };
    183182
    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 
    203183
    204184      /// The edge type of the graph
    … …  
    289269      };
    290270
    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 
    311 
    312271      /// Iterator class for the incident edges of a node.
    313272
    … …  
    357316        IncEdgeIt& operator++() { return *this; }
    358317      };
    359 
    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 
    381318
    382319      /// The arc type of the graph
    … …  
    474411        ArcIt& operator++() { return *this; }
    475412      };
    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 
    497413
    498414      /// Iterator class for the outgoing arcs of a node.
    … …  
    544460      };
    545461
    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 
    567462      /// Iterator class for the incoming arcs of a node.
    568463
    … …  
    613508      };
    614509
    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       }
    634 
    635510      /// \brief Standard graph map type for the nodes.
    636511      ///

  • lemon/concepts/path.h

    r1130 r1092  
    2727#include <lemon/core.h>
    2828#include <lemon/concept_check.h>
    29 #include <lemon/bits/stl_iterators.h>
    3029
    3130namespace lemon {
    … …  
    117116      };
    118117
    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 
    136118      template <typename _Path>
    137119      struct Constraints {
    … …  
    282264
    283265      };
    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 
    301266
    302267      /// \brief LEMON style iterator for enumerating the arcs of a path
    … …  
    329294      };
    330295
    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 
    349296      template <typename _Path>
    350297      struct Constraints {

  • lemon/config.h.in

    r1136 r1134  
    44#define LEMON_VERSION "@PROJECT_VERSION@"
    55#cmakedefine LEMON_HAVE_LONG_LONG 1
    6 
    7 #cmakedefine LEMON_CXX11 1
    86
    97#cmakedefine LEMON_WIN32 1

  • lemon/cplex.cc

    r1140 r1139  
    105105    int status;
    106106    _prob = CPXcloneprob(cplexEnv(), cplex._prob, &status);
    107     _rows = cplex._rows;
    108     _cols = cplex._cols;
     107    rows = cplex.rows;
     108    cols = cplex.cols;
    109109    messageLevel(MESSAGE_NOTHING);
    110110  }
    … …  
    133133                         ExprIterator e, Value ub) {
    134134    int i = CPXgetnumrows(cplexEnv(), _prob);
    135 
    136     int rmatbeg = 0;
    137    
     135    if (lb == -INF) {
     136      const char s = 'L';
     137      CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
     138    } else if (ub == INF) {
     139      const char s = 'G';
     140      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
     141    } else if (lb == ub){
     142      const char s = 'E';
     143      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
     144    } else {
     145      const char s = 'R';
     146      double len = ub - lb;
     147      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
     148    }
     149
    138150    std::vector<int> indices;
     151    std::vector<int> rowlist;
    139152    std::vector<Value> values;
    140153
    … …  
    142155      indices.push_back(it->first);
    143156      values.push_back(it->second);
    144     }
    145 
    146     if (lb == -INF) {
    147       const char s = 'L';
    148       CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &ub, &s,
    149                  &rmatbeg, &indices.front(), &values.front(), 0, 0);
    150     } else if (ub == INF) {
    151       const char s = 'G';
    152       CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &lb, &s,
    153                  &rmatbeg, &indices.front(), &values.front(), 0, 0);
    154     } else if (lb == ub){
    155       const char s = 'E';
    156       CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &lb, &s,
    157                  &rmatbeg, &indices.front(), &values.front(), 0, 0);
    158     } else {
    159       const char s = 'R';
    160       double len = ub - lb;
    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    
     157      rowlist.push_back(i);
     158    }
     159
     160    CPXchgcoeflist(cplexEnv(), _prob, values.size(),
     161                   &rowlist.front(), &indices.front(), &values.front());
     162
    166163    return i;
    167164  }
    … …  
    176173
    177174  void CplexBase::_eraseColId(int i) {
    178     _cols.eraseIndex(i);
    179     _cols.shiftIndices(i);
     175    cols.eraseIndex(i);
     176    cols.shiftIndices(i);
    180177  }
    181178  void CplexBase::_eraseRowId(int i) {
    182     _rows.eraseIndex(i);
    183     _rows.shiftIndices(i);
     179    rows.eraseIndex(i);
     180    rows.shiftIndices(i);
    184181  }
    185182

  • lemon/glpk.cc

    r1130 r1092  
    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

    r1130 r1092  
    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/list_graph.h

    r1149 r1148  
    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
    … …  
    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::IncEdgeIt IncEdgeIt;
     1212    typedef Parent::OutArcIt 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
    … …  
    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::IncEdgeIt IncEdgeIt;
     2139    typedef Parent::OutArcIt 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

  • lemon/lp_base.h

    r1144 r1092  
    3232#include<lemon/bits/solver_bits.h>
    3333
    34 #include<lemon/bits/stl_iterators.h>
    35 
    3634///\file
    3735///\brief The interface of the LP solver interface.
    … …  
    4846  protected:
    4947
    50     _solver_bits::VarIndex _rows;
    51     _solver_bits::VarIndex _cols;
     48    _solver_bits::VarIndex rows;
     49    _solver_bits::VarIndex cols;
    5250
    5351  public:
    … …  
    169167      ColIt(const LpBase &solver) : _solver(&solver)
    170168      {
    171         _solver->_cols.firstItem(_id);
     169        _solver->cols.firstItem(_id);
    172170      }
    173171      /// Invalid constructor \& conversion
    … …  
    182180      ColIt &operator++()
    183181      {
    184         _solver->_cols.nextItem(_id);
     182        _solver->cols.nextItem(_id);
    185183        return *this;
    186184      }
    187185    };
    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 
    204186
    205187    /// \brief Returns the ID of the column.
    … …  
    280262      RowIt(const LpBase &solver) : _solver(&solver)
    281263      {
    282         _solver->_rows.firstItem(_id);
     264        _solver->rows.firstItem(_id);
    283265      }
    284266      /// Invalid constructor \& conversion
    … …  
    293275      RowIt &operator++()
    294276      {
    295         _solver->_rows.nextItem(_id);
     277        _solver->rows.nextItem(_id);
    296278        return *this;
    297279      }
    298280    };
    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    
    315281
    316282    /// \brief Returns the ID of the row.
    … …  
    660626    ///This data structure represents a column of the matrix,
    661627    ///thas is it strores a linear expression of the dual variables
    662     ///(\ref LpBase::Row "Row"s).
     628    ///(\ref Row "Row"s).
    663629    ///
    664630    ///There are several ways to access and modify the contents of this
    … …  
    677643    ///(This code computes the sum of all coefficients).
    678644    ///- Numbers (<tt>double</tt>'s)
    679     ///and variables (\ref LpBase::Row "Row"s) directly convert to an
     645    ///and variables (\ref Row "Row"s) directly convert to an
    680646    ///\ref DualExpr and the usual linear operations are defined, so
    681647    ///\code
    … …  
    969935    //Abstract virtual functions
    970936
    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); }
     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); }
    976942
    977943    virtual int _addCol() = 0;
    … …  
    10381004    Value obj_const_comp;
    10391005
    1040     LpBase() : _rows(), _cols(), obj_const_comp(0) {}
     1006    LpBase() : rows(), cols(), obj_const_comp(0) {}
    10411007
    10421008  public:
    … …  
    11501116    void col(Col c, const DualExpr &e) {
    11511117      e.simplify();
    1152       _setColCoeffs(_cols(id(c)), ExprIterator(e.comps.begin(), _rows),
    1153                     ExprIterator(e.comps.end(), _rows));
     1118      _setColCoeffs(cols(id(c)), ExprIterator(e.comps.begin(), rows),
     1119                    ExprIterator(e.comps.end(), rows));
    11541120    }
    11551121
    … …  
    11601126    DualExpr col(Col c) const {
    11611127      DualExpr e;
    1162       _getColCoeffs(_cols(id(c)), InsertIterator(e.comps, _rows));
     1128      _getColCoeffs(cols(id(c)), InsertIterator(e.comps, rows));
    11631129      return e;
    11641130    }
    … …  
    11891155    ///\param t can be
    11901156    ///- a standard STL compatible iterable container with
    1191     ///\ref LpBase::Row "Row" as its \c values_type like
     1157    ///\ref Row as its \c values_type like
    11921158    ///\code
    11931159    ///std::vector<LpBase::Row>
    … …  
    11951161    ///\endcode
    11961162    ///- a standard STL compatible iterable container with
    1197     ///\ref LpBase::Row "Row" as its \c mapped_type like
     1163    ///\ref Row as its \c mapped_type like
    11981164    ///\code
    11991165    ///std::map<AnyType,LpBase::Row>
    … …  
    12471213    void row(Row r, Value l, const Expr &e, Value u) {
    12481214      e.simplify();
    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);
     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);
    12531219    }
    12541220
    … …  
    12691235    Expr row(Row r) const {
    12701236      Expr e;
    1271       _getRowCoeffs(_rows(id(r)), InsertIterator(e.comps, _cols));
     1237      _getRowCoeffs(rows(id(r)), InsertIterator(e.comps, cols));
    12721238      return e;
    12731239    }
    … …  
    12821248      Row r;
    12831249      e.simplify();
    1284       r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), _cols),
    1285                                 ExprIterator(e.comps.end(), _cols), u - *e));
     1250      r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols),
     1251                                ExprIterator(e.comps.end(), cols), u - *e));
    12861252      return r;
    12871253    }
    … …  
    12951261      c.expr().simplify();
    12961262      r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF,
    1297                                 ExprIterator(c.expr().comps.begin(), _cols),
    1298                                 ExprIterator(c.expr().comps.end(), _cols),
     1263                                ExprIterator(c.expr().comps.begin(), cols),
     1264                                ExprIterator(c.expr().comps.end(), cols),
    12991265                                c.upperBounded()?c.upperBound()-*c.expr():INF));
    13001266      return r;
    … …  
    13041270    ///\param c is the column to be deleted
    13051271    void erase(Col c) {
    1306       _eraseCol(_cols(id(c)));
    1307       _eraseColId(_cols(id(c)));
     1272      _eraseCol(cols(id(c)));
     1273      _eraseColId(cols(id(c)));
    13081274    }
    13091275    ///Erase a row (i.e a constraint) from the LP
    … …  
    13111277    ///\param r is the row to be deleted
    13121278    void erase(Row r) {
    1313       _eraseRow(_rows(id(r)));
    1314       _eraseRowId(_rows(id(r)));
     1279      _eraseRow(rows(id(r)));
     1280      _eraseRowId(rows(id(r)));
    13151281    }
    13161282
    … …  
    13211287    std::string colName(Col c) const {
    13221288      std::string name;
    1323       _getColName(_cols(id(c)), name);
     1289      _getColName(cols(id(c)), name);
    13241290      return name;
    13251291    }
    … …  
    13301296    ///\param name The name to be given
    13311297    void colName(Col c, const std::string& name) {
    1332       _setColName(_cols(id(c)), name);
     1298      _setColName(cols(id(c)), name);
    13331299    }
    13341300
    … …  
    13391305    Col colByName(const std::string& name) const {
    13401306      int k = _colByName(name);
    1341       return k != -1 ? Col(_cols[k]) : Col(INVALID);
     1307      return k != -1 ? Col(cols[k]) : Col(INVALID);
    13421308    }
    13431309
    … …  
    13481314    std::string rowName(Row r) const {
    13491315      std::string name;
    1350       _getRowName(_rows(id(r)), name);
     1316      _getRowName(rows(id(r)), name);
    13511317      return name;
    13521318    }
    … …  
    13571323    ///\param name The name to be given
    13581324    void rowName(Row r, const std::string& name) {
    1359       _setRowName(_rows(id(r)), name);
     1325      _setRowName(rows(id(r)), name);
    13601326    }
    13611327
    … …  
    13661332    Row rowByName(const std::string& name) const {
    13671333      int k = _rowByName(name);
    1368       return k != -1 ? Row(_rows[k]) : Row(INVALID);
     1334      return k != -1 ? Row(rows[k]) : Row(INVALID);
    13691335    }
    13701336
    … …  
    13751341    ///\param val is the new value of the coefficient
    13761342    void coeff(Row r, Col c, Value val) {
    1377       _setCoeff(_rows(id(r)),_cols(id(c)), val);
     1343      _setCoeff(rows(id(r)),cols(id(c)), val);
    13781344    }
    13791345
    … …  
    13841350    ///\return the corresponding coefficient
    13851351    Value coeff(Row r, Col c) const {
    1386       return _getCoeff(_rows(id(r)),_cols(id(c)));
     1352      return _getCoeff(rows(id(r)),cols(id(c)));
    13871353    }
    13881354
    … …  
    13931359    /// Value or -\ref INF.
    13941360    void colLowerBound(Col c, Value value) {
    1395       _setColLowerBound(_cols(id(c)),value);
     1361      _setColLowerBound(cols(id(c)),value);
    13961362    }
    13971363
    … …  
    14021368    ///\return The lower bound for column \c c
    14031369    Value colLowerBound(Col c) const {
    1404       return _getColLowerBound(_cols(id(c)));
     1370      return _getColLowerBound(cols(id(c)));
    14051371    }
    14061372
    … …  
    14481414    /// Value or \ref INF.
    14491415    void colUpperBound(Col c, Value value) {
    1450       _setColUpperBound(_cols(id(c)),value);
     1416      _setColUpperBound(cols(id(c)),value);
    14511417    };
    14521418
    … …  
    14571423    /// \return The upper bound for column \c c
    14581424    Value colUpperBound(Col c) const {
    1459       return _getColUpperBound(_cols(id(c)));
     1425      return _getColUpperBound(cols(id(c)));
    14601426    }
    14611427
    … …  
    15041470    /// Value, -\ref INF or \ref INF.
    15051471    void colBounds(Col c, Value lower, Value upper) {
    1506       _setColLowerBound(_cols(id(c)),lower);
    1507       _setColUpperBound(_cols(id(c)),upper);
     1472      _setColLowerBound(cols(id(c)),lower);
     1473      _setColUpperBound(cols(id(c)),upper);
    15081474    }
    15091475
    … …  
    15501516    /// Value or -\ref INF.
    15511517    void rowLowerBound(Row r, Value value) {
    1552       _setRowLowerBound(_rows(id(r)),value);
     1518      _setRowLowerBound(rows(id(r)),value);
    15531519    }
    15541520
    … …  
    15591525    ///\return The lower bound for row \c r
    15601526    Value rowLowerBound(Row r) const {
    1561       return _getRowLowerBound(_rows(id(r)));
     1527      return _getRowLowerBound(rows(id(r)));
    15621528    }
    15631529
    … …  
    15681534    /// Value or -\ref INF.
    15691535    void rowUpperBound(Row r, Value value) {
    1570       _setRowUpperBound(_rows(id(r)),value);
     1536      _setRowUpperBound(rows(id(r)),value);
    15711537    }
    15721538
    … …  
    15771543    ///\return The upper bound for row \c r
    15781544    Value rowUpperBound(Row r) const {
    1579       return _getRowUpperBound(_rows(id(r)));
     1545      return _getRowUpperBound(rows(id(r)));
    15801546    }
    15811547
    15821548    ///Set an element of the objective function
    1583     void objCoeff(Col c, Value v) {_setObjCoeff(_cols(id(c)),v); };
     1549    void objCoeff(Col c, Value v) {_setObjCoeff(cols(id(c)),v); };
    15841550
    15851551    ///Get an element of the objective function
    1586     Value objCoeff(Col c) const { return _getObjCoeff(_cols(id(c))); };
     1552    Value objCoeff(Col c) const { return _getObjCoeff(cols(id(c))); };
    15871553
    15881554    ///Set the objective function
    … …  
    15911557    ///
    15921558    void obj(const Expr& e) {
    1593       _setObjCoeffs(ExprIterator(e.comps.begin(), _cols),
    1594                     ExprIterator(e.comps.end(), _cols));
     1559      _setObjCoeffs(ExprIterator(e.comps.begin(), cols),
     1560                    ExprIterator(e.comps.end(), cols));
    15951561      obj_const_comp = *e;
    15961562    }
    … …  
    16021568    Expr obj() const {
    16031569      Expr e;
    1604       _getObjCoeffs(InsertIterator(e.comps, _cols));
     1570      _getObjCoeffs(InsertIterator(e.comps, cols));
    16051571      *e = obj_const_comp;
    16061572      return e;
    … …  
    16211587
    16221588    ///Clear the problem
    1623     void clear() { _clear(); _rows.clear(); _cols.clear(); }
     1589    void clear() { _clear(); rows.clear(); cols.clear(); }
    16241590
    16251591    /// Set the message level of the solver
    … …  
    19641930    /// Return the primal value of the column.
    19651931    /// \pre The problem is solved.
    1966     Value primal(Col c) const { return _getPrimal(_cols(id(c))); }
     1932    Value primal(Col c) const { return _getPrimal(cols(id(c))); }
    19671933
    19681934    /// Return the primal value of the expression
    … …  
    19911957    /// \note Some solvers does not provide primal ray calculation
    19921958    /// functions.
    1993     Value primalRay(Col c) const { return _getPrimalRay(_cols(id(c))); }
     1959    Value primalRay(Col c) const { return _getPrimalRay(cols(id(c))); }
    19941960
    19951961    /// Return the dual value of the row
    … …  
    19971963    /// Return the dual value of the row.
    19981964    /// \pre The problem is solved.
    1999     Value dual(Row r) const { return _getDual(_rows(id(r))); }
     1965    Value dual(Row r) const { return _getDual(rows(id(r))); }
    20001966
    20011967    /// Return the dual value of the dual expression
    … …  
    20251991    /// \note Some solvers does not provide dual ray calculation
    20261992    /// functions.
    2027     Value dualRay(Row r) const { return _getDualRay(_rows(id(r))); }
     1993    Value dualRay(Row r) const { return _getDualRay(rows(id(r))); }
    20281994
    20291995    /// Return the basis status of the column
    20301996
    20311997    /// \see VarStatus
    2032     VarStatus colStatus(Col c) const { return _getColStatus(_cols(id(c))); }
     1998    VarStatus colStatus(Col c) const { return _getColStatus(cols(id(c))); }
    20331999
    20342000    /// Return the basis status of the row
    20352001
    20362002    /// \see VarStatus
    2037     VarStatus rowStatus(Row r) const { return _getRowStatus(_rows(id(r))); }
     2003    VarStatus rowStatus(Row r) const { return _getRowStatus(rows(id(r))); }
    20382004
    20392005    ///The value of the objective function
    … …  
    21152081    ///
    21162082    void colType(Col c, ColTypes col_type) {
    2117       _setColType(_cols(id(c)),col_type);
     2083      _setColType(cols(id(c)),col_type);
    21182084    }
    21192085
    … …  
    21232089    ///
    21242090    ColTypes colType(Col c) const {
    2125       return _getColType(_cols(id(c)));
     2091      return _getColType(cols(id(c)));
    21262092    }
    21272093    ///@}
    … …  
    21402106    ///  Return the value of the row in the solution.
    21412107    /// \pre The problem is solved.
    2142     Value sol(Col c) const { return _getSol(_cols(id(c))); }
     2108    Value sol(Col c) const { return _getSol(cols(id(c))); }
    21432109
    21442110    /// Return the value of the expression in the solution

  • lemon/maps.h

    r1130 r1092  
    2626
    2727#include <lemon/core.h>
    28 #include <lemon/bits/stl_iterators.h>
    2928
    3029///\file
    … …  
    25832582    };
    25842583
    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 
    25952584    /// \brief Iterator for the keys mapped to \c false.
    25962585    ///
    … …  
    26312620      const IterableBoolMap* _map;
    26322621    };
    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 
    26432622
    26442623    /// \brief Iterator for the keys mapped to a given value.
    … …  
    26852664      const IterableBoolMap* _map;
    26862665    };
    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     }
    26962666
    26972667  protected:
    … …  
    30363006    };
    30373007
    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 
    30483008  protected:
    30493009
    … …  
    32893249    };
    32903250
    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 
    33013251  protected:
    33023252

  • lemon/path.h

    r1130 r1092  
    3131#include <lemon/core.h>
    3232#include <lemon/concepts/path.h>
    33 #include <lemon/bits/stl_iterators.h>
    3433
    3534namespace lemon {
    … …  
    141140      int idx;
    142141    };
    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 
    160142
    161143    /// \brief Length of the path.
    … …  
    364346    };
    365347
    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 
    383348    /// \brief Length of the path.
    384349    int length() const { return data.size(); }
    … …  
    578543      Node *node;
    579544    };
    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 
    597545
    598546    /// \brief The n-th arc.
    … …  
    848796    ///
    849797    /// Default constructor
    850     StaticPath() : len(0), _arcs(0) {}
     798    StaticPath() : len(0), arcs(0) {}
    851799
    852800    /// \brief Copy constructor
    853801    ///
    854     StaticPath(const StaticPath& cpath) : _arcs(0) {
     802    StaticPath(const StaticPath& cpath) : arcs(0) {
    855803      pathCopy(cpath, *this);
    856804    }
    … …  
    860808    /// This path can be initialized from any other path type.
    861809    template <typename CPath>
    862     StaticPath(const CPath& cpath) : _arcs(0) {
     810    StaticPath(const CPath& cpath) : arcs(0) {
    863811      pathCopy(cpath, *this);
    864812    }
    … …  
    868816    /// Destructor of the path
    869817    ~StaticPath() {
    870       if (_arcs) delete[] _arcs;
     818      if (arcs) delete[] arcs;
    871819    }
    872820
    … …  
    935883      int idx;
    936884    };
    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    
    954885
    955886    /// \brief The n-th arc.
    … …  
    957888    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    958889    const Arc& nth(int n) const {
    959       return _arcs[n];
     890      return arcs[n];
    960891    }
    961892
    … …  
    974905    void clear() {
    975906      len = 0;
    976       if (_arcs) delete[] _arcs;
    977       _arcs = 0;
     907      if (arcs) delete[] arcs;
     908      arcs = 0;
    978909    }
    979910
    980911    /// \brief The first arc of the path.
    981912    const Arc& front() const {
    982       return _arcs[0];
     913      return arcs[0];
    983914    }
    984915
    985916    /// \brief The last arc of the path.
    986917    const Arc& back() const {
    987       return _arcs[len - 1];
     918      return arcs[len - 1];
    988919    }
    989920
    … …  
    994925    void build(const CPath& path) {
    995926      len = path.length();
    996       _arcs = new Arc[len];
     927      arcs = new Arc[len];
    997928      int index = 0;
    998929      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
    999         _arcs[index] = it;
     930        arcs[index] = it;
    1000931        ++index;
    1001932      }
    … …  
    1005936    void buildRev(const CPath& path) {
    1006937      len = path.length();
    1007       _arcs = new Arc[len];
     938      arcs = new Arc[len];
    1008939      int index = len;
    1009940      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
    1010941        --index;
    1011         _arcs[index] = it;
     942        arcs[index] = it;
    1012943      }
    1013944    }
    … …  
    1015946  private:
    1016947    int len;
    1017     Arc* _arcs;
     948    Arc* arcs;
    1018949  };
    1019950
    … …  
    12271158  };
    12281159
    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 
    12481160  ///@}
    12491161

  • lemon/random.h

    r1136 r1134  
    252252        current = state + length;
    253253
    254         Word *curr = state + length - 1;
    255         long num;
     254        register Word *curr = state + length - 1;
     255        register long num;
    256256
    257257        num = length - shift;

  • lemon/smart_graph.h

    r1130 r1092  
    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         _nodes[_arcs[n-1].target].first_out=_arcs[n].next_out;
    1252         _nodes[_arcs[n].target].first_out=_arcs[n-1].next_out;
    1253         _arcs.pop_back();
    1254         _arcs.pop_back();
    1255       }
    1256       while(s.node_num<_nodes.size()) {
    1257         int n=_nodes.size()-1;
     1251        nodes[arcs[n-1].target].first_out=arcs[n].next_out;
     1252        nodes[arcs[n].target].first_out=arcs[n-1].next_out;
     1253        arcs.pop_back();
     1254        arcs.pop_back();
     1255      }
     1256      while(s.node_num<nodes.size()) {
     1257        int n=nodes.size()-1;
    12581258        Node node = nodeFromId(n);
    12591259        if (Parent::red(node)) {
    1260           first_red = _nodes[n].partition_next;
     1260          first_red = nodes[n].partition_next;
    12611261          if (first_red != -1) {
    1262             max_red = _nodes[first_red].partition_index;
     1262            max_red = nodes[first_red].partition_index;
    12631263          } else {
    12641264            max_red = -1;
    … …  
    12661266          Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));
    12671267        } else {
    1268           first_blue = _nodes[n].partition_next;
     1268          first_blue = nodes[n].partition_next;
    12691269          if (first_blue != -1) {
    1270             max_blue = _nodes[first_blue].partition_index;
     1270            max_blue = nodes[first_blue].partition_index;
    12711271          } else {
    12721272            max_blue = -1;
    … …  
    12751275        }
    12761276        Parent::notifier(Node()).erase(node);
    1277         _nodes.pop_back();
     1277        nodes.pop_back();
    12781278      }
    12791279    }

  • lemon/soplex.cc

    r1130 r1092  
    3838
    3939  SoplexLp::SoplexLp(const SoplexLp& lp) {
    40     _rows = lp._rows;
    41     _cols = lp._cols;
     40    rows = lp.rows;
     41    cols = lp.cols;
    4242
    4343    soplex = new soplex::SoPlex;
    … …  
    123123
    124124  void SoplexLp::_eraseColId(int i) {
    125     _cols.eraseIndex(i);
    126     _cols.relocateIndex(i, _cols.maxIndex());
     125    cols.eraseIndex(i);
     126    cols.relocateIndex(i, cols.maxIndex());
    127127  }
    128128  void SoplexLp::_eraseRowId(int i) {
    129     _rows.eraseIndex(i);
    130     _rows.relocateIndex(i, _rows.maxIndex());
     129    rows.eraseIndex(i);
     130    rows.relocateIndex(i, rows.maxIndex());
    131131  }
    132132
    … …  
    433433    _row_names.clear();
    434434    _row_names_ref.clear();
    435     _cols.clear();
    436     _rows.clear();
     435    cols.clear();
     436    rows.clear();
    437437    _clear_temporals();
    438438  }

  • test/CMakeLists.txt

    r1141 r1088  
    5555  tsp_test
    5656  unionfind_test
    57   vf2_test
    5857)
    5958

  • test/bellman_ford_test.cc

    r1131 r1092  
    102102
    103103    for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
    104     for (auto n: const_bf_test.activeNodes()) { ::lemon::ignore_unused_variable_warning(n); }
    105     for (Digraph::Node n: const_bf_test.activeNodes()) {
    106       ::lemon::ignore_unused_variable_warning(n);
    107     }
    108104  }
    109105  {

  • test/graph_test.h

    r1131 r1092  
    3939    check(n==INVALID,"Wrong Node list linking.");
    4040    check(countNodes(G)==cnt,"Wrong Node number.");
    41 
    42 #ifdef LEMON_CXX11
    43     {
    44       typename Graph::NodeIt n(G);
    45       for(auto u: G.nodes())
    46         {
    47           check(n==u,"Wrong STL Node iterator.");
    48           ++n;
    49         }
    50       check(n==INVALID,"Wrong STL Node iterator.");
    51     }
    52     {
    53       typename Graph::NodeIt n(G);
    54       for(typename Graph::Node u: G.nodes())
    55         {
    56           check(n==u,"Wrong STL Node iterator.");
    57           ++n;
    58         }
    59       check(n==INVALID,"Wrong STL Node iterator.");
    60     }
    61 #endif
    6241  }
    6342
    … …  
    7857    check(n==INVALID,"Wrong red Node list linking.");
    7958    check(countRedNodes(G)==cnt,"Wrong red Node number.");
    80 #ifdef LEMON_CXX11
    81     {
    82       typename Graph::RedNodeIt n(G);
    83       for(auto u: G.redNodes())
    84         {
    85           check(n==u,"Wrong STL RedNode iterator.");
    86           ++n;
    87         }
    88       check(n==INVALID,"Wrong STL RedNode iterator.");
    89     }
    90     {
    91       typename Graph::RedNodeIt n(G);
    92       for(typename Graph::RedNode u: G.redNodes())
    93         {
    94           check(n==u,"Wrong STL RedNode iterator.");
    95           ++n;
    96         }
    97       check(n==INVALID,"Wrong STL RedNode iterator.");
    98     }
    99 #endif
    10059  }
    10160
    … …  
    11675    check(n==INVALID,"Wrong blue Node list linking.");
    11776    check(countBlueNodes(G)==cnt,"Wrong blue Node number.");
    118 #ifdef LEMON_CXX11
    119     {
    120       typename Graph::BlueNodeIt n(G);
    121       for(auto u: G.blueNodes())
    122         {
    123           check(n==u,"Wrong STL BlueNode iterator.");
    124           ++n;
    125         }
    126       check(n==INVALID,"Wrong STL BlueNode iterator.");
    127     }
    128     {
    129       typename Graph::BlueNodeIt n(G);
    130       for(typename Graph::BlueNode u: G.blueNodes())
    131         {
    132           check(n==u,"Wrong STL BlueNode iterator.");
    133           ++n;
    134         }
    135       check(n==INVALID,"Wrong STL BlueNode iterator.");
    136     }
    137 #endif
    138 
    13977  }
    14078
    … …  
    15391    check(e==INVALID,"Wrong Arc list linking.");
    15492    check(countArcs(G)==cnt,"Wrong Arc number.");
    155 #ifdef LEMON_CXX11
    156     {
    157       typename Graph::ArcIt a(G);
    158       for(auto e: G.arcs())
    159         {
    160           check(a==e,"Wrong STL Arc iterator.");
    161           ++a;
    162         }
    163       check(a==INVALID,"Wrong STL Arc iterator.");
    164     }
    165     {
    166       typename Graph::ArcIt a(G);
    167       for(typename Graph::Arc e: G.arcs())
    168         {
    169           check(a==e,"Wrong STL Arc iterator.");
    170           ++a;
    171         }
    172       check(a==INVALID,"Wrong STL Arc iterator.");
    173     }
    174 #endif
    175 
    17693  }
    17794
    … …  
    189106    check(e==INVALID,"Wrong OutArc list linking.");
    190107    check(countOutArcs(G,n)==cnt,"Wrong OutArc number.");
    191 #ifdef LEMON_CXX11
    192     {
    193       typename Graph::OutArcIt a(G,n);
    194       for(auto e: G.outArcs(n))
    195         {
    196           check(a==e,"Wrong STL OutArc iterator.");
    197           ++a;
    198         }
    199       check(a==INVALID,"Wrong STL OutArc iterator.");
    200     }
    201     {
    202       typename Graph::OutArcIt a(G,n);
    203       for(typename Graph::Arc e: G.outArcs(n))
    204         {
    205           check(a==e,"Wrong STL OutArc iterator.");
    206           ++a;
    207         }
    208       check(a==INVALID,"Wrong STL OutArc iterator.");
    209     }
    210 #endif
    211 
    212108  }
    213109
    … …  
    225121    check(e==INVALID,"Wrong InArc list linking.");
    226122    check(countInArcs(G,n)==cnt,"Wrong InArc number.");
    227 #ifdef LEMON_CXX11
    228     {
    229       typename Graph::InArcIt a(G,n);
    230       for(auto e: G.inArcs(n))
    231         {
    232           check(a==e,"Wrong STL InArc iterator.");
    233           ++a;
    234         }
    235       check(a==INVALID,"Wrong STL InArc iterator.");
    236     }
    237     {
    238       typename Graph::InArcIt a(G,n);
    239       for(typename Graph::Arc e: G.inArcs(n))
    240         {
    241           check(a==e,"Wrong STL InArc iterator.");
    242           ++a;
    243         }
    244       check(a==INVALID,"Wrong STL InArc iterator.");
    245     }
    246 #endif
    247123  }
    248124
    … …  
    259135    check(e==INVALID,"Wrong Edge list linking.");
    260136    check(countEdges(G)==cnt,"Wrong Edge number.");
    261 #ifdef LEMON_CXX11
    262     {
    263       typename Graph::EdgeIt a(G);
    264       for(auto e: G.edges())
    265         {
    266           check(a==e,"Wrong STL Edge iterator.");
    267           ++a;
    268         }
    269       check(a==INVALID,"Wrong STL Edge iterator.");
    270     }
    271     {
    272       typename Graph::EdgeIt a(G);
    273       for(typename Graph::Edge e: G.edges())
    274         {
    275           check(a==e,"Wrong STL Edge iterator.");
    276           ++a;
    277         }
    278       check(a==INVALID,"Wrong STL Edge iterator.");
    279     }
    280 #endif
    281 
    282137  }
    283138
    … …  
    296151    check(e==INVALID,"Wrong IncEdge list linking.");
    297152    check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
    298 #ifdef LEMON_CXX11
    299     {
    300       typename Graph::IncEdgeIt a(G,n);
    301       for(auto e: G.incEdges(n))
    302         {
    303           check(a==e,"Wrong STL IncEdge iterator.");
    304           ++a;
    305         }
    306       check(a==INVALID,"Wrong STL IncEdge iterator.");
    307     }
    308     {
    309       typename Graph::IncEdgeIt a(G,n);
    310       for(typename Graph::Edge e: G.incEdges(n))
    311         {
    312           check(a==e,"Wrong STL IncEdge iterator.");
    313           ++a;
    314         }
    315       check(a==INVALID,"Wrong STL IncEdge iterator.");
    316     }
    317 #endif
    318 
    319153  }
    320154

  • test/lp_test.cc

    r1131 r1105  
    2121#include "test_tools.h"
    2222#include <lemon/tolerance.h>
    23 #include <lemon/concept_check.h>
     23
    2424#include <lemon/config.h>
    2525
    … …  
    4848  int count=0;
    4949  for (LpBase::ColIt c(lp); c!=INVALID; ++c) ++count;
    50 #ifdef LEMON_CXX11
    51   int cnt = 0;
    52   for(auto c: lp.cols()) { cnt++; ::lemon::ignore_unused_variable_warning(c); }
    53   check(count == cnt, "Wrong STL iterator");
    54 #endif
    5550  return count;
    5651}
    … …  
    5954  int count=0;
    6055  for (LpBase::RowIt r(lp); r!=INVALID; ++r) ++count;
    61 #ifdef LEMON_CXX11
    62   int cnt = 0;
    63   for(auto r: lp.rows()) { cnt++; ::lemon::ignore_unused_variable_warning(r); }
    64   check(count == cnt, "Wrong STL iterator");
    65 #endif
    6656  return count;
    6757}

  • test/maps_test.cc

    r1131 r1092  
    731731    check(n == 3, "Wrong number");
    732732    check(map1.falseNum() == 3, "Wrong number");
    733 
    734 #ifdef LEMON_CXX11
    735     {
    736       int c = 0;
    737       for(auto v: map1.items(false)) { c++; ::lemon::ignore_unused_variable_warning(v); }
    738       check(c == map1.falseNum(), "Wrong number");
    739     }
    740     {
    741       int c = 0;
    742       for(auto v: map1.items(true)) { c++; ::lemon::ignore_unused_variable_warning(v); }
    743       check(c == map1.trueNum(), "Wrong number");
    744     }
    745     {
    746       int c = 0;
    747       for(auto v: map1.falseKeys()) { c++; ::lemon::ignore_unused_variable_warning(v); }
    748       check(c == map1.falseNum(), "Wrong number");
    749     }
    750     {
    751       int c = 0;
    752       for(auto v: map1.trueKeys()) { c++; ::lemon::ignore_unused_variable_warning(v); }
    753       check(c == map1.trueNum(), "Wrong number");
    754     }
    755 #endif
    756 
    757733  }
    758734
    … …  
    805781    }
    806782    check(n == num, "Wrong number");
    807 #ifdef LEMON_CXX11
    808     {
    809       int c = 0;
    810       for(auto v: map1.items(0)) { c++; ::lemon::ignore_unused_variable_warning(v); }
    811       check(c == (num + 1) / 2, "Wrong number");
    812       for(auto v: map1.items(1)) { c++; ::lemon::ignore_unused_variable_warning(v); }
    813       check(c == num, "Wrong number");
    814     }
    815 #endif
    816783
    817784  }
    … …  
    872839    }
    873840    check(n == num, "Wrong number");
    874 
    875 #ifdef LEMON_CXX11
    876     {
    877       int c = 0;
    878       for(auto v: map1.items(0.0)) { c++; ::lemon::ignore_unused_variable_warning(v); }
    879       check(c == (num + 1) / 2, "Wrong number");
    880       for(auto v: map1.items(1.0)) { c++; ::lemon::ignore_unused_variable_warning(v); }
    881       check(c == num, "Wrong number");
    882     }
    883 #endif
    884841
    885842  }
Note: See TracChangeset for help on using the changeset viewer.