# HG changeset patch # User Gabor Gevay # Date 1388957096 -3600 # Node ID 0759d974de816af3492dff5e02de2d361ad27841 # Parent 39b6e65574c68620fda4e5faa9bd779c29c62190 STL style iterators (#325) For * graph types, * graph adaptors, * paths, * iterable maps, * LP rows/cols and * active nodes is BellmanFord diff -r 39b6e65574c6 -r 0759d974de81 CMakeLists.txt --- a/CMakeLists.txt Thu Apr 02 22:34:03 2015 +0200 +++ b/CMakeLists.txt Sun Jan 05 22:24:56 2014 +0100 @@ -262,6 +262,14 @@ ENABLE_TESTING() + +INCLUDE(CheckCXXCompilerFlag) +CHECK_CXX_COMPILER_FLAG("-std=c++11" CXX11FLAG) +IF(CXX11FLAG) + SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11") +ENDIF() + + IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer") ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND}) ELSE() diff -r 39b6e65574c6 -r 0759d974de81 lemon/bellman_ford.h --- a/lemon/bellman_ford.h Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/bellman_ford.h Sun Jan 05 22:24:56 2014 +0100 @@ -29,6 +29,7 @@ #include #include #include +#include #include @@ -690,6 +691,21 @@ int _index; }; + /// \brief Gets the collection of the active nodes. + /// + /// This function can be used for iterating on the active nodes of the + /// Bellman-Ford algorithm after the last phase. + /// These nodes should be checked in the next phase to + /// find augmenting arcs outgoing from them. + /// It returns a wrapped ActiveIt, which looks + /// like an STL container (by having begin() and end()) + /// which you can use in range-based for loops, STL algorithms, etc. + LemonRangeWrapper1 + activeNodes(const BellmanFord& algorithm) const { + return LemonRangeWrapper1(algorithm); + } + + /// \name Query Functions /// The result of the Bellman-Ford algorithm can be obtained using these /// functions.\n diff -r 39b6e65574c6 -r 0759d974de81 lemon/bits/graph_adaptor_extender.h --- a/lemon/bits/graph_adaptor_extender.h Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/bits/graph_adaptor_extender.h Sun Jan 05 22:24:56 2014 +0100 @@ -85,6 +85,9 @@ }; + LemonRangeWrapper1 nodes() { + return LemonRangeWrapper1(*this); + } class ArcIt : public Arc { const Adaptor* _adaptor; @@ -108,6 +111,10 @@ }; + LemonRangeWrapper1 arcs() { + return LemonRangeWrapper1(*this); + } + class OutArcIt : public Arc { const Adaptor* _adaptor; @@ -132,6 +139,10 @@ }; + LemonRangeWrapper2 outArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + class InArcIt : public Arc { const Adaptor* _adaptor; @@ -156,6 +167,10 @@ }; + LemonRangeWrapper2 inArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + Node baseNode(const OutArcIt &e) const { return Parent::source(e); } @@ -254,6 +269,10 @@ }; + LemonRangeWrapper1 nodes() { + return LemonRangeWrapper1(*this); + } + class ArcIt : public Arc { const Adaptor* _adaptor; @@ -277,6 +296,10 @@ }; + LemonRangeWrapper1 arcs() { + return LemonRangeWrapper1(*this); + } + class OutArcIt : public Arc { const Adaptor* _adaptor; @@ -301,6 +324,10 @@ }; + LemonRangeWrapper2 outArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + class InArcIt : public Arc { const Adaptor* _adaptor; @@ -325,6 +352,10 @@ }; + LemonRangeWrapper2 inArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + class EdgeIt : public Parent::Edge { const Adaptor* _adaptor; public: @@ -347,6 +378,11 @@ }; + LemonRangeWrapper1 edges() { + return LemonRangeWrapper1(*this); + } + + class IncEdgeIt : public Edge { friend class GraphAdaptorExtender; const Adaptor* _adaptor; @@ -372,6 +408,11 @@ } }; + LemonRangeWrapper2 incEdges(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + + Node baseNode(const OutArcIt &a) const { return Parent::source(a); } diff -r 39b6e65574c6 -r 0759d974de81 lemon/bits/graph_extender.h --- a/lemon/bits/graph_extender.h Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/bits/graph_extender.h Sun Jan 05 22:24:56 2014 +0100 @@ -27,6 +27,8 @@ #include #include +#include + //\ingroup graphbits //\file //\brief Extenders for the graph types @@ -116,6 +118,10 @@ }; + LemonRangeWrapper1 nodes() const { + return LemonRangeWrapper1(*this); + } + class ArcIt : public Arc { const Digraph* _digraph; @@ -139,6 +145,10 @@ }; + LemonRangeWrapper1 arcs() const { + return LemonRangeWrapper1(*this); + } + class OutArcIt : public Arc { const Digraph* _digraph; @@ -163,6 +173,10 @@ }; + LemonRangeWrapper2 outArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + class InArcIt : public Arc { const Digraph* _digraph; @@ -187,6 +201,10 @@ }; + LemonRangeWrapper2 inArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + // \brief Base node of the iterator // // Returns the base node (i.e. the source in this case) of the iterator @@ -436,6 +454,10 @@ }; + LemonRangeWrapper1 nodes() const { + return LemonRangeWrapper1(*this); + } + class ArcIt : public Arc { const Graph* _graph; @@ -459,6 +481,10 @@ }; + LemonRangeWrapper1 arcs() const { + return LemonRangeWrapper1(*this); + } + class OutArcIt : public Arc { const Graph* _graph; @@ -483,6 +509,10 @@ }; + LemonRangeWrapper2 outArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + class InArcIt : public Arc { const Graph* _graph; @@ -507,6 +537,10 @@ }; + LemonRangeWrapper2 inArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + class EdgeIt : public Parent::Edge { const Graph* _graph; @@ -530,6 +564,11 @@ }; + LemonRangeWrapper1 edges() const { + return LemonRangeWrapper1(*this); + } + + class IncEdgeIt : public Parent::Edge { friend class GraphExtender; const Graph* _graph; @@ -555,6 +594,11 @@ } }; + LemonRangeWrapper2 incEdges(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + + // \brief Base node of the iterator // // Returns the base node (ie. the source in this case) of the iterator @@ -903,6 +947,11 @@ }; + LemonRangeWrapper1 nodes() const { + return LemonRangeWrapper1(*this); + } + + class RedNodeIt : public RedNode { const BpGraph* _graph; public: @@ -925,6 +974,11 @@ }; + LemonRangeWrapper1 redNodes() const { + return LemonRangeWrapper1(*this); + } + + class BlueNodeIt : public BlueNode { const BpGraph* _graph; public: @@ -947,6 +1001,11 @@ }; + LemonRangeWrapper1 blueNodes() const { + return LemonRangeWrapper1(*this); + } + + class ArcIt : public Arc { const BpGraph* _graph; @@ -970,6 +1029,10 @@ }; + LemonRangeWrapper1 arcs() const { + return LemonRangeWrapper1(*this); + } + class OutArcIt : public Arc { const BpGraph* _graph; @@ -994,6 +1057,10 @@ }; + LemonRangeWrapper2 outArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + class InArcIt : public Arc { const BpGraph* _graph; @@ -1018,6 +1085,10 @@ }; + LemonRangeWrapper2 inArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + class EdgeIt : public Parent::Edge { const BpGraph* _graph; @@ -1041,6 +1112,11 @@ }; + LemonRangeWrapper1 edges() const { + return LemonRangeWrapper1(*this); + } + + class IncEdgeIt : public Parent::Edge { friend class BpGraphExtender; const BpGraph* _graph; @@ -1066,6 +1142,11 @@ } }; + LemonRangeWrapper2 incEdges(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + + // \brief Base node of the iterator // // Returns the base node (ie. the source in this case) of the iterator diff -r 39b6e65574c6 -r 0759d974de81 lemon/bits/stl_iterators.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/bits/stl_iterators.h Sun Jan 05 22:24:56 2014 +0100 @@ -0,0 +1,99 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + */ + +#ifndef STL_ITERATORS_H_ +#define STL_ITERATORS_H_ + +#include + +namespace lemon { + + /// \brief Template to make STL iterators from Lemon iterators. + /// + /// This template makes an STL iterator from a Lemon iterator + /// by adding the missing features. + /// It inherits from \c std::iterator to make \c iterator_concept work + /// (so that STL algorithms work). + /// \c T should be the lemon iterator to be decorated. + template + struct LemonItWrapper + : public T, public std::iterator { + + LemonItWrapper(const T &x) : T(x) {} + + //Lemon iterators don't have operator*, (because they rather + //inherit from their "value_type"), + //so we add one that just returns the object. + const T& operator*() const { + return static_cast(*this); + } + + //I can't think of any use case for this with Lemon iterators, + //but maybe it should be included for completeness. + const T* operator->() { + return static_cast(this); + } + + //Lemon iterators don't have postincrement. + void operator++(int) { + T::operator++(); + } + + using T::operator++; + + }; + + + /// \brief A generic wrapper for Lemon iterators for range-based for loops. + /// + /// This template can be used to create a class + /// that has begin() and end() from a Lemon iterator + /// (with a 1-parameter constructor) + /// to make range-based for loops and STL algorithms work. + /// + /// \c LIT is the Lemon iterator that will be wrapped + /// \c P is the type of the parameter of the constructor of \c LIT. + template + class LemonRangeWrapper1 { + const P &_p; + typedef LemonItWrapper It; + public: + LemonRangeWrapper1(const P &p) : _p(p) {} + It begin() const { + return It(LIT(_p)); + } + It end() const { + return It(lemon::INVALID); + } + }; + + + /// \brief A generic wrapper for Lemon iterators for range-based for loops. + /// + /// This template can be used to create a class + /// that has begin() and end() from a Lemon iterator + /// (with a 2-parameter constructor) + /// to make range-based for loops and STL algorithms work. + /// + /// \c LIT is the Lemon iterator that will be wrapped + /// \c P1 and \c P2 are the types of the parameters + /// of the constructor of \c LIT. + template + class LemonRangeWrapper2 { + const P1 &_p1; + const P2 &_p2; + typedef LemonItWrapper It; + public: + LemonRangeWrapper2(const P1 &p1, const P2 &p2) : _p1(p1), _p2(p2) {} + It begin() const { + return It(LIT(_p1, _p2)); + } + It end() const { + return It(lemon::INVALID); + } + }; + + +} + +#endif /* STL_ITERATORS_H_ */ diff -r 39b6e65574c6 -r 0759d974de81 lemon/cbc.cc --- a/lemon/cbc.cc Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/cbc.cc Sun Jan 05 22:24:56 2014 +0100 @@ -111,11 +111,11 @@ } void CbcMip::_eraseColId(int i) { - cols.eraseIndex(i); + _cols.eraseIndex(i); } void CbcMip::_eraseRowId(int i) { - rows.eraseIndex(i); + _rows.eraseIndex(i); } void CbcMip::_getColName(int c, std::string& name) const { diff -r 39b6e65574c6 -r 0759d974de81 lemon/clp.cc --- a/lemon/clp.cc Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/clp.cc Sun Jan 05 22:24:56 2014 +0100 @@ -29,8 +29,8 @@ ClpLp::ClpLp(const ClpLp& other) { _prob = new ClpSimplex(*other._prob); - rows = other.rows; - cols = other.cols; + _rows = other._rows; + _cols = other._cols; _init_temporals(); messageLevel(MESSAGE_NOTHING); } @@ -103,13 +103,13 @@ } void ClpLp::_eraseColId(int i) { - cols.eraseIndex(i); - cols.shiftIndices(i); + _cols.eraseIndex(i); + _cols.shiftIndices(i); } void ClpLp::_eraseRowId(int i) { - rows.eraseIndex(i); - rows.shiftIndices(i); + _rows.eraseIndex(i); + _rows.shiftIndices(i); } void ClpLp::_getColName(int c, std::string& name) const { diff -r 39b6e65574c6 -r 0759d974de81 lemon/clp.h --- a/lemon/clp.h Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/clp.h Sun Jan 05 22:24:56 2014 +0100 @@ -151,10 +151,10 @@ SolveExitStatus solveBarrier(); ///Returns the constraint identifier understood by CLP. - int clpRow(Row r) const { return rows(id(r)); } + int clpRow(Row r) const { return _rows(id(r)); } ///Returns the variable identifier understood by CLP. - int clpCol(Col c) const { return cols(id(c)); } + int clpCol(Col c) const { return _cols(id(c)); } }; diff -r 39b6e65574c6 -r 0759d974de81 lemon/concepts/bpgraph.h --- a/lemon/concepts/bpgraph.h Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/concepts/bpgraph.h Sun Jan 05 22:24:56 2014 +0100 @@ -27,6 +27,7 @@ #include #include #include +#include namespace lemon { namespace concepts { @@ -221,6 +222,22 @@ RedNodeIt& operator++() { return *this; } }; + /// \brief Gets the collection of the red nodes of the graph. + /// + /// This function can be used for iterating on + /// the red nodes of the graph. It returns a wrapped RedNodeIt, + /// which looks like an STL container (by having begin() and end()) + /// which you can use in range-based for loops, stl algorithms, etc. + /// For example if g is a BpGraph, you can write: + ///\code + /// for(auto v: g.redNodes()) + /// doSomething(v); + ///\endcode + LemonRangeWrapper1 redNodes() const { + return LemonRangeWrapper1(*this); + } + + /// Iterator class for the blue nodes. /// This iterator goes through each blue node of the graph. @@ -264,6 +281,22 @@ BlueNodeIt& operator++() { return *this; } }; + /// \brief Gets the collection of the blue nodes of the graph. + /// + /// This function can be used for iterating on + /// the blue nodes of the graph. It returns a wrapped BlueNodeIt, + /// which looks like an STL container (by having begin() and end()) + /// which you can use in range-based for loops, stl algorithms, etc. + /// For example if g is a BpGraph, you can write: + ///\code + /// for(auto v: g.blueNodes()) + /// doSomething(v); + ///\endcode + LemonRangeWrapper1 blueNodes() const { + return LemonRangeWrapper1(*this); + } + + /// Iterator class for the nodes. /// This iterator goes through each node of the graph. @@ -307,6 +340,22 @@ NodeIt& operator++() { return *this; } }; + /// \brief Gets the collection of the nodes of the graph. + /// + /// This function can be used for iterating on + /// the nodes of the graph. It returns a wrapped NodeIt, + /// which looks like an STL container (by having begin() and end()) + /// which you can use in range-based for loops, stl algorithms, etc. + /// For example if g is a BpGraph, you can write: + ///\code + /// for(auto v: g.nodes()) + /// doSomething(v); + ///\endcode + LemonRangeWrapper1 nodes() const { + return LemonRangeWrapper1(*this); + } + + /// The edge type of the graph @@ -395,6 +444,23 @@ EdgeIt& operator++() { return *this; } }; + /// \brief Gets the collection of the edges of the graph. + /// + /// This function can be used for iterating on the + /// edges of the graph. It returns a wrapped + /// EdgeIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, stl algorithms, etc. + /// For example if g is a BpGraph, you can write: + ///\code + /// for(auto e: g.edges()) + /// doSomething(e); + ///\endcode + LemonRangeWrapper1 edges() const { + return LemonRangeWrapper1(*this); + } + + /// Iterator class for the incident edges of a node. /// This iterator goes trough the incident undirected edges @@ -443,6 +509,25 @@ IncEdgeIt& operator++() { return *this; } }; + /// \brief Gets the collection of the incident edges + /// of a certain node of the graph. + /// + /// This function can be used for iterating on the + /// incident undirected edges of a certain node of the graph. + /// It returns a wrapped + /// IncEdgeIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, stl algorithms, etc. + /// For example if g is a BpGraph and u is a Node, you can write: + ///\code + /// for(auto e: g.incEdges(u)) + /// doSomething(e); + ///\endcode + LemonRangeWrapper2 incEdges(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + + /// The arc type of the graph /// This class identifies a directed arc of the graph. It also serves @@ -539,6 +624,23 @@ ArcIt& operator++() { return *this; } }; + /// \brief Gets the collection of the directed arcs of the graph. + /// + /// This function can be used for iterating on the + /// arcs of the graph. It returns a wrapped + /// ArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, stl algorithms, etc. + /// For example if g is a BpGraph you can write: + ///\code + /// for(auto a: g.arcs()) + /// doSomething(a); + ///\endcode + LemonRangeWrapper1 arcs() const { + return LemonRangeWrapper1(*this); + } + + /// Iterator class for the outgoing arcs of a node. /// This iterator goes trough the \e outgoing directed arcs of a @@ -587,6 +689,24 @@ OutArcIt& operator++() { return *this; } }; + /// \brief Gets the collection of the outgoing directed arcs of a + /// certain node of the graph. + /// + /// This function can be used for iterating on the + /// outgoing arcs of a certain node of the graph. It returns a wrapped + /// OutArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, stl algorithms, etc. + /// For example if g is a BpGraph and u is a Node, you can write: + ///\code + /// for(auto a: g.outArcs(u)) + /// doSomething(a); + ///\endcode + LemonRangeWrapper2 outArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + + /// Iterator class for the incoming arcs of a node. /// This iterator goes trough the \e incoming directed arcs of a @@ -635,6 +755,24 @@ InArcIt& operator++() { return *this; } }; + /// \brief Gets the collection of the incoming directed arcs of a + /// certain node of the graph. + /// + /// This function can be used for iterating on the + /// incoming arcs of a certain node of the graph. It returns a wrapped + /// InArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, stl algorithms, etc. + /// For example if g is a BpGraph and u is a Node, you can write: + ///\code + /// for(auto a: g.inArcs(u)) + /// doSomething(a); + ///\endcode + LemonRangeWrapper2 inArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + + /// \brief Standard graph map type for the nodes. /// /// Standard graph map type for the nodes. diff -r 39b6e65574c6 -r 0759d974de81 lemon/concepts/digraph.h --- a/lemon/concepts/digraph.h Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/concepts/digraph.h Sun Jan 05 22:24:56 2014 +0100 @@ -27,6 +27,7 @@ #include #include #include +#include namespace lemon { namespace concepts { @@ -147,6 +148,25 @@ NodeIt& operator++() { return *this; } }; + /// \brief Gets the collection of the nodes of the digraph. + /// + /// This function can be used for iterating on + /// the nodes of the digraph. It returns a wrapped NodeIt, which looks + /// like an STL container (by having begin() and end()) + /// which you can use in range-based for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// ListDigraph g; + /// for(auto v: g.nodes()) + /// doSomething(v); + /// + /// //Using an STL algorithm: + /// copy(g.nodes().begin(), g.nodes().end(), vect.begin()); + ///\endcode + LemonRangeWrapper1 nodes() const { + return LemonRangeWrapper1(*this); + } + /// The arc type of the digraph @@ -237,6 +257,27 @@ OutArcIt& operator++() { return *this; } }; + /// \brief Gets the collection of the outgoing arcs of a certain node + /// of the digraph. + /// + /// This function can be used for iterating on the + /// outgoing arcs of a certain node of the digraph. It returns a wrapped + /// OutArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example if g is a Digraph and u is a node, you can write: + ///\code + /// for(auto a: g.outArcs(u)) + /// doSomething(a); + /// + /// //Using an STL algorithm: + /// copy(g.outArcs(u).begin(), g.outArcs(u).end(), vect.begin()); + ///\endcode + LemonRangeWrapper2 outArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + + /// Iterator class for the incoming arcs of a node. /// This iterator goes trough the \e incoming arcs of a certain node @@ -282,6 +323,27 @@ InArcIt& operator++() { return *this; } }; + /// \brief Gets the collection of the incoming arcs of a certain node + /// of the digraph. + /// + /// This function can be used for iterating on the + /// incoming arcs of a certain node of the digraph. It returns a wrapped + /// InArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example if g is a Digraph and u is a node, you can write: + ///\code + /// for(auto a: g.inArcs(u)) + /// doSomething(a); + /// + /// //Using an STL algorithm: + /// copy(g.inArcs(u).begin(), g.inArcs(u).end(), vect.begin()); + ///\endcode + LemonRangeWrapper2 inArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + + /// Iterator class for the arcs. /// This iterator goes through each arc of the digraph. @@ -327,6 +389,27 @@ ArcIt& operator++() { return *this; } }; + /// \brief Gets the collection of the arcs of the digraph. + /// + /// This function can be used for iterating on the + /// arcs of the digraph. It returns a wrapped + /// ArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// ListDigraph g; + /// for(auto a: g.arcs()) + /// doSomething(a); + /// + /// //Using an STL algorithm: + /// copy(g.arcs().begin(), g.arcs().end(), vect.begin()); + ///\endcode + LemonRangeWrapper1 arcs() const { + return LemonRangeWrapper1(*this); + } + + /// \brief The source node of the arc. /// /// Returns the source node of the given arc. diff -r 39b6e65574c6 -r 0759d974de81 lemon/concepts/graph.h --- a/lemon/concepts/graph.h Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/concepts/graph.h Sun Jan 05 22:24:56 2014 +0100 @@ -27,6 +27,7 @@ #include #include #include +#include namespace lemon { namespace concepts { @@ -180,6 +181,25 @@ NodeIt& operator++() { return *this; } }; + /// \brief Gets the collection of the nodes of the graph. + /// + /// This function can be used for iterating on + /// the nodes of the graph. It returns a wrapped NodeIt, which looks + /// like an STL container (by having begin() and end()) + /// which you can use in range-based for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// ListGraph g; + /// for(auto v: g.nodes()) + /// doSomething(v); + /// + /// //Using an STL algorithm: + /// copy(g.nodes().begin(), g.nodes().end(), vect.begin()); + ///\endcode + LemonRangeWrapper1 nodes() const { + return LemonRangeWrapper1(*this); + } + /// The edge type of the graph @@ -268,6 +288,27 @@ EdgeIt& operator++() { return *this; } }; + /// \brief Gets the collection of the edges of the graph. + /// + /// This function can be used for iterating on the + /// edges of the graph. It returns a wrapped + /// EdgeIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// ListGraph g; + /// for(auto e: g.edges()) + /// doSomething(e); + /// + /// //Using an STL algorithm: + /// copy(g.edges().begin(), g.edges().end(), vect.begin()); + ///\endcode + LemonRangeWrapper1 edges() const { + return LemonRangeWrapper1(*this); + } + + /// Iterator class for the incident edges of a node. /// This iterator goes trough the incident undirected edges @@ -316,6 +357,28 @@ IncEdgeIt& operator++() { return *this; } }; + /// \brief Gets the collection of the incident undirected edges + /// of a certain node of the graph. + /// + /// This function can be used for iterating on the + /// incident undirected edges of a certain node of the graph. + /// It returns a wrapped + /// IncEdgeIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example if g is a Graph and u is a Node, you can write: + ///\code + /// for(auto e: g.incEdges(u)) + /// doSomething(e); + /// + /// //Using an STL algorithm: + /// copy(g.incEdges(u).begin(), g.incEdges(u).end(), vect.begin()); + ///\endcode + LemonRangeWrapper2 incEdges(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + + /// The arc type of the graph /// This class identifies a directed arc of the graph. It also serves @@ -411,6 +474,27 @@ ArcIt& operator++() { return *this; } }; + /// \brief Gets the collection of the directed arcs of the graph. + /// + /// This function can be used for iterating on the + /// arcs of the graph. It returns a wrapped + /// ArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// ListGraph g; + /// for(auto a: g.arcs()) + /// doSomething(a); + /// + /// //Using an STL algorithm: + /// copy(g.arcs().begin(), g.arcs().end(), vect.begin()); + ///\endcode + LemonRangeWrapper1 arcs() const { + return LemonRangeWrapper1(*this); + } + + /// Iterator class for the outgoing arcs of a node. /// This iterator goes trough the \e outgoing directed arcs of a @@ -459,6 +543,27 @@ OutArcIt& operator++() { return *this; } }; + /// \brief Gets the collection of the outgoing directed arcs of a + /// certain node of the graph. + /// + /// This function can be used for iterating on the + /// outgoing arcs of a certain node of the graph. It returns a wrapped + /// OutArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example if g is a Graph and u is a Node, you can write: + ///\code + /// for(auto a: g.outArcs(u)) + /// doSomething(a); + /// + /// //Using an STL algorithm: + /// copy(g.outArcs(u).begin(), g.outArcs(u).end(), vect.begin()); + ///\endcode + LemonRangeWrapper2 outArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + + /// Iterator class for the incoming arcs of a node. /// This iterator goes trough the \e incoming directed arcs of a @@ -507,6 +612,26 @@ InArcIt& operator++() { return *this; } }; + /// \brief Gets the collection of the incoming directed arcs of + /// a certain node of the graph. + /// + /// This function can be used for iterating on the + /// incoming directed arcs of a certain node of the graph. It returns + /// a wrapped InArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example if g is a Graph and u is a Node, you can write: + ///\code + /// for(auto a: g.inArcs(u)) + /// doSomething(a); + /// + /// //Using an STL algorithm: + /// copy(g.inArcs(u).begin(), g.inArcs(u).end(), vect.begin()); + ///\endcode + LemonRangeWrapper2 inArcs(const Node& u) const { + return LemonRangeWrapper2(*this, u); + } + /// \brief Standard graph map type for the nodes. /// /// Standard graph map type for the nodes. diff -r 39b6e65574c6 -r 0759d974de81 lemon/concepts/path.h --- a/lemon/concepts/path.h Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/concepts/path.h Sun Jan 05 22:24:56 2014 +0100 @@ -26,6 +26,7 @@ #include #include +#include namespace lemon { namespace concepts { @@ -115,6 +116,23 @@ }; + /// \brief Gets the collection of the arcs of the path. + /// + /// This function can be used for iterating on the + /// arcs of the path. It returns a wrapped + /// ArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// for(auto a: p.arcs()) + /// doSomething(a); + ///\endcode + LemonRangeWrapper1 arcs() const { + return LemonRangeWrapper1(*this); + } + + template struct Constraints { void constraints() { @@ -264,6 +282,23 @@ }; + /// \brief Gets the collection of the arcs of the path. + /// + /// This function can be used for iterating on the + /// arcs of the path. It returns a wrapped + /// ArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// for(auto a: p.arcs()) + /// doSomething(a); + ///\endcode + LemonRangeWrapper1 arcs() const { + return LemonRangeWrapper1(*this); + } + + /// \brief LEMON style iterator for enumerating the arcs of a path /// in reverse direction. /// @@ -293,6 +328,24 @@ }; + /// \brief Gets the collection of the arcs of the path + /// in reverse direction. + /// + /// This function can be used for iterating on the + /// arcs of the path in reverse direction. It returns a wrapped + /// RevArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// for(auto a: p.revArcs()) + /// doSomething(a); + ///\endcode + LemonRangeWrapper1 revArcs() const { + return LemonRangeWrapper1(*this); + } + + template struct Constraints { void constraints() { diff -r 39b6e65574c6 -r 0759d974de81 lemon/cplex.cc --- a/lemon/cplex.cc Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/cplex.cc Sun Jan 05 22:24:56 2014 +0100 @@ -87,8 +87,8 @@ : LpBase() { int status; _prob = CPXcloneprob(cplexEnv(), cplex._prob, &status); - rows = cplex.rows; - cols = cplex.cols; + _rows = cplex._rows; + _cols = cplex._cols; messageLevel(MESSAGE_NOTHING); } @@ -158,12 +158,12 @@ } void CplexBase::_eraseColId(int i) { - cols.eraseIndex(i); - cols.shiftIndices(i); + _cols.eraseIndex(i); + _cols.shiftIndices(i); } void CplexBase::_eraseRowId(int i) { - rows.eraseIndex(i); - rows.shiftIndices(i); + _rows.eraseIndex(i); + _rows.shiftIndices(i); } void CplexBase::_getColName(int col, std::string &name) const { diff -r 39b6e65574c6 -r 0759d974de81 lemon/glpk.cc --- a/lemon/glpk.cc Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/glpk.cc Sun Jan 05 22:24:56 2014 +0100 @@ -38,8 +38,8 @@ lp = glp_create_prob(); glp_copy_prob(lp, other.lp, GLP_ON); glp_create_index(lp); - rows = other.rows; - cols = other.cols; + _rows = other._rows; + _cols = other._cols; messageLevel(MESSAGE_NOTHING); } @@ -108,13 +108,13 @@ } void GlpkBase::_eraseColId(int i) { - cols.eraseIndex(i); - cols.shiftIndices(i); + _cols.eraseIndex(i); + _cols.shiftIndices(i); } void GlpkBase::_eraseRowId(int i) { - rows.eraseIndex(i); - rows.shiftIndices(i); + _rows.eraseIndex(i); + _rows.shiftIndices(i); } void GlpkBase::_getColName(int c, std::string& name) const { diff -r 39b6e65574c6 -r 0759d974de81 lemon/glpk.h --- a/lemon/glpk.h Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/glpk.h Sun Jan 05 22:24:56 2014 +0100 @@ -141,10 +141,10 @@ _solver_bits::VoidPtr lpx() const {return lp;} ///Returns the constraint identifier understood by GLPK. - int lpxRow(Row r) const { return rows(id(r)); } + int lpxRow(Row r) const { return _rows(id(r)); } ///Returns the variable identifier understood by GLPK. - int lpxCol(Col c) const { return cols(id(c)); } + int lpxCol(Col c) const { return _cols(id(c)); } #ifdef DOXYGEN /// Write the problem or the solution to a file in the given format diff -r 39b6e65574c6 -r 0759d974de81 lemon/list_graph.h --- a/lemon/list_graph.h Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/list_graph.h Sun Jan 05 22:24:56 2014 +0100 @@ -48,13 +48,13 @@ int next_in, next_out; }; - std::vector nodes; + std::vector _nodes; int first_node; int first_free_node; - std::vector arcs; + std::vector _arcs; int first_free_arc; @@ -97,15 +97,15 @@ ListDigraphBase() - : nodes(), first_node(-1), - first_free_node(-1), arcs(), first_free_arc(-1) {} - - - int maxNodeId() const { return nodes.size()-1; } - int maxArcId() const { return arcs.size()-1; } - - Node source(Arc e) const { return Node(arcs[e.id].source); } - Node target(Arc e) const { return Node(arcs[e.id].target); } + : _nodes(), first_node(-1), + first_free_node(-1), _arcs(), first_free_arc(-1) {} + + + int maxNodeId() const { return _nodes.size()-1; } + int maxArcId() const { return _arcs.size()-1; } + + Node source(Arc e) const { return Node(_arcs[e.id].source); } + Node target(Arc e) const { return Node(_arcs[e.id].target); } void first(Node& node) const { @@ -113,42 +113,42 @@ } void next(Node& node) const { - node.id = nodes[node.id].next; + node.id = _nodes[node.id].next; } void first(Arc& arc) const { int n; for(n = first_node; - n != -1 && nodes[n].first_out == -1; - n = nodes[n].next) {} - arc.id = (n == -1) ? -1 : nodes[n].first_out; + n != -1 && _nodes[n].first_out == -1; + n = _nodes[n].next) {} + arc.id = (n == -1) ? -1 : _nodes[n].first_out; } void next(Arc& arc) const { - if (arcs[arc.id].next_out != -1) { - arc.id = arcs[arc.id].next_out; + if (_arcs[arc.id].next_out != -1) { + arc.id = _arcs[arc.id].next_out; } else { int n; - for(n = nodes[arcs[arc.id].source].next; - n != -1 && nodes[n].first_out == -1; - n = nodes[n].next) {} - arc.id = (n == -1) ? -1 : nodes[n].first_out; + for(n = _nodes[_arcs[arc.id].source].next; + n != -1 && _nodes[n].first_out == -1; + n = _nodes[n].next) {} + arc.id = (n == -1) ? -1 : _nodes[n].first_out; } } void firstOut(Arc &e, const Node& v) const { - e.id = nodes[v.id].first_out; + e.id = _nodes[v.id].first_out; } void nextOut(Arc &e) const { - e.id=arcs[e.id].next_out; + e.id=_arcs[e.id].next_out; } void firstIn(Arc &e, const Node& v) const { - e.id = nodes[v.id].first_in; + e.id = _nodes[v.id].first_in; } void nextIn(Arc &e) const { - e.id=arcs[e.id].next_in; + e.id=_arcs[e.id].next_in; } @@ -159,32 +159,32 @@ static Arc arcFromId(int id) { return Arc(id);} bool valid(Node n) const { - return n.id >= 0 && n.id < static_cast(nodes.size()) && - nodes[n.id].prev != -2; + return n.id >= 0 && n.id < static_cast(_nodes.size()) && + _nodes[n.id].prev != -2; } bool valid(Arc a) const { - return a.id >= 0 && a.id < static_cast(arcs.size()) && - arcs[a.id].prev_in != -2; + return a.id >= 0 && a.id < static_cast(_arcs.size()) && + _arcs[a.id].prev_in != -2; } Node addNode() { int n; if(first_free_node==-1) { - n = nodes.size(); - nodes.push_back(NodeT()); + n = _nodes.size(); + _nodes.push_back(NodeT()); } else { n = first_free_node; - first_free_node = nodes[n].next; + first_free_node = _nodes[n].next; } - nodes[n].next = first_node; - if(first_node != -1) nodes[first_node].prev = n; + _nodes[n].next = first_node; + if(first_node != -1) _nodes[first_node].prev = n; first_node = n; - nodes[n].prev = -1; - - nodes[n].first_in = nodes[n].first_out = -1; + _nodes[n].prev = -1; + + _nodes[n].first_in = _nodes[n].first_out = -1; return Node(n); } @@ -193,29 +193,29 @@ int n; if (first_free_arc == -1) { - n = arcs.size(); - arcs.push_back(ArcT()); + n = _arcs.size(); + _arcs.push_back(ArcT()); } else { n = first_free_arc; - first_free_arc = arcs[n].next_in; + first_free_arc = _arcs[n].next_in; } - arcs[n].source = u.id; - arcs[n].target = v.id; - - arcs[n].next_out = nodes[u.id].first_out; - if(nodes[u.id].first_out != -1) { - arcs[nodes[u.id].first_out].prev_out = n; + _arcs[n].source = u.id; + _arcs[n].target = v.id; + + _arcs[n].next_out = _nodes[u.id].first_out; + if(_nodes[u.id].first_out != -1) { + _arcs[_nodes[u.id].first_out].prev_out = n; } - arcs[n].next_in = nodes[v.id].first_in; - if(nodes[v.id].first_in != -1) { - arcs[nodes[v.id].first_in].prev_in = n; + _arcs[n].next_in = _nodes[v.id].first_in; + if(_nodes[v.id].first_in != -1) { + _arcs[_nodes[v.id].first_in].prev_in = n; } - arcs[n].prev_in = arcs[n].prev_out = -1; - - nodes[u.id].first_out = nodes[v.id].first_in = n; + _arcs[n].prev_in = _arcs[n].prev_out = -1; + + _nodes[u.id].first_out = _nodes[v.id].first_in = n; return Arc(n); } @@ -223,87 +223,87 @@ void erase(const Node& node) { int n = node.id; - if(nodes[n].next != -1) { - nodes[nodes[n].next].prev = nodes[n].prev; + if(_nodes[n].next != -1) { + _nodes[_nodes[n].next].prev = _nodes[n].prev; } - if(nodes[n].prev != -1) { - nodes[nodes[n].prev].next = nodes[n].next; + if(_nodes[n].prev != -1) { + _nodes[_nodes[n].prev].next = _nodes[n].next; } else { - first_node = nodes[n].next; + first_node = _nodes[n].next; } - nodes[n].next = first_free_node; + _nodes[n].next = first_free_node; first_free_node = n; - nodes[n].prev = -2; + _nodes[n].prev = -2; } void erase(const Arc& arc) { int n = arc.id; - if(arcs[n].next_in!=-1) { - arcs[arcs[n].next_in].prev_in = arcs[n].prev_in; + if(_arcs[n].next_in!=-1) { + _arcs[_arcs[n].next_in].prev_in = _arcs[n].prev_in; } - if(arcs[n].prev_in!=-1) { - arcs[arcs[n].prev_in].next_in = arcs[n].next_in; + if(_arcs[n].prev_in!=-1) { + _arcs[_arcs[n].prev_in].next_in = _arcs[n].next_in; } else { - nodes[arcs[n].target].first_in = arcs[n].next_in; + _nodes[_arcs[n].target].first_in = _arcs[n].next_in; } - if(arcs[n].next_out!=-1) { - arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; + if(_arcs[n].next_out!=-1) { + _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out; } - if(arcs[n].prev_out!=-1) { - arcs[arcs[n].prev_out].next_out = arcs[n].next_out; + if(_arcs[n].prev_out!=-1) { + _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out; } else { - nodes[arcs[n].source].first_out = arcs[n].next_out; + _nodes[_arcs[n].source].first_out = _arcs[n].next_out; } - arcs[n].next_in = first_free_arc; + _arcs[n].next_in = first_free_arc; first_free_arc = n; - arcs[n].prev_in = -2; + _arcs[n].prev_in = -2; } void clear() { - arcs.clear(); - nodes.clear(); + _arcs.clear(); + _nodes.clear(); first_node = first_free_node = first_free_arc = -1; } protected: void changeTarget(Arc e, Node n) { - if(arcs[e.id].next_in != -1) - arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in; - if(arcs[e.id].prev_in != -1) - arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in; - else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in; - if (nodes[n.id].first_in != -1) { - arcs[nodes[n.id].first_in].prev_in = e.id; + if(_arcs[e.id].next_in != -1) + _arcs[_arcs[e.id].next_in].prev_in = _arcs[e.id].prev_in; + if(_arcs[e.id].prev_in != -1) + _arcs[_arcs[e.id].prev_in].next_in = _arcs[e.id].next_in; + else _nodes[_arcs[e.id].target].first_in = _arcs[e.id].next_in; + if (_nodes[n.id].first_in != -1) { + _arcs[_nodes[n.id].first_in].prev_in = e.id; } - arcs[e.id].target = n.id; - arcs[e.id].prev_in = -1; - arcs[e.id].next_in = nodes[n.id].first_in; - nodes[n.id].first_in = e.id; + _arcs[e.id].target = n.id; + _arcs[e.id].prev_in = -1; + _arcs[e.id].next_in = _nodes[n.id].first_in; + _nodes[n.id].first_in = e.id; } void changeSource(Arc e, Node n) { - if(arcs[e.id].next_out != -1) - arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out; - if(arcs[e.id].prev_out != -1) - arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out; - else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out; - if (nodes[n.id].first_out != -1) { - arcs[nodes[n.id].first_out].prev_out = e.id; + if(_arcs[e.id].next_out != -1) + _arcs[_arcs[e.id].next_out].prev_out = _arcs[e.id].prev_out; + if(_arcs[e.id].prev_out != -1) + _arcs[_arcs[e.id].prev_out].next_out = _arcs[e.id].next_out; + else _nodes[_arcs[e.id].source].first_out = _arcs[e.id].next_out; + if (_nodes[n.id].first_out != -1) { + _arcs[_nodes[n.id].first_out].prev_out = e.id; } - arcs[e.id].source = n.id; - arcs[e.id].prev_out = -1; - arcs[e.id].next_out = nodes[n.id].first_out; - nodes[n.id].first_out = e.id; + _arcs[e.id].source = n.id; + _arcs[e.id].prev_out = -1; + _arcs[e.id].next_out = _nodes[n.id].first_out; + _nodes[n.id].first_out = e.id; } }; @@ -486,10 +486,10 @@ ///Snapshot feature. Node split(Node n, bool connect = true) { Node b = addNode(); - nodes[b.id].first_out=nodes[n.id].first_out; - nodes[n.id].first_out=-1; - for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) { - arcs[i].source=b.id; + _nodes[b.id].first_out=_nodes[n.id].first_out; + _nodes[n.id].first_out=-1; + for(int i=_nodes[b.id].first_out; i!=-1; i=_arcs[i].next_out) { + _arcs[i].source=b.id; } if (connect) addArc(n,b); return b; @@ -532,7 +532,7 @@ /// then it is worth reserving space for this amount before starting /// to build the digraph. /// \sa reserveArc() - void reserveNode(int n) { nodes.reserve(n); }; + void reserveNode(int n) { _nodes.reserve(n); }; /// Reserve memory for arcs. @@ -542,7 +542,7 @@ /// then it is worth reserving space for this amount before starting /// to build the digraph. /// \sa reserveNode() - void reserveArc(int m) { arcs.reserve(m); }; + void reserveArc(int m) { _arcs.reserve(m); }; /// \brief Class to make a snapshot of the digraph and restore /// it later. @@ -803,13 +803,13 @@ int prev_out, next_out; }; - std::vector nodes; + std::vector _nodes; int first_node; int first_free_node; - std::vector arcs; + std::vector _arcs; int first_free_arc; @@ -867,19 +867,19 @@ }; ListGraphBase() - : nodes(), first_node(-1), - first_free_node(-1), arcs(), first_free_arc(-1) {} - - - int maxNodeId() const { return nodes.size()-1; } - int maxEdgeId() const { return arcs.size() / 2 - 1; } - int maxArcId() const { return arcs.size()-1; } - - Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); } - Node target(Arc e) const { return Node(arcs[e.id].target); } - - Node u(Edge e) const { return Node(arcs[2 * e.id].target); } - Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); } + : _nodes(), first_node(-1), + first_free_node(-1), _arcs(), first_free_arc(-1) {} + + + int maxNodeId() const { return _nodes.size()-1; } + int maxEdgeId() const { return _arcs.size() / 2 - 1; } + int maxArcId() const { return _arcs.size()-1; } + + Node source(Arc e) const { return Node(_arcs[e.id ^ 1].target); } + Node target(Arc e) const { return Node(_arcs[e.id].target); } + + Node u(Edge e) const { return Node(_arcs[2 * e.id].target); } + Node v(Edge e) const { return Node(_arcs[2 * e.id + 1].target); } static bool direction(Arc e) { return (e.id & 1) == 1; @@ -894,88 +894,88 @@ } void next(Node& node) const { - node.id = nodes[node.id].next; + node.id = _nodes[node.id].next; } void first(Arc& e) const { int n = first_node; - while (n != -1 && nodes[n].first_out == -1) { - n = nodes[n].next; + while (n != -1 && _nodes[n].first_out == -1) { + n = _nodes[n].next; } - e.id = (n == -1) ? -1 : nodes[n].first_out; + e.id = (n == -1) ? -1 : _nodes[n].first_out; } void next(Arc& e) const { - if (arcs[e.id].next_out != -1) { - e.id = arcs[e.id].next_out; + if (_arcs[e.id].next_out != -1) { + e.id = _arcs[e.id].next_out; } else { - int n = nodes[arcs[e.id ^ 1].target].next; - while(n != -1 && nodes[n].first_out == -1) { - n = nodes[n].next; + int n = _nodes[_arcs[e.id ^ 1].target].next; + while(n != -1 && _nodes[n].first_out == -1) { + n = _nodes[n].next; } - e.id = (n == -1) ? -1 : nodes[n].first_out; + e.id = (n == -1) ? -1 : _nodes[n].first_out; } } void first(Edge& e) const { int n = first_node; while (n != -1) { - e.id = nodes[n].first_out; + e.id = _nodes[n].first_out; while ((e.id & 1) != 1) { - e.id = arcs[e.id].next_out; + e.id = _arcs[e.id].next_out; } if (e.id != -1) { e.id /= 2; return; } - n = nodes[n].next; + n = _nodes[n].next; } e.id = -1; } void next(Edge& e) const { - int n = arcs[e.id * 2].target; - e.id = arcs[(e.id * 2) | 1].next_out; + int n = _arcs[e.id * 2].target; + e.id = _arcs[(e.id * 2) | 1].next_out; while ((e.id & 1) != 1) { - e.id = arcs[e.id].next_out; + e.id = _arcs[e.id].next_out; } if (e.id != -1) { e.id /= 2; return; } - n = nodes[n].next; + n = _nodes[n].next; while (n != -1) { - e.id = nodes[n].first_out; + e.id = _nodes[n].first_out; while ((e.id & 1) != 1) { - e.id = arcs[e.id].next_out; + e.id = _arcs[e.id].next_out; } if (e.id != -1) { e.id /= 2; return; } - n = nodes[n].next; + n = _nodes[n].next; } e.id = -1; } void firstOut(Arc &e, const Node& v) const { - e.id = nodes[v.id].first_out; + e.id = _nodes[v.id].first_out; } void nextOut(Arc &e) const { - e.id = arcs[e.id].next_out; + e.id = _arcs[e.id].next_out; } void firstIn(Arc &e, const Node& v) const { - e.id = ((nodes[v.id].first_out) ^ 1); + e.id = ((_nodes[v.id].first_out) ^ 1); if (e.id == -2) e.id = -1; } void nextIn(Arc &e) const { - e.id = ((arcs[e.id ^ 1].next_out) ^ 1); + e.id = ((_arcs[e.id ^ 1].next_out) ^ 1); if (e.id == -2) e.id = -1; } void firstInc(Edge &e, bool& d, const Node& v) const { - int a = nodes[v.id].first_out; + int a = _nodes[v.id].first_out; if (a != -1 ) { e.id = a / 2; d = ((a & 1) == 1); @@ -985,7 +985,7 @@ } } void nextInc(Edge &e, bool& d) const { - int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out); + int a = (_arcs[(e.id * 2) | (d ? 1 : 0)].next_out); if (a != -1 ) { e.id = a / 2; d = ((a & 1) == 1); @@ -1004,37 +1004,37 @@ static Edge edgeFromId(int id) { return Edge(id);} bool valid(Node n) const { - return n.id >= 0 && n.id < static_cast(nodes.size()) && - nodes[n.id].prev != -2; + return n.id >= 0 && n.id < static_cast(_nodes.size()) && + _nodes[n.id].prev != -2; } bool valid(Arc a) const { - return a.id >= 0 && a.id < static_cast(arcs.size()) && - arcs[a.id].prev_out != -2; + return a.id >= 0 && a.id < static_cast(_arcs.size()) && + _arcs[a.id].prev_out != -2; } bool valid(Edge e) const { - return e.id >= 0 && 2 * e.id < static_cast(arcs.size()) && - arcs[2 * e.id].prev_out != -2; + return e.id >= 0 && 2 * e.id < static_cast(_arcs.size()) && + _arcs[2 * e.id].prev_out != -2; } Node addNode() { int n; if(first_free_node==-1) { - n = nodes.size(); - nodes.push_back(NodeT()); + n = _nodes.size(); + _nodes.push_back(NodeT()); } else { n = first_free_node; - first_free_node = nodes[n].next; + first_free_node = _nodes[n].next; } - nodes[n].next = first_node; - if (first_node != -1) nodes[first_node].prev = n; + _nodes[n].next = first_node; + if (first_node != -1) _nodes[first_node].prev = n; first_node = n; - nodes[n].prev = -1; - - nodes[n].first_out = -1; + _nodes[n].prev = -1; + + _nodes[n].first_out = -1; return Node(n); } @@ -1043,30 +1043,30 @@ int n; if (first_free_arc == -1) { - n = arcs.size(); - arcs.push_back(ArcT()); - arcs.push_back(ArcT()); + n = _arcs.size(); + _arcs.push_back(ArcT()); + _arcs.push_back(ArcT()); } else { n = first_free_arc; - first_free_arc = arcs[n].next_out; + first_free_arc = _arcs[n].next_out; } - arcs[n].target = u.id; - arcs[n | 1].target = v.id; - - arcs[n].next_out = nodes[v.id].first_out; - if (nodes[v.id].first_out != -1) { - arcs[nodes[v.id].first_out].prev_out = n; + _arcs[n].target = u.id; + _arcs[n | 1].target = v.id; + + _arcs[n].next_out = _nodes[v.id].first_out; + if (_nodes[v.id].first_out != -1) { + _arcs[_nodes[v.id].first_out].prev_out = n; } - arcs[n].prev_out = -1; - nodes[v.id].first_out = n; - - arcs[n | 1].next_out = nodes[u.id].first_out; - if (nodes[u.id].first_out != -1) { - arcs[nodes[u.id].first_out].prev_out = (n | 1); + _arcs[n].prev_out = -1; + _nodes[v.id].first_out = n; + + _arcs[n | 1].next_out = _nodes[u.id].first_out; + if (_nodes[u.id].first_out != -1) { + _arcs[_nodes[u.id].first_out].prev_out = (n | 1); } - arcs[n | 1].prev_out = -1; - nodes[u.id].first_out = (n | 1); + _arcs[n | 1].prev_out = -1; + _nodes[u.id].first_out = (n | 1); return Edge(n / 2); } @@ -1074,100 +1074,100 @@ void erase(const Node& node) { int n = node.id; - if(nodes[n].next != -1) { - nodes[nodes[n].next].prev = nodes[n].prev; + if(_nodes[n].next != -1) { + _nodes[_nodes[n].next].prev = _nodes[n].prev; } - if(nodes[n].prev != -1) { - nodes[nodes[n].prev].next = nodes[n].next; + if(_nodes[n].prev != -1) { + _nodes[_nodes[n].prev].next = _nodes[n].next; } else { - first_node = nodes[n].next; + first_node = _nodes[n].next; } - nodes[n].next = first_free_node; + _nodes[n].next = first_free_node; first_free_node = n; - nodes[n].prev = -2; + _nodes[n].prev = -2; } void erase(const Edge& edge) { int n = edge.id * 2; - if (arcs[n].next_out != -1) { - arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; + if (_arcs[n].next_out != -1) { + _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out; } - if (arcs[n].prev_out != -1) { - arcs[arcs[n].prev_out].next_out = arcs[n].next_out; + if (_arcs[n].prev_out != -1) { + _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out; } else { - nodes[arcs[n | 1].target].first_out = arcs[n].next_out; + _nodes[_arcs[n | 1].target].first_out = _arcs[n].next_out; } - if (arcs[n | 1].next_out != -1) { - arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out; + if (_arcs[n | 1].next_out != -1) { + _arcs[_arcs[n | 1].next_out].prev_out = _arcs[n | 1].prev_out; } - if (arcs[n | 1].prev_out != -1) { - arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out; + if (_arcs[n | 1].prev_out != -1) { + _arcs[_arcs[n | 1].prev_out].next_out = _arcs[n | 1].next_out; } else { - nodes[arcs[n].target].first_out = arcs[n | 1].next_out; + _nodes[_arcs[n].target].first_out = _arcs[n | 1].next_out; } - arcs[n].next_out = first_free_arc; + _arcs[n].next_out = first_free_arc; first_free_arc = n; - arcs[n].prev_out = -2; - arcs[n | 1].prev_out = -2; + _arcs[n].prev_out = -2; + _arcs[n | 1].prev_out = -2; } void clear() { - arcs.clear(); - nodes.clear(); + _arcs.clear(); + _nodes.clear(); first_node = first_free_node = first_free_arc = -1; } protected: void changeV(Edge e, Node n) { - if(arcs[2 * e.id].next_out != -1) { - arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out; + if(_arcs[2 * e.id].next_out != -1) { + _arcs[_arcs[2 * e.id].next_out].prev_out = _arcs[2 * e.id].prev_out; } - if(arcs[2 * e.id].prev_out != -1) { - arcs[arcs[2 * e.id].prev_out].next_out = - arcs[2 * e.id].next_out; + if(_arcs[2 * e.id].prev_out != -1) { + _arcs[_arcs[2 * e.id].prev_out].next_out = + _arcs[2 * e.id].next_out; } else { - nodes[arcs[(2 * e.id) | 1].target].first_out = - arcs[2 * e.id].next_out; + _nodes[_arcs[(2 * e.id) | 1].target].first_out = + _arcs[2 * e.id].next_out; } - if (nodes[n.id].first_out != -1) { - arcs[nodes[n.id].first_out].prev_out = 2 * e.id; + if (_nodes[n.id].first_out != -1) { + _arcs[_nodes[n.id].first_out].prev_out = 2 * e.id; } - arcs[(2 * e.id) | 1].target = n.id; - arcs[2 * e.id].prev_out = -1; - arcs[2 * e.id].next_out = nodes[n.id].first_out; - nodes[n.id].first_out = 2 * e.id; + _arcs[(2 * e.id) | 1].target = n.id; + _arcs[2 * e.id].prev_out = -1; + _arcs[2 * e.id].next_out = _nodes[n.id].first_out; + _nodes[n.id].first_out = 2 * e.id; } void changeU(Edge e, Node n) { - if(arcs[(2 * e.id) | 1].next_out != -1) { - arcs[arcs[(2 * e.id) | 1].next_out].prev_out = - arcs[(2 * e.id) | 1].prev_out; + if(_arcs[(2 * e.id) | 1].next_out != -1) { + _arcs[_arcs[(2 * e.id) | 1].next_out].prev_out = + _arcs[(2 * e.id) | 1].prev_out; } - if(arcs[(2 * e.id) | 1].prev_out != -1) { - arcs[arcs[(2 * e.id) | 1].prev_out].next_out = - arcs[(2 * e.id) | 1].next_out; + if(_arcs[(2 * e.id) | 1].prev_out != -1) { + _arcs[_arcs[(2 * e.id) | 1].prev_out].next_out = + _arcs[(2 * e.id) | 1].next_out; } else { - nodes[arcs[2 * e.id].target].first_out = - arcs[(2 * e.id) | 1].next_out; + _nodes[_arcs[2 * e.id].target].first_out = + _arcs[(2 * e.id) | 1].next_out; } - if (nodes[n.id].first_out != -1) { - arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1); + if (_nodes[n.id].first_out != -1) { + _arcs[_nodes[n.id].first_out].prev_out = ((2 * e.id) | 1); } - arcs[2 * e.id].target = n.id; - arcs[(2 * e.id) | 1].prev_out = -1; - arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out; - nodes[n.id].first_out = ((2 * e.id) | 1); + _arcs[2 * e.id].target = n.id; + _arcs[(2 * e.id) | 1].prev_out = -1; + _arcs[(2 * e.id) | 1].next_out = _nodes[n.id].first_out; + _nodes[n.id].first_out = ((2 * e.id) | 1); } }; @@ -1344,7 +1344,7 @@ /// then it is worth reserving space for this amount before starting /// to build the graph. /// \sa reserveEdge() - void reserveNode(int n) { nodes.reserve(n); }; + void reserveNode(int n) { _nodes.reserve(n); }; /// Reserve memory for edges. @@ -1354,7 +1354,7 @@ /// then it is worth reserving space for this amount before starting /// to build the graph. /// \sa reserveNode() - void reserveEdge(int m) { arcs.reserve(2 * m); }; + void reserveEdge(int m) { _arcs.reserve(2 * m); }; /// \brief Class to make a snapshot of the graph and restore /// it later. @@ -1617,14 +1617,14 @@ int prev_out, next_out; }; - std::vector nodes; + std::vector _nodes; int first_node, first_red, first_blue; int max_red, max_blue; int first_free_red, first_free_blue; - std::vector arcs; + std::vector _arcs; int first_free_arc; @@ -1706,33 +1706,33 @@ }; ListBpGraphBase() - : nodes(), first_node(-1), + : _nodes(), first_node(-1), first_red(-1), first_blue(-1), max_red(-1), max_blue(-1), first_free_red(-1), first_free_blue(-1), - arcs(), first_free_arc(-1) {} - - - bool red(Node n) const { return nodes[n.id].red; } - bool blue(Node n) const { return !nodes[n.id].red; } + _arcs(), first_free_arc(-1) {} + + + bool red(Node n) const { return _nodes[n.id].red; } + bool blue(Node n) const { return !_nodes[n.id].red; } static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); } static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); } - int maxNodeId() const { return nodes.size()-1; } + int maxNodeId() const { return _nodes.size()-1; } int maxRedId() const { return max_red; } int maxBlueId() const { return max_blue; } - int maxEdgeId() const { return arcs.size() / 2 - 1; } - int maxArcId() const { return arcs.size()-1; } - - Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); } - Node target(Arc e) const { return Node(arcs[e.id].target); } + int maxEdgeId() const { return _arcs.size() / 2 - 1; } + int maxArcId() const { return _arcs.size()-1; } + + Node source(Arc e) const { return Node(_arcs[e.id ^ 1].target); } + Node target(Arc e) const { return Node(_arcs[e.id].target); } RedNode redNode(Edge e) const { - return RedNode(arcs[2 * e.id].target); + return RedNode(_arcs[2 * e.id].target); } BlueNode blueNode(Edge e) const { - return BlueNode(arcs[2 * e.id + 1].target); + return BlueNode(_arcs[2 * e.id + 1].target); } static bool direction(Arc e) { @@ -1748,7 +1748,7 @@ } void next(Node& node) const { - node.id = nodes[node.id].next; + node.id = _nodes[node.id].next; } void first(RedNode& node) const { @@ -1756,7 +1756,7 @@ } void next(RedNode& node) const { - node.id = nodes[node.id].partition_next; + node.id = _nodes[node.id].partition_next; } void first(BlueNode& node) const { @@ -1764,88 +1764,88 @@ } void next(BlueNode& node) const { - node.id = nodes[node.id].partition_next; + node.id = _nodes[node.id].partition_next; } void first(Arc& e) const { int n = first_node; - while (n != -1 && nodes[n].first_out == -1) { - n = nodes[n].next; + while (n != -1 && _nodes[n].first_out == -1) { + n = _nodes[n].next; } - e.id = (n == -1) ? -1 : nodes[n].first_out; + e.id = (n == -1) ? -1 : _nodes[n].first_out; } void next(Arc& e) const { - if (arcs[e.id].next_out != -1) { - e.id = arcs[e.id].next_out; + if (_arcs[e.id].next_out != -1) { + e.id = _arcs[e.id].next_out; } else { - int n = nodes[arcs[e.id ^ 1].target].next; - while(n != -1 && nodes[n].first_out == -1) { - n = nodes[n].next; + int n = _nodes[_arcs[e.id ^ 1].target].next; + while(n != -1 && _nodes[n].first_out == -1) { + n = _nodes[n].next; } - e.id = (n == -1) ? -1 : nodes[n].first_out; + e.id = (n == -1) ? -1 : _nodes[n].first_out; } } void first(Edge& e) const { int n = first_node; while (n != -1) { - e.id = nodes[n].first_out; + e.id = _nodes[n].first_out; while ((e.id & 1) != 1) { - e.id = arcs[e.id].next_out; + e.id = _arcs[e.id].next_out; } if (e.id != -1) { e.id /= 2; return; } - n = nodes[n].next; + n = _nodes[n].next; } e.id = -1; } void next(Edge& e) const { - int n = arcs[e.id * 2].target; - e.id = arcs[(e.id * 2) | 1].next_out; + int n = _arcs[e.id * 2].target; + e.id = _arcs[(e.id * 2) | 1].next_out; while ((e.id & 1) != 1) { - e.id = arcs[e.id].next_out; + e.id = _arcs[e.id].next_out; } if (e.id != -1) { e.id /= 2; return; } - n = nodes[n].next; + n = _nodes[n].next; while (n != -1) { - e.id = nodes[n].first_out; + e.id = _nodes[n].first_out; while ((e.id & 1) != 1) { - e.id = arcs[e.id].next_out; + e.id = _arcs[e.id].next_out; } if (e.id != -1) { e.id /= 2; return; } - n = nodes[n].next; + n = _nodes[n].next; } e.id = -1; } void firstOut(Arc &e, const Node& v) const { - e.id = nodes[v.id].first_out; + e.id = _nodes[v.id].first_out; } void nextOut(Arc &e) const { - e.id = arcs[e.id].next_out; + e.id = _arcs[e.id].next_out; } void firstIn(Arc &e, const Node& v) const { - e.id = ((nodes[v.id].first_out) ^ 1); + e.id = ((_nodes[v.id].first_out) ^ 1); if (e.id == -2) e.id = -1; } void nextIn(Arc &e) const { - e.id = ((arcs[e.id ^ 1].next_out) ^ 1); + e.id = ((_arcs[e.id ^ 1].next_out) ^ 1); if (e.id == -2) e.id = -1; } void firstInc(Edge &e, bool& d, const Node& v) const { - int a = nodes[v.id].first_out; + int a = _nodes[v.id].first_out; if (a != -1 ) { e.id = a / 2; d = ((a & 1) == 1); @@ -1855,7 +1855,7 @@ } } void nextInc(Edge &e, bool& d) const { - int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out); + int a = (_arcs[(e.id * 2) | (d ? 1 : 0)].next_out); if (a != -1 ) { e.id = a / 2; d = ((a & 1) == 1); @@ -1866,8 +1866,8 @@ } static int id(Node v) { return v.id; } - int id(RedNode v) const { return nodes[v.id].partition_index; } - int id(BlueNode v) const { return nodes[v.id].partition_index; } + int id(RedNode v) const { return _nodes[v.id].partition_index; } + int id(BlueNode v) const { return _nodes[v.id].partition_index; } static int id(Arc e) { return e.id; } static int id(Edge e) { return e.id; } @@ -1876,44 +1876,44 @@ static Edge edgeFromId(int id) { return Edge(id);} bool valid(Node n) const { - return n.id >= 0 && n.id < static_cast(nodes.size()) && - nodes[n.id].prev != -2; + return n.id >= 0 && n.id < static_cast(_nodes.size()) && + _nodes[n.id].prev != -2; } bool valid(Arc a) const { - return a.id >= 0 && a.id < static_cast(arcs.size()) && - arcs[a.id].prev_out != -2; + return a.id >= 0 && a.id < static_cast(_arcs.size()) && + _arcs[a.id].prev_out != -2; } bool valid(Edge e) const { - return e.id >= 0 && 2 * e.id < static_cast(arcs.size()) && - arcs[2 * e.id].prev_out != -2; + return e.id >= 0 && 2 * e.id < static_cast(_arcs.size()) && + _arcs[2 * e.id].prev_out != -2; } RedNode addRedNode() { int n; if(first_free_red==-1) { - n = nodes.size(); - nodes.push_back(NodeT()); - nodes[n].partition_index = ++max_red; - nodes[n].red = true; + n = _nodes.size(); + _nodes.push_back(NodeT()); + _nodes[n].partition_index = ++max_red; + _nodes[n].red = true; } else { n = first_free_red; - first_free_red = nodes[n].next; + first_free_red = _nodes[n].next; } - nodes[n].next = first_node; - if (first_node != -1) nodes[first_node].prev = n; + _nodes[n].next = first_node; + if (first_node != -1) _nodes[first_node].prev = n; first_node = n; - nodes[n].prev = -1; - - nodes[n].partition_next = first_red; - if (first_red != -1) nodes[first_red].partition_prev = n; + _nodes[n].prev = -1; + + _nodes[n].partition_next = first_red; + if (first_red != -1) _nodes[first_red].partition_prev = n; first_red = n; - nodes[n].partition_prev = -1; - - nodes[n].first_out = -1; + _nodes[n].partition_prev = -1; + + _nodes[n].first_out = -1; return RedNode(n); } @@ -1922,26 +1922,26 @@ int n; if(first_free_blue==-1) { - n = nodes.size(); - nodes.push_back(NodeT()); - nodes[n].partition_index = ++max_blue; - nodes[n].red = false; + n = _nodes.size(); + _nodes.push_back(NodeT()); + _nodes[n].partition_index = ++max_blue; + _nodes[n].red = false; } else { n = first_free_blue; - first_free_blue = nodes[n].next; + first_free_blue = _nodes[n].next; } - nodes[n].next = first_node; - if (first_node != -1) nodes[first_node].prev = n; + _nodes[n].next = first_node; + if (first_node != -1) _nodes[first_node].prev = n; first_node = n; - nodes[n].prev = -1; - - nodes[n].partition_next = first_blue; - if (first_blue != -1) nodes[first_blue].partition_prev = n; + _nodes[n].prev = -1; + + _nodes[n].partition_next = first_blue; + if (first_blue != -1) _nodes[first_blue].partition_prev = n; first_blue = n; - nodes[n].partition_prev = -1; - - nodes[n].first_out = -1; + _nodes[n].partition_prev = -1; + + _nodes[n].first_out = -1; return BlueNode(n); } @@ -1950,30 +1950,30 @@ int n; if (first_free_arc == -1) { - n = arcs.size(); - arcs.push_back(ArcT()); - arcs.push_back(ArcT()); + n = _arcs.size(); + _arcs.push_back(ArcT()); + _arcs.push_back(ArcT()); } else { n = first_free_arc; - first_free_arc = arcs[n].next_out; + first_free_arc = _arcs[n].next_out; } - arcs[n].target = u.id; - arcs[n | 1].target = v.id; - - arcs[n].next_out = nodes[v.id].first_out; - if (nodes[v.id].first_out != -1) { - arcs[nodes[v.id].first_out].prev_out = n; + _arcs[n].target = u.id; + _arcs[n | 1].target = v.id; + + _arcs[n].next_out = _nodes[v.id].first_out; + if (_nodes[v.id].first_out != -1) { + _arcs[_nodes[v.id].first_out].prev_out = n; } - arcs[n].prev_out = -1; - nodes[v.id].first_out = n; - - arcs[n | 1].next_out = nodes[u.id].first_out; - if (nodes[u.id].first_out != -1) { - arcs[nodes[u.id].first_out].prev_out = (n | 1); + _arcs[n].prev_out = -1; + _nodes[v.id].first_out = n; + + _arcs[n | 1].next_out = _nodes[u.id].first_out; + if (_nodes[u.id].first_out != -1) { + _arcs[_nodes[u.id].first_out].prev_out = (n | 1); } - arcs[n | 1].prev_out = -1; - nodes[u.id].first_out = (n | 1); + _arcs[n | 1].prev_out = -1; + _nodes[u.id].first_out = (n | 1); return Edge(n / 2); } @@ -1981,73 +1981,73 @@ void erase(const Node& node) { int n = node.id; - if(nodes[n].next != -1) { - nodes[nodes[n].next].prev = nodes[n].prev; + if(_nodes[n].next != -1) { + _nodes[_nodes[n].next].prev = _nodes[n].prev; } - if(nodes[n].prev != -1) { - nodes[nodes[n].prev].next = nodes[n].next; + if(_nodes[n].prev != -1) { + _nodes[_nodes[n].prev].next = _nodes[n].next; } else { - first_node = nodes[n].next; + first_node = _nodes[n].next; } - if (nodes[n].partition_next != -1) { - nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev; + if (_nodes[n].partition_next != -1) { + _nodes[_nodes[n].partition_next].partition_prev = _nodes[n].partition_prev; } - if (nodes[n].partition_prev != -1) { - nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next; + if (_nodes[n].partition_prev != -1) { + _nodes[_nodes[n].partition_prev].partition_next = _nodes[n].partition_next; } else { - if (nodes[n].red) { - first_red = nodes[n].partition_next; + if (_nodes[n].red) { + first_red = _nodes[n].partition_next; } else { - first_blue = nodes[n].partition_next; + first_blue = _nodes[n].partition_next; } } - if (nodes[n].red) { - nodes[n].next = first_free_red; + if (_nodes[n].red) { + _nodes[n].next = first_free_red; first_free_red = n; } else { - nodes[n].next = first_free_blue; + _nodes[n].next = first_free_blue; first_free_blue = n; } - nodes[n].prev = -2; + _nodes[n].prev = -2; } void erase(const Edge& edge) { int n = edge.id * 2; - if (arcs[n].next_out != -1) { - arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; + if (_arcs[n].next_out != -1) { + _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out; } - if (arcs[n].prev_out != -1) { - arcs[arcs[n].prev_out].next_out = arcs[n].next_out; + if (_arcs[n].prev_out != -1) { + _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out; } else { - nodes[arcs[n | 1].target].first_out = arcs[n].next_out; + _nodes[_arcs[n | 1].target].first_out = _arcs[n].next_out; } - if (arcs[n | 1].next_out != -1) { - arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out; + if (_arcs[n | 1].next_out != -1) { + _arcs[_arcs[n | 1].next_out].prev_out = _arcs[n | 1].prev_out; } - if (arcs[n | 1].prev_out != -1) { - arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out; + if (_arcs[n | 1].prev_out != -1) { + _arcs[_arcs[n | 1].prev_out].next_out = _arcs[n | 1].next_out; } else { - nodes[arcs[n].target].first_out = arcs[n | 1].next_out; + _nodes[_arcs[n].target].first_out = _arcs[n | 1].next_out; } - arcs[n].next_out = first_free_arc; + _arcs[n].next_out = first_free_arc; first_free_arc = n; - arcs[n].prev_out = -2; - arcs[n | 1].prev_out = -2; + _arcs[n].prev_out = -2; + _arcs[n | 1].prev_out = -2; } void clear() { - arcs.clear(); - nodes.clear(); + _arcs.clear(); + _nodes.clear(); first_node = first_free_arc = first_red = first_blue = max_red = max_blue = first_free_red = first_free_blue = -1; } @@ -2055,46 +2055,46 @@ protected: void changeRed(Edge e, RedNode n) { - if(arcs[(2 * e.id) | 1].next_out != -1) { - arcs[arcs[(2 * e.id) | 1].next_out].prev_out = - arcs[(2 * e.id) | 1].prev_out; + if(_arcs[(2 * e.id) | 1].next_out != -1) { + _arcs[_arcs[(2 * e.id) | 1].next_out].prev_out = + _arcs[(2 * e.id) | 1].prev_out; } - if(arcs[(2 * e.id) | 1].prev_out != -1) { - arcs[arcs[(2 * e.id) | 1].prev_out].next_out = - arcs[(2 * e.id) | 1].next_out; + if(_arcs[(2 * e.id) | 1].prev_out != -1) { + _arcs[_arcs[(2 * e.id) | 1].prev_out].next_out = + _arcs[(2 * e.id) | 1].next_out; } else { - nodes[arcs[2 * e.id].target].first_out = - arcs[(2 * e.id) | 1].next_out; + _nodes[_arcs[2 * e.id].target].first_out = + _arcs[(2 * e.id) | 1].next_out; } - if (nodes[n.id].first_out != -1) { - arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1); + if (_nodes[n.id].first_out != -1) { + _arcs[_nodes[n.id].first_out].prev_out = ((2 * e.id) | 1); } - arcs[2 * e.id].target = n.id; - arcs[(2 * e.id) | 1].prev_out = -1; - arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out; - nodes[n.id].first_out = ((2 * e.id) | 1); + _arcs[2 * e.id].target = n.id; + _arcs[(2 * e.id) | 1].prev_out = -1; + _arcs[(2 * e.id) | 1].next_out = _nodes[n.id].first_out; + _nodes[n.id].first_out = ((2 * e.id) | 1); } void changeBlue(Edge e, BlueNode n) { - if(arcs[2 * e.id].next_out != -1) { - arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out; + if(_arcs[2 * e.id].next_out != -1) { + _arcs[_arcs[2 * e.id].next_out].prev_out = _arcs[2 * e.id].prev_out; } - if(arcs[2 * e.id].prev_out != -1) { - arcs[arcs[2 * e.id].prev_out].next_out = - arcs[2 * e.id].next_out; + if(_arcs[2 * e.id].prev_out != -1) { + _arcs[_arcs[2 * e.id].prev_out].next_out = + _arcs[2 * e.id].next_out; } else { - nodes[arcs[(2 * e.id) | 1].target].first_out = - arcs[2 * e.id].next_out; + _nodes[_arcs[(2 * e.id) | 1].target].first_out = + _arcs[2 * e.id].next_out; } - if (nodes[n.id].first_out != -1) { - arcs[nodes[n.id].first_out].prev_out = 2 * e.id; + if (_nodes[n.id].first_out != -1) { + _arcs[_nodes[n.id].first_out].prev_out = 2 * e.id; } - arcs[(2 * e.id) | 1].target = n.id; - arcs[2 * e.id].prev_out = -1; - arcs[2 * e.id].next_out = nodes[n.id].first_out; - nodes[n.id].first_out = 2 * e.id; + _arcs[(2 * e.id) | 1].target = n.id; + _arcs[2 * e.id].prev_out = -1; + _arcs[2 * e.id].next_out = _nodes[n.id].first_out; + _nodes[n.id].first_out = 2 * e.id; } }; @@ -2249,7 +2249,7 @@ /// then it is worth reserving space for this amount before starting /// to build the graph. /// \sa reserveEdge() - void reserveNode(int n) { nodes.reserve(n); }; + void reserveNode(int n) { _nodes.reserve(n); }; /// Reserve memory for edges. @@ -2259,7 +2259,7 @@ /// then it is worth reserving space for this amount before starting /// to build the graph. /// \sa reserveNode() - void reserveEdge(int m) { arcs.reserve(2 * m); }; + void reserveEdge(int m) { _arcs.reserve(2 * m); }; /// \brief Class to make a snapshot of the graph and restore /// it later. diff -r 39b6e65574c6 -r 0759d974de81 lemon/lp_base.h --- a/lemon/lp_base.h Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/lp_base.h Sun Jan 05 22:24:56 2014 +0100 @@ -31,6 +31,8 @@ #include #include +#include + ///\file ///\brief The interface of the LP solver interface. ///\ingroup lp_group @@ -45,8 +47,8 @@ protected: - _solver_bits::VarIndex rows; - _solver_bits::VarIndex cols; + _solver_bits::VarIndex _rows; + _solver_bits::VarIndex _cols; public: @@ -166,7 +168,7 @@ /// ColIt(const LpBase &solver) : _solver(&solver) { - _solver->cols.firstItem(_id); + _solver->_cols.firstItem(_id); } /// Invalid constructor \& conversion @@ -179,11 +181,26 @@ /// ColIt &operator++() { - _solver->cols.nextItem(_id); + _solver->_cols.nextItem(_id); return *this; } }; + /// \brief Gets the collection of the columns of the LP problem. + /// + /// This function can be used for iterating on + /// the columns of the LP problem. It returns a wrapped ColIt, which looks + /// like an STL container (by having begin() and end()) + /// which you can use in range-based for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// for(auto c: lp.cols()) + /// doSomething(c); + LemonRangeWrapper1 cols() { + return LemonRangeWrapper1(*this); + } + + /// \brief Returns the ID of the column. static int id(const Col& col) { return col._id; } /// \brief Returns the column with the given ID. @@ -261,7 +278,7 @@ /// RowIt(const LpBase &solver) : _solver(&solver) { - _solver->rows.firstItem(_id); + _solver->_rows.firstItem(_id); } /// Invalid constructor \& conversion @@ -274,10 +291,25 @@ /// RowIt &operator++() { - _solver->rows.nextItem(_id); + _solver->_rows.nextItem(_id); return *this; } }; + + /// \brief Gets the collection of the rows of the LP problem. + /// + /// This function can be used for iterating on + /// the rows of the LP problem. It returns a wrapped RowIt, which looks + /// like an STL container (by having begin() and end()) + /// which you can use in range-based for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// for(auto c: lp.rows()) + /// doSomething(c); + LemonRangeWrapper1 rows() { + return LemonRangeWrapper1(*this); + } + /// \brief Returns the ID of the row. static int id(const Row& row) { return row._id; } @@ -934,11 +966,11 @@ //Abstract virtual functions - virtual int _addColId(int col) { return cols.addIndex(col); } - virtual int _addRowId(int row) { return rows.addIndex(row); } + virtual int _addColId(int col) { return _cols.addIndex(col); } + virtual int _addRowId(int row) { return _rows.addIndex(row); } - virtual void _eraseColId(int col) { cols.eraseIndex(col); } - virtual void _eraseRowId(int row) { rows.eraseIndex(row); } + virtual void _eraseColId(int col) { _cols.eraseIndex(col); } + virtual void _eraseRowId(int row) { _rows.eraseIndex(row); } virtual int _addCol() = 0; virtual int _addRow() = 0; @@ -1003,7 +1035,7 @@ //Constant component of the objective function Value obj_const_comp; - LpBase() : rows(), cols(), obj_const_comp(0) {} + LpBase() : _rows(), _cols(), obj_const_comp(0) {} public: @@ -1115,8 +1147,8 @@ ///a better one. void col(Col c, const DualExpr &e) { e.simplify(); - _setColCoeffs(cols(id(c)), ExprIterator(e.comps.begin(), rows), - ExprIterator(e.comps.end(), rows)); + _setColCoeffs(_cols(id(c)), ExprIterator(e.comps.begin(), _rows), + ExprIterator(e.comps.end(), _rows)); } ///Get a column (i.e a dual constraint) of the LP @@ -1125,7 +1157,7 @@ ///\return the dual expression associated to the column DualExpr col(Col c) const { DualExpr e; - _getColCoeffs(cols(id(c)), InsertIterator(e.comps, rows)); + _getColCoeffs(_cols(id(c)), InsertIterator(e.comps, _rows)); return e; } @@ -1212,10 +1244,10 @@ ///\param u is the upper bound (\ref INF means no bound) void row(Row r, Value l, const Expr &e, Value u) { e.simplify(); - _setRowCoeffs(rows(id(r)), ExprIterator(e.comps.begin(), cols), - ExprIterator(e.comps.end(), cols)); - _setRowLowerBound(rows(id(r)),l - *e); - _setRowUpperBound(rows(id(r)),u - *e); + _setRowCoeffs(_rows(id(r)), ExprIterator(e.comps.begin(), _cols), + ExprIterator(e.comps.end(), _cols)); + _setRowLowerBound(_rows(id(r)),l - *e); + _setRowUpperBound(_rows(id(r)),u - *e); } ///Set a row (i.e a constraint) of the LP @@ -1234,7 +1266,7 @@ ///\return the expression associated to the row Expr row(Row r) const { Expr e; - _getRowCoeffs(rows(id(r)), InsertIterator(e.comps, cols)); + _getRowCoeffs(_rows(id(r)), InsertIterator(e.comps, _cols)); return e; } @@ -1247,8 +1279,8 @@ Row addRow(Value l,const Expr &e, Value u) { Row r; e.simplify(); - r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols), - ExprIterator(e.comps.end(), cols), u - *e)); + r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), _cols), + ExprIterator(e.comps.end(), _cols), u - *e)); return r; } @@ -1260,8 +1292,8 @@ Row r; c.expr().simplify(); r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF, - ExprIterator(c.expr().comps.begin(), cols), - ExprIterator(c.expr().comps.end(), cols), + ExprIterator(c.expr().comps.begin(), _cols), + ExprIterator(c.expr().comps.end(), _cols), c.upperBounded()?c.upperBound()-*c.expr():INF)); return r; } @@ -1269,15 +1301,15 @@ ///\param c is the column to be deleted void erase(Col c) { - _eraseCol(cols(id(c))); - _eraseColId(cols(id(c))); + _eraseCol(_cols(id(c))); + _eraseColId(_cols(id(c))); } ///Erase a row (i.e a constraint) from the LP ///\param r is the row to be deleted void erase(Row r) { - _eraseRow(rows(id(r))); - _eraseRowId(rows(id(r))); + _eraseRow(_rows(id(r))); + _eraseRowId(_rows(id(r))); } /// Get the name of a column @@ -1286,7 +1318,7 @@ ///\return The name of the colunm std::string colName(Col c) const { std::string name; - _getColName(cols(id(c)), name); + _getColName(_cols(id(c)), name); return name; } @@ -1295,7 +1327,7 @@ ///\param c is the coresponding column ///\param name The name to be given void colName(Col c, const std::string& name) { - _setColName(cols(id(c)), name); + _setColName(_cols(id(c)), name); } /// Get the column by its name @@ -1304,7 +1336,7 @@ ///\return the proper column or \c INVALID Col colByName(const std::string& name) const { int k = _colByName(name); - return k != -1 ? Col(cols[k]) : Col(INVALID); + return k != -1 ? Col(_cols[k]) : Col(INVALID); } /// Get the name of a row @@ -1313,7 +1345,7 @@ ///\return The name of the row std::string rowName(Row r) const { std::string name; - _getRowName(rows(id(r)), name); + _getRowName(_rows(id(r)), name); return name; } @@ -1322,7 +1354,7 @@ ///\param r is the coresponding row ///\param name The name to be given void rowName(Row r, const std::string& name) { - _setRowName(rows(id(r)), name); + _setRowName(_rows(id(r)), name); } /// Get the row by its name @@ -1331,7 +1363,7 @@ ///\return the proper row or \c INVALID Row rowByName(const std::string& name) const { int k = _rowByName(name); - return k != -1 ? Row(rows[k]) : Row(INVALID); + return k != -1 ? Row(_rows[k]) : Row(INVALID); } /// Set an element of the coefficient matrix of the LP @@ -1340,7 +1372,7 @@ ///\param c is the column of the element to be modified ///\param val is the new value of the coefficient void coeff(Row r, Col c, Value val) { - _setCoeff(rows(id(r)),cols(id(c)), val); + _setCoeff(_rows(id(r)),_cols(id(c)), val); } /// Get an element of the coefficient matrix of the LP @@ -1349,7 +1381,7 @@ ///\param c is the column of the element ///\return the corresponding coefficient Value coeff(Row r, Col c) const { - return _getCoeff(rows(id(r)),cols(id(c))); + return _getCoeff(_rows(id(r)),_cols(id(c))); } /// Set the lower bound of a column (i.e a variable) @@ -1358,7 +1390,7 @@ /// extended number of type Value, i.e. a finite number of type /// Value or -\ref INF. void colLowerBound(Col c, Value value) { - _setColLowerBound(cols(id(c)),value); + _setColLowerBound(_cols(id(c)),value); } /// Get the lower bound of a column (i.e a variable) @@ -1367,7 +1399,7 @@ /// (this might be -\ref INF as well). ///\return The lower bound for column \c c Value colLowerBound(Col c) const { - return _getColLowerBound(cols(id(c))); + return _getColLowerBound(_cols(id(c))); } ///\brief Set the lower bound of several columns @@ -1413,7 +1445,7 @@ /// extended number of type Value, i.e. a finite number of type /// Value or \ref INF. void colUpperBound(Col c, Value value) { - _setColUpperBound(cols(id(c)),value); + _setColUpperBound(_cols(id(c)),value); }; /// Get the upper bound of a column (i.e a variable) @@ -1422,7 +1454,7 @@ /// (this might be \ref INF as well). /// \return The upper bound for column \c c Value colUpperBound(Col c) const { - return _getColUpperBound(cols(id(c))); + return _getColUpperBound(_cols(id(c))); } ///\brief Set the upper bound of several columns @@ -1469,8 +1501,8 @@ /// extended number of type Value, i.e. a finite number of type /// Value, -\ref INF or \ref INF. void colBounds(Col c, Value lower, Value upper) { - _setColLowerBound(cols(id(c)),lower); - _setColUpperBound(cols(id(c)),upper); + _setColLowerBound(_cols(id(c)),lower); + _setColUpperBound(_cols(id(c)),upper); } ///\brief Set the lower and the upper bound of several columns @@ -1515,7 +1547,7 @@ /// extended number of type Value, i.e. a finite number of type /// Value or -\ref INF. void rowLowerBound(Row r, Value value) { - _setRowLowerBound(rows(id(r)),value); + _setRowLowerBound(_rows(id(r)),value); } /// Get the lower bound of a row (i.e a constraint) @@ -1524,7 +1556,7 @@ /// (this might be -\ref INF as well). ///\return The lower bound for row \c r Value rowLowerBound(Row r) const { - return _getRowLowerBound(rows(id(r))); + return _getRowLowerBound(_rows(id(r))); } /// Set the upper bound of a row (i.e a constraint) @@ -1533,7 +1565,7 @@ /// extended number of type Value, i.e. a finite number of type /// Value or -\ref INF. void rowUpperBound(Row r, Value value) { - _setRowUpperBound(rows(id(r)),value); + _setRowUpperBound(_rows(id(r)),value); } /// Get the upper bound of a row (i.e a constraint) @@ -1542,22 +1574,22 @@ /// (this might be -\ref INF as well). ///\return The upper bound for row \c r Value rowUpperBound(Row r) const { - return _getRowUpperBound(rows(id(r))); + return _getRowUpperBound(_rows(id(r))); } ///Set an element of the objective function - void objCoeff(Col c, Value v) {_setObjCoeff(cols(id(c)),v); }; + void objCoeff(Col c, Value v) {_setObjCoeff(_cols(id(c)),v); }; ///Get an element of the objective function - Value objCoeff(Col c) const { return _getObjCoeff(cols(id(c))); }; + Value objCoeff(Col c) const { return _getObjCoeff(_cols(id(c))); }; ///Set the objective function ///\param e is a linear expression of type \ref Expr. /// void obj(const Expr& e) { - _setObjCoeffs(ExprIterator(e.comps.begin(), cols), - ExprIterator(e.comps.end(), cols)); + _setObjCoeffs(ExprIterator(e.comps.begin(), _cols), + ExprIterator(e.comps.end(), _cols)); obj_const_comp = *e; } @@ -1567,7 +1599,7 @@ ///Expr. Expr obj() const { Expr e; - _getObjCoeffs(InsertIterator(e.comps, cols)); + _getObjCoeffs(InsertIterator(e.comps, _cols)); *e = obj_const_comp; return e; } @@ -1586,7 +1618,7 @@ void min() { _setSense(MIN); } ///Clear the problem - void clear() { _clear(); rows.clear(); cols.clear(); } + void clear() { _clear(); _rows.clear(); _cols.clear(); } /// Set the message level of the solver void messageLevel(MessageLevel level) { _messageLevel(level); } @@ -1929,7 +1961,7 @@ /// Return the primal value of the column. /// \pre The problem is solved. - Value primal(Col c) const { return _getPrimal(cols(id(c))); } + Value primal(Col c) const { return _getPrimal(_cols(id(c))); } /// Return the primal value of the expression @@ -1956,13 +1988,13 @@ /// \pre The problem is solved and the dual problem is infeasible. /// \note Some solvers does not provide primal ray calculation /// functions. - Value primalRay(Col c) const { return _getPrimalRay(cols(id(c))); } + Value primalRay(Col c) const { return _getPrimalRay(_cols(id(c))); } /// Return the dual value of the row /// Return the dual value of the row. /// \pre The problem is solved. - Value dual(Row r) const { return _getDual(rows(id(r))); } + Value dual(Row r) const { return _getDual(_rows(id(r))); } /// Return the dual value of the dual expression @@ -1990,17 +2022,17 @@ /// \pre The problem is solved and the primal problem is infeasible. /// \note Some solvers does not provide dual ray calculation /// functions. - Value dualRay(Row r) const { return _getDualRay(rows(id(r))); } + Value dualRay(Row r) const { return _getDualRay(_rows(id(r))); } /// Return the basis status of the column /// \see VarStatus - VarStatus colStatus(Col c) const { return _getColStatus(cols(id(c))); } + VarStatus colStatus(Col c) const { return _getColStatus(_cols(id(c))); } /// Return the basis status of the row /// \see VarStatus - VarStatus rowStatus(Row r) const { return _getRowStatus(rows(id(r))); } + VarStatus rowStatus(Row r) const { return _getRowStatus(_rows(id(r))); } ///The value of the objective function @@ -2080,7 +2112,7 @@ ///Sets the type of the given column to the given type. /// void colType(Col c, ColTypes col_type) { - _setColType(cols(id(c)),col_type); + _setColType(_cols(id(c)),col_type); } ///Gives back the type of the column. @@ -2088,7 +2120,7 @@ ///Gives back the type of the column. /// ColTypes colType(Col c) const { - return _getColType(cols(id(c))); + return _getColType(_cols(id(c))); } ///@} @@ -2105,7 +2137,7 @@ /// Return the value of the row in the solution. /// \pre The problem is solved. - Value sol(Col c) const { return _getSol(cols(id(c))); } + Value sol(Col c) const { return _getSol(_cols(id(c))); } /// Return the value of the expression in the solution diff -r 39b6e65574c6 -r 0759d974de81 lemon/maps.h --- a/lemon/maps.h Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/maps.h Sun Jan 05 22:24:56 2014 +0100 @@ -25,6 +25,7 @@ #include #include +#include ///\file ///\ingroup maps @@ -2581,6 +2582,16 @@ const IterableBoolMap* _map; }; + /// \brief STL style iterator for the keys mapped to \c true. + /// + /// This is an STL style wrapper for \ref TrueIt. + /// It can be used in range-based for loops, STL algorithms, etc. + LemonRangeWrapper1 + trueKeys() { + return LemonRangeWrapper1(*this); + } + + /// \brief Iterator for the keys mapped to \c false. /// /// Iterator for the keys mapped to \c false. It works @@ -2620,6 +2631,16 @@ const IterableBoolMap* _map; }; + /// \brief STL style iterator for the keys mapped to \c false. + /// + /// This is an STL style wrapper for \ref FalseIt. + /// It can be used in range-based for loops, STL algorithms, etc. + LemonRangeWrapper1 + falseKeys() { + return LemonRangeWrapper1(*this); + } + + /// \brief Iterator for the keys mapped to a given value. /// /// Iterator for the keys mapped to a given value. It works @@ -2664,6 +2685,15 @@ const IterableBoolMap* _map; }; + /// \brief STL style iterator for the keys mapped to a given value. + /// + /// This is an STL style wrapper for \ref ItemIt. + /// It can be used in range-based for loops, STL algorithms, etc. + LemonRangeWrapper2 + items(bool value) { + return LemonRangeWrapper2(*this, value); + } + protected: virtual void add(const Key& key) { @@ -3005,6 +3035,16 @@ const IterableIntMap* _map; }; + /// \brief STL style iterator for the keys with the same value. + /// + /// This is an STL style wrapper for \ref ItemIt. + /// It can be used in range-based for loops, STL algorithms, etc. + LemonRangeWrapper2 + items(int value) { + return LemonRangeWrapper2(*this, value); + } + + protected: virtual void erase(const Key& key) { @@ -3248,6 +3288,16 @@ const IterableValueMap* _map; }; + /// \brief STL style iterator for the keys with the same value. + /// + /// This is an STL style wrapper for \ref ItemIt. + /// It can be used in range-based for loops, STL algorithms, etc. + LemonRangeWrapper2 + items(const V& value) { + return LemonRangeWrapper2(*this, value); + } + + protected: virtual void add(const Key& key) { diff -r 39b6e65574c6 -r 0759d974de81 lemon/path.h --- a/lemon/path.h Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/path.h Sun Jan 05 22:24:56 2014 +0100 @@ -30,6 +30,7 @@ #include #include #include +#include namespace lemon { @@ -140,6 +141,23 @@ int idx; }; + /// \brief Gets the collection of the arcs of the path. + /// + /// This function can be used for iterating on the + /// arcs of the path. It returns a wrapped + /// ArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// for(auto a: p.arcs()) + /// doSomething(a); + ///\endcode + LemonRangeWrapper1 arcs() const { + return LemonRangeWrapper1(*this); + } + + /// \brief Length of the path. int length() const { return head.size() + tail.size(); } /// \brief Return whether the path is empty. @@ -345,6 +363,23 @@ int idx; }; + /// \brief Gets the collection of the arcs of the path. + /// + /// This function can be used for iterating on the + /// arcs of the path. It returns a wrapped + /// ArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// for(auto a: p.arcs()) + /// doSomething(a); + ///\endcode + LemonRangeWrapper1 arcs() const { + return LemonRangeWrapper1(*this); + } + + /// \brief Length of the path. int length() const { return data.size(); } /// \brief Return true if the path is empty. @@ -543,6 +578,23 @@ Node *node; }; + /// \brief Gets the collection of the arcs of the path. + /// + /// This function can be used for iterating on the + /// arcs of the path. It returns a wrapped + /// ArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// for(auto a: p.arcs()) + /// doSomething(a); + ///\endcode + LemonRangeWrapper1 arcs() const { + return LemonRangeWrapper1(*this); + } + + /// \brief The n-th arc. /// /// This function looks for the n-th arc in O(n) time. @@ -795,11 +847,11 @@ /// \brief Default constructor /// /// Default constructor - StaticPath() : len(0), arcs(0) {} + StaticPath() : len(0), _arcs(0) {} /// \brief Copy constructor /// - StaticPath(const StaticPath& cpath) : arcs(0) { + StaticPath(const StaticPath& cpath) : _arcs(0) { pathCopy(cpath, *this); } @@ -807,7 +859,7 @@ /// /// This path can be initialized from any other path type. template - StaticPath(const CPath& cpath) : arcs(0) { + StaticPath(const CPath& cpath) : _arcs(0) { pathCopy(cpath, *this); } @@ -815,7 +867,7 @@ /// /// Destructor of the path ~StaticPath() { - if (arcs) delete[] arcs; + if (_arcs) delete[] _arcs; } /// \brief Copy assignment @@ -882,12 +934,29 @@ const StaticPath *path; int idx; }; + + /// \brief Gets the collection of the arcs of the path. + /// + /// This function can be used for iterating on the + /// arcs of the path. It returns a wrapped + /// ArcIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// for(auto a: p.arcs()) + /// doSomething(a); + ///\endcode + LemonRangeWrapper1 arcs() const { + return LemonRangeWrapper1(*this); + } + /// \brief The n-th arc. /// /// \pre \c n is in the [0..length() - 1] range. const Arc& nth(int n) const { - return arcs[n]; + return _arcs[n]; } /// \brief The arc iterator pointing to the n-th arc. @@ -904,18 +973,18 @@ /// \brief Erase all arcs in the digraph. void clear() { len = 0; - if (arcs) delete[] arcs; - arcs = 0; + if (_arcs) delete[] _arcs; + _arcs = 0; } /// \brief The first arc of the path. const Arc& front() const { - return arcs[0]; + return _arcs[0]; } /// \brief The last arc of the path. const Arc& back() const { - return arcs[len - 1]; + return _arcs[len - 1]; } @@ -924,10 +993,10 @@ template void build(const CPath& path) { len = path.length(); - arcs = new Arc[len]; + _arcs = new Arc[len]; int index = 0; for (typename CPath::ArcIt it(path); it != INVALID; ++it) { - arcs[index] = it; + _arcs[index] = it; ++index; } } @@ -935,17 +1004,17 @@ template void buildRev(const CPath& path) { len = path.length(); - arcs = new Arc[len]; + _arcs = new Arc[len]; int index = len; for (typename CPath::RevArcIt it(path); it != INVALID; ++it) { --index; - arcs[index] = it; + _arcs[index] = it; } } private: int len; - Arc* arcs; + Arc* _arcs; }; /////////////////////////////////////////////////////////////////////// @@ -1157,6 +1226,25 @@ }; + /// \brief Gets the collection of the nodes of the path. + /// + /// This function can be used for iterating on the + /// nodes of the path. It returns a wrapped + /// PathNodeIt, which looks like an STL container + /// (by having begin() and end()) which you can use in range-based + /// for loops, STL algorithms, etc. + /// For example you can write: + ///\code + /// for(auto u: pathNodes(g,p)) + /// doSomething(u); + ///\endcode + template + LemonRangeWrapper2, typename Path::Digraph, Path> + pathNodes(const typename Path::Digraph &g, const Path &p) { + return + LemonRangeWrapper2, typename Path::Digraph, Path>(g,p); + } + ///@} } // namespace lemon diff -r 39b6e65574c6 -r 0759d974de81 lemon/smart_graph.h --- a/lemon/smart_graph.h Thu Apr 02 22:34:03 2015 +0200 +++ b/lemon/smart_graph.h Sun Jan 05 22:24:56 2014 +0100 @@ -47,8 +47,8 @@ ArcT() {} }; - std::vector nodes; - std::vector arcs; + std::vector _nodes; + std::vector _arcs; public: @@ -59,46 +59,46 @@ public: - SmartDigraphBase() : nodes(), arcs() { } + SmartDigraphBase() : _nodes(), _arcs() { } SmartDigraphBase(const SmartDigraphBase &_g) - : nodes(_g.nodes), arcs(_g.arcs) { } + : _nodes(_g._nodes), _arcs(_g._arcs) { } typedef True NodeNumTag; typedef True ArcNumTag; - int nodeNum() const { return nodes.size(); } - int arcNum() const { return arcs.size(); } + int nodeNum() const { return _nodes.size(); } + int arcNum() const { return _arcs.size(); } - int maxNodeId() const { return nodes.size()-1; } - int maxArcId() const { return arcs.size()-1; } + int maxNodeId() const { return _nodes.size()-1; } + int maxArcId() const { return _arcs.size()-1; } Node addNode() { - int n = nodes.size(); - nodes.push_back(NodeT()); - nodes[n].first_in = -1; - nodes[n].first_out = -1; + int n = _nodes.size(); + _nodes.push_back(NodeT()); + _nodes[n].first_in = -1; + _nodes[n].first_out = -1; return Node(n); } Arc addArc(Node u, Node v) { - int n = arcs.size(); - arcs.push_back(ArcT()); - arcs[n].source = u._id; - arcs[n].target = v._id; - arcs[n].next_out = nodes[u._id].first_out; - arcs[n].next_in = nodes[v._id].first_in; - nodes[u._id].first_out = nodes[v._id].first_in = n; + int n = _arcs.size(); + _arcs.push_back(ArcT()); + _arcs[n].source = u._id; + _arcs[n].target = v._id; + _arcs[n].next_out = _nodes[u._id].first_out; + _arcs[n].next_in = _nodes[v._id].first_in; + _nodes[u._id].first_out = _nodes[v._id].first_in = n; return Arc(n); } void clear() { - arcs.clear(); - nodes.clear(); + _arcs.clear(); + _nodes.clear(); } - Node source(Arc a) const { return Node(arcs[a._id].source); } - Node target(Arc a) const { return Node(arcs[a._id].target); } + Node source(Arc a) const { return Node(_arcs[a._id].source); } + Node target(Arc a) const { return Node(_arcs[a._id].target); } static int id(Node v) { return v._id; } static int id(Arc a) { return a._id; } @@ -107,10 +107,10 @@ static Arc arcFromId(int id) { return Arc(id);} bool valid(Node n) const { - return n._id >= 0 && n._id < static_cast(nodes.size()); + return n._id >= 0 && n._id < static_cast(_nodes.size()); } bool valid(Arc a) const { - return a._id >= 0 && a._id < static_cast(arcs.size()); + return a._id >= 0 && a._id < static_cast(_arcs.size()); } class Node { @@ -145,7 +145,7 @@ }; void first(Node& node) const { - node._id = nodes.size() - 1; + node._id = _nodes.size() - 1; } static void next(Node& node) { @@ -153,7 +153,7 @@ } void first(Arc& arc) const { - arc._id = arcs.size() - 1; + arc._id = _arcs.size() - 1; } static void next(Arc& arc) { @@ -161,19 +161,19 @@ } void firstOut(Arc& arc, const Node& node) const { - arc._id = nodes[node._id].first_out; + arc._id = _nodes[node._id].first_out; } void nextOut(Arc& arc) const { - arc._id = arcs[arc._id].next_out; + arc._id = _arcs[arc._id].next_out; } void firstIn(Arc& arc, const Node& node) const { - arc._id = nodes[node._id].first_in; + arc._id = _nodes[node._id].first_in; } void nextIn(Arc& arc) const { - arc._id = arcs[arc._id].next_in; + arc._id = _arcs[arc._id].next_in; } }; @@ -266,10 +266,10 @@ Node split(Node n, bool connect = true) { Node b = addNode(); - nodes[b._id].first_out=nodes[n._id].first_out; - nodes[n._id].first_out=-1; - for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) { - arcs[i].source=b._id; + _nodes[b._id].first_out=_nodes[n._id].first_out; + _nodes[n._id].first_out=-1; + for(int i=_nodes[b._id].first_out; i!=-1; i=_arcs[i].next_out) { + _arcs[i].source=b._id; } if(connect) addArc(n,b); return b; @@ -291,7 +291,7 @@ /// then it is worth reserving space for this amount before starting /// to build the digraph. /// \sa reserveArc() - void reserveNode(int n) { nodes.reserve(n); }; + void reserveNode(int n) { _nodes.reserve(n); }; /// Reserve memory for arcs. @@ -301,7 +301,7 @@ /// then it is worth reserving space for this amount before starting /// to build the digraph. /// \sa reserveNode() - void reserveArc(int m) { arcs.reserve(m); }; + void reserveArc(int m) { _arcs.reserve(m); }; public: @@ -311,17 +311,17 @@ void restoreSnapshot(const Snapshot &s) { - while(s.arc_numnodes.size(); - arc_num=_graph->arcs.size(); + node_num=_graph->_nodes.size(); + arc_num=_graph->_arcs.size(); } ///Make a snapshot. @@ -373,8 +373,8 @@ ///call, the previous snapshot gets lost. void save(SmartDigraph &gr) { _graph=&gr; - node_num=_graph->nodes.size(); - arc_num=_graph->arcs.size(); + node_num=_graph->_nodes.size(); + arc_num=_graph->_arcs.size(); } ///Undo the changes until a snapshot. @@ -402,8 +402,8 @@ int next_out; }; - std::vector nodes; - std::vector arcs; + std::vector _nodes; + std::vector _arcs; public: @@ -465,25 +465,25 @@ SmartGraphBase() - : nodes(), arcs() {} + : _nodes(), _arcs() {} typedef True NodeNumTag; typedef True EdgeNumTag; typedef True ArcNumTag; - int nodeNum() const { return nodes.size(); } - int edgeNum() const { return arcs.size() / 2; } - int arcNum() const { return arcs.size(); } + int nodeNum() const { return _nodes.size(); } + int edgeNum() const { return _arcs.size() / 2; } + int arcNum() const { return _arcs.size(); } - int maxNodeId() const { return nodes.size()-1; } - int maxEdgeId() const { return arcs.size() / 2 - 1; } - int maxArcId() const { return arcs.size()-1; } + int maxNodeId() const { return _nodes.size()-1; } + int maxEdgeId() const { return _arcs.size() / 2 - 1; } + int maxArcId() const { return _arcs.size()-1; } - Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); } - Node target(Arc e) const { return Node(arcs[e._id].target); } + Node source(Arc e) const { return Node(_arcs[e._id ^ 1].target); } + Node target(Arc e) const { return Node(_arcs[e._id].target); } - Node u(Edge e) const { return Node(arcs[2 * e._id].target); } - Node v(Edge e) const { return Node(arcs[2 * e._id + 1].target); } + Node u(Edge e) const { return Node(_arcs[2 * e._id].target); } + Node v(Edge e) const { return Node(_arcs[2 * e._id + 1].target); } static bool direction(Arc e) { return (e._id & 1) == 1; @@ -494,7 +494,7 @@ } void first(Node& node) const { - node._id = nodes.size() - 1; + node._id = _nodes.size() - 1; } static void next(Node& node) { @@ -502,7 +502,7 @@ } void first(Arc& arc) const { - arc._id = arcs.size() - 1; + arc._id = _arcs.size() - 1; } static void next(Arc& arc) { @@ -510,7 +510,7 @@ } void first(Edge& arc) const { - arc._id = arcs.size() / 2 - 1; + arc._id = _arcs.size() / 2 - 1; } static void next(Edge& arc) { @@ -518,23 +518,23 @@ } void firstOut(Arc &arc, const Node& v) const { - arc._id = nodes[v._id].first_out; + arc._id = _nodes[v._id].first_out; } void nextOut(Arc &arc) const { - arc._id = arcs[arc._id].next_out; + arc._id = _arcs[arc._id].next_out; } void firstIn(Arc &arc, const Node& v) const { - arc._id = ((nodes[v._id].first_out) ^ 1); + arc._id = ((_nodes[v._id].first_out) ^ 1); if (arc._id == -2) arc._id = -1; } void nextIn(Arc &arc) const { - arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1); + arc._id = ((_arcs[arc._id ^ 1].next_out) ^ 1); if (arc._id == -2) arc._id = -1; } void firstInc(Edge &arc, bool& d, const Node& v) const { - int de = nodes[v._id].first_out; + int de = _nodes[v._id].first_out; if (de != -1) { arc._id = de / 2; d = ((de & 1) == 1); @@ -544,7 +544,7 @@ } } void nextInc(Edge &arc, bool& d) const { - int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out); + int de = (_arcs[(arc._id * 2) | (d ? 1 : 0)].next_out); if (de != -1) { arc._id = de / 2; d = ((de & 1) == 1); @@ -563,43 +563,43 @@ static Edge edgeFromId(int id) { return Edge(id);} bool valid(Node n) const { - return n._id >= 0 && n._id < static_cast(nodes.size()); + return n._id >= 0 && n._id < static_cast(_nodes.size()); } bool valid(Arc a) const { - return a._id >= 0 && a._id < static_cast(arcs.size()); + return a._id >= 0 && a._id < static_cast(_arcs.size()); } bool valid(Edge e) const { - return e._id >= 0 && 2 * e._id < static_cast(arcs.size()); + return e._id >= 0 && 2 * e._id < static_cast(_arcs.size()); } Node addNode() { - int n = nodes.size(); - nodes.push_back(NodeT()); - nodes[n].first_out = -1; + int n = _nodes.size(); + _nodes.push_back(NodeT()); + _nodes[n].first_out = -1; return Node(n); } Edge addEdge(Node u, Node v) { - int n = arcs.size(); - arcs.push_back(ArcT()); - arcs.push_back(ArcT()); + int n = _arcs.size(); + _arcs.push_back(ArcT()); + _arcs.push_back(ArcT()); - arcs[n].target = u._id; - arcs[n | 1].target = v._id; + _arcs[n].target = u._id; + _arcs[n | 1].target = v._id; - arcs[n].next_out = nodes[v._id].first_out; - nodes[v._id].first_out = n; + _arcs[n].next_out = _nodes[v._id].first_out; + _nodes[v._id].first_out = n; - arcs[n | 1].next_out = nodes[u._id].first_out; - nodes[u._id].first_out = (n | 1); + _arcs[n | 1].next_out = _nodes[u._id].first_out; + _nodes[u._id].first_out = (n | 1); return Edge(n / 2); } void clear() { - arcs.clear(); - nodes.clear(); + _arcs.clear(); + _nodes.clear(); } }; @@ -701,7 +701,7 @@ /// then it is worth reserving space for this amount before starting /// to build the graph. /// \sa reserveEdge() - void reserveNode(int n) { nodes.reserve(n); }; + void reserveNode(int n) { _nodes.reserve(n); }; /// Reserve memory for edges. @@ -711,7 +711,7 @@ /// then it is worth reserving space for this amount before starting /// to build the graph. /// \sa reserveNode() - void reserveEdge(int m) { arcs.reserve(2 * m); }; + void reserveEdge(int m) { _arcs.reserve(2 * m); }; public: @@ -722,30 +722,30 @@ void saveSnapshot(Snapshot &s) { s._graph = this; - s.node_num = nodes.size(); - s.arc_num = arcs.size(); + s.node_num = _nodes.size(); + s.arc_num = _arcs.size(); } void restoreSnapshot(const Snapshot &s) { - while(s.arc_num dir; dir.push_back(arcFromId(n)); dir.push_back(arcFromId(n-1)); Parent::notifier(Arc()).erase(dir); - nodes[arcs[n-1].target].first_out=arcs[n].next_out; - nodes[arcs[n].target].first_out=arcs[n-1].next_out; - arcs.pop_back(); - arcs.pop_back(); + _nodes[_arcs[n-1].target].first_out=_arcs[n].next_out; + _nodes[_arcs[n].target].first_out=_arcs[n-1].next_out; + _arcs.pop_back(); + _arcs.pop_back(); } - while(s.node_num nodes; - std::vector arcs; + std::vector _nodes; + std::vector _arcs; int first_red, first_blue; int max_red, max_blue; @@ -915,39 +915,39 @@ SmartBpGraphBase() - : nodes(), arcs(), first_red(-1), first_blue(-1), + : _nodes(), _arcs(), first_red(-1), first_blue(-1), max_red(-1), max_blue(-1) {} typedef True NodeNumTag; typedef True EdgeNumTag; typedef True ArcNumTag; - int nodeNum() const { return nodes.size(); } + int nodeNum() const { return _nodes.size(); } int redNum() const { return max_red + 1; } int blueNum() const { return max_blue + 1; } - int edgeNum() const { return arcs.size() / 2; } - int arcNum() const { return arcs.size(); } + int edgeNum() const { return _arcs.size() / 2; } + int arcNum() const { return _arcs.size(); } - int maxNodeId() const { return nodes.size()-1; } + int maxNodeId() const { return _nodes.size()-1; } int maxRedId() const { return max_red; } int maxBlueId() const { return max_blue; } - int maxEdgeId() const { return arcs.size() / 2 - 1; } - int maxArcId() const { return arcs.size()-1; } + int maxEdgeId() const { return _arcs.size() / 2 - 1; } + int maxArcId() const { return _arcs.size()-1; } - bool red(Node n) const { return nodes[n._id].red; } - bool blue(Node n) const { return !nodes[n._id].red; } + bool red(Node n) const { return _nodes[n._id].red; } + bool blue(Node n) const { return !_nodes[n._id].red; } static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); } static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); } - Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); } - Node target(Arc a) const { return Node(arcs[a._id].target); } + Node source(Arc a) const { return Node(_arcs[a._id ^ 1].target); } + Node target(Arc a) const { return Node(_arcs[a._id].target); } RedNode redNode(Edge e) const { - return RedNode(arcs[2 * e._id].target); + return RedNode(_arcs[2 * e._id].target); } BlueNode blueNode(Edge e) const { - return BlueNode(arcs[2 * e._id + 1].target); + return BlueNode(_arcs[2 * e._id + 1].target); } static bool direction(Arc a) { @@ -959,7 +959,7 @@ } void first(Node& node) const { - node._id = nodes.size() - 1; + node._id = _nodes.size() - 1; } static void next(Node& node) { @@ -971,7 +971,7 @@ } void next(RedNode& node) const { - node._id = nodes[node._id].partition_next; + node._id = _nodes[node._id].partition_next; } void first(BlueNode& node) const { @@ -979,11 +979,11 @@ } void next(BlueNode& node) const { - node._id = nodes[node._id].partition_next; + node._id = _nodes[node._id].partition_next; } void first(Arc& arc) const { - arc._id = arcs.size() - 1; + arc._id = _arcs.size() - 1; } static void next(Arc& arc) { @@ -991,7 +991,7 @@ } void first(Edge& arc) const { - arc._id = arcs.size() / 2 - 1; + arc._id = _arcs.size() / 2 - 1; } static void next(Edge& arc) { @@ -999,23 +999,23 @@ } void firstOut(Arc &arc, const Node& v) const { - arc._id = nodes[v._id].first_out; + arc._id = _nodes[v._id].first_out; } void nextOut(Arc &arc) const { - arc._id = arcs[arc._id].next_out; + arc._id = _arcs[arc._id].next_out; } void firstIn(Arc &arc, const Node& v) const { - arc._id = ((nodes[v._id].first_out) ^ 1); + arc._id = ((_nodes[v._id].first_out) ^ 1); if (arc._id == -2) arc._id = -1; } void nextIn(Arc &arc) const { - arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1); + arc._id = ((_arcs[arc._id ^ 1].next_out) ^ 1); if (arc._id == -2) arc._id = -1; } void firstInc(Edge &arc, bool& d, const Node& v) const { - int de = nodes[v._id].first_out; + int de = _nodes[v._id].first_out; if (de != -1) { arc._id = de / 2; d = ((de & 1) == 1); @@ -1025,7 +1025,7 @@ } } void nextInc(Edge &arc, bool& d) const { - int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out); + int de = (_arcs[(arc._id * 2) | (d ? 1 : 0)].next_out); if (de != -1) { arc._id = de / 2; d = ((de & 1) == 1); @@ -1036,8 +1036,8 @@ } static int id(Node v) { return v._id; } - int id(RedNode v) const { return nodes[v._id].partition_index; } - int id(BlueNode v) const { return nodes[v._id].partition_index; } + int id(RedNode v) const { return _nodes[v._id].partition_index; } + int id(BlueNode v) const { return _nodes[v._id].partition_index; } static int id(Arc e) { return e._id; } static int id(Edge e) { return e._id; } @@ -1046,59 +1046,59 @@ static Edge edgeFromId(int id) { return Edge(id);} bool valid(Node n) const { - return n._id >= 0 && n._id < static_cast(nodes.size()); + return n._id >= 0 && n._id < static_cast(_nodes.size()); } bool valid(Arc a) const { - return a._id >= 0 && a._id < static_cast(arcs.size()); + return a._id >= 0 && a._id < static_cast(_arcs.size()); } bool valid(Edge e) const { - return e._id >= 0 && 2 * e._id < static_cast(arcs.size()); + return e._id >= 0 && 2 * e._id < static_cast(_arcs.size()); } RedNode addRedNode() { - int n = nodes.size(); - nodes.push_back(NodeT()); - nodes[n].first_out = -1; - nodes[n].red = true; - nodes[n].partition_index = ++max_red; - nodes[n].partition_next = first_red; + int n = _nodes.size(); + _nodes.push_back(NodeT()); + _nodes[n].first_out = -1; + _nodes[n].red = true; + _nodes[n].partition_index = ++max_red; + _nodes[n].partition_next = first_red; first_red = n; return RedNode(n); } BlueNode addBlueNode() { - int n = nodes.size(); - nodes.push_back(NodeT()); - nodes[n].first_out = -1; - nodes[n].red = false; - nodes[n].partition_index = ++max_blue; - nodes[n].partition_next = first_blue; + int n = _nodes.size(); + _nodes.push_back(NodeT()); + _nodes[n].first_out = -1; + _nodes[n].red = false; + _nodes[n].partition_index = ++max_blue; + _nodes[n].partition_next = first_blue; first_blue = n; return BlueNode(n); } Edge addEdge(RedNode u, BlueNode v) { - int n = arcs.size(); - arcs.push_back(ArcT()); - arcs.push_back(ArcT()); + int n = _arcs.size(); + _arcs.push_back(ArcT()); + _arcs.push_back(ArcT()); - arcs[n].target = u._id; - arcs[n | 1].target = v._id; + _arcs[n].target = u._id; + _arcs[n | 1].target = v._id; - arcs[n].next_out = nodes[v._id].first_out; - nodes[v._id].first_out = n; + _arcs[n].next_out = _nodes[v._id].first_out; + _nodes[v._id].first_out = n; - arcs[n | 1].next_out = nodes[u._id].first_out; - nodes[u._id].first_out = (n | 1); + _arcs[n | 1].next_out = _nodes[u._id].first_out; + _nodes[u._id].first_out = (n | 1); return Edge(n / 2); } void clear() { - arcs.clear(); - nodes.clear(); + _arcs.clear(); + _nodes.clear(); first_red = -1; first_blue = -1; max_blue = -1; @@ -1213,7 +1213,7 @@ /// then it is worth reserving space for this amount before starting /// to build the graph. /// \sa reserveEdge() - void reserveNode(int n) { nodes.reserve(n); }; + void reserveNode(int n) { _nodes.reserve(n); }; /// Reserve memory for edges. @@ -1223,7 +1223,7 @@ /// then it is worth reserving space for this amount before starting /// to build the graph. /// \sa reserveNode() - void reserveEdge(int m) { arcs.reserve(2 * m); }; + void reserveEdge(int m) { _arcs.reserve(2 * m); }; public: @@ -1234,47 +1234,47 @@ void saveSnapshot(Snapshot &s) { s._graph = this; - s.node_num = nodes.size(); - s.arc_num = arcs.size(); + s.node_num = _nodes.size(); + s.arc_num = _arcs.size(); } void restoreSnapshot(const Snapshot &s) { - while(s.arc_num dir; dir.push_back(arcFromId(n)); dir.push_back(arcFromId(n-1)); Parent::notifier(Arc()).erase(dir); - nodes[arcs[n-1].target].first_out=arcs[n].next_out; - nodes[arcs[n].target].first_out=arcs[n-1].next_out; - arcs.pop_back(); - arcs.pop_back(); + _nodes[_arcs[n-1].target].first_out=_arcs[n].next_out; + _nodes[_arcs[n].target].first_out=_arcs[n-1].next_out; + _arcs.pop_back(); + _arcs.pop_back(); } - while(s.node_num(soplex)) = *(lp.soplex); @@ -122,12 +122,12 @@ } void SoplexLp::_eraseColId(int i) { - cols.eraseIndex(i); - cols.relocateIndex(i, cols.maxIndex()); + _cols.eraseIndex(i); + _cols.relocateIndex(i, _cols.maxIndex()); } void SoplexLp::_eraseRowId(int i) { - rows.eraseIndex(i); - rows.relocateIndex(i, rows.maxIndex()); + _rows.eraseIndex(i); + _rows.relocateIndex(i, _rows.maxIndex()); } void SoplexLp::_getColName(int c, std::string &name) const { @@ -432,8 +432,8 @@ _col_names_ref.clear(); _row_names.clear(); _row_names_ref.clear(); - cols.clear(); - rows.clear(); + _cols.clear(); + _rows.clear(); _clear_temporals(); }