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