Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt (revision 1404)
+++ CMakeLists.txt (revision 1416)
@@ -4,8 +4,4 @@
CMAKE_POLICY(SET CMP0048 OLD)
ENDIF(POLICY CMP0048)
-
-IF(POLICY CMP0043)
- CMAKE_POLICY(SET CMP0043 OLD)
-ENDIF(POLICY CMP0043)
IF(POLICY CMP0026)
@@ -153,10 +149,23 @@
ENDIF()
+IF( ( ("${CMAKE_CXX_COMPILER_ID}" STREQUAL "GNU") AND
+ ("${CMAKE_CXX_COMPILER_VERSION}" VERSION_GREATER_EQUAL "4.8") )
+ OR ("${CMAKE_CXX_COMPILER_ID}" STREQUAL "Clang")
+ OR ("${CMAKE_CXX_COMPILER_ID}" STREQUAL "Intel")
+ )
+ SET(LEMON_NO_UNUSED_LOCAL_TYPEDEF_WARNINGS TRUE)
+ENDIF()
IF(DEFINED ENV{LEMON_CXX_WARNING})
SET(CXX_WARNING $ENV{LEMON_CXX_WARNING})
ELSE()
- IF(CMAKE_COMPILER_IS_GNUCXX)
+ IF( ("${CMAKE_CXX_COMPILER_ID}" STREQUAL "GNU")
+ OR ("${CMAKE_CXX_COMPILER_ID}" STREQUAL "Clang")
+ )
SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
+ SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
+ SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
+ ELSEIF("${CMAKE_CXX_COMPILER_ID}" STREQUAL "Intel")
+ SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wsign-promo -Woverloaded-virtual -fno-strict-aliasing -Wno-unknown-pragmas")
SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
@@ -238,8 +247,4 @@
FORCE )
-SET_DIRECTORY_PROPERTIES(PROPERTIES
- COMPILE_DEFINITIONS_DEBUG "LEMON_ENABLE_DEBUG"
- COMPILE_DEFINITIONS_MAINTAINER "LEMON_ENABLE_DEBUG"
-)
INCLUDE(CheckTypeSize)
@@ -270,12 +275,4 @@
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")
Index: doc/Doxyfile.in
===================================================================
--- doc/Doxyfile.in (revision 1354)
+++ doc/Doxyfile.in (revision 1251)
@@ -20,5 +20,5 @@
STRIP_FROM_PATH = "@abs_top_srcdir@"
STRIP_FROM_INC_PATH = "@abs_top_srcdir@"
-SHORT_NAMES = NO
+SHORT_NAMES = YES
JAVADOC_AUTOBRIEF = NO
QT_AUTOBRIEF = NO
@@ -40,4 +40,5 @@
SUBGROUPING = YES
TYPEDEF_HIDES_STRUCT = NO
+SYMBOL_CACHE_SIZE = 0
#---------------------------------------------------------------------------
# Build related configuration options
@@ -72,4 +73,5 @@
MAX_INITIALIZER_LINES = 5
SHOW_USED_FILES = NO
+SHOW_DIRECTORIES = YES
SHOW_FILES = YES
SHOW_NAMESPACES = YES
@@ -149,4 +151,5 @@
HTML_COLORSTYLE_GAMMA = 80
HTML_TIMESTAMP = YES
+HTML_ALIGN_MEMBERS = YES
HTML_DYNAMIC_SECTIONS = YES
GENERATE_DOCSET = NO
@@ -175,4 +178,5 @@
ENUM_VALUES_PER_LINE = 4
GENERATE_TREEVIEW = NO
+USE_INLINE_TREES = NO
TREEVIEW_WIDTH = 250
EXT_LINKS_IN_WINDOW = NO
@@ -221,4 +225,6 @@
GENERATE_XML = NO
XML_OUTPUT = xml
+XML_SCHEMA =
+XML_DTD =
XML_PROGRAMLISTING = YES
#---------------------------------------------------------------------------
@@ -261,5 +267,5 @@
HAVE_DOT = YES
DOT_NUM_THREADS = 0
-DOT_FONTNAME =
+DOT_FONTNAME = FreeSans
DOT_FONTSIZE = 10
DOT_FONTPATH =
Index: doc/groups.dox
===================================================================
--- doc/groups.dox (revision 1366)
+++ doc/groups.dox (revision 1271)
@@ -562,33 +562,4 @@
/**
-@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 Subgraph Isomorphism Problem (SIP) 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 Induced Subgraph Isomorphism Problem (ISIP) 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
Index: doc/named-param.dox
===================================================================
--- doc/named-param.dox (revision 1351)
+++ doc/named-param.dox (revision 463)
@@ -26,5 +26,5 @@
function parameters by name also when you call the function. It is
especially comfortable in case of a function having tons of parameters
-with natural default values. Sadly, C++ lacks this amenity.
+with natural default values. Sadly, C++ lack this amenity.
However, with a crafty trick and with some little
Index: doc/references.bib
===================================================================
--- doc/references.bib (revision 1414)
+++ doc/references.bib (revision 1219)
@@ -43,15 +43,4 @@
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}
-}
-
@@ -366,15 +355,2 @@
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
-}
Index: lemon/bellman_ford.h
===================================================================
--- lemon/bellman_ford.h (revision 1337)
+++ lemon/bellman_ford.h (revision 1270)
@@ -30,5 +30,4 @@
#include
#include
-#include
#include
@@ -691,19 +690,4 @@
int _index;
};
-
- /// \brief Gets the collection of the active nodes.
- ///
- /// This function can be used for iterating on the active nodes of the
- /// Bellman-Ford algorithm after the last phase.
- /// These nodes should be checked in the next phase to
- /// find augmenting arcs outgoing from them.
- /// It returns a wrapped ActiveIt, which looks
- /// like an STL container (by having begin() and end())
- /// which you can use in range-based for loops, STL algorithms, etc.
- LemonRangeWrapper1
- activeNodes() const {
- return LemonRangeWrapper1(*this);
- }
-
/// \name Query Functions
Index: lemon/bfs.h
===================================================================
--- lemon/bfs.h (revision 1270)
+++ lemon/bfs.h (revision 1416)
@@ -1377,5 +1377,5 @@
struct SetReachedMapTraits : public Traits {
typedef T ReachedMap;
- static ReachedMap *createReachedMap(const Digraph &digraph) {
+ static ReachedMap *createReachedMap(const Digraph &) {
LEMON_ASSERT(false, "ReachedMap is not initialized");
return 0; // ignore warnings
Index: lemon/bits/edge_set_extender.h
===================================================================
--- lemon/bits/edge_set_extender.h (revision 1337)
+++ lemon/bits/edge_set_extender.h (revision 1270)
@@ -114,7 +114,4 @@
};
- LemonRangeWrapper1 nodes() const {
- return LemonRangeWrapper1(*this);
- }
class ArcIt : public Arc {
@@ -140,7 +137,4 @@
};
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
class OutArcIt : public Arc {
@@ -167,7 +161,4 @@
};
- LemonRangeWrapper2 outArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
class InArcIt : public Arc {
@@ -193,8 +184,4 @@
};
-
- LemonRangeWrapper2 inArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
// \brief Base node of the iterator
@@ -386,7 +373,4 @@
};
- LemonRangeWrapper1 nodes() const {
- return LemonRangeWrapper1(*this);
- }
class ArcIt : public Arc {
@@ -412,7 +396,4 @@
};
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
class OutArcIt : public Arc {
@@ -439,7 +420,4 @@
};
- LemonRangeWrapper2 outArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
class InArcIt : public Arc {
@@ -466,7 +444,4 @@
};
- LemonRangeWrapper2 inArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
class EdgeIt : public Parent::Edge {
@@ -491,8 +466,4 @@
};
-
- LemonRangeWrapper1 edges() const {
- return LemonRangeWrapper1(*this);
- }
class IncEdgeIt : public Parent::Edge {
@@ -520,8 +491,4 @@
}
};
-
- LemonRangeWrapper2 incEdges(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
// \brief Base node of the iterator
Index: lemon/bits/graph_adaptor_extender.h
===================================================================
--- lemon/bits/graph_adaptor_extender.h (revision 1337)
+++ lemon/bits/graph_adaptor_extender.h (revision 1270)
@@ -86,7 +86,4 @@
};
- LemonRangeWrapper1 nodes() const {
- return LemonRangeWrapper1(*this);
- }
class ArcIt : public Arc {
@@ -111,8 +108,4 @@
};
-
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
@@ -140,8 +133,4 @@
};
- LemonRangeWrapper2 outArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
class InArcIt : public Arc {
@@ -167,8 +156,4 @@
};
-
- LemonRangeWrapper2 inArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
Node baseNode(const OutArcIt &e) const {
@@ -270,8 +255,4 @@
};
- LemonRangeWrapper1 nodes() const {
- return LemonRangeWrapper1(*this);
- }
-
class ArcIt : public Arc {
@@ -296,8 +277,4 @@
};
-
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
@@ -325,8 +302,4 @@
};
- LemonRangeWrapper2 outArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
class InArcIt : public Arc {
@@ -353,8 +326,4 @@
};
- LemonRangeWrapper2 inArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
class EdgeIt : public Parent::Edge {
const Adaptor* _adaptor;
@@ -378,9 +347,4 @@
};
-
- LemonRangeWrapper1 edges() const {
- return LemonRangeWrapper1(*this);
- }
-
class IncEdgeIt : public Edge {
@@ -409,9 +373,4 @@
};
- LemonRangeWrapper2 incEdges(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
-
Node baseNode(const OutArcIt &a) const {
return Parent::source(a);
Index: lemon/bits/graph_extender.h
===================================================================
--- lemon/bits/graph_extender.h (revision 1336)
+++ lemon/bits/graph_extender.h (revision 1270)
@@ -28,6 +28,4 @@
#include
-#include
-
//\ingroup graphbits
//\file
@@ -119,8 +117,4 @@
};
- LemonRangeWrapper1 nodes() const {
- return LemonRangeWrapper1(*this);
- }
-
class ArcIt : public Arc {
@@ -145,8 +139,4 @@
};
-
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
@@ -174,8 +164,4 @@
};
- LemonRangeWrapper2 outArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
class InArcIt : public Arc {
@@ -201,8 +187,4 @@
};
-
- LemonRangeWrapper2 inArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
// \brief Base node of the iterator
@@ -455,8 +437,4 @@
};
- LemonRangeWrapper1 nodes() const {
- return LemonRangeWrapper1(*this);
- }
-
class ArcIt : public Arc {
@@ -481,8 +459,4 @@
};
-
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
@@ -510,8 +484,4 @@
};
- LemonRangeWrapper2 outArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
class InArcIt : public Arc {
@@ -538,8 +508,4 @@
};
- LemonRangeWrapper2 inArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
class EdgeIt : public Parent::Edge {
@@ -564,9 +530,4 @@
};
-
- LemonRangeWrapper1 edges() const {
- return LemonRangeWrapper1(*this);
- }
-
class IncEdgeIt : public Parent::Edge {
@@ -594,9 +555,4 @@
}
};
-
- LemonRangeWrapper2 incEdges(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
// \brief Base node of the iterator
@@ -948,9 +904,4 @@
};
- LemonRangeWrapper1 nodes() const {
- return LemonRangeWrapper1(*this);
- }
-
-
class RedNodeIt : public RedNode {
const BpGraph* _graph;
@@ -975,9 +926,4 @@
};
- LemonRangeWrapper1 redNodes() const {
- return LemonRangeWrapper1(*this);
- }
-
-
class BlueNodeIt : public BlueNode {
const BpGraph* _graph;
@@ -1002,9 +948,4 @@
};
- LemonRangeWrapper1 blueNodes() const {
- return LemonRangeWrapper1(*this);
- }
-
-
class ArcIt : public Arc {
@@ -1029,8 +970,4 @@
};
-
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
@@ -1058,8 +995,4 @@
};
- LemonRangeWrapper2 outArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
class InArcIt : public Arc {
@@ -1086,8 +1019,4 @@
};
- LemonRangeWrapper2 inArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
class EdgeIt : public Parent::Edge {
@@ -1112,9 +1041,4 @@
};
-
- LemonRangeWrapper1 edges() const {
- return LemonRangeWrapper1(*this);
- }
-
class IncEdgeIt : public Parent::Edge {
@@ -1142,9 +1066,4 @@
}
};
-
- LemonRangeWrapper2 incEdges(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
// \brief Base node of the iterator
Index: lemon/bits/path_dump.h
===================================================================
--- lemon/bits/path_dump.h (revision 1338)
+++ lemon/bits/path_dump.h (revision 1270)
@@ -62,5 +62,5 @@
}
- operator typename Digraph::Arc() const {
+ operator const typename Digraph::Arc() const {
return path->predMap[current];
}
Index: mon/bits/stl_iterators.h
===================================================================
--- lemon/bits/stl_iterators.h (revision 1339)
+++ (revision )
@@ -1,99 +1,0 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
- */
-
-#ifndef STL_ITERATORS_H_
-#define STL_ITERATORS_H_
-
-#include
-
-namespace lemon {
-
- /// \brief Template to make STL iterators from Lemon iterators.
- ///
- /// This template makes an STL iterator from a Lemon iterator
- /// by adding the missing features.
- /// It inherits from \c std::iterator to make \c iterator_concept work
- /// (so that STL algorithms work).
- /// \c T should be the lemon iterator to be decorated.
- template
- struct LemonItWrapper
- : public T, public std::iterator {
-
- LemonItWrapper(const T &x) : T(x) {}
-
- //Lemon iterators don't have operator*, (because they rather
- //inherit from their "value_type"),
- //so we add one that just returns the object.
- const T& operator*() const {
- return static_cast(*this);
- }
-
- //I can't think of any use case for this with Lemon iterators,
- //but maybe it should be included for completeness.
- const T* operator->() {
- return static_cast(this);
- }
-
- //Lemon iterators don't have postincrement.
- void operator++(int) {
- T::operator++();
- }
-
- using T::operator++;
-
- };
-
-
- /// \brief A generic wrapper for Lemon iterators for range-based for loops.
- ///
- /// This template can be used to create a class
- /// that has begin() and end() from a Lemon iterator
- /// (with a 1-parameter constructor)
- /// to make range-based for loops and STL algorithms work.
- ///
- /// \c LIT is the Lemon iterator that will be wrapped
- /// \c P is the type of the parameter of the constructor of \c LIT.
- template
- class LemonRangeWrapper1 {
- typedef LemonItWrapper It;
- It _begin;
-
- public:
- LemonRangeWrapper1(const P &p) : _begin(LIT(p)) {}
- It begin() const {
- return _begin;
- }
- It end() const {
- return It(lemon::INVALID);
- }
- };
-
-
- /// \brief A generic wrapper for Lemon iterators for range-based for loops.
- ///
- /// This template can be used to create a class
- /// that has begin() and end() from a Lemon iterator
- /// (with a 2-parameter constructor)
- /// to make range-based for loops and STL algorithms work.
- ///
- /// \c LIT is the Lemon iterator that will be wrapped
- /// \c P1 and \c P2 are the types of the parameters
- /// of the constructor of \c LIT.
- template
- class LemonRangeWrapper2 {
- typedef LemonItWrapper It;
- It _begin;
- public:
- LemonRangeWrapper2(const P1 &p1, const P2 &p2) : _begin(LIT(p1, p2)) {}
- It begin() const {
- return _begin;
- }
- It end() const {
- return It(lemon::INVALID);
- }
- };
-
-
-}
-
-#endif /* STL_ITERATORS_H_ */
Index: mon/bits/vf2_internals.h
===================================================================
--- lemon/bits/vf2_internals.h (revision 1407)
+++ (revision )
@@ -1,47 +1,0 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library.
- *
- * Copyright (C) 2015-2017
- * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef VF2_INTERNALS_H
-#define VF2_INTERNALS_H
-
-
-///\ingroup graph_properties
-///\file
-///\brief Mapping types for graph matching algorithms.
-
-namespace lemon {
- ///\ingroup graph_isomorphism
- ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
- ///graph embeddings, this enum specifies their types.
- ///
- ///See \ref graph_isomorphism for a more detailed description.
- enum MappingType {
- /// Subgraph isomorphism
- SUBGRAPH = 0,
- /// Induced subgraph isomorphism
- INDUCED = 1,
- /// Graph isomorphism
- ///
- /// If the two graphs have the same number of nodes, than it is
- /// equivalent to \ref INDUCED, and if they also have the same
- /// number of edges, then it is also equivalent to \ref SUBGRAPH.
- ///
- /// However, using this setting is faster than the other two options.
- ISOMORPH = 2
- };
-}
-#endif
Index: lemon/cbc.cc
===================================================================
--- lemon/cbc.cc (revision 1336)
+++ lemon/cbc.cc (revision 1270)
@@ -112,9 +112,9 @@
void CbcMip::_eraseColId(int i) {
- _cols.eraseIndex(i);
+ cols.eraseIndex(i);
}
void CbcMip::_eraseRowId(int i) {
- _rows.eraseIndex(i);
+ rows.eraseIndex(i);
}
Index: lemon/clp.cc
===================================================================
--- lemon/clp.cc (revision 1336)
+++ lemon/clp.cc (revision 1270)
@@ -30,6 +30,6 @@
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);
@@ -104,11 +104,11 @@
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);
}
Index: lemon/clp.h
===================================================================
--- lemon/clp.h (revision 1336)
+++ lemon/clp.h (revision 1270)
@@ -152,8 +152,8 @@
///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)); }
};
Index: lemon/concepts/bpgraph.h
===================================================================
--- lemon/concepts/bpgraph.h (revision 1336)
+++ lemon/concepts/bpgraph.h (revision 1270)
@@ -28,5 +28,4 @@
#include
#include
-#include
namespace lemon {
@@ -223,20 +222,4 @@
};
- /// \brief Gets the collection of the red nodes of the graph.
- ///
- /// This function can be used for iterating on
- /// the red nodes of the graph. It returns a wrapped RedNodeIt,
- /// which looks like an STL container (by having begin() and end())
- /// which you can use in range-based for loops, stl algorithms, etc.
- /// For example if g is a BpGraph, you can write:
- ///\code
- /// for(auto v: g.redNodes())
- /// doSomething(v);
- ///\endcode
- LemonRangeWrapper1 redNodes() const {
- return LemonRangeWrapper1(*this);
- }
-
-
/// Iterator class for the blue nodes.
@@ -282,20 +265,4 @@
};
- /// \brief Gets the collection of the blue nodes of the graph.
- ///
- /// This function can be used for iterating on
- /// the blue nodes of the graph. It returns a wrapped BlueNodeIt,
- /// which looks like an STL container (by having begin() and end())
- /// which you can use in range-based for loops, stl algorithms, etc.
- /// For example if g is a BpGraph, you can write:
- ///\code
- /// for(auto v: g.blueNodes())
- /// doSomething(v);
- ///\endcode
- LemonRangeWrapper1 blueNodes() const {
- return LemonRangeWrapper1(*this);
- }
-
-
/// Iterator class for the nodes.
@@ -341,20 +308,4 @@
};
- /// \brief Gets the collection of the nodes of the graph.
- ///
- /// This function can be used for iterating on
- /// the nodes of the graph. It returns a wrapped NodeIt,
- /// which looks like an STL container (by having begin() and end())
- /// which you can use in range-based for loops, stl algorithms, etc.
- /// For example if g is a BpGraph, you can write:
- ///\code
- /// for(auto v: g.nodes())
- /// doSomething(v);
- ///\endcode
- LemonRangeWrapper1 nodes() const {
- return LemonRangeWrapper1(*this);
- }
-
-
/// The edge type of the graph
@@ -445,21 +396,4 @@
};
- /// \brief Gets the collection of the edges of the graph.
- ///
- /// This function can be used for iterating on the
- /// edges of the graph. It returns a wrapped
- /// EdgeIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, stl algorithms, etc.
- /// For example if g is a BpGraph, you can write:
- ///\code
- /// for(auto e: g.edges())
- /// doSomething(e);
- ///\endcode
- LemonRangeWrapper1 edges() const {
- return LemonRangeWrapper1(*this);
- }
-
-
/// Iterator class for the incident edges of a node.
@@ -509,23 +443,4 @@
IncEdgeIt& operator++() { return *this; }
};
-
- /// \brief Gets the collection of the incident edges
- /// of a certain node of the graph.
- ///
- /// This function can be used for iterating on the
- /// incident undirected edges of a certain node of the graph.
- /// It returns a wrapped
- /// IncEdgeIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, stl algorithms, etc.
- /// For example if g is a BpGraph and u is a Node, you can write:
- ///\code
- /// for(auto e: g.incEdges(u))
- /// doSomething(e);
- ///\endcode
- LemonRangeWrapper2 incEdges(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
/// The arc type of the graph
@@ -624,21 +539,4 @@
ArcIt& operator++() { return *this; }
};
-
- /// \brief Gets the collection of the directed arcs of the graph.
- ///
- /// This function can be used for iterating on the
- /// arcs of the graph. It returns a wrapped
- /// ArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, stl algorithms, etc.
- /// For example if g is a BpGraph you can write:
- ///\code
- /// for(auto a: g.arcs())
- /// doSomething(a);
- ///\endcode
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
-
/// Iterator class for the outgoing arcs of a node.
@@ -690,22 +588,4 @@
};
- /// \brief Gets the collection of the outgoing directed arcs of a
- /// certain node of the graph.
- ///
- /// This function can be used for iterating on the
- /// outgoing arcs of a certain node of the graph. It returns a wrapped
- /// OutArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, stl algorithms, etc.
- /// For example if g is a BpGraph and u is a Node, you can write:
- ///\code
- /// for(auto a: g.outArcs(u))
- /// doSomething(a);
- ///\endcode
- LemonRangeWrapper2 outArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
-
/// Iterator class for the incoming arcs of a node.
@@ -756,22 +636,4 @@
};
- /// \brief Gets the collection of the incoming directed arcs of a
- /// certain node of the graph.
- ///
- /// This function can be used for iterating on the
- /// incoming arcs of a certain node of the graph. It returns a wrapped
- /// InArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, stl algorithms, etc.
- /// For example if g is a BpGraph and u is a Node, you can write:
- ///\code
- /// for(auto a: g.inArcs(u))
- /// doSomething(a);
- ///\endcode
- LemonRangeWrapper2 inArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
-
/// \brief Standard graph map type for the nodes.
///
Index: lemon/concepts/digraph.h
===================================================================
--- lemon/concepts/digraph.h (revision 1336)
+++ lemon/concepts/digraph.h (revision 1271)
@@ -28,5 +28,4 @@
#include
#include
-#include
namespace lemon {
@@ -149,23 +148,4 @@
};
- /// \brief Gets the collection of the nodes of the digraph.
- ///
- /// This function can be used for iterating on
- /// the nodes of the digraph. It returns a wrapped NodeIt, which looks
- /// like an STL container (by having begin() and end())
- /// which you can use in range-based for loops, STL algorithms, etc.
- /// For example you can write:
- ///\code
- /// ListDigraph g;
- /// for(auto v: g.nodes())
- /// doSomething(v);
- ///
- /// //Using an STL algorithm:
- /// copy(g.nodes().begin(), g.nodes().end(), vect.begin());
- ///\endcode
- LemonRangeWrapper1 nodes() const {
- return LemonRangeWrapper1(*this);
- }
-
/// The arc type of the digraph
@@ -258,25 +238,4 @@
};
- /// \brief Gets the collection of the outgoing arcs of a certain node
- /// of the digraph.
- ///
- /// This function can be used for iterating on the
- /// outgoing arcs of a certain node of the digraph. It returns a wrapped
- /// OutArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example if g is a Digraph and u is a node, you can write:
- ///\code
- /// for(auto a: g.outArcs(u))
- /// doSomething(a);
- ///
- /// //Using an STL algorithm:
- /// copy(g.outArcs(u).begin(), g.outArcs(u).end(), vect.begin());
- ///\endcode
- LemonRangeWrapper2 outArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
-
/// Iterator class for the incoming arcs of a node.
@@ -324,25 +283,4 @@
};
- /// \brief Gets the collection of the incoming arcs of a certain node
- /// of the digraph.
- ///
- /// This function can be used for iterating on the
- /// incoming arcs of a certain node of the digraph. It returns a wrapped
- /// InArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example if g is a Digraph and u is a node, you can write:
- ///\code
- /// for(auto a: g.inArcs(u))
- /// doSomething(a);
- ///
- /// //Using an STL algorithm:
- /// copy(g.inArcs(u).begin(), g.inArcs(u).end(), vect.begin());
- ///\endcode
- LemonRangeWrapper2 inArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
-
/// Iterator class for the arcs.
@@ -389,25 +327,4 @@
ArcIt& operator++() { return *this; }
};
-
- /// \brief Gets the collection of the arcs of the digraph.
- ///
- /// This function can be used for iterating on the
- /// arcs of the digraph. It returns a wrapped
- /// ArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example you can write:
- ///\code
- /// ListDigraph g;
- /// for(auto a: g.arcs())
- /// doSomething(a);
- ///
- /// //Using an STL algorithm:
- /// copy(g.arcs().begin(), g.arcs().end(), vect.begin());
- ///\endcode
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
-
/// \brief The source node of the arc.
Index: lemon/concepts/graph.h
===================================================================
--- lemon/concepts/graph.h (revision 1336)
+++ lemon/concepts/graph.h (revision 1271)
@@ -28,5 +28,4 @@
#include
#include
-#include
namespace lemon {
@@ -182,23 +181,4 @@
};
- /// \brief Gets the collection of the nodes of the graph.
- ///
- /// This function can be used for iterating on
- /// the nodes of the graph. It returns a wrapped NodeIt, which looks
- /// like an STL container (by having begin() and end())
- /// which you can use in range-based for loops, STL algorithms, etc.
- /// For example you can write:
- ///\code
- /// ListGraph g;
- /// for(auto v: g.nodes())
- /// doSomething(v);
- ///
- /// //Using an STL algorithm:
- /// copy(g.nodes().begin(), g.nodes().end(), vect.begin());
- ///\endcode
- LemonRangeWrapper1 nodes() const {
- return LemonRangeWrapper1(*this);
- }
-
/// The edge type of the graph
@@ -289,25 +269,4 @@
};
- /// \brief Gets the collection of the edges of the graph.
- ///
- /// This function can be used for iterating on the
- /// edges of the graph. It returns a wrapped
- /// EdgeIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example you can write:
- ///\code
- /// ListGraph g;
- /// for(auto e: g.edges())
- /// doSomething(e);
- ///
- /// //Using an STL algorithm:
- /// copy(g.edges().begin(), g.edges().end(), vect.begin());
- ///\endcode
- LemonRangeWrapper1 edges() const {
- return LemonRangeWrapper1(*this);
- }
-
-
/// Iterator class for the incident edges of a node.
@@ -357,26 +316,4 @@
IncEdgeIt& operator++() { return *this; }
};
-
- /// \brief Gets the collection of the incident undirected edges
- /// of a certain node of the graph.
- ///
- /// This function can be used for iterating on the
- /// incident undirected edges of a certain node of the graph.
- /// It returns a wrapped
- /// IncEdgeIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example if g is a Graph and u is a Node, you can write:
- ///\code
- /// for(auto e: g.incEdges(u))
- /// doSomething(e);
- ///
- /// //Using an STL algorithm:
- /// copy(g.incEdges(u).begin(), g.incEdges(u).end(), vect.begin());
- ///\endcode
- LemonRangeWrapper2 incEdges(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
/// The arc type of the graph
@@ -474,25 +411,4 @@
ArcIt& operator++() { return *this; }
};
-
- /// \brief Gets the collection of the directed arcs of the graph.
- ///
- /// This function can be used for iterating on the
- /// arcs of the graph. It returns a wrapped
- /// ArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example you can write:
- ///\code
- /// ListGraph g;
- /// for(auto a: g.arcs())
- /// doSomething(a);
- ///
- /// //Using an STL algorithm:
- /// copy(g.arcs().begin(), g.arcs().end(), vect.begin());
- ///\endcode
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
-
/// Iterator class for the outgoing arcs of a node.
@@ -544,25 +460,4 @@
};
- /// \brief Gets the collection of the outgoing directed arcs of a
- /// certain node of the graph.
- ///
- /// This function can be used for iterating on the
- /// outgoing arcs of a certain node of the graph. It returns a wrapped
- /// OutArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example if g is a Graph and u is a Node, you can write:
- ///\code
- /// for(auto a: g.outArcs(u))
- /// doSomething(a);
- ///
- /// //Using an STL algorithm:
- /// copy(g.outArcs(u).begin(), g.outArcs(u).end(), vect.begin());
- ///\endcode
- LemonRangeWrapper2 outArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
-
/// Iterator class for the incoming arcs of a node.
@@ -613,24 +508,4 @@
};
- /// \brief Gets the collection of the incoming directed arcs of
- /// a certain node of the graph.
- ///
- /// This function can be used for iterating on the
- /// incoming directed arcs of a certain node of the graph. It returns
- /// a wrapped InArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example if g is a Graph and u is a Node, you can write:
- ///\code
- /// for(auto a: g.inArcs(u))
- /// doSomething(a);
- ///
- /// //Using an STL algorithm:
- /// copy(g.inArcs(u).begin(), g.inArcs(u).end(), vect.begin());
- ///\endcode
- LemonRangeWrapper2 inArcs(const Node& u) const {
- return LemonRangeWrapper2(*this, u);
- }
-
/// \brief Standard graph map type for the nodes.
///
Index: lemon/concepts/graph_components.h
===================================================================
--- lemon/concepts/graph_components.h (revision 1270)
+++ lemon/concepts/graph_components.h (revision 1416)
@@ -104,4 +104,5 @@
i1=INVALID;
_GraphItem i2 = i1;
+ ::lemon::ignore_unused_variable_warning(i2);
_GraphItem i3 = INVALID;
@@ -735,4 +736,5 @@
Item bi = it1;
+ ::lemon::ignore_unused_variable_warning(bi);
bi = it2;
}
@@ -825,4 +827,5 @@
++(++it1);
Item e = it1;
+ ::lemon::ignore_unused_variable_warning(e);
e = it2;
}
Index: lemon/concepts/path.h
===================================================================
--- lemon/concepts/path.h (revision 1336)
+++ lemon/concepts/path.h (revision 1416)
@@ -27,5 +27,4 @@
#include
#include
-#include
namespace lemon {
@@ -72,5 +71,7 @@
/// \brief Template copy constructor
template
- Path(const CPath& cpath) {}
+ Path(const CPath& cpath) {
+ ::lemon::ignore_unused_variable_warning(cpath);
+ }
/// \brief Template assigment operator
@@ -117,21 +118,4 @@
};
- /// \brief Gets the collection of the arcs of the path.
- ///
- /// This function can be used for iterating on the
- /// arcs of the path. It returns a wrapped
- /// ArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example you can write:
- ///\code
- /// for(auto a: p.arcs())
- /// doSomething(a);
- ///\endcode
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
-
-
template
struct Constraints {
@@ -282,21 +266,4 @@
};
-
- /// \brief Gets the collection of the arcs of the path.
- ///
- /// This function can be used for iterating on the
- /// arcs of the path. It returns a wrapped
- /// ArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example you can write:
- ///\code
- /// for(auto a: p.arcs())
- /// doSomething(a);
- ///\endcode
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
-
/// \brief LEMON style iterator for enumerating the arcs of a path
@@ -329,22 +296,4 @@
};
- /// \brief Gets the collection of the arcs of the path
- /// in reverse direction.
- ///
- /// This function can be used for iterating on the
- /// arcs of the path in reverse direction. It returns a wrapped
- /// RevArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example you can write:
- ///\code
- /// for(auto a: p.revArcs())
- /// doSomething(a);
- ///\endcode
- LemonRangeWrapper1 revArcs() const {
- return LemonRangeWrapper1(*this);
- }
-
-
template
struct Constraints {
Index: lemon/config.h.in
===================================================================
--- lemon/config.h.in (revision 1343)
+++ lemon/config.h.in (revision 1416)
@@ -3,7 +3,6 @@
#define LEMON_VERSION "@PROJECT_VERSION@"
+
#cmakedefine LEMON_HAVE_LONG_LONG 1
-
-#cmakedefine LEMON_CXX11 1
#cmakedefine LEMON_WIN32 1
@@ -29,3 +28,5 @@
#cmakedefine LEMON_USE_WIN32_THREADS 1
+#cmakedefine LEMON_NO_UNUSED_LOCAL_TYPEDEF_WARNINGS 1
+
#endif
Index: lemon/core.h
===================================================================
--- lemon/core.h (revision 1341)
+++ lemon/core.h (revision 1416)
@@ -34,10 +34,13 @@
// C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
// C4996: 'function': was declared deprecated
+
+#include
+
#ifdef _MSC_VER
#pragma warning( disable : 4250 4267 4355 4503 4800 4996 )
#endif
-#if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)
-// Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8
+#if LEMON_NO_UNUSED_LOCAL_TYPEDEF_WARNINGS
+// Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc >=4.8 and clang
#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
#endif
@@ -46,5 +49,4 @@
#include
-#include
#include
#include
Index: lemon/cplex.cc
===================================================================
--- lemon/cplex.cc (revision 1349)
+++ lemon/cplex.cc (revision 1347)
@@ -105,6 +105,6 @@
int status;
_prob = CPXcloneprob(cplexEnv(), cplex._prob, &status);
- _rows = cplex._rows;
- _cols = cplex._cols;
+ rows = cplex.rows;
+ cols = cplex.cols;
messageLevel(MESSAGE_NOTHING);
}
@@ -133,8 +133,21 @@
ExprIterator e, Value ub) {
int i = CPXgetnumrows(cplexEnv(), _prob);
-
- int rmatbeg = 0;
-
+ if (lb == -INF) {
+ const char s = 'L';
+ CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
+ } else if (ub == INF) {
+ const char s = 'G';
+ CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
+ } else if (lb == ub){
+ const char s = 'E';
+ CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
+ } else {
+ const char s = 'R';
+ double len = ub - lb;
+ CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
+ }
+
std::vector indices;
+ std::vector rowlist;
std::vector values;
@@ -142,26 +155,10 @@
indices.push_back(it->first);
values.push_back(it->second);
- }
-
- if (lb == -INF) {
- const char s = 'L';
- CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &ub, &s,
- &rmatbeg, &indices.front(), &values.front(), 0, 0);
- } else if (ub == INF) {
- const char s = 'G';
- CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &lb, &s,
- &rmatbeg, &indices.front(), &values.front(), 0, 0);
- } else if (lb == ub){
- const char s = 'E';
- 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;
- CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &ub, &s,
- &rmatbeg, &indices.front(), &values.front(), 0, 0);
- CPXchgrngval(cplexEnv(), _prob, 1, &i, &len);
- }
-
+ rowlist.push_back(i);
+ }
+
+ CPXchgcoeflist(cplexEnv(), _prob, values.size(),
+ &rowlist.front(), &indices.front(), &values.front());
+
return i;
}
@@ -176,10 +173,10 @@
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);
}
Index: lemon/dfs.h
===================================================================
--- lemon/dfs.h (revision 1270)
+++ lemon/dfs.h (revision 1416)
@@ -1319,5 +1319,5 @@
struct SetReachedMapTraits : public Traits {
typedef T ReachedMap;
- static ReachedMap *createReachedMap(const Digraph &digraph) {
+ static ReachedMap *createReachedMap(const Digraph &) {
LEMON_ASSERT(false, "ReachedMap is not initialized");
return 0; // ignore warnings
Index: lemon/glpk.cc
===================================================================
--- lemon/glpk.cc (revision 1336)
+++ lemon/glpk.cc (revision 1270)
@@ -39,6 +39,6 @@
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);
}
@@ -109,11 +109,11 @@
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);
}
Index: lemon/glpk.h
===================================================================
--- lemon/glpk.h (revision 1336)
+++ lemon/glpk.h (revision 1270)
@@ -142,8 +142,8 @@
///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
Index: lemon/lgf_reader.h
===================================================================
--- lemon/lgf_reader.h (revision 1377)
+++ lemon/lgf_reader.h (revision 1270)
@@ -452,11 +452,11 @@
///
///\code
- /// DigraphReader(digraph, std::cin)
- /// .nodeMap("coordinates", coord_map)
- /// .arcMap("capacity", cap_map)
- /// .node("source", src)
- /// .node("target", trg)
- /// .attribute("caption", caption)
- /// .run();
+ /// DigraphReader(digraph, std::cin).
+ /// nodeMap("coordinates", coord_map).
+ /// arcMap("capacity", cap_map).
+ /// node("source", src).
+ /// node("target", trg).
+ /// attribute("caption", caption).
+ /// run();
///\endcode
///
@@ -1245,11 +1245,11 @@
///\code
///ListDigraph digraph;
- ///ListDigraph::ArcMap cap(digraph);
+ ///ListDigraph::ArcMap cm(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
///
@@ -2124,7 +2124,7 @@
///ListGraph graph;
///ListGraph::EdgeMap weight(graph);
- ///graphReader(graph, std::cin)
- /// .edgeMap("weight", weight)
- /// .run();
+ ///graphReader(graph, std::cin).
+ /// edgeMap("weight", weight).
+ /// run();
///\endcode
///
@@ -3192,7 +3192,7 @@
///ListBpGraph graph;
///ListBpGraph::EdgeMap weight(graph);
- ///bpGraphReader(graph, std::cin)
- /// .edgeMap("weight", weight)
- /// .run();
+ ///bpGraphReader(graph, std::cin).
+ /// edgeMap("weight", weight).
+ /// run();
///\endcode
///
Index: lemon/lgf_writer.h
===================================================================
--- lemon/lgf_writer.h (revision 1377)
+++ lemon/lgf_writer.h (revision 1270)
@@ -409,13 +409,13 @@
///
///\code
- /// DigraphWriter(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(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
///
@@ -962,9 +962,9 @@
///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
///
@@ -1600,7 +1600,7 @@
///ListGraph::EdgeMap weight(graph);
/// // Setting the weight map
- ///graphWriter(graph, std::cout)
- /// .edgeMap("weight", weight)
- /// .run();
+ ///graphWriter(graph, std::cout).
+ /// edgeMap("weight", weight).
+ /// run();
///\endcode
///
@@ -2420,7 +2420,7 @@
///ListBpGraph::EdgeMap weight(graph);
/// // Setting the weight map
- ///bpGraphWriter(graph, std::cout)
- /// .edgeMap("weight", weight)
- /// .run();
+ ///bpGraphWriter(graph, std::cout).
+ /// edgeMap("weight", weight).
+ /// run();
///\endcode
///
Index: lemon/list_graph.h
===================================================================
--- lemon/list_graph.h (revision 1359)
+++ lemon/list_graph.h (revision 1357)
@@ -49,5 +49,5 @@
};
- std::vector _nodes;
+ std::vector nodes;
int first_node;
@@ -55,5 +55,5 @@
int first_free_node;
- std::vector _arcs;
+ std::vector arcs;
int first_free_arc;
@@ -98,13 +98,13 @@
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); }
@@ -114,5 +114,5 @@
void next(Node& node) const {
- node.id = _nodes[node.id].next;
+ node.id = nodes[node.id].next;
}
@@ -121,33 +121,33 @@
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;
}
@@ -160,11 +160,11 @@
bool valid(Node n) const {
- return n.id >= 0 && n.id < static_cast(_nodes.size()) &&
- _nodes[n.id].prev != -2;
+ return n.id >= 0 && n.id < static_cast(nodes.size()) &&
+ nodes[n.id].prev != -2;
}
bool valid(Arc a) const {
- return a.id >= 0 && a.id < static_cast(_arcs.size()) &&
- _arcs[a.id].prev_in != -2;
+ return a.id >= 0 && a.id < static_cast(arcs.size()) &&
+ arcs[a.id].prev_in != -2;
}
@@ -173,17 +173,17 @@
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);
@@ -194,27 +194,27 @@
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);
@@ -224,17 +224,17 @@
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;
}
@@ -243,33 +243,33 @@
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;
}
@@ -278,31 +278,31 @@
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;
}
@@ -487,8 +487,8 @@
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);
@@ -533,5 +533,5 @@
/// to build the digraph.
/// \sa reserveArc()
- void reserveNode(int n) { _nodes.reserve(n); };
+ void reserveNode(int n) { nodes.reserve(n); };
/// Reserve memory for arcs.
@@ -543,5 +543,5 @@
/// 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
@@ -804,5 +804,5 @@
};
- std::vector _nodes;
+ std::vector nodes;
int first_node;
@@ -810,5 +810,5 @@
int first_free_node;
- std::vector _arcs;
+ std::vector arcs;
int first_free_arc;
@@ -868,17 +868,17 @@
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) {
@@ -895,24 +895,24 @@
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;
}
}
@@ -921,7 +921,7 @@
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) {
@@ -929,5 +929,5 @@
return;
}
- n = _nodes[n].next;
+ n = nodes[n].next;
}
e.id = -1;
@@ -935,8 +935,8 @@
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) {
@@ -944,9 +944,9 @@
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) {
@@ -954,5 +954,5 @@
return;
}
- n = _nodes[n].next;
+ n = nodes[n].next;
}
e.id = -1;
@@ -960,21 +960,21 @@
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;
@@ -986,5 +986,5 @@
}
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;
@@ -1005,16 +1005,16 @@
bool valid(Node n) const {
- return n.id >= 0 && n.id < static_cast(_nodes.size()) &&
- _nodes[n.id].prev != -2;
+ return n.id >= 0 && n.id < static_cast(nodes.size()) &&
+ nodes[n.id].prev != -2;
}
bool valid(Arc a) const {
- return a.id >= 0 && a.id < static_cast(_arcs.size()) &&
- _arcs[a.id].prev_out != -2;
+ return a.id >= 0 && a.id < static_cast(arcs.size()) &&
+ arcs[a.id].prev_out != -2;
}
bool valid(Edge e) const {
- return e.id >= 0 && 2 * e.id < static_cast(_arcs.size()) &&
- _arcs[2 * e.id].prev_out != -2;
+ return e.id >= 0 && 2 * e.id < static_cast(arcs.size()) &&
+ arcs[2 * e.id].prev_out != -2;
}
@@ -1023,17 +1023,17 @@
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);
@@ -1044,28 +1044,28 @@
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);
@@ -1075,17 +1075,17 @@
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;
}
@@ -1093,34 +1093,34 @@
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;
}
@@ -1129,44 +1129,44 @@
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);
}
@@ -1210,5 +1210,5 @@
ListGraph() {}
- typedef Parent::IncEdgeIt IncEdgeIt;
+ typedef Parent::OutArcIt IncEdgeIt;
/// \brief Add a new node to the graph.
@@ -1345,5 +1345,5 @@
/// to build the graph.
/// \sa reserveEdge()
- void reserveNode(int n) { _nodes.reserve(n); };
+ void reserveNode(int n) { nodes.reserve(n); };
/// Reserve memory for edges.
@@ -1355,5 +1355,5 @@
/// 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
@@ -1618,5 +1618,5 @@
};
- std::vector _nodes;
+ std::vector nodes;
int first_node, first_red, first_blue;
@@ -1625,5 +1625,5 @@
int first_free_red, first_free_blue;
- std::vector _arcs;
+ std::vector arcs;
int first_free_arc;
@@ -1707,31 +1707,31 @@
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);
}
@@ -1749,5 +1749,5 @@
void next(Node& node) const {
- node.id = _nodes[node.id].next;
+ node.id = nodes[node.id].next;
}
@@ -1757,5 +1757,5 @@
void next(RedNode& node) const {
- node.id = _nodes[node.id].partition_next;
+ node.id = nodes[node.id].partition_next;
}
@@ -1765,24 +1765,24 @@
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;
}
}
@@ -1791,7 +1791,7 @@
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) {
@@ -1799,5 +1799,5 @@
return;
}
- n = _nodes[n].next;
+ n = nodes[n].next;
}
e.id = -1;
@@ -1805,8 +1805,8 @@
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) {
@@ -1814,9 +1814,9 @@
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) {
@@ -1824,5 +1824,5 @@
return;
}
- n = _nodes[n].next;
+ n = nodes[n].next;
}
e.id = -1;
@@ -1830,21 +1830,21 @@
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;
@@ -1856,5 +1856,5 @@
}
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;
@@ -1867,6 +1867,6 @@
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; }
@@ -1877,16 +1877,16 @@
bool valid(Node n) const {
- return n.id >= 0 && n.id < static_cast(_nodes.size()) &&
- _nodes[n.id].prev != -2;
+ return n.id >= 0 && n.id < static_cast(nodes.size()) &&
+ nodes[n.id].prev != -2;
}
bool valid(Arc a) const {
- return a.id >= 0 && a.id < static_cast(_arcs.size()) &&
- _arcs[a.id].prev_out != -2;
+ return a.id >= 0 && a.id < static_cast(arcs.size()) &&
+ arcs[a.id].prev_out != -2;
}
bool valid(Edge e) const {
- return e.id >= 0 && 2 * e.id < static_cast(_arcs.size()) &&
- _arcs[2 * e.id].prev_out != -2;
+ return e.id >= 0 && 2 * e.id < static_cast(arcs.size()) &&
+ arcs[2 * e.id].prev_out != -2;
}
@@ -1895,24 +1895,24 @@
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);
@@ -1923,24 +1923,24 @@
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);
@@ -1951,28 +1951,28 @@
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);
@@ -1982,36 +1982,36 @@
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;
}
@@ -2019,34 +2019,34 @@
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;
@@ -2056,44 +2056,44 @@
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;
}
@@ -2137,5 +2137,5 @@
ListBpGraph() {}
- typedef Parent::IncEdgeIt IncEdgeIt;
+ typedef Parent::OutArcIt IncEdgeIt;
/// \brief Add a new red node to the graph.
@@ -2250,5 +2250,5 @@
/// to build the graph.
/// \sa reserveEdge()
- void reserveNode(int n) { _nodes.reserve(n); };
+ void reserveNode(int n) { nodes.reserve(n); };
/// Reserve memory for edges.
@@ -2260,5 +2260,5 @@
/// 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
Index: lemon/lp_base.h
===================================================================
--- lemon/lp_base.h (revision 1353)
+++ lemon/lp_base.h (revision 1270)
@@ -32,6 +32,4 @@
#include
-#include
-
///\file
///\brief The interface of the LP solver interface.
@@ -48,6 +46,6 @@
protected:
- _solver_bits::VarIndex _rows;
- _solver_bits::VarIndex _cols;
+ _solver_bits::VarIndex rows;
+ _solver_bits::VarIndex cols;
public:
@@ -169,5 +167,5 @@
ColIt(const LpBase &solver) : _solver(&solver)
{
- _solver->_cols.firstItem(_id);
+ _solver->cols.firstItem(_id);
}
/// Invalid constructor \& conversion
@@ -182,24 +180,8 @@
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 cols() {
- return LemonRangeWrapper1(*this);
- }
-
/// \brief Returns the ID of the column.
@@ -280,5 +262,5 @@
RowIt(const LpBase &solver) : _solver(&solver)
{
- _solver->_rows.firstItem(_id);
+ _solver->rows.firstItem(_id);
}
/// Invalid constructor \& conversion
@@ -293,24 +275,8 @@
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 rows() {
- return LemonRangeWrapper1(*this);
- }
-
/// \brief Returns the ID of the row.
@@ -660,5 +626,5 @@
///This data structure represents a column of the matrix,
///thas is it strores a linear expression of the dual variables
- ///(\ref LpBase::Row "Row"s).
+ ///(\ref Row "Row"s).
///
///There are several ways to access and modify the contents of this
@@ -677,5 +643,5 @@
///(This code computes the sum of all coefficients).
///- Numbers (double's)
- ///and variables (\ref LpBase::Row "Row"s) directly convert to an
+ ///and variables (\ref Row "Row"s) directly convert to an
///\ref DualExpr and the usual linear operations are defined, so
///\code
@@ -969,9 +935,9 @@
//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;
@@ -1038,5 +1004,5 @@
Value obj_const_comp;
- LpBase() : _rows(), _cols(), obj_const_comp(0) {}
+ LpBase() : rows(), cols(), obj_const_comp(0) {}
public:
@@ -1150,6 +1116,6 @@
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));
}
@@ -1160,5 +1126,5 @@
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;
}
@@ -1189,5 +1155,5 @@
///\param t can be
///- a standard STL compatible iterable container with
- ///\ref LpBase::Row "Row" as its \c values_type like
+ ///\ref Row as its \c values_type like
///\code
///std::vector
@@ -1195,5 +1161,5 @@
///\endcode
///- a standard STL compatible iterable container with
- ///\ref LpBase::Row "Row" as its \c mapped_type like
+ ///\ref Row as its \c mapped_type like
///\code
///std::map
@@ -1247,8 +1213,8 @@
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);
}
@@ -1269,5 +1235,5 @@
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;
}
@@ -1282,6 +1248,6 @@
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;
}
@@ -1295,6 +1261,6 @@
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;
@@ -1304,6 +1270,6 @@
///\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
@@ -1311,6 +1277,6 @@
///\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)));
}
@@ -1321,5 +1287,5 @@
std::string colName(Col c) const {
std::string name;
- _getColName(_cols(id(c)), name);
+ _getColName(cols(id(c)), name);
return name;
}
@@ -1330,5 +1296,5 @@
///\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);
}
@@ -1339,5 +1305,5 @@
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);
}
@@ -1348,5 +1314,5 @@
std::string rowName(Row r) const {
std::string name;
- _getRowName(_rows(id(r)), name);
+ _getRowName(rows(id(r)), name);
return name;
}
@@ -1357,5 +1323,5 @@
///\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);
}
@@ -1366,5 +1332,5 @@
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);
}
@@ -1375,5 +1341,5 @@
///\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);
}
@@ -1384,5 +1350,5 @@
///\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)));
}
@@ -1393,5 +1359,5 @@
/// Value or -\ref INF.
void colLowerBound(Col c, Value value) {
- _setColLowerBound(_cols(id(c)),value);
+ _setColLowerBound(cols(id(c)),value);
}
@@ -1402,5 +1368,5 @@
///\return The lower bound for column \c c
Value colLowerBound(Col c) const {
- return _getColLowerBound(_cols(id(c)));
+ return _getColLowerBound(cols(id(c)));
}
@@ -1448,5 +1414,5 @@
/// Value or \ref INF.
void colUpperBound(Col c, Value value) {
- _setColUpperBound(_cols(id(c)),value);
+ _setColUpperBound(cols(id(c)),value);
};
@@ -1457,5 +1423,5 @@
/// \return The upper bound for column \c c
Value colUpperBound(Col c) const {
- return _getColUpperBound(_cols(id(c)));
+ return _getColUpperBound(cols(id(c)));
}
@@ -1504,6 +1470,6 @@
/// 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);
}
@@ -1550,5 +1516,5 @@
/// Value or -\ref INF.
void rowLowerBound(Row r, Value value) {
- _setRowLowerBound(_rows(id(r)),value);
+ _setRowLowerBound(rows(id(r)),value);
}
@@ -1559,5 +1525,5 @@
///\return The lower bound for row \c r
Value rowLowerBound(Row r) const {
- return _getRowLowerBound(_rows(id(r)));
+ return _getRowLowerBound(rows(id(r)));
}
@@ -1568,5 +1534,5 @@
/// Value or -\ref INF.
void rowUpperBound(Row r, Value value) {
- _setRowUpperBound(_rows(id(r)),value);
+ _setRowUpperBound(rows(id(r)),value);
}
@@ -1577,12 +1543,12 @@
///\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
@@ -1591,6 +1557,6 @@
///
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;
}
@@ -1602,5 +1568,5 @@
Expr obj() const {
Expr e;
- _getObjCoeffs(InsertIterator(e.comps, _cols));
+ _getObjCoeffs(InsertIterator(e.comps, cols));
*e = obj_const_comp;
return e;
@@ -1621,5 +1587,5 @@
///Clear the problem
- void clear() { _clear(); _rows.clear(); _cols.clear(); }
+ void clear() { _clear(); rows.clear(); cols.clear(); }
/// Set the message level of the solver
@@ -1964,5 +1930,5 @@
/// 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
@@ -1991,5 +1957,5 @@
/// \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
@@ -1997,5 +1963,5 @@
/// 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
@@ -2025,15 +1991,15 @@
/// \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
@@ -2115,5 +2081,5 @@
///
void colType(Col c, ColTypes col_type) {
- _setColType(_cols(id(c)),col_type);
+ _setColType(cols(id(c)),col_type);
}
@@ -2123,5 +2089,5 @@
///
ColTypes colType(Col c) const {
- return _getColType(_cols(id(c)));
+ return _getColType(cols(id(c)));
}
///@}
@@ -2140,5 +2106,5 @@
/// 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
Index: lemon/maps.h
===================================================================
--- lemon/maps.h (revision 1336)
+++ lemon/maps.h (revision 1270)
@@ -26,5 +26,4 @@
#include
-#include
///\file
@@ -2583,14 +2582,4 @@
};
- /// \brief STL style iterator for the keys mapped to \c true.
- ///
- /// This is an STL style wrapper for \ref TrueIt.
- /// It can be used in range-based for loops, STL algorithms, etc.
- LemonRangeWrapper1
- trueKeys() {
- return LemonRangeWrapper1(*this);
- }
-
-
/// \brief Iterator for the keys mapped to \c false.
///
@@ -2631,14 +2620,4 @@
const IterableBoolMap* _map;
};
-
- /// \brief STL style iterator for the keys mapped to \c false.
- ///
- /// This is an STL style wrapper for \ref FalseIt.
- /// It can be used in range-based for loops, STL algorithms, etc.
- LemonRangeWrapper1
- falseKeys() {
- return LemonRangeWrapper1(*this);
- }
-
/// \brief Iterator for the keys mapped to a given value.
@@ -2685,13 +2664,4 @@
const IterableBoolMap* _map;
};
-
- /// \brief STL style iterator for the keys mapped to a given value.
- ///
- /// This is an STL style wrapper for \ref ItemIt.
- /// It can be used in range-based for loops, STL algorithms, etc.
- LemonRangeWrapper2
- items(bool value) {
- return LemonRangeWrapper2(*this, value);
- }
protected:
@@ -3036,14 +3006,4 @@
};
- /// \brief STL style iterator for the keys with the same value.
- ///
- /// This is an STL style wrapper for \ref ItemIt.
- /// It can be used in range-based for loops, STL algorithms, etc.
- LemonRangeWrapper2
- items(int value) {
- return LemonRangeWrapper2(*this, value);
- }
-
-
protected:
@@ -3289,14 +3249,4 @@
};
- /// \brief STL style iterator for the keys with the same value.
- ///
- /// This is an STL style wrapper for \ref ItemIt.
- /// It can be used in range-based for loops, STL algorithms, etc.
- LemonRangeWrapper2
- items(const V& value) {
- return LemonRangeWrapper2(*this, value);
- }
-
-
protected:
Index: lemon/nagamochi_ibaraki.h
===================================================================
--- lemon/nagamochi_ibaraki.h (revision 1270)
+++ lemon/nagamochi_ibaraki.h (revision 1416)
@@ -175,5 +175,5 @@
typedef CR HeapCrossRef;
typedef H Heap;
- static HeapCrossRef *createHeapCrossRef(int num) {
+ static HeapCrossRef *createHeapCrossRef(int) {
LEMON_ASSERT(false, "HeapCrossRef is not initialized");
return 0; // ignore warnings
Index: lemon/path.h
===================================================================
--- lemon/path.h (revision 1336)
+++ lemon/path.h (revision 1270)
@@ -31,5 +31,4 @@
#include
#include
-#include
namespace lemon {
@@ -141,21 +140,4 @@
int idx;
};
-
- /// \brief Gets the collection of the arcs of the path.
- ///
- /// This function can be used for iterating on the
- /// arcs of the path. It returns a wrapped
- /// ArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example you can write:
- ///\code
- /// for(auto a: p.arcs())
- /// doSomething(a);
- ///\endcode
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
-
/// \brief Length of the path.
@@ -364,21 +346,4 @@
};
- /// \brief Gets the collection of the arcs of the path.
- ///
- /// This function can be used for iterating on the
- /// arcs of the path. It returns a wrapped
- /// ArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example you can write:
- ///\code
- /// for(auto a: p.arcs())
- /// doSomething(a);
- ///\endcode
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
-
-
/// \brief Length of the path.
int length() const { return data.size(); }
@@ -578,21 +543,4 @@
Node *node;
};
-
- /// \brief Gets the collection of the arcs of the path.
- ///
- /// This function can be used for iterating on the
- /// arcs of the path. It returns a wrapped
- /// ArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example you can write:
- ///\code
- /// for(auto a: p.arcs())
- /// doSomething(a);
- ///\endcode
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
-
/// \brief The n-th arc.
@@ -848,9 +796,9 @@
///
/// 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);
}
@@ -860,5 +808,5 @@
/// This path can be initialized from any other path type.
template
- StaticPath(const CPath& cpath) : _arcs(0) {
+ StaticPath(const CPath& cpath) : arcs(0) {
pathCopy(cpath, *this);
}
@@ -868,5 +816,5 @@
/// Destructor of the path
~StaticPath() {
- if (_arcs) delete[] _arcs;
+ if (arcs) delete[] arcs;
}
@@ -935,21 +883,4 @@
int idx;
};
-
- /// \brief Gets the collection of the arcs of the path.
- ///
- /// This function can be used for iterating on the
- /// arcs of the path. It returns a wrapped
- /// ArcIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example you can write:
- ///\code
- /// for(auto a: p.arcs())
- /// doSomething(a);
- ///\endcode
- LemonRangeWrapper1 arcs() const {
- return LemonRangeWrapper1(*this);
- }
-
/// \brief The n-th arc.
@@ -957,5 +888,5 @@
/// \pre \c n is in the [0..length() - 1] range.
const Arc& nth(int n) const {
- return _arcs[n];
+ return arcs[n];
}
@@ -974,16 +905,16 @@
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];
}
@@ -994,8 +925,8 @@
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;
}
@@ -1005,9 +936,9 @@
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;
}
}
@@ -1015,5 +946,5 @@
private:
int len;
- Arc* _arcs;
+ Arc* arcs;
};
@@ -1227,23 +1158,4 @@
};
- /// \brief Gets the collection of the nodes of the path.
- ///
- /// This function can be used for iterating on the
- /// nodes of the path. It returns a wrapped
- /// PathNodeIt, which looks like an STL container
- /// (by having begin() and end()) which you can use in range-based
- /// for loops, STL algorithms, etc.
- /// For example you can write:
- ///\code
- /// for(auto u: pathNodes(g,p))
- /// doSomething(u);
- ///\endcode
- template
- LemonRangeWrapper2, typename Path::Digraph, Path>
- pathNodes(const typename Path::Digraph &g, const Path &p) {
- return
- LemonRangeWrapper2, typename Path::Digraph, Path>(g,p);
- }
-
///@}
Index: lemon/random.h
===================================================================
--- lemon/random.h (revision 1404)
+++ lemon/random.h (revision 1396)
@@ -111,4 +111,5 @@
static const Word loMask = (1u << 31) - 1;
static const Word hiMask = ~loMask;
+
static Word tempering(Word rnd) {
@@ -243,4 +244,5 @@
private:
+
void fillState() {
static const Word mask[2] = { 0x0ul, RandomTraits::mask };
@@ -250,6 +252,6 @@
current = state + length;
- Word *curr = state + length - 1;
- long num;
+ register Word *curr = state + length - 1;
+ register long num;
num = length - shift;
@@ -270,4 +272,5 @@
}
+
Word *current;
Word state[length];
@@ -294,5 +297,5 @@
template ::digits, int shift = 0,
- bool last = (rest <= std::numeric_limits::digits)>
+ bool last = rest <= std::numeric_limits::digits>
struct IntConversion {
static const int bits = std::numeric_limits::digits;
@@ -463,544 +466,5 @@
};
- /// \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(); // 0 .. 2^31 - 1
- /// int c = rnd.integer(); // - 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 Random {
- private:
-
- _random_bits::RandomCore core;
- _random_bits::BoolProducer 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
- Random(Number seed) {
- _random_bits::Initializer::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
- Random(Iterator begin, Iterator end) {
- typedef typename std::iterator_traits::value_type Number;
- _random_bits::Initializer::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
- void seed(Number seed) {
- _random_bits::Initializer::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
- void seed(Iterator begin, Iterator end) {
- typedef typename std::iterator_traits::value_type Number;
- _random_bits::Initializer::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 /dev/urandom 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, /dev/random and /dev/urandom which
- /// could give good seed values for pseudo random generators (The
- /// difference between two devices is that the random may
- /// block the reading operation while the kernel can give good
- /// source of randomness, while the urandom 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(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
- Number real() {
- return _random_bits::RealConversion::convert(core);
- }
-
- double real() {
- return real