COIN-OR::LEMON - Graph Library

Changeset 1336:0759d974de81 in lemon


Ignore:
Timestamp:
01/05/14 22:24:56 (6 years ago)
Author:
Gabor Gevay <ggab90@…>
Branch:
default
Phase:
public
Message:

STL style iterators (#325)

For

  • graph types,
  • graph adaptors,
  • paths,
  • iterable maps,
  • LP rows/cols and
  • active nodes is BellmanFord?
Files:
1 added
20 edited

Legend:

Unmodified
Added
Removed
  • CMakeLists.txt

    r1335 r1336  
    263263ENABLE_TESTING()
    264264
     265
     266INCLUDE(CheckCXXCompilerFlag)
     267CHECK_CXX_COMPILER_FLAG("-std=c++11" CXX11FLAG)
     268IF(CXX11FLAG)
     269  SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
     270ENDIF()
     271
     272
    265273IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
    266274  ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
  • lemon/bellman_ford.h

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

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

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

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

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

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

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

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

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

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

    r1330 r1336  
    8888    int status;
    8989    _prob = CPXcloneprob(cplexEnv(), cplex._prob, &status);
    90     rows = cplex.rows;
    91     cols = cplex.cols;
     90    _rows = cplex._rows;
     91    _cols = cplex._cols;
    9292    messageLevel(MESSAGE_NOTHING);
    9393  }
     
    159159
    160160  void CplexBase::_eraseColId(int i) {
    161     cols.eraseIndex(i);
    162     cols.shiftIndices(i);
     161    _cols.eraseIndex(i);
     162    _cols.shiftIndices(i);
    163163  }
    164164  void CplexBase::_eraseRowId(int i) {
    165     rows.eraseIndex(i);
    166     rows.shiftIndices(i);
     165    _rows.eraseIndex(i);
     166    _rows.shiftIndices(i);
    167167  }
    168168
  • lemon/glpk.cc

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

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

    r1270 r1336  
    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
     
    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
     
    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

    r1270 r1336  
    3232#include<lemon/bits/solver_bits.h>
    3333
     34#include<lemon/bits/stl_iterators.h>
     35
    3436///\file
    3537///\brief The interface of the LP solver interface.
     
    4648  protected:
    4749
    48     _solver_bits::VarIndex rows;
    49     _solver_bits::VarIndex cols;
     50    _solver_bits::VarIndex _rows;
     51    _solver_bits::VarIndex _cols;
    5052
    5153  public:
     
    167169      ColIt(const LpBase &solver) : _solver(&solver)
    168170      {
    169         _solver->cols.firstItem(_id);
     171        _solver->_cols.firstItem(_id);
    170172      }
    171173      /// Invalid constructor \& conversion
     
    180182      ColIt &operator++()
    181183      {
    182         _solver->cols.nextItem(_id);
     184        _solver->_cols.nextItem(_id);
    183185        return *this;
    184186      }
    185187    };
     188
     189    /// \brief Gets the collection of the columns of the LP problem.
     190    ///
     191    /// This function can be used for iterating on
     192    /// the columns of the LP problem. It returns a wrapped ColIt, which looks
     193    /// like an STL container (by having begin() and end())
     194    /// which you can use in range-based for loops, STL algorithms, etc.
     195    /// For example you can write:
     196    ///\code
     197    /// for(auto c: lp.cols())
     198    ///   doSomething(c);
     199    LemonRangeWrapper1<ColIt, LpBase> cols() {
     200      return LemonRangeWrapper1<ColIt, LpBase>(*this);
     201    }
     202
    186203
    187204    /// \brief Returns the ID of the column.
     
    262279      RowIt(const LpBase &solver) : _solver(&solver)
    263280      {
    264         _solver->rows.firstItem(_id);
     281        _solver->_rows.firstItem(_id);
    265282      }
    266283      /// Invalid constructor \& conversion
     
    275292      RowIt &operator++()
    276293      {
    277         _solver->rows.nextItem(_id);
     294        _solver->_rows.nextItem(_id);
    278295        return *this;
    279296      }
    280297    };
     298   
     299    /// \brief Gets the collection of the rows of the LP problem.
     300    ///
     301    /// This function can be used for iterating on
     302    /// the rows of the LP problem. It returns a wrapped RowIt, which looks
     303    /// like an STL container (by having begin() and end())
     304    /// which you can use in range-based for loops, STL algorithms, etc.
     305    /// For example you can write:
     306    ///\code
     307    /// for(auto c: lp.rows())
     308    ///   doSomething(c);
     309    LemonRangeWrapper1<RowIt, LpBase> rows() {
     310      return LemonRangeWrapper1<RowIt, LpBase>(*this);
     311    }
     312   
    281313
    282314    /// \brief Returns the ID of the row.
     
    935967    //Abstract virtual functions
    936968
    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); }
     969    virtual int _addColId(int col) { return _cols.addIndex(col); }
     970    virtual int _addRowId(int row) { return _rows.addIndex(row); }
     971
     972    virtual void _eraseColId(int col) { _cols.eraseIndex(col); }
     973    virtual void _eraseRowId(int row) { _rows.eraseIndex(row); }
    942974
    943975    virtual int _addCol() = 0;
     
    10041036    Value obj_const_comp;
    10051037
    1006     LpBase() : rows(), cols(), obj_const_comp(0) {}
     1038    LpBase() : _rows(), _cols(), obj_const_comp(0) {}
    10071039
    10081040  public:
     
    11161148    void col(Col c, const DualExpr &e) {
    11171149      e.simplify();
    1118       _setColCoeffs(cols(id(c)), ExprIterator(e.comps.begin(), rows),
    1119                     ExprIterator(e.comps.end(), rows));
     1150      _setColCoeffs(_cols(id(c)), ExprIterator(e.comps.begin(), _rows),
     1151                    ExprIterator(e.comps.end(), _rows));
    11201152    }
    11211153
     
    11261158    DualExpr col(Col c) const {
    11271159      DualExpr e;
    1128       _getColCoeffs(cols(id(c)), InsertIterator(e.comps, rows));
     1160      _getColCoeffs(_cols(id(c)), InsertIterator(e.comps, _rows));
    11291161      return e;
    11301162    }
     
    12131245    void row(Row r, Value l, const Expr &e, Value u) {
    12141246      e.simplify();
    1215       _setRowCoeffs(rows(id(r)), ExprIterator(e.comps.begin(), cols),
    1216                     ExprIterator(e.comps.end(), cols));
    1217       _setRowLowerBound(rows(id(r)),l - *e);
    1218       _setRowUpperBound(rows(id(r)),u - *e);
     1247      _setRowCoeffs(_rows(id(r)), ExprIterator(e.comps.begin(), _cols),
     1248                    ExprIterator(e.comps.end(), _cols));
     1249      _setRowLowerBound(_rows(id(r)),l - *e);
     1250      _setRowUpperBound(_rows(id(r)),u - *e);
    12191251    }
    12201252
     
    12351267    Expr row(Row r) const {
    12361268      Expr e;
    1237       _getRowCoeffs(rows(id(r)), InsertIterator(e.comps, cols));
     1269      _getRowCoeffs(_rows(id(r)), InsertIterator(e.comps, _cols));
    12381270      return e;
    12391271    }
     
    12481280      Row r;
    12491281      e.simplify();
    1250       r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols),
    1251                                 ExprIterator(e.comps.end(), cols), u - *e));
     1282      r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), _cols),
     1283                                ExprIterator(e.comps.end(), _cols), u - *e));
    12521284      return r;
    12531285    }
     
    12611293      c.expr().simplify();
    12621294      r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF,
    1263                                 ExprIterator(c.expr().comps.begin(), cols),
    1264                                 ExprIterator(c.expr().comps.end(), cols),
     1295                                ExprIterator(c.expr().comps.begin(), _cols),
     1296                                ExprIterator(c.expr().comps.end(), _cols),
    12651297                                c.upperBounded()?c.upperBound()-*c.expr():INF));
    12661298      return r;
     
    12701302    ///\param c is the column to be deleted
    12711303    void erase(Col c) {
    1272       _eraseCol(cols(id(c)));
    1273       _eraseColId(cols(id(c)));
     1304      _eraseCol(_cols(id(c)));
     1305      _eraseColId(_cols(id(c)));
    12741306    }
    12751307    ///Erase a row (i.e a constraint) from the LP
     
    12771309    ///\param r is the row to be deleted
    12781310    void erase(Row r) {
    1279       _eraseRow(rows(id(r)));
    1280       _eraseRowId(rows(id(r)));
     1311      _eraseRow(_rows(id(r)));
     1312      _eraseRowId(_rows(id(r)));
    12811313    }
    12821314
     
    12871319    std::string colName(Col c) const {
    12881320      std::string name;
    1289       _getColName(cols(id(c)), name);
     1321      _getColName(_cols(id(c)), name);
    12901322      return name;
    12911323    }
     
    12961328    ///\param name The name to be given
    12971329    void colName(Col c, const std::string& name) {
    1298       _setColName(cols(id(c)), name);
     1330      _setColName(_cols(id(c)), name);
    12991331    }
    13001332
     
    13051337    Col colByName(const std::string& name) const {
    13061338      int k = _colByName(name);
    1307       return k != -1 ? Col(cols[k]) : Col(INVALID);
     1339      return k != -1 ? Col(_cols[k]) : Col(INVALID);
    13081340    }
    13091341
     
    13141346    std::string rowName(Row r) const {
    13151347      std::string name;
    1316       _getRowName(rows(id(r)), name);
     1348      _getRowName(_rows(id(r)), name);
    13171349      return name;
    13181350    }
     
    13231355    ///\param name The name to be given
    13241356    void rowName(Row r, const std::string& name) {
    1325       _setRowName(rows(id(r)), name);
     1357      _setRowName(_rows(id(r)), name);
    13261358    }
    13271359
     
    13321364    Row rowByName(const std::string& name) const {
    13331365      int k = _rowByName(name);
    1334       return k != -1 ? Row(rows[k]) : Row(INVALID);
     1366      return k != -1 ? Row(_rows[k]) : Row(INVALID);
    13351367    }
    13361368
     
    13411373    ///\param val is the new value of the coefficient
    13421374    void coeff(Row r, Col c, Value val) {
    1343       _setCoeff(rows(id(r)),cols(id(c)), val);
     1375      _setCoeff(_rows(id(r)),_cols(id(c)), val);
    13441376    }
    13451377
     
    13501382    ///\return the corresponding coefficient
    13511383    Value coeff(Row r, Col c) const {
    1352       return _getCoeff(rows(id(r)),cols(id(c)));
     1384      return _getCoeff(_rows(id(r)),_cols(id(c)));
    13531385    }
    13541386
     
    13591391    /// Value or -\ref INF.
    13601392    void colLowerBound(Col c, Value value) {
    1361       _setColLowerBound(cols(id(c)),value);
     1393      _setColLowerBound(_cols(id(c)),value);
    13621394    }
    13631395
     
    13681400    ///\return The lower bound for column \c c
    13691401    Value colLowerBound(Col c) const {
    1370       return _getColLowerBound(cols(id(c)));
     1402      return _getColLowerBound(_cols(id(c)));
    13711403    }
    13721404
     
    14141446    /// Value or \ref INF.
    14151447    void colUpperBound(Col c, Value value) {
    1416       _setColUpperBound(cols(id(c)),value);
     1448      _setColUpperBound(_cols(id(c)),value);
    14171449    };
    14181450
     
    14231455    /// \return The upper bound for column \c c
    14241456    Value colUpperBound(Col c) const {
    1425       return _getColUpperBound(cols(id(c)));
     1457      return _getColUpperBound(_cols(id(c)));
    14261458    }
    14271459
     
    14701502    /// Value, -\ref INF or \ref INF.
    14711503    void colBounds(Col c, Value lower, Value upper) {
    1472       _setColLowerBound(cols(id(c)),lower);
    1473       _setColUpperBound(cols(id(c)),upper);
     1504      _setColLowerBound(_cols(id(c)),lower);
     1505      _setColUpperBound(_cols(id(c)),upper);
    14741506    }
    14751507
     
    15161548    /// Value or -\ref INF.
    15171549    void rowLowerBound(Row r, Value value) {
    1518       _setRowLowerBound(rows(id(r)),value);
     1550      _setRowLowerBound(_rows(id(r)),value);
    15191551    }
    15201552
     
    15251557    ///\return The lower bound for row \c r
    15261558    Value rowLowerBound(Row r) const {
    1527       return _getRowLowerBound(rows(id(r)));
     1559      return _getRowLowerBound(_rows(id(r)));
    15281560    }
    15291561
     
    15341566    /// Value or -\ref INF.
    15351567    void rowUpperBound(Row r, Value value) {
    1536       _setRowUpperBound(rows(id(r)),value);
     1568      _setRowUpperBound(_rows(id(r)),value);
    15371569    }
    15381570
     
    15431575    ///\return The upper bound for row \c r
    15441576    Value rowUpperBound(Row r) const {
    1545       return _getRowUpperBound(rows(id(r)));
     1577      return _getRowUpperBound(_rows(id(r)));
    15461578    }
    15471579
    15481580    ///Set an element of the objective function
    1549     void objCoeff(Col c, Value v) {_setObjCoeff(cols(id(c)),v); };
     1581    void objCoeff(Col c, Value v) {_setObjCoeff(_cols(id(c)),v); };
    15501582
    15511583    ///Get an element of the objective function
    1552     Value objCoeff(Col c) const { return _getObjCoeff(cols(id(c))); };
     1584    Value objCoeff(Col c) const { return _getObjCoeff(_cols(id(c))); };
    15531585
    15541586    ///Set the objective function
     
    15571589    ///
    15581590    void obj(const Expr& e) {
    1559       _setObjCoeffs(ExprIterator(e.comps.begin(), cols),
    1560                     ExprIterator(e.comps.end(), cols));
     1591      _setObjCoeffs(ExprIterator(e.comps.begin(), _cols),
     1592                    ExprIterator(e.comps.end(), _cols));
    15611593      obj_const_comp = *e;
    15621594    }
     
    15681600    Expr obj() const {
    15691601      Expr e;
    1570       _getObjCoeffs(InsertIterator(e.comps, cols));
     1602      _getObjCoeffs(InsertIterator(e.comps, _cols));
    15711603      *e = obj_const_comp;
    15721604      return e;
     
    15871619
    15881620    ///Clear the problem
    1589     void clear() { _clear(); rows.clear(); cols.clear(); }
     1621    void clear() { _clear(); _rows.clear(); _cols.clear(); }
    15901622
    15911623    /// Set the message level of the solver
     
    19301962    /// Return the primal value of the column.
    19311963    /// \pre The problem is solved.
    1932     Value primal(Col c) const { return _getPrimal(cols(id(c))); }
     1964    Value primal(Col c) const { return _getPrimal(_cols(id(c))); }
    19331965
    19341966    /// Return the primal value of the expression
     
    19571989    /// \note Some solvers does not provide primal ray calculation
    19581990    /// functions.
    1959     Value primalRay(Col c) const { return _getPrimalRay(cols(id(c))); }
     1991    Value primalRay(Col c) const { return _getPrimalRay(_cols(id(c))); }
    19601992
    19611993    /// Return the dual value of the row
     
    19631995    /// Return the dual value of the row.
    19641996    /// \pre The problem is solved.
    1965     Value dual(Row r) const { return _getDual(rows(id(r))); }
     1997    Value dual(Row r) const { return _getDual(_rows(id(r))); }
    19661998
    19671999    /// Return the dual value of the dual expression
     
    19912023    /// \note Some solvers does not provide dual ray calculation
    19922024    /// functions.
    1993     Value dualRay(Row r) const { return _getDualRay(rows(id(r))); }
     2025    Value dualRay(Row r) const { return _getDualRay(_rows(id(r))); }
    19942026
    19952027    /// Return the basis status of the column
    19962028
    19972029    /// \see VarStatus
    1998     VarStatus colStatus(Col c) const { return _getColStatus(cols(id(c))); }
     2030    VarStatus colStatus(Col c) const { return _getColStatus(_cols(id(c))); }
    19992031
    20002032    /// Return the basis status of the row
    20012033
    20022034    /// \see VarStatus
    2003     VarStatus rowStatus(Row r) const { return _getRowStatus(rows(id(r))); }
     2035    VarStatus rowStatus(Row r) const { return _getRowStatus(_rows(id(r))); }
    20042036
    20052037    ///The value of the objective function
     
    20812113    ///
    20822114    void colType(Col c, ColTypes col_type) {
    2083       _setColType(cols(id(c)),col_type);
     2115      _setColType(_cols(id(c)),col_type);
    20842116    }
    20852117
     
    20892121    ///
    20902122    ColTypes colType(Col c) const {
    2091       return _getColType(cols(id(c)));
     2123      return _getColType(_cols(id(c)));
    20922124    }
    20932125    ///@}
     
    21062138    ///  Return the value of the row in the solution.
    21072139    /// \pre The problem is solved.
    2108     Value sol(Col c) const { return _getSol(cols(id(c))); }
     2140    Value sol(Col c) const { return _getSol(_cols(id(c))); }
    21092141
    21102142    /// Return the value of the expression in the solution
  • lemon/maps.h

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

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

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

    r1270 r1336  
    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  }
Note: See TracChangeset for help on using the changeset viewer.