deba@414: /* -*- C++ -*-
deba@414:  *
deba@414:  * This file is a part of LEMON, a generic C++ optimization library
deba@414:  *
deba@414:  * Copyright (C) 2003-2008
deba@414:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@414:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@414:  *
deba@414:  * Permission to use, modify and distribute this software is granted
deba@414:  * provided that this copyright notice appears in all copies. For
deba@414:  * precise terms see the accompanying LICENSE file.
deba@414:  *
deba@414:  * This software is provided "AS IS" with no warranty of any kind,
deba@414:  * express or implied, and with no claim as to its suitability for any
deba@414:  * purpose.
deba@414:  *
deba@414:  */
deba@414: 
deba@414: #ifndef LEMON_GRAPH_ADAPTOR_H
deba@414: #define LEMON_GRAPH_ADAPTOR_H
deba@414: 
deba@414: ///\ingroup graph_adaptors
deba@414: ///\file
deba@414: ///\brief Several graph adaptors.
deba@414: ///
deba@414: ///This file contains several useful undirected graph adaptor classes.
deba@414: 
deba@414: #include <lemon/core.h>
deba@414: #include <lemon/maps.h>
deba@414: #include <lemon/bits/graph_adaptor_extender.h>
deba@414: 
deba@414: namespace lemon {
deba@414: 
deba@414:   /// \brief Base type for the Graph Adaptors
deba@414:   ///
deba@414:   /// This is the base type for most of LEMON graph adaptors. 
deba@414:   /// This class implements a trivial graph adaptor i.e. it only wraps the 
deba@414:   /// functions and types of the graph. The purpose of this class is to 
deba@414:   /// make easier implementing graph adaptors. E.g. if an adaptor is 
deba@414:   /// considered which differs from the wrapped graph only in some of its 
deba@414:   /// functions or types, then it can be derived from GraphAdaptor, and only 
deba@414:   /// the differences should be implemented.
deba@414:   template<typename _Graph>
deba@414:   class GraphAdaptorBase {
deba@414:   public:
deba@414:     typedef _Graph Graph;
deba@414:     typedef Graph ParentGraph;
deba@414: 
deba@414:   protected:
deba@414:     Graph* _graph;
deba@414: 
deba@414:     GraphAdaptorBase() : _graph(0) {}
deba@414: 
deba@414:     void setGraph(Graph& graph) { _graph = &graph; }
deba@414: 
deba@414:   public:
deba@414:     GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
deba@414:  
deba@414:     typedef typename Graph::Node Node;
deba@414:     typedef typename Graph::Arc Arc;
deba@414:     typedef typename Graph::Edge Edge;
deba@414:    
deba@414:     void first(Node& i) const { _graph->first(i); }
deba@414:     void first(Arc& i) const { _graph->first(i); }
deba@414:     void first(Edge& i) const { _graph->first(i); }
deba@414:     void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
deba@414:     void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
deba@414:     void firstInc(Edge &i, bool &d, const Node &n) const {
deba@414:       _graph->firstInc(i, d, n);
deba@414:     }
deba@414: 
deba@414:     void next(Node& i) const { _graph->next(i); }
deba@414:     void next(Arc& i) const { _graph->next(i); }
deba@414:     void next(Edge& i) const { _graph->next(i); }
deba@414:     void nextIn(Arc& i) const { _graph->nextIn(i); }
deba@414:     void nextOut(Arc& i) const { _graph->nextOut(i); }
deba@414:     void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
deba@414: 
deba@414:     Node u(const Edge& e) const { return _graph->u(e); }
deba@414:     Node v(const Edge& e) const { return _graph->v(e); }
deba@414: 
deba@414:     Node source(const Arc& a) const { return _graph->source(a); }
deba@414:     Node target(const Arc& a) const { return _graph->target(a); }
deba@414: 
deba@414:     typedef NodeNumTagIndicator<Graph> NodeNumTag;
deba@414:     int nodeNum() const { return _graph->nodeNum(); }
deba@414:     
deba@414:     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
deba@414:     int arcNum() const { return _graph->arcNum(); }
deba@414:     int edgeNum() const { return _graph->edgeNum(); }
deba@414: 
deba@414:     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@414:     Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
deba@414:       return _graph->findArc(u, v, prev);
deba@414:     }
deba@414:     Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
deba@414:       return _graph->findEdge(u, v, prev);
deba@414:     }
deba@414:   
deba@414:     Node addNode() { return _graph->addNode(); }
deba@414:     Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
deba@414: 
deba@414:     void erase(const Node& i) { _graph->erase(i); }
deba@414:     void erase(const Edge& i) { _graph->erase(i); }
deba@414:   
deba@414:     void clear() { _graph->clear(); }
deba@414:     
deba@414:     bool direction(const Arc& a) const { return _graph->direction(a); }
deba@414:     Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
deba@414: 
deba@414:     int id(const Node& v) const { return _graph->id(v); }
deba@414:     int id(const Arc& a) const { return _graph->id(a); }
deba@414:     int id(const Edge& e) const { return _graph->id(e); }
deba@414: 
deba@414:     Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
deba@414:     Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
deba@414:     Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
deba@414: 
deba@414:     int maxNodeId() const { return _graph->maxNodeId(); }
deba@414:     int maxArcId() const { return _graph->maxArcId(); }
deba@414:     int maxEdgeId() const { return _graph->maxEdgeId(); }
deba@414: 
deba@414:     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@414:     NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 
deba@414: 
deba@414:     typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
deba@414:     ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 
deba@414: 
deba@414:     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
deba@414:     EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); } 
deba@414: 
deba@414:     template <typename _Value>
deba@414:     class NodeMap : public Graph::template NodeMap<_Value> {
deba@414:     public:
deba@414:       typedef typename Graph::template NodeMap<_Value> Parent;
deba@414:       explicit NodeMap(const GraphAdaptorBase<Graph>& adapter) 
deba@414: 	: Parent(*adapter._graph) {}
deba@414:       NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
deba@414: 	: Parent(*adapter._graph, value) {}
deba@414: 
deba@414:     private:
deba@414:       NodeMap& operator=(const NodeMap& cmap) {
deba@414: 	return operator=<NodeMap>(cmap);
deba@414:       }
deba@414: 
deba@414:       template <typename CMap>
deba@414:       NodeMap& operator=(const CMap& cmap) {
deba@414:         Parent::operator=(cmap);
deba@414:         return *this;
deba@414:       }
deba@414:       
deba@414:     };
deba@414: 
deba@414:     template <typename _Value>
deba@414:     class ArcMap : public Graph::template ArcMap<_Value> {
deba@414:     public:
deba@414:       typedef typename Graph::template ArcMap<_Value> Parent;
deba@414:       explicit ArcMap(const GraphAdaptorBase<Graph>& adapter) 
deba@414: 	: Parent(*adapter._graph) {}
deba@414:       ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
deba@414: 	: Parent(*adapter._graph, value) {}
deba@414: 
deba@414:     private:
deba@414:       ArcMap& operator=(const ArcMap& cmap) {
deba@414: 	return operator=<ArcMap>(cmap);
deba@414:       }
deba@414: 
deba@414:       template <typename CMap>
deba@414:       ArcMap& operator=(const CMap& cmap) {
deba@414:         Parent::operator=(cmap);
deba@414: 	return *this;
deba@414:       }
deba@414:     };
deba@414: 
deba@414:     template <typename _Value>
deba@414:     class EdgeMap : public Graph::template EdgeMap<_Value> {
deba@414:     public:
deba@414:       typedef typename Graph::template EdgeMap<_Value> Parent;
deba@414:       explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter) 
deba@414: 	: Parent(*adapter._graph) {}
deba@414:       EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
deba@414: 	: Parent(*adapter._graph, value) {}
deba@414: 
deba@414:     private:
deba@414:       EdgeMap& operator=(const EdgeMap& cmap) {
deba@414: 	return operator=<EdgeMap>(cmap);
deba@414:       }
deba@414: 
deba@414:       template <typename CMap>
deba@414:       EdgeMap& operator=(const CMap& cmap) {
deba@414:         Parent::operator=(cmap);
deba@414:         return *this;
deba@414:       }
deba@414:     };
deba@414: 
deba@414:   };
deba@414: 
deba@414:   /// \ingroup graph_adaptors
deba@414:   ///
deba@414:   /// \brief Trivial graph adaptor
deba@414:   ///
deba@414:   /// This class is an adaptor which does not change the adapted undirected
deba@414:   /// graph. It can be used only to test the graph adaptors.
deba@414:   template <typename _Graph>
deba@414:   class GraphAdaptor 
deba@414:     : public GraphAdaptorExtender< GraphAdaptorBase<_Graph> > { 
deba@414:   public:
deba@414:     typedef _Graph Graph;
deba@414:     typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
deba@414:   protected:
deba@414:     GraphAdaptor() : Parent() {}
deba@414: 
deba@414:   public:
deba@414:     explicit GraphAdaptor(Graph& graph) { setGraph(graph); }
deba@414:   };
deba@414: 
deba@414:   template <typename _Graph, typename NodeFilterMap, 
deba@414: 	    typename EdgeFilterMap, bool checked = true>
deba@414:   class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
deba@414:   public:
deba@414:     typedef _Graph Graph;
deba@414:     typedef SubGraphAdaptorBase Adaptor;
deba@414:     typedef GraphAdaptorBase<_Graph> Parent;
deba@414:   protected:
deba@414: 
deba@414:     NodeFilterMap* _node_filter_map;
deba@414:     EdgeFilterMap* _edge_filter_map;
deba@414: 
deba@414:     SubGraphAdaptorBase() 
deba@414:       : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
deba@414: 
deba@414:     void setNodeFilterMap(NodeFilterMap& node_filter_map) {
deba@414:       _node_filter_map=&node_filter_map;
deba@414:     }
deba@414:     void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
deba@414:       _edge_filter_map=&edge_filter_map;
deba@414:     }
deba@414: 
deba@414:   public:
deba@414: 
deba@414:     typedef typename Parent::Node Node;
deba@414:     typedef typename Parent::Arc Arc;
deba@414:     typedef typename Parent::Edge Edge;
deba@414: 
deba@414:     void first(Node& i) const { 
deba@414:       Parent::first(i); 
deba@414:       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 
deba@414:     }
deba@414: 
deba@414:     void first(Arc& i) const { 
deba@414:       Parent::first(i); 
deba@414:       while (i!=INVALID && (!(*_edge_filter_map)[i] 
deba@414: 	     || !(*_node_filter_map)[Parent::source(i)]
deba@414: 	     || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i); 
deba@414:     }
deba@414: 
deba@414:     void first(Edge& i) const { 
deba@414:       Parent::first(i); 
deba@414:       while (i!=INVALID && (!(*_edge_filter_map)[i] 
deba@414: 	     || !(*_node_filter_map)[Parent::u(i)]
deba@414: 	     || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i); 
deba@414:     }
deba@414: 
deba@414:     void firstIn(Arc& i, const Node& n) const { 
deba@414:       Parent::firstIn(i, n); 
deba@414:       while (i!=INVALID && (!(*_edge_filter_map)[i] 
deba@414: 	     || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
deba@414:     }
deba@414: 
deba@414:     void firstOut(Arc& i, const Node& n) const { 
deba@414:       Parent::firstOut(i, n); 
deba@414:       while (i!=INVALID && (!(*_edge_filter_map)[i] 
deba@414: 	     || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
deba@414:     }
deba@414: 
deba@414:     void firstInc(Edge& i, bool& d, const Node& n) const { 
deba@414:       Parent::firstInc(i, d, n); 
deba@414:       while (i!=INVALID && (!(*_edge_filter_map)[i] 
deba@414:             || !(*_node_filter_map)[Parent::u(i)]
deba@414:             || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d); 
deba@414:     }
deba@414: 
deba@414:     void next(Node& i) const { 
deba@414:       Parent::next(i); 
deba@414:       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 
deba@414:     }
deba@414: 
deba@414:     void next(Arc& i) const { 
deba@414:       Parent::next(i); 
deba@414:       while (i!=INVALID && (!(*_edge_filter_map)[i] 
deba@414: 	     || !(*_node_filter_map)[Parent::source(i)]
deba@414: 	     || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i); 
deba@414:     }
deba@414: 
deba@414:     void next(Edge& i) const { 
deba@414:       Parent::next(i); 
deba@414:       while (i!=INVALID && (!(*_edge_filter_map)[i] 
deba@414: 	     || !(*_node_filter_map)[Parent::u(i)]
deba@414: 	     || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i); 
deba@414:     }
deba@414: 
deba@414:     void nextIn(Arc& i) const { 
deba@414:       Parent::nextIn(i); 
deba@414:       while (i!=INVALID && (!(*_edge_filter_map)[i] 
deba@414: 	     || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
deba@414:     }
deba@414: 
deba@414:     void nextOut(Arc& i) const { 
deba@414:       Parent::nextOut(i); 
deba@414:       while (i!=INVALID && (!(*_edge_filter_map)[i] 
deba@414: 	     || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
deba@414:     }
deba@414: 
deba@414:     void nextInc(Edge& i, bool& d) const { 
deba@414:       Parent::nextInc(i, d); 
deba@414:       while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@414:             || !(*_node_filter_map)[Parent::u(i)]
deba@414:             || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d); 
deba@414:     }
deba@414: 
deba@414:     /// \brief Hide the given node in the graph.
deba@414:     ///
deba@414:     /// This function hides \c n in the graph, i.e. the iteration 
deba@414:     /// jumps over it. This is done by simply setting the value of \c n  
deba@414:     /// to be false in the corresponding node-map.
deba@414:     void hide(const Node& n) const { _node_filter_map->set(n, false); }
deba@414: 
deba@414:     /// \brief Hide the given edge in the graph.
deba@414:     ///
deba@414:     /// This function hides \c e in the graph, i.e. the iteration 
deba@414:     /// jumps over it. This is done by simply setting the value of \c e  
deba@414:     /// to be false in the corresponding edge-map.
deba@414:     void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
deba@414: 
deba@414:     /// \brief Unhide the given node in the graph.
deba@414:     ///
deba@414:     /// The value of \c n is set to be true in the node-map which stores 
deba@414:     /// hide information. If \c n was hidden previuosly, then it is shown 
deba@414:     /// again
deba@414:      void unHide(const Node& n) const { _node_filter_map->set(n, true); }
deba@414: 
deba@414:     /// \brief Hide the given edge in the graph.
deba@414:     ///
deba@414:     /// The value of \c e is set to be true in the edge-map which stores 
deba@414:     /// hide information. If \c e was hidden previuosly, then it is shown 
deba@414:     /// again
deba@414:     void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
deba@414: 
deba@414:     /// \brief Returns true if \c n is hidden.
deba@414:     ///
deba@414:     /// Returns true if \c n is hidden.
deba@414:     bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
deba@414: 
deba@414:     /// \brief Returns true if \c e is hidden.
deba@414:     ///
deba@414:     /// Returns true if \c e is hidden.
deba@414:     bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
deba@414: 
deba@414:     typedef False NodeNumTag;
deba@414:     typedef False EdgeNumTag;
deba@414: 
deba@414:     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@414:     Arc findArc(const Node& u, const Node& v, 
deba@414: 		  const Arc& prev = INVALID) {
deba@414:       if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
deba@414:         return INVALID;
deba@414:       }
deba@414:       Arc arc = Parent::findArc(u, v, prev);
deba@414:       while (arc != INVALID && !(*_edge_filter_map)[arc]) {
deba@414:         arc = Parent::findArc(u, v, arc);
deba@414:       }
deba@414:       return arc;
deba@414:     }
deba@414:     Edge findEdge(const Node& u, const Node& v, 
deba@414: 		  const Edge& prev = INVALID) {
deba@414:       if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
deba@414:         return INVALID;
deba@414:       }
deba@414:       Edge edge = Parent::findEdge(u, v, prev);
deba@414:       while (edge != INVALID && !(*_edge_filter_map)[edge]) {
deba@414:         edge = Parent::findEdge(u, v, edge);
deba@414:       }
deba@414:       return edge;
deba@414:     }
deba@414: 
deba@414:     template <typename _Value>
deba@414:     class NodeMap : public SubMapExtender<Adaptor, 
deba@414:         typename Parent::template NodeMap<_Value> > {
deba@414:     public:
deba@414:       typedef _Value Value;
deba@414:       typedef SubMapExtender<Adaptor, typename Parent::
deba@414:                              template NodeMap<Value> > MapParent;
deba@414:     
deba@414:       NodeMap(const Adaptor& adaptor) 
deba@414: 	: MapParent(adaptor) {}
deba@414:       NodeMap(const Adaptor& adaptor, const Value& value) 
deba@414: 	: MapParent(adaptor, value) {}
deba@414: 
deba@414:     private:
deba@414:       NodeMap& operator=(const NodeMap& cmap) {
deba@414: 	return operator=<NodeMap>(cmap);
deba@414:       }
deba@414:     
deba@414:       template <typename CMap>
deba@414:       NodeMap& operator=(const CMap& cmap) {
deba@414:         MapParent::operator=(cmap);
deba@414: 	return *this;
deba@414:       }
deba@414:     };
deba@414: 
deba@414:     template <typename _Value>
deba@414:     class ArcMap : public SubMapExtender<Adaptor, 
deba@414: 	typename Parent::template ArcMap<_Value> > {
deba@414:     public:
deba@414:       typedef _Value Value;
deba@414:       typedef SubMapExtender<Adaptor, typename Parent::
deba@414:                              template ArcMap<Value> > MapParent;
deba@414:     
deba@414:       ArcMap(const Adaptor& adaptor) 
deba@414: 	: MapParent(adaptor) {}
deba@414:       ArcMap(const Adaptor& adaptor, const Value& value) 
deba@414: 	: MapParent(adaptor, value) {}
deba@414: 
deba@414:     private:
deba@414:       ArcMap& operator=(const ArcMap& cmap) {
deba@414: 	return operator=<ArcMap>(cmap);
deba@414:       }
deba@414:     
deba@414:       template <typename CMap>
deba@414:       ArcMap& operator=(const CMap& cmap) {
deba@414:         MapParent::operator=(cmap);
deba@414: 	return *this;
deba@414:       }
deba@414:     };
deba@414: 
deba@414:     template <typename _Value>
deba@414:     class EdgeMap : public SubMapExtender<Adaptor, 
deba@414:         typename Parent::template EdgeMap<_Value> > {
deba@414:     public:
deba@414:       typedef _Value Value;
deba@414:       typedef SubMapExtender<Adaptor, typename Parent::
deba@414:                              template EdgeMap<Value> > MapParent;
deba@414:     
deba@414:       EdgeMap(const Adaptor& adaptor) 
deba@414: 	: MapParent(adaptor) {}
deba@414: 
deba@414:       EdgeMap(const Adaptor& adaptor, const Value& value) 
deba@414: 	: MapParent(adaptor, value) {}
deba@414: 
deba@414:     private:
deba@414:       EdgeMap& operator=(const EdgeMap& cmap) {
deba@414: 	return operator=<EdgeMap>(cmap);
deba@414:       }
deba@414:     
deba@414:       template <typename CMap>
deba@414:       EdgeMap& operator=(const CMap& cmap) {
deba@414:         MapParent::operator=(cmap);
deba@414: 	return *this;
deba@414:       }
deba@414:     };
deba@414: 
deba@414:   };
deba@414: 
deba@414:   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@414:   class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false> 
deba@414:     : public GraphAdaptorBase<_Graph> {
deba@414:   public:
deba@414:     typedef _Graph Graph;
deba@414:     typedef SubGraphAdaptorBase Adaptor;
deba@414:     typedef GraphAdaptorBase<_Graph> Parent;
deba@414:   protected:
deba@414:     NodeFilterMap* _node_filter_map;
deba@414:     EdgeFilterMap* _edge_filter_map;
deba@414:     SubGraphAdaptorBase() : Parent(), 
deba@414: 			    _node_filter_map(0), _edge_filter_map(0) { }
deba@414: 
deba@414:     void setNodeFilterMap(NodeFilterMap& node_filter_map) {
deba@414:       _node_filter_map=&node_filter_map;
deba@414:     }
deba@414:     void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
deba@414:       _edge_filter_map=&edge_filter_map;
deba@414:     }
deba@414: 
deba@414:   public:
deba@414: 
deba@414:     typedef typename Parent::Node Node;
deba@414:     typedef typename Parent::Arc Arc;
deba@414:     typedef typename Parent::Edge Edge;
deba@414: 
deba@414:     void first(Node& i) const { 
deba@414:       Parent::first(i); 
deba@414:       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 
deba@414:     }
deba@414: 
deba@414:     void first(Arc& i) const { 
deba@414:       Parent::first(i); 
deba@414:       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 
deba@414:     }
deba@414: 
deba@414:     void first(Edge& i) const { 
deba@414:       Parent::first(i); 
deba@414:       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 
deba@414:     }
deba@414: 
deba@414:     void firstIn(Arc& i, const Node& n) const { 
deba@414:       Parent::firstIn(i, n); 
deba@414:       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); 
deba@414:     }
deba@414: 
deba@414:     void firstOut(Arc& i, const Node& n) const { 
deba@414:       Parent::firstOut(i, n); 
deba@414:       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); 
deba@414:     }
deba@414: 
deba@414:     void firstInc(Edge& i, bool& d, const Node& n) const { 
deba@414:       Parent::firstInc(i, d, n); 
deba@414:       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); 
deba@414:     }
deba@414: 
deba@414:     void next(Node& i) const { 
deba@414:       Parent::next(i); 
deba@414:       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 
deba@414:     }
deba@414:     void next(Arc& i) const { 
deba@414:       Parent::next(i); 
deba@414:       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 
deba@414:     }
deba@414:     void next(Edge& i) const { 
deba@414:       Parent::next(i); 
deba@414:       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 
deba@414:     }
deba@414:     void nextIn(Arc& i) const { 
deba@414:       Parent::nextIn(i); 
deba@414:       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); 
deba@414:     }
deba@414: 
deba@414:     void nextOut(Arc& i) const { 
deba@414:       Parent::nextOut(i); 
deba@414:       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); 
deba@414:     }
deba@414:     void nextInc(Edge& i, bool& d) const { 
deba@414:       Parent::nextInc(i, d); 
deba@414:       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); 
deba@414:     }
deba@414: 
deba@414:     /// \brief Hide the given node in the graph.
deba@414:     ///
deba@414:     /// This function hides \c n in the graph, i.e. the iteration 
deba@414:     /// jumps over it. This is done by simply setting the value of \c n  
deba@414:     /// to be false in the corresponding node-map.
deba@414:     void hide(const Node& n) const { _node_filter_map->set(n, false); }
deba@414: 
deba@414:     /// \brief Hide the given edge in the graph.
deba@414:     ///
deba@414:     /// This function hides \c e in the graph, i.e. the iteration 
deba@414:     /// jumps over it. This is done by simply setting the value of \c e  
deba@414:     /// to be false in the corresponding edge-map.
deba@414:     void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
deba@414: 
deba@414:     /// \brief Unhide the given node in the graph.
deba@414:     ///
deba@414:     /// The value of \c n is set to be true in the node-map which stores 
deba@414:     /// hide information. If \c n was hidden previuosly, then it is shown 
deba@414:     /// again
deba@414:      void unHide(const Node& n) const { _node_filter_map->set(n, true); }
deba@414: 
deba@414:     /// \brief Hide the given edge in the graph.
deba@414:     ///
deba@414:     /// The value of \c e is set to be true in the edge-map which stores 
deba@414:     /// hide information. If \c e was hidden previuosly, then it is shown 
deba@414:     /// again
deba@414:     void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
deba@414: 
deba@414:     /// \brief Returns true if \c n is hidden.
deba@414:     ///
deba@414:     /// Returns true if \c n is hidden.
deba@414:     bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
deba@414: 
deba@414:     /// \brief Returns true if \c e is hidden.
deba@414:     ///
deba@414:     /// Returns true if \c e is hidden.
deba@414:     bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
deba@414: 
deba@414:     typedef False NodeNumTag;
deba@414:     typedef False EdgeNumTag;
deba@414: 
deba@414:     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@414:     Arc findArc(const Node& u, const Node& v, 
deba@414: 		  const Arc& prev = INVALID) {
deba@414:       Arc arc = Parent::findArc(u, v, prev);
deba@414:       while (arc != INVALID && !(*_edge_filter_map)[arc]) {
deba@414:         arc = Parent::findArc(u, v, arc);
deba@414:       }
deba@414:       return arc;
deba@414:     }
deba@414:     Edge findEdge(const Node& u, const Node& v, 
deba@414: 		  const Edge& prev = INVALID) {
deba@414:       Edge edge = Parent::findEdge(u, v, prev);
deba@414:       while (edge != INVALID && !(*_edge_filter_map)[edge]) {
deba@414:         edge = Parent::findEdge(u, v, edge);
deba@414:       }
deba@414:       return edge;
deba@414:     }
deba@414: 
deba@414:     template <typename _Value>
deba@414:     class NodeMap : public SubMapExtender<Adaptor, 
deba@414:         typename Parent::template NodeMap<_Value> > {
deba@414:     public:
deba@414:       typedef _Value Value;
deba@414:       typedef SubMapExtender<Adaptor, typename Parent::
deba@414:                              template NodeMap<Value> > MapParent;
deba@414:     
deba@414:       NodeMap(const Adaptor& adaptor) 
deba@414: 	: MapParent(adaptor) {}
deba@414:       NodeMap(const Adaptor& adaptor, const Value& value) 
deba@414: 	: MapParent(adaptor, value) {}
deba@414:     
deba@414:     private:
deba@414:       NodeMap& operator=(const NodeMap& cmap) {
deba@414: 	return operator=<NodeMap>(cmap);
deba@414:       }
deba@414:     
deba@414:       template <typename CMap>
deba@414:       NodeMap& operator=(const CMap& cmap) {
deba@414:         MapParent::operator=(cmap);
deba@414: 	return *this;
deba@414:       }
deba@414:     };
deba@414: 
deba@414:     template <typename _Value>
deba@414:     class ArcMap : public SubMapExtender<Adaptor, 
deba@414: 	typename Parent::template ArcMap<_Value> > {
deba@414:     public:
deba@414:       typedef _Value Value;
deba@414:       typedef SubMapExtender<Adaptor, typename Parent::
deba@414:                              template ArcMap<Value> > MapParent;
deba@414:     
deba@414:       ArcMap(const Adaptor& adaptor) 
deba@414: 	: MapParent(adaptor) {}
deba@414:       ArcMap(const Adaptor& adaptor, const Value& value) 
deba@414: 	: MapParent(adaptor, value) {}
deba@414: 
deba@414:     private:
deba@414:       ArcMap& operator=(const ArcMap& cmap) {
deba@414: 	return operator=<ArcMap>(cmap);
deba@414:       }
deba@414:     
deba@414:       template <typename CMap>
deba@414:       ArcMap& operator=(const CMap& cmap) {
deba@414:         MapParent::operator=(cmap);
deba@414: 	return *this;
deba@414:       }
deba@414:     };
deba@414: 
deba@414:     template <typename _Value>
deba@414:     class EdgeMap : public SubMapExtender<Adaptor, 
deba@414:         typename Parent::template EdgeMap<_Value> > {
deba@414:     public:
deba@414:       typedef _Value Value;
deba@414:       typedef SubMapExtender<Adaptor, typename Parent::
deba@414:                              template EdgeMap<Value> > MapParent;
deba@414:     
deba@414:       EdgeMap(const Adaptor& adaptor) 
deba@414: 	: MapParent(adaptor) {}
deba@414: 
deba@414:       EdgeMap(const Adaptor& adaptor, const _Value& value) 
deba@414: 	: MapParent(adaptor, value) {}
deba@414: 
deba@414:     private:
deba@414:       EdgeMap& operator=(const EdgeMap& cmap) {
deba@414: 	return operator=<EdgeMap>(cmap);
deba@414:       }
deba@414:     
deba@414:       template <typename CMap>
deba@414:       EdgeMap& operator=(const CMap& cmap) {
deba@414:         MapParent::operator=(cmap);
deba@414: 	return *this;
deba@414:       }
deba@414:     };
deba@414: 
deba@414:   };
deba@414: 
deba@414:   /// \ingroup graph_adaptors
deba@414:   ///
deba@414:   /// \brief A graph adaptor for hiding nodes and arcs from an
deba@414:   /// undirected graph.
deba@414:   /// 
deba@414:   /// SubGraphAdaptor shows the graph with filtered node-set and
deba@414:   /// edge-set. If the \c checked parameter is true then it filters
deba@414:   /// the edge-set to do not get invalid edges which incident node is
deba@414:   /// filtered.
deba@414:   /// 
deba@414:   /// If the \c checked template parameter is false then we have to
deba@414:   /// note that the node-iterator cares only the filter on the
deba@414:   /// node-set, and the edge-iterator cares only the filter on the
deba@414:   /// edge-set.  This way the edge-map should filter all arcs which
deba@414:   /// has filtered end node.
deba@414:   template<typename _Graph, typename NodeFilterMap, 
deba@414: 	   typename EdgeFilterMap, bool checked = true>
deba@414:   class SubGraphAdaptor : 
deba@414:     public GraphAdaptorExtender<
deba@414:     SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
deba@414:   public:
deba@414:     typedef _Graph Graph;
deba@414:     typedef GraphAdaptorExtender<
deba@414:       SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
deba@414:   protected:
deba@414:     SubGraphAdaptor() { }
deba@414:   public:
deba@414:     SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map, 
deba@414: 		    EdgeFilterMap& edge_filter_map) { 
deba@414:       setGraph(_graph);
deba@414:       setNodeFilterMap(node_filter_map);
deba@414:       setEdgeFilterMap(edge_filter_map);
deba@414:     }
deba@414:   };
deba@414: 
deba@414:   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@414:   SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
deba@414:   subGraphAdaptor(const Graph& graph, 
deba@414:                    NodeFilterMap& nfm, ArcFilterMap& efm) {
deba@414:     return SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
deba@414:       (graph, nfm, efm);
deba@414:   }
deba@414: 
deba@414:   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@414:   SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
deba@414:   subGraphAdaptor(const Graph& graph, 
deba@414:                    NodeFilterMap& nfm, ArcFilterMap& efm) {
deba@414:     return SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
deba@414:       (graph, nfm, efm);
deba@414:   }
deba@414: 
deba@414:   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@414:   SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
deba@414:   subGraphAdaptor(const Graph& graph, 
deba@414:                    NodeFilterMap& nfm, ArcFilterMap& efm) {
deba@414:     return SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
deba@414:       (graph, nfm, efm);
deba@414:   }
deba@414: 
deba@414:   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@414:   SubGraphAdaptor<const Graph, const NodeFilterMap, const ArcFilterMap>
deba@414:   subGraphAdaptor(const Graph& graph, 
deba@414:                    NodeFilterMap& nfm, ArcFilterMap& efm) {
deba@414:     return SubGraphAdaptor<const Graph, const NodeFilterMap, 
deba@414:       const ArcFilterMap>(graph, nfm, efm);
deba@414:   }
deba@414: 
deba@414:   /// \ingroup graph_adaptors
deba@414:   ///
deba@414:   /// \brief An adaptor for hiding nodes from an graph.
deba@414:   ///
deba@414:   /// An adaptor for hiding nodes from an graph.  This
deba@414:   /// adaptor specializes SubGraphAdaptor in the way that only the
deba@414:   /// node-set can be filtered. In usual case the checked parameter is
deba@414:   /// true, we get the induced subgraph. But if the checked parameter
deba@414:   /// is false then we can filter only isolated nodes.
deba@414:   template<typename _Graph, typename _NodeFilterMap, bool checked = true>
deba@414:   class NodeSubGraphAdaptor : 
deba@414:     public SubGraphAdaptor<_Graph, _NodeFilterMap, 
deba@414: 			   ConstMap<typename _Graph::Edge, bool>, checked> {
deba@414:   public:
deba@414:     typedef _Graph Graph;
deba@414:     typedef _NodeFilterMap NodeFilterMap;
deba@414:     typedef SubGraphAdaptor<Graph, NodeFilterMap, 
deba@414: 			    ConstMap<typename Graph::Edge, bool> > Parent;
deba@414:   protected:
deba@414:     ConstMap<typename Graph::Edge, bool> const_true_map;
deba@414: 
deba@414:     NodeSubGraphAdaptor() : const_true_map(true) {
deba@414:       Parent::setEdgeFilterMap(const_true_map);
deba@414:     }
deba@414: 
deba@414:   public:
deba@414:     NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) : 
deba@414:       Parent(), const_true_map(true) { 
deba@414:       Parent::setGraph(_graph);
deba@414:       Parent::setNodeFilterMap(node_filter_map);
deba@414:       Parent::setEdgeFilterMap(const_true_map);
deba@414:     }
deba@414:   };
deba@414: 
deba@414:   template<typename Graph, typename NodeFilterMap>
deba@414:   NodeSubGraphAdaptor<const Graph, NodeFilterMap>
deba@414:   nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
deba@414:     return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
deba@414:   }
deba@414: 
deba@414:   template<typename Graph, typename NodeFilterMap>
deba@414:   NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
deba@414:   nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
deba@414:     return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
deba@414:   }
deba@414: 
deba@414:   /// \ingroup graph_adaptors
deba@414:   ///
deba@414:   /// \brief An adaptor for hiding edges from an graph.
deba@414:   ///
deba@414:   /// \warning Graph adaptors are in even more experimental state
deba@414:   /// than the other parts of the lib. Use them at you own risk.
deba@414:   ///
deba@414:   /// An adaptor for hiding edges from an graph.
deba@414:   /// This adaptor specializes SubGraphAdaptor in the way that
deba@414:   /// only the arc-set 
deba@414:   /// can be filtered.
deba@414:   template<typename _Graph, typename _EdgeFilterMap>
deba@414:   class EdgeSubGraphAdaptor : 
deba@414:     public SubGraphAdaptor<_Graph, ConstMap<typename _Graph::Node,bool>, 
deba@414:                            _EdgeFilterMap, false> {
deba@414:   public:
deba@414:     typedef _Graph Graph;
deba@414:     typedef _EdgeFilterMap EdgeFilterMap;
deba@414:     typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
deba@414: 			    EdgeFilterMap, false> Parent;
deba@414:   protected:
deba@414:     ConstMap<typename Graph::Node, bool> const_true_map;
deba@414: 
deba@414:     EdgeSubGraphAdaptor() : const_true_map(true) {
deba@414:       Parent::setNodeFilterMap(const_true_map);
deba@414:     }
deba@414: 
deba@414:   public:
deba@414: 
deba@414:     EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& edge_filter_map) : 
deba@414:       Parent(), const_true_map(true) { 
deba@414:       Parent::setGraph(_graph);
deba@414:       Parent::setNodeFilterMap(const_true_map);
deba@414:       Parent::setEdgeFilterMap(edge_filter_map);
deba@414:     }
deba@414: 
deba@414:   };
deba@414: 
deba@414:   template<typename Graph, typename EdgeFilterMap>
deba@414:   EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
deba@414:   edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
deba@414:     return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
deba@414:   }
deba@414: 
deba@414:   template<typename Graph, typename EdgeFilterMap>
deba@414:   EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
deba@414:   edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
deba@414:     return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
deba@414:   }
deba@414: 
deba@414:   /// \brief Base of direct graph adaptor
deba@414:   ///
deba@414:   /// Base class of the direct graph adaptor. All public member
deba@414:   /// of this class can be used with the DirGraphAdaptor too.
deba@414:   /// \sa DirGraphAdaptor
deba@414:   template <typename _Graph, typename _DirectionMap>
deba@414:   class DirGraphAdaptorBase {
deba@414:   public:
deba@414:     
deba@414:     typedef _Graph Graph;
deba@414:     typedef _DirectionMap DirectionMap;
deba@414: 
deba@414:     typedef typename Graph::Node Node;
deba@414:     typedef typename Graph::Edge Arc;
deba@414:    
deba@414:     /// \brief Reverse arc
deba@414:     /// 
deba@414:     /// It reverse the given arc. It simply negate the direction in the map.
deba@414:     void reverseArc(const Arc& arc) {
deba@414:       _direction->set(arc, !(*_direction)[arc]);
deba@414:     }
deba@414: 
deba@414:     void first(Node& i) const { _graph->first(i); }
deba@414:     void first(Arc& i) const { _graph->first(i); }
deba@414:     void firstIn(Arc& i, const Node& n) const {
deba@414:       bool d;
deba@414:       _graph->firstInc(i, d, n);
deba@414:       while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
deba@414:     }
deba@414:     void firstOut(Arc& i, const Node& n ) const { 
deba@414:       bool d;
deba@414:       _graph->firstInc(i, d, n);
deba@414:       while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
deba@414:     }
deba@414: 
deba@414:     void next(Node& i) const { _graph->next(i); }
deba@414:     void next(Arc& i) const { _graph->next(i); }
deba@414:     void nextIn(Arc& i) const {
deba@414:       bool d = !(*_direction)[i];
deba@414:       _graph->nextInc(i, d);
deba@414:       while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
deba@414:     }
deba@414:     void nextOut(Arc& i) const {
deba@414:       bool d = (*_direction)[i];
deba@414:       _graph->nextInc(i, d);
deba@414:       while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
deba@414:     }
deba@414: 
deba@414:     Node source(const Arc& e) const { 
deba@414:       return (*_direction)[e] ? _graph->u(e) : _graph->v(e); 
deba@414:     }
deba@414:     Node target(const Arc& e) const { 
deba@414:       return (*_direction)[e] ? _graph->v(e) : _graph->u(e); 
deba@414:     }
deba@414: 
deba@414:     typedef NodeNumTagIndicator<Graph> NodeNumTag;
deba@414:     int nodeNum() const { return _graph->nodeNum(); }
deba@414:     
deba@414:     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
deba@414:     int arcNum() const { return _graph->edgeNum(); }
deba@414: 
deba@414:     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@414:     Arc findArc(const Node& u, const Node& v, 
deba@414: 		  const Arc& prev = INVALID) {
deba@414:       Arc arc = prev;
deba@414:       bool d = arc == INVALID ? true : (*_direction)[arc];
deba@414:       if (d) {
deba@414:         arc = _graph->findEdge(u, v, arc);
deba@414:         while (arc != INVALID && !(*_direction)[arc]) {
deba@414:           _graph->findEdge(u, v, arc);
deba@414:         }
deba@414:         if (arc != INVALID) return arc;
deba@414:       }
deba@414:       _graph->findEdge(v, u, arc);
deba@414:       while (arc != INVALID && (*_direction)[arc]) {
deba@414:         _graph->findEdge(u, v, arc);
deba@414:       }
deba@414:       return arc;
deba@414:     }
deba@414:   
deba@414:     Node addNode() { 
deba@414:       return Node(_graph->addNode()); 
deba@414:     }
deba@414: 
deba@414:     Arc addArc(const Node& u, const Node& v) {
deba@414:       Arc arc = _graph->addArc(u, v);
deba@414:       _direction->set(arc, _graph->source(arc) == u);
deba@414:       return arc; 
deba@414:     }
deba@414: 
deba@414:     void erase(const Node& i) { _graph->erase(i); }
deba@414:     void erase(const Arc& i) { _graph->erase(i); }
deba@414:   
deba@414:     void clear() { _graph->clear(); }
deba@414:     
deba@414:     int id(const Node& v) const { return _graph->id(v); }
deba@414:     int id(const Arc& e) const { return _graph->id(e); }
deba@414: 
deba@414:     Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
deba@414:     Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
deba@414: 
deba@414:     int maxNodeId() const { return _graph->maxNodeId(); }
deba@414:     int maxArcId() const { return _graph->maxEdgeId(); }
deba@414: 
deba@414:     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@414:     NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 
deba@414: 
deba@414:     typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
deba@414:     ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 
deba@414: 
deba@414:     template <typename _Value>
deba@414:     class NodeMap : public _Graph::template NodeMap<_Value> {
deba@414:     public:
deba@414: 
deba@414:       typedef typename _Graph::template NodeMap<_Value> Parent;
deba@414: 
deba@414:       explicit NodeMap(const DirGraphAdaptorBase& adapter) 
deba@414: 	: Parent(*adapter._graph) {}
deba@414: 
deba@414:       NodeMap(const DirGraphAdaptorBase& adapter, const _Value& value)
deba@414: 	: Parent(*adapter._graph, value) {}
deba@414: 
deba@414:     private:
deba@414:       NodeMap& operator=(const NodeMap& cmap) {
deba@414:         return operator=<NodeMap>(cmap);
deba@414:       }
deba@414: 
deba@414:       template <typename CMap>
deba@414:       NodeMap& operator=(const CMap& cmap) {
deba@414:         Parent::operator=(cmap);
deba@414:         return *this;
deba@414:       }
deba@414: 
deba@414:     };
deba@414: 
deba@414:     template <typename _Value>
deba@414:     class ArcMap : public _Graph::template EdgeMap<_Value> {
deba@414:     public:
deba@414: 
deba@414:       typedef typename Graph::template EdgeMap<_Value> Parent;
deba@414: 
deba@414:       explicit ArcMap(const DirGraphAdaptorBase& adapter) 
deba@414: 	: Parent(*adapter._graph) { }
deba@414: 
deba@414:       ArcMap(const DirGraphAdaptorBase& adapter, const _Value& value)
deba@414: 	: Parent(*adapter._graph, value) { }
deba@414: 
deba@414:     private:
deba@414:       ArcMap& operator=(const ArcMap& cmap) {
deba@414:         return operator=<ArcMap>(cmap);
deba@414:       }
deba@414: 
deba@414:       template <typename CMap>
deba@414:       ArcMap& operator=(const CMap& cmap) {
deba@414:         Parent::operator=(cmap);
deba@414:         return *this;
deba@414:       }
deba@414:     };
deba@414: 
deba@414:     
deba@414: 
deba@414:   protected:
deba@414:     Graph* _graph;
deba@414:     DirectionMap* _direction;
deba@414: 
deba@414:     void setDirectionMap(DirectionMap& direction) {
deba@414:       _direction = &direction;
deba@414:     }
deba@414: 
deba@414:     void setGraph(Graph& graph) {
deba@414:       _graph = &graph;
deba@414:     }
deba@414: 
deba@414:   };
deba@414: 
deba@414: 
deba@414:   /// \ingroup graph_adaptors
deba@414:   ///
deba@414:   /// \brief A directed graph is made from an graph by an adaptor
deba@414:   ///
deba@414:   /// This adaptor gives a direction for each edge in the undirected
deba@414:   /// graph. The direction of the arcs stored in the
deba@414:   /// DirectionMap. This map is a bool map on the edges. If
deba@414:   /// the edge is mapped to true then the direction of the directed
deba@414:   /// arc will be the same as the default direction of the edge. The
deba@414:   /// arcs can be easily reverted by the \ref
deba@414:   /// DirGraphAdaptorBase::reverseArc "reverseArc()" member in the
deba@414:   /// adaptor.
deba@414:   ///
deba@414:   /// It can be used to solve orientation problems on directed graphs.
deba@414:   /// For example how can we orient an graph to get the minimum
deba@414:   /// number of strongly connected components. If we orient the arcs with
deba@414:   /// the dfs algorithm out from the source then we will get such an 
deba@414:   /// orientation. 
deba@414:   ///
deba@414:   /// We use the \ref DfsVisitor "visitor" interface of the 
deba@414:   /// \ref DfsVisit "dfs" algorithm:
deba@414:   ///\code
deba@414:   /// template <typename DirMap>
deba@414:   /// class OrientVisitor : public DfsVisitor<Graph> {
deba@414:   /// public:
deba@414:   ///
deba@414:   ///   OrientVisitor(const Graph& graph, DirMap& dirMap)
deba@414:   ///     : _graph(graph), _dirMap(dirMap), _processed(graph, false) {}
deba@414:   ///
deba@414:   ///   void discover(const Arc& arc) {
deba@414:   ///     _processed.set(arc, true);
deba@414:   ///     _dirMap.set(arc, _graph.direction(arc));
deba@414:   ///   }
deba@414:   ///
deba@414:   ///   void examine(const Arc& arc) {
deba@414:   ///     if (_processed[arc]) return;
deba@414:   ///     _processed.set(arc, true);
deba@414:   ///     _dirMap.set(arc, _graph.direction(arc));
deba@414:   ///   }  
deba@414:   /// 
deba@414:   /// private:
deba@414:   ///   const Graph& _graph;  
deba@414:   ///   DirMap& _dirMap;
deba@414:   ///   Graph::EdgeMap<bool> _processed;
deba@414:   /// };
deba@414:   ///\endcode
deba@414:   ///
deba@414:   /// And now we can use the orientation:
deba@414:   ///\code
deba@414:   /// Graph::EdgeMap<bool> dmap(graph);
deba@414:   ///
deba@414:   /// typedef OrientVisitor<Graph::EdgeMap<bool> > Visitor;
deba@414:   /// Visitor visitor(graph, dmap);
deba@414:   ///
deba@414:   /// DfsVisit<Graph, Visitor> dfs(graph, visitor);
deba@414:   ///
deba@414:   /// dfs.run();
deba@414:   ///
deba@414:   /// typedef DirGraphAdaptor<Graph> DGraph;
deba@414:   /// DGraph dgraph(graph, dmap);
deba@414:   ///
deba@414:   /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) == 
deba@414:   ///              countBiArcConnectedComponents(graph), "Wrong Orientation");
deba@414:   ///\endcode
deba@414:   ///
deba@414:   /// The number of the bi-connected components is a lower bound for
deba@414:   /// the number of the strongly connected components in the directed
deba@414:   /// graph because if we contract the bi-connected components to
deba@414:   /// nodes we will get a tree therefore we cannot orient arcs in
deba@414:   /// both direction between bi-connected components. In the other way
deba@414:   /// the algorithm will orient one component to be strongly
deba@414:   /// connected. The two relations proof that the assertion will
deba@414:   /// be always true and the found solution is optimal.
deba@414:   ///
deba@414:   /// \sa DirGraphAdaptorBase
deba@414:   /// \sa dirGraphAdaptor
deba@414:   template<typename _Graph, 
deba@414:            typename DirectionMap = typename _Graph::template EdgeMap<bool> > 
deba@414:   class DirGraphAdaptor : 
deba@414:     public DigraphAdaptorExtender<DirGraphAdaptorBase<_Graph, DirectionMap> > {
deba@414:   public:
deba@414:     typedef _Graph Graph;
deba@414:     typedef DigraphAdaptorExtender<
deba@414:       DirGraphAdaptorBase<_Graph, DirectionMap> > Parent;
deba@414:   protected:
deba@414:     DirGraphAdaptor() { }
deba@414:   public:
deba@414:     
deba@414:     /// \brief Constructor of the adaptor
deba@414:     ///
deba@414:     /// Constructor of the adaptor
deba@414:     DirGraphAdaptor(Graph& graph, DirectionMap& direction) { 
deba@414:       setGraph(graph);
deba@414:       setDirectionMap(direction);
deba@414:     }
deba@414:   };
deba@414: 
deba@414:   /// \brief Just gives back a DirGraphAdaptor
deba@414:   ///
deba@414:   /// Just gives back a DirGraphAdaptor
deba@414:   template<typename Graph, typename DirectionMap>
deba@414:   DirGraphAdaptor<const Graph, DirectionMap>
deba@414:   dirGraphAdaptor(const Graph& graph, DirectionMap& dm) {
deba@414:     return DirGraphAdaptor<const Graph, DirectionMap>(graph, dm);
deba@414:   }
deba@414: 
deba@414:   template<typename Graph, typename DirectionMap>
deba@414:   DirGraphAdaptor<const Graph, const DirectionMap>
deba@414:   dirGraphAdaptor(const Graph& graph, const DirectionMap& dm) {
deba@414:     return DirGraphAdaptor<const Graph, const DirectionMap>(graph, dm);
deba@414:   }
deba@414: 
deba@414: }
deba@414: 
deba@414: #endif