deba@416: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@414: * deba@416: * This file is a part of LEMON, a generic C++ optimization library. deba@414: * alpar@454: * Copyright (C) 2003-2009 deba@414: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@414: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@414: * deba@414: * Permission to use, modify and distribute this software is granted deba@414: * provided that this copyright notice appears in all copies. For deba@414: * precise terms see the accompanying LICENSE file. deba@414: * deba@414: * This software is provided "AS IS" with no warranty of any kind, deba@414: * express or implied, and with no claim as to its suitability for any deba@414: * purpose. deba@414: * deba@414: */ deba@414: deba@416: #ifndef LEMON_ADAPTORS_H deba@416: #define LEMON_ADAPTORS_H deba@416: deba@416: /// \ingroup graph_adaptors deba@416: /// \file kpeter@451: /// \brief Adaptor classes for digraphs and graphs deba@414: /// deba@416: /// This file contains several useful adaptors for digraphs and graphs. deba@414: deba@414: #include deba@414: #include deba@414: #include deba@414: deba@414: #include deba@414: #include deba@414: deba@414: #include deba@414: deba@414: namespace lemon { deba@414: deba@512: #ifdef _MSC_VER deba@512: #define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED deba@512: #else deba@512: #define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED deba@512: #endif deba@512: deba@512: template deba@414: class DigraphAdaptorBase { deba@414: public: deba@512: typedef DGR Digraph; deba@414: typedef DigraphAdaptorBase Adaptor; deba@414: deba@414: protected: deba@512: DGR* _digraph; deba@414: DigraphAdaptorBase() : _digraph(0) { } deba@512: void initialize(DGR& digraph) { _digraph = &digraph; } deba@414: deba@414: public: deba@512: DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { } deba@512: deba@512: typedef typename DGR::Node Node; deba@512: typedef typename DGR::Arc Arc; deba@416: deba@414: void first(Node& i) const { _digraph->first(i); } deba@414: void first(Arc& i) const { _digraph->first(i); } deba@414: void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); } deba@414: void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); } deba@414: deba@414: void next(Node& i) const { _digraph->next(i); } deba@414: void next(Arc& i) const { _digraph->next(i); } deba@414: void nextIn(Arc& i) const { _digraph->nextIn(i); } deba@414: void nextOut(Arc& i) const { _digraph->nextOut(i); } deba@414: deba@414: Node source(const Arc& a) const { return _digraph->source(a); } deba@414: Node target(const Arc& a) const { return _digraph->target(a); } deba@414: deba@512: typedef NodeNumTagIndicator NodeNumTag; deba@414: int nodeNum() const { return _digraph->nodeNum(); } deba@416: deba@512: typedef ArcNumTagIndicator ArcNumTag; deba@414: int arcNum() const { return _digraph->arcNum(); } deba@414: deba@512: typedef FindArcTagIndicator FindArcTag; kpeter@448: Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const { deba@414: return _digraph->findArc(u, v, prev); deba@414: } deba@416: deba@414: Node addNode() { return _digraph->addNode(); } deba@414: Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); } deba@414: kpeter@448: void erase(const Node& n) { _digraph->erase(n); } kpeter@448: void erase(const Arc& a) { _digraph->erase(a); } kpeter@448: kpeter@448: void clear() { _digraph->clear(); } deba@416: deba@414: int id(const Node& n) const { return _digraph->id(n); } deba@414: int id(const Arc& a) const { return _digraph->id(a); } deba@414: deba@414: Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); } deba@414: Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); } deba@414: deba@414: int maxNodeId() const { return _digraph->maxNodeId(); } deba@414: int maxArcId() const { return _digraph->maxArcId(); } deba@414: deba@512: typedef typename ItemSetTraits::ItemNotifier NodeNotifier; deba@416: NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } deba@414: deba@512: typedef typename ItemSetTraits::ItemNotifier ArcNotifier; deba@416: ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); } deba@416: deba@512: template deba@512: class NodeMap : public DGR::template NodeMap { deba@414: public: deba@414: deba@512: typedef typename DGR::template NodeMap Parent; deba@414: deba@416: explicit NodeMap(const Adaptor& adaptor) deba@416: : Parent(*adaptor._digraph) {} deba@414: deba@512: NodeMap(const Adaptor& adaptor, const V& value) deba@416: : Parent(*adaptor._digraph, value) { } deba@414: deba@414: private: deba@414: NodeMap& operator=(const NodeMap& cmap) { deba@414: return operator=(cmap); deba@414: } deba@414: deba@414: template deba@414: NodeMap& operator=(const CMap& cmap) { deba@414: Parent::operator=(cmap); deba@414: return *this; deba@414: } deba@416: deba@414: }; deba@414: deba@512: template deba@512: class ArcMap : public DGR::template ArcMap { deba@414: public: deba@416: deba@512: typedef typename DGR::template ArcMap Parent; deba@512: deba@512: explicit ArcMap(const DigraphAdaptorBase& adaptor) deba@416: : Parent(*adaptor._digraph) {} deba@414: deba@512: ArcMap(const DigraphAdaptorBase& adaptor, const V& value) deba@416: : Parent(*adaptor._digraph, value) {} deba@414: deba@414: private: deba@414: ArcMap& operator=(const ArcMap& cmap) { deba@414: return operator=(cmap); deba@414: } deba@414: deba@414: template deba@414: ArcMap& operator=(const CMap& cmap) { deba@414: Parent::operator=(cmap); deba@414: return *this; deba@414: } deba@414: deba@414: }; deba@414: deba@414: }; deba@414: deba@512: template deba@416: class GraphAdaptorBase { deba@416: public: deba@512: typedef GR Graph; deba@416: deba@416: protected: deba@512: GR* _graph; deba@416: deba@416: GraphAdaptorBase() : _graph(0) {} deba@416: deba@512: void initialize(GR& graph) { _graph = &graph; } deba@416: deba@416: public: deba@512: GraphAdaptorBase(GR& graph) : _graph(&graph) {} deba@512: deba@512: typedef typename GR::Node Node; deba@512: typedef typename GR::Arc Arc; deba@512: typedef typename GR::Edge Edge; deba@416: deba@416: void first(Node& i) const { _graph->first(i); } deba@416: void first(Arc& i) const { _graph->first(i); } deba@416: void first(Edge& i) const { _graph->first(i); } deba@416: void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); } deba@416: void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); } deba@416: void firstInc(Edge &i, bool &d, const Node &n) const { deba@416: _graph->firstInc(i, d, n); deba@416: } deba@416: deba@416: void next(Node& i) const { _graph->next(i); } deba@416: void next(Arc& i) const { _graph->next(i); } deba@416: void next(Edge& i) const { _graph->next(i); } deba@416: void nextIn(Arc& i) const { _graph->nextIn(i); } deba@416: void nextOut(Arc& i) const { _graph->nextOut(i); } deba@416: void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); } deba@416: deba@416: Node u(const Edge& e) const { return _graph->u(e); } deba@416: Node v(const Edge& e) const { return _graph->v(e); } deba@416: deba@416: Node source(const Arc& a) const { return _graph->source(a); } deba@416: Node target(const Arc& a) const { return _graph->target(a); } deba@416: deba@416: typedef NodeNumTagIndicator NodeNumTag; deba@416: int nodeNum() const { return _graph->nodeNum(); } deba@416: kpeter@446: typedef ArcNumTagIndicator ArcNumTag; kpeter@446: int arcNum() const { return _graph->arcNum(); } kpeter@446: deba@416: typedef EdgeNumTagIndicator EdgeNumTag; deba@416: int edgeNum() const { return _graph->edgeNum(); } deba@416: kpeter@446: typedef FindArcTagIndicator FindArcTag; kpeter@448: Arc findArc(const Node& u, const Node& v, kpeter@448: const Arc& prev = INVALID) const { deba@416: return _graph->findArc(u, v, prev); deba@416: } kpeter@446: kpeter@446: typedef FindEdgeTagIndicator FindEdgeTag; kpeter@448: Edge findEdge(const Node& u, const Node& v, kpeter@448: const Edge& prev = INVALID) const { deba@416: return _graph->findEdge(u, v, prev); deba@416: } deba@416: deba@416: Node addNode() { return _graph->addNode(); } deba@416: Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); } deba@416: deba@416: void erase(const Node& i) { _graph->erase(i); } deba@416: void erase(const Edge& i) { _graph->erase(i); } deba@416: deba@416: void clear() { _graph->clear(); } deba@416: deba@416: bool direction(const Arc& a) const { return _graph->direction(a); } deba@416: Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); } deba@416: deba@416: int id(const Node& v) const { return _graph->id(v); } deba@416: int id(const Arc& a) const { return _graph->id(a); } deba@416: int id(const Edge& e) const { return _graph->id(e); } deba@416: deba@416: Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); } deba@416: Arc arcFromId(int ix) const { return _graph->arcFromId(ix); } deba@416: Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); } deba@416: deba@416: int maxNodeId() const { return _graph->maxNodeId(); } deba@416: int maxArcId() const { return _graph->maxArcId(); } deba@416: int maxEdgeId() const { return _graph->maxEdgeId(); } deba@416: deba@512: typedef typename ItemSetTraits::ItemNotifier NodeNotifier; deba@416: NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } deba@416: deba@512: typedef typename ItemSetTraits::ItemNotifier ArcNotifier; deba@416: ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } deba@416: deba@512: typedef typename ItemSetTraits::ItemNotifier EdgeNotifier; deba@416: EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); } deba@416: deba@512: template deba@512: class NodeMap : public GR::template NodeMap { deba@416: public: deba@512: typedef typename GR::template NodeMap Parent; deba@512: explicit NodeMap(const GraphAdaptorBase& adapter) deba@416: : Parent(*adapter._graph) {} deba@512: NodeMap(const GraphAdaptorBase& adapter, const V& value) deba@416: : Parent(*adapter._graph, value) {} deba@416: deba@416: private: deba@416: NodeMap& operator=(const NodeMap& cmap) { deba@416: return operator=(cmap); deba@416: } deba@416: deba@416: template deba@416: NodeMap& operator=(const CMap& cmap) { deba@416: Parent::operator=(cmap); deba@416: return *this; deba@416: } deba@416: deba@416: }; deba@416: deba@512: template deba@512: class ArcMap : public GR::template ArcMap { deba@416: public: deba@512: typedef typename GR::template ArcMap Parent; deba@512: explicit ArcMap(const GraphAdaptorBase& adapter) deba@416: : Parent(*adapter._graph) {} deba@512: ArcMap(const GraphAdaptorBase& adapter, const V& value) deba@416: : Parent(*adapter._graph, value) {} deba@416: deba@416: private: deba@416: ArcMap& operator=(const ArcMap& cmap) { deba@416: return operator=(cmap); deba@416: } deba@416: deba@416: template deba@416: ArcMap& operator=(const CMap& cmap) { deba@416: Parent::operator=(cmap); deba@416: return *this; deba@416: } deba@416: }; deba@416: deba@512: template deba@512: class EdgeMap : public GR::template EdgeMap { deba@416: public: deba@512: typedef typename GR::template EdgeMap Parent; deba@512: explicit EdgeMap(const GraphAdaptorBase& adapter) deba@416: : Parent(*adapter._graph) {} deba@512: EdgeMap(const GraphAdaptorBase& adapter, const V& value) deba@416: : Parent(*adapter._graph, value) {} deba@416: deba@416: private: deba@416: EdgeMap& operator=(const EdgeMap& cmap) { deba@416: return operator=(cmap); deba@416: } deba@416: deba@416: template deba@416: EdgeMap& operator=(const CMap& cmap) { deba@416: Parent::operator=(cmap); deba@416: return *this; deba@416: } deba@416: }; deba@416: deba@416: }; deba@414: deba@512: template deba@512: class ReverseDigraphBase : public DigraphAdaptorBase { deba@414: public: deba@512: typedef DGR Digraph; deba@512: typedef DigraphAdaptorBase Parent; deba@414: protected: deba@416: ReverseDigraphBase() : Parent() { } deba@414: public: deba@414: typedef typename Parent::Node Node; deba@414: typedef typename Parent::Arc Arc; deba@414: deba@414: void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); } deba@414: void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); } deba@414: deba@414: void nextIn(Arc& a) const { Parent::nextOut(a); } deba@414: void nextOut(Arc& a) const { Parent::nextIn(a); } deba@414: deba@414: Node source(const Arc& a) const { return Parent::target(a); } deba@414: Node target(const Arc& a) const { return Parent::source(a); } deba@414: deba@416: Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); } deba@416: deba@512: typedef FindArcTagIndicator FindArcTag; deba@416: Arc findArc(const Node& u, const Node& v, kpeter@448: const Arc& prev = INVALID) const { deba@414: return Parent::findArc(v, u, prev); deba@414: } deba@414: deba@414: }; deba@416: deba@416: /// \ingroup graph_adaptors deba@414: /// kpeter@451: /// \brief Adaptor class for reversing the orientation of the arcs in kpeter@451: /// a digraph. deba@414: /// kpeter@451: /// ReverseDigraph can be used for reversing the arcs in a digraph. kpeter@451: /// It conforms to the \ref concepts::Digraph "Digraph" concept. deba@414: /// kpeter@451: /// The adapted digraph can also be modified through this adaptor kpeter@453: /// by adding or removing nodes or arcs, unless the \c GR template kpeter@451: /// parameter is set to be \c const. kpeter@451: /// deba@512: /// \tparam DGR The type of the adapted digraph. kpeter@451: /// It must conform to the \ref concepts::Digraph "Digraph" concept. kpeter@451: /// It can also be specified to be \c const. kpeter@451: /// kpeter@451: /// \note The \c Node and \c Arc types of this adaptor and the adapted kpeter@451: /// digraph are convertible to each other. deba@512: template kpeter@453: #ifdef DOXYGEN kpeter@453: class ReverseDigraph { kpeter@453: #else deba@416: class ReverseDigraph : deba@512: public DigraphAdaptorExtender > { kpeter@453: #endif deba@414: public: kpeter@453: /// The type of the adapted digraph. deba@512: typedef DGR Digraph; deba@512: typedef DigraphAdaptorExtender > Parent; deba@414: protected: deba@416: ReverseDigraph() { } deba@414: public: deba@415: deba@415: /// \brief Constructor deba@415: /// kpeter@451: /// Creates a reverse digraph adaptor for the given digraph. deba@512: explicit ReverseDigraph(DGR& digraph) { deba@512: Parent::initialize(digraph); deba@414: } deba@414: }; deba@414: kpeter@451: /// \brief Returns a read-only ReverseDigraph adaptor deba@414: /// kpeter@451: /// This function just returns a read-only \ref ReverseDigraph adaptor. kpeter@451: /// \ingroup graph_adaptors kpeter@451: /// \relates ReverseDigraph deba@512: template deba@512: ReverseDigraph reverseDigraph(const DGR& digraph) { deba@512: return ReverseDigraph(digraph); deba@414: } deba@414: kpeter@451: deba@512: template deba@512: class SubDigraphBase : public DigraphAdaptorBase { deba@414: public: deba@512: typedef DGR Digraph; deba@512: typedef NF NodeFilterMap; deba@512: typedef AF ArcFilterMap; deba@414: deba@416: typedef SubDigraphBase Adaptor; deba@512: typedef DigraphAdaptorBase Parent; deba@414: protected: deba@512: NF* _node_filter; deba@512: AF* _arc_filter; deba@416: SubDigraphBase() deba@414: : Parent(), _node_filter(0), _arc_filter(0) { } deba@414: deba@512: void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) { deba@512: Parent::initialize(digraph); deba@414: _node_filter = &node_filter; deba@512: _arc_filter = &arc_filter; deba@414: } deba@414: deba@414: public: deba@414: deba@414: typedef typename Parent::Node Node; deba@414: typedef typename Parent::Arc Arc; deba@414: deba@416: void first(Node& i) const { deba@416: Parent::first(i); deba@416: while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); deba@414: } deba@414: deba@416: void first(Arc& i) const { deba@416: Parent::first(i); deba@416: while (i != INVALID && (!(*_arc_filter)[i] deba@416: || !(*_node_filter)[Parent::source(i)] deba@416: || !(*_node_filter)[Parent::target(i)])) deba@416: Parent::next(i); deba@414: } deba@414: deba@416: void firstIn(Arc& i, const Node& n) const { deba@416: Parent::firstIn(i, n); deba@416: while (i != INVALID && (!(*_arc_filter)[i] deba@416: || !(*_node_filter)[Parent::source(i)])) deba@416: Parent::nextIn(i); deba@414: } deba@414: deba@416: void firstOut(Arc& i, const Node& n) const { deba@416: Parent::firstOut(i, n); deba@416: while (i != INVALID && (!(*_arc_filter)[i] deba@416: || !(*_node_filter)[Parent::target(i)])) deba@416: Parent::nextOut(i); deba@414: } deba@414: deba@416: void next(Node& i) const { deba@416: Parent::next(i); deba@416: while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); deba@414: } deba@414: deba@416: void next(Arc& i) const { deba@416: Parent::next(i); deba@416: while (i != INVALID && (!(*_arc_filter)[i] deba@416: || !(*_node_filter)[Parent::source(i)] deba@416: || !(*_node_filter)[Parent::target(i)])) deba@416: Parent::next(i); deba@414: } deba@414: deba@416: void nextIn(Arc& i) const { deba@416: Parent::nextIn(i); deba@416: while (i != INVALID && (!(*_arc_filter)[i] deba@416: || !(*_node_filter)[Parent::source(i)])) deba@416: Parent::nextIn(i); deba@414: } deba@414: deba@416: void nextOut(Arc& i) const { deba@416: Parent::nextOut(i); deba@416: while (i != INVALID && (!(*_arc_filter)[i] deba@416: || !(*_node_filter)[Parent::target(i)])) deba@416: Parent::nextOut(i); deba@414: } deba@414: kpeter@452: void status(const Node& n, bool v) const { _node_filter->set(n, v); } kpeter@452: void status(const Arc& a, bool v) const { _arc_filter->set(a, v); } kpeter@452: kpeter@452: bool status(const Node& n) const { return (*_node_filter)[n]; } kpeter@452: bool status(const Arc& a) const { return (*_arc_filter)[a]; } deba@414: deba@414: typedef False NodeNumTag; kpeter@446: typedef False ArcNumTag; kpeter@446: deba@512: typedef FindArcTagIndicator FindArcTag; deba@416: Arc findArc(const Node& source, const Node& target, kpeter@448: const Arc& prev = INVALID) const { deba@414: if (!(*_node_filter)[source] || !(*_node_filter)[target]) { deba@414: return INVALID; deba@414: } deba@414: Arc arc = Parent::findArc(source, target, prev); deba@414: while (arc != INVALID && !(*_arc_filter)[arc]) { deba@414: arc = Parent::findArc(source, target, arc); deba@414: } deba@414: return arc; deba@414: } deba@414: deba@512: public: deba@512: deba@512: template deba@512: class NodeMap deba@512: : public SubMapExtender, deba@512: LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> { deba@414: public: deba@512: typedef V Value; deba@512: typedef SubMapExtender, deba@512: LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent; deba@512: deba@512: NodeMap(const SubDigraphBase& adaptor) deba@512: : Parent(adaptor) {} deba@512: NodeMap(const SubDigraphBase& adaptor, const V& value) deba@512: : Parent(adaptor, value) {} deba@416: deba@414: private: deba@414: NodeMap& operator=(const NodeMap& cmap) { deba@416: return operator=(cmap); deba@414: } deba@416: deba@414: template deba@414: NodeMap& operator=(const CMap& cmap) { deba@512: Parent::operator=(cmap); deba@416: return *this; deba@414: } deba@414: }; deba@414: deba@512: template deba@512: class ArcMap deba@512: : public SubMapExtender, deba@512: LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> { deba@414: public: deba@512: typedef V Value; deba@512: typedef SubMapExtender, deba@512: LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> Parent; deba@512: deba@512: ArcMap(const SubDigraphBase& adaptor) deba@512: : Parent(adaptor) {} deba@512: ArcMap(const SubDigraphBase& adaptor, const V& value) deba@512: : Parent(adaptor, value) {} deba@416: deba@414: private: deba@414: ArcMap& operator=(const ArcMap& cmap) { deba@416: return operator=(cmap); deba@414: } deba@416: deba@414: template deba@414: ArcMap& operator=(const CMap& cmap) { deba@512: Parent::operator=(cmap); deba@416: return *this; deba@414: } deba@414: }; deba@414: deba@414: }; deba@414: deba@512: template deba@512: class SubDigraphBase deba@512: : public DigraphAdaptorBase { deba@414: public: deba@512: typedef DGR Digraph; deba@512: typedef NF NodeFilterMap; deba@512: typedef AF ArcFilterMap; deba@414: deba@416: typedef SubDigraphBase Adaptor; deba@414: typedef DigraphAdaptorBase Parent; deba@414: protected: deba@512: NF* _node_filter; deba@512: AF* _arc_filter; deba@416: SubDigraphBase() deba@414: : Parent(), _node_filter(0), _arc_filter(0) { } deba@414: deba@512: void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) { deba@512: Parent::initialize(digraph); deba@414: _node_filter = &node_filter; deba@512: _arc_filter = &arc_filter; deba@414: } deba@414: deba@414: public: deba@414: deba@414: typedef typename Parent::Node Node; deba@414: typedef typename Parent::Arc Arc; deba@414: deba@416: void first(Node& i) const { deba@416: Parent::first(i); deba@416: while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); deba@414: } deba@414: deba@416: void first(Arc& i) const { deba@416: Parent::first(i); deba@416: while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); deba@414: } deba@414: deba@416: void firstIn(Arc& i, const Node& n) const { deba@416: Parent::firstIn(i, n); deba@416: while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); deba@414: } deba@414: deba@416: void firstOut(Arc& i, const Node& n) const { deba@416: Parent::firstOut(i, n); deba@416: while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); deba@414: } deba@414: deba@416: void next(Node& i) const { deba@416: Parent::next(i); deba@416: while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); deba@414: } deba@416: void next(Arc& i) const { deba@416: Parent::next(i); deba@416: while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); deba@414: } deba@416: void nextIn(Arc& i) const { deba@416: Parent::nextIn(i); deba@416: while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); deba@414: } deba@414: deba@416: void nextOut(Arc& i) const { deba@416: Parent::nextOut(i); deba@416: while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); deba@414: } deba@414: kpeter@452: void status(const Node& n, bool v) const { _node_filter->set(n, v); } kpeter@452: void status(const Arc& a, bool v) const { _arc_filter->set(a, v); } kpeter@452: kpeter@452: bool status(const Node& n) const { return (*_node_filter)[n]; } kpeter@452: bool status(const Arc& a) const { return (*_arc_filter)[a]; } deba@414: deba@414: typedef False NodeNumTag; kpeter@446: typedef False ArcNumTag; kpeter@446: deba@512: typedef FindArcTagIndicator FindArcTag; deba@416: Arc findArc(const Node& source, const Node& target, kpeter@448: const Arc& prev = INVALID) const { deba@414: if (!(*_node_filter)[source] || !(*_node_filter)[target]) { deba@414: return INVALID; deba@414: } deba@414: Arc arc = Parent::findArc(source, target, prev); deba@414: while (arc != INVALID && !(*_arc_filter)[arc]) { deba@414: arc = Parent::findArc(source, target, arc); deba@414: } deba@414: return arc; deba@414: } deba@414: deba@512: template deba@512: class NodeMap deba@512: : public SubMapExtender, deba@512: LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> { deba@414: public: deba@512: typedef V Value; deba@512: typedef SubMapExtender, deba@512: LEMON_SCOPE_FIX(DigraphAdaptorBase, NodeMap)> Parent; deba@512: deba@512: NodeMap(const SubDigraphBase& adaptor) deba@512: : Parent(adaptor) {} deba@512: NodeMap(const SubDigraphBase& adaptor, const V& value) deba@512: : Parent(adaptor, value) {} deba@416: deba@414: private: deba@414: NodeMap& operator=(const NodeMap& cmap) { deba@416: return operator=(cmap); deba@414: } deba@416: deba@414: template deba@414: NodeMap& operator=(const CMap& cmap) { deba@512: Parent::operator=(cmap); deba@416: return *this; deba@414: } deba@414: }; deba@414: deba@512: template deba@512: class ArcMap deba@512: : public SubMapExtender, deba@512: LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> { deba@414: public: deba@512: typedef V Value; deba@512: typedef SubMapExtender, deba@512: LEMON_SCOPE_FIX(DigraphAdaptorBase, ArcMap)> Parent; deba@512: deba@512: ArcMap(const SubDigraphBase& adaptor) deba@512: : Parent(adaptor) {} deba@512: ArcMap(const SubDigraphBase& adaptor, const V& value) deba@512: : Parent(adaptor, value) {} deba@416: deba@414: private: deba@414: ArcMap& operator=(const ArcMap& cmap) { deba@416: return operator=(cmap); deba@414: } deba@416: deba@414: template deba@414: ArcMap& operator=(const CMap& cmap) { deba@512: Parent::operator=(cmap); deba@416: return *this; deba@414: } deba@414: }; deba@414: deba@414: }; deba@414: deba@414: /// \ingroup graph_adaptors deba@414: /// kpeter@451: /// \brief Adaptor class for hiding nodes and arcs in a digraph deba@416: /// kpeter@451: /// SubDigraph can be used for hiding nodes and arcs in a digraph. kpeter@451: /// A \c bool node map and a \c bool arc map must be specified, which kpeter@451: /// define the filters for nodes and arcs. kpeter@451: /// Only the nodes and arcs with \c true filter value are kpeter@453: /// shown in the subdigraph. The arcs that are incident to hidden kpeter@453: /// nodes are also filtered out. kpeter@453: /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept. deba@416: /// kpeter@451: /// The adapted digraph can also be modified through this adaptor kpeter@453: /// by adding or removing nodes or arcs, unless the \c GR template kpeter@451: /// parameter is set to be \c const. kpeter@451: /// deba@512: /// \tparam DGR The type of the adapted digraph. kpeter@451: /// It must conform to the \ref concepts::Digraph "Digraph" concept. kpeter@451: /// It can also be specified to be \c const. kpeter@453: /// \tparam NF The type of the node filter map. kpeter@453: /// It must be a \c bool (or convertible) node map of the kpeter@453: /// adapted digraph. The default type is deba@512: /// \ref concepts::Digraph::NodeMap "DGR::NodeMap". kpeter@453: /// \tparam AF The type of the arc filter map. kpeter@453: /// It must be \c bool (or convertible) arc map of the kpeter@453: /// adapted digraph. The default type is deba@512: /// \ref concepts::Digraph::ArcMap "DGR::ArcMap". kpeter@451: /// kpeter@451: /// \note The \c Node and \c Arc types of this adaptor and the adapted kpeter@451: /// digraph are convertible to each other. deba@416: /// deba@416: /// \see FilterNodes deba@416: /// \see FilterArcs kpeter@451: #ifdef DOXYGEN deba@512: template kpeter@453: class SubDigraph { kpeter@451: #else deba@512: template, deba@512: typename AF = typename DGR::template ArcMap > kpeter@453: class SubDigraph : deba@512: public DigraphAdaptorExtender > { kpeter@451: #endif deba@414: public: kpeter@451: /// The type of the adapted digraph. deba@512: typedef DGR Digraph; kpeter@451: /// The type of the node filter map. kpeter@453: typedef NF NodeFilterMap; kpeter@451: /// The type of the arc filter map. kpeter@453: typedef AF ArcFilterMap; kpeter@453: deba@512: typedef DigraphAdaptorExtender > kpeter@453: Parent; deba@414: deba@415: typedef typename Parent::Node Node; deba@415: typedef typename Parent::Arc Arc; deba@415: deba@414: protected: deba@416: SubDigraph() { } deba@414: public: deba@414: deba@415: /// \brief Constructor deba@415: /// kpeter@451: /// Creates a subdigraph for the given digraph with the kpeter@451: /// given node and arc filter maps. deba@512: SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) { deba@512: Parent::initialize(digraph, node_filter, arc_filter); deba@414: } deba@414: kpeter@452: /// \brief Sets the status of the given node deba@415: /// kpeter@452: /// This function sets the status of the given node. kpeter@451: /// It is done by simply setting the assigned value of \c n kpeter@452: /// to \c v in the node filter map. kpeter@452: void status(const Node& n, bool v) const { Parent::status(n, v); } kpeter@452: kpeter@452: /// \brief Sets the status of the given arc deba@415: /// kpeter@452: /// This function sets the status of the given arc. kpeter@451: /// It is done by simply setting the assigned value of \c a kpeter@452: /// to \c v in the arc filter map. kpeter@452: void status(const Arc& a, bool v) const { Parent::status(a, v); } kpeter@452: kpeter@452: /// \brief Returns the status of the given node deba@415: /// kpeter@452: /// This function returns the status of the given node. kpeter@452: /// It is \c true if the given node is enabled (i.e. not hidden). kpeter@452: bool status(const Node& n) const { return Parent::status(n); } kpeter@452: kpeter@452: /// \brief Returns the status of the given arc deba@415: /// kpeter@452: /// This function returns the status of the given arc. kpeter@452: /// It is \c true if the given arc is enabled (i.e. not hidden). kpeter@452: bool status(const Arc& a) const { return Parent::status(a); } kpeter@452: kpeter@452: /// \brief Disables the given node deba@415: /// kpeter@452: /// This function disables the given node in the subdigraph, kpeter@452: /// so the iteration jumps over it. kpeter@452: /// It is the same as \ref status() "status(n, false)". kpeter@452: void disable(const Node& n) const { Parent::status(n, false); } kpeter@452: kpeter@452: /// \brief Disables the given arc deba@415: /// kpeter@452: /// This function disables the given arc in the subdigraph, kpeter@452: /// so the iteration jumps over it. kpeter@452: /// It is the same as \ref status() "status(a, false)". kpeter@452: void disable(const Arc& a) const { Parent::status(a, false); } kpeter@452: kpeter@452: /// \brief Enables the given node kpeter@452: /// kpeter@452: /// This function enables the given node in the subdigraph. kpeter@452: /// It is the same as \ref status() "status(n, true)". kpeter@452: void enable(const Node& n) const { Parent::status(n, true); } kpeter@452: kpeter@452: /// \brief Enables the given arc kpeter@452: /// kpeter@452: /// This function enables the given arc in the subdigraph. kpeter@452: /// It is the same as \ref status() "status(a, true)". kpeter@452: void enable(const Arc& a) const { Parent::status(a, true); } deba@415: deba@414: }; deba@414: kpeter@451: /// \brief Returns a read-only SubDigraph adaptor deba@414: /// kpeter@451: /// This function just returns a read-only \ref SubDigraph adaptor. kpeter@451: /// \ingroup graph_adaptors kpeter@451: /// \relates SubDigraph deba@512: template deba@512: SubDigraph deba@512: subDigraph(const DGR& digraph, deba@512: NF& node_filter, AF& arc_filter) { deba@512: return SubDigraph deba@512: (digraph, node_filter, arc_filter); deba@414: } deba@414: deba@512: template deba@512: SubDigraph deba@512: subDigraph(const DGR& digraph, deba@512: const NF& node_filter, AF& arc_filter) { deba@512: return SubDigraph deba@512: (digraph, node_filter, arc_filter); deba@414: } deba@414: deba@512: template deba@512: SubDigraph deba@512: subDigraph(const DGR& digraph, deba@512: NF& node_filter, const AF& arc_filter) { deba@512: return SubDigraph deba@512: (digraph, node_filter, arc_filter); deba@414: } deba@414: deba@512: template deba@512: SubDigraph deba@512: subDigraph(const DGR& digraph, deba@512: const NF& node_filter, const AF& arc_filter) { deba@512: return SubDigraph deba@512: (digraph, node_filter, arc_filter); deba@414: } deba@414: deba@414: deba@512: template deba@512: class SubGraphBase : public GraphAdaptorBase { deba@416: public: deba@512: typedef GR Graph; deba@512: typedef NF NodeFilterMap; deba@512: typedef EF EdgeFilterMap; kpeter@449: deba@416: typedef SubGraphBase Adaptor; deba@512: typedef GraphAdaptorBase Parent; deba@416: protected: deba@416: deba@512: NF* _node_filter; deba@512: EF* _edge_filter; deba@416: deba@416: SubGraphBase() deba@512: : Parent(), _node_filter(0), _edge_filter(0) { } deba@512: deba@512: void initialize(GR& graph, NF& node_filter, EF& edge_filter) { deba@512: Parent::initialize(graph); deba@512: _node_filter = &node_filter; deba@512: _edge_filter = &edge_filter; deba@416: } deba@416: deba@416: public: deba@416: deba@416: typedef typename Parent::Node Node; deba@416: typedef typename Parent::Arc Arc; deba@416: typedef typename Parent::Edge Edge; deba@416: deba@416: void first(Node& i) const { deba@416: Parent::first(i); deba@512: while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); deba@416: } deba@416: deba@416: void first(Arc& i) const { deba@416: Parent::first(i); deba@512: while (i!=INVALID && (!(*_edge_filter)[i] deba@512: || !(*_node_filter)[Parent::source(i)] deba@512: || !(*_node_filter)[Parent::target(i)])) deba@416: Parent::next(i); deba@416: } deba@416: deba@416: void first(Edge& i) const { deba@416: Parent::first(i); deba@512: while (i!=INVALID && (!(*_edge_filter)[i] deba@512: || !(*_node_filter)[Parent::u(i)] deba@512: || !(*_node_filter)[Parent::v(i)])) deba@416: Parent::next(i); deba@416: } deba@416: deba@416: void firstIn(Arc& i, const Node& n) const { deba@416: Parent::firstIn(i, n); deba@512: while (i!=INVALID && (!(*_edge_filter)[i] deba@512: || !(*_node_filter)[Parent::source(i)])) deba@416: Parent::nextIn(i); deba@416: } deba@416: deba@416: void firstOut(Arc& i, const Node& n) const { deba@416: Parent::firstOut(i, n); deba@512: while (i!=INVALID && (!(*_edge_filter)[i] deba@512: || !(*_node_filter)[Parent::target(i)])) deba@416: Parent::nextOut(i); deba@416: } deba@416: deba@416: void firstInc(Edge& i, bool& d, const Node& n) const { deba@416: Parent::firstInc(i, d, n); deba@512: while (i!=INVALID && (!(*_edge_filter)[i] deba@512: || !(*_node_filter)[Parent::u(i)] deba@512: || !(*_node_filter)[Parent::v(i)])) deba@416: Parent::nextInc(i, d); deba@416: } deba@416: deba@416: void next(Node& i) const { deba@416: Parent::next(i); deba@512: while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); deba@416: } deba@416: deba@416: void next(Arc& i) const { deba@416: Parent::next(i); deba@512: while (i!=INVALID && (!(*_edge_filter)[i] deba@512: || !(*_node_filter)[Parent::source(i)] deba@512: || !(*_node_filter)[Parent::target(i)])) deba@416: Parent::next(i); deba@416: } deba@416: deba@416: void next(Edge& i) const { deba@416: Parent::next(i); deba@512: while (i!=INVALID && (!(*_edge_filter)[i] deba@512: || !(*_node_filter)[Parent::u(i)] deba@512: || !(*_node_filter)[Parent::v(i)])) deba@416: Parent::next(i); deba@416: } deba@416: deba@416: void nextIn(Arc& i) const { deba@416: Parent::nextIn(i); deba@512: while (i!=INVALID && (!(*_edge_filter)[i] deba@512: || !(*_node_filter)[Parent::source(i)])) deba@416: Parent::nextIn(i); deba@416: } deba@416: deba@416: void nextOut(Arc& i) const { deba@416: Parent::nextOut(i); deba@512: while (i!=INVALID && (!(*_edge_filter)[i] deba@512: || !(*_node_filter)[Parent::target(i)])) deba@416: Parent::nextOut(i); deba@416: } deba@416: deba@416: void nextInc(Edge& i, bool& d) const { deba@416: Parent::nextInc(i, d); deba@512: while (i!=INVALID && (!(*_edge_filter)[i] deba@512: || !(*_node_filter)[Parent::u(i)] deba@512: || !(*_node_filter)[Parent::v(i)])) deba@416: Parent::nextInc(i, d); deba@416: } deba@416: deba@512: void status(const Node& n, bool v) const { _node_filter->set(n, v); } deba@512: void status(const Edge& e, bool v) const { _edge_filter->set(e, v); } deba@512: deba@512: bool status(const Node& n) const { return (*_node_filter)[n]; } deba@512: bool status(const Edge& e) const { return (*_edge_filter)[e]; } deba@416: deba@416: typedef False NodeNumTag; kpeter@446: typedef False ArcNumTag; deba@416: typedef False EdgeNumTag; deba@416: kpeter@446: typedef FindArcTagIndicator FindArcTag; deba@416: Arc findArc(const Node& u, const Node& v, kpeter@448: const Arc& prev = INVALID) const { deba@512: if (!(*_node_filter)[u] || !(*_node_filter)[v]) { deba@416: return INVALID; deba@416: } deba@416: Arc arc = Parent::findArc(u, v, prev); deba@512: while (arc != INVALID && !(*_edge_filter)[arc]) { deba@416: arc = Parent::findArc(u, v, arc); deba@416: } deba@416: return arc; deba@416: } kpeter@446: kpeter@446: typedef FindEdgeTagIndicator FindEdgeTag; deba@416: Edge findEdge(const Node& u, const Node& v, kpeter@448: const Edge& prev = INVALID) const { deba@512: if (!(*_node_filter)[u] || !(*_node_filter)[v]) { deba@416: return INVALID; deba@416: } deba@416: Edge edge = Parent::findEdge(u, v, prev); deba@512: while (edge != INVALID && !(*_edge_filter)[edge]) { deba@416: edge = Parent::findEdge(u, v, edge); deba@416: } deba@416: return edge; deba@416: } deba@416: deba@512: template deba@512: class NodeMap deba@512: : public SubMapExtender, deba@512: LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> { deba@416: public: deba@512: typedef V Value; deba@512: typedef SubMapExtender, deba@512: LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent; deba@512: deba@512: NodeMap(const SubGraphBase& adaptor) deba@512: : Parent(adaptor) {} deba@512: NodeMap(const SubGraphBase& adaptor, const V& value) deba@512: : Parent(adaptor, value) {} deba@416: deba@416: private: deba@416: NodeMap& operator=(const NodeMap& cmap) { deba@416: return operator=(cmap); deba@416: } deba@416: deba@416: template deba@416: NodeMap& operator=(const CMap& cmap) { deba@512: Parent::operator=(cmap); deba@416: return *this; deba@416: } deba@416: }; deba@416: deba@512: template deba@512: class ArcMap deba@512: : public SubMapExtender, deba@512: LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> { deba@416: public: deba@512: typedef V Value; deba@512: typedef SubMapExtender, deba@512: LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent; deba@512: deba@512: ArcMap(const SubGraphBase& adaptor) deba@512: : Parent(adaptor) {} deba@512: ArcMap(const SubGraphBase& adaptor, const V& value) deba@512: : Parent(adaptor, value) {} deba@416: deba@416: private: deba@416: ArcMap& operator=(const ArcMap& cmap) { deba@416: return operator=(cmap); deba@416: } deba@416: deba@416: template deba@416: ArcMap& operator=(const CMap& cmap) { deba@512: Parent::operator=(cmap); deba@416: return *this; deba@416: } deba@416: }; deba@416: deba@512: template deba@512: class EdgeMap deba@512: : public SubMapExtender, deba@512: LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> { deba@416: public: deba@512: typedef V Value; deba@512: typedef SubMapExtender, deba@512: LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent; deba@512: deba@512: EdgeMap(const SubGraphBase& adaptor) deba@512: : Parent(adaptor) {} deba@512: deba@512: EdgeMap(const SubGraphBase& adaptor, const V& value) deba@512: : Parent(adaptor, value) {} deba@416: deba@416: private: deba@416: EdgeMap& operator=(const EdgeMap& cmap) { deba@416: return operator=(cmap); deba@416: } deba@416: deba@416: template deba@416: EdgeMap& operator=(const CMap& cmap) { deba@512: Parent::operator=(cmap); deba@416: return *this; deba@416: } deba@416: }; deba@416: deba@416: }; deba@416: deba@512: template deba@512: class SubGraphBase deba@512: : public GraphAdaptorBase { deba@416: public: deba@512: typedef GR Graph; deba@512: typedef NF NodeFilterMap; deba@512: typedef EF EdgeFilterMap; kpeter@449: deba@416: typedef SubGraphBase Adaptor; deba@512: typedef GraphAdaptorBase Parent; deba@416: protected: deba@512: NF* _node_filter; deba@512: EF* _edge_filter; deba@512: SubGraphBase() deba@512: : Parent(), _node_filter(0), _edge_filter(0) { } deba@512: deba@512: void initialize(GR& graph, NF& node_filter, EF& edge_filter) { deba@512: Parent::initialize(graph); deba@512: _node_filter = &node_filter; deba@512: _edge_filter = &edge_filter; deba@416: } deba@416: deba@416: public: deba@416: deba@416: typedef typename Parent::Node Node; deba@416: typedef typename Parent::Arc Arc; deba@416: typedef typename Parent::Edge Edge; deba@416: deba@416: void first(Node& i) const { deba@416: Parent::first(i); deba@512: while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); deba@416: } deba@416: deba@416: void first(Arc& i) const { deba@416: Parent::first(i); deba@512: while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); deba@416: } deba@416: deba@416: void first(Edge& i) const { deba@416: Parent::first(i); deba@512: while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); deba@416: } deba@416: deba@416: void firstIn(Arc& i, const Node& n) const { deba@416: Parent::firstIn(i, n); deba@512: while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i); deba@416: } deba@416: deba@416: void firstOut(Arc& i, const Node& n) const { deba@416: Parent::firstOut(i, n); deba@512: while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i); deba@416: } deba@416: deba@416: void firstInc(Edge& i, bool& d, const Node& n) const { deba@416: Parent::firstInc(i, d, n); deba@512: while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d); deba@416: } deba@416: deba@416: void next(Node& i) const { deba@416: Parent::next(i); deba@512: while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); deba@416: } deba@416: void next(Arc& i) const { deba@416: Parent::next(i); deba@512: while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); deba@416: } deba@416: void next(Edge& i) const { deba@416: Parent::next(i); deba@512: while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); deba@416: } deba@416: void nextIn(Arc& i) const { deba@416: Parent::nextIn(i); deba@512: while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i); deba@416: } deba@416: deba@416: void nextOut(Arc& i) const { deba@416: Parent::nextOut(i); deba@512: while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i); deba@416: } deba@416: void nextInc(Edge& i, bool& d) const { deba@416: Parent::nextInc(i, d); deba@512: while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d); deba@416: } deba@416: deba@512: void status(const Node& n, bool v) const { _node_filter->set(n, v); } deba@512: void status(const Edge& e, bool v) const { _edge_filter->set(e, v); } deba@512: deba@512: bool status(const Node& n) const { return (*_node_filter)[n]; } deba@512: bool status(const Edge& e) const { return (*_edge_filter)[e]; } deba@416: deba@416: typedef False NodeNumTag; kpeter@446: typedef False ArcNumTag; deba@416: typedef False EdgeNumTag; deba@416: kpeter@446: typedef FindArcTagIndicator FindArcTag; deba@416: Arc findArc(const Node& u, const Node& v, kpeter@448: const Arc& prev = INVALID) const { deba@416: Arc arc = Parent::findArc(u, v, prev); deba@512: while (arc != INVALID && !(*_edge_filter)[arc]) { deba@416: arc = Parent::findArc(u, v, arc); deba@416: } deba@416: return arc; deba@416: } kpeter@446: kpeter@446: typedef FindEdgeTagIndicator FindEdgeTag; deba@416: Edge findEdge(const Node& u, const Node& v, kpeter@448: const Edge& prev = INVALID) const { deba@416: Edge edge = Parent::findEdge(u, v, prev); deba@512: while (edge != INVALID && !(*_edge_filter)[edge]) { deba@416: edge = Parent::findEdge(u, v, edge); deba@416: } deba@416: return edge; deba@416: } deba@416: deba@512: template deba@512: class NodeMap deba@512: : public SubMapExtender, deba@512: LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> { deba@416: public: deba@512: typedef V Value; deba@512: typedef SubMapExtender, deba@512: LEMON_SCOPE_FIX(GraphAdaptorBase, NodeMap)> Parent; deba@512: deba@512: NodeMap(const SubGraphBase& adaptor) deba@512: : Parent(adaptor) {} deba@512: NodeMap(const SubGraphBase& adaptor, const V& value) deba@512: : Parent(adaptor, value) {} deba@416: deba@416: private: deba@416: NodeMap& operator=(const NodeMap& cmap) { deba@416: return operator=(cmap); deba@416: } deba@416: deba@416: template deba@416: NodeMap& operator=(const CMap& cmap) { deba@512: Parent::operator=(cmap); deba@416: return *this; deba@416: } deba@416: }; deba@416: deba@512: template deba@512: class ArcMap deba@512: : public SubMapExtender, deba@512: LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> { deba@416: public: deba@512: typedef V Value; deba@512: typedef SubMapExtender, deba@512: LEMON_SCOPE_FIX(GraphAdaptorBase, ArcMap)> Parent; deba@512: deba@512: ArcMap(const SubGraphBase& adaptor) deba@512: : Parent(adaptor) {} deba@512: ArcMap(const SubGraphBase& adaptor, const V& value) deba@512: : Parent(adaptor, value) {} deba@416: deba@416: private: deba@416: ArcMap& operator=(const ArcMap& cmap) { deba@416: return operator=(cmap); deba@416: } deba@416: deba@416: template deba@416: ArcMap& operator=(const CMap& cmap) { deba@512: Parent::operator=(cmap); deba@416: return *this; deba@416: } deba@416: }; deba@416: deba@512: template deba@512: class EdgeMap deba@512: : public SubMapExtender, deba@512: LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> { deba@416: public: deba@512: typedef V Value; deba@512: typedef SubMapExtender, deba@512: LEMON_SCOPE_FIX(GraphAdaptorBase, EdgeMap)> Parent; deba@512: deba@512: EdgeMap(const SubGraphBase& adaptor) deba@512: : Parent(adaptor) {} deba@512: deba@512: EdgeMap(const SubGraphBase& adaptor, const V& value) deba@512: : Parent(adaptor, value) {} deba@416: deba@416: private: deba@416: EdgeMap& operator=(const EdgeMap& cmap) { deba@416: return operator=(cmap); deba@416: } deba@416: deba@416: template deba@416: EdgeMap& operator=(const CMap& cmap) { deba@512: Parent::operator=(cmap); deba@416: return *this; deba@416: } deba@416: }; deba@416: deba@416: }; deba@416: deba@416: /// \ingroup graph_adaptors deba@414: /// kpeter@451: /// \brief Adaptor class for hiding nodes and edges in an undirected kpeter@451: /// graph. deba@414: /// kpeter@451: /// SubGraph can be used for hiding nodes and edges in a graph. kpeter@451: /// A \c bool node map and a \c bool edge map must be specified, which kpeter@451: /// define the filters for nodes and edges. kpeter@451: /// Only the nodes and edges with \c true filter value are kpeter@453: /// shown in the subgraph. The edges that are incident to hidden kpeter@453: /// nodes are also filtered out. kpeter@453: /// This adaptor conforms to the \ref concepts::Graph "Graph" concept. deba@416: /// kpeter@451: /// The adapted graph can also be modified through this adaptor kpeter@453: /// by adding or removing nodes or edges, unless the \c GR template kpeter@451: /// parameter is set to be \c const. kpeter@451: /// kpeter@453: /// \tparam GR The type of the adapted graph. kpeter@451: /// It must conform to the \ref concepts::Graph "Graph" concept. kpeter@451: /// It can also be specified to be \c const. kpeter@453: /// \tparam NF The type of the node filter map. kpeter@453: /// It must be a \c bool (or convertible) node map of the kpeter@453: /// adapted graph. The default type is kpeter@453: /// \ref concepts::Graph::NodeMap "GR::NodeMap". kpeter@453: /// \tparam EF The type of the edge filter map. kpeter@453: /// It must be a \c bool (or convertible) edge map of the kpeter@453: /// adapted graph. The default type is kpeter@453: /// \ref concepts::Graph::EdgeMap "GR::EdgeMap". kpeter@451: /// kpeter@451: /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the kpeter@451: /// adapted graph are convertible to each other. deba@416: /// deba@416: /// \see FilterNodes deba@416: /// \see FilterEdges kpeter@451: #ifdef DOXYGEN kpeter@453: template kpeter@453: class SubGraph { kpeter@451: #else kpeter@453: template, kpeter@453: typename EF = typename GR::template EdgeMap > kpeter@453: class SubGraph : kpeter@453: public GraphAdaptorExtender > { kpeter@451: #endif deba@414: public: kpeter@451: /// The type of the adapted graph. kpeter@453: typedef GR Graph; kpeter@451: /// The type of the node filter map. kpeter@453: typedef NF NodeFilterMap; kpeter@451: /// The type of the edge filter map. kpeter@453: typedef EF EdgeFilterMap; kpeter@453: deba@512: typedef GraphAdaptorExtender > kpeter@453: Parent; deba@414: deba@415: typedef typename Parent::Node Node; deba@416: typedef typename Parent::Edge Edge; deba@415: deba@414: protected: deba@416: SubGraph() { } deba@414: public: deba@414: deba@415: /// \brief Constructor deba@415: /// kpeter@451: /// Creates a subgraph for the given graph with the given node kpeter@451: /// and edge filter maps. deba@512: SubGraph(GR& graph, NF& node_filter, EF& edge_filter) { deba@512: initialize(graph, node_filter, edge_filter); deba@414: } deba@414: kpeter@452: /// \brief Sets the status of the given node deba@415: /// kpeter@452: /// This function sets the status of the given node. kpeter@451: /// It is done by simply setting the assigned value of \c n kpeter@452: /// to \c v in the node filter map. kpeter@452: void status(const Node& n, bool v) const { Parent::status(n, v); } kpeter@452: kpeter@452: /// \brief Sets the status of the given edge deba@416: /// kpeter@452: /// This function sets the status of the given edge. kpeter@451: /// It is done by simply setting the assigned value of \c e kpeter@452: /// to \c v in the edge filter map. kpeter@452: void status(const Edge& e, bool v) const { Parent::status(e, v); } kpeter@452: kpeter@452: /// \brief Returns the status of the given node deba@415: /// kpeter@452: /// This function returns the status of the given node. kpeter@452: /// It is \c true if the given node is enabled (i.e. not hidden). kpeter@452: bool status(const Node& n) const { return Parent::status(n); } kpeter@452: kpeter@452: /// \brief Returns the status of the given edge deba@416: /// kpeter@452: /// This function returns the status of the given edge. kpeter@452: /// It is \c true if the given edge is enabled (i.e. not hidden). kpeter@452: bool status(const Edge& e) const { return Parent::status(e); } kpeter@452: kpeter@452: /// \brief Disables the given node deba@415: /// kpeter@452: /// This function disables the given node in the subdigraph, kpeter@452: /// so the iteration jumps over it. kpeter@452: /// It is the same as \ref status() "status(n, false)". kpeter@452: void disable(const Node& n) const { Parent::status(n, false); } kpeter@452: kpeter@452: /// \brief Disables the given edge deba@415: /// kpeter@452: /// This function disables the given edge in the subgraph, kpeter@452: /// so the iteration jumps over it. kpeter@452: /// It is the same as \ref status() "status(e, false)". kpeter@452: void disable(const Edge& e) const { Parent::status(e, false); } kpeter@452: kpeter@452: /// \brief Enables the given node kpeter@452: /// kpeter@452: /// This function enables the given node in the subdigraph. kpeter@452: /// It is the same as \ref status() "status(n, true)". kpeter@452: void enable(const Node& n) const { Parent::status(n, true); } kpeter@452: kpeter@452: /// \brief Enables the given edge kpeter@452: /// kpeter@452: /// This function enables the given edge in the subgraph. kpeter@452: /// It is the same as \ref status() "status(e, true)". kpeter@452: void enable(const Edge& e) const { Parent::status(e, true); } kpeter@452: deba@414: }; deba@414: kpeter@451: /// \brief Returns a read-only SubGraph adaptor deba@414: /// kpeter@451: /// This function just returns a read-only \ref SubGraph adaptor. kpeter@451: /// \ingroup graph_adaptors kpeter@451: /// \relates SubGraph kpeter@453: template kpeter@453: SubGraph deba@512: subGraph(const GR& graph, NF& node_filter, EF& edge_filter) { kpeter@453: return SubGraph deba@512: (graph, node_filter, edge_filter); deba@416: } deba@416: kpeter@453: template kpeter@453: SubGraph deba@512: subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) { kpeter@453: return SubGraph deba@512: (graph, node_filter, edge_filter); deba@416: } deba@416: kpeter@453: template kpeter@453: SubGraph deba@512: subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) { kpeter@453: return SubGraph deba@512: (graph, node_filter, edge_filter); deba@416: } deba@416: kpeter@453: template kpeter@453: SubGraph deba@512: subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) { kpeter@453: return SubGraph deba@512: (graph, node_filter, edge_filter); deba@416: } deba@416: kpeter@451: deba@416: /// \ingroup graph_adaptors deba@416: /// kpeter@451: /// \brief Adaptor class for hiding nodes in a digraph or a graph. deba@416: /// kpeter@451: /// FilterNodes adaptor can be used for hiding nodes in a digraph or a kpeter@451: /// graph. A \c bool node map must be specified, which defines the filter kpeter@451: /// for the nodes. Only the nodes with \c true filter value and the kpeter@451: /// arcs/edges incident to nodes both with \c true filter value are shown kpeter@451: /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph kpeter@451: /// "Digraph" concept or the \ref concepts::Graph "Graph" concept kpeter@453: /// depending on the \c GR template parameter. deba@416: /// kpeter@451: /// The adapted (di)graph can also be modified through this adaptor kpeter@453: /// by adding or removing nodes or arcs/edges, unless the \c GR template kpeter@451: /// parameter is set to be \c const. kpeter@451: /// kpeter@453: /// \tparam GR The type of the adapted digraph or graph. kpeter@451: /// It must conform to the \ref concepts::Digraph "Digraph" concept kpeter@451: /// or the \ref concepts::Graph "Graph" concept. kpeter@451: /// It can also be specified to be \c const. kpeter@453: /// \tparam NF The type of the node filter map. kpeter@453: /// It must be a \c bool (or convertible) node map of the kpeter@453: /// adapted (di)graph. The default type is kpeter@453: /// \ref concepts::Graph::NodeMap "GR::NodeMap". kpeter@451: /// kpeter@451: /// \note The \c Node and Arc/Edge types of this adaptor and the kpeter@451: /// adapted (di)graph are convertible to each other. deba@416: #ifdef DOXYGEN kpeter@453: template kpeter@453: class FilterNodes { deba@416: #else kpeter@453: template, deba@416: typename Enable = void> kpeter@453: class FilterNodes : kpeter@453: public DigraphAdaptorExtender< deba@512: SubDigraphBase >, deba@512: true> > { deba@416: #endif deba@416: public: deba@416: kpeter@453: typedef GR Digraph; kpeter@453: typedef NF NodeFilterMap; kpeter@453: kpeter@453: typedef DigraphAdaptorExtender< deba@512: SubDigraphBase >, deba@512: true> > Parent; deba@416: deba@416: typedef typename Parent::Node Node; deba@416: deba@416: protected: deba@512: ConstMap > const_true_map; deba@512: deba@512: FilterNodes() : const_true_map() {} deba@416: deba@416: public: deba@416: deba@416: /// \brief Constructor deba@416: /// kpeter@451: /// Creates a subgraph for the given digraph or graph with the deba@416: /// given node filter map. deba@512: FilterNodes(GR& graph, NF& node_filter) deba@512: : Parent(), const_true_map() kpeter@453: { deba@512: Parent::initialize(graph, node_filter, const_true_map); deba@416: } deba@416: kpeter@452: /// \brief Sets the status of the given node deba@416: /// kpeter@452: /// This function sets the status of the given node. kpeter@451: /// It is done by simply setting the assigned value of \c n kpeter@452: /// to \c v in the node filter map. kpeter@452: void status(const Node& n, bool v) const { Parent::status(n, v); } kpeter@452: kpeter@452: /// \brief Returns the status of the given node deba@416: /// kpeter@452: /// This function returns the status of the given node. kpeter@452: /// It is \c true if the given node is enabled (i.e. not hidden). kpeter@452: bool status(const Node& n) const { return Parent::status(n); } kpeter@452: kpeter@452: /// \brief Disables the given node deba@416: /// kpeter@452: /// This function disables the given node, so the iteration kpeter@452: /// jumps over it. kpeter@452: /// It is the same as \ref status() "status(n, false)". kpeter@452: void disable(const Node& n) const { Parent::status(n, false); } kpeter@452: kpeter@452: /// \brief Enables the given node kpeter@452: /// kpeter@452: /// This function enables the given node. kpeter@452: /// It is the same as \ref status() "status(n, true)". kpeter@452: void enable(const Node& n) const { Parent::status(n, true); } deba@416: deba@416: }; deba@416: kpeter@453: template kpeter@453: class FilterNodes >::type> : kpeter@453: public GraphAdaptorExtender< deba@512: SubGraphBase >, deba@512: true> > { kpeter@453: deba@416: public: kpeter@453: typedef GR Graph; kpeter@453: typedef NF NodeFilterMap; kpeter@453: typedef GraphAdaptorExtender< deba@512: SubGraphBase >, deba@512: true> > Parent; deba@416: deba@416: typedef typename Parent::Node Node; deba@416: protected: deba@512: ConstMap > const_true_map; deba@512: deba@512: FilterNodes() : const_true_map() {} deba@416: deba@416: public: deba@416: deba@512: FilterNodes(GR& graph, NodeFilterMap& node_filter) : deba@512: Parent(), const_true_map() { deba@512: Parent::initialize(graph, node_filter, const_true_map); deba@416: } deba@416: kpeter@452: void status(const Node& n, bool v) const { Parent::status(n, v); } kpeter@452: bool status(const Node& n) const { return Parent::status(n); } kpeter@452: void disable(const Node& n) const { Parent::status(n, false); } kpeter@452: void enable(const Node& n) const { Parent::status(n, true); } deba@416: deba@416: }; deba@416: deba@416: kpeter@451: /// \brief Returns a read-only FilterNodes adaptor deba@416: /// kpeter@451: /// This function just returns a read-only \ref FilterNodes adaptor. kpeter@451: /// \ingroup graph_adaptors kpeter@451: /// \relates FilterNodes kpeter@453: template kpeter@453: FilterNodes deba@512: filterNodes(const GR& graph, NF& node_filter) { deba@512: return FilterNodes(graph, node_filter); deba@414: } deba@414: kpeter@453: template kpeter@453: FilterNodes deba@512: filterNodes(const GR& graph, const NF& node_filter) { deba@512: return FilterNodes(graph, node_filter); deba@414: } deba@414: deba@416: /// \ingroup graph_adaptors deba@414: /// kpeter@451: /// \brief Adaptor class for hiding arcs in a digraph. deba@414: /// kpeter@451: /// FilterArcs adaptor can be used for hiding arcs in a digraph. kpeter@451: /// A \c bool arc map must be specified, which defines the filter for kpeter@451: /// the arcs. Only the arcs with \c true filter value are shown in the kpeter@451: /// subdigraph. This adaptor conforms to the \ref concepts::Digraph kpeter@451: /// "Digraph" concept. deba@414: /// kpeter@451: /// The adapted digraph can also be modified through this adaptor kpeter@453: /// by adding or removing nodes or arcs, unless the \c GR template kpeter@451: /// parameter is set to be \c const. kpeter@451: /// deba@512: /// \tparam DGR The type of the adapted digraph. kpeter@451: /// It must conform to the \ref concepts::Digraph "Digraph" concept. kpeter@451: /// It can also be specified to be \c const. kpeter@453: /// \tparam AF The type of the arc filter map. kpeter@453: /// It must be a \c bool (or convertible) arc map of the kpeter@453: /// adapted digraph. The default type is deba@512: /// \ref concepts::Digraph::ArcMap "DGR::ArcMap". kpeter@451: /// kpeter@451: /// \note The \c Node and \c Arc types of this adaptor and the adapted kpeter@451: /// digraph are convertible to each other. kpeter@451: #ifdef DOXYGEN deba@512: template kpeter@453: class FilterArcs { kpeter@451: #else deba@512: template > kpeter@453: class FilterArcs : kpeter@453: public DigraphAdaptorExtender< deba@512: SubDigraphBase >, deba@512: AF, false> > { kpeter@451: #endif deba@414: public: kpeter@453: /// The type of the adapted digraph. deba@512: typedef DGR Digraph; kpeter@453: /// The type of the arc filter map. kpeter@453: typedef AF ArcFilterMap; kpeter@453: kpeter@453: typedef DigraphAdaptorExtender< deba@512: SubDigraphBase >, deba@512: AF, false> > Parent; deba@415: deba@415: typedef typename Parent::Arc Arc; deba@415: deba@414: protected: deba@512: ConstMap > const_true_map; deba@512: deba@512: FilterArcs() : const_true_map() {} deba@414: deba@414: public: deba@414: deba@415: /// \brief Constructor deba@415: /// kpeter@451: /// Creates a subdigraph for the given digraph with the given arc kpeter@451: /// filter map. deba@512: FilterArcs(DGR& digraph, ArcFilterMap& arc_filter) deba@512: : Parent(), const_true_map() { deba@512: Parent::initialize(digraph, const_true_map, arc_filter); deba@414: } deba@414: kpeter@452: /// \brief Sets the status of the given arc deba@415: /// kpeter@452: /// This function sets the status of the given arc. kpeter@451: /// It is done by simply setting the assigned value of \c a kpeter@452: /// to \c v in the arc filter map. kpeter@452: void status(const Arc& a, bool v) const { Parent::status(a, v); } kpeter@452: kpeter@452: /// \brief Returns the status of the given arc deba@415: /// kpeter@452: /// This function returns the status of the given arc. kpeter@452: /// It is \c true if the given arc is enabled (i.e. not hidden). kpeter@452: bool status(const Arc& a) const { return Parent::status(a); } kpeter@452: kpeter@452: /// \brief Disables the given arc deba@415: /// kpeter@452: /// This function disables the given arc in the subdigraph, kpeter@452: /// so the iteration jumps over it. kpeter@452: /// It is the same as \ref status() "status(a, false)". kpeter@452: void disable(const Arc& a) const { Parent::status(a, false); } kpeter@452: kpeter@452: /// \brief Enables the given arc kpeter@452: /// kpeter@452: /// This function enables the given arc in the subdigraph. kpeter@452: /// It is the same as \ref status() "status(a, true)". kpeter@452: void enable(const Arc& a) const { Parent::status(a, true); } deba@415: deba@414: }; deba@414: kpeter@451: /// \brief Returns a read-only FilterArcs adaptor deba@414: /// kpeter@451: /// This function just returns a read-only \ref FilterArcs adaptor. kpeter@451: /// \ingroup graph_adaptors kpeter@451: /// \relates FilterArcs deba@512: template deba@512: FilterArcs deba@512: filterArcs(const DGR& digraph, AF& arc_filter) { deba@512: return FilterArcs(digraph, arc_filter); deba@414: } deba@414: deba@512: template deba@512: FilterArcs deba@512: filterArcs(const DGR& digraph, const AF& arc_filter) { deba@512: return FilterArcs(digraph, arc_filter); deba@414: } deba@414: deba@416: /// \ingroup graph_adaptors deba@416: /// kpeter@451: /// \brief Adaptor class for hiding edges in a graph. deba@416: /// kpeter@451: /// FilterEdges adaptor can be used for hiding edges in a graph. kpeter@451: /// A \c bool edge map must be specified, which defines the filter for kpeter@451: /// the edges. Only the edges with \c true filter value are shown in the kpeter@451: /// subgraph. This adaptor conforms to the \ref concepts::Graph kpeter@451: /// "Graph" concept. deba@416: /// kpeter@451: /// The adapted graph can also be modified through this adaptor kpeter@453: /// by adding or removing nodes or edges, unless the \c GR template kpeter@451: /// parameter is set to be \c const. kpeter@451: /// kpeter@453: /// \tparam GR The type of the adapted graph. kpeter@451: /// It must conform to the \ref concepts::Graph "Graph" concept. kpeter@451: /// It can also be specified to be \c const. kpeter@453: /// \tparam EF The type of the edge filter map. kpeter@453: /// It must be a \c bool (or convertible) edge map of the kpeter@453: /// adapted graph. The default type is kpeter@453: /// \ref concepts::Graph::EdgeMap "GR::EdgeMap". kpeter@451: /// kpeter@451: /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the kpeter@451: /// adapted graph are convertible to each other. kpeter@451: #ifdef DOXYGEN kpeter@453: template kpeter@453: class FilterEdges { kpeter@451: #else kpeter@453: template > kpeter@453: class FilterEdges : kpeter@453: public GraphAdaptorExtender< deba@512: SubGraphBase >, deba@512: EF, false> > { kpeter@451: #endif deba@416: public: kpeter@453: /// The type of the adapted graph. kpeter@453: typedef GR Graph; kpeter@453: /// The type of the edge filter map. kpeter@453: typedef EF EdgeFilterMap; kpeter@453: kpeter@453: typedef GraphAdaptorExtender< deba@512: SubGraphBase >, deba@512: EF, false> > Parent; kpeter@453: deba@416: typedef typename Parent::Edge Edge; kpeter@453: deba@416: protected: deba@512: ConstMap > const_true_map; deba@416: deba@416: FilterEdges() : const_true_map(true) { deba@416: Parent::setNodeFilterMap(const_true_map); deba@416: } deba@416: deba@416: public: deba@416: deba@416: /// \brief Constructor deba@416: /// kpeter@451: /// Creates a subgraph for the given graph with the given edge kpeter@451: /// filter map. deba@512: FilterEdges(GR& graph, EF& edge_filter) deba@512: : Parent(), const_true_map() { deba@512: Parent::initialize(graph, const_true_map, edge_filter); deba@416: } deba@416: kpeter@452: /// \brief Sets the status of the given edge deba@416: /// kpeter@452: /// This function sets the status of the given edge. kpeter@451: /// It is done by simply setting the assigned value of \c e kpeter@452: /// to \c v in the edge filter map. kpeter@452: void status(const Edge& e, bool v) const { Parent::status(e, v); } kpeter@452: kpeter@452: /// \brief Returns the status of the given edge deba@416: /// kpeter@452: /// This function returns the status of the given edge. kpeter@452: /// It is \c true if the given edge is enabled (i.e. not hidden). kpeter@452: bool status(const Edge& e) const { return Parent::status(e); } kpeter@452: kpeter@452: /// \brief Disables the given edge deba@416: /// kpeter@452: /// This function disables the given edge in the subgraph, kpeter@452: /// so the iteration jumps over it. kpeter@452: /// It is the same as \ref status() "status(e, false)". kpeter@452: void disable(const Edge& e) const { Parent::status(e, false); } kpeter@452: kpeter@452: /// \brief Enables the given edge kpeter@452: /// kpeter@452: /// This function enables the given edge in the subgraph. kpeter@452: /// It is the same as \ref status() "status(e, true)". kpeter@452: void enable(const Edge& e) const { Parent::status(e, true); } deba@416: deba@416: }; deba@416: kpeter@451: /// \brief Returns a read-only FilterEdges adaptor deba@416: /// kpeter@451: /// This function just returns a read-only \ref FilterEdges adaptor. kpeter@451: /// \ingroup graph_adaptors kpeter@451: /// \relates FilterEdges kpeter@453: template kpeter@453: FilterEdges deba@512: filterEdges(const GR& graph, EF& edge_filter) { deba@512: return FilterEdges(graph, edge_filter); deba@416: } deba@416: kpeter@453: template kpeter@453: FilterEdges deba@512: filterEdges(const GR& graph, const EF& edge_filter) { deba@512: return FilterEdges(graph, edge_filter); deba@416: } deba@416: kpeter@451: deba@512: template deba@416: class UndirectorBase { deba@414: public: deba@512: typedef DGR Digraph; deba@416: typedef UndirectorBase Adaptor; deba@414: deba@414: typedef True UndirectedTag; deba@414: deba@414: typedef typename Digraph::Arc Edge; deba@414: typedef typename Digraph::Node Node; deba@414: deba@414: class Arc : public Edge { deba@416: friend class UndirectorBase; deba@414: protected: deba@414: bool _forward; deba@414: deba@414: Arc(const Edge& edge, bool forward) : deba@414: Edge(edge), _forward(forward) {} deba@414: deba@414: public: deba@414: Arc() {} deba@414: deba@414: Arc(Invalid) : Edge(INVALID), _forward(true) {} deba@414: deba@414: bool operator==(const Arc &other) const { deba@416: return _forward == other._forward && deba@416: static_cast(*this) == static_cast(other); deba@414: } deba@414: bool operator!=(const Arc &other) const { deba@416: return _forward != other._forward || deba@416: static_cast(*this) != static_cast(other); deba@414: } deba@414: bool operator<(const Arc &other) const { deba@416: return _forward < other._forward || deba@416: (_forward == other._forward && deba@416: static_cast(*this) < static_cast(other)); deba@414: } deba@414: }; deba@414: deba@414: void first(Node& n) const { deba@414: _digraph->first(n); deba@414: } deba@414: deba@414: void next(Node& n) const { deba@414: _digraph->next(n); deba@414: } deba@414: deba@414: void first(Arc& a) const { deba@414: _digraph->first(a); deba@414: a._forward = true; deba@414: } deba@414: deba@414: void next(Arc& a) const { deba@414: if (a._forward) { deba@416: a._forward = false; deba@414: } else { deba@416: _digraph->next(a); deba@416: a._forward = true; deba@414: } deba@414: } deba@414: deba@414: void first(Edge& e) const { deba@414: _digraph->first(e); deba@414: } deba@414: deba@414: void next(Edge& e) const { deba@414: _digraph->next(e); deba@414: } deba@414: deba@414: void firstOut(Arc& a, const Node& n) const { deba@414: _digraph->firstIn(a, n); deba@414: if( static_cast(a) != INVALID ) { deba@416: a._forward = false; deba@414: } else { deba@416: _digraph->firstOut(a, n); deba@416: a._forward = true; deba@414: } deba@414: } deba@414: void nextOut(Arc &a) const { deba@414: if (!a._forward) { deba@416: Node n = _digraph->target(a); deba@416: _digraph->nextIn(a); deba@416: if (static_cast(a) == INVALID ) { deba@416: _digraph->firstOut(a, n); deba@416: a._forward = true; deba@416: } deba@414: } deba@414: else { deba@416: _digraph->nextOut(a); deba@414: } deba@414: } deba@414: deba@414: void firstIn(Arc &a, const Node &n) const { deba@414: _digraph->firstOut(a, n); deba@414: if (static_cast(a) != INVALID ) { deba@416: a._forward = false; deba@414: } else { deba@416: _digraph->firstIn(a, n); deba@416: a._forward = true; deba@414: } deba@414: } deba@414: void nextIn(Arc &a) const { deba@414: if (!a._forward) { deba@416: Node n = _digraph->source(a); deba@416: _digraph->nextOut(a); deba@416: if( static_cast(a) == INVALID ) { deba@416: _digraph->firstIn(a, n); deba@416: a._forward = true; deba@416: } deba@414: } deba@414: else { deba@416: _digraph->nextIn(a); deba@414: } deba@414: } deba@414: deba@414: void firstInc(Edge &e, bool &d, const Node &n) const { deba@414: d = true; deba@414: _digraph->firstOut(e, n); deba@414: if (e != INVALID) return; deba@414: d = false; deba@414: _digraph->firstIn(e, n); deba@414: } deba@414: deba@414: void nextInc(Edge &e, bool &d) const { deba@414: if (d) { deba@416: Node s = _digraph->source(e); deba@416: _digraph->nextOut(e); deba@416: if (e != INVALID) return; deba@416: d = false; deba@416: _digraph->firstIn(e, s); deba@414: } else { deba@416: _digraph->nextIn(e); deba@414: } deba@414: } deba@414: deba@414: Node u(const Edge& e) const { deba@414: return _digraph->source(e); deba@414: } deba@414: deba@414: Node v(const Edge& e) const { deba@414: return _digraph->target(e); deba@414: } deba@414: deba@414: Node source(const Arc &a) const { deba@414: return a._forward ? _digraph->source(a) : _digraph->target(a); deba@414: } deba@414: deba@414: Node target(const Arc &a) const { deba@414: return a._forward ? _digraph->target(a) : _digraph->source(a); deba@414: } deba@414: deba@414: static Arc direct(const Edge &e, bool d) { deba@414: return Arc(e, d); deba@414: } deba@414: Arc direct(const Edge &e, const Node& n) const { deba@414: return Arc(e, _digraph->source(e) == n); deba@414: } deba@414: deba@414: static bool direction(const Arc &a) { return a._forward; } deba@414: deba@414: Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); } deba@414: Arc arcFromId(int ix) const { deba@414: return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1)); deba@414: } deba@414: Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); } deba@414: deba@414: int id(const Node &n) const { return _digraph->id(n); } deba@414: int id(const Arc &a) const { deba@414: return (_digraph->id(a) << 1) | (a._forward ? 1 : 0); deba@414: } deba@414: int id(const Edge &e) const { return _digraph->id(e); } deba@414: deba@414: int maxNodeId() const { return _digraph->maxNodeId(); } deba@414: int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; } deba@414: int maxEdgeId() const { return _digraph->maxArcId(); } deba@414: deba@414: Node addNode() { return _digraph->addNode(); } deba@416: Edge addEdge(const Node& u, const Node& v) { deba@416: return _digraph->addArc(u, v); deba@414: } deba@414: deba@414: void erase(const Node& i) { _digraph->erase(i); } deba@414: void erase(const Edge& i) { _digraph->erase(i); } deba@416: deba@414: void clear() { _digraph->clear(); } deba@414: deba@414: typedef NodeNumTagIndicator NodeNumTag; kpeter@449: int nodeNum() const { return _digraph->nodeNum(); } kpeter@446: kpeter@446: typedef ArcNumTagIndicator ArcNumTag; deba@414: int arcNum() const { return 2 * _digraph->arcNum(); } kpeter@446: kpeter@446: typedef ArcNumTag EdgeNumTag; deba@414: int edgeNum() const { return _digraph->arcNum(); } deba@414: kpeter@446: typedef FindArcTagIndicator FindArcTag; deba@414: Arc findArc(Node s, Node t, Arc p = INVALID) const { deba@414: if (p == INVALID) { deba@416: Edge arc = _digraph->findArc(s, t); deba@416: if (arc != INVALID) return direct(arc, true); deba@416: arc = _digraph->findArc(t, s); deba@416: if (arc != INVALID) return direct(arc, false); deba@414: } else if (direction(p)) { deba@416: Edge arc = _digraph->findArc(s, t, p); deba@416: if (arc != INVALID) return direct(arc, true); deba@416: arc = _digraph->findArc(t, s); deba@416: if (arc != INVALID) return direct(arc, false); deba@414: } else { deba@416: Edge arc = _digraph->findArc(t, s, p); deba@416: if (arc != INVALID) return direct(arc, false); deba@414: } deba@414: return INVALID; deba@414: } deba@414: kpeter@446: typedef FindArcTag FindEdgeTag; deba@414: Edge findEdge(Node s, Node t, Edge p = INVALID) const { deba@414: if (s != t) { deba@414: if (p == INVALID) { deba@414: Edge arc = _digraph->findArc(s, t); deba@414: if (arc != INVALID) return arc; deba@414: arc = _digraph->findArc(t, s); deba@414: if (arc != INVALID) return arc; kpeter@449: } else if (_digraph->source(p) == s) { deba@414: Edge arc = _digraph->findArc(s, t, p); deba@414: if (arc != INVALID) return arc; deba@414: arc = _digraph->findArc(t, s); deba@416: if (arc != INVALID) return arc; deba@414: } else { deba@414: Edge arc = _digraph->findArc(t, s, p); deba@416: if (arc != INVALID) return arc; deba@414: } deba@414: } else { deba@414: return _digraph->findArc(s, t, p); deba@414: } deba@414: return INVALID; deba@414: } deba@414: deba@414: private: deba@416: deba@512: template deba@414: class ArcMapBase { deba@414: private: deba@416: deba@512: typedef typename DGR::template ArcMap MapImpl; deba@416: deba@414: public: deba@414: deba@414: typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; deba@414: deba@512: typedef V Value; deba@414: typedef Arc Key; kpeter@449: typedef typename MapTraits::ConstReturnValue ConstReturnValue; kpeter@449: typedef typename MapTraits::ReturnValue ReturnValue; kpeter@449: typedef typename MapTraits::ConstReturnValue ConstReference; kpeter@449: typedef typename MapTraits::ReturnValue Reference; deba@416: deba@512: ArcMapBase(const UndirectorBase& adaptor) : deba@416: _forward(*adaptor._digraph), _backward(*adaptor._digraph) {} deba@416: deba@512: ArcMapBase(const UndirectorBase& adaptor, const V& value) deba@512: : _forward(*adaptor._digraph, value), deba@512: _backward(*adaptor._digraph, value) {} deba@512: deba@512: void set(const Arc& a, const V& value) { deba@416: if (direction(a)) { deba@512: _forward.set(a, value); deba@416: } else { deba@512: _backward.set(a, value); deba@414: } deba@414: } deba@414: kpeter@449: ConstReturnValue operator[](const Arc& a) const { deba@416: if (direction(a)) { deba@416: return _forward[a]; deba@416: } else { deba@416: return _backward[a]; deba@414: } deba@414: } deba@414: kpeter@449: ReturnValue operator[](const Arc& a) { deba@416: if (direction(a)) { deba@416: return _forward[a]; deba@416: } else { deba@416: return _backward[a]; deba@416: } deba@416: } deba@416: deba@414: protected: deba@414: deba@416: MapImpl _forward, _backward; deba@414: deba@414: }; deba@414: deba@414: public: deba@414: deba@512: template deba@512: class NodeMap : public DGR::template NodeMap { deba@414: public: deba@414: deba@512: typedef V Value; deba@512: typedef typename DGR::template NodeMap Parent; deba@512: deba@512: explicit NodeMap(const UndirectorBase& adaptor) deba@416: : Parent(*adaptor._digraph) {} deba@414: deba@512: NodeMap(const UndirectorBase& adaptor, const V& value) deba@416: : Parent(*adaptor._digraph, value) { } deba@414: deba@414: private: deba@414: NodeMap& operator=(const NodeMap& cmap) { deba@414: return operator=(cmap); deba@414: } deba@414: deba@414: template deba@414: NodeMap& operator=(const CMap& cmap) { deba@414: Parent::operator=(cmap); deba@414: return *this; deba@414: } deba@416: deba@414: }; deba@414: deba@512: template deba@416: class ArcMap deba@512: : public SubMapExtender, ArcMapBase > deba@414: { deba@414: public: deba@512: typedef V Value; deba@512: typedef SubMapExtender > Parent; deba@512: deba@512: explicit ArcMap(const UndirectorBase& adaptor) deba@416: : Parent(adaptor) {} deba@416: deba@512: ArcMap(const UndirectorBase& adaptor, const V& value) deba@416: : Parent(adaptor, value) {} deba@416: deba@414: private: deba@414: ArcMap& operator=(const ArcMap& cmap) { deba@416: return operator=(cmap); deba@414: } deba@416: deba@414: template deba@414: ArcMap& operator=(const CMap& cmap) { deba@414: Parent::operator=(cmap); deba@416: return *this; deba@414: } deba@414: }; deba@416: deba@512: template deba@512: class EdgeMap : public Digraph::template ArcMap { deba@414: public: deba@416: deba@512: typedef V Value; deba@512: typedef typename Digraph::template ArcMap Parent; deba@512: deba@512: explicit EdgeMap(const UndirectorBase& adaptor) deba@416: : Parent(*adaptor._digraph) {} deba@414: deba@512: EdgeMap(const UndirectorBase& adaptor, const V& value) deba@416: : Parent(*adaptor._digraph, value) {} deba@414: deba@414: private: deba@414: EdgeMap& operator=(const EdgeMap& cmap) { deba@414: return operator=(cmap); deba@414: } deba@414: deba@414: template deba@414: EdgeMap& operator=(const CMap& cmap) { deba@414: Parent::operator=(cmap); deba@414: return *this; deba@414: } deba@414: deba@414: }; deba@414: deba@512: typedef typename ItemSetTraits::ItemNotifier NodeNotifier; deba@416: NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } deba@414: deba@512: typedef typename ItemSetTraits::ItemNotifier EdgeNotifier; kpeter@449: EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); } kpeter@449: deba@414: protected: deba@414: deba@416: UndirectorBase() : _digraph(0) {} deba@414: deba@512: DGR* _digraph; deba@512: deba@512: void initialize(DGR& digraph) { deba@414: _digraph = &digraph; deba@414: } deba@416: deba@414: }; deba@414: deba@416: /// \ingroup graph_adaptors deba@414: /// kpeter@451: /// \brief Adaptor class for viewing a digraph as an undirected graph. deba@414: /// kpeter@451: /// Undirector adaptor can be used for viewing a digraph as an undirected kpeter@451: /// graph. All arcs of the underlying digraph are showed in the kpeter@451: /// adaptor as an edge (and also as a pair of arcs, of course). kpeter@451: /// This adaptor conforms to the \ref concepts::Graph "Graph" concept. deba@414: /// kpeter@451: /// The adapted digraph can also be modified through this adaptor kpeter@453: /// by adding or removing nodes or edges, unless the \c GR template kpeter@451: /// parameter is set to be \c const. kpeter@451: /// deba@512: /// \tparam DGR The type of the adapted digraph. kpeter@451: /// It must conform to the \ref concepts::Digraph "Digraph" concept. kpeter@451: /// It can also be specified to be \c const. kpeter@451: /// kpeter@451: /// \note The \c Node type of this adaptor and the adapted digraph are kpeter@451: /// convertible to each other, moreover the \c Edge type of the adaptor kpeter@451: /// and the \c Arc type of the adapted digraph are also convertible to kpeter@451: /// each other. kpeter@451: /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type kpeter@451: /// of the adapted digraph.) deba@512: template kpeter@453: #ifdef DOXYGEN kpeter@453: class Undirector { kpeter@453: #else kpeter@453: class Undirector : deba@512: public GraphAdaptorExtender > { kpeter@453: #endif deba@414: public: kpeter@453: /// The type of the adapted digraph. deba@512: typedef DGR Digraph; deba@512: typedef GraphAdaptorExtender > Parent; deba@414: protected: deba@416: Undirector() { } deba@414: public: deba@414: deba@414: /// \brief Constructor deba@414: /// kpeter@451: /// Creates an undirected graph from the given digraph. deba@512: Undirector(DGR& digraph) { deba@512: initialize(digraph); deba@414: } deba@414: kpeter@451: /// \brief Arc map combined from two original arc maps deba@414: /// kpeter@451: /// This map adaptor class adapts two arc maps of the underlying kpeter@451: /// digraph to get an arc map of the undirected graph. kpeter@451: /// Its value type is inherited from the first arc map type kpeter@451: /// (\c %ForwardMap). kpeter@453: template deba@414: class CombinedArcMap { deba@414: public: deba@416: kpeter@451: /// The key type of the map kpeter@451: typedef typename Parent::Arc Key; kpeter@451: /// The value type of the map deba@414: typedef typename ForwardMap::Value Value; deba@414: kpeter@453: typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; kpeter@453: kpeter@449: typedef typename MapTraits::ReturnValue ReturnValue; kpeter@449: typedef typename MapTraits::ConstReturnValue ConstReturnValue; kpeter@449: typedef typename MapTraits::ReturnValue Reference; kpeter@449: typedef typename MapTraits::ConstReturnValue ConstReference; kpeter@449: deba@416: /// Constructor deba@416: CombinedArcMap(ForwardMap& forward, BackwardMap& backward) deba@414: : _forward(&forward), _backward(&backward) {} deba@416: kpeter@451: /// Sets the value associated with the given key. deba@416: void set(const Key& e, const Value& a) { deba@416: if (Parent::direction(e)) { deba@416: _forward->set(e, a); deba@416: } else { deba@416: _backward->set(e, a); deba@416: } deba@414: } deba@414: kpeter@451: /// Returns the value associated with the given key. kpeter@449: ConstReturnValue operator[](const Key& e) const { deba@416: if (Parent::direction(e)) { deba@416: return (*_forward)[e]; deba@416: } else { deba@416: return (*_backward)[e]; deba@414: } deba@414: } deba@414: kpeter@451: /// Returns a reference to the value associated with the given key. kpeter@449: ReturnValue operator[](const Key& e) { deba@416: if (Parent::direction(e)) { deba@416: return (*_forward)[e]; deba@416: } else { deba@416: return (*_backward)[e]; deba@414: } deba@414: } deba@414: deba@416: protected: deba@416: deba@416: ForwardMap* _forward; deba@416: BackwardMap* _backward; deba@416: deba@416: }; deba@416: kpeter@451: /// \brief Returns a combined arc map deba@416: /// kpeter@451: /// This function just returns a combined arc map. deba@416: template deba@416: static CombinedArcMap deba@416: combinedArcMap(ForwardMap& forward, BackwardMap& backward) { deba@416: return CombinedArcMap(forward, backward); deba@416: } deba@416: deba@416: template deba@416: static CombinedArcMap deba@416: combinedArcMap(const ForwardMap& forward, BackwardMap& backward) { deba@416: return CombinedArcMap(forward, backward); deba@416: } deba@416: deba@416: template deba@416: static CombinedArcMap deba@416: combinedArcMap(ForwardMap& forward, const BackwardMap& backward) { deba@416: return CombinedArcMap(forward, backward); deba@416: } deba@416: deba@416: template deba@416: static CombinedArcMap deba@416: combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) { deba@416: return CombinedArcMap(forward, backward); deba@416: } deba@416: deba@416: }; deba@416: kpeter@451: /// \brief Returns a read-only Undirector adaptor deba@416: /// kpeter@451: /// This function just returns a read-only \ref Undirector adaptor. kpeter@451: /// \ingroup graph_adaptors kpeter@451: /// \relates Undirector deba@512: template deba@512: Undirector undirector(const DGR& digraph) { deba@512: return Undirector(digraph); deba@416: } deba@416: kpeter@451: deba@512: template deba@416: class OrienterBase { deba@416: public: deba@416: deba@512: typedef GR Graph; deba@512: typedef DM DirectionMap; deba@512: deba@512: typedef typename GR::Node Node; deba@512: typedef typename GR::Edge Arc; deba@416: deba@416: void reverseArc(const Arc& arc) { deba@416: _direction->set(arc, !(*_direction)[arc]); deba@416: } deba@416: deba@416: void first(Node& i) const { _graph->first(i); } deba@416: void first(Arc& i) const { _graph->first(i); } deba@416: void firstIn(Arc& i, const Node& n) const { kpeter@447: bool d = true; deba@416: _graph->firstInc(i, d, n); deba@416: while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d); deba@416: } deba@416: void firstOut(Arc& i, const Node& n ) const { kpeter@447: bool d = true; deba@416: _graph->firstInc(i, d, n); deba@416: while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d); deba@416: } deba@416: deba@416: void next(Node& i) const { _graph->next(i); } deba@416: void next(Arc& i) const { _graph->next(i); } deba@416: void nextIn(Arc& i) const { deba@416: bool d = !(*_direction)[i]; deba@416: _graph->nextInc(i, d); deba@416: while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d); deba@416: } deba@416: void nextOut(Arc& i) const { deba@416: bool d = (*_direction)[i]; deba@416: _graph->nextInc(i, d); deba@416: while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d); deba@416: } deba@416: deba@416: Node source(const Arc& e) const { deba@416: return (*_direction)[e] ? _graph->u(e) : _graph->v(e); deba@416: } deba@416: Node target(const Arc& e) const { deba@416: return (*_direction)[e] ? _graph->v(e) : _graph->u(e); deba@416: } deba@416: deba@416: typedef NodeNumTagIndicator NodeNumTag; deba@416: int nodeNum() const { return _graph->nodeNum(); } deba@416: kpeter@446: typedef EdgeNumTagIndicator ArcNumTag; deba@416: int arcNum() const { return _graph->edgeNum(); } deba@416: kpeter@446: typedef FindEdgeTagIndicator FindArcTag; deba@416: Arc findArc(const Node& u, const Node& v, kpeter@448: const Arc& prev = INVALID) const { kpeter@449: Arc arc = _graph->findEdge(u, v, prev); kpeter@449: while (arc != INVALID && source(arc) != u) { deba@416: arc = _graph->findEdge(u, v, arc); deba@414: } deba@416: return arc; deba@416: } deba@416: deba@416: Node addNode() { deba@416: return Node(_graph->addNode()); deba@416: } deba@416: deba@416: Arc addArc(const Node& u, const Node& v) { kpeter@449: Arc arc = _graph->addEdge(u, v); kpeter@449: _direction->set(arc, _graph->u(arc) == u); deba@416: return arc; deba@416: } deba@416: deba@416: void erase(const Node& i) { _graph->erase(i); } deba@416: void erase(const Arc& i) { _graph->erase(i); } deba@416: deba@416: void clear() { _graph->clear(); } deba@416: deba@416: int id(const Node& v) const { return _graph->id(v); } deba@416: int id(const Arc& e) const { return _graph->id(e); } deba@416: deba@416: Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); } deba@416: Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); } deba@416: deba@416: int maxNodeId() const { return _graph->maxNodeId(); } deba@416: int maxArcId() const { return _graph->maxEdgeId(); } deba@416: deba@512: typedef typename ItemSetTraits::ItemNotifier NodeNotifier; deba@416: NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } deba@416: deba@512: typedef typename ItemSetTraits::ItemNotifier ArcNotifier; deba@416: ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } deba@416: deba@512: template deba@512: class NodeMap : public GR::template NodeMap { deba@416: public: deba@416: deba@512: typedef typename GR::template NodeMap Parent; deba@512: deba@512: explicit NodeMap(const OrienterBase& adapter) deba@416: : Parent(*adapter._graph) {} deba@416: deba@512: NodeMap(const OrienterBase& adapter, const V& value) deba@416: : Parent(*adapter._graph, value) {} deba@416: deba@416: private: deba@416: NodeMap& operator=(const NodeMap& cmap) { deba@416: return operator=(cmap); deba@416: } deba@416: deba@416: template deba@416: NodeMap& operator=(const CMap& cmap) { deba@416: Parent::operator=(cmap); deba@416: return *this; deba@416: } deba@414: deba@414: }; deba@414: deba@512: template deba@512: class ArcMap : public GR::template EdgeMap { deba@416: public: deba@416: deba@512: typedef typename Graph::template EdgeMap Parent; deba@512: deba@512: explicit ArcMap(const OrienterBase& adapter) deba@416: : Parent(*adapter._graph) { } deba@416: deba@512: ArcMap(const OrienterBase& adapter, const V& value) deba@416: : Parent(*adapter._graph, value) { } deba@416: deba@416: private: deba@416: ArcMap& operator=(const ArcMap& cmap) { deba@416: return operator=(cmap); deba@416: } deba@416: deba@416: template deba@416: ArcMap& operator=(const CMap& cmap) { deba@416: Parent::operator=(cmap); deba@416: return *this; deba@416: } deba@416: }; deba@416: deba@416: deba@416: deba@416: protected: deba@416: Graph* _graph; deba@512: DM* _direction; deba@512: deba@512: void initialize(GR& graph, DM& direction) { deba@512: _graph = &graph; deba@416: _direction = &direction; deba@416: } deba@416: deba@414: }; deba@414: deba@416: /// \ingroup graph_adaptors deba@414: /// kpeter@451: /// \brief Adaptor class for orienting the edges of a graph to get a digraph deba@416: /// kpeter@451: /// Orienter adaptor can be used for orienting the edges of a graph to kpeter@451: /// get a digraph. A \c bool edge map of the underlying graph must be kpeter@451: /// specified, which define the direction of the arcs in the adaptor. kpeter@451: /// The arcs can be easily reversed by the \c reverseArc() member function kpeter@451: /// of the adaptor. kpeter@451: /// This class conforms to the \ref concepts::Digraph "Digraph" concept. deba@416: /// kpeter@451: /// The adapted graph can also be modified through this adaptor kpeter@453: /// by adding or removing nodes or arcs, unless the \c GR template kpeter@451: /// parameter is set to be \c const. deba@416: /// kpeter@453: /// \tparam GR The type of the adapted graph. kpeter@451: /// It must conform to the \ref concepts::Graph "Graph" concept. kpeter@451: /// It can also be specified to be \c const. kpeter@453: /// \tparam DM The type of the direction map. kpeter@453: /// It must be a \c bool (or convertible) edge map of the kpeter@453: /// adapted graph. The default type is kpeter@453: /// \ref concepts::Graph::EdgeMap "GR::EdgeMap". kpeter@451: /// kpeter@451: /// \note The \c Node type of this adaptor and the adapted graph are kpeter@451: /// convertible to each other, moreover the \c Arc type of the adaptor kpeter@451: /// and the \c Edge type of the adapted graph are also convertible to kpeter@451: /// each other. kpeter@451: #ifdef DOXYGEN kpeter@453: template kpeter@453: class Orienter { kpeter@451: #else kpeter@453: template > kpeter@453: class Orienter : kpeter@453: public DigraphAdaptorExtender > { kpeter@451: #endif deba@416: public: kpeter@451: kpeter@451: /// The type of the adapted graph. kpeter@453: typedef GR Graph; kpeter@451: /// The type of the direction edge map. kpeter@453: typedef DM DirectionMap; kpeter@453: kpeter@453: typedef DigraphAdaptorExtender > Parent; deba@416: typedef typename Parent::Arc Arc; deba@416: protected: deba@416: Orienter() { } deba@416: public: deba@416: kpeter@451: /// \brief Constructor deba@416: /// kpeter@451: /// Constructor of the adaptor. deba@512: Orienter(GR& graph, DM& direction) { deba@512: Parent::initialize(graph, direction); deba@416: } deba@416: kpeter@451: /// \brief Reverses the given arc deba@416: /// kpeter@451: /// This function reverses the given arc. kpeter@451: /// It is done by simply negate the assigned value of \c a kpeter@451: /// in the direction map. deba@416: void reverseArc(const Arc& a) { deba@416: Parent::reverseArc(a); deba@416: } deba@416: }; deba@416: kpeter@451: /// \brief Returns a read-only Orienter adaptor deba@416: /// kpeter@451: /// This function just returns a read-only \ref Orienter adaptor. kpeter@451: /// \ingroup graph_adaptors kpeter@451: /// \relates Orienter kpeter@453: template kpeter@453: Orienter deba@512: orienter(const GR& graph, DM& direction) { deba@512: return Orienter(graph, direction); deba@414: } deba@414: kpeter@453: template kpeter@453: Orienter deba@512: orienter(const GR& graph, const DM& direction) { deba@512: return Orienter(graph, direction); deba@416: } deba@416: deba@416: namespace _adaptor_bits { deba@416: deba@512: template deba@416: class ResForwardFilter { deba@416: public: deba@416: deba@512: typedef typename DGR::Arc Key; deba@416: typedef bool Value; deba@416: deba@416: private: deba@416: deba@512: const CM* _capacity; deba@512: const FM* _flow; deba@512: TL _tolerance; deba@512: deba@416: public: deba@416: deba@512: ResForwardFilter(const CM& capacity, const FM& flow, deba@512: const TL& tolerance = TL()) deba@416: : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } deba@416: deba@512: bool operator[](const typename DGR::Arc& a) const { deba@416: return _tolerance.positive((*_capacity)[a] - (*_flow)[a]); deba@416: } deba@416: }; deba@416: deba@512: template deba@416: class ResBackwardFilter { deba@416: public: deba@416: deba@512: typedef typename DGR::Arc Key; deba@416: typedef bool Value; deba@416: deba@416: private: deba@416: deba@512: const CM* _capacity; deba@512: const FM* _flow; deba@512: TL _tolerance; deba@416: deba@416: public: deba@416: deba@512: ResBackwardFilter(const CM& capacity, const FM& flow, deba@512: const TL& tolerance = TL()) deba@416: : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } deba@416: deba@512: bool operator[](const typename DGR::Arc& a) const { deba@416: return _tolerance.positive((*_flow)[a]); deba@416: } deba@416: }; deba@416: deba@416: } deba@416: deba@416: /// \ingroup graph_adaptors deba@416: /// kpeter@451: /// \brief Adaptor class for composing the residual digraph for directed deba@416: /// flow and circulation problems. deba@416: /// kpeter@464: /// ResidualDigraph can be used for composing the \e residual digraph kpeter@464: /// for directed flow and circulation problems. Let \f$ G=(V, A) \f$ kpeter@464: /// be a directed graph and let \f$ F \f$ be a number type. kpeter@464: /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs. kpeter@451: /// This adaptor implements a digraph structure with node set \f$ V \f$ kpeter@451: /// and arc set \f$ A_{forward}\cup A_{backward} \f$, kpeter@451: /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)0\} \f$, i.e. the so kpeter@451: /// called residual digraph. kpeter@451: /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken, kpeter@451: /// multiplicities are counted, i.e. the adaptor has exactly kpeter@451: /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel kpeter@451: /// arcs). kpeter@451: /// This class conforms to the \ref concepts::Digraph "Digraph" concept. deba@416: /// deba@512: /// \tparam DGR The type of the adapted digraph. kpeter@451: /// It must conform to the \ref concepts::Digraph "Digraph" concept. kpeter@451: /// It is implicitly \c const. kpeter@453: /// \tparam CM The type of the capacity map. kpeter@453: /// It must be an arc map of some numerical type, which defines kpeter@451: /// the capacities in the flow problem. It is implicitly \c const. kpeter@453: /// The default type is kpeter@453: /// \ref concepts::Digraph::ArcMap "GR::ArcMap". kpeter@453: /// \tparam FM The type of the flow map. kpeter@453: /// It must be an arc map of some numerical type, which defines kpeter@453: /// the flow values in the flow problem. The default type is \c CM. kpeter@453: /// \tparam TL The tolerance type for handling inexact computation. kpeter@451: /// The default tolerance type depends on the value type of the kpeter@451: /// capacity map. deba@416: /// kpeter@451: /// \note This adaptor is implemented using Undirector and FilterArcs kpeter@451: /// adaptors. kpeter@451: /// kpeter@451: /// \note The \c Node type of this adaptor and the adapted digraph are kpeter@451: /// convertible to each other, moreover the \c Arc type of the adaptor kpeter@451: /// is convertible to the \c Arc type of the adapted digraph. kpeter@451: #ifdef DOXYGEN deba@512: template kpeter@464: class ResidualDigraph kpeter@451: #else deba@512: template, kpeter@453: typename FM = CM, kpeter@453: typename TL = Tolerance > deba@512: class ResidualDigraph deba@512: : public SubDigraph< deba@512: Undirector, deba@512: ConstMap >, deba@512: typename Undirector::template CombinedArcMap< deba@512: _adaptor_bits::ResForwardFilter, deba@512: _adaptor_bits::ResBackwardFilter > > kpeter@451: #endif deba@416: { deba@414: public: deba@414: kpeter@451: /// The type of the underlying digraph. deba@512: typedef DGR Digraph; kpeter@451: /// The type of the capacity map. kpeter@453: typedef CM CapacityMap; kpeter@451: /// The type of the flow map. kpeter@453: typedef FM FlowMap; kpeter@453: /// The tolerance type. kpeter@453: typedef TL Tolerance; deba@414: deba@414: typedef typename CapacityMap::Value Value; kpeter@464: typedef ResidualDigraph Adaptor; deba@414: deba@414: protected: deba@414: deba@416: typedef Undirector Undirected; deba@416: deba@512: typedef ConstMap > NodeFilter; deba@512: deba@512: typedef _adaptor_bits::ResForwardFilter ForwardFilter; deba@512: deba@512: typedef _adaptor_bits::ResBackwardFilter BackwardFilter; deba@416: deba@416: typedef typename Undirected:: kpeter@453: template CombinedArcMap ArcFilter; deba@414: deba@512: typedef SubDigraph Parent; deba@414: deba@414: const CapacityMap* _capacity; deba@414: FlowMap* _flow; deba@414: deba@416: Undirected _graph; deba@512: NodeFilter _node_filter; deba@414: ForwardFilter _forward_filter; deba@414: BackwardFilter _backward_filter; deba@414: ArcFilter _arc_filter; deba@414: deba@414: public: deba@414: kpeter@451: /// \brief Constructor deba@414: /// kpeter@451: /// Constructor of the residual digraph adaptor. The parameters are the kpeter@451: /// digraph, the capacity map, the flow map, and a tolerance object. deba@512: ResidualDigraph(const DGR& digraph, const CM& capacity, deba@512: FM& flow, const TL& tolerance = Tolerance()) deba@512: : Parent(), _capacity(&capacity), _flow(&flow), deba@512: _graph(digraph), _node_filter(), deba@416: _forward_filter(capacity, flow, tolerance), deba@414: _backward_filter(capacity, flow, tolerance), deba@414: _arc_filter(_forward_filter, _backward_filter) deba@414: { deba@512: Parent::initialize(_graph, _node_filter, _arc_filter); deba@414: } deba@414: deba@414: typedef typename Parent::Arc Arc; deba@414: kpeter@451: /// \brief Returns the residual capacity of the given arc. deba@414: /// kpeter@451: /// Returns the residual capacity of the given arc. deba@416: Value residualCapacity(const Arc& a) const { deba@416: if (Undirected::direction(a)) { deba@416: return (*_capacity)[a] - (*_flow)[a]; deba@414: } else { deba@416: return (*_flow)[a]; deba@414: } deba@416: } deba@416: kpeter@452: /// \brief Augments on the given arc in the residual digraph. deba@414: /// kpeter@452: /// Augments on the given arc in the residual digraph. It increases kpeter@451: /// or decreases the flow value on the original arc according to the kpeter@451: /// direction of the residual arc. deba@416: void augment(const Arc& a, const Value& v) const { deba@416: if (Undirected::direction(a)) { deba@416: _flow->set(a, (*_flow)[a] + v); deba@416: } else { deba@416: _flow->set(a, (*_flow)[a] - v); deba@414: } deba@414: } deba@414: kpeter@451: /// \brief Returns \c true if the given residual arc is a forward arc. deba@414: /// kpeter@451: /// Returns \c true if the given residual arc has the same orientation kpeter@451: /// as the original arc, i.e. it is a so called forward arc. deba@416: static bool forward(const Arc& a) { deba@416: return Undirected::direction(a); deba@414: } deba@414: kpeter@451: /// \brief Returns \c true if the given residual arc is a backward arc. deba@414: /// kpeter@451: /// Returns \c true if the given residual arc has the opposite orientation kpeter@451: /// than the original arc, i.e. it is a so called backward arc. deba@416: static bool backward(const Arc& a) { deba@416: return !Undirected::direction(a); deba@414: } deba@414: kpeter@451: /// \brief Returns the forward oriented residual arc. deba@414: /// kpeter@451: /// Returns the forward oriented residual arc related to the given kpeter@451: /// arc of the underlying digraph. deba@416: static Arc forward(const typename Digraph::Arc& a) { deba@416: return Undirected::direct(a, true); deba@414: } deba@414: kpeter@451: /// \brief Returns the backward oriented residual arc. deba@414: /// kpeter@451: /// Returns the backward oriented residual arc related to the given kpeter@451: /// arc of the underlying digraph. deba@416: static Arc backward(const typename Digraph::Arc& a) { deba@416: return Undirected::direct(a, false); deba@414: } deba@414: deba@414: /// \brief Residual capacity map. deba@414: /// kpeter@451: /// This map adaptor class can be used for obtaining the residual kpeter@451: /// capacities as an arc map of the residual digraph. kpeter@451: /// Its value type is inherited from the capacity map. deba@416: class ResidualCapacity { deba@414: protected: deba@414: const Adaptor* _adaptor; deba@414: public: kpeter@451: /// The key type of the map deba@414: typedef Arc Key; kpeter@451: /// The value type of the map kpeter@453: typedef typename CapacityMap::Value Value; deba@414: deba@416: /// Constructor deba@512: ResidualCapacity(const ResidualDigraph& adaptor) deba@512: : _adaptor(&adaptor) {} deba@416: kpeter@451: /// Returns the value associated with the given residual arc deba@416: Value operator[](const Arc& a) const { deba@416: return _adaptor->residualCapacity(a); deba@414: } deba@416: deba@414: }; deba@414: kpeter@450: /// \brief Returns a residual capacity map kpeter@450: /// kpeter@450: /// This function just returns a residual capacity map. kpeter@450: ResidualCapacity residualCapacity() const { kpeter@450: return ResidualCapacity(*this); kpeter@450: } kpeter@450: deba@414: }; deba@414: kpeter@450: /// \brief Returns a (read-only) Residual adaptor kpeter@450: /// deba@512: /// This function just returns a (read-only) \ref ResidualDigraph adaptor. kpeter@450: /// \ingroup graph_adaptors deba@512: /// \relates ResidualDigraph deba@512: template deba@512: ResidualDigraph deba@512: residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) { deba@512: return ResidualDigraph (digraph, capacity_map, flow_map); kpeter@450: } kpeter@450: kpeter@450: deba@512: template deba@416: class SplitNodesBase { deba@414: public: deba@414: deba@512: typedef DGR Digraph; deba@512: typedef DigraphAdaptorBase Parent; deba@416: typedef SplitNodesBase Adaptor; deba@414: deba@512: typedef typename DGR::Node DigraphNode; deba@512: typedef typename DGR::Arc DigraphArc; deba@414: deba@414: class Node; deba@414: class Arc; deba@414: deba@414: private: deba@414: deba@414: template class NodeMapBase; deba@414: template class ArcMapBase; deba@414: deba@414: public: deba@416: deba@414: class Node : public DigraphNode { deba@416: friend class SplitNodesBase; deba@414: template friend class NodeMapBase; deba@414: private: deba@414: deba@414: bool _in; deba@414: Node(DigraphNode node, bool in) deba@416: : DigraphNode(node), _in(in) {} deba@416: deba@414: public: deba@414: deba@414: Node() {} deba@414: Node(Invalid) : DigraphNode(INVALID), _in(true) {} deba@414: deba@414: bool operator==(const Node& node) const { deba@416: return DigraphNode::operator==(node) && _in == node._in; deba@414: } deba@416: deba@414: bool operator!=(const Node& node) const { deba@416: return !(*this == node); deba@414: } deba@416: deba@414: bool operator<(const Node& node) const { deba@416: return DigraphNode::operator<(node) || deba@416: (DigraphNode::operator==(node) && _in < node._in); deba@414: } deba@414: }; deba@414: deba@414: class Arc { deba@416: friend class SplitNodesBase; deba@414: template friend class ArcMapBase; deba@414: private: deba@414: typedef BiVariant ArcImpl; deba@414: deba@414: explicit Arc(const DigraphArc& arc) : _item(arc) {} deba@414: explicit Arc(const DigraphNode& node) : _item(node) {} deba@416: deba@414: ArcImpl _item; deba@414: deba@414: public: deba@414: Arc() {} deba@414: Arc(Invalid) : _item(DigraphArc(INVALID)) {} deba@414: deba@414: bool operator==(const Arc& arc) const { deba@414: if (_item.firstState()) { deba@414: if (arc._item.firstState()) { deba@414: return _item.first() == arc._item.first(); deba@414: } deba@414: } else { deba@414: if (arc._item.secondState()) { deba@414: return _item.second() == arc._item.second(); deba@414: } deba@414: } deba@414: return false; deba@414: } deba@416: deba@414: bool operator!=(const Arc& arc) const { deba@416: return !(*this == arc); deba@414: } deba@416: deba@414: bool operator<(const Arc& arc) const { deba@414: if (_item.firstState()) { deba@414: if (arc._item.firstState()) { deba@414: return _item.first() < arc._item.first(); deba@414: } deba@414: return false; deba@414: } else { deba@414: if (arc._item.secondState()) { deba@414: return _item.second() < arc._item.second(); deba@414: } deba@414: return true; deba@414: } deba@414: } deba@414: deba@414: operator DigraphArc() const { return _item.first(); } deba@414: operator DigraphNode() const { return _item.second(); } deba@414: deba@414: }; deba@414: deba@414: void first(Node& n) const { deba@414: _digraph->first(n); deba@414: n._in = true; deba@414: } deba@414: deba@414: void next(Node& n) const { deba@414: if (n._in) { deba@416: n._in = false; deba@414: } else { deba@416: n._in = true; deba@416: _digraph->next(n); deba@414: } deba@414: } deba@414: deba@414: void first(Arc& e) const { deba@414: e._item.setSecond(); deba@414: _digraph->first(e._item.second()); deba@414: if (e._item.second() == INVALID) { deba@414: e._item.setFirst(); deba@416: _digraph->first(e._item.first()); deba@414: } deba@414: } deba@414: deba@414: void next(Arc& e) const { deba@414: if (e._item.secondState()) { deba@416: _digraph->next(e._item.second()); deba@414: if (e._item.second() == INVALID) { deba@414: e._item.setFirst(); deba@414: _digraph->first(e._item.first()); deba@414: } deba@414: } else { deba@416: _digraph->next(e._item.first()); deba@416: } deba@414: } deba@414: deba@414: void firstOut(Arc& e, const Node& n) const { deba@414: if (n._in) { deba@414: e._item.setSecond(n); deba@414: } else { deba@414: e._item.setFirst(); deba@416: _digraph->firstOut(e._item.first(), n); deba@414: } deba@414: } deba@414: deba@414: void nextOut(Arc& e) const { deba@414: if (!e._item.firstState()) { deba@416: e._item.setFirst(INVALID); deba@414: } else { deba@416: _digraph->nextOut(e._item.first()); deba@416: } deba@414: } deba@414: deba@414: void firstIn(Arc& e, const Node& n) const { deba@414: if (!n._in) { deba@416: e._item.setSecond(n); deba@414: } else { deba@414: e._item.setFirst(); deba@416: _digraph->firstIn(e._item.first(), n); deba@414: } deba@414: } deba@414: deba@414: void nextIn(Arc& e) const { deba@414: if (!e._item.firstState()) { deba@416: e._item.setFirst(INVALID); deba@414: } else { deba@416: _digraph->nextIn(e._item.first()); deba@414: } deba@414: } deba@414: deba@414: Node source(const Arc& e) const { deba@414: if (e._item.firstState()) { deba@416: return Node(_digraph->source(e._item.first()), false); deba@414: } else { deba@416: return Node(e._item.second(), true); deba@414: } deba@414: } deba@414: deba@414: Node target(const Arc& e) const { deba@414: if (e._item.firstState()) { deba@416: return Node(_digraph->target(e._item.first()), true); deba@414: } else { deba@416: return Node(e._item.second(), false); deba@414: } deba@414: } deba@414: deba@414: int id(const Node& n) const { deba@414: return (_digraph->id(n) << 1) | (n._in ? 0 : 1); deba@414: } deba@414: Node nodeFromId(int ix) const { deba@414: return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0); deba@414: } deba@414: int maxNodeId() const { deba@414: return 2 * _digraph->maxNodeId() + 1; deba@414: } deba@414: deba@414: int id(const Arc& e) const { deba@414: if (e._item.firstState()) { deba@414: return _digraph->id(e._item.first()) << 1; deba@414: } else { deba@414: return (_digraph->id(e._item.second()) << 1) | 1; deba@414: } deba@414: } deba@414: Arc arcFromId(int ix) const { deba@414: if ((ix & 1) == 0) { deba@414: return Arc(_digraph->arcFromId(ix >> 1)); deba@414: } else { deba@414: return Arc(_digraph->nodeFromId(ix >> 1)); deba@414: } deba@414: } deba@414: int maxArcId() const { deba@416: return std::max(_digraph->maxNodeId() << 1, deba@414: (_digraph->maxArcId() << 1) | 1); deba@414: } deba@414: deba@414: static bool inNode(const Node& n) { deba@414: return n._in; deba@414: } deba@414: deba@414: static bool outNode(const Node& n) { deba@414: return !n._in; deba@414: } deba@414: deba@414: static bool origArc(const Arc& e) { deba@414: return e._item.firstState(); deba@414: } deba@414: deba@414: static bool bindArc(const Arc& e) { deba@414: return e._item.secondState(); deba@414: } deba@414: deba@414: static Node inNode(const DigraphNode& n) { deba@414: return Node(n, true); deba@414: } deba@414: deba@414: static Node outNode(const DigraphNode& n) { deba@414: return Node(n, false); deba@414: } deba@414: deba@414: static Arc arc(const DigraphNode& n) { deba@414: return Arc(n); deba@414: } deba@414: deba@414: static Arc arc(const DigraphArc& e) { deba@414: return Arc(e); deba@414: } deba@414: deba@414: typedef True NodeNumTag; deba@414: int nodeNum() const { deba@414: return 2 * countNodes(*_digraph); deba@414: } deba@414: kpeter@446: typedef True ArcNumTag; deba@414: int arcNum() const { deba@414: return countArcs(*_digraph) + countNodes(*_digraph); deba@414: } deba@414: kpeter@446: typedef True FindArcTag; deba@416: Arc findArc(const Node& u, const Node& v, deba@416: const Arc& prev = INVALID) const { kpeter@449: if (inNode(u) && outNode(v)) { kpeter@449: if (static_cast(u) == kpeter@449: static_cast(v) && prev == INVALID) { kpeter@449: return Arc(u); deba@414: } kpeter@449: } kpeter@449: else if (outNode(u) && inNode(v)) { kpeter@449: return Arc(::lemon::findArc(*_digraph, u, v, prev)); deba@414: } deba@414: return INVALID; deba@414: } deba@414: deba@414: private: deba@416: deba@512: template deba@416: class NodeMapBase deba@512: : public MapTraits > { deba@512: typedef typename Parent::template NodeMap NodeImpl; deba@414: public: deba@414: typedef Node Key; deba@512: typedef V Value; kpeter@449: typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; kpeter@449: typedef typename MapTraits::ReturnValue ReturnValue; kpeter@449: typedef typename MapTraits::ConstReturnValue ConstReturnValue; kpeter@449: typedef typename MapTraits::ReturnValue Reference; kpeter@449: typedef typename MapTraits::ConstReturnValue ConstReference; deba@416: deba@512: NodeMapBase(const SplitNodesBase& adaptor) deba@416: : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {} deba@512: NodeMapBase(const SplitNodesBase& adaptor, const V& value) deba@416: : _in_map(*adaptor._digraph, value), deba@416: _out_map(*adaptor._digraph, value) {} deba@414: deba@512: void set(const Node& key, const V& val) { deba@512: if (SplitNodesBase::inNode(key)) { _in_map.set(key, val); } deba@416: else {_out_map.set(key, val); } deba@414: } deba@416: kpeter@449: ReturnValue operator[](const Node& key) { deba@512: if (SplitNodesBase::inNode(key)) { return _in_map[key]; } deba@416: else { return _out_map[key]; } deba@414: } deba@414: kpeter@449: ConstReturnValue operator[](const Node& key) const { deba@416: if (Adaptor::inNode(key)) { return _in_map[key]; } deba@416: else { return _out_map[key]; } deba@414: } deba@414: deba@414: private: deba@414: NodeImpl _in_map, _out_map; deba@414: }; deba@414: deba@512: template deba@416: class ArcMapBase deba@512: : public MapTraits > { deba@512: typedef typename Parent::template ArcMap ArcImpl; deba@512: typedef typename Parent::template NodeMap NodeImpl; deba@414: public: deba@414: typedef Arc Key; deba@512: typedef V Value; kpeter@449: typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; kpeter@449: typedef typename MapTraits::ReturnValue ReturnValue; kpeter@449: typedef typename MapTraits::ConstReturnValue ConstReturnValue; kpeter@449: typedef typename MapTraits::ReturnValue Reference; kpeter@449: typedef typename MapTraits::ConstReturnValue ConstReference; deba@414: deba@512: ArcMapBase(const SplitNodesBase& adaptor) deba@416: : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {} deba@512: ArcMapBase(const SplitNodesBase& adaptor, const V& value) deba@416: : _arc_map(*adaptor._digraph, value), deba@416: _node_map(*adaptor._digraph, value) {} deba@414: deba@512: void set(const Arc& key, const V& val) { deba@512: if (SplitNodesBase::origArc(key)) { kpeter@516: _arc_map.set(static_cast(key), val); deba@414: } else { kpeter@516: _node_map.set(static_cast(key), val); deba@414: } deba@414: } deba@416: kpeter@449: ReturnValue operator[](const Arc& key) { deba@512: if (SplitNodesBase::origArc(key)) { kpeter@516: return _arc_map[static_cast(key)]; deba@414: } else { kpeter@516: return _node_map[static_cast(key)]; deba@414: } deba@414: } deba@414: kpeter@449: ConstReturnValue operator[](const Arc& key) const { deba@512: if (SplitNodesBase::origArc(key)) { kpeter@516: return _arc_map[static_cast(key)]; deba@414: } else { kpeter@516: return _node_map[static_cast(key)]; deba@414: } deba@414: } deba@414: deba@414: private: deba@414: ArcImpl _arc_map; deba@414: NodeImpl _node_map; deba@414: }; deba@414: deba@414: public: deba@414: deba@512: template deba@416: class NodeMap deba@512: : public SubMapExtender, NodeMapBase > deba@414: { deba@414: public: deba@512: typedef V Value; deba@512: typedef SubMapExtender, NodeMapBase > Parent; deba@512: deba@512: NodeMap(const SplitNodesBase& adaptor) deba@416: : Parent(adaptor) {} deba@416: deba@512: NodeMap(const SplitNodesBase& adaptor, const V& value) deba@416: : Parent(adaptor, value) {} deba@416: deba@414: private: deba@414: NodeMap& operator=(const NodeMap& cmap) { deba@416: return operator=(cmap); deba@414: } deba@416: deba@414: template deba@414: NodeMap& operator=(const CMap& cmap) { deba@414: Parent::operator=(cmap); deba@416: return *this; deba@414: } deba@414: }; deba@414: deba@512: template deba@416: class ArcMap deba@512: : public SubMapExtender, ArcMapBase > deba@414: { deba@414: public: deba@512: typedef V Value; deba@512: typedef SubMapExtender, ArcMapBase > Parent; deba@512: deba@512: ArcMap(const SplitNodesBase& adaptor) deba@416: : Parent(adaptor) {} deba@416: deba@512: ArcMap(const SplitNodesBase& adaptor, const V& value) deba@416: : Parent(adaptor, value) {} deba@416: deba@414: private: deba@414: ArcMap& operator=(const ArcMap& cmap) { deba@416: return operator=(cmap); deba@414: } deba@416: deba@414: template deba@414: ArcMap& operator=(const CMap& cmap) { deba@414: Parent::operator=(cmap); deba@416: return *this; deba@414: } deba@414: }; deba@414: deba@414: protected: deba@414: deba@416: SplitNodesBase() : _digraph(0) {} deba@414: deba@512: DGR* _digraph; deba@512: deba@512: void initialize(Digraph& digraph) { deba@414: _digraph = &digraph; deba@414: } deba@416: deba@414: }; deba@414: deba@414: /// \ingroup graph_adaptors deba@414: /// kpeter@451: /// \brief Adaptor class for splitting the nodes of a digraph. deba@416: /// kpeter@451: /// SplitNodes adaptor can be used for splitting each node into an kpeter@451: /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor kpeter@451: /// replaces each node \f$ u \f$ in the digraph with two nodes, kpeter@451: /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$. kpeter@451: /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the kpeter@451: /// new target of the arc will be \f$ u_{in} \f$ and similarly the kpeter@451: /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$. kpeter@451: /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$ kpeter@451: /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph. deba@414: /// kpeter@451: /// The aim of this class is running an algorithm with respect to node kpeter@451: /// costs or capacities if the algorithm considers only arc costs or kpeter@451: /// capacities directly. kpeter@451: /// In this case you can use \c SplitNodes adaptor, and set the node kpeter@451: /// costs/capacities of the original digraph to the \e bind \e arcs kpeter@451: /// in the adaptor. deba@414: /// deba@512: /// \tparam DGR The type of the adapted digraph. kpeter@451: /// It must conform to the \ref concepts::Digraph "Digraph" concept. kpeter@451: /// It is implicitly \c const. kpeter@451: /// kpeter@451: /// \note The \c Node type of this adaptor is converible to the \c Node kpeter@451: /// type of the adapted digraph. deba@512: template kpeter@453: #ifdef DOXYGEN kpeter@453: class SplitNodes { kpeter@453: #else deba@416: class SplitNodes deba@512: : public DigraphAdaptorExtender > { kpeter@453: #endif deba@414: public: deba@512: typedef DGR Digraph; deba@512: typedef DigraphAdaptorExtender > Parent; deba@512: deba@512: typedef typename DGR::Node DigraphNode; deba@512: typedef typename DGR::Arc DigraphArc; deba@415: deba@414: typedef typename Parent::Node Node; deba@414: typedef typename Parent::Arc Arc; deba@414: kpeter@451: /// \brief Constructor deba@414: /// deba@414: /// Constructor of the adaptor. deba@512: SplitNodes(const DGR& g) { deba@512: Parent::initialize(g); deba@414: } deba@414: kpeter@451: /// \brief Returns \c true if the given node is an in-node. deba@415: /// kpeter@451: /// Returns \c true if the given node is an in-node. deba@415: static bool inNode(const Node& n) { deba@415: return Parent::inNode(n); deba@415: } deba@415: kpeter@451: /// \brief Returns \c true if the given node is an out-node. deba@415: /// kpeter@451: /// Returns \c true if the given node is an out-node. deba@415: static bool outNode(const Node& n) { deba@415: return Parent::outNode(n); deba@415: } deba@415: kpeter@451: /// \brief Returns \c true if the given arc is an original arc. deba@415: /// kpeter@451: /// Returns \c true if the given arc is one of the arcs in the kpeter@451: /// original digraph. deba@415: static bool origArc(const Arc& a) { deba@415: return Parent::origArc(a); deba@415: } deba@415: kpeter@451: /// \brief Returns \c true if the given arc is a bind arc. deba@415: /// kpeter@451: /// Returns \c true if the given arc is a bind arc, i.e. it connects kpeter@451: /// an in-node and an out-node. deba@415: static bool bindArc(const Arc& a) { deba@415: return Parent::bindArc(a); deba@415: } deba@415: kpeter@451: /// \brief Returns the in-node created from the given original node. deba@415: /// kpeter@451: /// Returns the in-node created from the given original node. deba@415: static Node inNode(const DigraphNode& n) { deba@415: return Parent::inNode(n); deba@415: } deba@415: kpeter@451: /// \brief Returns the out-node created from the given original node. deba@415: /// kpeter@451: /// Returns the out-node created from the given original node. deba@415: static Node outNode(const DigraphNode& n) { deba@415: return Parent::outNode(n); deba@415: } deba@415: kpeter@451: /// \brief Returns the bind arc that corresponds to the given kpeter@451: /// original node. deba@416: /// kpeter@451: /// Returns the bind arc in the adaptor that corresponds to the given kpeter@451: /// original node, i.e. the arc connecting the in-node and out-node kpeter@451: /// of \c n. deba@415: static Arc arc(const DigraphNode& n) { deba@415: return Parent::arc(n); deba@415: } deba@415: kpeter@451: /// \brief Returns the arc that corresponds to the given original arc. deba@416: /// kpeter@451: /// Returns the arc in the adaptor that corresponds to the given kpeter@451: /// original arc. deba@415: static Arc arc(const DigraphArc& a) { deba@415: return Parent::arc(a); deba@415: } deba@415: kpeter@451: /// \brief Node map combined from two original node maps deba@414: /// kpeter@451: /// This map adaptor class adapts two node maps of the original digraph kpeter@451: /// to get a node map of the split digraph. kpeter@451: /// Its value type is inherited from the first node map type kpeter@451: /// (\c InNodeMap). deba@414: template deba@414: class CombinedNodeMap { deba@414: public: deba@414: kpeter@451: /// The key type of the map deba@414: typedef Node Key; kpeter@451: /// The value type of the map deba@414: typedef typename InNodeMap::Value Value; deba@414: kpeter@449: typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; kpeter@449: typedef typename MapTraits::ReturnValue ReturnValue; kpeter@449: typedef typename MapTraits::ConstReturnValue ConstReturnValue; kpeter@449: typedef typename MapTraits::ReturnValue Reference; kpeter@449: typedef typename MapTraits::ConstReturnValue ConstReference; kpeter@449: kpeter@451: /// Constructor deba@416: CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) deba@416: : _in_map(in_map), _out_map(out_map) {} deba@414: kpeter@451: /// Returns the value associated with the given key. kpeter@451: Value operator[](const Key& key) const { deba@512: if (SplitNodesBase::inNode(key)) { kpeter@451: return _in_map[key]; kpeter@451: } else { kpeter@451: return _out_map[key]; kpeter@451: } kpeter@451: } kpeter@451: kpeter@451: /// Returns a reference to the value associated with the given key. deba@414: Value& operator[](const Key& key) { deba@512: if (SplitNodesBase::inNode(key)) { deba@416: return _in_map[key]; deba@416: } else { deba@416: return _out_map[key]; deba@416: } deba@414: } deba@414: kpeter@451: /// Sets the value associated with the given key. deba@414: void set(const Key& key, const Value& value) { deba@512: if (SplitNodesBase::inNode(key)) { deba@416: _in_map.set(key, value); deba@416: } else { deba@416: _out_map.set(key, value); deba@416: } deba@414: } deba@416: deba@414: private: deba@416: deba@414: InNodeMap& _in_map; deba@414: OutNodeMap& _out_map; deba@416: deba@414: }; deba@414: deba@414: kpeter@451: /// \brief Returns a combined node map deba@416: /// kpeter@451: /// This function just returns a combined node map. deba@414: template deba@416: static CombinedNodeMap deba@414: combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) { deba@414: return CombinedNodeMap(in_map, out_map); deba@414: } deba@414: deba@414: template deba@416: static CombinedNodeMap deba@414: combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) { deba@414: return CombinedNodeMap(in_map, out_map); deba@414: } deba@414: deba@414: template deba@416: static CombinedNodeMap deba@414: combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) { deba@414: return CombinedNodeMap(in_map, out_map); deba@414: } deba@414: deba@414: template deba@416: static CombinedNodeMap deba@414: combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) { deba@416: return CombinedNodeMap(in_map, out_map); deba@414: } deba@414: kpeter@451: /// \brief Arc map combined from an arc map and a node map of the kpeter@451: /// original digraph. deba@414: /// kpeter@451: /// This map adaptor class adapts an arc map and a node map of the kpeter@451: /// original digraph to get an arc map of the split digraph. kpeter@451: /// Its value type is inherited from the original arc map type kpeter@453: /// (\c ArcMap). kpeter@453: template deba@414: class CombinedArcMap { deba@414: public: deba@416: kpeter@451: /// The key type of the map deba@414: typedef Arc Key; kpeter@451: /// The value type of the map kpeter@453: typedef typename ArcMap::Value Value; kpeter@453: kpeter@453: typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; kpeter@453: typedef typename MapTraits::ReturnValue ReturnValue; kpeter@453: typedef typename MapTraits::ConstReturnValue ConstReturnValue; kpeter@453: typedef typename MapTraits::ReturnValue Reference; kpeter@453: typedef typename MapTraits::ConstReturnValue ConstReference; kpeter@449: kpeter@451: /// Constructor kpeter@453: CombinedArcMap(ArcMap& arc_map, NodeMap& node_map) deba@416: : _arc_map(arc_map), _node_map(node_map) {} deba@414: kpeter@451: /// Returns the value associated with the given key. kpeter@451: Value operator[](const Key& arc) const { deba@512: if (SplitNodesBase::origArc(arc)) { kpeter@451: return _arc_map[arc]; kpeter@451: } else { kpeter@451: return _node_map[arc]; kpeter@451: } kpeter@451: } kpeter@451: kpeter@451: /// Returns a reference to the value associated with the given key. kpeter@451: Value& operator[](const Key& arc) { deba@512: if (SplitNodesBase::origArc(arc)) { kpeter@451: return _arc_map[arc]; kpeter@451: } else { kpeter@451: return _node_map[arc]; kpeter@451: } kpeter@451: } kpeter@451: kpeter@451: /// Sets the value associated with the given key. deba@414: void set(const Arc& arc, const Value& val) { deba@512: if (SplitNodesBase::origArc(arc)) { deba@416: _arc_map.set(arc, val); deba@416: } else { deba@416: _node_map.set(arc, val); deba@416: } deba@414: } deba@414: deba@414: private: kpeter@453: ArcMap& _arc_map; kpeter@453: NodeMap& _node_map; deba@414: }; deba@416: kpeter@451: /// \brief Returns a combined arc map deba@416: /// kpeter@451: /// This function just returns a combined arc map. kpeter@453: template kpeter@453: static CombinedArcMap kpeter@453: combinedArcMap(ArcMap& arc_map, NodeMap& node_map) { kpeter@453: return CombinedArcMap(arc_map, node_map); deba@414: } deba@414: kpeter@453: template kpeter@453: static CombinedArcMap kpeter@453: combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) { kpeter@453: return CombinedArcMap(arc_map, node_map); deba@414: } deba@414: kpeter@453: template kpeter@453: static CombinedArcMap kpeter@453: combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) { kpeter@453: return CombinedArcMap(arc_map, node_map); deba@414: } deba@414: kpeter@453: template kpeter@453: static CombinedArcMap kpeter@453: combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) { kpeter@453: return CombinedArcMap(arc_map, node_map); deba@414: } deba@414: deba@414: }; deba@414: kpeter@451: /// \brief Returns a (read-only) SplitNodes adaptor deba@414: /// kpeter@451: /// This function just returns a (read-only) \ref SplitNodes adaptor. kpeter@451: /// \ingroup graph_adaptors kpeter@451: /// \relates SplitNodes deba@512: template deba@512: SplitNodes deba@512: splitNodes(const DGR& digraph) { deba@512: return SplitNodes(digraph); deba@414: } deba@414: deba@512: #undef LEMON_SCOPE_FIX deba@512: deba@414: } //namespace lemon deba@414: deba@416: #endif //LEMON_ADAPTORS_H