diff -r c35afa9e89e7 -r ef88c0a30f85 lemon/adaptors.h --- a/lemon/adaptors.h Mon Jan 12 23:11:39 2009 +0100 +++ b/lemon/adaptors.h Thu Nov 05 15:48:01 2009 +0100 @@ -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