deba@1979: /* -*- C++ -*-
deba@1979:  *
deba@1979:  * This file is a part of LEMON, a generic C++ optimization library
deba@1979:  *
alpar@2553:  * Copyright (C) 2003-2008
deba@1979:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1979:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1979:  *
deba@1979:  * Permission to use, modify and distribute this software is granted
deba@1979:  * provided that this copyright notice appears in all copies. For
deba@1979:  * precise terms see the accompanying LICENSE file.
deba@1979:  *
deba@1979:  * This software is provided "AS IS" with no warranty of any kind,
deba@1979:  * express or implied, and with no claim as to its suitability for any
deba@1979:  * purpose.
deba@1979:  *
deba@1979:  */
deba@1979: 
deba@1979: #ifndef LEMON_UGRAPH_ADAPTOR_H
deba@1979: #define LEMON_UGRAPH_ADAPTOR_H
deba@1979: 
deba@1979: ///\ingroup graph_adaptors
deba@1979: ///\file
deba@1979: ///\brief Several graph adaptors.
deba@1979: ///
deba@1979: ///This file contains several useful ugraph adaptor functions.
deba@1979: ///
deba@1979: ///\author Balazs Dezso
deba@1979: 
deba@1993: #include <lemon/bits/invalid.h>
deba@1979: #include <lemon/maps.h>
deba@1979: 
deba@1979: #include <lemon/bits/graph_adaptor_extender.h>
deba@1979: 
deba@1993: #include <lemon/bits/traits.h>
deba@1979: 
deba@1979: #include <iostream>
deba@1979: 
deba@1979: namespace lemon {
deba@1979: 
deba@1979:   /// \brief Base type for the Graph Adaptors
deba@1979:   ///
deba@1979:   /// This is the base type for most of LEMON graph adaptors. 
deba@1979:   /// This class implements a trivial graph adaptor i.e. it only wraps the 
deba@1979:   /// functions and types of the graph. The purpose of this class is to 
deba@1979:   /// make easier implementing graph adaptors. E.g. if an adaptor is 
deba@1979:   /// considered which differs from the wrapped graph only in some of its 
deba@1979:   /// functions or types, then it can be derived from GraphAdaptor, and only 
deba@1979:   /// the differences should be implemented.
deba@1979:   ///
deba@1979:   /// \author Balazs Dezso 
deba@1979:   template<typename _UGraph>
deba@1979:   class UGraphAdaptorBase {
deba@1979:   public:
deba@1979:     typedef _UGraph Graph;
deba@1979:     typedef Graph ParentGraph;
deba@1979: 
deba@1979:   protected:
deba@1979:     Graph* graph;
deba@1979: 
deba@1979:     UGraphAdaptorBase() : graph(0) {}
deba@1979: 
deba@1979:     void setGraph(Graph& _graph) { graph=&_graph; }
deba@1979: 
deba@1979:   public:
deba@1979:     UGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
deba@1979:  
deba@1979:     typedef typename Graph::Node Node;
deba@1979:     typedef typename Graph::Edge Edge;
deba@1979:     typedef typename Graph::UEdge UEdge;
deba@1979:    
deba@1979:     void first(Node& i) const { graph->first(i); }
deba@1979:     void first(Edge& i) const { graph->first(i); }
deba@1979:     void first(UEdge& i) const { graph->first(i); }
deba@1979:     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
deba@1979:     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
deba@1979:     void firstInc(UEdge &i, bool &d, const Node &n) const {
deba@1979:       graph->firstInc(i, d, n);
deba@1979:     }
deba@1979: 
deba@1979:     void next(Node& i) const { graph->next(i); }
deba@1979:     void next(Edge& i) const { graph->next(i); }
deba@1979:     void next(UEdge& i) const { graph->next(i); }
deba@1979:     void nextIn(Edge& i) const { graph->nextIn(i); }
deba@1979:     void nextOut(Edge& i) const { graph->nextOut(i); }
deba@1979:     void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
deba@1979: 
deba@1979:     Node source(const UEdge& e) const { return graph->source(e); }
deba@1979:     Node target(const UEdge& e) const { return graph->target(e); }
deba@1979: 
deba@1979:     Node source(const Edge& e) const { return graph->source(e); }
deba@1979:     Node target(const Edge& e) const { return graph->target(e); }
deba@1979: 
deba@1979:     typedef NodeNumTagIndicator<Graph> NodeNumTag;
deba@1979:     int nodeNum() const { return graph->nodeNum(); }
deba@1979:     
deba@1979:     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
deba@1979:     int edgeNum() const { return graph->edgeNum(); }
deba@2031:     int uEdgeNum() const { return graph->uEdgeNum(); }
deba@1979: 
deba@1979:     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@2386:     Edge findEdge(const Node& u, const Node& v, 
deba@1979: 		  const Edge& prev = INVALID) {
deba@2386:       return graph->findEdge(u, v, prev);
deba@1979:     }
deba@2386:     UEdge findUEdge(const Node& u, const Node& v, 
deba@1979:                     const UEdge& prev = INVALID) {
deba@2386:       return graph->findUEdge(u, v, prev);
deba@1979:     }
deba@1979:   
deba@1979:     Node addNode() const { return graph->addNode(); }
deba@2386:     UEdge addEdge(const Node& u, const Node& v) const { 
deba@2386:       return graph->addEdge(u, v); 
deba@1979:     }
deba@1979: 
deba@1979:     void erase(const Node& i) const { graph->erase(i); }
deba@2031:     void erase(const UEdge& i) const { graph->erase(i); }
deba@1979:   
deba@1979:     void clear() const { graph->clear(); }
deba@1979:     
deba@2031:     bool direction(const Edge& e) const { return graph->direction(e); }
deba@2031:     Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
deba@2031: 
deba@1979:     int id(const Node& v) const { return graph->id(v); }
deba@2031:     int id(const Edge& e) const { return graph->id(e); }
deba@1979:     int id(const UEdge& e) const { return graph->id(e); }
deba@1979: 
deba@2386:     Node fromNodeId(int ix) const {
deba@2386:       return graph->fromNodeId(ix);
deba@2031:     }
deba@2031: 
deba@2386:     Edge fromEdgeId(int ix) const {
deba@2386:       return graph->fromEdgeId(ix);
deba@2031:     }
deba@2031: 
deba@2386:     UEdge fromUEdgeId(int ix) const {
deba@2386:       return graph->fromUEdgeId(ix);
deba@2031:     }
deba@1991: 
deba@1991:     int maxNodeId() const {
deba@1991:       return graph->maxNodeId();
deba@1979:     }
deba@1979: 
deba@1991:     int maxEdgeId() const {
deba@1991:       return graph->maxEdgeId();
deba@1979:     }
deba@1979: 
deba@1991:     int maxUEdgeId() const {
deba@1991:       return graph->maxEdgeId();
deba@1979:     }
deba@1979: 
deba@1991:     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@1991: 
deba@2381:     NodeNotifier& notifier(Node) const {
deba@2381:       return graph->notifier(Node());
deba@1991:     } 
deba@1991: 
deba@1991:     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
deba@1991: 
deba@2381:     EdgeNotifier& notifier(Edge) const {
deba@2381:       return graph->notifier(Edge());
deba@1991:     } 
deba@1991: 
deba@1991:     typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
deba@1991: 
deba@2381:     UEdgeNotifier& notifier(UEdge) const {
deba@2381:       return graph->notifier(UEdge());
deba@1991:     } 
deba@1979: 
deba@1979:     template <typename _Value>
deba@1979:     class NodeMap : public Graph::template NodeMap<_Value> {
deba@1979:     public:
deba@1979:       typedef typename Graph::template NodeMap<_Value> Parent;
deba@1979:       explicit NodeMap(const UGraphAdaptorBase<Graph>& ga) 
deba@1979: 	: Parent(*ga.graph) {}
deba@1979:       NodeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
deba@1979: 	: Parent(*ga.graph, value) {}
deba@1979: 
deba@1979:       NodeMap& operator=(const NodeMap& cmap) {
deba@1979: 	return operator=<NodeMap>(cmap);
deba@1979:       }
deba@1979: 
deba@1979:       template <typename CMap>
deba@1979:       NodeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031:         return *this;
deba@1979:       }
deba@2031: 
deba@1979:     };
deba@1979: 
deba@1979:     template <typename _Value>
deba@1979:     class EdgeMap : public Graph::template EdgeMap<_Value> {
deba@1979:     public:
deba@1979:       typedef typename Graph::template EdgeMap<_Value> Parent;
deba@1979:       explicit EdgeMap(const UGraphAdaptorBase<Graph>& ga) 
deba@1979: 	: Parent(*ga.graph) {}
deba@1979:       EdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
deba@1979: 	: Parent(*ga.graph, value) {}
deba@1979: 
deba@1979:       EdgeMap& operator=(const EdgeMap& cmap) {
deba@1979: 	return operator=<EdgeMap>(cmap);
deba@1979:       }
deba@1979: 
deba@1979:       template <typename CMap>
deba@1979:       EdgeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@1979: 	return *this;
deba@1979:       }
deba@1979:     };
deba@1979: 
deba@1979:     template <typename _Value>
deba@1979:     class UEdgeMap : public Graph::template UEdgeMap<_Value> {
deba@1979:     public:
deba@1979:       typedef typename Graph::template UEdgeMap<_Value> Parent;
deba@1979:       explicit UEdgeMap(const UGraphAdaptorBase<Graph>& ga) 
deba@1979: 	: Parent(*ga.graph) {}
deba@1979:       UEdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
deba@1979: 	: Parent(*ga.graph, value) {}
deba@1979: 
deba@1979:       UEdgeMap& operator=(const UEdgeMap& cmap) {
deba@1979: 	return operator=<UEdgeMap>(cmap);
deba@1979:       }
deba@1979: 
deba@1979:       template <typename CMap>
deba@1979:       UEdgeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031:         return *this;
deba@1979:       }
deba@1979:     };
deba@1979: 
deba@1979:   };
deba@1979: 
deba@1979:   /// \ingroup graph_adaptors
deba@2084:   ///
deba@2084:   /// \brief Trivial undirected graph adaptor
deba@2084:   ///
deba@2084:   /// This class is an adaptor which does not change the adapted undirected
deba@2084:   /// graph. It can be used only to test the undirected graph adaptors.
deba@1979:   template <typename _UGraph>
deba@1979:   class UGraphAdaptor 
deba@1979:     : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > { 
deba@1979:   public:
deba@1979:     typedef _UGraph Graph;
deba@1979:     typedef UGraphAdaptorExtender<UGraphAdaptorBase<_UGraph> > Parent;
deba@1979:   protected:
deba@1979:     UGraphAdaptor() : Parent() {}
deba@1979: 
deba@1979:   public:
deba@1979:     explicit UGraphAdaptor(Graph& _graph) { setGraph(_graph); }
deba@1979:   };
deba@1979: 
deba@1979:   template <typename _UGraph, typename NodeFilterMap, 
deba@1979: 	    typename UEdgeFilterMap, bool checked = true>
deba@1979:   class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> {
deba@1979:   public:
deba@1979:     typedef _UGraph Graph;
deba@2031:     typedef SubUGraphAdaptorBase Adaptor;
deba@1979:     typedef UGraphAdaptorBase<_UGraph> Parent;
deba@1979:   protected:
deba@1979: 
deba@1979:     NodeFilterMap* node_filter_map;
deba@1979:     UEdgeFilterMap* uedge_filter_map;
deba@1979: 
deba@1979:     SubUGraphAdaptorBase() 
deba@1979:       : Parent(), node_filter_map(0), uedge_filter_map(0) { }
deba@1979: 
deba@1979:     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
deba@1979:       node_filter_map=&_node_filter_map;
deba@1979:     }
deba@1979:     void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
deba@1979:       uedge_filter_map=&_uedge_filter_map;
deba@1979:     }
deba@1979: 
deba@1979:   public:
deba@1979: 
deba@1979:     typedef typename Parent::Node Node;
deba@1979:     typedef typename Parent::Edge Edge;
deba@1979:     typedef typename Parent::UEdge UEdge;
deba@1979: 
deba@1979:     void first(Node& i) const { 
deba@1979:       Parent::first(i); 
deba@1979:       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void first(Edge& i) const { 
deba@1979:       Parent::first(i); 
deba@1979:       while (i!=INVALID && (!(*uedge_filter_map)[i] 
deba@1979: 	     || !(*node_filter_map)[Parent::source(i)]
deba@1979: 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void first(UEdge& i) const { 
deba@1979:       Parent::first(i); 
deba@1979:       while (i!=INVALID && (!(*uedge_filter_map)[i] 
deba@1979: 	     || !(*node_filter_map)[Parent::source(i)]
deba@1979: 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void firstIn(Edge& i, const Node& n) const { 
deba@1979:       Parent::firstIn(i, n); 
deba@1979:       while (i!=INVALID && (!(*uedge_filter_map)[i] 
deba@1979: 	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void firstOut(Edge& i, const Node& n) const { 
deba@1979:       Parent::firstOut(i, n); 
deba@1979:       while (i!=INVALID && (!(*uedge_filter_map)[i] 
deba@1979: 	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void firstInc(UEdge& i, bool& d, const Node& n) const { 
deba@1979:       Parent::firstInc(i, d, n); 
deba@1979:       while (i!=INVALID && (!(*uedge_filter_map)[i] 
deba@2381:             || !(*node_filter_map)[Parent::source(i)]
deba@1979:             || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d); 
deba@1979:     }
deba@1979: 
deba@1979:     void next(Node& i) const { 
deba@1979:       Parent::next(i); 
deba@1979:       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void next(Edge& i) const { 
deba@1979:       Parent::next(i); 
deba@1979:       while (i!=INVALID && (!(*uedge_filter_map)[i] 
deba@1979: 	     || !(*node_filter_map)[Parent::source(i)]
deba@1979: 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void next(UEdge& i) const { 
deba@1979:       Parent::next(i); 
deba@1979:       while (i!=INVALID && (!(*uedge_filter_map)[i] 
deba@1979: 	     || !(*node_filter_map)[Parent::source(i)]
deba@1979: 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void nextIn(Edge& i) const { 
deba@1979:       Parent::nextIn(i); 
deba@1979:       while (i!=INVALID && (!(*uedge_filter_map)[i] 
deba@1979: 	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void nextOut(Edge& i) const { 
deba@1979:       Parent::nextOut(i); 
deba@1979:       while (i!=INVALID && (!(*uedge_filter_map)[i] 
deba@1979: 	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void nextInc(UEdge& i, bool& d) const { 
deba@1979:       Parent::nextInc(i, d); 
deba@2381:       while (i!=INVALID && (!(*uedge_filter_map)[i]
deba@2381:             || !(*node_filter_map)[Parent::source(i)]
deba@2381:             || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d); 
deba@1979:     }
deba@1979: 
deba@2084:     /// \brief Hide the given node in the graph.
deba@2084:     ///
deba@1979:     /// This function hides \c n in the graph, i.e. the iteration 
deba@1979:     /// jumps over it. This is done by simply setting the value of \c n  
deba@1979:     /// to be false in the corresponding node-map.
deba@1979:     void hide(const Node& n) const { node_filter_map->set(n, false); }
deba@1979: 
deba@2084:     /// \brief Hide the given undirected edge in the graph.
deba@2084:     ///
deba@1979:     /// This function hides \c e in the graph, i.e. the iteration 
deba@1979:     /// jumps over it. This is done by simply setting the value of \c e  
deba@2084:     /// to be false in the corresponding uedge-map.
deba@1979:     void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
deba@1979: 
deba@2084:     /// \brief Unhide the given node in the graph.
deba@2084:     ///
deba@1979:     /// The value of \c n is set to be true in the node-map which stores 
deba@1979:     /// hide information. If \c n was hidden previuosly, then it is shown 
deba@1979:     /// again
deba@1979:      void unHide(const Node& n) const { node_filter_map->set(n, true); }
deba@1979: 
deba@2084:     /// \brief Hide the given undirected edge in the graph.
deba@2084:     ///
deba@2084:     /// The value of \c e is set to be true in the uedge-map which stores 
deba@1979:     /// hide information. If \c e was hidden previuosly, then it is shown 
deba@1979:     /// again
deba@1979:     void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
deba@1979: 
deba@2084:     /// \brief Returns true if \c n is hidden.
deba@2084:     ///
deba@1979:     /// Returns true if \c n is hidden.
deba@1979:     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
deba@1979: 
deba@2084:     /// \brief Returns true if \c e is hidden.
deba@1979:     ///
deba@2084:     /// Returns true if \c e is hidden.
deba@1979:     bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
deba@1979: 
deba@1979:     typedef False NodeNumTag;
deba@1979:     typedef False EdgeNumTag;
deba@1991: 
deba@1991:     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@2386:     Edge findEdge(const Node& u, const Node& v, 
deba@1991: 		  const Edge& prev = INVALID) {
deba@2386:       if (!(*node_filter_map)[u] || !(*node_filter_map)[v]) {
deba@1991:         return INVALID;
deba@1991:       }
deba@2386:       Edge edge = Parent::findEdge(u, v, prev);
deba@1991:       while (edge != INVALID && !(*uedge_filter_map)[edge]) {
deba@2386:         edge = Parent::findEdge(u, v, edge);
deba@1991:       }
deba@1991:       return edge;
deba@1991:     }
deba@2386:     UEdge findUEdge(const Node& u, const Node& v, 
deba@1991: 		  const UEdge& prev = INVALID) {
deba@2386:       if (!(*node_filter_map)[u] || !(*node_filter_map)[v]) {
deba@1991:         return INVALID;
deba@1991:       }
deba@2386:       UEdge uedge = Parent::findUEdge(u, v, prev);
deba@1991:       while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
deba@2386:         uedge = Parent::findUEdge(u, v, uedge);
deba@1991:       }
deba@1991:       return uedge;
deba@1991:     }
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class NodeMap 
deba@2031:       : public SubMapExtender<Adaptor, 
deba@2031:                               typename Parent::template NodeMap<_Value> > 
deba@2031:     {
deba@2031:     public:
deba@2031:       typedef Adaptor Graph;
deba@2031:       typedef SubMapExtender<Adaptor, typename Parent::
deba@2031:                              template NodeMap<_Value> > Parent;
deba@2031:     
deba@2386:       NodeMap(const Graph& g) 
deba@2386: 	: Parent(g) {}
deba@2386:       NodeMap(const Graph& g, const _Value& v) 
deba@2386: 	: Parent(g, v) {}
deba@2031:     
deba@2031:       NodeMap& operator=(const NodeMap& cmap) {
deba@2031: 	return operator=<NodeMap>(cmap);
deba@2031:       }
deba@2031:     
deba@2031:       template <typename CMap>
deba@2031:       NodeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class EdgeMap 
deba@2031:       : public SubMapExtender<Adaptor, 
deba@2031:                               typename Parent::template EdgeMap<_Value> > 
deba@2031:     {
deba@2031:     public:
deba@2031:       typedef Adaptor Graph;
deba@2031:       typedef SubMapExtender<Adaptor, typename Parent::
deba@2031:                              template EdgeMap<_Value> > Parent;
deba@2031:     
deba@2386:       EdgeMap(const Graph& g) 
deba@2386: 	: Parent(g) {}
deba@2386:       EdgeMap(const Graph& g, const _Value& v) 
deba@2386: 	: Parent(g, v) {}
deba@2031:     
deba@2031:       EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031: 	return operator=<EdgeMap>(cmap);
deba@2031:       }
deba@2031:     
deba@2031:       template <typename CMap>
deba@2031:       EdgeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class UEdgeMap 
deba@2031:       : public SubMapExtender<Adaptor, 
deba@2031:                               typename Parent::template UEdgeMap<_Value> > 
deba@2031:     {
deba@2031:     public:
deba@2031:       typedef Adaptor Graph;
deba@2031:       typedef SubMapExtender<Adaptor, typename Parent::
deba@2031:                              template UEdgeMap<_Value> > Parent;
deba@2031:     
deba@2386:       UEdgeMap(const Graph& g) 
deba@2386: 	: Parent(g) {}
deba@2386:       UEdgeMap(const Graph& g, const _Value& v) 
deba@2386: 	: Parent(g, v) {}
deba@2031:     
deba@2031:       UEdgeMap& operator=(const UEdgeMap& cmap) {
deba@2031: 	return operator=<UEdgeMap>(cmap);
deba@2031:       }
deba@2031:     
deba@2031:       template <typename CMap>
deba@2031:       UEdgeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
deba@1979:   };
deba@1979: 
deba@1979:   template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
deba@1979:   class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false> 
deba@1979:     : public UGraphAdaptorBase<_UGraph> {
deba@1979:   public:
deba@1979:     typedef _UGraph Graph;
deba@2031:     typedef SubUGraphAdaptorBase Adaptor;
deba@1979:     typedef UGraphAdaptorBase<_UGraph> Parent;
deba@1979:   protected:
deba@1979:     NodeFilterMap* node_filter_map;
deba@1979:     UEdgeFilterMap* uedge_filter_map;
deba@1979:     SubUGraphAdaptorBase() : Parent(), 
deba@1979: 			    node_filter_map(0), uedge_filter_map(0) { }
deba@1979: 
deba@1979:     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
deba@1979:       node_filter_map=&_node_filter_map;
deba@1979:     }
deba@1979:     void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
deba@1979:       uedge_filter_map=&_uedge_filter_map;
deba@1979:     }
deba@1979: 
deba@1979:   public:
deba@1979: 
deba@1979:     typedef typename Parent::Node Node;
deba@1979:     typedef typename Parent::Edge Edge;
deba@1979:     typedef typename Parent::UEdge UEdge;
deba@1979: 
deba@1979:     void first(Node& i) const { 
deba@1979:       Parent::first(i); 
deba@1979:       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void first(Edge& i) const { 
deba@1979:       Parent::first(i); 
deba@1979:       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void first(UEdge& i) const { 
deba@1979:       Parent::first(i); 
deba@1979:       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void firstIn(Edge& i, const Node& n) const { 
deba@1979:       Parent::firstIn(i, n); 
deba@1979:       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void firstOut(Edge& i, const Node& n) const { 
deba@1979:       Parent::firstOut(i, n); 
deba@1979:       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void firstInc(UEdge& i, bool& d, const Node& n) const { 
deba@1979:       Parent::firstInc(i, d, n); 
deba@1979:       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d); 
deba@1979:     }
deba@1979: 
deba@1979:     void next(Node& i) const { 
deba@1979:       Parent::next(i); 
deba@1979:       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
deba@1979:     }
deba@1979:     void next(Edge& i) const { 
deba@1979:       Parent::next(i); 
deba@1979:       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
deba@1979:     }
deba@1979:     void next(UEdge& i) const { 
deba@1979:       Parent::next(i); 
deba@1979:       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
deba@1979:     }
deba@1979:     void nextIn(Edge& i) const { 
deba@1979:       Parent::nextIn(i); 
deba@1979:       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i); 
deba@1979:     }
deba@1979: 
deba@1979:     void nextOut(Edge& i) const { 
deba@1979:       Parent::nextOut(i); 
deba@1979:       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i); 
deba@1979:     }
deba@1979:     void nextInc(UEdge& i, bool& d) const { 
deba@1979:       Parent::nextInc(i, d); 
deba@1979:       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d); 
deba@1979:     }
deba@1979: 
deba@2084:     /// \brief Hide the given node in the graph.
deba@2084:     ///
deba@1979:     /// This function hides \c n in the graph, i.e. the iteration 
deba@1979:     /// jumps over it. This is done by simply setting the value of \c n  
deba@1979:     /// to be false in the corresponding node-map.
deba@1979:     void hide(const Node& n) const { node_filter_map->set(n, false); }
deba@1979: 
deba@2084:     /// \brief Hide the given undirected edge in the graph.
deba@2084:     ///
deba@1979:     /// This function hides \c e in the graph, i.e. the iteration 
deba@1979:     /// jumps over it. This is done by simply setting the value of \c e  
deba@2084:     /// to be false in the corresponding uedge-map.
deba@1979:     void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
deba@1979: 
deba@2084:     /// \brief Unhide the given node in the graph.
deba@2084:     ///
deba@1979:     /// The value of \c n is set to be true in the node-map which stores 
deba@1979:     /// hide information. If \c n was hidden previuosly, then it is shown 
deba@1979:     /// again
deba@1979:      void unHide(const Node& n) const { node_filter_map->set(n, true); }
deba@1979: 
deba@2084:     /// \brief Hide the given undirected edge in the graph.
deba@2084:     ///
deba@2084:     /// The value of \c e is set to be true in the uedge-map which stores 
deba@1979:     /// hide information. If \c e was hidden previuosly, then it is shown 
deba@1979:     /// again
deba@1979:     void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
deba@1979: 
deba@2084:     /// \brief Returns true if \c n is hidden.
deba@2084:     ///
deba@1979:     /// Returns true if \c n is hidden.
deba@1979:     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
deba@1979: 
deba@2084:     /// \brief Returns true if \c e is hidden.
deba@1979:     ///
deba@2084:     /// Returns true if \c e is hidden.
deba@1979:     bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
deba@1979: 
deba@1979:     typedef False NodeNumTag;
deba@1979:     typedef False EdgeNumTag;
deba@1991: 
deba@1991:     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@2386:     Edge findEdge(const Node& u, const Node& v, 
deba@1991: 		  const Edge& prev = INVALID) {
deba@2386:       Edge edge = Parent::findEdge(u, v, prev);
deba@1991:       while (edge != INVALID && !(*uedge_filter_map)[edge]) {
deba@2386:         edge = Parent::findEdge(u, v, edge);
deba@1991:       }
deba@1991:       return edge;
deba@1991:     }
deba@2386:     UEdge findUEdge(const Node& u, const Node& v, 
deba@1991: 		  const UEdge& prev = INVALID) {
deba@2386:       UEdge uedge = Parent::findUEdge(u, v, prev);
deba@1991:       while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
deba@2386:         uedge = Parent::findUEdge(u, v, uedge);
deba@1991:       }
deba@1991:       return uedge;
deba@1991:     }
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class NodeMap 
deba@2031:       : public SubMapExtender<Adaptor, 
deba@2031:                               typename Parent::template NodeMap<_Value> > 
deba@2031:     {
deba@2031:     public:
deba@2031:       typedef Adaptor Graph;
deba@2031:       typedef SubMapExtender<Adaptor, typename Parent::
deba@2031:                              template NodeMap<_Value> > Parent;
deba@2031:     
deba@2386:       NodeMap(const Graph& g) 
deba@2386: 	: Parent(g) {}
deba@2386:       NodeMap(const Graph& g, const _Value& v) 
deba@2386: 	: Parent(g, v) {}
deba@2031:     
deba@2031:       NodeMap& operator=(const NodeMap& cmap) {
deba@2031: 	return operator=<NodeMap>(cmap);
deba@2031:       }
deba@2031:     
deba@2031:       template <typename CMap>
deba@2031:       NodeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class EdgeMap 
deba@2031:       : public SubMapExtender<Adaptor, 
deba@2031:                               typename Parent::template EdgeMap<_Value> > 
deba@2031:     {
deba@2031:     public:
deba@2031:       typedef Adaptor Graph;
deba@2031:       typedef SubMapExtender<Adaptor, typename Parent::
deba@2031:                              template EdgeMap<_Value> > Parent;
deba@2031:     
deba@2386:       EdgeMap(const Graph& g) 
deba@2386: 	: Parent(g) {}
deba@2386:       EdgeMap(const Graph& g, const _Value& v) 
deba@2386: 	: Parent(g, v) {}
deba@2031:     
deba@2031:       EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031: 	return operator=<EdgeMap>(cmap);
deba@2031:       }
deba@2031:     
deba@2031:       template <typename CMap>
deba@2031:       EdgeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class UEdgeMap 
deba@2031:       : public SubMapExtender<Adaptor, 
deba@2031:                               typename Parent::template UEdgeMap<_Value> > 
deba@2031:     {
deba@2031:     public:
deba@2031:       typedef Adaptor Graph;
deba@2031:       typedef SubMapExtender<Adaptor, typename Parent::
deba@2031:                              template UEdgeMap<_Value> > Parent;
deba@2031:     
deba@2386:       UEdgeMap(const Graph& g) 
deba@2386: 	: Parent(g) {}
deba@2386:       UEdgeMap(const Graph& g, const _Value& v) 
deba@2386: 	: Parent(g, v) {}
deba@2031:     
deba@2031:       UEdgeMap& operator=(const UEdgeMap& cmap) {
deba@2031: 	return operator=<UEdgeMap>(cmap);
deba@2031:       }
deba@2031:     
deba@2031:       template <typename CMap>
deba@2031:       UEdgeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@1979:   };
deba@1979: 
deba@1979:   /// \ingroup graph_adaptors
deba@1979:   ///
deba@1979:   /// \brief A graph adaptor for hiding nodes and edges from an undirected 
deba@1979:   /// graph.
deba@1979:   /// 
deba@1979:   /// SubUGraphAdaptor shows the undirected graph with filtered node-set and 
deba@1979:   /// edge-set. If the \c checked parameter is true then it filters the edgeset
deba@1979:   /// to do not get invalid edges without source or target.
deba@1979:   /// 
deba@1979:   /// If the \c checked template parameter is false then we have to note that 
deba@1979:   /// the node-iterator cares only the filter on the node-set, and the 
deba@1979:   /// edge-iterator cares only the filter on the edge-set.
deba@1979:   /// This way the edge-map
deba@1979:   /// should filter all edges which's source or target is filtered by the 
deba@1979:   /// node-filter.
deba@1979:   ///
deba@1979:   template<typename _UGraph, typename NodeFilterMap, 
deba@1979: 	   typename UEdgeFilterMap, bool checked = true>
deba@1979:   class SubUGraphAdaptor : 
deba@1979:     public UGraphAdaptorExtender<
deba@1979:     SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {
deba@1979:   public:
deba@1979:     typedef _UGraph Graph;
deba@1979:     typedef UGraphAdaptorExtender<
deba@1979:       SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;
deba@1979:   protected:
deba@1979:     SubUGraphAdaptor() { }
deba@1979:   public:
deba@1979:     SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map, 
deba@1979: 		    UEdgeFilterMap& _uedge_filter_map) { 
deba@1979:       setGraph(_graph);
deba@1979:       setNodeFilterMap(_node_filter_map);
deba@1979:       setUEdgeFilterMap(_uedge_filter_map);
deba@1979:     }
deba@1979:   };
deba@1979: 
deba@1980:   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1980:   SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
deba@1980:   subUGraphAdaptor(const UGraph& graph, 
deba@1980:                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1980:     return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
deba@1980:       (graph, nfm, efm);
deba@1980:   }
deba@1980: 
deba@1980:   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1980:   SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
deba@1980:   subUGraphAdaptor(const UGraph& graph, 
deba@1980:                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1980:     return SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
deba@1980:       (graph, nfm, efm);
deba@1980:   }
deba@1980: 
deba@1980:   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1980:   SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
deba@1980:   subUGraphAdaptor(const UGraph& graph, 
deba@1980:                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1980:     return SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
deba@1980:       (graph, nfm, efm);
deba@1980:   }
deba@1980: 
deba@1980:   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1980:   SubUGraphAdaptor<const UGraph, const NodeFilterMap, const EdgeFilterMap>
deba@1980:   subUGraphAdaptor(const UGraph& graph, 
deba@1980:                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1980:     return SubUGraphAdaptor<const UGraph, const NodeFilterMap, 
deba@1980:       const EdgeFilterMap>(graph, nfm, efm);
deba@1980:   }
deba@1980: 
deba@1979:   /// \ingroup graph_adaptors
deba@1979:   ///
deba@1980:   /// \brief An adaptor for hiding nodes from an undirected graph.
deba@1979:   ///
deba@2422:   /// An adaptor for hiding nodes from an undirected graph.  This
deba@2422:   /// adaptor specializes SubUGraphAdaptor in the way that only the
deba@2422:   /// node-set can be filtered. In usual case the checked parameter is
deba@2422:   /// true, we get the induced subgraph. But if the checked parameter
deba@2422:   /// is false then we can filter only isolated nodes.
deba@1979:   template<typename _UGraph, typename NodeFilterMap, bool checked = true>
deba@1979:   class NodeSubUGraphAdaptor : 
deba@1979:     public SubUGraphAdaptor<_UGraph, NodeFilterMap, 
deba@1979:                             ConstMap<typename _UGraph::UEdge, bool>, checked> {
deba@1979:   public:
deba@1979:     typedef SubUGraphAdaptor<_UGraph, NodeFilterMap, 
deba@1979:                              ConstMap<typename _UGraph::UEdge, bool> > Parent;
deba@1979:     typedef _UGraph Graph;
deba@1979:   protected:
deba@1985:     ConstMap<typename _UGraph::UEdge, bool> const_true_map;
deba@1991: 
deba@1991:     NodeSubUGraphAdaptor() : const_true_map(true) {
deba@1991:       Parent::setUEdgeFilterMap(const_true_map);
deba@1991:     }
deba@1991: 
deba@1979:   public:
deba@1979:     NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : 
deba@1979:       Parent(), const_true_map(true) { 
deba@1979:       Parent::setGraph(_graph);
deba@1979:       Parent::setNodeFilterMap(_node_filter_map);
deba@1979:       Parent::setUEdgeFilterMap(const_true_map);
deba@1979:     }
deba@1979:   };
deba@1979: 
deba@1979:   template<typename UGraph, typename NodeFilterMap>
deba@1979:   NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
deba@1979:   nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
deba@1979:     return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
deba@1979:   }
deba@1979: 
deba@1979:   template<typename UGraph, typename NodeFilterMap>
deba@1979:   NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
deba@1979:   nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
deba@1979:     return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
deba@1979:   }
deba@1979: 
deba@2042:   /// \ingroup graph_adaptors
deba@2042:   ///
deba@1979:   /// \brief An adaptor for hiding undirected edges from an undirected graph.
deba@1979:   ///
deba@1979:   /// \warning Graph adaptors are in even more experimental state
deba@1979:   /// than the other parts of the lib. Use them at you own risk.
deba@1979:   ///
deba@1979:   /// An adaptor for hiding undirected edges from an undirected graph.
deba@1979:   /// This adaptor specializes SubUGraphAdaptor in the way that
deba@1979:   /// only the edge-set 
deba@1979:   /// can be filtered.
deba@1979:   template<typename _UGraph, typename UEdgeFilterMap>
deba@1979:   class EdgeSubUGraphAdaptor : 
deba@1979:     public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>, 
deba@1979:                             UEdgeFilterMap, false> {
deba@1979:   public:
deba@1979:     typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>, 
deba@1979:                              UEdgeFilterMap, false> Parent;
deba@1979:     typedef _UGraph Graph;
deba@1979:   protected:
deba@1979:     ConstMap<typename Graph::Node, bool> const_true_map;
deba@1991: 
deba@1991:     EdgeSubUGraphAdaptor() : const_true_map(true) {
deba@1991:       Parent::setNodeFilterMap(const_true_map);
deba@1991:     }
deba@1991: 
deba@1979:   public:
deba@2031: 
deba@1979:     EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) : 
deba@1979:       Parent(), const_true_map(true) { 
deba@1979:       Parent::setGraph(_graph);
deba@1979:       Parent::setNodeFilterMap(const_true_map);
deba@1979:       Parent::setUEdgeFilterMap(_uedge_filter_map);
deba@1979:     }
deba@2031: 
deba@1979:   };
deba@1979: 
deba@1979:   template<typename UGraph, typename EdgeFilterMap>
deba@1979:   EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
deba@1979:   edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
deba@1979:     return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
deba@1979:   }
deba@1979: 
deba@1979:   template<typename UGraph, typename EdgeFilterMap>
deba@1979:   EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
deba@1979:   edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
deba@1979:     return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
deba@1979:   }
deba@1979: 
deba@2087:   /// \brief Base of direct undirected graph adaptor
deba@2087:   ///
deba@2087:   /// Base class of the direct undirected graph adaptor. All public member
deba@2087:   /// of this class can be used with the DirUGraphAdaptor too.
deba@2087:   /// \sa DirUGraphAdaptor
deba@1979:   template <typename _UGraph, typename _DirectionMap>
deba@1980:   class DirUGraphAdaptorBase {
deba@1979:   public:
deba@1979:     
deba@1979:     typedef _UGraph Graph;
deba@1979:     typedef _DirectionMap DirectionMap;
deba@1979: 
deba@1979:     typedef typename _UGraph::Node Node;
deba@1979:     typedef typename _UGraph::UEdge Edge;
deba@1979:    
deba@2087:     /// \brief Reverse edge
deba@2087:     /// 
deba@2087:     /// It reverse the given edge. It simply negate the direction in the map.
deba@1991:     void reverseEdge(const Edge& edge) {
deba@1991:       direction->set(edge, !(*direction)[edge]);
deba@1991:     }
deba@1991: 
deba@1979:     void first(Node& i) const { graph->first(i); }
deba@1979:     void first(Edge& i) const { graph->first(i); }
deba@1979:     void firstIn(Edge& i, const Node& n) const {
deba@1979:       bool d;
deba@1979:       graph->firstInc(i, d, n);
deba@1979:       while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
deba@1979:     }
deba@1979:     void firstOut(Edge& i, const Node& n ) const { 
deba@1979:       bool d;
deba@1979:       graph->firstInc(i, d, n);
deba@1979:       while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
deba@1979:     }
deba@1979: 
deba@1979:     void next(Node& i) const { graph->next(i); }
deba@1979:     void next(Edge& i) const { graph->next(i); }
deba@1979:     void nextIn(Edge& i) const {
deba@1979:       bool d = !(*direction)[i];
deba@1979:       graph->nextInc(i, d);
deba@1979:       while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
deba@1979:     }
deba@1979:     void nextOut(Edge& i) const {
deba@1979:       bool d = (*direction)[i];
deba@1979:       graph->nextInc(i, d);
deba@1979:       while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
deba@1979:     }
deba@1979: 
deba@1979:     Node source(const Edge& e) const { 
deba@1979:       return (*direction)[e] ? graph->source(e) : graph->target(e); 
deba@1979:     }
deba@1979:     Node target(const Edge& e) const { 
deba@1979:       return (*direction)[e] ? graph->target(e) : graph->source(e); 
deba@1979:     }
deba@1979: 
deba@1979:     typedef NodeNumTagIndicator<Graph> NodeNumTag;
deba@1979:     int nodeNum() const { return graph->nodeNum(); }
deba@1979:     
deba@1979:     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
deba@1979:     int edgeNum() const { return graph->uEdgeNum(); }
deba@1979: 
deba@1979:     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@2386:     Edge findEdge(const Node& u, const Node& v, 
deba@1979: 		  const Edge& prev = INVALID) {
deba@1979:       Edge edge = prev;
deba@1979:       bool d = edge == INVALID ? true : (*direction)[edge];
deba@1979:       if (d) {
deba@2386:         edge = graph->findUEdge(u, v, edge);
deba@1979:         while (edge != INVALID && !(*direction)[edge]) {
deba@2386:           graph->findUEdge(u, v, edge);
deba@1979:         }
deba@1979:         if (edge != INVALID) return edge;
deba@1979:       }
deba@2386:       graph->findUEdge(v, u, edge);
deba@1979:       while (edge != INVALID && (*direction)[edge]) {
deba@2386:         graph->findUEdge(u, v, edge);
deba@1979:       }
deba@1979:       return edge;
deba@1979:     }
deba@1979:   
deba@1979:     Node addNode() const { 
deba@1979:       return Node(graph->addNode()); 
deba@1979:     }
deba@1979: 
deba@2386:     Edge addEdge(const Node& u, const Node& v) const {
deba@2386:       Edge edge = graph->addEdge(u, v);
deba@2386:       direction->set(edge, graph->source(edge) == u);
deba@1979:       return edge; 
deba@1979:     }
deba@1979: 
deba@1979:     void erase(const Node& i) const { graph->erase(i); }
deba@1979:     void erase(const Edge& i) const { graph->erase(i); }
deba@1979:   
deba@1979:     void clear() const { graph->clear(); }
deba@1979:     
deba@1979:     int id(const Node& v) const { return graph->id(v); }
deba@1979:     int id(const Edge& e) const { return graph->id(e); }
deba@1979: 
deba@1991:     int maxNodeId() const {
deba@1991:       return graph->maxNodeId();
deba@1979:     }
deba@1979: 
deba@1991:     int maxEdgeId() const {
deba@1991:       return graph->maxEdgeId();
deba@1991:     }
deba@1991: 
deba@1991:     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@1991: 
deba@2381:     NodeNotifier& notifier(Node) const {
deba@2381:       return graph->notifier(Node());
deba@1991:     } 
deba@1991: 
deba@1991:     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
deba@1991: 
deba@2381:     EdgeNotifier& notifier(Edge) const {
deba@2381:       return graph->notifier(Edge());
deba@1991:     } 
deba@1991: 
deba@1979:     template <typename _Value>
deba@1979:     class NodeMap : public _UGraph::template NodeMap<_Value> {
deba@1979:     public:
deba@2031: 
deba@1979:       typedef typename _UGraph::template NodeMap<_Value> Parent;
deba@2031: 
deba@1980:       explicit NodeMap(const DirUGraphAdaptorBase& ga) 
deba@2031: 	: Parent(*ga.graph) {}
deba@2031: 
deba@1980:       NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
deba@2031: 	: Parent(*ga.graph, value) {}
deba@2031: 
deba@2031:       NodeMap& operator=(const NodeMap& cmap) {
deba@2031:         return operator=<NodeMap>(cmap);
deba@2031:       }
deba@2031: 
deba@2031:       template <typename CMap>
deba@2031:       NodeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031:         return *this;
deba@2031:       }
deba@2031: 
deba@1979:     };
deba@1979: 
deba@1979:     template <typename _Value>
deba@1979:     class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
deba@1979:     public:
deba@2031: 
deba@1980:       typedef typename _UGraph::template UEdgeMap<_Value> Parent;
deba@2031: 
deba@1980:       explicit EdgeMap(const DirUGraphAdaptorBase& ga) 
deba@1979: 	: Parent(*ga.graph) { }
deba@2031: 
deba@1980:       EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
deba@1979: 	: Parent(*ga.graph, value) { }
deba@2031: 
deba@2031:       EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031:         return operator=<EdgeMap>(cmap);
deba@2031:       }
deba@2031: 
deba@2031:       template <typename CMap>
deba@2031:       EdgeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031:         return *this;
deba@2031:       }
deba@1979:     };
deba@1979: 
deba@1979:     
deba@1979: 
deba@1979:   protected:
deba@1979:     Graph* graph;
deba@1979:     DirectionMap* direction;
deba@1979: 
deba@1979:     void setDirectionMap(DirectionMap& _direction) {
deba@1979:       direction = &_direction;
deba@1979:     }
deba@1979: 
deba@1979:     void setGraph(Graph& _graph) {
deba@1979:       graph = &_graph;
deba@1979:     }
deba@1979: 
deba@1979:   };
deba@1979: 
deba@1979: 
deba@1980:   /// \ingroup graph_adaptors
deba@1991:   ///
deba@1991:   /// \brief A directed graph is made from an undirected graph by an adaptor
deba@1980:   ///
deba@2087:   /// This adaptor gives a direction for each uedge in the undirected
deba@2087:   /// graph. The direction of the edges stored in the
deba@2087:   /// DirectionMap. This map is a bool map on the undirected edges. If
deba@2087:   /// the uedge is mapped to true then the direction of the directed
deba@2087:   /// edge will be the same as the default direction of the uedge. The
deba@2087:   /// edges can be easily reverted by the \ref
deba@2087:   /// DirUGraphAdaptorBase::reverseEdge "reverseEdge()" member in the
deba@2087:   /// adaptor.
deba@2087:   ///
deba@2087:   /// It can be used to solve orientation problems on directed graphs.
deba@2087:   /// By example how can we orient an undirected graph to get the minimum
deba@2087:   /// number of strongly connected components. If we orient the edges with
deba@2087:   /// the dfs algorithm out from the source then we will get such an 
deba@2087:   /// orientation. 
deba@2087:   ///
deba@2087:   /// We use the \ref DfsVisitor "visitor" interface of the 
deba@2087:   /// \ref DfsVisit "dfs" algorithm:
deba@2087:   ///\code
deba@2087:   /// template <typename DirMap>
deba@2087:   /// class OrientVisitor : public DfsVisitor<UGraph> {
deba@2087:   /// public:
deba@2087:   ///
deba@2087:   ///   OrientVisitor(const UGraph& ugraph, DirMap& dirMap)
deba@2087:   ///     : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}
deba@2087:   ///
deba@2087:   ///   void discover(const Edge& edge) {
deba@2087:   ///     _processed.set(edge, true);
deba@2087:   ///     _dirMap.set(edge, _ugraph.direction(edge));
deba@2087:   ///   }
deba@2087:   ///
deba@2087:   ///   void examine(const Edge& edge) {
deba@2087:   ///     if (_processed[edge]) return;
deba@2087:   ///     _processed.set(edge, true);
deba@2087:   ///     _dirMap.set(edge, _ugraph.direction(edge));
deba@2087:   ///   }  
deba@2087:   /// 
deba@2087:   /// private:
deba@2087:   ///   const UGraph& _ugraph;  
deba@2087:   ///   DirMap& _dirMap;
deba@2087:   ///   UGraph::UEdgeMap<bool> _processed;
deba@2087:   /// };
deba@2087:   ///\endcode
deba@2087:   ///
deba@2087:   /// And now we can use the orientation:
deba@2087:   ///\code
deba@2087:   /// UGraph::UEdgeMap<bool> dmap(ugraph);
deba@2087:   ///
deba@2087:   /// typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
deba@2087:   /// Visitor visitor(ugraph, dmap);
deba@2087:   ///
deba@2087:   /// DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
deba@2087:   ///
deba@2087:   /// dfs.run();
deba@2087:   ///
deba@2087:   /// typedef DirUGraphAdaptor<UGraph> DGraph;
deba@2087:   /// DGraph dgraph(ugraph, dmap);
deba@2087:   ///
deba@2087:   /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) == 
deba@2087:   ///              countBiEdgeConnectedComponents(ugraph), "Wrong Orientation");
deba@2087:   ///\endcode
deba@2087:   ///
deba@2087:   /// The number of the bi-connected components is a lower bound for
deba@2087:   /// the number of the strongly connected components in the directed
deba@2087:   /// graph because if we contract the bi-connected components to
deba@2087:   /// nodes we will get a tree therefore we cannot orient edges in
deba@2087:   /// both direction between bi-connected components. In the other way
deba@2087:   /// the algorithm will orient one component to be strongly
deba@2087:   /// connected. The two relations proof that the assertion will
deba@2087:   /// be always true and the found solution is optimal.
deba@2087:   ///
deba@2087:   /// \sa DirUGraphAdaptorBase
deba@2087:   /// \sa dirUGraphAdaptor
deba@1980:   template<typename _Graph, 
deba@1980:            typename DirectionMap = typename _Graph::template UEdgeMap<bool> > 
deba@1980:   class DirUGraphAdaptor : 
deba@1979:     public GraphAdaptorExtender<
deba@1980:     DirUGraphAdaptorBase<_Graph, DirectionMap> > {
deba@1979:   public:
deba@1979:     typedef _Graph Graph;
deba@1979:     typedef GraphAdaptorExtender<
deba@1980:       DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
deba@1979:   protected:
deba@1980:     DirUGraphAdaptor() { }
deba@1979:   public:
deba@2087:     
deba@2087:     /// \brief Constructor of the adaptor
deba@2087:     ///
deba@2087:     /// Constructor of the adaptor
deba@1980:     DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) { 
deba@1979:       setGraph(_graph);
deba@1979:       setDirectionMap(_direction_map);
deba@1979:     }
deba@1979:   };
deba@1979: 
deba@2087:   /// \brief Just gives back a DirUGraphAdaptor
deba@2087:   ///
deba@2087:   /// Just gives back a DirUGraphAdaptor
deba@1979:   template<typename UGraph, typename DirectionMap>
deba@1980:   DirUGraphAdaptor<const UGraph, DirectionMap>
deba@1980:   dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
deba@1980:     return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
deba@1979:   }
deba@1979: 
deba@1979:   template<typename UGraph, typename DirectionMap>
deba@1980:   DirUGraphAdaptor<const UGraph, const DirectionMap>
deba@1980:   dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
deba@1980:     return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
deba@1979:   }
deba@1979: 
deba@1979: }
deba@1979: 
deba@1979: #endif