1.1 --- a/lemon/adaptors.h Mon Jan 12 23:11:39 2009 +0100
1.2 +++ b/lemon/adaptors.h Thu Nov 05 15:48:01 2009 +0100
1.3 @@ -30,29 +30,35 @@
1.4 #include <lemon/bits/variant.h>
1.5
1.6 #include <lemon/bits/graph_adaptor_extender.h>
1.7 +#include <lemon/bits/map_extender.h>
1.8 #include <lemon/tolerance.h>
1.9
1.10 #include <algorithm>
1.11
1.12 namespace lemon {
1.13
1.14 - template<typename _Digraph>
1.15 +#ifdef _MSC_VER
1.16 +#define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED
1.17 +#else
1.18 +#define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED
1.19 +#endif
1.20 +
1.21 + template<typename DGR>
1.22 class DigraphAdaptorBase {
1.23 public:
1.24 - typedef _Digraph Digraph;
1.25 + typedef DGR Digraph;
1.26 typedef DigraphAdaptorBase Adaptor;
1.27 - typedef Digraph ParentDigraph;
1.28
1.29 protected:
1.30 - Digraph* _digraph;
1.31 + DGR* _digraph;
1.32 DigraphAdaptorBase() : _digraph(0) { }
1.33 - void setDigraph(Digraph& digraph) { _digraph = &digraph; }
1.34 + void initialize(DGR& digraph) { _digraph = &digraph; }
1.35
1.36 public:
1.37 - DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
1.38 -
1.39 - typedef typename Digraph::Node Node;
1.40 - typedef typename Digraph::Arc Arc;
1.41 + DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { }
1.42 +
1.43 + typedef typename DGR::Node Node;
1.44 + typedef typename DGR::Arc Arc;
1.45
1.46 void first(Node& i) const { _digraph->first(i); }
1.47 void first(Arc& i) const { _digraph->first(i); }
1.48 @@ -67,13 +73,13 @@
1.49 Node source(const Arc& a) const { return _digraph->source(a); }
1.50 Node target(const Arc& a) const { return _digraph->target(a); }
1.51
1.52 - typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1.53 + typedef NodeNumTagIndicator<DGR> NodeNumTag;
1.54 int nodeNum() const { return _digraph->nodeNum(); }
1.55
1.56 - typedef ArcNumTagIndicator<Digraph> ArcNumTag;
1.57 + typedef ArcNumTagIndicator<DGR> ArcNumTag;
1.58 int arcNum() const { return _digraph->arcNum(); }
1.59
1.60 - typedef FindArcTagIndicator<Digraph> FindArcTag;
1.61 + typedef FindArcTagIndicator<DGR> FindArcTag;
1.62 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
1.63 return _digraph->findArc(u, v, prev);
1.64 }
1.65 @@ -95,22 +101,20 @@
1.66 int maxNodeId() const { return _digraph->maxNodeId(); }
1.67 int maxArcId() const { return _digraph->maxArcId(); }
1.68
1.69 - typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
1.70 + typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
1.71 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
1.72
1.73 - typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
1.74 + typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;
1.75 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
1.76
1.77 - template <typename _Value>
1.78 - class NodeMap : public Digraph::template NodeMap<_Value> {
1.79 + template <typename V>
1.80 + class NodeMap : public DGR::template NodeMap<V> {
1.81 + typedef typename DGR::template NodeMap<V> Parent;
1.82 +
1.83 public:
1.84 -
1.85 - typedef typename Digraph::template NodeMap<_Value> Parent;
1.86 -
1.87 explicit NodeMap(const Adaptor& adaptor)
1.88 : Parent(*adaptor._digraph) {}
1.89 -
1.90 - NodeMap(const Adaptor& adaptor, const _Value& value)
1.91 + NodeMap(const Adaptor& adaptor, const V& value)
1.92 : Parent(*adaptor._digraph, value) { }
1.93
1.94 private:
1.95 @@ -126,16 +130,14 @@
1.96
1.97 };
1.98
1.99 - template <typename _Value>
1.100 - class ArcMap : public Digraph::template ArcMap<_Value> {
1.101 + template <typename V>
1.102 + class ArcMap : public DGR::template ArcMap<V> {
1.103 + typedef typename DGR::template ArcMap<V> Parent;
1.104 +
1.105 public:
1.106 -
1.107 - typedef typename Digraph::template ArcMap<_Value> Parent;
1.108 -
1.109 - explicit ArcMap(const Adaptor& adaptor)
1.110 + explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
1.111 : Parent(*adaptor._digraph) {}
1.112 -
1.113 - ArcMap(const Adaptor& adaptor, const _Value& value)
1.114 + ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)
1.115 : Parent(*adaptor._digraph, value) {}
1.116
1.117 private:
1.118 @@ -153,25 +155,24 @@
1.119
1.120 };
1.121
1.122 - template<typename _Graph>
1.123 + template<typename GR>
1.124 class GraphAdaptorBase {
1.125 public:
1.126 - typedef _Graph Graph;
1.127 - typedef Graph ParentGraph;
1.128 + typedef GR Graph;
1.129
1.130 protected:
1.131 - Graph* _graph;
1.132 + GR* _graph;
1.133
1.134 GraphAdaptorBase() : _graph(0) {}
1.135
1.136 - void setGraph(Graph& graph) { _graph = &graph; }
1.137 + void initialize(GR& graph) { _graph = &graph; }
1.138
1.139 public:
1.140 - GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
1.141 -
1.142 - typedef typename Graph::Node Node;
1.143 - typedef typename Graph::Arc Arc;
1.144 - typedef typename Graph::Edge Edge;
1.145 + GraphAdaptorBase(GR& graph) : _graph(&graph) {}
1.146 +
1.147 + typedef typename GR::Node Node;
1.148 + typedef typename GR::Arc Arc;
1.149 + typedef typename GR::Edge Edge;
1.150
1.151 void first(Node& i) const { _graph->first(i); }
1.152 void first(Arc& i) const { _graph->first(i); }
1.153 @@ -239,22 +240,23 @@
1.154 int maxArcId() const { return _graph->maxArcId(); }
1.155 int maxEdgeId() const { return _graph->maxEdgeId(); }
1.156
1.157 - typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.158 + typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
1.159 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
1.160
1.161 - typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
1.162 + typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
1.163 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
1.164
1.165 - typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
1.166 + typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier;
1.167 EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
1.168
1.169 - template <typename _Value>
1.170 - class NodeMap : public Graph::template NodeMap<_Value> {
1.171 + template <typename V>
1.172 + class NodeMap : public GR::template NodeMap<V> {
1.173 + typedef typename GR::template NodeMap<V> Parent;
1.174 +
1.175 public:
1.176 - typedef typename Graph::template NodeMap<_Value> Parent;
1.177 - explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
1.178 + explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
1.179 : Parent(*adapter._graph) {}
1.180 - NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
1.181 + NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
1.182 : Parent(*adapter._graph, value) {}
1.183
1.184 private:
1.185 @@ -270,13 +272,14 @@
1.186
1.187 };
1.188
1.189 - template <typename _Value>
1.190 - class ArcMap : public Graph::template ArcMap<_Value> {
1.191 + template <typename V>
1.192 + class ArcMap : public GR::template ArcMap<V> {
1.193 + typedef typename GR::template ArcMap<V> Parent;
1.194 +
1.195 public:
1.196 - typedef typename Graph::template ArcMap<_Value> Parent;
1.197 - explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
1.198 + explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
1.199 : Parent(*adapter._graph) {}
1.200 - ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
1.201 + ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value)
1.202 : Parent(*adapter._graph, value) {}
1.203
1.204 private:
1.205 @@ -291,13 +294,14 @@
1.206 }
1.207 };
1.208
1.209 - template <typename _Value>
1.210 - class EdgeMap : public Graph::template EdgeMap<_Value> {
1.211 + template <typename V>
1.212 + class EdgeMap : public GR::template EdgeMap<V> {
1.213 + typedef typename GR::template EdgeMap<V> Parent;
1.214 +
1.215 public:
1.216 - typedef typename Graph::template EdgeMap<_Value> Parent;
1.217 - explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
1.218 + explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
1.219 : Parent(*adapter._graph) {}
1.220 - EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
1.221 + EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
1.222 : Parent(*adapter._graph, value) {}
1.223
1.224 private:
1.225 @@ -314,11 +318,11 @@
1.226
1.227 };
1.228
1.229 - template <typename _Digraph>
1.230 - class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
1.231 + template <typename DGR>
1.232 + class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
1.233 + typedef DigraphAdaptorBase<DGR> Parent;
1.234 public:
1.235 - typedef _Digraph Digraph;
1.236 - typedef DigraphAdaptorBase<_Digraph> Parent;
1.237 + typedef DGR Digraph;
1.238 protected:
1.239 ReverseDigraphBase() : Parent() { }
1.240 public:
1.241 @@ -336,7 +340,7 @@
1.242
1.243 Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
1.244
1.245 - typedef FindArcTagIndicator<Digraph> FindArcTag;
1.246 + typedef FindArcTagIndicator<DGR> FindArcTag;
1.247 Arc findArc(const Node& u, const Node& v,
1.248 const Arc& prev = INVALID) const {
1.249 return Parent::findArc(v, u, prev);
1.250 @@ -356,23 +360,23 @@
1.251 /// by adding or removing nodes or arcs, unless the \c GR template
1.252 /// parameter is set to be \c const.
1.253 ///
1.254 - /// \tparam GR The type of the adapted digraph.
1.255 + /// \tparam DGR The type of the adapted digraph.
1.256 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.257 /// It can also be specified to be \c const.
1.258 ///
1.259 /// \note The \c Node and \c Arc types of this adaptor and the adapted
1.260 /// digraph are convertible to each other.
1.261 - template<typename GR>
1.262 + template<typename DGR>
1.263 #ifdef DOXYGEN
1.264 class ReverseDigraph {
1.265 #else
1.266 class ReverseDigraph :
1.267 - public DigraphAdaptorExtender<ReverseDigraphBase<GR> > {
1.268 + public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
1.269 #endif
1.270 + typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
1.271 public:
1.272 /// The type of the adapted digraph.
1.273 - typedef GR Digraph;
1.274 - typedef DigraphAdaptorExtender<ReverseDigraphBase<GR> > Parent;
1.275 + typedef DGR Digraph;
1.276 protected:
1.277 ReverseDigraph() { }
1.278 public:
1.279 @@ -380,8 +384,8 @@
1.280 /// \brief Constructor
1.281 ///
1.282 /// Creates a reverse digraph adaptor for the given digraph.
1.283 - explicit ReverseDigraph(Digraph& digraph) {
1.284 - Parent::setDigraph(digraph);
1.285 + explicit ReverseDigraph(DGR& digraph) {
1.286 + Parent::initialize(digraph);
1.287 }
1.288 };
1.289
1.290 @@ -390,33 +394,31 @@
1.291 /// This function just returns a read-only \ref ReverseDigraph adaptor.
1.292 /// \ingroup graph_adaptors
1.293 /// \relates ReverseDigraph
1.294 - template<typename GR>
1.295 - ReverseDigraph<const GR> reverseDigraph(const GR& digraph) {
1.296 - return ReverseDigraph<const GR>(digraph);
1.297 + template<typename DGR>
1.298 + ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) {
1.299 + return ReverseDigraph<const DGR>(digraph);
1.300 }
1.301
1.302
1.303 - template <typename _Digraph, typename _NodeFilterMap,
1.304 - typename _ArcFilterMap, bool _checked = true>
1.305 - class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
1.306 + template <typename DGR, typename NF, typename AF, bool ch = true>
1.307 + class SubDigraphBase : public DigraphAdaptorBase<DGR> {
1.308 + typedef DigraphAdaptorBase<DGR> Parent;
1.309 public:
1.310 - typedef _Digraph Digraph;
1.311 - typedef _NodeFilterMap NodeFilterMap;
1.312 - typedef _ArcFilterMap ArcFilterMap;
1.313 + typedef DGR Digraph;
1.314 + typedef NF NodeFilterMap;
1.315 + typedef AF ArcFilterMap;
1.316
1.317 typedef SubDigraphBase Adaptor;
1.318 - typedef DigraphAdaptorBase<_Digraph> Parent;
1.319 protected:
1.320 - NodeFilterMap* _node_filter;
1.321 - ArcFilterMap* _arc_filter;
1.322 + NF* _node_filter;
1.323 + AF* _arc_filter;
1.324 SubDigraphBase()
1.325 : Parent(), _node_filter(0), _arc_filter(0) { }
1.326
1.327 - void setNodeFilterMap(NodeFilterMap& node_filter) {
1.328 + void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
1.329 + Parent::initialize(digraph);
1.330 _node_filter = &node_filter;
1.331 - }
1.332 - void setArcFilterMap(ArcFilterMap& arc_filter) {
1.333 - _arc_filter = &arc_filter;
1.334 + _arc_filter = &arc_filter;
1.335 }
1.336
1.337 public:
1.338 @@ -487,7 +489,7 @@
1.339 typedef False NodeNumTag;
1.340 typedef False ArcNumTag;
1.341
1.342 - typedef FindArcTagIndicator<Digraph> FindArcTag;
1.343 + typedef FindArcTagIndicator<DGR> FindArcTag;
1.344 Arc findArc(const Node& source, const Node& target,
1.345 const Arc& prev = INVALID) const {
1.346 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
1.347 @@ -500,18 +502,22 @@
1.348 return arc;
1.349 }
1.350
1.351 - template <typename _Value>
1.352 - class NodeMap : public SubMapExtender<Adaptor,
1.353 - typename Parent::template NodeMap<_Value> > {
1.354 + public:
1.355 +
1.356 + template <typename V>
1.357 + class NodeMap
1.358 + : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
1.359 + LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
1.360 + typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
1.361 + LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
1.362 +
1.363 public:
1.364 - typedef _Value Value;
1.365 - typedef SubMapExtender<Adaptor, typename Parent::
1.366 - template NodeMap<Value> > MapParent;
1.367 -
1.368 - NodeMap(const Adaptor& adaptor)
1.369 - : MapParent(adaptor) {}
1.370 - NodeMap(const Adaptor& adaptor, const Value& value)
1.371 - : MapParent(adaptor, value) {}
1.372 + typedef V Value;
1.373 +
1.374 + NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
1.375 + : Parent(adaptor) {}
1.376 + NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
1.377 + : Parent(adaptor, value) {}
1.378
1.379 private:
1.380 NodeMap& operator=(const NodeMap& cmap) {
1.381 @@ -520,23 +526,25 @@
1.382
1.383 template <typename CMap>
1.384 NodeMap& operator=(const CMap& cmap) {
1.385 - MapParent::operator=(cmap);
1.386 + Parent::operator=(cmap);
1.387 return *this;
1.388 }
1.389 };
1.390
1.391 - template <typename _Value>
1.392 - class ArcMap : public SubMapExtender<Adaptor,
1.393 - typename Parent::template ArcMap<_Value> > {
1.394 + template <typename V>
1.395 + class ArcMap
1.396 + : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
1.397 + LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
1.398 + typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
1.399 + LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
1.400 +
1.401 public:
1.402 - typedef _Value Value;
1.403 - typedef SubMapExtender<Adaptor, typename Parent::
1.404 - template ArcMap<Value> > MapParent;
1.405 -
1.406 - ArcMap(const Adaptor& adaptor)
1.407 - : MapParent(adaptor) {}
1.408 - ArcMap(const Adaptor& adaptor, const Value& value)
1.409 - : MapParent(adaptor, value) {}
1.410 + typedef V Value;
1.411 +
1.412 + ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
1.413 + : Parent(adaptor) {}
1.414 + ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
1.415 + : Parent(adaptor, value) {}
1.416
1.417 private:
1.418 ArcMap& operator=(const ArcMap& cmap) {
1.419 @@ -545,34 +553,33 @@
1.420
1.421 template <typename CMap>
1.422 ArcMap& operator=(const CMap& cmap) {
1.423 - MapParent::operator=(cmap);
1.424 + Parent::operator=(cmap);
1.425 return *this;
1.426 }
1.427 };
1.428
1.429 };
1.430
1.431 - template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
1.432 - class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
1.433 - : public DigraphAdaptorBase<_Digraph> {
1.434 + template <typename DGR, typename NF, typename AF>
1.435 + class SubDigraphBase<DGR, NF, AF, false>
1.436 + : public DigraphAdaptorBase<DGR> {
1.437 + typedef DigraphAdaptorBase<DGR> Parent;
1.438 public:
1.439 - typedef _Digraph Digraph;
1.440 - typedef _NodeFilterMap NodeFilterMap;
1.441 - typedef _ArcFilterMap ArcFilterMap;
1.442 + typedef DGR Digraph;
1.443 + typedef NF NodeFilterMap;
1.444 + typedef AF ArcFilterMap;
1.445
1.446 typedef SubDigraphBase Adaptor;
1.447 - typedef DigraphAdaptorBase<Digraph> Parent;
1.448 protected:
1.449 - NodeFilterMap* _node_filter;
1.450 - ArcFilterMap* _arc_filter;
1.451 + NF* _node_filter;
1.452 + AF* _arc_filter;
1.453 SubDigraphBase()
1.454 : Parent(), _node_filter(0), _arc_filter(0) { }
1.455
1.456 - void setNodeFilterMap(NodeFilterMap& node_filter) {
1.457 + void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
1.458 + Parent::initialize(digraph);
1.459 _node_filter = &node_filter;
1.460 - }
1.461 - void setArcFilterMap(ArcFilterMap& arc_filter) {
1.462 - _arc_filter = &arc_filter;
1.463 + _arc_filter = &arc_filter;
1.464 }
1.465
1.466 public:
1.467 @@ -627,7 +634,7 @@
1.468 typedef False NodeNumTag;
1.469 typedef False ArcNumTag;
1.470
1.471 - typedef FindArcTagIndicator<Digraph> FindArcTag;
1.472 + typedef FindArcTagIndicator<DGR> FindArcTag;
1.473 Arc findArc(const Node& source, const Node& target,
1.474 const Arc& prev = INVALID) const {
1.475 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
1.476 @@ -640,18 +647,20 @@
1.477 return arc;
1.478 }
1.479
1.480 - template <typename _Value>
1.481 - class NodeMap : public SubMapExtender<Adaptor,
1.482 - typename Parent::template NodeMap<_Value> > {
1.483 + template <typename V>
1.484 + class NodeMap
1.485 + : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
1.486 + LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
1.487 + typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
1.488 + LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
1.489 +
1.490 public:
1.491 - typedef _Value Value;
1.492 - typedef SubMapExtender<Adaptor, typename Parent::
1.493 - template NodeMap<Value> > MapParent;
1.494 -
1.495 - NodeMap(const Adaptor& adaptor)
1.496 - : MapParent(adaptor) {}
1.497 - NodeMap(const Adaptor& adaptor, const Value& value)
1.498 - : MapParent(adaptor, value) {}
1.499 + typedef V Value;
1.500 +
1.501 + NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
1.502 + : Parent(adaptor) {}
1.503 + NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
1.504 + : Parent(adaptor, value) {}
1.505
1.506 private:
1.507 NodeMap& operator=(const NodeMap& cmap) {
1.508 @@ -660,23 +669,25 @@
1.509
1.510 template <typename CMap>
1.511 NodeMap& operator=(const CMap& cmap) {
1.512 - MapParent::operator=(cmap);
1.513 + Parent::operator=(cmap);
1.514 return *this;
1.515 }
1.516 };
1.517
1.518 - template <typename _Value>
1.519 - class ArcMap : public SubMapExtender<Adaptor,
1.520 - typename Parent::template ArcMap<_Value> > {
1.521 + template <typename V>
1.522 + class ArcMap
1.523 + : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
1.524 + LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
1.525 + typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
1.526 + LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
1.527 +
1.528 public:
1.529 - typedef _Value Value;
1.530 - typedef SubMapExtender<Adaptor, typename Parent::
1.531 - template ArcMap<Value> > MapParent;
1.532 -
1.533 - ArcMap(const Adaptor& adaptor)
1.534 - : MapParent(adaptor) {}
1.535 - ArcMap(const Adaptor& adaptor, const Value& value)
1.536 - : MapParent(adaptor, value) {}
1.537 + typedef V Value;
1.538 +
1.539 + ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
1.540 + : Parent(adaptor) {}
1.541 + ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
1.542 + : Parent(adaptor, value) {}
1.543
1.544 private:
1.545 ArcMap& operator=(const ArcMap& cmap) {
1.546 @@ -685,7 +696,7 @@
1.547
1.548 template <typename CMap>
1.549 ArcMap& operator=(const CMap& cmap) {
1.550 - MapParent::operator=(cmap);
1.551 + Parent::operator=(cmap);
1.552 return *this;
1.553 }
1.554 };
1.555 @@ -708,17 +719,17 @@
1.556 /// by adding or removing nodes or arcs, unless the \c GR template
1.557 /// parameter is set to be \c const.
1.558 ///
1.559 - /// \tparam GR The type of the adapted digraph.
1.560 + /// \tparam DGR The type of the adapted digraph.
1.561 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.562 /// It can also be specified to be \c const.
1.563 /// \tparam NF The type of the node filter map.
1.564 /// It must be a \c bool (or convertible) node map of the
1.565 /// adapted digraph. The default type is
1.566 - /// \ref concepts::Digraph::NodeMap "GR::NodeMap<bool>".
1.567 + /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>".
1.568 /// \tparam AF The type of the arc filter map.
1.569 /// It must be \c bool (or convertible) arc map of the
1.570 /// adapted digraph. The default type is
1.571 - /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
1.572 + /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
1.573 ///
1.574 /// \note The \c Node and \c Arc types of this adaptor and the adapted
1.575 /// digraph are convertible to each other.
1.576 @@ -726,24 +737,24 @@
1.577 /// \see FilterNodes
1.578 /// \see FilterArcs
1.579 #ifdef DOXYGEN
1.580 - template<typename GR, typename NF, typename AF>
1.581 + template<typename DGR, typename NF, typename AF>
1.582 class SubDigraph {
1.583 #else
1.584 - template<typename GR,
1.585 - typename NF = typename GR::template NodeMap<bool>,
1.586 - typename AF = typename GR::template ArcMap<bool> >
1.587 + template<typename DGR,
1.588 + typename NF = typename DGR::template NodeMap<bool>,
1.589 + typename AF = typename DGR::template ArcMap<bool> >
1.590 class SubDigraph :
1.591 - public DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > {
1.592 + public DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > {
1.593 #endif
1.594 public:
1.595 /// The type of the adapted digraph.
1.596 - typedef GR Digraph;
1.597 + typedef DGR Digraph;
1.598 /// The type of the node filter map.
1.599 typedef NF NodeFilterMap;
1.600 /// The type of the arc filter map.
1.601 typedef AF ArcFilterMap;
1.602
1.603 - typedef DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> >
1.604 + typedef DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> >
1.605 Parent;
1.606
1.607 typedef typename Parent::Node Node;
1.608 @@ -757,11 +768,8 @@
1.609 ///
1.610 /// Creates a subdigraph for the given digraph with the
1.611 /// given node and arc filter maps.
1.612 - SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
1.613 - ArcFilterMap& arc_filter) {
1.614 - setDigraph(digraph);
1.615 - setNodeFilterMap(node_filter);
1.616 - setArcFilterMap(arc_filter);
1.617 + SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) {
1.618 + Parent::initialize(digraph, node_filter, arc_filter);
1.619 }
1.620
1.621 /// \brief Sets the status of the given node
1.622 @@ -823,62 +831,60 @@
1.623 /// This function just returns a read-only \ref SubDigraph adaptor.
1.624 /// \ingroup graph_adaptors
1.625 /// \relates SubDigraph
1.626 - template<typename GR, typename NF, typename AF>
1.627 - SubDigraph<const GR, NF, AF>
1.628 - subDigraph(const GR& digraph,
1.629 - NF& node_filter_map, AF& arc_filter_map) {
1.630 - return SubDigraph<const GR, NF, AF>
1.631 - (digraph, node_filter_map, arc_filter_map);
1.632 + template<typename DGR, typename NF, typename AF>
1.633 + SubDigraph<const DGR, NF, AF>
1.634 + subDigraph(const DGR& digraph,
1.635 + NF& node_filter, AF& arc_filter) {
1.636 + return SubDigraph<const DGR, NF, AF>
1.637 + (digraph, node_filter, arc_filter);
1.638 }
1.639
1.640 - template<typename GR, typename NF, typename AF>
1.641 - SubDigraph<const GR, const NF, AF>
1.642 - subDigraph(const GR& digraph,
1.643 - const NF& node_filter_map, AF& arc_filter_map) {
1.644 - return SubDigraph<const GR, const NF, AF>
1.645 - (digraph, node_filter_map, arc_filter_map);
1.646 + template<typename DGR, typename NF, typename AF>
1.647 + SubDigraph<const DGR, const NF, AF>
1.648 + subDigraph(const DGR& digraph,
1.649 + const NF& node_filter, AF& arc_filter) {
1.650 + return SubDigraph<const DGR, const NF, AF>
1.651 + (digraph, node_filter, arc_filter);
1.652 }
1.653
1.654 - template<typename GR, typename NF, typename AF>
1.655 - SubDigraph<const GR, NF, const AF>
1.656 - subDigraph(const GR& digraph,
1.657 - NF& node_filter_map, const AF& arc_filter_map) {
1.658 - return SubDigraph<const GR, NF, const AF>
1.659 - (digraph, node_filter_map, arc_filter_map);
1.660 + template<typename DGR, typename NF, typename AF>
1.661 + SubDigraph<const DGR, NF, const AF>
1.662 + subDigraph(const DGR& digraph,
1.663 + NF& node_filter, const AF& arc_filter) {
1.664 + return SubDigraph<const DGR, NF, const AF>
1.665 + (digraph, node_filter, arc_filter);
1.666 }
1.667
1.668 - template<typename GR, typename NF, typename AF>
1.669 - SubDigraph<const GR, const NF, const AF>
1.670 - subDigraph(const GR& digraph,
1.671 - const NF& node_filter_map, const AF& arc_filter_map) {
1.672 - return SubDigraph<const GR, const NF, const AF>
1.673 - (digraph, node_filter_map, arc_filter_map);
1.674 + template<typename DGR, typename NF, typename AF>
1.675 + SubDigraph<const DGR, const NF, const AF>
1.676 + subDigraph(const DGR& digraph,
1.677 + const NF& node_filter, const AF& arc_filter) {
1.678 + return SubDigraph<const DGR, const NF, const AF>
1.679 + (digraph, node_filter, arc_filter);
1.680 }
1.681
1.682
1.683 - template <typename _Graph, typename _NodeFilterMap,
1.684 - typename _EdgeFilterMap, bool _checked = true>
1.685 - class SubGraphBase : public GraphAdaptorBase<_Graph> {
1.686 + template <typename GR, typename NF, typename EF, bool ch = true>
1.687 + class SubGraphBase : public GraphAdaptorBase<GR> {
1.688 + typedef GraphAdaptorBase<GR> Parent;
1.689 public:
1.690 - typedef _Graph Graph;
1.691 - typedef _NodeFilterMap NodeFilterMap;
1.692 - typedef _EdgeFilterMap EdgeFilterMap;
1.693 + typedef GR Graph;
1.694 + typedef NF NodeFilterMap;
1.695 + typedef EF EdgeFilterMap;
1.696
1.697 typedef SubGraphBase Adaptor;
1.698 - typedef GraphAdaptorBase<_Graph> Parent;
1.699 protected:
1.700
1.701 - NodeFilterMap* _node_filter_map;
1.702 - EdgeFilterMap* _edge_filter_map;
1.703 + NF* _node_filter;
1.704 + EF* _edge_filter;
1.705
1.706 SubGraphBase()
1.707 - : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
1.708 -
1.709 - void setNodeFilterMap(NodeFilterMap& node_filter_map) {
1.710 - _node_filter_map=&node_filter_map;
1.711 - }
1.712 - void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
1.713 - _edge_filter_map=&edge_filter_map;
1.714 + : Parent(), _node_filter(0), _edge_filter(0) { }
1.715 +
1.716 + void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
1.717 + Parent::initialize(graph);
1.718 + _node_filter = &node_filter;
1.719 + _edge_filter = &edge_filter;
1.720 }
1.721
1.722 public:
1.723 @@ -889,95 +895,95 @@
1.724
1.725 void first(Node& i) const {
1.726 Parent::first(i);
1.727 - while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1.728 + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
1.729 }
1.730
1.731 void first(Arc& i) const {
1.732 Parent::first(i);
1.733 - while (i!=INVALID && (!(*_edge_filter_map)[i]
1.734 - || !(*_node_filter_map)[Parent::source(i)]
1.735 - || !(*_node_filter_map)[Parent::target(i)]))
1.736 + while (i!=INVALID && (!(*_edge_filter)[i]
1.737 + || !(*_node_filter)[Parent::source(i)]
1.738 + || !(*_node_filter)[Parent::target(i)]))
1.739 Parent::next(i);
1.740 }
1.741
1.742 void first(Edge& i) const {
1.743 Parent::first(i);
1.744 - while (i!=INVALID && (!(*_edge_filter_map)[i]
1.745 - || !(*_node_filter_map)[Parent::u(i)]
1.746 - || !(*_node_filter_map)[Parent::v(i)]))
1.747 + while (i!=INVALID && (!(*_edge_filter)[i]
1.748 + || !(*_node_filter)[Parent::u(i)]
1.749 + || !(*_node_filter)[Parent::v(i)]))
1.750 Parent::next(i);
1.751 }
1.752
1.753 void firstIn(Arc& i, const Node& n) const {
1.754 Parent::firstIn(i, n);
1.755 - while (i!=INVALID && (!(*_edge_filter_map)[i]
1.756 - || !(*_node_filter_map)[Parent::source(i)]))
1.757 + while (i!=INVALID && (!(*_edge_filter)[i]
1.758 + || !(*_node_filter)[Parent::source(i)]))
1.759 Parent::nextIn(i);
1.760 }
1.761
1.762 void firstOut(Arc& i, const Node& n) const {
1.763 Parent::firstOut(i, n);
1.764 - while (i!=INVALID && (!(*_edge_filter_map)[i]
1.765 - || !(*_node_filter_map)[Parent::target(i)]))
1.766 + while (i!=INVALID && (!(*_edge_filter)[i]
1.767 + || !(*_node_filter)[Parent::target(i)]))
1.768 Parent::nextOut(i);
1.769 }
1.770
1.771 void firstInc(Edge& i, bool& d, const Node& n) const {
1.772 Parent::firstInc(i, d, n);
1.773 - while (i!=INVALID && (!(*_edge_filter_map)[i]
1.774 - || !(*_node_filter_map)[Parent::u(i)]
1.775 - || !(*_node_filter_map)[Parent::v(i)]))
1.776 + while (i!=INVALID && (!(*_edge_filter)[i]
1.777 + || !(*_node_filter)[Parent::u(i)]
1.778 + || !(*_node_filter)[Parent::v(i)]))
1.779 Parent::nextInc(i, d);
1.780 }
1.781
1.782 void next(Node& i) const {
1.783 Parent::next(i);
1.784 - while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1.785 + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
1.786 }
1.787
1.788 void next(Arc& i) const {
1.789 Parent::next(i);
1.790 - while (i!=INVALID && (!(*_edge_filter_map)[i]
1.791 - || !(*_node_filter_map)[Parent::source(i)]
1.792 - || !(*_node_filter_map)[Parent::target(i)]))
1.793 + while (i!=INVALID && (!(*_edge_filter)[i]
1.794 + || !(*_node_filter)[Parent::source(i)]
1.795 + || !(*_node_filter)[Parent::target(i)]))
1.796 Parent::next(i);
1.797 }
1.798
1.799 void next(Edge& i) const {
1.800 Parent::next(i);
1.801 - while (i!=INVALID && (!(*_edge_filter_map)[i]
1.802 - || !(*_node_filter_map)[Parent::u(i)]
1.803 - || !(*_node_filter_map)[Parent::v(i)]))
1.804 + while (i!=INVALID && (!(*_edge_filter)[i]
1.805 + || !(*_node_filter)[Parent::u(i)]
1.806 + || !(*_node_filter)[Parent::v(i)]))
1.807 Parent::next(i);
1.808 }
1.809
1.810 void nextIn(Arc& i) const {
1.811 Parent::nextIn(i);
1.812 - while (i!=INVALID && (!(*_edge_filter_map)[i]
1.813 - || !(*_node_filter_map)[Parent::source(i)]))
1.814 + while (i!=INVALID && (!(*_edge_filter)[i]
1.815 + || !(*_node_filter)[Parent::source(i)]))
1.816 Parent::nextIn(i);
1.817 }
1.818
1.819 void nextOut(Arc& i) const {
1.820 Parent::nextOut(i);
1.821 - while (i!=INVALID && (!(*_edge_filter_map)[i]
1.822 - || !(*_node_filter_map)[Parent::target(i)]))
1.823 + while (i!=INVALID && (!(*_edge_filter)[i]
1.824 + || !(*_node_filter)[Parent::target(i)]))
1.825 Parent::nextOut(i);
1.826 }
1.827
1.828 void nextInc(Edge& i, bool& d) const {
1.829 Parent::nextInc(i, d);
1.830 - while (i!=INVALID && (!(*_edge_filter_map)[i]
1.831 - || !(*_node_filter_map)[Parent::u(i)]
1.832 - || !(*_node_filter_map)[Parent::v(i)]))
1.833 + while (i!=INVALID && (!(*_edge_filter)[i]
1.834 + || !(*_node_filter)[Parent::u(i)]
1.835 + || !(*_node_filter)[Parent::v(i)]))
1.836 Parent::nextInc(i, d);
1.837 }
1.838
1.839 - void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
1.840 - void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
1.841 -
1.842 - bool status(const Node& n) const { return (*_node_filter_map)[n]; }
1.843 - bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
1.844 + void status(const Node& n, bool v) const { _node_filter->set(n, v); }
1.845 + void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
1.846 +
1.847 + bool status(const Node& n) const { return (*_node_filter)[n]; }
1.848 + bool status(const Edge& e) const { return (*_edge_filter)[e]; }
1.849
1.850 typedef False NodeNumTag;
1.851 typedef False ArcNumTag;
1.852 @@ -986,11 +992,11 @@
1.853 typedef FindArcTagIndicator<Graph> FindArcTag;
1.854 Arc findArc(const Node& u, const Node& v,
1.855 const Arc& prev = INVALID) const {
1.856 - if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
1.857 + if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
1.858 return INVALID;
1.859 }
1.860 Arc arc = Parent::findArc(u, v, prev);
1.861 - while (arc != INVALID && !(*_edge_filter_map)[arc]) {
1.862 + while (arc != INVALID && !(*_edge_filter)[arc]) {
1.863 arc = Parent::findArc(u, v, arc);
1.864 }
1.865 return arc;
1.866 @@ -999,28 +1005,30 @@
1.867 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.868 Edge findEdge(const Node& u, const Node& v,
1.869 const Edge& prev = INVALID) const {
1.870 - if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
1.871 + if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
1.872 return INVALID;
1.873 }
1.874 Edge edge = Parent::findEdge(u, v, prev);
1.875 - while (edge != INVALID && !(*_edge_filter_map)[edge]) {
1.876 + while (edge != INVALID && !(*_edge_filter)[edge]) {
1.877 edge = Parent::findEdge(u, v, edge);
1.878 }
1.879 return edge;
1.880 }
1.881
1.882 - template <typename _Value>
1.883 - class NodeMap : public SubMapExtender<Adaptor,
1.884 - typename Parent::template NodeMap<_Value> > {
1.885 + template <typename V>
1.886 + class NodeMap
1.887 + : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.888 + LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
1.889 + typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.890 + LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
1.891 +
1.892 public:
1.893 - typedef _Value Value;
1.894 - typedef SubMapExtender<Adaptor, typename Parent::
1.895 - template NodeMap<Value> > MapParent;
1.896 -
1.897 - NodeMap(const Adaptor& adaptor)
1.898 - : MapParent(adaptor) {}
1.899 - NodeMap(const Adaptor& adaptor, const Value& value)
1.900 - : MapParent(adaptor, value) {}
1.901 + typedef V Value;
1.902 +
1.903 + NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
1.904 + : Parent(adaptor) {}
1.905 + NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
1.906 + : Parent(adaptor, value) {}
1.907
1.908 private:
1.909 NodeMap& operator=(const NodeMap& cmap) {
1.910 @@ -1029,23 +1037,25 @@
1.911
1.912 template <typename CMap>
1.913 NodeMap& operator=(const CMap& cmap) {
1.914 - MapParent::operator=(cmap);
1.915 + Parent::operator=(cmap);
1.916 return *this;
1.917 }
1.918 };
1.919
1.920 - template <typename _Value>
1.921 - class ArcMap : public SubMapExtender<Adaptor,
1.922 - typename Parent::template ArcMap<_Value> > {
1.923 + template <typename V>
1.924 + class ArcMap
1.925 + : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.926 + LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
1.927 + typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.928 + LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
1.929 +
1.930 public:
1.931 - typedef _Value Value;
1.932 - typedef SubMapExtender<Adaptor, typename Parent::
1.933 - template ArcMap<Value> > MapParent;
1.934 -
1.935 - ArcMap(const Adaptor& adaptor)
1.936 - : MapParent(adaptor) {}
1.937 - ArcMap(const Adaptor& adaptor, const Value& value)
1.938 - : MapParent(adaptor, value) {}
1.939 + typedef V Value;
1.940 +
1.941 + ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
1.942 + : Parent(adaptor) {}
1.943 + ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
1.944 + : Parent(adaptor, value) {}
1.945
1.946 private:
1.947 ArcMap& operator=(const ArcMap& cmap) {
1.948 @@ -1054,24 +1064,26 @@
1.949
1.950 template <typename CMap>
1.951 ArcMap& operator=(const CMap& cmap) {
1.952 - MapParent::operator=(cmap);
1.953 + Parent::operator=(cmap);
1.954 return *this;
1.955 }
1.956 };
1.957
1.958 - template <typename _Value>
1.959 - class EdgeMap : public SubMapExtender<Adaptor,
1.960 - typename Parent::template EdgeMap<_Value> > {
1.961 + template <typename V>
1.962 + class EdgeMap
1.963 + : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.964 + LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
1.965 + typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.966 + LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
1.967 +
1.968 public:
1.969 - typedef _Value Value;
1.970 - typedef SubMapExtender<Adaptor, typename Parent::
1.971 - template EdgeMap<Value> > MapParent;
1.972 -
1.973 - EdgeMap(const Adaptor& adaptor)
1.974 - : MapParent(adaptor) {}
1.975 -
1.976 - EdgeMap(const Adaptor& adaptor, const Value& value)
1.977 - : MapParent(adaptor, value) {}
1.978 + typedef V Value;
1.979 +
1.980 + EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
1.981 + : Parent(adaptor) {}
1.982 +
1.983 + EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
1.984 + : Parent(adaptor, value) {}
1.985
1.986 private:
1.987 EdgeMap& operator=(const EdgeMap& cmap) {
1.988 @@ -1080,34 +1092,33 @@
1.989
1.990 template <typename CMap>
1.991 EdgeMap& operator=(const CMap& cmap) {
1.992 - MapParent::operator=(cmap);
1.993 + Parent::operator=(cmap);
1.994 return *this;
1.995 }
1.996 };
1.997
1.998 };
1.999
1.1000 - template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
1.1001 - class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
1.1002 - : public GraphAdaptorBase<_Graph> {
1.1003 + template <typename GR, typename NF, typename EF>
1.1004 + class SubGraphBase<GR, NF, EF, false>
1.1005 + : public GraphAdaptorBase<GR> {
1.1006 + typedef GraphAdaptorBase<GR> Parent;
1.1007 public:
1.1008 - typedef _Graph Graph;
1.1009 - typedef _NodeFilterMap NodeFilterMap;
1.1010 - typedef _EdgeFilterMap EdgeFilterMap;
1.1011 + typedef GR Graph;
1.1012 + typedef NF NodeFilterMap;
1.1013 + typedef EF EdgeFilterMap;
1.1014
1.1015 typedef SubGraphBase Adaptor;
1.1016 - typedef GraphAdaptorBase<_Graph> Parent;
1.1017 protected:
1.1018 - NodeFilterMap* _node_filter_map;
1.1019 - EdgeFilterMap* _edge_filter_map;
1.1020 - SubGraphBase() : Parent(),
1.1021 - _node_filter_map(0), _edge_filter_map(0) { }
1.1022 -
1.1023 - void setNodeFilterMap(NodeFilterMap& node_filter_map) {
1.1024 - _node_filter_map=&node_filter_map;
1.1025 - }
1.1026 - void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
1.1027 - _edge_filter_map=&edge_filter_map;
1.1028 + NF* _node_filter;
1.1029 + EF* _edge_filter;
1.1030 + SubGraphBase()
1.1031 + : Parent(), _node_filter(0), _edge_filter(0) { }
1.1032 +
1.1033 + void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
1.1034 + Parent::initialize(graph);
1.1035 + _node_filter = &node_filter;
1.1036 + _edge_filter = &edge_filter;
1.1037 }
1.1038
1.1039 public:
1.1040 @@ -1118,65 +1129,65 @@
1.1041
1.1042 void first(Node& i) const {
1.1043 Parent::first(i);
1.1044 - while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1.1045 + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
1.1046 }
1.1047
1.1048 void first(Arc& i) const {
1.1049 Parent::first(i);
1.1050 - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1.1051 + while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
1.1052 }
1.1053
1.1054 void first(Edge& i) const {
1.1055 Parent::first(i);
1.1056 - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1.1057 + while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
1.1058 }
1.1059
1.1060 void firstIn(Arc& i, const Node& n) const {
1.1061 Parent::firstIn(i, n);
1.1062 - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1.1063 + while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
1.1064 }
1.1065
1.1066 void firstOut(Arc& i, const Node& n) const {
1.1067 Parent::firstOut(i, n);
1.1068 - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1.1069 + while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
1.1070 }
1.1071
1.1072 void firstInc(Edge& i, bool& d, const Node& n) const {
1.1073 Parent::firstInc(i, d, n);
1.1074 - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1.1075 + while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
1.1076 }
1.1077
1.1078 void next(Node& i) const {
1.1079 Parent::next(i);
1.1080 - while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1.1081 + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
1.1082 }
1.1083 void next(Arc& i) const {
1.1084 Parent::next(i);
1.1085 - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1.1086 + while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
1.1087 }
1.1088 void next(Edge& i) const {
1.1089 Parent::next(i);
1.1090 - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1.1091 + while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
1.1092 }
1.1093 void nextIn(Arc& i) const {
1.1094 Parent::nextIn(i);
1.1095 - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1.1096 + while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
1.1097 }
1.1098
1.1099 void nextOut(Arc& i) const {
1.1100 Parent::nextOut(i);
1.1101 - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1.1102 + while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
1.1103 }
1.1104 void nextInc(Edge& i, bool& d) const {
1.1105 Parent::nextInc(i, d);
1.1106 - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1.1107 + while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
1.1108 }
1.1109
1.1110 - void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
1.1111 - void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
1.1112 -
1.1113 - bool status(const Node& n) const { return (*_node_filter_map)[n]; }
1.1114 - bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
1.1115 + void status(const Node& n, bool v) const { _node_filter->set(n, v); }
1.1116 + void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
1.1117 +
1.1118 + bool status(const Node& n) const { return (*_node_filter)[n]; }
1.1119 + bool status(const Edge& e) const { return (*_edge_filter)[e]; }
1.1120
1.1121 typedef False NodeNumTag;
1.1122 typedef False ArcNumTag;
1.1123 @@ -1186,7 +1197,7 @@
1.1124 Arc findArc(const Node& u, const Node& v,
1.1125 const Arc& prev = INVALID) const {
1.1126 Arc arc = Parent::findArc(u, v, prev);
1.1127 - while (arc != INVALID && !(*_edge_filter_map)[arc]) {
1.1128 + while (arc != INVALID && !(*_edge_filter)[arc]) {
1.1129 arc = Parent::findArc(u, v, arc);
1.1130 }
1.1131 return arc;
1.1132 @@ -1196,24 +1207,26 @@
1.1133 Edge findEdge(const Node& u, const Node& v,
1.1134 const Edge& prev = INVALID) const {
1.1135 Edge edge = Parent::findEdge(u, v, prev);
1.1136 - while (edge != INVALID && !(*_edge_filter_map)[edge]) {
1.1137 + while (edge != INVALID && !(*_edge_filter)[edge]) {
1.1138 edge = Parent::findEdge(u, v, edge);
1.1139 }
1.1140 return edge;
1.1141 }
1.1142
1.1143 - template <typename _Value>
1.1144 - class NodeMap : public SubMapExtender<Adaptor,
1.1145 - typename Parent::template NodeMap<_Value> > {
1.1146 + template <typename V>
1.1147 + class NodeMap
1.1148 + : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.1149 + LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
1.1150 + typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.1151 + LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
1.1152 +
1.1153 public:
1.1154 - typedef _Value Value;
1.1155 - typedef SubMapExtender<Adaptor, typename Parent::
1.1156 - template NodeMap<Value> > MapParent;
1.1157 -
1.1158 - NodeMap(const Adaptor& adaptor)
1.1159 - : MapParent(adaptor) {}
1.1160 - NodeMap(const Adaptor& adaptor, const Value& value)
1.1161 - : MapParent(adaptor, value) {}
1.1162 + typedef V Value;
1.1163 +
1.1164 + NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
1.1165 + : Parent(adaptor) {}
1.1166 + NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
1.1167 + : Parent(adaptor, value) {}
1.1168
1.1169 private:
1.1170 NodeMap& operator=(const NodeMap& cmap) {
1.1171 @@ -1222,23 +1235,25 @@
1.1172
1.1173 template <typename CMap>
1.1174 NodeMap& operator=(const CMap& cmap) {
1.1175 - MapParent::operator=(cmap);
1.1176 + Parent::operator=(cmap);
1.1177 return *this;
1.1178 }
1.1179 };
1.1180
1.1181 - template <typename _Value>
1.1182 - class ArcMap : public SubMapExtender<Adaptor,
1.1183 - typename Parent::template ArcMap<_Value> > {
1.1184 + template <typename V>
1.1185 + class ArcMap
1.1186 + : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.1187 + LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
1.1188 + typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.1189 + LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
1.1190 +
1.1191 public:
1.1192 - typedef _Value Value;
1.1193 - typedef SubMapExtender<Adaptor, typename Parent::
1.1194 - template ArcMap<Value> > MapParent;
1.1195 -
1.1196 - ArcMap(const Adaptor& adaptor)
1.1197 - : MapParent(adaptor) {}
1.1198 - ArcMap(const Adaptor& adaptor, const Value& value)
1.1199 - : MapParent(adaptor, value) {}
1.1200 + typedef V Value;
1.1201 +
1.1202 + ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
1.1203 + : Parent(adaptor) {}
1.1204 + ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
1.1205 + : Parent(adaptor, value) {}
1.1206
1.1207 private:
1.1208 ArcMap& operator=(const ArcMap& cmap) {
1.1209 @@ -1247,24 +1262,26 @@
1.1210
1.1211 template <typename CMap>
1.1212 ArcMap& operator=(const CMap& cmap) {
1.1213 - MapParent::operator=(cmap);
1.1214 + Parent::operator=(cmap);
1.1215 return *this;
1.1216 }
1.1217 };
1.1218
1.1219 - template <typename _Value>
1.1220 - class EdgeMap : public SubMapExtender<Adaptor,
1.1221 - typename Parent::template EdgeMap<_Value> > {
1.1222 + template <typename V>
1.1223 + class EdgeMap
1.1224 + : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.1225 + LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
1.1226 + typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.1227 + LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
1.1228 +
1.1229 public:
1.1230 - typedef _Value Value;
1.1231 - typedef SubMapExtender<Adaptor, typename Parent::
1.1232 - template EdgeMap<Value> > MapParent;
1.1233 -
1.1234 - EdgeMap(const Adaptor& adaptor)
1.1235 - : MapParent(adaptor) {}
1.1236 -
1.1237 - EdgeMap(const Adaptor& adaptor, const _Value& value)
1.1238 - : MapParent(adaptor, value) {}
1.1239 + typedef V Value;
1.1240 +
1.1241 + EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
1.1242 + : Parent(adaptor) {}
1.1243 +
1.1244 + EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
1.1245 + : Parent(adaptor, value) {}
1.1246
1.1247 private:
1.1248 EdgeMap& operator=(const EdgeMap& cmap) {
1.1249 @@ -1273,7 +1290,7 @@
1.1250
1.1251 template <typename CMap>
1.1252 EdgeMap& operator=(const CMap& cmap) {
1.1253 - MapParent::operator=(cmap);
1.1254 + Parent::operator=(cmap);
1.1255 return *this;
1.1256 }
1.1257 };
1.1258 @@ -1332,7 +1349,7 @@
1.1259 /// The type of the edge filter map.
1.1260 typedef EF EdgeFilterMap;
1.1261
1.1262 - typedef GraphAdaptorExtender< SubGraphBase<GR, NF, EF, true> >
1.1263 + typedef GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> >
1.1264 Parent;
1.1265
1.1266 typedef typename Parent::Node Node;
1.1267 @@ -1346,11 +1363,8 @@
1.1268 ///
1.1269 /// Creates a subgraph for the given graph with the given node
1.1270 /// and edge filter maps.
1.1271 - SubGraph(Graph& graph, NodeFilterMap& node_filter_map,
1.1272 - EdgeFilterMap& edge_filter_map) {
1.1273 - setGraph(graph);
1.1274 - setNodeFilterMap(node_filter_map);
1.1275 - setEdgeFilterMap(edge_filter_map);
1.1276 + SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {
1.1277 + initialize(graph, node_filter, edge_filter);
1.1278 }
1.1279
1.1280 /// \brief Sets the status of the given node
1.1281 @@ -1414,34 +1428,30 @@
1.1282 /// \relates SubGraph
1.1283 template<typename GR, typename NF, typename EF>
1.1284 SubGraph<const GR, NF, EF>
1.1285 - subGraph(const GR& graph,
1.1286 - NF& node_filter_map, EF& edge_filter_map) {
1.1287 + subGraph(const GR& graph, NF& node_filter, EF& edge_filter) {
1.1288 return SubGraph<const GR, NF, EF>
1.1289 - (graph, node_filter_map, edge_filter_map);
1.1290 + (graph, node_filter, edge_filter);
1.1291 }
1.1292
1.1293 template<typename GR, typename NF, typename EF>
1.1294 SubGraph<const GR, const NF, EF>
1.1295 - subGraph(const GR& graph,
1.1296 - const NF& node_filter_map, EF& edge_filter_map) {
1.1297 + subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) {
1.1298 return SubGraph<const GR, const NF, EF>
1.1299 - (graph, node_filter_map, edge_filter_map);
1.1300 + (graph, node_filter, edge_filter);
1.1301 }
1.1302
1.1303 template<typename GR, typename NF, typename EF>
1.1304 SubGraph<const GR, NF, const EF>
1.1305 - subGraph(const GR& graph,
1.1306 - NF& node_filter_map, const EF& edge_filter_map) {
1.1307 + subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) {
1.1308 return SubGraph<const GR, NF, const EF>
1.1309 - (graph, node_filter_map, edge_filter_map);
1.1310 + (graph, node_filter, edge_filter);
1.1311 }
1.1312
1.1313 template<typename GR, typename NF, typename EF>
1.1314 SubGraph<const GR, const NF, const EF>
1.1315 - subGraph(const GR& graph,
1.1316 - const NF& node_filter_map, const EF& edge_filter_map) {
1.1317 + subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) {
1.1318 return SubGraph<const GR, const NF, const EF>
1.1319 - (graph, node_filter_map, edge_filter_map);
1.1320 + (graph, node_filter, edge_filter);
1.1321 }
1.1322
1.1323
1.1324 @@ -1481,25 +1491,24 @@
1.1325 typename Enable = void>
1.1326 class FilterNodes :
1.1327 public DigraphAdaptorExtender<
1.1328 - SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > {
1.1329 + SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
1.1330 + true> > {
1.1331 #endif
1.1332 + typedef DigraphAdaptorExtender<
1.1333 + SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
1.1334 + true> > Parent;
1.1335 +
1.1336 public:
1.1337
1.1338 typedef GR Digraph;
1.1339 typedef NF NodeFilterMap;
1.1340
1.1341 - typedef DigraphAdaptorExtender<
1.1342 - SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> >
1.1343 - Parent;
1.1344 -
1.1345 typedef typename Parent::Node Node;
1.1346
1.1347 protected:
1.1348 - ConstMap<typename Digraph::Arc, bool> const_true_map;
1.1349 -
1.1350 - FilterNodes() : const_true_map(true) {
1.1351 - Parent::setArcFilterMap(const_true_map);
1.1352 - }
1.1353 + ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;
1.1354 +
1.1355 + FilterNodes() : const_true_map() {}
1.1356
1.1357 public:
1.1358
1.1359 @@ -1507,12 +1516,10 @@
1.1360 ///
1.1361 /// Creates a subgraph for the given digraph or graph with the
1.1362 /// given node filter map.
1.1363 - FilterNodes(GR& graph, NodeFilterMap& node_filter) :
1.1364 - Parent(), const_true_map(true)
1.1365 + FilterNodes(GR& graph, NF& node_filter)
1.1366 + : Parent(), const_true_map()
1.1367 {
1.1368 - Parent::setDigraph(graph);
1.1369 - Parent::setNodeFilterMap(node_filter);
1.1370 - Parent::setArcFilterMap(const_true_map);
1.1371 + Parent::initialize(graph, node_filter, const_true_map);
1.1372 }
1.1373
1.1374 /// \brief Sets the status of the given node
1.1375 @@ -1547,30 +1554,30 @@
1.1376 class FilterNodes<GR, NF,
1.1377 typename enable_if<UndirectedTagIndicator<GR> >::type> :
1.1378 public GraphAdaptorExtender<
1.1379 - SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > {
1.1380 + SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
1.1381 + true> > {
1.1382 +
1.1383 + typedef GraphAdaptorExtender<
1.1384 + SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
1.1385 + true> > Parent;
1.1386
1.1387 public:
1.1388 +
1.1389 typedef GR Graph;
1.1390 typedef NF NodeFilterMap;
1.1391 - typedef GraphAdaptorExtender<
1.1392 - SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> >
1.1393 - Parent;
1.1394
1.1395 typedef typename Parent::Node Node;
1.1396 +
1.1397 protected:
1.1398 - ConstMap<typename Graph::Edge, bool> const_true_map;
1.1399 -
1.1400 - FilterNodes() : const_true_map(true) {
1.1401 - Parent::setEdgeFilterMap(const_true_map);
1.1402 - }
1.1403 + ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
1.1404 +
1.1405 + FilterNodes() : const_true_map() {}
1.1406
1.1407 public:
1.1408
1.1409 - FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
1.1410 - Parent(), const_true_map(true) {
1.1411 - Parent::setGraph(_graph);
1.1412 - Parent::setNodeFilterMap(node_filter_map);
1.1413 - Parent::setEdgeFilterMap(const_true_map);
1.1414 + FilterNodes(GR& graph, NodeFilterMap& node_filter) :
1.1415 + Parent(), const_true_map() {
1.1416 + Parent::initialize(graph, node_filter, const_true_map);
1.1417 }
1.1418
1.1419 void status(const Node& n, bool v) const { Parent::status(n, v); }
1.1420 @@ -1588,14 +1595,14 @@
1.1421 /// \relates FilterNodes
1.1422 template<typename GR, typename NF>
1.1423 FilterNodes<const GR, NF>
1.1424 - filterNodes(const GR& graph, NF& node_filter_map) {
1.1425 - return FilterNodes<const GR, NF>(graph, node_filter_map);
1.1426 + filterNodes(const GR& graph, NF& node_filter) {
1.1427 + return FilterNodes<const GR, NF>(graph, node_filter);
1.1428 }
1.1429
1.1430 template<typename GR, typename NF>
1.1431 FilterNodes<const GR, const NF>
1.1432 - filterNodes(const GR& graph, const NF& node_filter_map) {
1.1433 - return FilterNodes<const GR, const NF>(graph, node_filter_map);
1.1434 + filterNodes(const GR& graph, const NF& node_filter) {
1.1435 + return FilterNodes<const GR, const NF>(graph, node_filter);
1.1436 }
1.1437
1.1438 /// \ingroup graph_adaptors
1.1439 @@ -1612,45 +1619,45 @@
1.1440 /// by adding or removing nodes or arcs, unless the \c GR template
1.1441 /// parameter is set to be \c const.
1.1442 ///
1.1443 - /// \tparam GR The type of the adapted digraph.
1.1444 + /// \tparam DGR The type of the adapted digraph.
1.1445 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.1446 /// It can also be specified to be \c const.
1.1447 /// \tparam AF The type of the arc filter map.
1.1448 /// It must be a \c bool (or convertible) arc map of the
1.1449 /// adapted digraph. The default type is
1.1450 - /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
1.1451 + /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
1.1452 ///
1.1453 /// \note The \c Node and \c Arc types of this adaptor and the adapted
1.1454 /// digraph are convertible to each other.
1.1455 #ifdef DOXYGEN
1.1456 - template<typename GR,
1.1457 + template<typename DGR,
1.1458 typename AF>
1.1459 class FilterArcs {
1.1460 #else
1.1461 - template<typename GR,
1.1462 - typename AF = typename GR::template ArcMap<bool> >
1.1463 + template<typename DGR,
1.1464 + typename AF = typename DGR::template ArcMap<bool> >
1.1465 class FilterArcs :
1.1466 public DigraphAdaptorExtender<
1.1467 - SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > {
1.1468 + SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
1.1469 + AF, false> > {
1.1470 #endif
1.1471 + typedef DigraphAdaptorExtender<
1.1472 + SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
1.1473 + AF, false> > Parent;
1.1474 +
1.1475 public:
1.1476 +
1.1477 /// The type of the adapted digraph.
1.1478 - typedef GR Digraph;
1.1479 + typedef DGR Digraph;
1.1480 /// The type of the arc filter map.
1.1481 typedef AF ArcFilterMap;
1.1482
1.1483 - typedef DigraphAdaptorExtender<
1.1484 - SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> >
1.1485 - Parent;
1.1486 -
1.1487 typedef typename Parent::Arc Arc;
1.1488
1.1489 protected:
1.1490 - ConstMap<typename Digraph::Node, bool> const_true_map;
1.1491 -
1.1492 - FilterArcs() : const_true_map(true) {
1.1493 - Parent::setNodeFilterMap(const_true_map);
1.1494 - }
1.1495 + ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;
1.1496 +
1.1497 + FilterArcs() : const_true_map() {}
1.1498
1.1499 public:
1.1500
1.1501 @@ -1658,11 +1665,9 @@
1.1502 ///
1.1503 /// Creates a subdigraph for the given digraph with the given arc
1.1504 /// filter map.
1.1505 - FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
1.1506 - : Parent(), const_true_map(true) {
1.1507 - Parent::setDigraph(digraph);
1.1508 - Parent::setNodeFilterMap(const_true_map);
1.1509 - Parent::setArcFilterMap(arc_filter);
1.1510 + FilterArcs(DGR& digraph, ArcFilterMap& arc_filter)
1.1511 + : Parent(), const_true_map() {
1.1512 + Parent::initialize(digraph, const_true_map, arc_filter);
1.1513 }
1.1514
1.1515 /// \brief Sets the status of the given arc
1.1516 @@ -1698,16 +1703,16 @@
1.1517 /// This function just returns a read-only \ref FilterArcs adaptor.
1.1518 /// \ingroup graph_adaptors
1.1519 /// \relates FilterArcs
1.1520 - template<typename GR, typename AF>
1.1521 - FilterArcs<const GR, AF>
1.1522 - filterArcs(const GR& digraph, AF& arc_filter_map) {
1.1523 - return FilterArcs<const GR, AF>(digraph, arc_filter_map);
1.1524 + template<typename DGR, typename AF>
1.1525 + FilterArcs<const DGR, AF>
1.1526 + filterArcs(const DGR& digraph, AF& arc_filter) {
1.1527 + return FilterArcs<const DGR, AF>(digraph, arc_filter);
1.1528 }
1.1529
1.1530 - template<typename GR, typename AF>
1.1531 - FilterArcs<const GR, const AF>
1.1532 - filterArcs(const GR& digraph, const AF& arc_filter_map) {
1.1533 - return FilterArcs<const GR, const AF>(digraph, arc_filter_map);
1.1534 + template<typename DGR, typename AF>
1.1535 + FilterArcs<const DGR, const AF>
1.1536 + filterArcs(const DGR& digraph, const AF& arc_filter) {
1.1537 + return FilterArcs<const DGR, const AF>(digraph, arc_filter);
1.1538 }
1.1539
1.1540 /// \ingroup graph_adaptors
1.1541 @@ -1743,22 +1748,24 @@
1.1542 typename EF = typename GR::template EdgeMap<bool> >
1.1543 class FilterEdges :
1.1544 public GraphAdaptorExtender<
1.1545 - SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > {
1.1546 + SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
1.1547 + EF, false> > {
1.1548 #endif
1.1549 + typedef GraphAdaptorExtender<
1.1550 + SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
1.1551 + EF, false> > Parent;
1.1552 +
1.1553 public:
1.1554 +
1.1555 /// The type of the adapted graph.
1.1556 typedef GR Graph;
1.1557 /// The type of the edge filter map.
1.1558 typedef EF EdgeFilterMap;
1.1559
1.1560 - typedef GraphAdaptorExtender<
1.1561 - SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> >
1.1562 - Parent;
1.1563 -
1.1564 typedef typename Parent::Edge Edge;
1.1565
1.1566 protected:
1.1567 - ConstMap<typename Graph::Node, bool> const_true_map;
1.1568 + ConstMap<typename GR::Node, Const<bool, true> > const_true_map;
1.1569
1.1570 FilterEdges() : const_true_map(true) {
1.1571 Parent::setNodeFilterMap(const_true_map);
1.1572 @@ -1770,11 +1777,9 @@
1.1573 ///
1.1574 /// Creates a subgraph for the given graph with the given edge
1.1575 /// filter map.
1.1576 - FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :
1.1577 - Parent(), const_true_map(true) {
1.1578 - Parent::setGraph(graph);
1.1579 - Parent::setNodeFilterMap(const_true_map);
1.1580 - Parent::setEdgeFilterMap(edge_filter_map);
1.1581 + FilterEdges(GR& graph, EF& edge_filter)
1.1582 + : Parent(), const_true_map() {
1.1583 + Parent::initialize(graph, const_true_map, edge_filter);
1.1584 }
1.1585
1.1586 /// \brief Sets the status of the given edge
1.1587 @@ -1812,21 +1817,21 @@
1.1588 /// \relates FilterEdges
1.1589 template<typename GR, typename EF>
1.1590 FilterEdges<const GR, EF>
1.1591 - filterEdges(const GR& graph, EF& edge_filter_map) {
1.1592 - return FilterEdges<const GR, EF>(graph, edge_filter_map);
1.1593 + filterEdges(const GR& graph, EF& edge_filter) {
1.1594 + return FilterEdges<const GR, EF>(graph, edge_filter);
1.1595 }
1.1596
1.1597 template<typename GR, typename EF>
1.1598 FilterEdges<const GR, const EF>
1.1599 - filterEdges(const GR& graph, const EF& edge_filter_map) {
1.1600 - return FilterEdges<const GR, const EF>(graph, edge_filter_map);
1.1601 + filterEdges(const GR& graph, const EF& edge_filter) {
1.1602 + return FilterEdges<const GR, const EF>(graph, edge_filter);
1.1603 }
1.1604
1.1605
1.1606 - template <typename _Digraph>
1.1607 + template <typename DGR>
1.1608 class UndirectorBase {
1.1609 public:
1.1610 - typedef _Digraph Digraph;
1.1611 + typedef DGR Digraph;
1.1612 typedef UndirectorBase Adaptor;
1.1613
1.1614 typedef True UndirectedTag;
1.1615 @@ -1834,31 +1839,31 @@
1.1616 typedef typename Digraph::Arc Edge;
1.1617 typedef typename Digraph::Node Node;
1.1618
1.1619 - class Arc : public Edge {
1.1620 + class Arc {
1.1621 friend class UndirectorBase;
1.1622 protected:
1.1623 + Edge _edge;
1.1624 bool _forward;
1.1625
1.1626 - Arc(const Edge& edge, bool forward) :
1.1627 - Edge(edge), _forward(forward) {}
1.1628 + Arc(const Edge& edge, bool forward)
1.1629 + : _edge(edge), _forward(forward) {}
1.1630
1.1631 public:
1.1632 Arc() {}
1.1633
1.1634 - Arc(Invalid) : Edge(INVALID), _forward(true) {}
1.1635 + Arc(Invalid) : _edge(INVALID), _forward(true) {}
1.1636 +
1.1637 + operator const Edge&() const { return _edge; }
1.1638
1.1639 bool operator==(const Arc &other) const {
1.1640 - return _forward == other._forward &&
1.1641 - static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
1.1642 + return _forward == other._forward && _edge == other._edge;
1.1643 }
1.1644 bool operator!=(const Arc &other) const {
1.1645 - return _forward != other._forward ||
1.1646 - static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
1.1647 + return _forward != other._forward || _edge != other._edge;
1.1648 }
1.1649 bool operator<(const Arc &other) const {
1.1650 return _forward < other._forward ||
1.1651 - (_forward == other._forward &&
1.1652 - static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
1.1653 + (_forward == other._forward && _edge < other._edge);
1.1654 }
1.1655 };
1.1656
1.1657 @@ -1871,7 +1876,7 @@
1.1658 }
1.1659
1.1660 void first(Arc& a) const {
1.1661 - _digraph->first(a);
1.1662 + _digraph->first(a._edge);
1.1663 a._forward = true;
1.1664 }
1.1665
1.1666 @@ -1879,7 +1884,7 @@
1.1667 if (a._forward) {
1.1668 a._forward = false;
1.1669 } else {
1.1670 - _digraph->next(a);
1.1671 + _digraph->next(a._edge);
1.1672 a._forward = true;
1.1673 }
1.1674 }
1.1675 @@ -1893,48 +1898,48 @@
1.1676 }
1.1677
1.1678 void firstOut(Arc& a, const Node& n) const {
1.1679 - _digraph->firstIn(a, n);
1.1680 - if( static_cast<const Edge&>(a) != INVALID ) {
1.1681 + _digraph->firstIn(a._edge, n);
1.1682 + if (a._edge != INVALID ) {
1.1683 a._forward = false;
1.1684 } else {
1.1685 - _digraph->firstOut(a, n);
1.1686 + _digraph->firstOut(a._edge, n);
1.1687 a._forward = true;
1.1688 }
1.1689 }
1.1690 void nextOut(Arc &a) const {
1.1691 if (!a._forward) {
1.1692 - Node n = _digraph->target(a);
1.1693 - _digraph->nextIn(a);
1.1694 - if (static_cast<const Edge&>(a) == INVALID ) {
1.1695 - _digraph->firstOut(a, n);
1.1696 + Node n = _digraph->target(a._edge);
1.1697 + _digraph->nextIn(a._edge);
1.1698 + if (a._edge == INVALID) {
1.1699 + _digraph->firstOut(a._edge, n);
1.1700 a._forward = true;
1.1701 }
1.1702 }
1.1703 else {
1.1704 - _digraph->nextOut(a);
1.1705 + _digraph->nextOut(a._edge);
1.1706 }
1.1707 }
1.1708
1.1709 void firstIn(Arc &a, const Node &n) const {
1.1710 - _digraph->firstOut(a, n);
1.1711 - if (static_cast<const Edge&>(a) != INVALID ) {
1.1712 + _digraph->firstOut(a._edge, n);
1.1713 + if (a._edge != INVALID ) {
1.1714 a._forward = false;
1.1715 } else {
1.1716 - _digraph->firstIn(a, n);
1.1717 + _digraph->firstIn(a._edge, n);
1.1718 a._forward = true;
1.1719 }
1.1720 }
1.1721 void nextIn(Arc &a) const {
1.1722 if (!a._forward) {
1.1723 - Node n = _digraph->source(a);
1.1724 - _digraph->nextOut(a);
1.1725 - if( static_cast<const Edge&>(a) == INVALID ) {
1.1726 - _digraph->firstIn(a, n);
1.1727 + Node n = _digraph->source(a._edge);
1.1728 + _digraph->nextOut(a._edge);
1.1729 + if (a._edge == INVALID ) {
1.1730 + _digraph->firstIn(a._edge, n);
1.1731 a._forward = true;
1.1732 }
1.1733 }
1.1734 else {
1.1735 - _digraph->nextIn(a);
1.1736 + _digraph->nextIn(a._edge);
1.1737 }
1.1738 }
1.1739
1.1740 @@ -1967,19 +1972,16 @@
1.1741 }
1.1742
1.1743 Node source(const Arc &a) const {
1.1744 - return a._forward ? _digraph->source(a) : _digraph->target(a);
1.1745 + return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge);
1.1746 }
1.1747
1.1748 Node target(const Arc &a) const {
1.1749 - return a._forward ? _digraph->target(a) : _digraph->source(a);
1.1750 + return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge);
1.1751 }
1.1752
1.1753 static Arc direct(const Edge &e, bool d) {
1.1754 return Arc(e, d);
1.1755 }
1.1756 - Arc direct(const Edge &e, const Node& n) const {
1.1757 - return Arc(e, _digraph->source(e) == n);
1.1758 - }
1.1759
1.1760 static bool direction(const Arc &a) { return a._forward; }
1.1761
1.1762 @@ -2062,34 +2064,35 @@
1.1763
1.1764 private:
1.1765
1.1766 - template <typename _Value>
1.1767 + template <typename V>
1.1768 class ArcMapBase {
1.1769 private:
1.1770
1.1771 - typedef typename Digraph::template ArcMap<_Value> MapImpl;
1.1772 + typedef typename DGR::template ArcMap<V> MapImpl;
1.1773
1.1774 public:
1.1775
1.1776 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1.1777
1.1778 - typedef _Value Value;
1.1779 + typedef V Value;
1.1780 typedef Arc Key;
1.1781 typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
1.1782 typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
1.1783 typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
1.1784 typedef typename MapTraits<MapImpl>::ReturnValue Reference;
1.1785
1.1786 - ArcMapBase(const Adaptor& adaptor) :
1.1787 + ArcMapBase(const UndirectorBase<DGR>& adaptor) :
1.1788 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
1.1789
1.1790 - ArcMapBase(const Adaptor& adaptor, const Value& v)
1.1791 - : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
1.1792 -
1.1793 - void set(const Arc& a, const Value& v) {
1.1794 + ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
1.1795 + : _forward(*adaptor._digraph, value),
1.1796 + _backward(*adaptor._digraph, value) {}
1.1797 +
1.1798 + void set(const Arc& a, const V& value) {
1.1799 if (direction(a)) {
1.1800 - _forward.set(a, v);
1.1801 + _forward.set(a, value);
1.1802 } else {
1.1803 - _backward.set(a, v);
1.1804 + _backward.set(a, value);
1.1805 }
1.1806 }
1.1807
1.1808 @@ -2117,17 +2120,17 @@
1.1809
1.1810 public:
1.1811
1.1812 - template <typename _Value>
1.1813 - class NodeMap : public Digraph::template NodeMap<_Value> {
1.1814 + template <typename V>
1.1815 + class NodeMap : public DGR::template NodeMap<V> {
1.1816 + typedef typename DGR::template NodeMap<V> Parent;
1.1817 +
1.1818 public:
1.1819 -
1.1820 - typedef _Value Value;
1.1821 - typedef typename Digraph::template NodeMap<Value> Parent;
1.1822 -
1.1823 - explicit NodeMap(const Adaptor& adaptor)
1.1824 + typedef V Value;
1.1825 +
1.1826 + explicit NodeMap(const UndirectorBase<DGR>& adaptor)
1.1827 : Parent(*adaptor._digraph) {}
1.1828
1.1829 - NodeMap(const Adaptor& adaptor, const _Value& value)
1.1830 + NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)
1.1831 : Parent(*adaptor._digraph, value) { }
1.1832
1.1833 private:
1.1834 @@ -2143,18 +2146,18 @@
1.1835
1.1836 };
1.1837
1.1838 - template <typename _Value>
1.1839 + template <typename V>
1.1840 class ArcMap
1.1841 - : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
1.1842 - {
1.1843 + : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > {
1.1844 + typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent;
1.1845 +
1.1846 public:
1.1847 - typedef _Value Value;
1.1848 - typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
1.1849 -
1.1850 - explicit ArcMap(const Adaptor& adaptor)
1.1851 + typedef V Value;
1.1852 +
1.1853 + explicit ArcMap(const UndirectorBase<DGR>& adaptor)
1.1854 : Parent(adaptor) {}
1.1855
1.1856 - ArcMap(const Adaptor& adaptor, const Value& value)
1.1857 + ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)
1.1858 : Parent(adaptor, value) {}
1.1859
1.1860 private:
1.1861 @@ -2169,17 +2172,17 @@
1.1862 }
1.1863 };
1.1864
1.1865 - template <typename _Value>
1.1866 - class EdgeMap : public Digraph::template ArcMap<_Value> {
1.1867 + template <typename V>
1.1868 + class EdgeMap : public Digraph::template ArcMap<V> {
1.1869 + typedef typename Digraph::template ArcMap<V> Parent;
1.1870 +
1.1871 public:
1.1872 -
1.1873 - typedef _Value Value;
1.1874 - typedef typename Digraph::template ArcMap<Value> Parent;
1.1875 -
1.1876 - explicit EdgeMap(const Adaptor& adaptor)
1.1877 + typedef V Value;
1.1878 +
1.1879 + explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
1.1880 : Parent(*adaptor._digraph) {}
1.1881
1.1882 - EdgeMap(const Adaptor& adaptor, const Value& value)
1.1883 + EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
1.1884 : Parent(*adaptor._digraph, value) {}
1.1885
1.1886 private:
1.1887 @@ -2195,19 +2198,22 @@
1.1888
1.1889 };
1.1890
1.1891 - typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
1.1892 + typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
1.1893 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
1.1894
1.1895 - typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;
1.1896 + typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
1.1897 EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
1.1898 +
1.1899 + typedef EdgeNotifier ArcNotifier;
1.1900 + ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
1.1901
1.1902 protected:
1.1903
1.1904 UndirectorBase() : _digraph(0) {}
1.1905
1.1906 - Digraph* _digraph;
1.1907 -
1.1908 - void setDigraph(Digraph& digraph) {
1.1909 + DGR* _digraph;
1.1910 +
1.1911 + void initialize(DGR& digraph) {
1.1912 _digraph = &digraph;
1.1913 }
1.1914
1.1915 @@ -2226,7 +2232,7 @@
1.1916 /// by adding or removing nodes or edges, unless the \c GR template
1.1917 /// parameter is set to be \c const.
1.1918 ///
1.1919 - /// \tparam GR The type of the adapted digraph.
1.1920 + /// \tparam DGR The type of the adapted digraph.
1.1921 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.1922 /// It can also be specified to be \c const.
1.1923 ///
1.1924 @@ -2236,17 +2242,17 @@
1.1925 /// each other.
1.1926 /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
1.1927 /// of the adapted digraph.)
1.1928 - template<typename GR>
1.1929 + template<typename DGR>
1.1930 #ifdef DOXYGEN
1.1931 class Undirector {
1.1932 #else
1.1933 class Undirector :
1.1934 - public GraphAdaptorExtender<UndirectorBase<GR> > {
1.1935 + public GraphAdaptorExtender<UndirectorBase<DGR> > {
1.1936 #endif
1.1937 + typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
1.1938 public:
1.1939 /// The type of the adapted digraph.
1.1940 - typedef GR Digraph;
1.1941 - typedef GraphAdaptorExtender<UndirectorBase<GR> > Parent;
1.1942 + typedef DGR Digraph;
1.1943 protected:
1.1944 Undirector() { }
1.1945 public:
1.1946 @@ -2254,34 +2260,35 @@
1.1947 /// \brief Constructor
1.1948 ///
1.1949 /// Creates an undirected graph from the given digraph.
1.1950 - Undirector(Digraph& digraph) {
1.1951 - setDigraph(digraph);
1.1952 + Undirector(DGR& digraph) {
1.1953 + initialize(digraph);
1.1954 }
1.1955
1.1956 /// \brief Arc map combined from two original arc maps
1.1957 ///
1.1958 /// This map adaptor class adapts two arc maps of the underlying
1.1959 /// digraph to get an arc map of the undirected graph.
1.1960 - /// Its value type is inherited from the first arc map type
1.1961 - /// (\c %ForwardMap).
1.1962 - template <typename ForwardMap, typename BackwardMap>
1.1963 + /// Its value type is inherited from the first arc map type (\c FW).
1.1964 + /// \tparam FW The type of the "foward" arc map.
1.1965 + /// \tparam BK The type of the "backward" arc map.
1.1966 + template <typename FW, typename BK>
1.1967 class CombinedArcMap {
1.1968 public:
1.1969
1.1970 /// The key type of the map
1.1971 typedef typename Parent::Arc Key;
1.1972 /// The value type of the map
1.1973 - typedef typename ForwardMap::Value Value;
1.1974 -
1.1975 - typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
1.1976 -
1.1977 - typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
1.1978 - typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
1.1979 - typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
1.1980 - typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
1.1981 + typedef typename FW::Value Value;
1.1982 +
1.1983 + typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;
1.1984 +
1.1985 + typedef typename MapTraits<FW>::ReturnValue ReturnValue;
1.1986 + typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;
1.1987 + typedef typename MapTraits<FW>::ReturnValue Reference;
1.1988 + typedef typename MapTraits<FW>::ConstReturnValue ConstReference;
1.1989
1.1990 /// Constructor
1.1991 - CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
1.1992 + CombinedArcMap(FW& forward, BK& backward)
1.1993 : _forward(&forward), _backward(&backward) {}
1.1994
1.1995 /// Sets the value associated with the given key.
1.1996 @@ -2313,39 +2320,36 @@
1.1997
1.1998 protected:
1.1999
1.2000 - ForwardMap* _forward;
1.2001 - BackwardMap* _backward;
1.2002 + FW* _forward;
1.2003 + BK* _backward;
1.2004
1.2005 };
1.2006
1.2007 /// \brief Returns a combined arc map
1.2008 ///
1.2009 /// This function just returns a combined arc map.
1.2010 - template <typename ForwardMap, typename BackwardMap>
1.2011 - static CombinedArcMap<ForwardMap, BackwardMap>
1.2012 - combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
1.2013 - return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
1.2014 + template <typename FW, typename BK>
1.2015 + static CombinedArcMap<FW, BK>
1.2016 + combinedArcMap(FW& forward, BK& backward) {
1.2017 + return CombinedArcMap<FW, BK>(forward, backward);
1.2018 }
1.2019
1.2020 - template <typename ForwardMap, typename BackwardMap>
1.2021 - static CombinedArcMap<const ForwardMap, BackwardMap>
1.2022 - combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
1.2023 - return CombinedArcMap<const ForwardMap,
1.2024 - BackwardMap>(forward, backward);
1.2025 + template <typename FW, typename BK>
1.2026 + static CombinedArcMap<const FW, BK>
1.2027 + combinedArcMap(const FW& forward, BK& backward) {
1.2028 + return CombinedArcMap<const FW, BK>(forward, backward);
1.2029 }
1.2030
1.2031 - template <typename ForwardMap, typename BackwardMap>
1.2032 - static CombinedArcMap<ForwardMap, const BackwardMap>
1.2033 - combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
1.2034 - return CombinedArcMap<ForwardMap,
1.2035 - const BackwardMap>(forward, backward);
1.2036 + template <typename FW, typename BK>
1.2037 + static CombinedArcMap<FW, const BK>
1.2038 + combinedArcMap(FW& forward, const BK& backward) {
1.2039 + return CombinedArcMap<FW, const BK>(forward, backward);
1.2040 }
1.2041
1.2042 - template <typename ForwardMap, typename BackwardMap>
1.2043 - static CombinedArcMap<const ForwardMap, const BackwardMap>
1.2044 - combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
1.2045 - return CombinedArcMap<const ForwardMap,
1.2046 - const BackwardMap>(forward, backward);
1.2047 + template <typename FW, typename BK>
1.2048 + static CombinedArcMap<const FW, const BK>
1.2049 + combinedArcMap(const FW& forward, const BK& backward) {
1.2050 + return CombinedArcMap<const FW, const BK>(forward, backward);
1.2051 }
1.2052
1.2053 };
1.2054 @@ -2355,21 +2359,21 @@
1.2055 /// This function just returns a read-only \ref Undirector adaptor.
1.2056 /// \ingroup graph_adaptors
1.2057 /// \relates Undirector
1.2058 - template<typename GR>
1.2059 - Undirector<const GR> undirector(const GR& digraph) {
1.2060 - return Undirector<const GR>(digraph);
1.2061 + template<typename DGR>
1.2062 + Undirector<const DGR> undirector(const DGR& digraph) {
1.2063 + return Undirector<const DGR>(digraph);
1.2064 }
1.2065
1.2066
1.2067 - template <typename _Graph, typename _DirectionMap>
1.2068 + template <typename GR, typename DM>
1.2069 class OrienterBase {
1.2070 public:
1.2071
1.2072 - typedef _Graph Graph;
1.2073 - typedef _DirectionMap DirectionMap;
1.2074 -
1.2075 - typedef typename Graph::Node Node;
1.2076 - typedef typename Graph::Edge Arc;
1.2077 + typedef GR Graph;
1.2078 + typedef DM DirectionMap;
1.2079 +
1.2080 + typedef typename GR::Node Node;
1.2081 + typedef typename GR::Edge Arc;
1.2082
1.2083 void reverseArc(const Arc& arc) {
1.2084 _direction->set(arc, !(*_direction)[arc]);
1.2085 @@ -2448,22 +2452,22 @@
1.2086 int maxNodeId() const { return _graph->maxNodeId(); }
1.2087 int maxArcId() const { return _graph->maxEdgeId(); }
1.2088
1.2089 - typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.2090 + typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
1.2091 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
1.2092
1.2093 - typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
1.2094 + typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
1.2095 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
1.2096
1.2097 - template <typename _Value>
1.2098 - class NodeMap : public _Graph::template NodeMap<_Value> {
1.2099 + template <typename V>
1.2100 + class NodeMap : public GR::template NodeMap<V> {
1.2101 + typedef typename GR::template NodeMap<V> Parent;
1.2102 +
1.2103 public:
1.2104
1.2105 - typedef typename _Graph::template NodeMap<_Value> Parent;
1.2106 -
1.2107 - explicit NodeMap(const OrienterBase& adapter)
1.2108 + explicit NodeMap(const OrienterBase<GR, DM>& adapter)
1.2109 : Parent(*adapter._graph) {}
1.2110
1.2111 - NodeMap(const OrienterBase& adapter, const _Value& value)
1.2112 + NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
1.2113 : Parent(*adapter._graph, value) {}
1.2114
1.2115 private:
1.2116 @@ -2479,16 +2483,16 @@
1.2117
1.2118 };
1.2119
1.2120 - template <typename _Value>
1.2121 - class ArcMap : public _Graph::template EdgeMap<_Value> {
1.2122 + template <typename V>
1.2123 + class ArcMap : public GR::template EdgeMap<V> {
1.2124 + typedef typename Graph::template EdgeMap<V> Parent;
1.2125 +
1.2126 public:
1.2127
1.2128 - typedef typename Graph::template EdgeMap<_Value> Parent;
1.2129 -
1.2130 - explicit ArcMap(const OrienterBase& adapter)
1.2131 + explicit ArcMap(const OrienterBase<GR, DM>& adapter)
1.2132 : Parent(*adapter._graph) { }
1.2133
1.2134 - ArcMap(const OrienterBase& adapter, const _Value& value)
1.2135 + ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
1.2136 : Parent(*adapter._graph, value) { }
1.2137
1.2138 private:
1.2139 @@ -2507,16 +2511,13 @@
1.2140
1.2141 protected:
1.2142 Graph* _graph;
1.2143 - DirectionMap* _direction;
1.2144 -
1.2145 - void setDirectionMap(DirectionMap& direction) {
1.2146 + DM* _direction;
1.2147 +
1.2148 + void initialize(GR& graph, DM& direction) {
1.2149 + _graph = &graph;
1.2150 _direction = &direction;
1.2151 }
1.2152
1.2153 - void setGraph(Graph& graph) {
1.2154 - _graph = &graph;
1.2155 - }
1.2156 -
1.2157 };
1.2158
1.2159 /// \ingroup graph_adaptors
1.2160 @@ -2556,6 +2557,7 @@
1.2161 class Orienter :
1.2162 public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
1.2163 #endif
1.2164 + typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
1.2165 public:
1.2166
1.2167 /// The type of the adapted graph.
1.2168 @@ -2563,18 +2565,18 @@
1.2169 /// The type of the direction edge map.
1.2170 typedef DM DirectionMap;
1.2171
1.2172 - typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
1.2173 typedef typename Parent::Arc Arc;
1.2174 +
1.2175 protected:
1.2176 Orienter() { }
1.2177 +
1.2178 public:
1.2179
1.2180 /// \brief Constructor
1.2181 ///
1.2182 /// Constructor of the adaptor.
1.2183 - Orienter(Graph& graph, DirectionMap& direction) {
1.2184 - setGraph(graph);
1.2185 - setDirectionMap(direction);
1.2186 + Orienter(GR& graph, DM& direction) {
1.2187 + Parent::initialize(graph, direction);
1.2188 }
1.2189
1.2190 /// \brief Reverses the given arc
1.2191 @@ -2594,67 +2596,62 @@
1.2192 /// \relates Orienter
1.2193 template<typename GR, typename DM>
1.2194 Orienter<const GR, DM>
1.2195 - orienter(const GR& graph, DM& direction_map) {
1.2196 - return Orienter<const GR, DM>(graph, direction_map);
1.2197 + orienter(const GR& graph, DM& direction) {
1.2198 + return Orienter<const GR, DM>(graph, direction);
1.2199 }
1.2200
1.2201 template<typename GR, typename DM>
1.2202 Orienter<const GR, const DM>
1.2203 - orienter(const GR& graph, const DM& direction_map) {
1.2204 - return Orienter<const GR, const DM>(graph, direction_map);
1.2205 + orienter(const GR& graph, const DM& direction) {
1.2206 + return Orienter<const GR, const DM>(graph, direction);
1.2207 }
1.2208
1.2209 namespace _adaptor_bits {
1.2210
1.2211 - template<typename Digraph,
1.2212 - typename CapacityMap,
1.2213 - typename FlowMap,
1.2214 - typename Tolerance>
1.2215 + template <typename DGR, typename CM, typename FM, typename TL>
1.2216 class ResForwardFilter {
1.2217 public:
1.2218
1.2219 - typedef typename Digraph::Arc Key;
1.2220 + typedef typename DGR::Arc Key;
1.2221 typedef bool Value;
1.2222
1.2223 private:
1.2224
1.2225 - const CapacityMap* _capacity;
1.2226 - const FlowMap* _flow;
1.2227 - Tolerance _tolerance;
1.2228 + const CM* _capacity;
1.2229 + const FM* _flow;
1.2230 + TL _tolerance;
1.2231 +
1.2232 public:
1.2233
1.2234 - ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
1.2235 - const Tolerance& tolerance = Tolerance())
1.2236 + ResForwardFilter(const CM& capacity, const FM& flow,
1.2237 + const TL& tolerance = TL())
1.2238 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
1.2239
1.2240 - bool operator[](const typename Digraph::Arc& a) const {
1.2241 + bool operator[](const typename DGR::Arc& a) const {
1.2242 return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
1.2243 }
1.2244 };
1.2245
1.2246 - template<typename Digraph,
1.2247 - typename CapacityMap,
1.2248 - typename FlowMap,
1.2249 - typename Tolerance>
1.2250 + template<typename DGR,typename CM, typename FM, typename TL>
1.2251 class ResBackwardFilter {
1.2252 public:
1.2253
1.2254 - typedef typename Digraph::Arc Key;
1.2255 + typedef typename DGR::Arc Key;
1.2256 typedef bool Value;
1.2257
1.2258 private:
1.2259
1.2260 - const CapacityMap* _capacity;
1.2261 - const FlowMap* _flow;
1.2262 - Tolerance _tolerance;
1.2263 + const CM* _capacity;
1.2264 + const FM* _flow;
1.2265 + TL _tolerance;
1.2266
1.2267 public:
1.2268
1.2269 - ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
1.2270 - const Tolerance& tolerance = Tolerance())
1.2271 + ResBackwardFilter(const CM& capacity, const FM& flow,
1.2272 + const TL& tolerance = TL())
1.2273 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
1.2274
1.2275 - bool operator[](const typename Digraph::Arc& a) const {
1.2276 + bool operator[](const typename DGR::Arc& a) const {
1.2277 return _tolerance.positive((*_flow)[a]);
1.2278 }
1.2279 };
1.2280 @@ -2681,7 +2678,7 @@
1.2281 /// arcs).
1.2282 /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
1.2283 ///
1.2284 - /// \tparam GR The type of the adapted digraph.
1.2285 + /// \tparam DGR The type of the adapted digraph.
1.2286 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.2287 /// It is implicitly \c const.
1.2288 /// \tparam CM The type of the capacity map.
1.2289 @@ -2703,25 +2700,26 @@
1.2290 /// convertible to each other, moreover the \c Arc type of the adaptor
1.2291 /// is convertible to the \c Arc type of the adapted digraph.
1.2292 #ifdef DOXYGEN
1.2293 - template<typename GR, typename CM, typename FM, typename TL>
1.2294 + template<typename DGR, typename CM, typename FM, typename TL>
1.2295 class ResidualDigraph
1.2296 #else
1.2297 - template<typename GR,
1.2298 - typename CM = typename GR::template ArcMap<int>,
1.2299 + template<typename DGR,
1.2300 + typename CM = typename DGR::template ArcMap<int>,
1.2301 typename FM = CM,
1.2302 typename TL = Tolerance<typename CM::Value> >
1.2303 - class ResidualDigraph :
1.2304 - public FilterArcs<
1.2305 - Undirector<const GR>,
1.2306 - typename Undirector<const GR>::template CombinedArcMap<
1.2307 - _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>,
1.2308 - _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > >
1.2309 + class ResidualDigraph
1.2310 + : public SubDigraph<
1.2311 + Undirector<const DGR>,
1.2312 + ConstMap<typename DGR::Node, Const<bool, true> >,
1.2313 + typename Undirector<const DGR>::template CombinedArcMap<
1.2314 + _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
1.2315 + _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >
1.2316 #endif
1.2317 {
1.2318 public:
1.2319
1.2320 /// The type of the underlying digraph.
1.2321 - typedef GR Digraph;
1.2322 + typedef DGR Digraph;
1.2323 /// The type of the capacity map.
1.2324 typedef CM CapacityMap;
1.2325 /// The type of the flow map.
1.2326 @@ -2736,21 +2734,24 @@
1.2327
1.2328 typedef Undirector<const Digraph> Undirected;
1.2329
1.2330 - typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
1.2331 - FlowMap, Tolerance> ForwardFilter;
1.2332 -
1.2333 - typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
1.2334 - FlowMap, Tolerance> BackwardFilter;
1.2335 + typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter;
1.2336 +
1.2337 + typedef _adaptor_bits::ResForwardFilter<const DGR, CM,
1.2338 + FM, TL> ForwardFilter;
1.2339 +
1.2340 + typedef _adaptor_bits::ResBackwardFilter<const DGR, CM,
1.2341 + FM, TL> BackwardFilter;
1.2342
1.2343 typedef typename Undirected::
1.2344 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
1.2345
1.2346 - typedef FilterArcs<Undirected, ArcFilter> Parent;
1.2347 + typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;
1.2348
1.2349 const CapacityMap* _capacity;
1.2350 FlowMap* _flow;
1.2351
1.2352 Undirected _graph;
1.2353 + NodeFilter _node_filter;
1.2354 ForwardFilter _forward_filter;
1.2355 BackwardFilter _backward_filter;
1.2356 ArcFilter _arc_filter;
1.2357 @@ -2761,15 +2762,15 @@
1.2358 ///
1.2359 /// Constructor of the residual digraph adaptor. The parameters are the
1.2360 /// digraph, the capacity map, the flow map, and a tolerance object.
1.2361 - ResidualDigraph(const Digraph& digraph, const CapacityMap& capacity,
1.2362 - FlowMap& flow, const Tolerance& tolerance = Tolerance())
1.2363 - : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
1.2364 + ResidualDigraph(const DGR& digraph, const CM& capacity,
1.2365 + FM& flow, const TL& tolerance = Tolerance())
1.2366 + : Parent(), _capacity(&capacity), _flow(&flow),
1.2367 + _graph(digraph), _node_filter(),
1.2368 _forward_filter(capacity, flow, tolerance),
1.2369 _backward_filter(capacity, flow, tolerance),
1.2370 _arc_filter(_forward_filter, _backward_filter)
1.2371 {
1.2372 - Parent::setDigraph(_graph);
1.2373 - Parent::setArcFilterMap(_arc_filter);
1.2374 + Parent::initialize(_graph, _node_filter, _arc_filter);
1.2375 }
1.2376
1.2377 typedef typename Parent::Arc Arc;
1.2378 @@ -2845,7 +2846,8 @@
1.2379 typedef typename CapacityMap::Value Value;
1.2380
1.2381 /// Constructor
1.2382 - ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
1.2383 + ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
1.2384 + : _adaptor(&adaptor) {}
1.2385
1.2386 /// Returns the value associated with the given residual arc
1.2387 Value operator[](const Arc& a) const {
1.2388 @@ -2865,26 +2867,27 @@
1.2389
1.2390 /// \brief Returns a (read-only) Residual adaptor
1.2391 ///
1.2392 - /// This function just returns a (read-only) \ref Residual adaptor.
1.2393 + /// This function just returns a (read-only) \ref ResidualDigraph adaptor.
1.2394 /// \ingroup graph_adaptors
1.2395 - /// \relates Residual
1.2396 - template<typename GR, typename CM, typename FM>
1.2397 - ResidualDigraph<GR, CM, FM>
1.2398 - residualDigraph(const GR& digraph, const CM& capacity_map, FM& flow_map) {
1.2399 - return ResidualDigraph<GR, CM, FM> (digraph, capacity_map, flow_map);
1.2400 + /// \relates ResidualDigraph
1.2401 + template<typename DGR, typename CM, typename FM>
1.2402 + ResidualDigraph<DGR, CM, FM>
1.2403 + residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) {
1.2404 + return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map);
1.2405 }
1.2406
1.2407
1.2408 - template <typename _Digraph>
1.2409 + template <typename DGR>
1.2410 class SplitNodesBase {
1.2411 + typedef DigraphAdaptorBase<const DGR> Parent;
1.2412 +
1.2413 public:
1.2414
1.2415 - typedef _Digraph Digraph;
1.2416 - typedef DigraphAdaptorBase<const _Digraph> Parent;
1.2417 + typedef DGR Digraph;
1.2418 typedef SplitNodesBase Adaptor;
1.2419
1.2420 - typedef typename Digraph::Node DigraphNode;
1.2421 - typedef typename Digraph::Arc DigraphArc;
1.2422 + typedef typename DGR::Node DigraphNode;
1.2423 + typedef typename DGR::Arc DigraphArc;
1.2424
1.2425 class Node;
1.2426 class Arc;
1.2427 @@ -3148,32 +3151,32 @@
1.2428
1.2429 private:
1.2430
1.2431 - template <typename _Value>
1.2432 + template <typename V>
1.2433 class NodeMapBase
1.2434 - : public MapTraits<typename Parent::template NodeMap<_Value> > {
1.2435 - typedef typename Parent::template NodeMap<_Value> NodeImpl;
1.2436 + : public MapTraits<typename Parent::template NodeMap<V> > {
1.2437 + typedef typename Parent::template NodeMap<V> NodeImpl;
1.2438 public:
1.2439 typedef Node Key;
1.2440 - typedef _Value Value;
1.2441 + typedef V Value;
1.2442 typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
1.2443 typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
1.2444 typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
1.2445 typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
1.2446 typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
1.2447
1.2448 - NodeMapBase(const Adaptor& adaptor)
1.2449 + NodeMapBase(const SplitNodesBase<DGR>& adaptor)
1.2450 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
1.2451 - NodeMapBase(const Adaptor& adaptor, const Value& value)
1.2452 + NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
1.2453 : _in_map(*adaptor._digraph, value),
1.2454 _out_map(*adaptor._digraph, value) {}
1.2455
1.2456 - void set(const Node& key, const Value& val) {
1.2457 - if (Adaptor::inNode(key)) { _in_map.set(key, val); }
1.2458 + void set(const Node& key, const V& val) {
1.2459 + if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }
1.2460 else {_out_map.set(key, val); }
1.2461 }
1.2462
1.2463 ReturnValue operator[](const Node& key) {
1.2464 - if (Adaptor::inNode(key)) { return _in_map[key]; }
1.2465 + if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }
1.2466 else { return _out_map[key]; }
1.2467 }
1.2468
1.2469 @@ -3186,47 +3189,47 @@
1.2470 NodeImpl _in_map, _out_map;
1.2471 };
1.2472
1.2473 - template <typename _Value>
1.2474 + template <typename V>
1.2475 class ArcMapBase
1.2476 - : public MapTraits<typename Parent::template ArcMap<_Value> > {
1.2477 - typedef typename Parent::template ArcMap<_Value> ArcImpl;
1.2478 - typedef typename Parent::template NodeMap<_Value> NodeImpl;
1.2479 + : public MapTraits<typename Parent::template ArcMap<V> > {
1.2480 + typedef typename Parent::template ArcMap<V> ArcImpl;
1.2481 + typedef typename Parent::template NodeMap<V> NodeImpl;
1.2482 public:
1.2483 typedef Arc Key;
1.2484 - typedef _Value Value;
1.2485 + typedef V Value;
1.2486 typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
1.2487 typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
1.2488 typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
1.2489 typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
1.2490 typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
1.2491
1.2492 - ArcMapBase(const Adaptor& adaptor)
1.2493 + ArcMapBase(const SplitNodesBase<DGR>& adaptor)
1.2494 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
1.2495 - ArcMapBase(const Adaptor& adaptor, const Value& value)
1.2496 + ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
1.2497 : _arc_map(*adaptor._digraph, value),
1.2498 _node_map(*adaptor._digraph, value) {}
1.2499
1.2500 - void set(const Arc& key, const Value& val) {
1.2501 - if (Adaptor::origArc(key)) {
1.2502 - _arc_map.set(key._item.first(), val);
1.2503 + void set(const Arc& key, const V& val) {
1.2504 + if (SplitNodesBase<DGR>::origArc(key)) {
1.2505 + _arc_map.set(static_cast<const DigraphArc&>(key), val);
1.2506 } else {
1.2507 - _node_map.set(key._item.second(), val);
1.2508 + _node_map.set(static_cast<const DigraphNode&>(key), val);
1.2509 }
1.2510 }
1.2511
1.2512 ReturnValue operator[](const Arc& key) {
1.2513 - if (Adaptor::origArc(key)) {
1.2514 - return _arc_map[key._item.first()];
1.2515 + if (SplitNodesBase<DGR>::origArc(key)) {
1.2516 + return _arc_map[static_cast<const DigraphArc&>(key)];
1.2517 } else {
1.2518 - return _node_map[key._item.second()];
1.2519 + return _node_map[static_cast<const DigraphNode&>(key)];
1.2520 }
1.2521 }
1.2522
1.2523 ConstReturnValue operator[](const Arc& key) const {
1.2524 - if (Adaptor::origArc(key)) {
1.2525 - return _arc_map[key._item.first()];
1.2526 + if (SplitNodesBase<DGR>::origArc(key)) {
1.2527 + return _arc_map[static_cast<const DigraphArc&>(key)];
1.2528 } else {
1.2529 - return _node_map[key._item.second()];
1.2530 + return _node_map[static_cast<const DigraphNode&>(key)];
1.2531 }
1.2532 }
1.2533
1.2534 @@ -3237,18 +3240,18 @@
1.2535
1.2536 public:
1.2537
1.2538 - template <typename _Value>
1.2539 + template <typename V>
1.2540 class NodeMap
1.2541 - : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
1.2542 - {
1.2543 + : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > {
1.2544 + typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent;
1.2545 +
1.2546 public:
1.2547 - typedef _Value Value;
1.2548 - typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
1.2549 -
1.2550 - NodeMap(const Adaptor& adaptor)
1.2551 + typedef V Value;
1.2552 +
1.2553 + NodeMap(const SplitNodesBase<DGR>& adaptor)
1.2554 : Parent(adaptor) {}
1.2555
1.2556 - NodeMap(const Adaptor& adaptor, const Value& value)
1.2557 + NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
1.2558 : Parent(adaptor, value) {}
1.2559
1.2560 private:
1.2561 @@ -3263,18 +3266,18 @@
1.2562 }
1.2563 };
1.2564
1.2565 - template <typename _Value>
1.2566 + template <typename V>
1.2567 class ArcMap
1.2568 - : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
1.2569 - {
1.2570 + : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > {
1.2571 + typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent;
1.2572 +
1.2573 public:
1.2574 - typedef _Value Value;
1.2575 - typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
1.2576 -
1.2577 - ArcMap(const Adaptor& adaptor)
1.2578 + typedef V Value;
1.2579 +
1.2580 + ArcMap(const SplitNodesBase<DGR>& adaptor)
1.2581 : Parent(adaptor) {}
1.2582
1.2583 - ArcMap(const Adaptor& adaptor, const Value& value)
1.2584 + ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
1.2585 : Parent(adaptor, value) {}
1.2586
1.2587 private:
1.2588 @@ -3293,9 +3296,9 @@
1.2589
1.2590 SplitNodesBase() : _digraph(0) {}
1.2591
1.2592 - Digraph* _digraph;
1.2593 -
1.2594 - void setDigraph(Digraph& digraph) {
1.2595 + DGR* _digraph;
1.2596 +
1.2597 + void initialize(Digraph& digraph) {
1.2598 _digraph = &digraph;
1.2599 }
1.2600
1.2601 @@ -3322,25 +3325,26 @@
1.2602 /// costs/capacities of the original digraph to the \e bind \e arcs
1.2603 /// in the adaptor.
1.2604 ///
1.2605 - /// \tparam GR The type of the adapted digraph.
1.2606 + /// \tparam DGR The type of the adapted digraph.
1.2607 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.2608 /// It is implicitly \c const.
1.2609 ///
1.2610 /// \note The \c Node type of this adaptor is converible to the \c Node
1.2611 /// type of the adapted digraph.
1.2612 - template <typename GR>
1.2613 + template <typename DGR>
1.2614 #ifdef DOXYGEN
1.2615 class SplitNodes {
1.2616 #else
1.2617 class SplitNodes
1.2618 - : public DigraphAdaptorExtender<SplitNodesBase<const GR> > {
1.2619 + : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
1.2620 #endif
1.2621 + typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
1.2622 +
1.2623 public:
1.2624 - typedef GR Digraph;
1.2625 - typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent;
1.2626 -
1.2627 - typedef typename Digraph::Node DigraphNode;
1.2628 - typedef typename Digraph::Arc DigraphArc;
1.2629 + typedef DGR Digraph;
1.2630 +
1.2631 + typedef typename DGR::Node DigraphNode;
1.2632 + typedef typename DGR::Arc DigraphArc;
1.2633
1.2634 typedef typename Parent::Node Node;
1.2635 typedef typename Parent::Arc Arc;
1.2636 @@ -3348,8 +3352,8 @@
1.2637 /// \brief Constructor
1.2638 ///
1.2639 /// Constructor of the adaptor.
1.2640 - SplitNodes(const Digraph& g) {
1.2641 - Parent::setDigraph(g);
1.2642 + SplitNodes(const DGR& g) {
1.2643 + Parent::initialize(g);
1.2644 }
1.2645
1.2646 /// \brief Returns \c true if the given node is an in-node.
1.2647 @@ -3418,30 +3422,31 @@
1.2648 ///
1.2649 /// This map adaptor class adapts two node maps of the original digraph
1.2650 /// to get a node map of the split digraph.
1.2651 - /// Its value type is inherited from the first node map type
1.2652 - /// (\c InNodeMap).
1.2653 - template <typename InNodeMap, typename OutNodeMap>
1.2654 + /// Its value type is inherited from the first node map type (\c IN).
1.2655 + /// \tparam IN The type of the node map for the in-nodes.
1.2656 + /// \tparam OUT The type of the node map for the out-nodes.
1.2657 + template <typename IN, typename OUT>
1.2658 class CombinedNodeMap {
1.2659 public:
1.2660
1.2661 /// The key type of the map
1.2662 typedef Node Key;
1.2663 /// The value type of the map
1.2664 - typedef typename InNodeMap::Value Value;
1.2665 -
1.2666 - typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
1.2667 - typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
1.2668 - typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
1.2669 - typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
1.2670 - typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
1.2671 + typedef typename IN::Value Value;
1.2672 +
1.2673 + typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag;
1.2674 + typedef typename MapTraits<IN>::ReturnValue ReturnValue;
1.2675 + typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue;
1.2676 + typedef typename MapTraits<IN>::ReturnValue Reference;
1.2677 + typedef typename MapTraits<IN>::ConstReturnValue ConstReference;
1.2678
1.2679 /// Constructor
1.2680 - CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
1.2681 + CombinedNodeMap(IN& in_map, OUT& out_map)
1.2682 : _in_map(in_map), _out_map(out_map) {}
1.2683
1.2684 /// Returns the value associated with the given key.
1.2685 Value operator[](const Key& key) const {
1.2686 - if (Parent::inNode(key)) {
1.2687 + if (SplitNodesBase<const DGR>::inNode(key)) {
1.2688 return _in_map[key];
1.2689 } else {
1.2690 return _out_map[key];
1.2691 @@ -3450,7 +3455,7 @@
1.2692
1.2693 /// Returns a reference to the value associated with the given key.
1.2694 Value& operator[](const Key& key) {
1.2695 - if (Parent::inNode(key)) {
1.2696 + if (SplitNodesBase<const DGR>::inNode(key)) {
1.2697 return _in_map[key];
1.2698 } else {
1.2699 return _out_map[key];
1.2700 @@ -3459,7 +3464,7 @@
1.2701
1.2702 /// Sets the value associated with the given key.
1.2703 void set(const Key& key, const Value& value) {
1.2704 - if (Parent::inNode(key)) {
1.2705 + if (SplitNodesBase<const DGR>::inNode(key)) {
1.2706 _in_map.set(key, value);
1.2707 } else {
1.2708 _out_map.set(key, value);
1.2709 @@ -3468,8 +3473,8 @@
1.2710
1.2711 private:
1.2712
1.2713 - InNodeMap& _in_map;
1.2714 - OutNodeMap& _out_map;
1.2715 + IN& _in_map;
1.2716 + OUT& _out_map;
1.2717
1.2718 };
1.2719
1.2720 @@ -3477,29 +3482,28 @@
1.2721 /// \brief Returns a combined node map
1.2722 ///
1.2723 /// This function just returns a combined node map.
1.2724 - template <typename InNodeMap, typename OutNodeMap>
1.2725 - static CombinedNodeMap<InNodeMap, OutNodeMap>
1.2726 - combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
1.2727 - return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
1.2728 + template <typename IN, typename OUT>
1.2729 + static CombinedNodeMap<IN, OUT>
1.2730 + combinedNodeMap(IN& in_map, OUT& out_map) {
1.2731 + return CombinedNodeMap<IN, OUT>(in_map, out_map);
1.2732 }
1.2733
1.2734 - template <typename InNodeMap, typename OutNodeMap>
1.2735 - static CombinedNodeMap<const InNodeMap, OutNodeMap>
1.2736 - combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
1.2737 - return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
1.2738 + template <typename IN, typename OUT>
1.2739 + static CombinedNodeMap<const IN, OUT>
1.2740 + combinedNodeMap(const IN& in_map, OUT& out_map) {
1.2741 + return CombinedNodeMap<const IN, OUT>(in_map, out_map);
1.2742 }
1.2743
1.2744 - template <typename InNodeMap, typename OutNodeMap>
1.2745 - static CombinedNodeMap<InNodeMap, const OutNodeMap>
1.2746 - combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
1.2747 - return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
1.2748 + template <typename IN, typename OUT>
1.2749 + static CombinedNodeMap<IN, const OUT>
1.2750 + combinedNodeMap(IN& in_map, const OUT& out_map) {
1.2751 + return CombinedNodeMap<IN, const OUT>(in_map, out_map);
1.2752 }
1.2753
1.2754 - template <typename InNodeMap, typename OutNodeMap>
1.2755 - static CombinedNodeMap<const InNodeMap, const OutNodeMap>
1.2756 - combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
1.2757 - return CombinedNodeMap<const InNodeMap,
1.2758 - const OutNodeMap>(in_map, out_map);
1.2759 + template <typename IN, typename OUT>
1.2760 + static CombinedNodeMap<const IN, const OUT>
1.2761 + combinedNodeMap(const IN& in_map, const OUT& out_map) {
1.2762 + return CombinedNodeMap<const IN, const OUT>(in_map, out_map);
1.2763 }
1.2764
1.2765 /// \brief Arc map combined from an arc map and a node map of the
1.2766 @@ -3507,30 +3511,31 @@
1.2767 ///
1.2768 /// This map adaptor class adapts an arc map and a node map of the
1.2769 /// original digraph to get an arc map of the split digraph.
1.2770 - /// Its value type is inherited from the original arc map type
1.2771 - /// (\c ArcMap).
1.2772 - template <typename ArcMap, typename NodeMap>
1.2773 + /// Its value type is inherited from the original arc map type (\c AM).
1.2774 + /// \tparam AM The type of the arc map.
1.2775 + /// \tparam NM the type of the node map.
1.2776 + template <typename AM, typename NM>
1.2777 class CombinedArcMap {
1.2778 public:
1.2779
1.2780 /// The key type of the map
1.2781 typedef Arc Key;
1.2782 /// The value type of the map
1.2783 - typedef typename ArcMap::Value Value;
1.2784 -
1.2785 - typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
1.2786 - typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
1.2787 - typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;
1.2788 - typedef typename MapTraits<ArcMap>::ReturnValue Reference;
1.2789 - typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;
1.2790 + typedef typename AM::Value Value;
1.2791 +
1.2792 + typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag;
1.2793 + typedef typename MapTraits<AM>::ReturnValue ReturnValue;
1.2794 + typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue;
1.2795 + typedef typename MapTraits<AM>::ReturnValue Reference;
1.2796 + typedef typename MapTraits<AM>::ConstReturnValue ConstReference;
1.2797
1.2798 /// Constructor
1.2799 - CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
1.2800 + CombinedArcMap(AM& arc_map, NM& node_map)
1.2801 : _arc_map(arc_map), _node_map(node_map) {}
1.2802
1.2803 /// Returns the value associated with the given key.
1.2804 Value operator[](const Key& arc) const {
1.2805 - if (Parent::origArc(arc)) {
1.2806 + if (SplitNodesBase<const DGR>::origArc(arc)) {
1.2807 return _arc_map[arc];
1.2808 } else {
1.2809 return _node_map[arc];
1.2810 @@ -3539,7 +3544,7 @@
1.2811
1.2812 /// Returns a reference to the value associated with the given key.
1.2813 Value& operator[](const Key& arc) {
1.2814 - if (Parent::origArc(arc)) {
1.2815 + if (SplitNodesBase<const DGR>::origArc(arc)) {
1.2816 return _arc_map[arc];
1.2817 } else {
1.2818 return _node_map[arc];
1.2819 @@ -3548,7 +3553,7 @@
1.2820
1.2821 /// Sets the value associated with the given key.
1.2822 void set(const Arc& arc, const Value& val) {
1.2823 - if (Parent::origArc(arc)) {
1.2824 + if (SplitNodesBase<const DGR>::origArc(arc)) {
1.2825 _arc_map.set(arc, val);
1.2826 } else {
1.2827 _node_map.set(arc, val);
1.2828 @@ -3556,8 +3561,10 @@
1.2829 }
1.2830
1.2831 private:
1.2832 - ArcMap& _arc_map;
1.2833 - NodeMap& _node_map;
1.2834 +
1.2835 + AM& _arc_map;
1.2836 + NM& _node_map;
1.2837 +
1.2838 };
1.2839
1.2840 /// \brief Returns a combined arc map
1.2841 @@ -3594,12 +3601,14 @@
1.2842 /// This function just returns a (read-only) \ref SplitNodes adaptor.
1.2843 /// \ingroup graph_adaptors
1.2844 /// \relates SplitNodes
1.2845 - template<typename GR>
1.2846 - SplitNodes<GR>
1.2847 - splitNodes(const GR& digraph) {
1.2848 - return SplitNodes<GR>(digraph);
1.2849 + template<typename DGR>
1.2850 + SplitNodes<DGR>
1.2851 + splitNodes(const DGR& digraph) {
1.2852 + return SplitNodes<DGR>(digraph);
1.2853 }
1.2854
1.2855 +#undef LEMON_SCOPE_FIX
1.2856 +
1.2857 } //namespace lemon
1.2858
1.2859 #endif //LEMON_ADAPTORS_H