diff --git a/lemon/adaptors.h b/lemon/adaptors.h --- a/lemon/adaptors.h +++ b/lemon/adaptors.h @@ -30,29 +30,35 @@ #include #include +#include #include #include namespace lemon { - template +#ifdef _MSC_VER +#define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED +#else +#define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED +#endif + + template class DigraphAdaptorBase { public: - typedef _Digraph Digraph; + typedef DGR Digraph; typedef DigraphAdaptorBase Adaptor; - typedef Digraph ParentDigraph; protected: - Digraph* _digraph; + DGR* _digraph; DigraphAdaptorBase() : _digraph(0) { } - void setDigraph(Digraph& digraph) { _digraph = &digraph; } + void initialize(DGR& digraph) { _digraph = &digraph; } public: - DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { } - - typedef typename Digraph::Node Node; - typedef typename Digraph::Arc Arc; + DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { } + + typedef typename DGR::Node Node; + typedef typename DGR::Arc Arc; void first(Node& i) const { _digraph->first(i); } void first(Arc& i) const { _digraph->first(i); } @@ -67,13 +73,13 @@ Node source(const Arc& a) const { return _digraph->source(a); } Node target(const Arc& a) const { return _digraph->target(a); } - typedef NodeNumTagIndicator NodeNumTag; + typedef NodeNumTagIndicator NodeNumTag; int nodeNum() const { return _digraph->nodeNum(); } - typedef ArcNumTagIndicator ArcNumTag; + typedef ArcNumTagIndicator ArcNumTag; int arcNum() const { return _digraph->arcNum(); } - typedef FindArcTagIndicator FindArcTag; + typedef FindArcTagIndicator FindArcTag; Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const { return _digraph->findArc(u, v, prev); } @@ -95,22 +101,20 @@ int maxNodeId() const { return _digraph->maxNodeId(); } int maxArcId() const { return _digraph->maxArcId(); } - typedef typename ItemSetTraits::ItemNotifier NodeNotifier; + typedef typename ItemSetTraits::ItemNotifier NodeNotifier; NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } - typedef typename ItemSetTraits::ItemNotifier ArcNotifier; + typedef typename ItemSetTraits::ItemNotifier ArcNotifier; ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); } - template - class NodeMap : public Digraph::template NodeMap<_Value> { + template + class NodeMap : public DGR::template NodeMap { + typedef typename DGR::template NodeMap Parent; + public: - - typedef typename Digraph::template NodeMap<_Value> Parent; - explicit NodeMap(const Adaptor& adaptor) : Parent(*adaptor._digraph) {} - - NodeMap(const Adaptor& adaptor, const _Value& value) + NodeMap(const Adaptor& adaptor, const V& value) : Parent(*adaptor._digraph, value) { } private: @@ -126,16 +130,14 @@ }; - template - class ArcMap : public Digraph::template ArcMap<_Value> { + template + class ArcMap : public DGR::template ArcMap { + typedef typename DGR::template ArcMap Parent; + public: - - typedef typename Digraph::template ArcMap<_Value> Parent; - - explicit ArcMap(const Adaptor& adaptor) + explicit ArcMap(const DigraphAdaptorBase& adaptor) : Parent(*adaptor._digraph) {} - - ArcMap(const Adaptor& adaptor, const _Value& value) + ArcMap(const DigraphAdaptorBase& adaptor, const V& value) : Parent(*adaptor._digraph, value) {} private: @@ -153,25 +155,24 @@ }; - template + template class GraphAdaptorBase { public: - typedef _Graph Graph; - typedef Graph ParentGraph; + typedef GR Graph; protected: - Graph* _graph; + GR* _graph; GraphAdaptorBase() : _graph(0) {} - void setGraph(Graph& graph) { _graph = &graph; } + void initialize(GR& graph) { _graph = &graph; } public: - GraphAdaptorBase(Graph& graph) : _graph(&graph) {} - - typedef typename Graph::Node Node; - typedef typename Graph::Arc Arc; - typedef typename Graph::Edge Edge; + GraphAdaptorBase(GR& graph) : _graph(&graph) {} + + typedef typename GR::Node Node; + typedef typename GR::Arc Arc; + typedef typename GR::Edge Edge; void first(Node& i) const { _graph->first(i); } void first(Arc& i) const { _graph->first(i); } @@ -239,22 +240,23 @@ int maxArcId() const { return _graph->maxArcId(); } int maxEdgeId() const { return _graph->maxEdgeId(); } - typedef typename ItemSetTraits::ItemNotifier NodeNotifier; + typedef typename ItemSetTraits::ItemNotifier NodeNotifier; NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } - typedef typename ItemSetTraits::ItemNotifier ArcNotifier; + typedef typename ItemSetTraits::ItemNotifier ArcNotifier; ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } - typedef typename ItemSetTraits::ItemNotifier EdgeNotifier; + typedef typename ItemSetTraits::ItemNotifier EdgeNotifier; EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); } - template - class NodeMap : public Graph::template NodeMap<_Value> { + template + class NodeMap : public GR::template NodeMap { + typedef typename GR::template NodeMap Parent; + public: - typedef typename Graph::template NodeMap<_Value> Parent; - explicit NodeMap(const GraphAdaptorBase& adapter) + explicit NodeMap(const GraphAdaptorBase& adapter) : Parent(*adapter._graph) {} - NodeMap(const GraphAdaptorBase& adapter, const _Value& value) + NodeMap(const GraphAdaptorBase& adapter, const V& value) : Parent(*adapter._graph, value) {} private: @@ -270,13 +272,14 @@ }; - template - class ArcMap : public Graph::template ArcMap<_Value> { + template + class ArcMap : public GR::template ArcMap { + typedef typename GR::template ArcMap Parent; + public: - typedef typename Graph::template ArcMap<_Value> Parent; - explicit ArcMap(const GraphAdaptorBase& adapter) + explicit ArcMap(const GraphAdaptorBase& adapter) : Parent(*adapter._graph) {} - ArcMap(const GraphAdaptorBase& adapter, const _Value& value) + ArcMap(const GraphAdaptorBase& adapter, const V& value) : Parent(*adapter._graph, value) {} private: @@ -291,13 +294,14 @@ } }; - template - class EdgeMap : public Graph::template EdgeMap<_Value> { + template + class EdgeMap : public GR::template EdgeMap { + typedef typename GR::template EdgeMap Parent; + public: - typedef typename Graph::template EdgeMap<_Value> Parent; - explicit EdgeMap(const GraphAdaptorBase& adapter) + explicit EdgeMap(const GraphAdaptorBase& adapter) : Parent(*adapter._graph) {} - EdgeMap(const GraphAdaptorBase& adapter, const _Value& value) + EdgeMap(const GraphAdaptorBase& adapter, const V& value) : Parent(*adapter._graph, value) {} private: @@ -314,11 +318,11 @@ }; - template - class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> { + template + class ReverseDigraphBase : public DigraphAdaptorBase { + typedef DigraphAdaptorBase Parent; public: - typedef _Digraph Digraph; - typedef DigraphAdaptorBase<_Digraph> Parent; + typedef DGR Digraph; protected: ReverseDigraphBase() : Parent() { } public: @@ -336,7 +340,7 @@ Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); } - typedef FindArcTagIndicator FindArcTag; + typedef FindArcTagIndicator FindArcTag; Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const { return Parent::findArc(v, u, prev); @@ -356,23 +360,23 @@ /// by adding or removing nodes or arcs, unless the \c GR template /// parameter is set to be \c const. /// - /// \tparam GR The type of the adapted digraph. + /// \tparam DGR The type of the adapted digraph. /// It must conform to the \ref concepts::Digraph "Digraph" concept. /// It can also be specified to be \c const. /// /// \note The \c Node and \c Arc types of this adaptor and the adapted /// digraph are convertible to each other. - template + template #ifdef DOXYGEN class ReverseDigraph { #else class ReverseDigraph : - public DigraphAdaptorExtender > { + public DigraphAdaptorExtender > { #endif + typedef DigraphAdaptorExtender > Parent; public: /// The type of the adapted digraph. - typedef GR Digraph; - typedef DigraphAdaptorExtender > Parent; + typedef DGR Digraph; protected: ReverseDigraph() { } public: @@ -380,8 +384,8 @@ /// \brief Constructor /// /// Creates a reverse digraph adaptor for the given digraph. - explicit ReverseDigraph(Digraph& digraph) { - Parent::setDigraph(digraph); + explicit ReverseDigraph(DGR& digraph) { + Parent::initialize(digraph); } }; @@ -390,33 +394,31 @@ /// This function just returns a read-only \ref ReverseDigraph adaptor. /// \ingroup graph_adaptors /// \relates ReverseDigraph - template - ReverseDigraph reverseDigraph(const GR& digraph) { - return ReverseDigraph(digraph); + template + ReverseDigraph reverseDigraph(const DGR& digraph) { + return ReverseDigraph(digraph); } - template - class SubDigraphBase : public DigraphAdaptorBase<_Digraph> { + template + class SubDigraphBase : public DigraphAdaptorBase { + typedef DigraphAdaptorBase Parent; public: - typedef _Digraph Digraph; - typedef _NodeFilterMap NodeFilterMap; - typedef _ArcFilterMap ArcFilterMap; + typedef DGR Digraph; + typedef NF NodeFilterMap; + typedef AF ArcFilterMap; typedef SubDigraphBase Adaptor; - typedef DigraphAdaptorBase<_Digraph> Parent; protected: - NodeFilterMap* _node_filter; - ArcFilterMap* _arc_filter; + NF* _node_filter; + AF* _arc_filter; SubDigraphBase() : Parent(), _node_filter(0), _arc_filter(0) { } - void setNodeFilterMap(NodeFilterMap& node_filter) { + void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) { + Parent::initialize(digraph); _node_filter = &node_filter; - } - void setArcFilterMap(ArcFilterMap& arc_filter) { - _arc_filter = &arc_filter; + _arc_filter = &arc_filter; } public: @@ -487,7 +489,7 @@ typedef False NodeNumTag; typedef False ArcNumTag; - typedef FindArcTagIndicator FindArcTag; + typedef FindArcTagIndicator FindArcTag; Arc findArc(const Node& source, const Node& target, const Arc& prev = INVALID) const { if (!(*_node_filter)[source] || !(*_node_filter)[target]) { @@ -500,18 +502,22 @@ return arc; } - template - class NodeMap : public SubMapExtender > { + public: + + template + class NodeMap + : public SubMapExtender, + LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> { + typedef SubMapExtender, + LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent; + public: - typedef _Value Value; - typedef SubMapExtender > MapParent; - - NodeMap(const Adaptor& adaptor) - : MapParent(adaptor) {} - NodeMap(const Adaptor& adaptor, const Value& value) - : MapParent(adaptor, value) {} + typedef V Value; + + NodeMap(const SubDigraphBase& adaptor) + : Parent(adaptor) {} + NodeMap(const SubDigraphBase& adaptor, const V& value) + : Parent(adaptor, value) {} private: NodeMap& operator=(const NodeMap& cmap) { @@ -520,23 +526,25 @@ template NodeMap& operator=(const CMap& cmap) { - MapParent::operator=(cmap); + Parent::operator=(cmap); return *this; } }; - template - class ArcMap : public SubMapExtender > { + template + class ArcMap + : public SubMapExtender, + LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> { + typedef SubMapExtender, + LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> Parent; + public: - typedef _Value Value; - typedef SubMapExtender > MapParent; - - ArcMap(const Adaptor& adaptor) - : MapParent(adaptor) {} - ArcMap(const Adaptor& adaptor, const Value& value) - : MapParent(adaptor, value) {} + typedef V Value; + + ArcMap(const SubDigraphBase& adaptor) + : Parent(adaptor) {} + ArcMap(const SubDigraphBase& adaptor, const V& value) + : Parent(adaptor, value) {} private: ArcMap& operator=(const ArcMap& cmap) { @@ -545,34 +553,33 @@ template ArcMap& operator=(const CMap& cmap) { - MapParent::operator=(cmap); + Parent::operator=(cmap); return *this; } }; }; - template - class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false> - : public DigraphAdaptorBase<_Digraph> { + template + class SubDigraphBase + : public DigraphAdaptorBase { + typedef DigraphAdaptorBase Parent; public: - typedef _Digraph Digraph; - typedef _NodeFilterMap NodeFilterMap; - typedef _ArcFilterMap ArcFilterMap; + typedef DGR Digraph; + typedef NF NodeFilterMap; + typedef AF ArcFilterMap; typedef SubDigraphBase Adaptor; - typedef DigraphAdaptorBase Parent; protected: - NodeFilterMap* _node_filter; - ArcFilterMap* _arc_filter; + NF* _node_filter; + AF* _arc_filter; SubDigraphBase() : Parent(), _node_filter(0), _arc_filter(0) { } - void setNodeFilterMap(NodeFilterMap& node_filter) { + void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) { + Parent::initialize(digraph); _node_filter = &node_filter; - } - void setArcFilterMap(ArcFilterMap& arc_filter) { - _arc_filter = &arc_filter; + _arc_filter = &arc_filter; } public: @@ -627,7 +634,7 @@ typedef False NodeNumTag; typedef False ArcNumTag; - typedef FindArcTagIndicator FindArcTag; + typedef FindArcTagIndicator FindArcTag; Arc findArc(const Node& source, const Node& target, const Arc& prev = INVALID) const { if (!(*_node_filter)[source] || !(*_node_filter)[target]) { @@ -640,18 +647,20 @@ return arc; } - template - class NodeMap : public SubMapExtender > { + template + class NodeMap + : public SubMapExtender, + LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> { + typedef SubMapExtender, + LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent; + public: - typedef _Value Value; - typedef SubMapExtender > MapParent; - - NodeMap(const Adaptor& adaptor) - : MapParent(adaptor) {} - NodeMap(const Adaptor& adaptor, const Value& value) - : MapParent(adaptor, value) {} + typedef V Value; + + NodeMap(const SubDigraphBase& adaptor) + : Parent(adaptor) {} + NodeMap(const SubDigraphBase& adaptor, const V& value) + : Parent(adaptor, value) {} private: NodeMap& operator=(const NodeMap& cmap) { @@ -660,23 +669,25 @@ template NodeMap& operator=(const CMap& cmap) { - MapParent::operator=(cmap); + Parent::operator=(cmap); return *this; } }; - template - class ArcMap : public SubMapExtender > { + template + class ArcMap + : public SubMapExtender, + LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> { + typedef SubMapExtender, + LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> Parent; + public: - typedef _Value Value; - typedef SubMapExtender > MapParent; - - ArcMap(const Adaptor& adaptor) - : MapParent(adaptor) {} - ArcMap(const Adaptor& adaptor, const Value& value) - : MapParent(adaptor, value) {} + typedef V Value; + + ArcMap(const SubDigraphBase& adaptor) + : Parent(adaptor) {} + ArcMap(const SubDigraphBase& adaptor, const V& value) + : Parent(adaptor, value) {} private: ArcMap& operator=(const ArcMap& cmap) { @@ -685,7 +696,7 @@ template ArcMap& operator=(const CMap& cmap) { - MapParent::operator=(cmap); + Parent::operator=(cmap); return *this; } }; @@ -708,17 +719,17 @@ /// by adding or removing nodes or arcs, unless the \c GR template /// parameter is set to be \c const. /// - /// \tparam GR The type of the adapted digraph. + /// \tparam DGR The type of the adapted digraph. /// It must conform to the \ref concepts::Digraph "Digraph" concept. /// It can also be specified to be \c const. /// \tparam NF The type of the node filter map. /// It must be a \c bool (or convertible) node map of the /// adapted digraph. The default type is - /// \ref concepts::Digraph::NodeMap "GR::NodeMap". + /// \ref concepts::Digraph::NodeMap "DGR::NodeMap". /// \tparam AF The type of the arc filter map. /// It must be \c bool (or convertible) arc map of the /// adapted digraph. The default type is - /// \ref concepts::Digraph::ArcMap "GR::ArcMap". + /// \ref concepts::Digraph::ArcMap "DGR::ArcMap". /// /// \note The \c Node and \c Arc types of this adaptor and the adapted /// digraph are convertible to each other. @@ -726,24 +737,24 @@ /// \see FilterNodes /// \see FilterArcs #ifdef DOXYGEN - template + template class SubDigraph { #else - template, - typename AF = typename GR::template ArcMap > + template, + typename AF = typename DGR::template ArcMap > class SubDigraph : - public DigraphAdaptorExtender > { + public DigraphAdaptorExtender > { #endif public: /// The type of the adapted digraph. - typedef GR Digraph; + typedef DGR Digraph; /// The type of the node filter map. typedef NF NodeFilterMap; /// The type of the arc filter map. typedef AF ArcFilterMap; - typedef DigraphAdaptorExtender > + typedef DigraphAdaptorExtender > Parent; typedef typename Parent::Node Node; @@ -757,11 +768,8 @@ /// /// Creates a subdigraph for the given digraph with the /// given node and arc filter maps. - SubDigraph(Digraph& digraph, NodeFilterMap& node_filter, - ArcFilterMap& arc_filter) { - setDigraph(digraph); - setNodeFilterMap(node_filter); - setArcFilterMap(arc_filter); + SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) { + Parent::initialize(digraph, node_filter, arc_filter); } /// \brief Sets the status of the given node @@ -823,62 +831,60 @@ /// This function just returns a read-only \ref SubDigraph adaptor. /// \ingroup graph_adaptors /// \relates SubDigraph - template - SubDigraph - subDigraph(const GR& digraph, - NF& node_filter_map, AF& arc_filter_map) { - return SubDigraph - (digraph, node_filter_map, arc_filter_map); + template + SubDigraph + subDigraph(const DGR& digraph, + NF& node_filter, AF& arc_filter) { + return SubDigraph + (digraph, node_filter, arc_filter); } - template - SubDigraph - subDigraph(const GR& digraph, - const NF& node_filter_map, AF& arc_filter_map) { - return SubDigraph - (digraph, node_filter_map, arc_filter_map); + template + SubDigraph + subDigraph(const DGR& digraph, + const NF& node_filter, AF& arc_filter) { + return SubDigraph + (digraph, node_filter, arc_filter); } - template - SubDigraph - subDigraph(const GR& digraph, - NF& node_filter_map, const AF& arc_filter_map) { - return SubDigraph - (digraph, node_filter_map, arc_filter_map); + template + SubDigraph + subDigraph(const DGR& digraph, + NF& node_filter, const AF& arc_filter) { + return SubDigraph + (digraph, node_filter, arc_filter); } - template - SubDigraph - subDigraph(const GR& digraph, - const NF& node_filter_map, const AF& arc_filter_map) { - return SubDigraph - (digraph, node_filter_map, arc_filter_map); + template + SubDigraph + subDigraph(const DGR& digraph, + const NF& node_filter, const AF& arc_filter) { + return SubDigraph + (digraph, node_filter, arc_filter); } - template - class SubGraphBase : public GraphAdaptorBase<_Graph> { + template + class SubGraphBase : public GraphAdaptorBase { + typedef GraphAdaptorBase Parent; public: - typedef _Graph Graph; - typedef _NodeFilterMap NodeFilterMap; - typedef _EdgeFilterMap EdgeFilterMap; + typedef GR Graph; + typedef NF NodeFilterMap; + typedef EF EdgeFilterMap; typedef SubGraphBase Adaptor; - typedef GraphAdaptorBase<_Graph> Parent; protected: - NodeFilterMap* _node_filter_map; - EdgeFilterMap* _edge_filter_map; + NF* _node_filter; + EF* _edge_filter; SubGraphBase() - : Parent(), _node_filter_map(0), _edge_filter_map(0) { } - - void setNodeFilterMap(NodeFilterMap& node_filter_map) { - _node_filter_map=&node_filter_map; - } - void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) { - _edge_filter_map=&edge_filter_map; + : Parent(), _node_filter(0), _edge_filter(0) { } + + void initialize(GR& graph, NF& node_filter, EF& edge_filter) { + Parent::initialize(graph); + _node_filter = &node_filter; + _edge_filter = &edge_filter; } public: @@ -889,95 +895,95 @@ void first(Node& i) const { Parent::first(i); - while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); } void first(Arc& i) const { Parent::first(i); - while (i!=INVALID && (!(*_edge_filter_map)[i] - || !(*_node_filter_map)[Parent::source(i)] - || !(*_node_filter_map)[Parent::target(i)])) + while (i!=INVALID && (!(*_edge_filter)[i] + || !(*_node_filter)[Parent::source(i)] + || !(*_node_filter)[Parent::target(i)])) Parent::next(i); } void first(Edge& i) const { Parent::first(i); - while (i!=INVALID && (!(*_edge_filter_map)[i] - || !(*_node_filter_map)[Parent::u(i)] - || !(*_node_filter_map)[Parent::v(i)])) + while (i!=INVALID && (!(*_edge_filter)[i] + || !(*_node_filter)[Parent::u(i)] + || !(*_node_filter)[Parent::v(i)])) Parent::next(i); } void firstIn(Arc& i, const Node& n) const { Parent::firstIn(i, n); - while (i!=INVALID && (!(*_edge_filter_map)[i] - || !(*_node_filter_map)[Parent::source(i)])) + while (i!=INVALID && (!(*_edge_filter)[i] + || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i); } void firstOut(Arc& i, const Node& n) const { Parent::firstOut(i, n); - while (i!=INVALID && (!(*_edge_filter_map)[i] - || !(*_node_filter_map)[Parent::target(i)])) + while (i!=INVALID && (!(*_edge_filter)[i] + || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i); } void firstInc(Edge& i, bool& d, const Node& n) const { Parent::firstInc(i, d, n); - while (i!=INVALID && (!(*_edge_filter_map)[i] - || !(*_node_filter_map)[Parent::u(i)] - || !(*_node_filter_map)[Parent::v(i)])) + while (i!=INVALID && (!(*_edge_filter)[i] + || !(*_node_filter)[Parent::u(i)] + || !(*_node_filter)[Parent::v(i)])) Parent::nextInc(i, d); } void next(Node& i) const { Parent::next(i); - while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); } void next(Arc& i) const { Parent::next(i); - while (i!=INVALID && (!(*_edge_filter_map)[i] - || !(*_node_filter_map)[Parent::source(i)] - || !(*_node_filter_map)[Parent::target(i)])) + while (i!=INVALID && (!(*_edge_filter)[i] + || !(*_node_filter)[Parent::source(i)] + || !(*_node_filter)[Parent::target(i)])) Parent::next(i); } void next(Edge& i) const { Parent::next(i); - while (i!=INVALID && (!(*_edge_filter_map)[i] - || !(*_node_filter_map)[Parent::u(i)] - || !(*_node_filter_map)[Parent::v(i)])) + while (i!=INVALID && (!(*_edge_filter)[i] + || !(*_node_filter)[Parent::u(i)] + || !(*_node_filter)[Parent::v(i)])) Parent::next(i); } void nextIn(Arc& i) const { Parent::nextIn(i); - while (i!=INVALID && (!(*_edge_filter_map)[i] - || !(*_node_filter_map)[Parent::source(i)])) + while (i!=INVALID && (!(*_edge_filter)[i] + || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i); } void nextOut(Arc& i) const { Parent::nextOut(i); - while (i!=INVALID && (!(*_edge_filter_map)[i] - || !(*_node_filter_map)[Parent::target(i)])) + while (i!=INVALID && (!(*_edge_filter)[i] + || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i); } void nextInc(Edge& i, bool& d) const { Parent::nextInc(i, d); - while (i!=INVALID && (!(*_edge_filter_map)[i] - || !(*_node_filter_map)[Parent::u(i)] - || !(*_node_filter_map)[Parent::v(i)])) + while (i!=INVALID && (!(*_edge_filter)[i] + || !(*_node_filter)[Parent::u(i)] + || !(*_node_filter)[Parent::v(i)])) Parent::nextInc(i, d); } - void status(const Node& n, bool v) const { _node_filter_map->set(n, v); } - void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); } - - bool status(const Node& n) const { return (*_node_filter_map)[n]; } - bool status(const Edge& e) const { return (*_edge_filter_map)[e]; } + void status(const Node& n, bool v) const { _node_filter->set(n, v); } + void status(const Edge& e, bool v) const { _edge_filter->set(e, v); } + + bool status(const Node& n) const { return (*_node_filter)[n]; } + bool status(const Edge& e) const { return (*_edge_filter)[e]; } typedef False NodeNumTag; typedef False ArcNumTag; @@ -986,11 +992,11 @@ typedef FindArcTagIndicator FindArcTag; Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const { - if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) { + if (!(*_node_filter)[u] || !(*_node_filter)[v]) { return INVALID; } Arc arc = Parent::findArc(u, v, prev); - while (arc != INVALID && !(*_edge_filter_map)[arc]) { + while (arc != INVALID && !(*_edge_filter)[arc]) { arc = Parent::findArc(u, v, arc); } return arc; @@ -999,28 +1005,30 @@ typedef FindEdgeTagIndicator FindEdgeTag; Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) const { - if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) { + if (!(*_node_filter)[u] || !(*_node_filter)[v]) { return INVALID; } Edge edge = Parent::findEdge(u, v, prev); - while (edge != INVALID && !(*_edge_filter_map)[edge]) { + while (edge != INVALID && !(*_edge_filter)[edge]) { edge = Parent::findEdge(u, v, edge); } return edge; } - template - class NodeMap : public SubMapExtender > { + template + class NodeMap + : public SubMapExtender, + LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> { + typedef SubMapExtender, + LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent; + public: - typedef _Value Value; - typedef SubMapExtender > MapParent; - - NodeMap(const Adaptor& adaptor) - : MapParent(adaptor) {} - NodeMap(const Adaptor& adaptor, const Value& value) - : MapParent(adaptor, value) {} + typedef V Value; + + NodeMap(const SubGraphBase& adaptor) + : Parent(adaptor) {} + NodeMap(const SubGraphBase& adaptor, const V& value) + : Parent(adaptor, value) {} private: NodeMap& operator=(const NodeMap& cmap) { @@ -1029,23 +1037,25 @@ template NodeMap& operator=(const CMap& cmap) { - MapParent::operator=(cmap); + Parent::operator=(cmap); return *this; } }; - template - class ArcMap : public SubMapExtender > { + template + class ArcMap + : public SubMapExtender, + LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> { + typedef SubMapExtender, + LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent; + public: - typedef _Value Value; - typedef SubMapExtender > MapParent; - - ArcMap(const Adaptor& adaptor) - : MapParent(adaptor) {} - ArcMap(const Adaptor& adaptor, const Value& value) - : MapParent(adaptor, value) {} + typedef V Value; + + ArcMap(const SubGraphBase& adaptor) + : Parent(adaptor) {} + ArcMap(const SubGraphBase& adaptor, const V& value) + : Parent(adaptor, value) {} private: ArcMap& operator=(const ArcMap& cmap) { @@ -1054,24 +1064,26 @@ template ArcMap& operator=(const CMap& cmap) { - MapParent::operator=(cmap); + Parent::operator=(cmap); return *this; } }; - template - class EdgeMap : public SubMapExtender > { + template + class EdgeMap + : public SubMapExtender, + LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> { + typedef SubMapExtender, + LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent; + public: - typedef _Value Value; - typedef SubMapExtender > MapParent; - - EdgeMap(const Adaptor& adaptor) - : MapParent(adaptor) {} - - EdgeMap(const Adaptor& adaptor, const Value& value) - : MapParent(adaptor, value) {} + typedef V Value; + + EdgeMap(const SubGraphBase& adaptor) + : Parent(adaptor) {} + + EdgeMap(const SubGraphBase& adaptor, const V& value) + : Parent(adaptor, value) {} private: EdgeMap& operator=(const EdgeMap& cmap) { @@ -1080,34 +1092,33 @@ template EdgeMap& operator=(const CMap& cmap) { - MapParent::operator=(cmap); + Parent::operator=(cmap); return *this; } }; }; - template - class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false> - : public GraphAdaptorBase<_Graph> { + template + class SubGraphBase + : public GraphAdaptorBase { + typedef GraphAdaptorBase Parent; public: - typedef _Graph Graph; - typedef _NodeFilterMap NodeFilterMap; - typedef _EdgeFilterMap EdgeFilterMap; + typedef GR Graph; + typedef NF NodeFilterMap; + typedef EF EdgeFilterMap; typedef SubGraphBase Adaptor; - typedef GraphAdaptorBase<_Graph> Parent; protected: - NodeFilterMap* _node_filter_map; - EdgeFilterMap* _edge_filter_map; - SubGraphBase() : Parent(), - _node_filter_map(0), _edge_filter_map(0) { } - - void setNodeFilterMap(NodeFilterMap& node_filter_map) { - _node_filter_map=&node_filter_map; - } - void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) { - _edge_filter_map=&edge_filter_map; + NF* _node_filter; + EF* _edge_filter; + SubGraphBase() + : Parent(), _node_filter(0), _edge_filter(0) { } + + void initialize(GR& graph, NF& node_filter, EF& edge_filter) { + Parent::initialize(graph); + _node_filter = &node_filter; + _edge_filter = &edge_filter; } public: @@ -1118,65 +1129,65 @@ void first(Node& i) const { Parent::first(i); - while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); } void first(Arc& i) const { Parent::first(i); - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); + while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); } void first(Edge& i) const { Parent::first(i); - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); + while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); } void firstIn(Arc& i, const Node& n) const { Parent::firstIn(i, n); - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); + while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i); } void firstOut(Arc& i, const Node& n) const { Parent::firstOut(i, n); - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); + while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i); } void firstInc(Edge& i, bool& d, const Node& n) const { Parent::firstInc(i, d, n); - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); + while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d); } void next(Node& i) const { Parent::next(i); - while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); } void next(Arc& i) const { Parent::next(i); - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); + while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); } void next(Edge& i) const { Parent::next(i); - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); + while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); } void nextIn(Arc& i) const { Parent::nextIn(i); - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); + while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i); } void nextOut(Arc& i) const { Parent::nextOut(i); - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); + while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i); } void nextInc(Edge& i, bool& d) const { Parent::nextInc(i, d); - while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); + while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d); } - void status(const Node& n, bool v) const { _node_filter_map->set(n, v); } - void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); } - - bool status(const Node& n) const { return (*_node_filter_map)[n]; } - bool status(const Edge& e) const { return (*_edge_filter_map)[e]; } + void status(const Node& n, bool v) const { _node_filter->set(n, v); } + void status(const Edge& e, bool v) const { _edge_filter->set(e, v); } + + bool status(const Node& n) const { return (*_node_filter)[n]; } + bool status(const Edge& e) const { return (*_edge_filter)[e]; } typedef False NodeNumTag; typedef False ArcNumTag; @@ -1186,7 +1197,7 @@ Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const { Arc arc = Parent::findArc(u, v, prev); - while (arc != INVALID && !(*_edge_filter_map)[arc]) { + while (arc != INVALID && !(*_edge_filter)[arc]) { arc = Parent::findArc(u, v, arc); } return arc; @@ -1196,24 +1207,26 @@ Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) const { Edge edge = Parent::findEdge(u, v, prev); - while (edge != INVALID && !(*_edge_filter_map)[edge]) { + while (edge != INVALID && !(*_edge_filter)[edge]) { edge = Parent::findEdge(u, v, edge); } return edge; } - template - class NodeMap : public SubMapExtender > { + template + class NodeMap + : public SubMapExtender, + LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> { + typedef SubMapExtender, + LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent; + public: - typedef _Value Value; - typedef SubMapExtender > MapParent; - - NodeMap(const Adaptor& adaptor) - : MapParent(adaptor) {} - NodeMap(const Adaptor& adaptor, const Value& value) - : MapParent(adaptor, value) {} + typedef V Value; + + NodeMap(const SubGraphBase& adaptor) + : Parent(adaptor) {} + NodeMap(const SubGraphBase& adaptor, const V& value) + : Parent(adaptor, value) {} private: NodeMap& operator=(const NodeMap& cmap) { @@ -1222,23 +1235,25 @@ template NodeMap& operator=(const CMap& cmap) { - MapParent::operator=(cmap); + Parent::operator=(cmap); return *this; } }; - template - class ArcMap : public SubMapExtender > { + template + class ArcMap + : public SubMapExtender, + LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> { + typedef SubMapExtender, + LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent; + public: - typedef _Value Value; - typedef SubMapExtender > MapParent; - - ArcMap(const Adaptor& adaptor) - : MapParent(adaptor) {} - ArcMap(const Adaptor& adaptor, const Value& value) - : MapParent(adaptor, value) {} + typedef V Value; + + ArcMap(const SubGraphBase& adaptor) + : Parent(adaptor) {} + ArcMap(const SubGraphBase& adaptor, const V& value) + : Parent(adaptor, value) {} private: ArcMap& operator=(const ArcMap& cmap) { @@ -1247,24 +1262,26 @@ template ArcMap& operator=(const CMap& cmap) { - MapParent::operator=(cmap); + Parent::operator=(cmap); return *this; } }; - template - class EdgeMap : public SubMapExtender > { + template + class EdgeMap + : public SubMapExtender, + LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> { + typedef SubMapExtender, + LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent; + public: - typedef _Value Value; - typedef SubMapExtender > MapParent; - - EdgeMap(const Adaptor& adaptor) - : MapParent(adaptor) {} - - EdgeMap(const Adaptor& adaptor, const _Value& value) - : MapParent(adaptor, value) {} + typedef V Value; + + EdgeMap(const SubGraphBase& adaptor) + : Parent(adaptor) {} + + EdgeMap(const SubGraphBase& adaptor, const V& value) + : Parent(adaptor, value) {} private: EdgeMap& operator=(const EdgeMap& cmap) { @@ -1273,7 +1290,7 @@ template EdgeMap& operator=(const CMap& cmap) { - MapParent::operator=(cmap); + Parent::operator=(cmap); return *this; } }; @@ -1332,7 +1349,7 @@ /// The type of the edge filter map. typedef EF EdgeFilterMap; - typedef GraphAdaptorExtender< SubGraphBase > + typedef GraphAdaptorExtender > Parent; typedef typename Parent::Node Node; @@ -1346,11 +1363,8 @@ /// /// Creates a subgraph for the given graph with the given node /// and edge filter maps. - SubGraph(Graph& graph, NodeFilterMap& node_filter_map, - EdgeFilterMap& edge_filter_map) { - setGraph(graph); - setNodeFilterMap(node_filter_map); - setEdgeFilterMap(edge_filter_map); + SubGraph(GR& graph, NF& node_filter, EF& edge_filter) { + initialize(graph, node_filter, edge_filter); } /// \brief Sets the status of the given node @@ -1414,34 +1428,30 @@ /// \relates SubGraph template SubGraph - subGraph(const GR& graph, - NF& node_filter_map, EF& edge_filter_map) { + subGraph(const GR& graph, NF& node_filter, EF& edge_filter) { return SubGraph - (graph, node_filter_map, edge_filter_map); + (graph, node_filter, edge_filter); } template SubGraph - subGraph(const GR& graph, - const NF& node_filter_map, EF& edge_filter_map) { + subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) { return SubGraph - (graph, node_filter_map, edge_filter_map); + (graph, node_filter, edge_filter); } template SubGraph - subGraph(const GR& graph, - NF& node_filter_map, const EF& edge_filter_map) { + subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) { return SubGraph - (graph, node_filter_map, edge_filter_map); + (graph, node_filter, edge_filter); } template SubGraph - subGraph(const GR& graph, - const NF& node_filter_map, const EF& edge_filter_map) { + subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) { return SubGraph - (graph, node_filter_map, edge_filter_map); + (graph, node_filter, edge_filter); } @@ -1481,25 +1491,24 @@ typename Enable = void> class FilterNodes : public DigraphAdaptorExtender< - SubDigraphBase, true> > { + SubDigraphBase >, + true> > { #endif + typedef DigraphAdaptorExtender< + SubDigraphBase >, + true> > Parent; + public: typedef GR Digraph; typedef NF NodeFilterMap; - typedef DigraphAdaptorExtender< - SubDigraphBase, true> > - Parent; - typedef typename Parent::Node Node; protected: - ConstMap const_true_map; - - FilterNodes() : const_true_map(true) { - Parent::setArcFilterMap(const_true_map); - } + ConstMap > const_true_map; + + FilterNodes() : const_true_map() {} public: @@ -1507,12 +1516,10 @@ /// /// Creates a subgraph for the given digraph or graph with the /// given node filter map. - FilterNodes(GR& graph, NodeFilterMap& node_filter) : - Parent(), const_true_map(true) + FilterNodes(GR& graph, NF& node_filter) + : Parent(), const_true_map() { - Parent::setDigraph(graph); - Parent::setNodeFilterMap(node_filter); - Parent::setArcFilterMap(const_true_map); + Parent::initialize(graph, node_filter, const_true_map); } /// \brief Sets the status of the given node @@ -1547,30 +1554,30 @@ class FilterNodes >::type> : public GraphAdaptorExtender< - SubGraphBase, true> > { + SubGraphBase >, + true> > { + + typedef GraphAdaptorExtender< + SubGraphBase >, + true> > Parent; public: + typedef GR Graph; typedef NF NodeFilterMap; - typedef GraphAdaptorExtender< - SubGraphBase, true> > - Parent; typedef typename Parent::Node Node; + protected: - ConstMap const_true_map; - - FilterNodes() : const_true_map(true) { - Parent::setEdgeFilterMap(const_true_map); - } + ConstMap > const_true_map; + + FilterNodes() : const_true_map() {} public: - FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) : - Parent(), const_true_map(true) { - Parent::setGraph(_graph); - Parent::setNodeFilterMap(node_filter_map); - Parent::setEdgeFilterMap(const_true_map); + FilterNodes(GR& graph, NodeFilterMap& node_filter) : + Parent(), const_true_map() { + Parent::initialize(graph, node_filter, const_true_map); } void status(const Node& n, bool v) const { Parent::status(n, v); } @@ -1588,14 +1595,14 @@ /// \relates FilterNodes template FilterNodes - filterNodes(const GR& graph, NF& node_filter_map) { - return FilterNodes(graph, node_filter_map); + filterNodes(const GR& graph, NF& node_filter) { + return FilterNodes(graph, node_filter); } template FilterNodes - filterNodes(const GR& graph, const NF& node_filter_map) { - return FilterNodes(graph, node_filter_map); + filterNodes(const GR& graph, const NF& node_filter) { + return FilterNodes(graph, node_filter); } /// \ingroup graph_adaptors @@ -1612,45 +1619,45 @@ /// by adding or removing nodes or arcs, unless the \c GR template /// parameter is set to be \c const. /// - /// \tparam GR The type of the adapted digraph. + /// \tparam DGR The type of the adapted digraph. /// It must conform to the \ref concepts::Digraph "Digraph" concept. /// It can also be specified to be \c const. /// \tparam AF The type of the arc filter map. /// It must be a \c bool (or convertible) arc map of the /// adapted digraph. The default type is - /// \ref concepts::Digraph::ArcMap "GR::ArcMap". + /// \ref concepts::Digraph::ArcMap "DGR::ArcMap". /// /// \note The \c Node and \c Arc types of this adaptor and the adapted /// digraph are convertible to each other. #ifdef DOXYGEN - template class FilterArcs { #else - template > + template > class FilterArcs : public DigraphAdaptorExtender< - SubDigraphBase, AF, false> > { + SubDigraphBase >, + AF, false> > { #endif + typedef DigraphAdaptorExtender< + SubDigraphBase >, + AF, false> > Parent; + public: + /// The type of the adapted digraph. - typedef GR Digraph; + typedef DGR Digraph; /// The type of the arc filter map. typedef AF ArcFilterMap; - typedef DigraphAdaptorExtender< - SubDigraphBase, AF, false> > - Parent; - typedef typename Parent::Arc Arc; protected: - ConstMap const_true_map; - - FilterArcs() : const_true_map(true) { - Parent::setNodeFilterMap(const_true_map); - } + ConstMap > const_true_map; + + FilterArcs() : const_true_map() {} public: @@ -1658,11 +1665,9 @@ /// /// Creates a subdigraph for the given digraph with the given arc /// filter map. - FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter) - : Parent(), const_true_map(true) { - Parent::setDigraph(digraph); - Parent::setNodeFilterMap(const_true_map); - Parent::setArcFilterMap(arc_filter); + FilterArcs(DGR& digraph, ArcFilterMap& arc_filter) + : Parent(), const_true_map() { + Parent::initialize(digraph, const_true_map, arc_filter); } /// \brief Sets the status of the given arc @@ -1698,16 +1703,16 @@ /// This function just returns a read-only \ref FilterArcs adaptor. /// \ingroup graph_adaptors /// \relates FilterArcs - template - FilterArcs - filterArcs(const GR& digraph, AF& arc_filter_map) { - return FilterArcs(digraph, arc_filter_map); + template + FilterArcs + filterArcs(const DGR& digraph, AF& arc_filter) { + return FilterArcs(digraph, arc_filter); } - template - FilterArcs - filterArcs(const GR& digraph, const AF& arc_filter_map) { - return FilterArcs(digraph, arc_filter_map); + template + FilterArcs + filterArcs(const DGR& digraph, const AF& arc_filter) { + return FilterArcs(digraph, arc_filter); } /// \ingroup graph_adaptors @@ -1743,22 +1748,24 @@ typename EF = typename GR::template EdgeMap > class FilterEdges : public GraphAdaptorExtender< - SubGraphBase, EF, false> > { + SubGraphBase >, + EF, false> > { #endif + typedef GraphAdaptorExtender< + SubGraphBase >, + EF, false> > Parent; + public: + /// The type of the adapted graph. typedef GR Graph; /// The type of the edge filter map. typedef EF EdgeFilterMap; - typedef GraphAdaptorExtender< - SubGraphBase, EF, false> > - Parent; - typedef typename Parent::Edge Edge; protected: - ConstMap const_true_map; + ConstMap > const_true_map; FilterEdges() : const_true_map(true) { Parent::setNodeFilterMap(const_true_map); @@ -1770,11 +1777,9 @@ /// /// Creates a subgraph for the given graph with the given edge /// filter map. - FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) : - Parent(), const_true_map(true) { - Parent::setGraph(graph); - Parent::setNodeFilterMap(const_true_map); - Parent::setEdgeFilterMap(edge_filter_map); + FilterEdges(GR& graph, EF& edge_filter) + : Parent(), const_true_map() { + Parent::initialize(graph, const_true_map, edge_filter); } /// \brief Sets the status of the given edge @@ -1812,21 +1817,21 @@ /// \relates FilterEdges template FilterEdges - filterEdges(const GR& graph, EF& edge_filter_map) { - return FilterEdges(graph, edge_filter_map); + filterEdges(const GR& graph, EF& edge_filter) { + return FilterEdges(graph, edge_filter); } template FilterEdges - filterEdges(const GR& graph, const EF& edge_filter_map) { - return FilterEdges(graph, edge_filter_map); + filterEdges(const GR& graph, const EF& edge_filter) { + return FilterEdges(graph, edge_filter); } - template + template class UndirectorBase { public: - typedef _Digraph Digraph; + typedef DGR Digraph; typedef UndirectorBase Adaptor; typedef True UndirectedTag; @@ -1834,31 +1839,31 @@ typedef typename Digraph::Arc Edge; typedef typename Digraph::Node Node; - class Arc : public Edge { + class Arc { friend class UndirectorBase; protected: + Edge _edge; bool _forward; - Arc(const Edge& edge, bool forward) : - Edge(edge), _forward(forward) {} + Arc(const Edge& edge, bool forward) + : _edge(edge), _forward(forward) {} public: Arc() {} - Arc(Invalid) : Edge(INVALID), _forward(true) {} + Arc(Invalid) : _edge(INVALID), _forward(true) {} + + operator const Edge&() const { return _edge; } bool operator==(const Arc &other) const { - return _forward == other._forward && - static_cast(*this) == static_cast(other); + return _forward == other._forward && _edge == other._edge; } bool operator!=(const Arc &other) const { - return _forward != other._forward || - static_cast(*this) != static_cast(other); + return _forward != other._forward || _edge != other._edge; } bool operator<(const Arc &other) const { return _forward < other._forward || - (_forward == other._forward && - static_cast(*this) < static_cast(other)); + (_forward == other._forward && _edge < other._edge); } }; @@ -1871,7 +1876,7 @@ } void first(Arc& a) const { - _digraph->first(a); + _digraph->first(a._edge); a._forward = true; } @@ -1879,7 +1884,7 @@ if (a._forward) { a._forward = false; } else { - _digraph->next(a); + _digraph->next(a._edge); a._forward = true; } } @@ -1893,48 +1898,48 @@ } void firstOut(Arc& a, const Node& n) const { - _digraph->firstIn(a, n); - if( static_cast(a) != INVALID ) { + _digraph->firstIn(a._edge, n); + if (a._edge != INVALID ) { a._forward = false; } else { - _digraph->firstOut(a, n); + _digraph->firstOut(a._edge, n); a._forward = true; } } void nextOut(Arc &a) const { if (!a._forward) { - Node n = _digraph->target(a); - _digraph->nextIn(a); - if (static_cast(a) == INVALID ) { - _digraph->firstOut(a, n); + Node n = _digraph->target(a._edge); + _digraph->nextIn(a._edge); + if (a._edge == INVALID) { + _digraph->firstOut(a._edge, n); a._forward = true; } } else { - _digraph->nextOut(a); + _digraph->nextOut(a._edge); } } void firstIn(Arc &a, const Node &n) const { - _digraph->firstOut(a, n); - if (static_cast(a) != INVALID ) { + _digraph->firstOut(a._edge, n); + if (a._edge != INVALID ) { a._forward = false; } else { - _digraph->firstIn(a, n); + _digraph->firstIn(a._edge, n); a._forward = true; } } void nextIn(Arc &a) const { if (!a._forward) { - Node n = _digraph->source(a); - _digraph->nextOut(a); - if( static_cast(a) == INVALID ) { - _digraph->firstIn(a, n); + Node n = _digraph->source(a._edge); + _digraph->nextOut(a._edge); + if (a._edge == INVALID ) { + _digraph->firstIn(a._edge, n); a._forward = true; } } else { - _digraph->nextIn(a); + _digraph->nextIn(a._edge); } } @@ -1967,19 +1972,16 @@ } Node source(const Arc &a) const { - return a._forward ? _digraph->source(a) : _digraph->target(a); + return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge); } Node target(const Arc &a) const { - return a._forward ? _digraph->target(a) : _digraph->source(a); + return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge); } static Arc direct(const Edge &e, bool d) { return Arc(e, d); } - Arc direct(const Edge &e, const Node& n) const { - return Arc(e, _digraph->source(e) == n); - } static bool direction(const Arc &a) { return a._forward; } @@ -2062,34 +2064,35 @@ private: - template + template class ArcMapBase { private: - typedef typename Digraph::template ArcMap<_Value> MapImpl; + typedef typename DGR::template ArcMap MapImpl; public: typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; - typedef _Value Value; + typedef V Value; typedef Arc Key; typedef typename MapTraits::ConstReturnValue ConstReturnValue; typedef typename MapTraits::ReturnValue ReturnValue; typedef typename MapTraits::ConstReturnValue ConstReference; typedef typename MapTraits::ReturnValue Reference; - ArcMapBase(const Adaptor& adaptor) : + ArcMapBase(const UndirectorBase& adaptor) : _forward(*adaptor._digraph), _backward(*adaptor._digraph) {} - ArcMapBase(const Adaptor& adaptor, const Value& v) - : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {} - - void set(const Arc& a, const Value& v) { + ArcMapBase(const UndirectorBase& adaptor, const V& value) + : _forward(*adaptor._digraph, value), + _backward(*adaptor._digraph, value) {} + + void set(const Arc& a, const V& value) { if (direction(a)) { - _forward.set(a, v); + _forward.set(a, value); } else { - _backward.set(a, v); + _backward.set(a, value); } } @@ -2117,17 +2120,17 @@ public: - template - class NodeMap : public Digraph::template NodeMap<_Value> { + template + class NodeMap : public DGR::template NodeMap { + typedef typename DGR::template NodeMap Parent; + public: - - typedef _Value Value; - typedef typename Digraph::template NodeMap Parent; - - explicit NodeMap(const Adaptor& adaptor) + typedef V Value; + + explicit NodeMap(const UndirectorBase& adaptor) : Parent(*adaptor._digraph) {} - NodeMap(const Adaptor& adaptor, const _Value& value) + NodeMap(const UndirectorBase& adaptor, const V& value) : Parent(*adaptor._digraph, value) { } private: @@ -2143,18 +2146,18 @@ }; - template + template class ArcMap - : public SubMapExtender > - { + : public SubMapExtender, ArcMapBase > { + typedef SubMapExtender, ArcMapBase > Parent; + public: - typedef _Value Value; - typedef SubMapExtender > Parent; - - explicit ArcMap(const Adaptor& adaptor) + typedef V Value; + + explicit ArcMap(const UndirectorBase& adaptor) : Parent(adaptor) {} - ArcMap(const Adaptor& adaptor, const Value& value) + ArcMap(const UndirectorBase& adaptor, const V& value) : Parent(adaptor, value) {} private: @@ -2169,17 +2172,17 @@ } }; - template - class EdgeMap : public Digraph::template ArcMap<_Value> { + template + class EdgeMap : public Digraph::template ArcMap { + typedef typename Digraph::template ArcMap Parent; + public: - - typedef _Value Value; - typedef typename Digraph::template ArcMap Parent; - - explicit EdgeMap(const Adaptor& adaptor) + typedef V Value; + + explicit EdgeMap(const UndirectorBase& adaptor) : Parent(*adaptor._digraph) {} - EdgeMap(const Adaptor& adaptor, const Value& value) + EdgeMap(const UndirectorBase& adaptor, const V& value) : Parent(*adaptor._digraph, value) {} private: @@ -2195,19 +2198,22 @@ }; - typedef typename ItemSetTraits::ItemNotifier NodeNotifier; + typedef typename ItemSetTraits::ItemNotifier NodeNotifier; NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } - typedef typename ItemSetTraits::ItemNotifier EdgeNotifier; + typedef typename ItemSetTraits::ItemNotifier EdgeNotifier; EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); } + + typedef EdgeNotifier ArcNotifier; + ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); } protected: UndirectorBase() : _digraph(0) {} - Digraph* _digraph; - - void setDigraph(Digraph& digraph) { + DGR* _digraph; + + void initialize(DGR& digraph) { _digraph = &digraph; } @@ -2226,7 +2232,7 @@ /// by adding or removing nodes or edges, unless the \c GR template /// parameter is set to be \c const. /// - /// \tparam GR The type of the adapted digraph. + /// \tparam DGR The type of the adapted digraph. /// It must conform to the \ref concepts::Digraph "Digraph" concept. /// It can also be specified to be \c const. /// @@ -2236,17 +2242,17 @@ /// each other. /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type /// of the adapted digraph.) - template + template #ifdef DOXYGEN class Undirector { #else class Undirector : - public GraphAdaptorExtender > { + public GraphAdaptorExtender > { #endif + typedef GraphAdaptorExtender > Parent; public: /// The type of the adapted digraph. - typedef GR Digraph; - typedef GraphAdaptorExtender > Parent; + typedef DGR Digraph; protected: Undirector() { } public: @@ -2254,34 +2260,35 @@ /// \brief Constructor /// /// Creates an undirected graph from the given digraph. - Undirector(Digraph& digraph) { - setDigraph(digraph); + Undirector(DGR& digraph) { + initialize(digraph); } /// \brief Arc map combined from two original arc maps /// /// This map adaptor class adapts two arc maps of the underlying /// digraph to get an arc map of the undirected graph. - /// Its value type is inherited from the first arc map type - /// (\c %ForwardMap). - template + /// Its value type is inherited from the first arc map type (\c FW). + /// \tparam FW The type of the "foward" arc map. + /// \tparam BK The type of the "backward" arc map. + template class CombinedArcMap { public: /// The key type of the map typedef typename Parent::Arc Key; /// The value type of the map - typedef typename ForwardMap::Value Value; - - typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; - - typedef typename MapTraits::ReturnValue ReturnValue; - typedef typename MapTraits::ConstReturnValue ConstReturnValue; - typedef typename MapTraits::ReturnValue Reference; - typedef typename MapTraits::ConstReturnValue ConstReference; + typedef typename FW::Value Value; + + typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; + + typedef typename MapTraits::ReturnValue ReturnValue; + typedef typename MapTraits::ConstReturnValue ConstReturnValue; + typedef typename MapTraits::ReturnValue Reference; + typedef typename MapTraits::ConstReturnValue ConstReference; /// Constructor - CombinedArcMap(ForwardMap& forward, BackwardMap& backward) + CombinedArcMap(FW& forward, BK& backward) : _forward(&forward), _backward(&backward) {} /// Sets the value associated with the given key. @@ -2313,39 +2320,36 @@ protected: - ForwardMap* _forward; - BackwardMap* _backward; + FW* _forward; + BK* _backward; }; /// \brief Returns a combined arc map /// /// This function just returns a combined arc map. - template - static CombinedArcMap - combinedArcMap(ForwardMap& forward, BackwardMap& backward) { - return CombinedArcMap(forward, backward); + template + static CombinedArcMap + combinedArcMap(FW& forward, BK& backward) { + return CombinedArcMap(forward, backward); } - template - static CombinedArcMap - combinedArcMap(const ForwardMap& forward, BackwardMap& backward) { - return CombinedArcMap(forward, backward); + template + static CombinedArcMap + combinedArcMap(const FW& forward, BK& backward) { + return CombinedArcMap(forward, backward); } - template - static CombinedArcMap - combinedArcMap(ForwardMap& forward, const BackwardMap& backward) { - return CombinedArcMap(forward, backward); + template + static CombinedArcMap + combinedArcMap(FW& forward, const BK& backward) { + return CombinedArcMap(forward, backward); } - template - static CombinedArcMap - combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) { - return CombinedArcMap(forward, backward); + template + static CombinedArcMap + combinedArcMap(const FW& forward, const BK& backward) { + return CombinedArcMap(forward, backward); } }; @@ -2355,21 +2359,21 @@ /// This function just returns a read-only \ref Undirector adaptor. /// \ingroup graph_adaptors /// \relates Undirector - template - Undirector undirector(const GR& digraph) { - return Undirector(digraph); + template + Undirector undirector(const DGR& digraph) { + return Undirector(digraph); } - template + template class OrienterBase { public: - typedef _Graph Graph; - typedef _DirectionMap DirectionMap; - - typedef typename Graph::Node Node; - typedef typename Graph::Edge Arc; + typedef GR Graph; + typedef DM DirectionMap; + + typedef typename GR::Node Node; + typedef typename GR::Edge Arc; void reverseArc(const Arc& arc) { _direction->set(arc, !(*_direction)[arc]); @@ -2448,22 +2452,22 @@ int maxNodeId() const { return _graph->maxNodeId(); } int maxArcId() const { return _graph->maxEdgeId(); } - typedef typename ItemSetTraits::ItemNotifier NodeNotifier; + typedef typename ItemSetTraits::ItemNotifier NodeNotifier; NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } - typedef typename ItemSetTraits::ItemNotifier ArcNotifier; + typedef typename ItemSetTraits::ItemNotifier ArcNotifier; ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } - template - class NodeMap : public _Graph::template NodeMap<_Value> { + template + class NodeMap : public GR::template NodeMap { + typedef typename GR::template NodeMap Parent; + public: - typedef typename _Graph::template NodeMap<_Value> Parent; - - explicit NodeMap(const OrienterBase& adapter) + explicit NodeMap(const OrienterBase& adapter) : Parent(*adapter._graph) {} - NodeMap(const OrienterBase& adapter, const _Value& value) + NodeMap(const OrienterBase& adapter, const V& value) : Parent(*adapter._graph, value) {} private: @@ -2479,16 +2483,16 @@ }; - template - class ArcMap : public _Graph::template EdgeMap<_Value> { + template + class ArcMap : public GR::template EdgeMap { + typedef typename Graph::template EdgeMap Parent; + public: - typedef typename Graph::template EdgeMap<_Value> Parent; - - explicit ArcMap(const OrienterBase& adapter) + explicit ArcMap(const OrienterBase& adapter) : Parent(*adapter._graph) { } - ArcMap(const OrienterBase& adapter, const _Value& value) + ArcMap(const OrienterBase& adapter, const V& value) : Parent(*adapter._graph, value) { } private: @@ -2507,16 +2511,13 @@ protected: Graph* _graph; - DirectionMap* _direction; - - void setDirectionMap(DirectionMap& direction) { + DM* _direction; + + void initialize(GR& graph, DM& direction) { + _graph = &graph; _direction = &direction; } - void setGraph(Graph& graph) { - _graph = &graph; - } - }; /// \ingroup graph_adaptors @@ -2556,6 +2557,7 @@ class Orienter : public DigraphAdaptorExtender > { #endif + typedef DigraphAdaptorExtender > Parent; public: /// The type of the adapted graph. @@ -2563,18 +2565,18 @@ /// The type of the direction edge map. typedef DM DirectionMap; - typedef DigraphAdaptorExtender > Parent; typedef typename Parent::Arc Arc; + protected: Orienter() { } + public: /// \brief Constructor /// /// Constructor of the adaptor. - Orienter(Graph& graph, DirectionMap& direction) { - setGraph(graph); - setDirectionMap(direction); + Orienter(GR& graph, DM& direction) { + Parent::initialize(graph, direction); } /// \brief Reverses the given arc @@ -2594,67 +2596,62 @@ /// \relates Orienter template Orienter - orienter(const GR& graph, DM& direction_map) { - return Orienter(graph, direction_map); + orienter(const GR& graph, DM& direction) { + return Orienter(graph, direction); } template Orienter - orienter(const GR& graph, const DM& direction_map) { - return Orienter(graph, direction_map); + orienter(const GR& graph, const DM& direction) { + return Orienter(graph, direction); } namespace _adaptor_bits { - template + template class ResForwardFilter { public: - typedef typename Digraph::Arc Key; + typedef typename DGR::Arc Key; typedef bool Value; private: - const CapacityMap* _capacity; - const FlowMap* _flow; - Tolerance _tolerance; + const CM* _capacity; + const FM* _flow; + TL _tolerance; + public: - ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow, - const Tolerance& tolerance = Tolerance()) + ResForwardFilter(const CM& capacity, const FM& flow, + const TL& tolerance = TL()) : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } - bool operator[](const typename Digraph::Arc& a) const { + bool operator[](const typename DGR::Arc& a) const { return _tolerance.positive((*_capacity)[a] - (*_flow)[a]); } }; - template + template class ResBackwardFilter { public: - typedef typename Digraph::Arc Key; + typedef typename DGR::Arc Key; typedef bool Value; private: - const CapacityMap* _capacity; - const FlowMap* _flow; - Tolerance _tolerance; + const CM* _capacity; + const FM* _flow; + TL _tolerance; public: - ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow, - const Tolerance& tolerance = Tolerance()) + ResBackwardFilter(const CM& capacity, const FM& flow, + const TL& tolerance = TL()) : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } - bool operator[](const typename Digraph::Arc& a) const { + bool operator[](const typename DGR::Arc& a) const { return _tolerance.positive((*_flow)[a]); } }; @@ -2681,7 +2678,7 @@ /// arcs). /// This class conforms to the \ref concepts::Digraph "Digraph" concept. /// - /// \tparam GR The type of the adapted digraph. + /// \tparam DGR The type of the adapted digraph. /// It must conform to the \ref concepts::Digraph "Digraph" concept. /// It is implicitly \c const. /// \tparam CM The type of the capacity map. @@ -2703,25 +2700,26 @@ /// convertible to each other, moreover the \c Arc type of the adaptor /// is convertible to the \c Arc type of the adapted digraph. #ifdef DOXYGEN - template + template class ResidualDigraph #else - template, + template, typename FM = CM, typename TL = Tolerance > - class ResidualDigraph : - public FilterArcs< - Undirector, - typename Undirector::template CombinedArcMap< - _adaptor_bits::ResForwardFilter, - _adaptor_bits::ResBackwardFilter > > + class ResidualDigraph + : public SubDigraph< + Undirector, + ConstMap >, + typename Undirector::template CombinedArcMap< + _adaptor_bits::ResForwardFilter, + _adaptor_bits::ResBackwardFilter > > #endif { public: /// The type of the underlying digraph. - typedef GR Digraph; + typedef DGR Digraph; /// The type of the capacity map. typedef CM CapacityMap; /// The type of the flow map. @@ -2736,21 +2734,24 @@ typedef Undirector Undirected; - typedef _adaptor_bits::ResForwardFilter ForwardFilter; - - typedef _adaptor_bits::ResBackwardFilter BackwardFilter; + typedef ConstMap > NodeFilter; + + typedef _adaptor_bits::ResForwardFilter ForwardFilter; + + typedef _adaptor_bits::ResBackwardFilter BackwardFilter; typedef typename Undirected:: template CombinedArcMap ArcFilter; - typedef FilterArcs Parent; + typedef SubDigraph Parent; const CapacityMap* _capacity; FlowMap* _flow; Undirected _graph; + NodeFilter _node_filter; ForwardFilter _forward_filter; BackwardFilter _backward_filter; ArcFilter _arc_filter; @@ -2761,15 +2762,15 @@ /// /// Constructor of the residual digraph adaptor. The parameters are the /// digraph, the capacity map, the flow map, and a tolerance object. - ResidualDigraph(const Digraph& digraph, const CapacityMap& capacity, - FlowMap& flow, const Tolerance& tolerance = Tolerance()) - : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph), + ResidualDigraph(const DGR& digraph, const CM& capacity, + FM& flow, const TL& tolerance = Tolerance()) + : Parent(), _capacity(&capacity), _flow(&flow), + _graph(digraph), _node_filter(), _forward_filter(capacity, flow, tolerance), _backward_filter(capacity, flow, tolerance), _arc_filter(_forward_filter, _backward_filter) { - Parent::setDigraph(_graph); - Parent::setArcFilterMap(_arc_filter); + Parent::initialize(_graph, _node_filter, _arc_filter); } typedef typename Parent::Arc Arc; @@ -2845,7 +2846,8 @@ typedef typename CapacityMap::Value Value; /// Constructor - ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {} + ResidualCapacity(const ResidualDigraph& adaptor) + : _adaptor(&adaptor) {} /// Returns the value associated with the given residual arc Value operator[](const Arc& a) const { @@ -2865,26 +2867,27 @@ /// \brief Returns a (read-only) Residual adaptor /// - /// This function just returns a (read-only) \ref Residual adaptor. + /// This function just returns a (read-only) \ref ResidualDigraph adaptor. /// \ingroup graph_adaptors - /// \relates Residual - template - ResidualDigraph - residualDigraph(const GR& digraph, const CM& capacity_map, FM& flow_map) { - return ResidualDigraph (digraph, capacity_map, flow_map); + /// \relates ResidualDigraph + template + ResidualDigraph + residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) { + return ResidualDigraph (digraph, capacity_map, flow_map); } - template + template class SplitNodesBase { + typedef DigraphAdaptorBase Parent; + public: - typedef _Digraph Digraph; - typedef DigraphAdaptorBase Parent; + typedef DGR Digraph; typedef SplitNodesBase Adaptor; - typedef typename Digraph::Node DigraphNode; - typedef typename Digraph::Arc DigraphArc; + typedef typename DGR::Node DigraphNode; + typedef typename DGR::Arc DigraphArc; class Node; class Arc; @@ -3148,32 +3151,32 @@ private: - template + template class NodeMapBase - : public MapTraits > { - typedef typename Parent::template NodeMap<_Value> NodeImpl; + : public MapTraits > { + typedef typename Parent::template NodeMap NodeImpl; public: typedef Node Key; - typedef _Value Value; + typedef V Value; typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; typedef typename MapTraits::ReturnValue ReturnValue; typedef typename MapTraits::ConstReturnValue ConstReturnValue; typedef typename MapTraits::ReturnValue Reference; typedef typename MapTraits::ConstReturnValue ConstReference; - NodeMapBase(const Adaptor& adaptor) + NodeMapBase(const SplitNodesBase& adaptor) : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {} - NodeMapBase(const Adaptor& adaptor, const Value& value) + NodeMapBase(const SplitNodesBase& adaptor, const V& value) : _in_map(*adaptor._digraph, value), _out_map(*adaptor._digraph, value) {} - void set(const Node& key, const Value& val) { - if (Adaptor::inNode(key)) { _in_map.set(key, val); } + void set(const Node& key, const V& val) { + if (SplitNodesBase::inNode(key)) { _in_map.set(key, val); } else {_out_map.set(key, val); } } ReturnValue operator[](const Node& key) { - if (Adaptor::inNode(key)) { return _in_map[key]; } + if (SplitNodesBase::inNode(key)) { return _in_map[key]; } else { return _out_map[key]; } } @@ -3186,47 +3189,47 @@ NodeImpl _in_map, _out_map; }; - template + template class ArcMapBase - : public MapTraits > { - typedef typename Parent::template ArcMap<_Value> ArcImpl; - typedef typename Parent::template NodeMap<_Value> NodeImpl; + : public MapTraits > { + typedef typename Parent::template ArcMap ArcImpl; + typedef typename Parent::template NodeMap NodeImpl; public: typedef Arc Key; - typedef _Value Value; + typedef V Value; typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; typedef typename MapTraits::ReturnValue ReturnValue; typedef typename MapTraits::ConstReturnValue ConstReturnValue; typedef typename MapTraits::ReturnValue Reference; typedef typename MapTraits::ConstReturnValue ConstReference; - ArcMapBase(const Adaptor& adaptor) + ArcMapBase(const SplitNodesBase& adaptor) : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {} - ArcMapBase(const Adaptor& adaptor, const Value& value) + ArcMapBase(const SplitNodesBase& adaptor, const V& value) : _arc_map(*adaptor._digraph, value), _node_map(*adaptor._digraph, value) {} - void set(const Arc& key, const Value& val) { - if (Adaptor::origArc(key)) { - _arc_map.set(key._item.first(), val); + void set(const Arc& key, const V& val) { + if (SplitNodesBase::origArc(key)) { + _arc_map.set(static_cast(key), val); } else { - _node_map.set(key._item.second(), val); + _node_map.set(static_cast(key), val); } } ReturnValue operator[](const Arc& key) { - if (Adaptor::origArc(key)) { - return _arc_map[key._item.first()]; + if (SplitNodesBase::origArc(key)) { + return _arc_map[static_cast(key)]; } else { - return _node_map[key._item.second()]; + return _node_map[static_cast(key)]; } } ConstReturnValue operator[](const Arc& key) const { - if (Adaptor::origArc(key)) { - return _arc_map[key._item.first()]; + if (SplitNodesBase::origArc(key)) { + return _arc_map[static_cast(key)]; } else { - return _node_map[key._item.second()]; + return _node_map[static_cast(key)]; } } @@ -3237,18 +3240,18 @@ public: - template + template class NodeMap - : public SubMapExtender > - { + : public SubMapExtender, NodeMapBase > { + typedef SubMapExtender, NodeMapBase > Parent; + public: - typedef _Value Value; - typedef SubMapExtender > Parent; - - NodeMap(const Adaptor& adaptor) + typedef V Value; + + NodeMap(const SplitNodesBase& adaptor) : Parent(adaptor) {} - NodeMap(const Adaptor& adaptor, const Value& value) + NodeMap(const SplitNodesBase& adaptor, const V& value) : Parent(adaptor, value) {} private: @@ -3263,18 +3266,18 @@ } }; - template + template class ArcMap - : public SubMapExtender > - { + : public SubMapExtender, ArcMapBase > { + typedef SubMapExtender, ArcMapBase > Parent; + public: - typedef _Value Value; - typedef SubMapExtender > Parent; - - ArcMap(const Adaptor& adaptor) + typedef V Value; + + ArcMap(const SplitNodesBase& adaptor) : Parent(adaptor) {} - ArcMap(const Adaptor& adaptor, const Value& value) + ArcMap(const SplitNodesBase& adaptor, const V& value) : Parent(adaptor, value) {} private: @@ -3293,9 +3296,9 @@ SplitNodesBase() : _digraph(0) {} - Digraph* _digraph; - - void setDigraph(Digraph& digraph) { + DGR* _digraph; + + void initialize(Digraph& digraph) { _digraph = &digraph; } @@ -3322,25 +3325,26 @@ /// costs/capacities of the original digraph to the \e bind \e arcs /// in the adaptor. /// - /// \tparam GR The type of the adapted digraph. + /// \tparam DGR The type of the adapted digraph. /// It must conform to the \ref concepts::Digraph "Digraph" concept. /// It is implicitly \c const. /// /// \note The \c Node type of this adaptor is converible to the \c Node /// type of the adapted digraph. - template + template #ifdef DOXYGEN class SplitNodes { #else class SplitNodes - : public DigraphAdaptorExtender > { + : public DigraphAdaptorExtender > { #endif + typedef DigraphAdaptorExtender > Parent; + public: - typedef GR Digraph; - typedef DigraphAdaptorExtender > Parent; - - typedef typename Digraph::Node DigraphNode; - typedef typename Digraph::Arc DigraphArc; + typedef DGR Digraph; + + typedef typename DGR::Node DigraphNode; + typedef typename DGR::Arc DigraphArc; typedef typename Parent::Node Node; typedef typename Parent::Arc Arc; @@ -3348,8 +3352,8 @@ /// \brief Constructor /// /// Constructor of the adaptor. - SplitNodes(const Digraph& g) { - Parent::setDigraph(g); + SplitNodes(const DGR& g) { + Parent::initialize(g); } /// \brief Returns \c true if the given node is an in-node. @@ -3418,30 +3422,31 @@ /// /// This map adaptor class adapts two node maps of the original digraph /// to get a node map of the split digraph. - /// Its value type is inherited from the first node map type - /// (\c InNodeMap). - template + /// Its value type is inherited from the first node map type (\c IN). + /// \tparam IN The type of the node map for the in-nodes. + /// \tparam OUT The type of the node map for the out-nodes. + template class CombinedNodeMap { public: /// The key type of the map typedef Node Key; /// The value type of the map - typedef typename InNodeMap::Value Value; - - typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; - typedef typename MapTraits::ReturnValue ReturnValue; - typedef typename MapTraits::ConstReturnValue ConstReturnValue; - typedef typename MapTraits::ReturnValue Reference; - typedef typename MapTraits::ConstReturnValue ConstReference; + typedef typename IN::Value Value; + + typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; + typedef typename MapTraits::ReturnValue ReturnValue; + typedef typename MapTraits::ConstReturnValue ConstReturnValue; + typedef typename MapTraits::ReturnValue Reference; + typedef typename MapTraits::ConstReturnValue ConstReference; /// Constructor - CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) + CombinedNodeMap(IN& in_map, OUT& out_map) : _in_map(in_map), _out_map(out_map) {} /// Returns the value associated with the given key. Value operator[](const Key& key) const { - if (Parent::inNode(key)) { + if (SplitNodesBase::inNode(key)) { return _in_map[key]; } else { return _out_map[key]; @@ -3450,7 +3455,7 @@ /// Returns a reference to the value associated with the given key. Value& operator[](const Key& key) { - if (Parent::inNode(key)) { + if (SplitNodesBase::inNode(key)) { return _in_map[key]; } else { return _out_map[key]; @@ -3459,7 +3464,7 @@ /// Sets the value associated with the given key. void set(const Key& key, const Value& value) { - if (Parent::inNode(key)) { + if (SplitNodesBase::inNode(key)) { _in_map.set(key, value); } else { _out_map.set(key, value); @@ -3468,8 +3473,8 @@ private: - InNodeMap& _in_map; - OutNodeMap& _out_map; + IN& _in_map; + OUT& _out_map; }; @@ -3477,29 +3482,28 @@ /// \brief Returns a combined node map /// /// This function just returns a combined node map. - template - static CombinedNodeMap - combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) { - return CombinedNodeMap(in_map, out_map); + template + static CombinedNodeMap + combinedNodeMap(IN& in_map, OUT& out_map) { + return CombinedNodeMap(in_map, out_map); } - template - static CombinedNodeMap - combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) { - return CombinedNodeMap(in_map, out_map); + template + static CombinedNodeMap + combinedNodeMap(const IN& in_map, OUT& out_map) { + return CombinedNodeMap(in_map, out_map); } - template - static CombinedNodeMap - combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) { - return CombinedNodeMap(in_map, out_map); + template + static CombinedNodeMap + combinedNodeMap(IN& in_map, const OUT& out_map) { + return CombinedNodeMap(in_map, out_map); } - template - static CombinedNodeMap - combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) { - return CombinedNodeMap(in_map, out_map); + template + static CombinedNodeMap + combinedNodeMap(const IN& in_map, const OUT& out_map) { + return CombinedNodeMap(in_map, out_map); } /// \brief Arc map combined from an arc map and a node map of the @@ -3507,30 +3511,31 @@ /// /// This map adaptor class adapts an arc map and a node map of the /// original digraph to get an arc map of the split digraph. - /// Its value type is inherited from the original arc map type - /// (\c ArcMap). - template + /// Its value type is inherited from the original arc map type (\c AM). + /// \tparam AM The type of the arc map. + /// \tparam NM the type of the node map. + template class CombinedArcMap { public: /// The key type of the map typedef Arc Key; /// The value type of the map - typedef typename ArcMap::Value Value; - - typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; - typedef typename MapTraits::ReturnValue ReturnValue; - typedef typename MapTraits::ConstReturnValue ConstReturnValue; - typedef typename MapTraits::ReturnValue Reference; - typedef typename MapTraits::ConstReturnValue ConstReference; + typedef typename AM::Value Value; + + typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; + typedef typename MapTraits::ReturnValue ReturnValue; + typedef typename MapTraits::ConstReturnValue ConstReturnValue; + typedef typename MapTraits::ReturnValue Reference; + typedef typename MapTraits::ConstReturnValue ConstReference; /// Constructor - CombinedArcMap(ArcMap& arc_map, NodeMap& node_map) + CombinedArcMap(AM& arc_map, NM& node_map) : _arc_map(arc_map), _node_map(node_map) {} /// Returns the value associated with the given key. Value operator[](const Key& arc) const { - if (Parent::origArc(arc)) { + if (SplitNodesBase::origArc(arc)) { return _arc_map[arc]; } else { return _node_map[arc]; @@ -3539,7 +3544,7 @@ /// Returns a reference to the value associated with the given key. Value& operator[](const Key& arc) { - if (Parent::origArc(arc)) { + if (SplitNodesBase::origArc(arc)) { return _arc_map[arc]; } else { return _node_map[arc]; @@ -3548,7 +3553,7 @@ /// Sets the value associated with the given key. void set(const Arc& arc, const Value& val) { - if (Parent::origArc(arc)) { + if (SplitNodesBase::origArc(arc)) { _arc_map.set(arc, val); } else { _node_map.set(arc, val); @@ -3556,8 +3561,10 @@ } private: - ArcMap& _arc_map; - NodeMap& _node_map; + + AM& _arc_map; + NM& _node_map; + }; /// \brief Returns a combined arc map @@ -3594,12 +3601,14 @@ /// This function just returns a (read-only) \ref SplitNodes adaptor. /// \ingroup graph_adaptors /// \relates SplitNodes - template - SplitNodes - splitNodes(const GR& digraph) { - return SplitNodes(digraph); + template + SplitNodes + splitNodes(const DGR& digraph) { + return SplitNodes(digraph); } +#undef LEMON_SCOPE_FIX + } //namespace lemon #endif //LEMON_ADAPTORS_H