Diff [f179aa1045a4a179215d017a324f5177d72d7b2c:2236d00ca7785f6e8e7d164dbee7ddfe946a30d0] for / – LEMON

CMakeLists.txt

-                      r1197
+                      r1198
   CMAKE_POLICY(SET CMP0048 OLD)
 ENDIF(POLICY CMP0048)
+IF(POLICY CMP0043)
+  CMAKE_POLICY(SET CMP0043 OLD)
+ENDIF(POLICY CMP0043)
 IF(POLICY CMP0026)
 …
     FORCE )
+SET_DIRECTORY_PROPERTIES(PROPERTIES
+  COMPILE_DEFINITIONS_DEBUG "LEMON_ENABLE_DEBUG"
+  COMPILE_DEFINITIONS_MAINTAINER "LEMON_ENABLE_DEBUG"
+)
 INCLUDE(CheckTypeSize)
 …
 ENABLE_TESTING()
+INCLUDE(CheckCXXCompilerFlag)
+CHECK_CXX_COMPILER_FLAG("-std=c++11" LEMON_CXX11)
+IF(LEMON_CXX11)
+  SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
+ENDIF()
 IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")

doc/Doxyfile.in

-                      r1075
+                      r1145
 STRIP_FROM_PATH        = "@abs_top_srcdir@"
 STRIP_FROM_INC_PATH    = "@abs_top_srcdir@"
 SHORT_NAMES            = YES
+SHORT_NAMES            = NO
 JAVADOC_AUTOBRIEF      = NO
 QT_AUTOBRIEF           = NO
 …
 SUBGROUPING            = YES
 TYPEDEF_HIDES_STRUCT   = NO
-SYMBOL_CACHE_SIZE      = 0
 #---------------------------------------------------------------------------
 # Build related configuration options
 …
 MAX_INITIALIZER_LINES  = 5
 SHOW_USED_FILES        = NO
-SHOW_DIRECTORIES       = YES
 SHOW_FILES             = YES
 SHOW_NAMESPACES        = YES
 …
 HTML_COLORSTYLE_GAMMA  = 80
 HTML_TIMESTAMP         = YES
-HTML_ALIGN_MEMBERS     = YES
 HTML_DYNAMIC_SECTIONS  = YES
 GENERATE_DOCSET        = NO
 …
 ENUM_VALUES_PER_LINE   = 4
 GENERATE_TREEVIEW      = NO
-USE_INLINE_TREES       = NO
 TREEVIEW_WIDTH         = 250
 EXT_LINKS_IN_WINDOW    = NO
 …
 GENERATE_XML           = NO
 XML_OUTPUT             = xml
-XML_SCHEMA             =
-XML_DTD                =
 XML_PROGRAMLISTING     = YES
 #---------------------------------------------------------------------------
 …
 HAVE_DOT               = YES
 DOT_NUM_THREADS        = 0
 DOT_FONTNAME           = FreeSans
+DOT_FONTNAME           =
 DOT_FONTSIZE           = 10
 DOT_FONTPATH           =

doc/groups.dox

-                      r1093
+                      r1152
 /**
+@defgroup graph_isomorphism Graph Isomorphism
+@ingroup algs
+\brief Algorithms for testing (sub)graph isomorphism
+This group contains algorithms for finding isomorph copies of a
+given graph in another one, or simply check whether two graphs are isomorphic.
+The formal definition of subgraph isomorphism is as follows.
+We are given two graphs, \f$G_1=(V_1,E_1)\f$ and \f$G_2=(V_2,E_2)\f$. A
+function \f$f:V_1\longrightarrow V_2\f$ is called \e mapping or \e
+embedding if \f$f(u)\neq f(v)\f$ whenever \f$u\neq v\f$.
+The standard <em>Subgraph Isomorphism Problem (SIP)</em> looks for a
+mapping with the property that whenever \f$(u,v)\in E_1\f$, then
+\f$(f(u),f(v))\in E_2\f$.
+In case of <em>Induced Subgraph Isomorphism Problem (ISIP)</em> one
+also requires that if \f$(u,v)\not\in E_1\f$, then \f$(f(u),f(v))\not\in
+E_2\f$
+In addition, the graph nodes may be \e labeled, i.e. we are given two
+node labelings \f$l_1:V_1\longrightarrow L\f$ and \f$l_2:V_2\longrightarrow
+L\f$ and we require that \f$l_1(u)=l_2(f(u))\f$ holds for all nodes \f$u \in
+G_1\f$.
+*/
+/**
 @defgroup planar Planar Embedding and Drawing
 @ingroup algs

doc/named-param.dox

r440	r1142
26	26	function parameters by name also when you call the function. It is
27	27	especially comfortable in case of a function having tons of parameters
28		with natural default values. Sadly, C++ lack this amenity.
	28	with natural default values. Sadly, C++ lacks this amenity.
29	29
30	30	However, with a crafty trick and with some little

doc/references.bib

-                      r1051
+                      r1195
   pages =        {67--118}
+}
+@article{VF2PP,
+  author =       {Alp\'ar J\"uttner and  P\'eter Madarasi},
+  title =        {{VF2++} â An improved subgraph isomorphism algorithm},
+  journal =      {Discrete Applied Mathematics},
+  year =         {2018},
+  volume =       {242},
+  pages =        {69--81},
+  url =          {https://doi.org/10.1016/j.dam.2018.02.018}
+}
 …
   pages =        {587--612}
+}
+@article{cordella2004sub,
+  author =       {Cordella, Luigi P. and Foggia, Pasquale and Sansone,
+                  Carlo and Vento, Mario},
+  title =        {A (sub)graph isomorphism algorithm for matching
+                  large graphs},
+  journal =      {IEEE Transactions on Pattern Analysis and Machine
+                  Intelligence},
+  volume =       26,
+  number =       10,
+  pages =        {1367--1372},
+  year =         2004
+}

lemon/bellman_ford.h

-                      r1092
+                      r1131
 #include <lemon/maps.h>
 #include <lemon/path.h>
+#include <lemon/bits/stl_iterators.h>
 #include <limits>
 …
       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<ActiveIt, BellmanFord>
+    activeNodes() const {
+      return LemonRangeWrapper1<ActiveIt, BellmanFord>(*this);
+    }
     /// \name Query Functions

lemon/bits/edge_set_extender.h

-                      r1092
+                      r1131
     };
+    LemonRangeWrapper1<NodeIt, Digraph> nodes() const {
+      return LemonRangeWrapper1<NodeIt, Digraph>(*this);
+    }
     class ArcIt : public Arc {
 …
     };
+    LemonRangeWrapper1<ArcIt, Digraph> arcs() const {
+      return LemonRangeWrapper1<ArcIt, Digraph>(*this);
+    }
     class OutArcIt : public Arc {
 …
     };
+    LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {
+      return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);
+    }
     class InArcIt : public Arc {
 …
     };
+    LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {
+      return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);
+    }
     // \brief Base node of the iterator
 …
     };
+    LemonRangeWrapper1<NodeIt, Graph> nodes() const {
+      return LemonRangeWrapper1<NodeIt, Graph>(*this);
+    }
     class ArcIt : public Arc {
 …
     };
+    LemonRangeWrapper1<ArcIt, Graph> arcs() const {
+      return LemonRangeWrapper1<ArcIt, Graph>(*this);
+    }
     class OutArcIt : public Arc {
 …
     };
+    LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {
+      return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);
+    }
     class InArcIt : public Arc {
 …
     };
+    LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {
+      return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);
+    }
     class EdgeIt : public Parent::Edge {
 …
     };
+    LemonRangeWrapper1<EdgeIt, Graph> edges() const {
+      return LemonRangeWrapper1<EdgeIt, Graph>(*this);
+    }
     class IncEdgeIt : public Parent::Edge {
 …
+      }
     };
+    LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {
+      return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);
+    }
     // \brief Base node of the iterator

lemon/bits/graph_adaptor_extender.h

-                      r1092
+                      r1131
     };
+    LemonRangeWrapper1<NodeIt, Adaptor> nodes() const {
+      return LemonRangeWrapper1<NodeIt, Adaptor>(*this);
+    }
     class ArcIt : public Arc {
 …
     };
+    LemonRangeWrapper1<ArcIt, Adaptor> arcs() const {
+      return LemonRangeWrapper1<ArcIt, Adaptor>(*this);
+    }
 …
     };
+    LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {
+      return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);
+    }
     class InArcIt : public Arc {
 …
     };
+    LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {
+      return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);
+    }
     Node baseNode(const OutArcIt &e) const {
 …
     };
+    LemonRangeWrapper1<NodeIt, Adaptor> nodes() const {
+      return LemonRangeWrapper1<NodeIt, Adaptor>(*this);
+    }
     class ArcIt : public Arc {
 …
     };
+    LemonRangeWrapper1<ArcIt, Adaptor> arcs() const {
+      return LemonRangeWrapper1<ArcIt, Adaptor>(*this);
+    }
 …
     };
+    LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {
+      return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);
+    }
     class InArcIt : public Arc {
 …
     };
+    LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {
+      return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);
+    }
     class EdgeIt : public Parent::Edge {
       const Adaptor* _adaptor;
 …
     };
+    LemonRangeWrapper1<EdgeIt, Adaptor> edges() const {
+      return LemonRangeWrapper1<EdgeIt, Adaptor>(*this);
+    }
     class IncEdgeIt : public Edge {
 …
     };
+    LemonRangeWrapper2<IncEdgeIt, Adaptor, Node> incEdges(const Node& u) const {
+      return LemonRangeWrapper2<IncEdgeIt, Adaptor, Node>(*this, u);
+    }
     Node baseNode(const OutArcIt &a) const {
       return Parent::source(a);

lemon/bits/graph_extender.h

-                      r1092
+                      r1130
 #include <lemon/concepts/maps.h>
+#include <lemon/bits/stl_iterators.h>
 //\ingroup graphbits
 //\file
 …
     };
+    LemonRangeWrapper1<NodeIt, Digraph> nodes() const {
+      return LemonRangeWrapper1<NodeIt, Digraph>(*this);
+    }
     class ArcIt : public Arc {
 …
     };
+    LemonRangeWrapper1<ArcIt, Digraph> arcs() const {
+      return LemonRangeWrapper1<ArcIt, Digraph>(*this);
+    }
 …
     };
+    LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {
+      return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);
+    }
     class InArcIt : public Arc {
 …
     };
+    LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {
+      return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);
+    }
     // \brief Base node of the iterator
 …
     };
+    LemonRangeWrapper1<NodeIt, Graph> nodes() const {
+      return LemonRangeWrapper1<NodeIt, Graph>(*this);
+    }
     class ArcIt : public Arc {
 …
     };
+    LemonRangeWrapper1<ArcIt, Graph> arcs() const {
+      return LemonRangeWrapper1<ArcIt, Graph>(*this);
+    }
 …
     };
+    LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {
+      return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);
+    }
     class InArcIt : public Arc {
 …
     };
+    LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {
+      return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);
+    }
     class EdgeIt : public Parent::Edge {
 …
     };
+    LemonRangeWrapper1<EdgeIt, Graph> edges() const {
+      return LemonRangeWrapper1<EdgeIt, Graph>(*this);
+    }
     class IncEdgeIt : public Parent::Edge {
 …
+      }
     };
+    LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {
+      return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);
+    }
     // \brief Base node of the iterator
 …
     };
+    LemonRangeWrapper1<NodeIt, BpGraph> nodes() const {
+      return LemonRangeWrapper1<NodeIt, BpGraph>(*this);
+    }
     class RedNodeIt : public RedNode {
       const BpGraph* _graph;
 …
     };
+    LemonRangeWrapper1<RedNodeIt, BpGraph> redNodes() const {
+      return LemonRangeWrapper1<RedNodeIt, BpGraph>(*this);
+    }
     class BlueNodeIt : public BlueNode {
       const BpGraph* _graph;
 …
     };
+    LemonRangeWrapper1<BlueNodeIt, BpGraph> blueNodes() const {
+      return LemonRangeWrapper1<BlueNodeIt, BpGraph>(*this);
+    }
     class ArcIt : public Arc {
 …
     };
+    LemonRangeWrapper1<ArcIt, BpGraph> arcs() const {
+      return LemonRangeWrapper1<ArcIt, BpGraph>(*this);
+    }
 …
     };
+    LemonRangeWrapper2<OutArcIt, BpGraph, Node> outArcs(const Node& u) const {
+      return LemonRangeWrapper2<OutArcIt, BpGraph, Node>(*this, u);
+    }
     class InArcIt : public Arc {
 …
     };
+    LemonRangeWrapper2<InArcIt, BpGraph, Node> inArcs(const Node& u) const {
+      return LemonRangeWrapper2<InArcIt, BpGraph, Node>(*this, u);
+    }
     class EdgeIt : public Parent::Edge {
 …
     };
+    LemonRangeWrapper1<EdgeIt, BpGraph> edges() const {
+      return LemonRangeWrapper1<EdgeIt, BpGraph>(*this);
+    }
     class IncEdgeIt : public Parent::Edge {
 …
+      }
     };
+    LemonRangeWrapper2<IncEdgeIt, BpGraph, Node> incEdges(const Node& u) const {
+      return LemonRangeWrapper2<IncEdgeIt, BpGraph, Node>(*this, u);
+    }
     // \brief Base node of the iterator

lemon/bits/path_dump.h

r1092	r1132
62	62	}
63	63
64		operator ~~const~~ typename Digraph::Arc() const {
	64	operator typename Digraph::Arc() const {
65	65	return path->predMap[current];
66	66	}

lemon/cbc.cc

r1092	r1130
112	112
113	113	void CbcMip::_eraseColId(int i) {
114		cols.eraseIndex(i);
	114	_cols.eraseIndex(i);
115	115	}
116	116
117	117	void CbcMip::_eraseRowId(int i) {
118		rows.eraseIndex(i);
	118	_rows.eraseIndex(i);
119	119	}
120	120

lemon/clp.cc

-                      r1092
+                      r1130
   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);
 …
   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);
+  }

lemon/clp.h

-                      r1092
+                      r1130
     ///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)); }
   };

lemon/concepts/bpgraph.h

-                      r1092
+                      r1130
 #include <lemon/concept_check.h>
 #include <lemon/core.h>
+#include <lemon/bits/stl_iterators.h>
 namespace lemon {
 …
       };
+      /// \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<RedNodeIt, BpGraph> redNodes() const {
+        return LemonRangeWrapper1<RedNodeIt, BpGraph>(*this);
+      }
       /// Iterator class for the blue nodes.
 …
       };
+      /// \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<BlueNodeIt, BpGraph> blueNodes() const {
+        return LemonRangeWrapper1<BlueNodeIt, BpGraph>(*this);
+      }
       /// Iterator class for the nodes.
 …
         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<NodeIt, BpGraph> nodes() const {
+        return LemonRangeWrapper1<NodeIt, BpGraph>(*this);
+      }
 …
         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<EdgeIt, BpGraph> edges() const {
+        return LemonRangeWrapper1<EdgeIt, BpGraph>(*this);
+      }
       /// Iterator class for the incident edges of a node.
 …
       };
+      /// \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<IncEdgeIt, BpGraph, Node> incEdges(const Node& u) const {
+        return LemonRangeWrapper2<IncEdgeIt, BpGraph, Node>(*this, u);
+      }
       /// The arc type of the graph
 …
       };
+      /// \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<ArcIt, BpGraph> arcs() const {
+        return LemonRangeWrapper1<ArcIt, BpGraph>(*this);
+      }
       /// Iterator class for the outgoing arcs of a node.
 …
       };
+      /// \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<OutArcIt, BpGraph, Node> outArcs(const Node& u) const {
+        return LemonRangeWrapper2<OutArcIt, BpGraph, Node>(*this, u);
+      }
       /// Iterator class for the incoming arcs of a node.
 …
         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<InArcIt, BpGraph, Node> inArcs(const Node& u) const {
+        return LemonRangeWrapper2<InArcIt, BpGraph, Node>(*this, u);
+      }
       /// \brief Standard graph map type for the nodes.

lemon/concepts/digraph.h

-                      r1093
+                      r1130
 #include <lemon/concept_check.h>
 #include <lemon/concepts/graph_components.h>
+#include <lemon/bits/stl_iterators.h>
 namespace lemon {
 …
       };
+      /// \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<NodeIt, Digraph> nodes() const {
+        return LemonRangeWrapper1<NodeIt, Digraph>(*this);
+      }
       /// The arc type of the digraph
 …
       };
+      /// \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<OutArcIt, Digraph, Node> outArcs(const Node& u) const {
+        return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);
+      }
       /// Iterator class for the incoming arcs of a node.
 …
       };
+      /// \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<InArcIt, Digraph, Node> inArcs(const Node& u) const {
+        return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);
+      }
       /// Iterator class for the arcs.
 …
         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<ArcIt, Digraph> arcs() const {
+        return LemonRangeWrapper1<ArcIt, Digraph>(*this);
+      }
       /// \brief The source node of the arc.

lemon/concepts/graph.h

-                      r1093
+                      r1130
 #include <lemon/concept_check.h>
 #include <lemon/core.h>
+#include <lemon/bits/stl_iterators.h>
 namespace lemon {
 …
       };
+      /// \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<NodeIt, Graph> nodes() const {
+        return LemonRangeWrapper1<NodeIt, Graph>(*this);
+      }
       /// The edge type of the graph
 …
         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<EdgeIt, Graph> edges() const {
+        return LemonRangeWrapper1<EdgeIt, Graph>(*this);
+      }
       /// Iterator class for the incident edges of a node.
 …
       };
+      /// \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<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {
+        return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);
+      }
       /// The arc type of the graph
 …
         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<ArcIt, Graph> arcs() const {
+        return LemonRangeWrapper1<ArcIt, Graph>(*this);
+      }
       /// Iterator class for the outgoing arcs of a node.
 …
       };
+      /// \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<OutArcIt, Graph, Node> outArcs(const Node& u) const {
+        return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);
+      }
       /// Iterator class for the incoming arcs of a node.
 …
         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<InArcIt, Graph, Node> inArcs(const Node& u) const {
+        return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);
+      }
       /// \brief Standard graph map type for the nodes.

lemon/concepts/path.h

-                      r1197
+                      r1198
 #include <lemon/core.h>
 #include <lemon/concept_check.h>
+#include <lemon/bits/stl_iterators.h>
 namespace lemon {
 …
       };
+      /// \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<ArcIt, Path> arcs() const {
+        return LemonRangeWrapper1<ArcIt, Path>(*this);
+      }
       template <typename _Path>
       struct Constraints {
 …
       };
+      /// \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<ArcIt, PathDumper> arcs() const {
+        return LemonRangeWrapper1<ArcIt, PathDumper>(*this);
+      }
       /// \brief LEMON style iterator for enumerating the arcs of a path
 …
       };
+      /// \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<RevArcIt, PathDumper> revArcs() const {
+        return LemonRangeWrapper1<RevArcIt, PathDumper>(*this);
+      }
       template <typename _Path>
       struct Constraints {

lemon/config.h.in

r1197	r1198
5	5
6	6	#cmakedefine LEMON_HAVE_LONG_LONG 1
	7
	8	#cmakedefine LEMON_CXX11 1
7	9
8	10	#cmakedefine LEMON_WIN32 1

lemon/cplex.cc

-                      r1139
+                      r1140
     int status;
     _prob = CPXcloneprob(cplexEnv(), cplex._prob, &status);
     rows = cplex.rows;
     cols = cplex.cols;
+    _rows = cplex._rows;
+    _cols = cplex._cols;
     messageLevel(MESSAGE_NOTHING);
+  }
 …
                          ExprIterator e, Value ub) {
     int i = CPXgetnumrows(cplexEnv(), _prob);
+    int rmatbeg = 0;
+    std::vector<int> indices;
+    std::vector<Value> values;
+    for(ExprIterator it=b; it!=e; ++it) {
+      indices.push_back(it->first);
+      values.push_back(it->second);
+    }
     if (lb == -INF) {
       const char s = 'L';
+      CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
+      CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &ub, &s,
+                 &rmatbeg, &indices.front(), &values.front(), 0, 0);
     } else if (ub == INF) {
       const char s = 'G';
+      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
+      CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &lb, &s,
+                 &rmatbeg, &indices.front(), &values.front(), 0, 0);
     } else if (lb == ub){
       const char s = 'E';
+      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
+      CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &lb, &s,
+                 &rmatbeg, &indices.front(), &values.front(), 0, 0);
     } else {
       const char s = 'R';
       double len = ub - lb;
+      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
+    }
+    std::vector<int> indices;
+    std::vector<int> rowlist;
+    std::vector<Value> values;
+    for(ExprIterator it=b; it!=e; ++it) {
+      indices.push_back(it->first);
+      values.push_back(it->second);
+      rowlist.push_back(i);
+    }
+    CPXchgcoeflist(cplexEnv(), _prob, values.size(),
+                   &rowlist.front(), &indices.front(), &values.front());
+      CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &ub, &s,
+                 &rmatbeg, &indices.front(), &values.front(), 0, 0);
+      CPXchgrngval(cplexEnv(), _prob, 1, &i, &len);
+    }
     return i;
+  }
 …
   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);
+  }

lemon/glpk.cc

-                      r1092
+                      r1130
     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);
+  }
 …
   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);
+  }

lemon/glpk.h

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

lemon/lgf_reader.h

-                      r1092
+                      r1161
   ///
   ///\code
   /// DigraphReader<DGR>(digraph, std::cin).
   ///   nodeMap("coordinates", coord_map).
   ///   arcMap("capacity", cap_map).
   ///   node("source", src).
   ///   node("target", trg).
   ///   attribute("caption", caption).
   ///   run();
+  /// DigraphReader<DGR>(digraph, std::cin)
+  ///   .nodeMap("coordinates", coord_map)
+  ///   .arcMap("capacity", cap_map)
+  ///   .node("source", src)
+  ///   .node("target", trg)
+  ///   .attribute("caption", caption)
+  ///   .run();
   ///\endcode
   ///
 …
   ///\code
   ///ListDigraph digraph;
   ///ListDigraph::ArcMap<int> cm(digraph);
+  ///ListDigraph::ArcMap<int> cap(digraph);
   ///ListDigraph::Node src, trg;
   ///digraphReader(digraph, std::cin).
   ///  arcMap("capacity", cap).
   ///  node("source", src).
   ///  node("target", trg).
   ///  run();
+  ///digraphReader(digraph, std::cin)
+  ///  .arcMap("capacity", cap)
+  ///  .node("source", src)
+  ///  .node("target", trg)
+  ///  .run();
   ///\endcode
   ///
 …
   ///ListGraph graph;
   ///ListGraph::EdgeMap<int> weight(graph);
   ///graphReader(graph, std::cin).
   ///  edgeMap("weight", weight).
   ///  run();
+  ///graphReader(graph, std::cin)
+  ///  .edgeMap("weight", weight)
+  ///  .run();
   ///\endcode
   ///
 …
   ///ListBpGraph graph;
   ///ListBpGraph::EdgeMap<int> weight(graph);
   ///bpGraphReader(graph, std::cin).
   ///  edgeMap("weight", weight).
   ///  run();
+  ///bpGraphReader(graph, std::cin)
+  ///  .edgeMap("weight", weight)
+  ///  .run();
   ///\endcode
   ///

lemon/lgf_writer.h

-                      r1092
+                      r1161
   ///
   ///\code
   /// DigraphWriter<DGR>(digraph, std::cout).
   ///   nodeMap("coordinates", coord_map).
   ///   nodeMap("size", size).
   ///   nodeMap("title", title).
   ///   arcMap("capacity", cap_map).
   ///   node("source", src).
   ///   node("target", trg).
   ///   attribute("caption", caption).
   ///   run();
+  /// DigraphWriter<DGR>(digraph, std::cout)
+  ///   .nodeMap("coordinates", coord_map)
+  ///   .nodeMap("size", size)
+  ///   .nodeMap("title", title)
+  ///   .arcMap("capacity", cap_map)
+  ///   .node("source", src)
+  ///   .node("target", trg)
+  ///   .attribute("caption", caption)
+  ///   .run();
   ///\endcode
   ///
 …
   ///ListDigraph::Node src, trg;
   ///  // Setting the capacity map and source and target nodes
   ///digraphWriter(digraph, std::cout).
   ///  arcMap("capacity", cap).
   ///  node("source", src).
   ///  node("target", trg).
   ///  run();
+  ///digraphWriter(digraph, std::cout)
+  ///  .arcMap("capacity", cap)
+  ///  .node("source", src)
+  ///  .node("target", trg)
+  ///  .run();
   ///\endcode
   ///
 …
   ///ListGraph::EdgeMap<int> weight(graph);
   ///  // Setting the weight map
   ///graphWriter(graph, std::cout).
   ///  edgeMap("weight", weight).
   ///  run();
+  ///graphWriter(graph, std::cout)
+  ///  .edgeMap("weight", weight)
+  ///  .run();
   ///\endcode
   ///
 …
   ///ListBpGraph::EdgeMap<int> weight(graph);
   ///  // Setting the weight map
   ///bpGraphWriter(graph, std::cout).
   ///  edgeMap("weight", weight).
   ///  run();
+  ///bpGraphWriter(graph, std::cout)
+  ///  .edgeMap("weight", weight)
+  ///  .run();
   ///\endcode
   ///

lemon/list_graph.h

-                      r1148
+                      r1149
     };
     std::vector<NodeT> nodes;
+    std::vector<NodeT> _nodes;
     int first_node;
 …
     int first_free_node;
     std::vector<ArcT> arcs;
+    std::vector<ArcT> _arcs;
     int first_free_arc;
 …
     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 next(Node& node) const {
       node.id = nodes[node.id].next;
+      node.id = _nodes[node.id].next;
+    }
 …
       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;
+    }
 …
     bool valid(Node n) const {
       return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
         nodes[n.id].prev != -2;
+      return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
+        _nodes[n.id].prev != -2;
+    }
     bool valid(Arc a) const {
       return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
         arcs[a.id].prev_in != -2;
+      return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
+        _arcs[a.id].prev_in != -2;
+    }
 …
       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;
+      }
       nodes[n].next = first_node;
       if(first_node != -1) nodes[first_node].prev = n;
+        first_free_node = _nodes[n].next;
+      }
+      _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);
 …
       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;
+      }
       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].prev_in = arcs[n].prev_out = -1;
       nodes[u.id].first_out = nodes[v.id].first_in = n;
+        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].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;
       return Arc(n);
 …
       int n = node.id;
       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;
       } else {
         first_node = nodes[n].next;
+      }
       nodes[n].next = first_free_node;
+      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;
+      } else {
+        first_node = _nodes[n].next;
+      }
+      _nodes[n].next = first_free_node;
       first_free_node = n;
       nodes[n].prev = -2;
+      _nodes[n].prev = -2;
+    }
 …
       int n = arc.id;
       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;
       } else {
         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].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;
+      }
       arcs[n].next_in = first_free_arc;
+      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;
+      } else {
+        _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].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;
+      }
+      _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;
+    }
 …
     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;
+      }
       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;
+      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;
+    }
     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;
+      }
       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;
+      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;
+    }
 …
     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);
 …
     /// to build the digraph.
     /// \sa reserveArc()
     void reserveNode(int n) { nodes.reserve(n); };
+    void reserveNode(int n) { _nodes.reserve(n); };
     /// Reserve memory for arcs.
 …
     /// 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
 …
     };
     std::vector<NodeT> nodes;
+    std::vector<NodeT> _nodes;
     int first_node;
 …
     int first_free_node;
     std::vector<ArcT> arcs;
+    std::vector<ArcT> _arcs;
     int first_free_arc;
 …
     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) {
 …
     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;
+      }
       e.id = (n == -1) ? -1 : nodes[n].first_out;
+      while (n != -1 && _nodes[n].first_out == -1) {
+        n = _nodes[n].next;
+      }
+      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;
       } else {
         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;
+      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;
+        }
+        e.id = (n == -1) ? -1 : _nodes[n].first_out;
+      }
+    }
 …
       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) {
 …
           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) {
 …
         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) {
 …
           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;
 …
+    }
     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;
 …
     bool valid(Node n) const {
       return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
         nodes[n.id].prev != -2;
+      return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
+        _nodes[n.id].prev != -2;
+    }
     bool valid(Arc a) const {
       return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
         arcs[a.id].prev_out != -2;
+      return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
+        _arcs[a.id].prev_out != -2;
+    }
     bool valid(Edge e) const {
       return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
         arcs[2 * e.id].prev_out != -2;
+      return e.id >= 0 && 2 * e.id < static_cast<int>(_arcs.size()) &&
+        _arcs[2 * e.id].prev_out != -2;
+    }
 …
       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;
+      }
       nodes[n].next = first_node;
       if (first_node != -1) nodes[first_node].prev = n;
+        first_free_node = _nodes[n].next;
+      }
+      _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);
 …
       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;
+      }
       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 | 1].prev_out = -1;
       nodes[u.id].first_out = (n | 1);
+        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].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);
       return Edge(n / 2);
 …
       int n = node.id;
       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;
       } else {
         first_node = nodes[n].next;
+      }
       nodes[n].next = first_free_node;
+      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;
+      } else {
+        first_node = _nodes[n].next;
+      }
+      _nodes[n].next = first_free_node;
       first_free_node = n;
       nodes[n].prev = -2;
+      _nodes[n].prev = -2;
+    }
 …
       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].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;
+      }
       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;
       } else {
         nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
+      }
       arcs[n].next_out = first_free_arc;
+      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;
+      } else {
+        _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].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;
+      }
+      _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;
+    }
 …
     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].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;
+      }
       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;
+      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;
+      } else {
+        _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;
+      }
+      _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].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;
+      }
       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);
+      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;
+      } else {
+        _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);
+      }
+      _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);
+    }
 …
     ListGraph() {}
     typedef Parent::OutArcIt IncEdgeIt;
+    typedef Parent::IncEdgeIt IncEdgeIt;
     /// \brief Add a new node to the graph.
 …
     /// to build the graph.
     /// \sa reserveEdge()
     void reserveNode(int n) { nodes.reserve(n); };
+    void reserveNode(int n) { _nodes.reserve(n); };
     /// Reserve memory for edges.
 …
     /// 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
 …
     };
     std::vector<NodeT> nodes;
+    std::vector<NodeT> _nodes;
     int first_node, first_red, first_blue;
 …
     int first_free_red, first_free_blue;
     std::vector<ArcT> arcs;
+    std::vector<ArcT> _arcs;
     int first_free_arc;
 …
     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);
+    }
 …
     void next(Node& node) const {
       node.id = nodes[node.id].next;
+      node.id = _nodes[node.id].next;
+    }
 …
     void next(RedNode& node) const {
       node.id = nodes[node.id].partition_next;
+      node.id = _nodes[node.id].partition_next;
+    }
 …
     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;
+      }
       e.id = (n == -1) ? -1 : nodes[n].first_out;
+      while (n != -1 && _nodes[n].first_out == -1) {
+        n = _nodes[n].next;
+      }
+      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;
       } else {
         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;
+      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;
+        }
+        e.id = (n == -1) ? -1 : _nodes[n].first_out;
+      }
+    }
 …
       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) {
 …
           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) {
 …
         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) {
 …
           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;
 …
+    }
     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;
 …
     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; }
 …
     bool valid(Node n) const {
       return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
         nodes[n.id].prev != -2;
+      return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
+        _nodes[n.id].prev != -2;
+    }
     bool valid(Arc a) const {
       return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
         arcs[a.id].prev_out != -2;
+      return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
+        _arcs[a.id].prev_out != -2;
+    }
     bool valid(Edge e) const {
       return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
         arcs[2 * e.id].prev_out != -2;
+      return e.id >= 0 && 2 * e.id < static_cast<int>(_arcs.size()) &&
+        _arcs[2 * e.id].prev_out != -2;
+    }
 …
       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;
+      }
       nodes[n].next = first_node;
       if (first_node != -1) nodes[first_node].prev = n;
+        first_free_red = _nodes[n].next;
+      }
+      _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);
 …
       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;
+      }
       nodes[n].next = first_node;
       if (first_node != -1) nodes[first_node].prev = n;
+        first_free_blue = _nodes[n].next;
+      }
+      _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);
 …
       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;
+      }
       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 | 1].prev_out = -1;
       nodes[u.id].first_out = (n | 1);
+        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].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);
       return Edge(n / 2);
 …
       int n = node.id;
       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;
       } else {
         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_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].next != -1) {
+        _nodes[_nodes[n].next].prev = _nodes[n].prev;
+      }
+      if(_nodes[n].prev != -1) {
+        _nodes[_nodes[n].prev].next = _nodes[n].next;
+      } else {
+        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_prev != -1) {
+        _nodes[_nodes[n].partition_prev].partition_next = _nodes[n].partition_next;
+      } else {
+        if (_nodes[n].red) {
+          first_red = _nodes[n].partition_next;
         } else {
           first_blue = nodes[n].partition_next;
+        }
+      }
       if (nodes[n].red) {
         nodes[n].next = first_free_red;
+          first_blue = _nodes[n].partition_next;
+        }
+      }
+      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;
+    }
 …
       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].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;
+      }
       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;
       } else {
         nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
+      }
       arcs[n].next_out = first_free_arc;
+      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;
+      } else {
+        _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].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;
+      }
+      _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;
 …
     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].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;
+      }
       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);
+      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;
+      } else {
+        _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);
+      }
+      _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].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;
+      }
       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;
+       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;
+      } else {
+        _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;
+      }
+      _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;
+    }
 …
     ListBpGraph() {}
     typedef Parent::OutArcIt IncEdgeIt;
+    typedef Parent::IncEdgeIt IncEdgeIt;
     /// \brief Add a new red node to the graph.
 …
     /// to build the graph.
     /// \sa reserveEdge()
     void reserveNode(int n) { nodes.reserve(n); };
+    void reserveNode(int n) { _nodes.reserve(n); };
     /// Reserve memory for edges.
 …
     /// 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

lemon/lp_base.h

-                      r1092
+                      r1144
 #include<lemon/bits/solver_bits.h>
+#include<lemon/bits/stl_iterators.h>
 ///\file
 ///\brief The interface of the LP solver interface.
 …
   protected:
     _solver_bits::VarIndex rows;
     _solver_bits::VarIndex cols;
+    _solver_bits::VarIndex _rows;
+    _solver_bits::VarIndex _cols;
   public:
 …
       ColIt(const LpBase &solver) : _solver(&solver)
+      {
         _solver->cols.firstItem(_id);
+        _solver->_cols.firstItem(_id);
+      }
       /// Invalid constructor \& conversion
 …
       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);
+    ///\endcode
+    LemonRangeWrapper1<ColIt, LpBase> cols() {
+      return LemonRangeWrapper1<ColIt, LpBase>(*this);
+    }
     /// \brief Returns the ID of the column.
 …
       RowIt(const LpBase &solver) : _solver(&solver)
+      {
         _solver->rows.firstItem(_id);
+        _solver->_rows.firstItem(_id);
+      }
       /// Invalid constructor \& conversion
 …
       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);
+    ///\endcode
+    LemonRangeWrapper1<RowIt, LpBase> rows() {
+      return LemonRangeWrapper1<RowIt, LpBase>(*this);
+    }
     /// \brief Returns the ID of the row.
 …
     ///This data structure represents a column of the matrix,
     ///thas is it strores a linear expression of the dual variables
     ///(\ref Row "Row"s).
+    ///(\ref LpBase::Row "Row"s).
     ///
     ///There are several ways to access and modify the contents of this
 …
     ///(This code computes the sum of all coefficients).
     ///- Numbers (<tt>double</tt>'s)
     ///and variables (\ref Row "Row"s) directly convert to an
+    ///and variables (\ref LpBase::Row "Row"s) directly convert to an
     ///\ref DualExpr and the usual linear operations are defined, so
     ///\code
 …
     //Abstract virtual functions
     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 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 int _addCol() = 0;
 …
     Value obj_const_comp;
     LpBase() : rows(), cols(), obj_const_comp(0) {}
+    LpBase() : _rows(), _cols(), obj_const_comp(0) {}
   public:
 …
     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));
+    }
 …
     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;
+    }
 …
     ///\param t can be
     ///- a standard STL compatible iterable container with
     ///\ref Row as its \c values_type like
+    ///\ref LpBase::Row "Row" as its \c values_type like
     ///\code
     ///std::vector<LpBase::Row>
 …
     ///\endcode
     ///- a standard STL compatible iterable container with
     ///\ref Row as its \c mapped_type like
+    ///\ref LpBase::Row "Row" as its \c mapped_type like
     ///\code
     ///std::map<AnyType,LpBase::Row>
 …
     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);
+    }
 …
     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;
+    }
 …
       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;
+    }
 …
       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;
 …
     ///\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)));
+    }
 …
     std::string colName(Col c) const {
       std::string name;
       _getColName(cols(id(c)), name);
+      _getColName(_cols(id(c)), name);
       return name;
+    }
 …
     ///\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);
+    }
 …
     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);
+    }
 …
     std::string rowName(Row r) const {
       std::string name;
       _getRowName(rows(id(r)), name);
+      _getRowName(_rows(id(r)), name);
       return name;
+    }
 …
     ///\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);
+    }
 …
     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);
+    }
 …
     ///\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);
+    }
 …
     ///\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)));
+    }
 …
     /// Value or -\ref INF.
     void colLowerBound(Col c, Value value) {
       _setColLowerBound(cols(id(c)),value);
+      _setColLowerBound(_cols(id(c)),value);
+    }
 …
     ///\return The lower bound for column \c c
     Value colLowerBound(Col c) const {
       return _getColLowerBound(cols(id(c)));
+      return _getColLowerBound(_cols(id(c)));
+    }
 …
     /// Value or \ref INF.
     void colUpperBound(Col c, Value value) {
       _setColUpperBound(cols(id(c)),value);
+      _setColUpperBound(_cols(id(c)),value);
     };
 …
     /// \return The upper bound for column \c c
     Value colUpperBound(Col c) const {
       return _getColUpperBound(cols(id(c)));
+      return _getColUpperBound(_cols(id(c)));
+    }
 …
     /// 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);
+    }
 …
     /// Value or -\ref INF.
     void rowLowerBound(Row r, Value value) {
       _setRowLowerBound(rows(id(r)),value);
+      _setRowLowerBound(_rows(id(r)),value);
+    }
 …
     ///\return The lower bound for row \c r
     Value rowLowerBound(Row r) const {
       return _getRowLowerBound(rows(id(r)));
+      return _getRowLowerBound(_rows(id(r)));
+    }
 …
     /// Value or -\ref INF.
     void rowUpperBound(Row r, Value value) {
       _setRowUpperBound(rows(id(r)),value);
+      _setRowUpperBound(_rows(id(r)),value);
+    }
 …
     ///\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
 …
     ///
     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;
+    }
 …
     Expr obj() const {
       Expr e;
       _getObjCoeffs(InsertIterator(e.comps, cols));
+      _getObjCoeffs(InsertIterator(e.comps, _cols));
       *e = obj_const_comp;
       return e;
 …
     ///Clear the problem
     void clear() { _clear(); rows.clear(); cols.clear(); }
+    void clear() { _clear(); _rows.clear(); _cols.clear(); }
     /// Set the message level of the solver
 …
     /// 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
 …
     /// \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
 …
     /// \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
 …
     ///
     void colType(Col c, ColTypes col_type) {
       _setColType(cols(id(c)),col_type);
+      _setColType(_cols(id(c)),col_type);
+    }
 …
     ///
     ColTypes colType(Col c) const {
       return _getColType(cols(id(c)));
+      return _getColType(_cols(id(c)));
+    }
     ///@}
 …
     ///  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

lemon/maps.h

-                      r1092
+                      r1130
 #include <lemon/core.h>
+#include <lemon/bits/stl_iterators.h>
 ///\file
 …
     };
+    /// \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<TrueIt, IterableBoolMap>
+    trueKeys() {
+      return LemonRangeWrapper1<TrueIt, IterableBoolMap>(*this);
+    }
     /// \brief Iterator for the keys mapped to \c false.
     ///
 …
       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<FalseIt, IterableBoolMap>
+    falseKeys() {
+      return LemonRangeWrapper1<FalseIt, IterableBoolMap>(*this);
+    }
     /// \brief Iterator for the keys mapped to a given value.
 …
       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<ItemIt, IterableBoolMap, bool>
+    items(bool value) {
+      return LemonRangeWrapper2<ItemIt, IterableBoolMap, bool>(*this, value);
+    }
   protected:
 …
     };
+    /// \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<ItemIt, IterableIntMap, int>
+    items(int value) {
+      return LemonRangeWrapper2<ItemIt, IterableIntMap, int>(*this, value);
+    }
   protected:
 …
     };
+    /// \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<ItemIt, IterableValueMap, V>
+    items(const V& value) {
+      return LemonRangeWrapper2<ItemIt, IterableValueMap, V>(*this, value);
+    }
   protected:

lemon/path.h

-                      r1092
+                      r1130
 #include <lemon/core.h>
 #include <lemon/concepts/path.h>
+#include <lemon/bits/stl_iterators.h>
 namespace lemon {
 …
       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<ArcIt, Path> arcs() const {
+      return LemonRangeWrapper1<ArcIt, Path>(*this);
+    }
     /// \brief Length of the path.
 …
     };
+    /// \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<ArcIt, SimplePath> arcs() const {
+      return LemonRangeWrapper1<ArcIt, SimplePath>(*this);
+    }
     /// \brief Length of the path.
     int length() const { return data.size(); }
 …
       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<ArcIt, ListPath> arcs() const {
+      return LemonRangeWrapper1<ArcIt, ListPath>(*this);
+    }
     /// \brief The n-th arc.
 …
     ///
     /// 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);
+    }
 …
     /// This path can be initialized from any other path type.
     template <typename CPath>
     StaticPath(const CPath& cpath) : arcs(0) {
+    StaticPath(const CPath& cpath) : _arcs(0) {
       pathCopy(cpath, *this);
+    }
 …
     /// Destructor of the path
     ~StaticPath() {
       if (arcs) delete[] arcs;
+      if (_arcs) delete[] _arcs;
+    }
 …
       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<ArcIt, StaticPath> arcs() const {
+      return LemonRangeWrapper1<ArcIt, StaticPath>(*this);
+    }
     /// \brief The n-th arc.
 …
     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
     const Arc& nth(int n) const {
       return arcs[n];
+      return _arcs[n];
+    }
 …
     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];
+    }
 …
     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;
+      }
 …
     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;
   };
 …
   };
+  /// \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<typename Path>
+  LemonRangeWrapper2<PathNodeIt<Path>, typename Path::Digraph, Path>
+      pathNodes(const typename Path::Digraph &g, const Path &p) {
+    return
+        LemonRangeWrapper2<PathNodeIt<Path>, typename Path::Digraph, Path>(g,p);
+  }
   ///@}

lemon/random.h

-                      r1178
+                      r1185
       static const Word loMask = (1u << 31) - 1;
       static const Word hiMask = ~loMask;
       static Word tempering(Word rnd) {
 …
     private:
       void fillState() {
         static const Word mask[2] = { 0x0ul, RandomTraits<Word>::mask };
 …
         current = state + length;
         register Word *curr = state + length - 1;
         register long num;
+        Word *curr = state + length - 1;
+        long num;
         num = length - shift;
 …
+      }
       Word *current;
       Word state[length];
 …
     template <typename Result, typename Word,
               int rest = std::numeric_limits<Result>::digits, int shift = 0,
               bool last = rest <= std::numeric_limits<Word>::digits>
+              bool last = (rest <= std::numeric_limits<Word>::digits)>
     struct IntConversion {
       static const int bits = std::numeric_limits<Word>::digits;
 …
     };
+  }
+    /// \ingroup misc
+    ///
+    /// \brief Mersenne Twister random number generator
+    ///
+    /// The Mersenne Twister is a twisted generalized feedback
+    /// shift-register generator of Matsumoto and Nishimura. The period
+    /// of this generator is \f$ 2^{19937} - 1\f$ and it is
+    /// equi-distributed in 623 dimensions for 32-bit numbers. The time
+    /// performance of this generator is comparable to the commonly used
+    /// generators.
+    ///
+    /// This is a template implementation of both 32-bit and
+    /// 64-bit architecture optimized versions. The generators differ
+    /// sligthly in the initialization and generation phase so they
+    /// produce two completly different sequences.
+    ///
+    /// \alert Do not use this class directly, but instead one of \ref
+    /// Random, \ref Random32 or \ref Random64.
+    ///
+    /// The generator gives back random numbers of serveral types. To
+    /// get a random number from a range of a floating point type, you
+    /// can use one form of the \c operator() or the \c real() member
+    /// function. If you want to get random number from the {0, 1, ...,
+    /// n-1} integer range, use the \c operator[] or the \c integer()
+    /// method. And to get random number from the whole range of an
+    /// integer type, you can use the argumentless \c integer() or
+    /// \c uinteger() functions. Finally, you can get random bool with
+    /// equal chance of true and false or with given probability of true
+    /// result using the \c boolean() member functions.
+    ///
+    /// Various non-uniform distributions are also supported: normal (Gauss),
+    /// exponential, gamma, Poisson, etc.; and a few two-dimensional
+    /// distributions, too.
+    ///
+    ///\code
+    /// // The commented code is identical to the other
+    /// double a = rnd();                     // [0.0, 1.0)
+    /// // double a = rnd.real();             // [0.0, 1.0)
+    /// double b = rnd(100.0);                // [0.0, 100.0)
+    /// // double b = rnd.real(100.0);        // [0.0, 100.0)
+    /// double c = rnd(1.0, 2.0);             // [1.0, 2.0)
+    /// // double c = rnd.real(1.0, 2.0);     // [1.0, 2.0)
+    /// int d = rnd[100000];                  // 0..99999
+    /// // int d = rnd.integer(100000);       // 0..99999
+    /// int e = rnd[6] + 1;                   // 1..6
+    /// // int e = rnd.integer(1, 1 + 6);     // 1..6
+    /// int b = rnd.uinteger<int>();          // 0 .. 2^31 - 1
+    /// int c = rnd.integer<int>();           // - 2^31 .. 2^31 - 1
+    /// bool g = rnd.boolean();               // P(g = true) = 0.5
+    /// bool h = rnd.boolean(0.8);            // P(h = true) = 0.8
+    ///\endcode
+    ///
+    /// LEMON provides a global instance of the random number generator:
+    /// \ref lemon::rnd "rnd". In most cases, it is a good practice
+    /// to use this global generator to get random numbers.
+    ///
+    /// \sa \ref Random, \ref Random32 or \ref Random64.
+    template<class Word>
+    class Random {
+    private:
+      _random_bits::RandomCore<Word> core;
+      _random_bits::BoolProducer<Word> bool_producer;
+    public:
+      ///\name Initialization
+      ///
+      /// @{
+      /// \brief Default constructor
+      ///
+      /// Constructor with constant seeding.
+      Random() { core.initState(); }
+      /// \brief Constructor with seed
+      ///
+      /// Constructor with seed. The current number type will be converted
+      /// to the architecture word type.
+      template <typename Number>
+      Random(Number seed) {
+        _random_bits::Initializer<Number, Word>::init(core, seed);
+      }
+      /// \brief Constructor with array seeding
+      ///
+      /// Constructor with array seeding. The given range should contain
+      /// any number type and the numbers will be converted to the
+      /// architecture word type.
+      template <typename Iterator>
+      Random(Iterator begin, Iterator end) {
+        typedef typename std::iterator_traits<Iterator>::value_type Number;
+        _random_bits::Initializer<Number, Word>::init(core, begin, end);
+      }
+      /// \brief Copy constructor
+      ///
+      /// Copy constructor. The generated sequence will be identical to
+      /// the other sequence. It can be used to save the current state
+      /// of the generator and later use it to generate the same
+      /// sequence.
+      Random(const Random& other) {
+        core.copyState(other.core);
+      }
+      /// \brief Assign operator
+      ///
+      /// Assign operator. The generated sequence will be identical to
+      /// the other sequence. It can be used to save the current state
+      /// of the generator and later use it to generate the same
+      /// sequence.
+      Random& operator=(const Random& other) {
+        if (&other != this) {
+          core.copyState(other.core);
+        }
+        return *this;
+      }
+      /// \brief Seeding random sequence
+      ///
+      /// Seeding the random sequence. The current number type will be
+      /// converted to the architecture word type.
+      template <typename Number>
+      void seed(Number seed) {
+        _random_bits::Initializer<Number, Word>::init(core, seed);
+      }
+      /// \brief Seeding random sequence
+      ///
+      /// Seeding the random sequence. The given range should contain
+      /// any number type and the numbers will be converted to the
+      /// architecture word type.
+      template <typename Iterator>
+      void seed(Iterator begin, Iterator end) {
+        typedef typename std::iterator_traits<Iterator>::value_type Number;
+        _random_bits::Initializer<Number, Word>::init(core, begin, end);
+      }
+      /// \brief Seeding from file or from process id and time
+      ///
+      /// By default, this function calls the \c seedFromFile() member
+      /// function with the <tt>/dev/urandom</tt> file. If it does not success,
+      /// it uses the \c seedFromTime().
+      /// \return Currently always \c true.
+      bool seed() {
+#ifndef LEMON_WIN32
+        if (seedFromFile("/dev/urandom", 0)) return true;
+#endif
+        if (seedFromTime()) return true;
+        return false;
+      }
+      /// \brief Seeding from file
+      ///
+      /// Seeding the random sequence from file. The linux kernel has two
+      /// devices, <tt>/dev/random</tt> and <tt>/dev/urandom</tt> which
+      /// could give good seed values for pseudo random generators (The
+      /// difference between two devices is that the <tt>random</tt> may
+      /// block the reading operation while the kernel can give good
+      /// source of randomness, while the <tt>urandom</tt> does not
+      /// block the input, but it could give back bytes with worse
+      /// entropy).
+      /// \param file The source file
+      /// \param offset The offset, from the file read.
+      /// \return \c true when the seeding successes.
+#ifndef LEMON_WIN32
+      bool seedFromFile(const std::string& file = "/dev/urandom", int offset = 0)
+#else
+        bool seedFromFile(const std::string& file = "", int offset = 0)
+#endif
+      {
+        std::ifstream rs(file.c_str());
+        const int size = 4;
+        Word buf[size];
+        if (offset != 0 && !rs.seekg(offset)) return false;
+        if (!rs.read(reinterpret_cast<char*>(buf), sizeof(buf))) return false;
+        seed(buf, buf + size);
+        return true;
+      }
+      /// \brief Seeding from process id and time
+      ///
+      /// Seeding from process id and time. This function uses the
+      /// current process id and the current time for initialize the
+      /// random sequence.
+      /// \return Currently always \c true.
+      bool seedFromTime() {
+#ifndef LEMON_WIN32
+        timeval tv;
+        gettimeofday(&tv, 0);
+        seed(getpid() + tv.tv_sec + tv.tv_usec);
+#else
+        seed(bits::getWinRndSeed());
+#endif
+        return true;
+      }
+      /// @}
+      ///\name Uniform Distributions
+      ///
+      /// @{
+      /// \brief Returns a random real number from the range [0, 1)
+      ///
+      /// It returns a random real number from the range [0, 1). The
+      /// default Number type is \c double.
+      template <typename Number>
+      Number real() {
+        return _random_bits::RealConversion<Number, Word>::convert(core);
+      }
+      double real() {
+        return real<double>();
+      }
+      /// \brief Returns a random real number from the range [0, 1)
+      ///
+      /// It returns a random double from the range [0, 1).
+      double operator()() {
+        return real<double>();
+      }
+      /// \brief Returns a random real number from the range [0, b)
+      ///
+      /// It returns a random real number from the range [0, b).
+      double operator()(double b) {
+        return real<double>() * b;
+      }
+      /// \brief Returns a random real number from the range [a, b)
+      ///
+      /// It returns a random real number from the range [a, b).
+      double operator()(double a, double b) {
+        return real<double>() * (b - a) + a;
+      }
+      /// \brief Returns a random integer from a range
+      ///
+      /// It returns a random integer from the range {0, 1, ..., b - 1}.
+      template <typename Number>
+      Number integer(Number b) {
+        return _random_bits::Mapping<Number, Word>::map(core, b);
+      }
+      /// \brief Returns a random integer from a range
+      ///
+      /// It returns a random integer from the range {a, a + 1, ..., b - 1}.
+      template <typename Number>
+      Number integer(Number a, Number b) {
+        return _random_bits::Mapping<Number, Word>::map(core, b - a) + a;
+      }
+      /// \brief Returns a random integer from a range
+      ///
+      /// It returns a random integer from the range {0, 1, ..., b - 1}.
+      template <typename Number>
+      Number operator[](Number b) {
+        return _random_bits::Mapping<Number, Word>::map(core, b);
+      }
+      /// \brief Returns a random non-negative integer
+      ///
+      /// It returns a random non-negative integer uniformly from the
+      /// whole range of the current \c Number type. The default result
+      /// type of this function is <tt>unsigned int</tt>.
+      template <typename Number>
+      Number uinteger() {
+        return _random_bits::IntConversion<Number, Word>::convert(core);
+      }
+      unsigned int uinteger() {
+        return uinteger<unsigned int>();
+      }
+      /// \brief Returns a random integer
+      ///
+      /// It returns a random integer uniformly from the whole range of
+      /// the current \c Number type. The default result type of this
+      /// function is \c int.
+      template <typename Number>
+      Number integer() {
+        static const int nb = std::numeric_limits<Number>::digits +
+          (std::numeric_limits<Number>::is_signed ? 1 : 0);
+        return _random_bits::IntConversion<Number, Word, nb>::convert(core);
+      }
+      int integer() {
+        return integer<int>();
+      }
+      /// \brief Returns a random bool
+      ///
+      /// It returns a random bool. The generator holds a buffer for
+      /// random bits. Every time when it become empty the generator makes
+      /// a new random word and fill the buffer up.
+      bool boolean() {
+        return bool_producer.convert(core);
+      }
+      /// @}
+      ///\name Non-uniform Distributions
+      ///
+      ///@{
+      /// \brief Returns a random bool with given probability of true result.
+      ///
+      /// It returns a random bool with given probability of true result.
+      bool boolean(double p) {
+        return operator()() < p;
+      }
+      /// Standard normal (Gauss) distribution
+      /// Standard normal (Gauss) distribution.
+      /// \note The Cartesian form of the Box-Muller
+      /// transformation is used to generate a random normal distribution.
+      double gauss()
+      {
+        double V1,V2,S;
+        do {
+          V1=2*real<double>()-1;
+          V2=2*real<double>()-1;
+          S=V1*V1+V2*V2;
+        } while(S>=1);
+        return std::sqrt(-2*std::log(S)/S)*V1;
+      }
+      /// Normal (Gauss) distribution with given mean and standard deviation
+      /// Normal (Gauss) distribution with given mean and standard deviation.
+      /// \sa gauss()
+      double gauss(double mean,double std_dev)
+      {
+        return gauss()*std_dev+mean;
+      }
+      /// Lognormal distribution
+      /// Lognormal distribution. The parameters are the mean and the standard
+      /// deviation of <tt>exp(X)</tt>.
+      ///
+      double lognormal(double n_mean,double n_std_dev)
+      {
+        return std::exp(gauss(n_mean,n_std_dev));
+      }
+      /// Lognormal distribution
+      /// Lognormal distribution. The parameter is an <tt>std::pair</tt> of
+      /// the mean and the standard deviation of <tt>exp(X)</tt>.
+      ///
+      double lognormal(const std::pair<double,double> &params)
+      {
+        return std::exp(gauss(params.first,params.second));
+      }
+      /// Compute the lognormal parameters from mean and standard deviation
+      /// This function computes the lognormal parameters from mean and
+      /// standard deviation. The return value can direcly be passed to
+      /// lognormal().
+      std::pair<double,double> lognormalParamsFromMD(double mean,
+                                                     double std_dev)
+      {
+        double fr=std_dev/mean;
+        fr*=fr;
+        double lg=std::log(1+fr);
+        return std::pair<double,double>(std::log(mean)-lg/2.0,std::sqrt(lg));
+      }
+      /// Lognormal distribution with given mean and standard deviation
+      /// Lognormal distribution with given mean and standard deviation.
+      ///
+      double lognormalMD(double mean,double std_dev)
+      {
+        return lognormal(lognormalParamsFromMD(mean,std_dev));
+      }
+      /// Exponential distribution with given mean
+      /// This function generates an exponential distribution random number
+      /// with mean <tt>1/lambda</tt>.
+      ///
+      double exponential(double lambda=1.0)
+      {
+        return -std::log(1.0-real<double>())/lambda;
+      }
+      /// Gamma distribution with given integer shape
+      /// This function generates a gamma distribution random number.
+      ///
+      ///\param k shape parameter (<tt>k>0</tt> integer)
+      double gamma(int k)
+      {
+        double s = 0;
+        for(int i=0;i<k;i++) s-=std::log(1.0-real<double>());
+        return s;
+      }
+      /// Gamma distribution with given shape and scale parameter
+      /// This function generates a gamma distribution random number.
+      ///
+      ///\param k shape parameter (<tt>k>0</tt>)
+      ///\param theta scale parameter
+      ///
+      double gamma(double k,double theta=1.0)
+      {
+        double xi,nu;
+        const double delta = k-std::floor(k);
+        const double v0=E/(E-delta);
+        do {
+          double V0=1.0-real<double>();
+          double V1=1.0-real<double>();
+          double V2=1.0-real<double>();
+          if(V2<=v0)
+            {
+              xi=std::pow(V1,1.0/delta);
+              nu=V0*std::pow(xi,delta-1.0);
+            }
+          else
+            {
+              xi=1.0-std::log(V1);
+              nu=V0*std::exp(-xi);
+            }
+        } while(nu>std::pow(xi,delta-1.0)*std::exp(-xi));
+        return theta*(xi+gamma(int(std::floor(k))));
+      }
+      /// Weibull distribution
+      /// This function generates a Weibull distribution random number.
+      ///
+      ///\param k shape parameter (<tt>k>0</tt>)
+      ///\param lambda scale parameter (<tt>lambda>0</tt>)
+      ///
+      double weibull(double k,double lambda)
+      {
+        return lambda*pow(-std::log(1.0-real<double>()),1.0/k);
+      }
+      /// Pareto distribution
+      /// This function generates a Pareto distribution random number.
+      ///
+      ///\param k shape parameter (<tt>k>0</tt>)
+      ///\param x_min location parameter (<tt>x_min>0</tt>)
+      ///
+      double pareto(double k,double x_min)
+      {
+        return exponential(gamma(k,1.0/x_min))+x_min;
+      }
+      /// Poisson distribution
+      /// This function generates a Poisson distribution random number with
+      /// parameter \c lambda.
+      ///
+      /// The probability mass function of this distribusion is
+      /// \f[ \frac{e^{-\lambda}\lambda^k}{k!} \f]
+      /// \note The algorithm is taken from the book of Donald E. Knuth titled
+      /// ''Seminumerical Algorithms'' (1969). Its running time is linear in the
+      /// return value.
+      int poisson(double lambda)
+      {
+        const double l = std::exp(-lambda);
+        int k=0;
+        double p = 1.0;
+        do {
+          k++;
+          p*=real<double>();
+        } while (p>=l);
+        return k-1;
+      }
+      ///@}
+      ///\name Two-Dimensional Distributions
+      ///
+      ///@{
+      /// Uniform distribution on the full unit circle
+      /// Uniform distribution on the full unit circle.
+      ///
+      dim2::Point<double> disc()
+      {
+        double V1,V2;
+        do {
+          V1=2*real<double>()-1;
+          V2=2*real<double>()-1;
+        } while(V1*V1+V2*V2>=1);
+        return dim2::Point<double>(V1,V2);
+      }
+      /// A kind of two-dimensional normal (Gauss) distribution
+      /// This function provides a turning symmetric two-dimensional distribution.
+      /// Both coordinates are of standard normal distribution, but they are not
+      /// independent.
+      ///
+      /// \note The coordinates are the two random variables provided by
+      /// the Box-Muller method.
+      dim2::Point<double> gauss2()
+      {
+        double V1,V2,S;
+        do {
+          V1=2*real<double>()-1;
+          V2=2*real<double>()-1;
+          S=V1*V1+V2*V2;
+        } while(S>=1);
+        double W=std::sqrt(-2*std::log(S)/S);
+        return dim2::Point<double>(W*V1,W*V2);
+      }
+      /// A kind of two-dimensional exponential distribution
+      /// This function provides a turning symmetric two-dimensional distribution.
+      /// The x-coordinate is of conditionally exponential distribution
+      /// with the condition that x is positive and y=0. If x is negative and
+      /// y=0 then, -x is of exponential distribution. The same is true for the
+      /// y-coordinate.
+      dim2::Point<double> exponential2()
+      {
+        double V1,V2,S;
+        do {
+          V1=2*real<double>()-1;
+          V2=2*real<double>()-1;
+          S=V1*V1+V2*V2;
+        } while(S>=1);
+        double W=-std::log(S)/S;
+        return dim2::Point<double>(W*V1,W*V2);
+      }
+      ///@}
+    };
+  };
   /// \ingroup misc
 …
   /// \brief Mersenne Twister random number generator
   ///
   /// The Mersenne Twister is a twisted generalized feedback
   /// shift-register generator of Matsumoto and Nishimura. The period
   /// of this generator is \f$ 2^{19937} - 1 \f$ and it is
   /// equi-distributed in 623 dimensions for 32-bit numbers. The time
   /// performance of this generator is comparable to the commonly used
   /// generators.
+  /// This class implements either the 32-bit or the 64-bit version of
+  /// the Mersenne Twister random number generator algorithm
+  /// depending on the system architecture.
+  ///
+  /// For the API description, see its base class
+  /// \ref _random_bits::Random.
   ///
   /// This implementation is specialized for both 32-bit and 64-bit
   /// architectures. The generators differ sligthly in the
+  /// initialization and generation phase so they produce two
   /// completly different sequences.
+  /// \sa \ref _random_bits::Random
+  typedef _random_bits::Random<unsigned long> Random;
+  /// \ingroup misc
   ///
+  /// The generator gives back random numbers of serveral types. To
+  /// get a random number from a range of a floating point type you
+  /// can use one form of the \c operator() or the \c real() member
+  /// function. If you want to get random number from the {0, 1, ...,
+  /// n-1} integer range use the \c operator[] or the \c integer()
+  /// method. And to get random number from the whole range of an
+  /// integer type you can use the argumentless \c integer() or \c
+  /// uinteger() functions. After all you can get random bool with
+  /// equal chance of true and false or given probability of true
+  /// result with the \c boolean() member functions.
+  /// \brief Mersenne Twister random number generator (32-bit version)
   ///
+  ///\code
+  /// // The commented code is identical to the other
+  /// double a = rnd();                     // [0.0, 1.0)
+  /// // double a = rnd.real();             // [0.0, 1.0)
+  /// double b = rnd(100.0);                // [0.0, 100.0)
+  /// // double b = rnd.real(100.0);        // [0.0, 100.0)
+  /// double c = rnd(1.0, 2.0);             // [1.0, 2.0)
+  /// // double c = rnd.real(1.0, 2.0);     // [1.0, 2.0)
+  /// int d = rnd[100000];                  // 0..99999
+  /// // int d = rnd.integer(100000);       // 0..99999
+  /// int e = rnd[6] + 1;                   // 1..6
+  /// // int e = rnd.integer(1, 1 + 6);     // 1..6
+  /// int b = rnd.uinteger<int>();          // 0 .. 2^31 - 1
+  /// int c = rnd.integer<int>();           // - 2^31 .. 2^31 - 1
+  /// bool g = rnd.boolean();               // P(g = true) = 0.5
+  /// bool h = rnd.boolean(0.8);            // P(h = true) = 0.8
+  ///\endcode
+  /// This class implements the 32-bit version of the Mersenne Twister
+  /// random number generator algorithm. It is recommended to be used
+  /// when someone wants to make sure that the \e same pseudo random
+  /// sequence will be generated on every platfrom.
   ///
+  /// LEMON provides a global instance of the random number
+  /// generator which name is \ref lemon::rnd "rnd". Usually it is a
+  /// good programming convenience to use this global generator to get
+  /// random numbers.
+  class Random {
+  private:
+    // Architecture word
+    typedef unsigned long Word;
+    _random_bits::RandomCore<Word> core;
+    _random_bits::BoolProducer<Word> bool_producer;
+  public:
+    ///\name Initialization
+    ///
+    /// @{
+    /// \brief Default constructor
+    ///
+    /// Constructor with constant seeding.
+    Random() { core.initState(); }
+    /// \brief Constructor with seed
+    ///
+    /// Constructor with seed. The current number type will be converted
+    /// to the architecture word type.
+    template <typename Number>
+    Random(Number seed) {
+      _random_bits::Initializer<Number, Word>::init(core, seed);
+    }
+    /// \brief Constructor with array seeding
+    ///
+    /// Constructor with array seeding. The given range should contain
+    /// any number type and the numbers will be converted to the
+    /// architecture word type.
+    template <typename Iterator>
+    Random(Iterator begin, Iterator end) {
+      typedef typename std::iterator_traits<Iterator>::value_type Number;
+      _random_bits::Initializer<Number, Word>::init(core, begin, end);
+    }
+    /// \brief Copy constructor
+    ///
+    /// Copy constructor. The generated sequence will be identical to
+    /// the other sequence. It can be used to save the current state
+    /// of the generator and later use it to generate the same
+    /// sequence.
+    Random(const Random& other) {
+      core.copyState(other.core);
+    }
+    /// \brief Assign operator
+    ///
+    /// Assign operator. The generated sequence will be identical to
+    /// the other sequence. It can be used to save the current state
+    /// of the generator and later use it to generate the same
+    /// sequence.
+    Random& operator=(const Random& other) {
+      if (&other != this) {
+        core.copyState(other.core);
+      }
+      return *this;
+    }
+    /// \brief Seeding random sequence
+    ///
+    /// Seeding the random sequence. The current number type will be
+    /// converted to the architecture word type.
+    template <typename Number>
+    void seed(Number seed) {
+      _random_bits::Initializer<Number, Word>::init(core, seed);
+    }
+    /// \brief Seeding random sequence
+    ///
+    /// Seeding the random sequence. The given range should contain
+    /// any number type and the numbers will be converted to the
+    /// architecture word type.
+    template <typename Iterator>
+    void seed(Iterator begin, Iterator end) {
+      typedef typename std::iterator_traits<Iterator>::value_type Number;
+      _random_bits::Initializer<Number, Word>::init(core, begin, end);
+    }
+    /// \brief Seeding from file or from process id and time
+    ///
+    /// By default, this function calls the \c seedFromFile() member
+    /// function with the <tt>/dev/urandom</tt> file. If it does not success,
+    /// it uses the \c seedFromTime().
+    /// \return Currently always \c true.
+    bool seed() {
+#ifndef LEMON_WIN32
+      if (seedFromFile("/dev/urandom", 0)) return true;
+  /// For the API description, see its base class
+  /// \ref _random_bits::Random.
+  ///
+  /// \sa \ref _random_bits::Random
+  typedef _random_bits::Random<unsigned int> Random32;
+  /// \ingroup misc
+  ///
+  /// \brief Mersenne Twister random number generator (64-bit version)
+  ///
+  /// This class implements the 64-bit version of the Mersenne Twister
+  /// random number generator algorithm. (Even though it runs
+  /// on 32-bit architectures, too.) It is recommended to be used when
+  /// someone wants to make sure that the \e same pseudo random sequence
+  /// will be generated on every platfrom.
+  ///
+  /// For the API description, see its base class
+  /// \ref _random_bits::Random.
+  ///
+  /// \sa \ref _random_bits::Random
+  typedef _random_bits::Random<unsigned long long> Random64;
+  extern Random rnd;
+}
 #endif
-      if (seedFromTime()) return true;
-      return false;
+    }
-    /// \brief Seeding from file
-    ///
-    /// Seeding the random sequence from file. The linux kernel has two
-    /// devices, <tt>/dev/random</tt> and <tt>/dev/urandom</tt> which
-    /// could give good seed values for pseudo random generators (The
-    /// difference between two devices is that the <tt>random</tt> may
-    /// block the reading operation while the kernel can give good
-    /// source of randomness, while the <tt>urandom</tt> does not
-    /// block the input, but it could give back bytes with worse
-    /// entropy).
-    /// \param file The source file
-    /// \param offset The offset, from the file read.
-    /// \return \c true when the seeding successes.
-#ifndef LEMON_WIN32
-    bool seedFromFile(const std::string& file = "/dev/urandom", int offset = 0)
-#else
-    bool seedFromFile(const std::string& file = "", int offset = 0)
-#endif
+    {
-      std::ifstream rs(file.c_str());
-      const int size = 4;
-      Word buf[size];
-      if (offset != 0 && !rs.seekg(offset)) return false;
-      if (!rs.read(reinterpret_cast<char*>(buf), sizeof(buf))) return false;
-      seed(buf, buf + size);
-      return true;
+    }
-    /// \brief Seding from process id and time
-    ///
-    /// Seding from process id and time. This function uses the
-    /// current process id and the current time for initialize the
-    /// random sequence.
-    /// \return Currently always \c true.
-    bool seedFromTime() {
-#ifndef LEMON_WIN32
-      timeval tv;
-      gettimeofday(&tv, 0);
-      seed(getpid() + tv.tv_sec + tv.tv_usec);
-#else
-      seed(bits::getWinRndSeed());
-#endif
-      return true;
+    }
-    /// @}
-    ///\name Uniform Distributions
-    ///
-    /// @{
-    /// \brief Returns a random real number from the range [0, 1)
-    ///
-    /// It returns a random real number from the range [0, 1). The
-    /// default Number type is \c double.
-    template <typename Number>
-    Number real() {
-      return _random_bits::RealConversion<Number, Word>::convert(core);
+    }
-    double real() {
-      return real<double>();
+    }
-    /// \brief Returns a random real number from the range [0, 1)
-    ///
-    /// It returns a random double from the range [0, 1).
-    double operator()() {
-      return real<double>();
+    }
-    /// \brief Returns a random real number from the range [0, b)
-    ///
-    /// It returns a random real number from the range [0, b).
-    double operator()(double b) {
-      return real<double>() * b;
+    }
-    /// \brief Returns a random real number from the range [a, b)
-    ///
-    /// It returns a random real number from the range [a, b).
-    double operator()(double a, double b) {
-      return real<double>() * (b - a) + a;
+    }
-    /// \brief Returns a random integer from a range
-    ///
-    /// It returns a random integer from the range {0, 1, ..., b - 1}.
-    template <typename Number>
-    Number integer(Number b) {
-      return _random_bits::Mapping<Number, Word>::map(core, b);
+    }
-    /// \brief Returns a random integer from a range
-    ///
-    /// It returns a random integer from the range {a, a + 1, ..., b - 1}.
-    template <typename Number>
-    Number integer(Number a, Number b) {
-      return _random_bits::Mapping<Number, Word>::map(core, b - a) + a;
+    }
-    /// \brief Returns a random integer from a range
-    ///
-    /// It returns a random integer from the range {0, 1, ..., b - 1}.
-    template <typename Number>
-    Number operator[](Number b) {
-      return _random_bits::Mapping<Number, Word>::map(core, b);
+    }
-    /// \brief Returns a random non-negative integer
-    ///
-    /// It returns a random non-negative integer uniformly from the
-    /// whole range of the current \c Number type. The default result
-    /// type of this function is <tt>unsigned int</tt>.
-    template <typename Number>
-    Number uinteger() {
-      return _random_bits::IntConversion<Number, Word>::convert(core);
+    }
-    unsigned int uinteger() {
-      return uinteger<unsigned int>();
+    }
-    /// \brief Returns a random integer
-    ///
-    /// It returns a random integer uniformly from the whole range of
-    /// the current \c Number type. The default result type of this
-    /// function is \c int.
-    template <typename Number>
-    Number integer() {
-      static const int nb = std::numeric_limits<Number>::digits +
-        (std::numeric_limits<Number>::is_signed ? 1 : 0);
-      return _random_bits::IntConversion<Number, Word, nb>::convert(core);
+    }
-    int integer() {
-      return integer<int>();
+    }
-    /// \brief Returns a random bool
-    ///
-    /// It returns a random bool. The generator holds a buffer for
-    /// random bits. Every time when it become empty the generator makes
-    /// a new random word and fill the buffer up.
-    bool boolean() {
-      return bool_producer.convert(core);
+    }
-    /// @}
-    ///\name Non-uniform Distributions
-    ///
-    ///@{
-    /// \brief Returns a random bool with given probability of true result.
-    ///
-    /// It returns a random bool with given probability of true result.
-    bool boolean(double p) {
-      return operator()() < p;
+    }
-    /// Standard normal (Gauss) distribution
-    /// Standard normal (Gauss) distribution.
-    /// \note The Cartesian form of the Box-Muller
-    /// transformation is used to generate a random normal distribution.
-    double gauss()
+    {
-      double V1,V2,S;
-      do {
-        V1=2*real<double>()-1;
-        V2=2*real<double>()-1;
-        S=V1*V1+V2*V2;
-      } while(S>=1);
-      return std::sqrt(-2*std::log(S)/S)*V1;
+    }
-    /// Normal (Gauss) distribution with given mean and standard deviation
-    /// Normal (Gauss) distribution with given mean and standard deviation.
-    /// \sa gauss()
-    double gauss(double mean,double std_dev)
+    {
-      return gauss()*std_dev+mean;
+    }
-    /// Lognormal distribution
-    /// Lognormal distribution. The parameters are the mean and the standard
-    /// deviation of <tt>exp(X)</tt>.
-    ///
-    double lognormal(double n_mean,double n_std_dev)
+    {
-      return std::exp(gauss(n_mean,n_std_dev));
+    }
-    /// Lognormal distribution
-    /// Lognormal distribution. The parameter is an <tt>std::pair</tt> of
-    /// the mean and the standard deviation of <tt>exp(X)</tt>.
-    ///
-    double lognormal(const std::pair<double,double> &params)
+    {
-      return std::exp(gauss(params.first,params.second));
+    }
-    /// Compute the lognormal parameters from mean and standard deviation
-    /// This function computes the lognormal parameters from mean and
-    /// standard deviation. The return value can direcly be passed to
-    /// lognormal().
-    std::pair<double,double> lognormalParamsFromMD(double mean,
-                                                   double std_dev)
+    {
-      double fr=std_dev/mean;
-      fr*=fr;
-      double lg=std::log(1+fr);
-      return std::pair<double,double>(std::log(mean)-lg/2.0,std::sqrt(lg));
+    }
-    /// Lognormal distribution with given mean and standard deviation
-    /// Lognormal distribution with given mean and standard deviation.
-    ///
-    double lognormalMD(double mean,double std_dev)
+    {
-      return lognormal(lognormalParamsFromMD(mean,std_dev));
+    }
-    /// Exponential distribution with given mean
-    /// This function generates an exponential distribution random number
-    /// with mean <tt>1/lambda</tt>.
-    ///
-    double exponential(double lambda=1.0)
+    {
-      return -std::log(1.0-real<double>())/lambda;
+    }
-    /// Gamma distribution with given integer shape
-    /// This function generates a gamma distribution random number.
-    ///
-    ///\param k shape parameter (<tt>k>0</tt> integer)
-    double gamma(int k)
+    {
-      double s = 0;
-      for(int i=0;i<k;i++) s-=std::log(1.0-real<double>());
-      return s;
+    }
-    /// Gamma distribution with given shape and scale parameter
-    /// This function generates a gamma distribution random number.
-    ///
-    ///\param k shape parameter (<tt>k>0</tt>)
-    ///\param theta scale parameter
-    ///
-    double gamma(double k,double theta=1.0)
+    {
-      double xi,nu;
-      const double delta = k-std::floor(k);
-      const double v0=E/(E-delta);
-      do {
-        double V0=1.0-real<double>();
-        double V1=1.0-real<double>();
-        double V2=1.0-real<double>();
-        if(V2<=v0)
+          {
-            xi=std::pow(V1,1.0/delta);
-            nu=V0*std::pow(xi,delta-1.0);
+          }
-        else
+          {
-            xi=1.0-std::log(V1);
-            nu=V0*std::exp(-xi);
+          }
-      } while(nu>std::pow(xi,delta-1.0)*std::exp(-xi));
-      return theta*(xi+gamma(int(std::floor(k))));
+    }
-    /// Weibull distribution
-    /// This function generates a Weibull distribution random number.
-    ///
-    ///\param k shape parameter (<tt>k>0</tt>)
-    ///\param lambda scale parameter (<tt>lambda>0</tt>)
-    ///
-    double weibull(double k,double lambda)
+    {
-      return lambda*pow(-std::log(1.0-real<double>()),1.0/k);
+    }
-    /// Pareto distribution
-    /// This function generates a Pareto distribution random number.
-    ///
-    ///\param k shape parameter (<tt>k>0</tt>)
-    ///\param x_min location parameter (<tt>x_min>0</tt>)
-    ///
-    double pareto(double k,double x_min)
+    {
-      return exponential(gamma(k,1.0/x_min))+x_min;
+    }
-    /// Poisson distribution
-    /// This function generates a Poisson distribution random number with
-    /// parameter \c lambda.
-    ///
-    /// The probability mass function of this distribusion is
-    /// \f[ \frac{e^{-\lambda}\lambda^k}{k!} \f]
-    /// \note The algorithm is taken from the book of Donald E. Knuth titled
-    /// ''Seminumerical Algorithms'' (1969). Its running time is linear in the
-    /// return value.
-    int poisson(double lambda)
+    {
-      const double l = std::exp(-lambda);
-      int k=0;
-      double p = 1.0;
-      do {
-        k++;
-        p*=real<double>();
-      } while (p>=l);
-      return k-1;
+    }
-    ///@}
-    ///\name Two Dimensional Distributions
-    ///
-    ///@{
-    /// Uniform distribution on the full unit circle
-    /// Uniform distribution on the full unit circle.
-    ///
-    dim2::Point<double> disc()
+    {
-      double V1,V2;
-      do {
-        V1=2*real<double>()-1;
-        V2=2*real<double>()-1;
-      } while(V1*V1+V2*V2>=1);
-      return dim2::Point<double>(V1,V2);
+    }
-    /// A kind of two dimensional normal (Gauss) distribution
-    /// This function provides a turning symmetric two-dimensional distribution.
-    /// Both coordinates are of standard normal distribution, but they are not
-    /// independent.
-    ///
-    /// \note The coordinates are the two random variables provided by
-    /// the Box-Muller method.
-    dim2::Point<double> gauss2()
+    {
-      double V1,V2,S;
-      do {
-        V1=2*real<double>()-1;
-        V2=2*real<double>()-1;
-        S=V1*V1+V2*V2;
-      } while(S>=1);
-      double W=std::sqrt(-2*std::log(S)/S);
-      return dim2::Point<double>(W*V1,W*V2);
+    }
-    /// A kind of two dimensional exponential distribution
-    /// This function provides a turning symmetric two-dimensional distribution.
-    /// The x-coordinate is of conditionally exponential distribution
-    /// with the condition that x is positive and y=0. If x is negative and
-    /// y=0 then, -x is of exponential distribution. The same is true for the
-    /// y-coordinate.
-    dim2::Point<double> exponential2()
+    {
-      double V1,V2,S;
-      do {
-        V1=2*real<double>()-1;
-        V2=2*real<double>()-1;
-        S=V1*V1+V2*V2;
-      } while(S>=1);
-      double W=-std::log(S)/S;
-      return dim2::Point<double>(W*V1,W*V2);
+    }
-    ///@}
-  };
-  extern Random rnd;
+}
-#endif

lemon/smart_graph.h

-                      r1092
+                      r1130
     };
     std::vector<NodeT> nodes;
     std::vector<ArcT> arcs;
+    std::vector<NodeT> _nodes;
+    std::vector<ArcT> _arcs;
   public:
 …
   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 maxNodeId() const { return nodes.size()-1; }
     int maxArcId() const { return arcs.size()-1; }
+    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; }
     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();
+    }
     Node source(Arc a) const { return Node(arcs[a._id].source); }
     Node target(Arc a) const { return Node(arcs[a._id].target); }
+      _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); }
     static int id(Node v) { return v._id; }
 …
     bool valid(Node n) const {
       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
+      return n._id >= 0 && n._id < static_cast<int>(_nodes.size());
+    }
     bool valid(Arc a) const {
       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
+      return a._id >= 0 && a._id < static_cast<int>(_arcs.size());
+    }
 …
     void first(Node& node) const {
       node._id = nodes.size() - 1;
+      node._id = _nodes.size() - 1;
+    }
 …
     void first(Arc& arc) const {
       arc._id = arcs.size() - 1;
+      arc._id = _arcs.size() - 1;
+    }
 …
     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;
+    }
 …
+    {
       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);
 …
     /// to build the digraph.
     /// \sa reserveArc()
     void reserveNode(int n) { nodes.reserve(n); };
+    void reserveNode(int n) { _nodes.reserve(n); };
     /// Reserve memory for arcs.
 …
     /// to build the digraph.
     /// \sa reserveNode()
     void reserveArc(int m) { arcs.reserve(m); };
+    void reserveArc(int m) { _arcs.reserve(m); };
   public:
 …
     void restoreSnapshot(const Snapshot &s)
+    {
       while(s.arc_num<arcs.size()) {
         Arc arc = arcFromId(arcs.size()-1);
+      while(s.arc_num<_arcs.size()) {
+        Arc arc = arcFromId(_arcs.size()-1);
         Parent::notifier(Arc()).erase(arc);
         nodes[arcs.back().source].first_out=arcs.back().next_out;
         nodes[arcs.back().target].first_in=arcs.back().next_in;
         arcs.pop_back();
+      }
       while(s.node_num<nodes.size()) {
         Node node = nodeFromId(nodes.size()-1);
+        _nodes[_arcs.back().source].first_out=_arcs.back().next_out;
+        _nodes[_arcs.back().target].first_in=_arcs.back().next_in;
+        _arcs.pop_back();
+      }
+      while(s.node_num<_nodes.size()) {
+        Node node = nodeFromId(_nodes.size()-1);
         Parent::notifier(Node()).erase(node);
         nodes.pop_back();
+        _nodes.pop_back();
+      }
+    }
 …
       ///
       Snapshot(SmartDigraph &gr) : _graph(&gr) {
         node_num=_graph->nodes.size();
         arc_num=_graph->arcs.size();
+        node_num=_graph->_nodes.size();
+        arc_num=_graph->_arcs.size();
+      }
 …
       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();
+      }
 …
     };
     std::vector<NodeT> nodes;
     std::vector<ArcT> arcs;
+    std::vector<NodeT> _nodes;
+    std::vector<ArcT> _arcs;
   public:
 …
     SmartGraphBase()
       : nodes(), arcs() {}
+      : _nodes(), _arcs() {}
     typedef True NodeNumTag;
 …
     typedef True ArcNumTag;
     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; }
     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); }
+    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; }
+    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) {
 …
     void first(Node& node) const {
       node._id = nodes.size() - 1;
+      node._id = _nodes.size() - 1;
+    }
 …
     void first(Arc& arc) const {
       arc._id = arcs.size() - 1;
+      arc._id = _arcs.size() - 1;
+    }
 …
     void first(Edge& arc) const {
       arc._id = arcs.size() / 2 - 1;
+      arc._id = _arcs.size() / 2 - 1;
+    }
 …
     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;
 …
+    }
     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;
 …
     bool valid(Node n) const {
       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
+      return n._id >= 0 && n._id < static_cast<int>(_nodes.size());
+    }
     bool valid(Arc a) const {
       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
+      return a._id >= 0 && a._id < static_cast<int>(_arcs.size());
+    }
     bool valid(Edge e) const {
       return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
+      return e._id >= 0 && 2 * e._id < static_cast<int>(_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());
       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 | 1].next_out = nodes[u._id].first_out;
       nodes[u._id].first_out = (n | 1);
+      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].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);
       return Edge(n / 2);
 …
     void clear() {
       arcs.clear();
       nodes.clear();
+      _arcs.clear();
+      _nodes.clear();
+    }
 …
     /// to build the graph.
     /// \sa reserveEdge()
     void reserveNode(int n) { nodes.reserve(n); };
+    void reserveNode(int n) { _nodes.reserve(n); };
     /// Reserve memory for edges.
 …
     /// to build the graph.
     /// \sa reserveNode()
     void reserveEdge(int m) { arcs.reserve(2 * m); };
+    void reserveEdge(int m) { _arcs.reserve(2 * m); };
   public:
 …
+    {
       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<arcs.size()) {
         int n=arcs.size()-1;
+      while(s.arc_num<_arcs.size()) {
+        int n=_arcs.size()-1;
         Edge arc=edgeFromId(n/2);
         Parent::notifier(Edge()).erase(arc);
 …
         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();
+      }
       while(s.node_num<nodes.size()) {
         int n=nodes.size()-1;
+        _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.size()) {
+        int n=_nodes.size()-1;
         Node node = nodeFromId(n);
         Parent::notifier(Node()).erase(node);
         nodes.pop_back();
+        _nodes.pop_back();
+      }
+    }
 …
     };
     std::vector<NodeT> nodes;
     std::vector<ArcT> arcs;
+    std::vector<NodeT> _nodes;
+    std::vector<ArcT> _arcs;
     int first_red, first_blue;
 …
     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 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 maxNodeId() const { return nodes.size()-1; }
+    int edgeNum() const { return _arcs.size() / 2; }
+    int arcNum() const { return _arcs.size(); }
+    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; }
     bool red(Node n) const { return nodes[n._id].red; }
     bool blue(Node n) const { return !nodes[n._id].red; }
+    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; }
     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);
+    }
 …
     void first(Node& node) const {
       node._id = nodes.size() - 1;
+      node._id = _nodes.size() - 1;
+    }
 …
     void next(RedNode& node) const {
       node._id = nodes[node._id].partition_next;
+      node._id = _nodes[node._id].partition_next;
+    }
 …
     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;
+    }
 …
     void first(Edge& arc) const {
       arc._id = arcs.size() / 2 - 1;
+      arc._id = _arcs.size() / 2 - 1;
+    }
 …
     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;
 …
+    }
     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;
 …
     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; }
 …
     bool valid(Node n) const {
       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
+      return n._id >= 0 && n._id < static_cast<int>(_nodes.size());
+    }
     bool valid(Arc a) const {
       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
+      return a._id >= 0 && a._id < static_cast<int>(_arcs.size());
+    }
     bool valid(Edge e) const {
       return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
+      return e._id >= 0 && 2 * e._id < static_cast<int>(_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;
 …
     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;
 …
     Edge addEdge(RedNode u, BlueNode v) {
       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].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);
+      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].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);
       return Edge(n / 2);
 …
     void clear() {
       arcs.clear();
       nodes.clear();
+      _arcs.clear();
+      _nodes.clear();
       first_red = -1;
       first_blue = -1;
 …
     /// to build the graph.
     /// \sa reserveEdge()
     void reserveNode(int n) { nodes.reserve(n); };
+    void reserveNode(int n) { _nodes.reserve(n); };
     /// Reserve memory for edges.
 …
     /// to build the graph.
     /// \sa reserveNode()
     void reserveEdge(int m) { arcs.reserve(2 * m); };
+    void reserveEdge(int m) { _arcs.reserve(2 * m); };
   public:
 …
+    {
       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<arcs.size()) {
         int n=arcs.size()-1;
+      while(s.arc_num<_arcs.size()) {
+        int n=_arcs.size()-1;
         Edge arc=edgeFromId(n/2);
         Parent::notifier(Edge()).erase(arc);
 …
         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();
+      }
       while(s.node_num<nodes.size()) {
         int n=nodes.size()-1;
+        _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.size()) {
+        int n=_nodes.size()-1;
         Node node = nodeFromId(n);
         if (Parent::red(node)) {
           first_red = nodes[n].partition_next;
+          first_red = _nodes[n].partition_next;
           if (first_red != -1) {
             max_red = nodes[first_red].partition_index;
+            max_red = _nodes[first_red].partition_index;
           } else {
             max_red = -1;
 …
           Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));
         } else {
           first_blue = nodes[n].partition_next;
+          first_blue = _nodes[n].partition_next;
           if (first_blue != -1) {
             max_blue = nodes[first_blue].partition_index;
+            max_blue = _nodes[first_blue].partition_index;
           } else {
             max_blue = -1;
 …
+        }
         Parent::notifier(Node()).erase(node);
         nodes.pop_back();
+        _nodes.pop_back();
+      }
+    }

lemon/soplex.cc

-                      r1092
+                      r1130
   SoplexLp::SoplexLp(const SoplexLp& lp) {
     rows = lp.rows;
     cols = lp.cols;
+    _rows = lp._rows;
+    _cols = lp._cols;
     soplex = new soplex::SoPlex;
 …
   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());
+  }
 …
     _row_names.clear();
     _row_names_ref.clear();
     cols.clear();
     rows.clear();
+    _cols.clear();
+    _rows.clear();
     _clear_temporals();
+  }

lemon/static_graph.h

-                      r1124
+                      r1157
   class StaticDigraphBase {
   public:
 …
   /// \sa concepts::Digraph
   class StaticDigraph : public ExtendedStaticDigraphBase {
+  private:
+    /// Graphs are \e not copy constructible. Use DigraphCopy instead.
+    StaticDigraph(const StaticDigraph &) : ExtendedStaticDigraphBase() {};
+    /// \brief Assignment of a graph to another one is \e not allowed.
+    /// Use DigraphCopy instead.
+    void operator=(const StaticDigraph&) {}
   public:

test/CMakeLists.txt

r1088	r1187
55	55	tsp_test
56	56	unionfind_test
	57	vf2_test
57	58	)
58	59

test/bellman_ford_test.cc

-                      r1092
+                      r1162
     pp = const_bf_test.negativeCycle();
+#ifdef LEMON_CXX11
     for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
+    for (auto n: const_bf_test.activeNodes()) { ::lemon::ignore_unused_variable_warning(n); }
+    for (Digraph::Node n: const_bf_test.activeNodes()) {
+      ::lemon::ignore_unused_variable_warning(n);
+    }
+#endif
+  }
+  {

test/graph_test.h

-                      r1092
+                      r1131
     check(n==INVALID,"Wrong Node list linking.");
     check(countNodes(G)==cnt,"Wrong Node number.");
+#ifdef LEMON_CXX11
+    {
+      typename Graph::NodeIt n(G);
+      for(auto u: G.nodes())
+        {
+          check(n==u,"Wrong STL Node iterator.");
+          ++n;
+        }
+      check(n==INVALID,"Wrong STL Node iterator.");
+    }
+    {
+      typename Graph::NodeIt n(G);
+      for(typename Graph::Node u: G.nodes())
+        {
+          check(n==u,"Wrong STL Node iterator.");
+          ++n;
+        }
+      check(n==INVALID,"Wrong STL Node iterator.");
+    }
+#endif
+  }
 …
     check(n==INVALID,"Wrong red Node list linking.");
     check(countRedNodes(G)==cnt,"Wrong red Node number.");
+#ifdef LEMON_CXX11
+    {
+      typename Graph::RedNodeIt n(G);
+      for(auto u: G.redNodes())
+        {
+          check(n==u,"Wrong STL RedNode iterator.");
+          ++n;
+        }
+      check(n==INVALID,"Wrong STL RedNode iterator.");
+    }
+    {
+      typename Graph::RedNodeIt n(G);
+      for(typename Graph::RedNode u: G.redNodes())
+        {
+          check(n==u,"Wrong STL RedNode iterator.");
+          ++n;
+        }
+      check(n==INVALID,"Wrong STL RedNode iterator.");
+    }
+#endif
+  }
 …
     check(n==INVALID,"Wrong blue Node list linking.");
     check(countBlueNodes(G)==cnt,"Wrong blue Node number.");
+#ifdef LEMON_CXX11
+    {
+      typename Graph::BlueNodeIt n(G);
+      for(auto u: G.blueNodes())
+        {
+          check(n==u,"Wrong STL BlueNode iterator.");
+          ++n;
+        }
+      check(n==INVALID,"Wrong STL BlueNode iterator.");
+    }
+    {
+      typename Graph::BlueNodeIt n(G);
+      for(typename Graph::BlueNode u: G.blueNodes())
+        {
+          check(n==u,"Wrong STL BlueNode iterator.");
+          ++n;
+        }
+      check(n==INVALID,"Wrong STL BlueNode iterator.");
+    }
+#endif
+  }
 …
     check(e==INVALID,"Wrong Arc list linking.");
     check(countArcs(G)==cnt,"Wrong Arc number.");
+#ifdef LEMON_CXX11
+    {
+      typename Graph::ArcIt a(G);
+      for(auto e: G.arcs())
+        {
+          check(a==e,"Wrong STL Arc iterator.");
+          ++a;
+        }
+      check(a==INVALID,"Wrong STL Arc iterator.");
+    }
+    {
+      typename Graph::ArcIt a(G);
+      for(typename Graph::Arc e: G.arcs())
+        {
+          check(a==e,"Wrong STL Arc iterator.");
+          ++a;
+        }
+      check(a==INVALID,"Wrong STL Arc iterator.");
+    }
+#endif
+  }
 …
     check(e==INVALID,"Wrong OutArc list linking.");
     check(countOutArcs(G,n)==cnt,"Wrong OutArc number.");
+#ifdef LEMON_CXX11
+    {
+      typename Graph::OutArcIt a(G,n);
+      for(auto e: G.outArcs(n))
+        {
+          check(a==e,"Wrong STL OutArc iterator.");
+          ++a;
+        }
+      check(a==INVALID,"Wrong STL OutArc iterator.");
+    }
+    {
+      typename Graph::OutArcIt a(G,n);
+      for(typename Graph::Arc e: G.outArcs(n))
+        {
+          check(a==e,"Wrong STL OutArc iterator.");
+          ++a;
+        }
+      check(a==INVALID,"Wrong STL OutArc iterator.");
+    }
+#endif
+  }
 …
     check(e==INVALID,"Wrong InArc list linking.");
     check(countInArcs(G,n)==cnt,"Wrong InArc number.");
+#ifdef LEMON_CXX11
+    {
+      typename Graph::InArcIt a(G,n);
+      for(auto e: G.inArcs(n))
+        {
+          check(a==e,"Wrong STL InArc iterator.");
+          ++a;
+        }
+      check(a==INVALID,"Wrong STL InArc iterator.");
+    }
+    {
+      typename Graph::InArcIt a(G,n);
+      for(typename Graph::Arc e: G.inArcs(n))
+        {
+          check(a==e,"Wrong STL InArc iterator.");
+          ++a;
+        }
+      check(a==INVALID,"Wrong STL InArc iterator.");
+    }
+#endif
+  }
 …
     check(e==INVALID,"Wrong Edge list linking.");
     check(countEdges(G)==cnt,"Wrong Edge number.");
+#ifdef LEMON_CXX11
+    {
+      typename Graph::EdgeIt a(G);
+      for(auto e: G.edges())
+        {
+          check(a==e,"Wrong STL Edge iterator.");
+          ++a;
+        }
+      check(a==INVALID,"Wrong STL Edge iterator.");
+    }
+    {
+      typename Graph::EdgeIt a(G);
+      for(typename Graph::Edge e: G.edges())
+        {
+          check(a==e,"Wrong STL Edge iterator.");
+          ++a;
+        }
+      check(a==INVALID,"Wrong STL Edge iterator.");
+    }
+#endif
+  }
 …
     check(e==INVALID,"Wrong IncEdge list linking.");
     check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
+#ifdef LEMON_CXX11
+    {
+      typename Graph::IncEdgeIt a(G,n);
+      for(auto e: G.incEdges(n))
+        {
+          check(a==e,"Wrong STL IncEdge iterator.");
+          ++a;
+        }
+      check(a==INVALID,"Wrong STL IncEdge iterator.");
+    }
+    {
+      typename Graph::IncEdgeIt a(G,n);
+      for(typename Graph::Edge e: G.incEdges(n))
+        {
+          check(a==e,"Wrong STL IncEdge iterator.");
+          ++a;
+        }
+      check(a==INVALID,"Wrong STL IncEdge iterator.");
+    }
+#endif
+  }

test/lp_test.cc

-                      r1105
+                      r1131
 #include "test_tools.h"
 #include <lemon/tolerance.h>
+#include <lemon/concept_check.h>
 #include <lemon/config.h>
 …
   int count=0;
   for (LpBase::ColIt c(lp); c!=INVALID; ++c) ++count;
+#ifdef LEMON_CXX11
+  int cnt = 0;
+  for(auto c: lp.cols()) { cnt++; ::lemon::ignore_unused_variable_warning(c); }
+  check(count == cnt, "Wrong STL iterator");
+#endif
   return count;
+}
 …
   int count=0;
   for (LpBase::RowIt r(lp); r!=INVALID; ++r) ++count;
+#ifdef LEMON_CXX11
+  int cnt = 0;
+  for(auto r: lp.rows()) { cnt++; ::lemon::ignore_unused_variable_warning(r); }
+  check(count == cnt, "Wrong STL iterator");
+#endif
   return count;
+}

test/maps_test.cc

-                      r1092
+                      r1131
     check(n == 3, "Wrong number");
     check(map1.falseNum() == 3, "Wrong number");
+#ifdef LEMON_CXX11
+    {
+      int c = 0;
+      for(auto v: map1.items(false)) { c++; ::lemon::ignore_unused_variable_warning(v); }
+      check(c == map1.falseNum(), "Wrong number");
+    }
+    {
+      int c = 0;
+      for(auto v: map1.items(true)) { c++; ::lemon::ignore_unused_variable_warning(v); }
+      check(c == map1.trueNum(), "Wrong number");
+    }
+    {
+      int c = 0;
+      for(auto v: map1.falseKeys()) { c++; ::lemon::ignore_unused_variable_warning(v); }
+      check(c == map1.falseNum(), "Wrong number");
+    }
+    {
+      int c = 0;
+      for(auto v: map1.trueKeys()) { c++; ::lemon::ignore_unused_variable_warning(v); }
+      check(c == map1.trueNum(), "Wrong number");
+    }
+#endif
+  }
 …
+    }
     check(n == num, "Wrong number");
+#ifdef LEMON_CXX11
+    {
+      int c = 0;
+      for(auto v: map1.items(0)) { c++; ::lemon::ignore_unused_variable_warning(v); }
+      check(c == (num + 1) / 2, "Wrong number");
+      for(auto v: map1.items(1)) { c++; ::lemon::ignore_unused_variable_warning(v); }
+      check(c == num, "Wrong number");
+    }
+#endif
+  }
 …
+    }
     check(n == num, "Wrong number");
+#ifdef LEMON_CXX11
+    {
+      int c = 0;
+      for(auto v: map1.items(0.0)) { c++; ::lemon::ignore_unused_variable_warning(v); }
+      check(c == (num + 1) / 2, "Wrong number");
+      for(auto v: map1.items(1.0)) { c++; ::lemon::ignore_unused_variable_warning(v); }
+      check(c == num, "Wrong number");
+    }
+#endif
+  }

test/random_test.cc

-                      r440
+                      r1163
 int seed_array[] = {1, 2};
+int rnd_seq32[] = {
+, 43567, 42613, 52416, 45891, 21243, 30403, 32103,
+, 33003, 12172, 5192, 32511, 50057, 43723, 7813,
+, 35343, 6637, 30280, 44566, 31019, 18898, 33867,
+, 1688, 11513, 59011, 48056, 25544, 39168, 25365,
+, 8366, 27063, 49861, 55169, 63848, 11863, 49608
+};
+int rnd_seq64[] = {
+, 63883, 59577, 64750, 9644, 59886, 57647, 18152,
+, 64078, 17818, 49294, 26424, 26697, 53684, 19209,
+, 12121, 12837, 11827, 32156, 58333, 62553, 7907,
+, 39399, 21971, 48789, 46981, 15716, 53335, 65256,
+, 15308, 10906, 42162, 47587, 43006, 53921, 18716
+};
+void seq_test() {
+  for(int i=0;i<5;i++) {
+    lemon::Random32 r32(i);
+    lemon::Random64 r64(i);
+    for(int j=0;j<8;j++) {
+      check(r32[65536]==rnd_seq32[i*8+j], "Wrong random sequence");
+      check(r64[65536]==rnd_seq64[i*8+j], "Wrong random sequence");
+    }
+  }
+}
 int main()
+{
 …
                   (sizeof(seed_array) / sizeof(seed_array[0])));
+  seq_test();
   return 0;
+}

Context Navigation

Changes in / [1197:f179aa1045a4:1198:2236d00ca778] in lemon-main

Legend:

Download in other formats: