lemon/ugraph_adaptor.h
author deba
Fri, 12 May 2006 09:56:14 +0000
changeset 2079 7fe378247fea
parent 2042 bdc953f2a449
child 2084 59769591eb60
permissions -rw-r--r--
Remade SplitGraphAdaptor
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_UGRAPH_ADAPTOR_H
    20 #define LEMON_UGRAPH_ADAPTOR_H
    21 
    22 ///\ingroup graph_adaptors
    23 ///\file
    24 ///\brief Several graph adaptors.
    25 ///
    26 ///This file contains several useful ugraph adaptor functions.
    27 ///
    28 ///\author Balazs Dezso
    29 
    30 #include <lemon/bits/invalid.h>
    31 #include <lemon/maps.h>
    32 
    33 #include <lemon/bits/graph_adaptor_extender.h>
    34 
    35 #include <lemon/bits/traits.h>
    36 
    37 #include <iostream>
    38 
    39 namespace lemon {
    40 
    41   /// \ingroup graph_adaptors
    42   ///
    43   /// \brief Base type for the Graph Adaptors
    44   ///
    45   /// This is the base type for most of LEMON graph adaptors. 
    46   /// This class implements a trivial graph adaptor i.e. it only wraps the 
    47   /// functions and types of the graph. The purpose of this class is to 
    48   /// make easier implementing graph adaptors. E.g. if an adaptor is 
    49   /// considered which differs from the wrapped graph only in some of its 
    50   /// functions or types, then it can be derived from GraphAdaptor, and only 
    51   /// the differences should be implemented.
    52   ///
    53   /// \author Balazs Dezso 
    54   template<typename _UGraph>
    55   class UGraphAdaptorBase {
    56   public:
    57     typedef _UGraph Graph;
    58     typedef Graph ParentGraph;
    59 
    60   protected:
    61     Graph* graph;
    62 
    63     UGraphAdaptorBase() : graph(0) {}
    64 
    65     void setGraph(Graph& _graph) { graph=&_graph; }
    66 
    67   public:
    68     UGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
    69  
    70     typedef typename Graph::Node Node;
    71     typedef typename Graph::Edge Edge;
    72     typedef typename Graph::UEdge UEdge;
    73    
    74     void first(Node& i) const { graph->first(i); }
    75     void first(Edge& i) const { graph->first(i); }
    76     void first(UEdge& i) const { graph->first(i); }
    77     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
    78     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
    79     void firstInc(UEdge &i, bool &d, const Node &n) const {
    80       graph->firstInc(i, d, n);
    81     }
    82 
    83     void next(Node& i) const { graph->next(i); }
    84     void next(Edge& i) const { graph->next(i); }
    85     void next(UEdge& i) const { graph->next(i); }
    86     void nextIn(Edge& i) const { graph->nextIn(i); }
    87     void nextOut(Edge& i) const { graph->nextOut(i); }
    88     void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
    89 
    90     Node source(const UEdge& e) const { return graph->source(e); }
    91     Node target(const UEdge& e) const { return graph->target(e); }
    92 
    93     Node source(const Edge& e) const { return graph->source(e); }
    94     Node target(const Edge& e) const { return graph->target(e); }
    95 
    96     typedef NodeNumTagIndicator<Graph> NodeNumTag;
    97     int nodeNum() const { return graph->nodeNum(); }
    98     
    99     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
   100     int edgeNum() const { return graph->edgeNum(); }
   101     int uEdgeNum() const { return graph->uEdgeNum(); }
   102 
   103     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   104     Edge findEdge(const Node& source, const Node& target, 
   105 		  const Edge& prev = INVALID) {
   106       return graph->findEdge(source, target, prev);
   107     }
   108     UEdge findUEdge(const Node& source, const Node& target, 
   109                     const UEdge& prev = INVALID) {
   110       return graph->findUEdge(source, target, prev);
   111     }
   112   
   113     Node addNode() const { return graph->addNode(); }
   114     UEdge addEdge(const Node& source, const Node& target) const { 
   115       return graph->addEdge(source, target); 
   116     }
   117 
   118     void erase(const Node& i) const { graph->erase(i); }
   119     void erase(const UEdge& i) const { graph->erase(i); }
   120   
   121     void clear() const { graph->clear(); }
   122     
   123     bool direction(const Edge& e) const { return graph->direction(e); }
   124     Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
   125 
   126     int id(const Node& v) const { return graph->id(v); }
   127     int id(const Edge& e) const { return graph->id(e); }
   128     int id(const UEdge& e) const { return graph->id(e); }
   129 
   130     Node fromNodeId(int id) const {
   131       return graph->fromNodeId(id);
   132     }
   133 
   134     Edge fromEdgeId(int id) const {
   135       return graph->fromEdgeId(id);
   136     }
   137 
   138     UEdge fromUEdgeId(int id) const {
   139       return graph->fromUEdgeId(id);
   140     }
   141 
   142     int maxNodeId() const {
   143       return graph->maxNodeId();
   144     }
   145 
   146     int maxEdgeId() const {
   147       return graph->maxEdgeId();
   148     }
   149 
   150     int maxUEdgeId() const {
   151       return graph->maxEdgeId();
   152     }
   153 
   154     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
   155 
   156     NodeNotifier& getNotifier(Node) const {
   157       return graph->getNotifier(Node());
   158     } 
   159 
   160     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
   161 
   162     EdgeNotifier& getNotifier(Edge) const {
   163       return graph->getNotifier(Edge());
   164     } 
   165 
   166     typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
   167 
   168     UEdgeNotifier& getNotifier(UEdge) const {
   169       return graph->getNotifier(UEdge());
   170     } 
   171 
   172     template <typename _Value>
   173     class NodeMap : public Graph::template NodeMap<_Value> {
   174     public:
   175       typedef typename Graph::template NodeMap<_Value> Parent;
   176       explicit NodeMap(const UGraphAdaptorBase<Graph>& ga) 
   177 	: Parent(*ga.graph) {}
   178       NodeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
   179 	: Parent(*ga.graph, value) {}
   180 
   181       NodeMap& operator=(const NodeMap& cmap) {
   182 	return operator=<NodeMap>(cmap);
   183       }
   184 
   185       template <typename CMap>
   186       NodeMap& operator=(const CMap& cmap) {
   187         Parent::operator=(cmap);
   188         return *this;
   189       }
   190 
   191     };
   192 
   193     template <typename _Value>
   194     class EdgeMap : public Graph::template EdgeMap<_Value> {
   195     public:
   196       typedef typename Graph::template EdgeMap<_Value> Parent;
   197       explicit EdgeMap(const UGraphAdaptorBase<Graph>& ga) 
   198 	: Parent(*ga.graph) {}
   199       EdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
   200 	: Parent(*ga.graph, value) {}
   201 
   202       EdgeMap& operator=(const EdgeMap& cmap) {
   203 	return operator=<EdgeMap>(cmap);
   204       }
   205 
   206       template <typename CMap>
   207       EdgeMap& operator=(const CMap& cmap) {
   208         Parent::operator=(cmap);
   209 	return *this;
   210       }
   211     };
   212 
   213     template <typename _Value>
   214     class UEdgeMap : public Graph::template UEdgeMap<_Value> {
   215     public:
   216       typedef typename Graph::template UEdgeMap<_Value> Parent;
   217       explicit UEdgeMap(const UGraphAdaptorBase<Graph>& ga) 
   218 	: Parent(*ga.graph) {}
   219       UEdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
   220 	: Parent(*ga.graph, value) {}
   221 
   222       UEdgeMap& operator=(const UEdgeMap& cmap) {
   223 	return operator=<UEdgeMap>(cmap);
   224       }
   225 
   226       template <typename CMap>
   227       UEdgeMap& operator=(const CMap& cmap) {
   228         Parent::operator=(cmap);
   229         return *this;
   230       }
   231     };
   232 
   233   };
   234 
   235   /// \ingroup graph_adaptors
   236   template <typename _UGraph>
   237   class UGraphAdaptor 
   238     : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > { 
   239   public:
   240     typedef _UGraph Graph;
   241     typedef UGraphAdaptorExtender<UGraphAdaptorBase<_UGraph> > Parent;
   242   protected:
   243     UGraphAdaptor() : Parent() {}
   244 
   245   public:
   246     explicit UGraphAdaptor(Graph& _graph) { setGraph(_graph); }
   247   };
   248 
   249   template <typename _UGraph, typename NodeFilterMap, 
   250 	    typename UEdgeFilterMap, bool checked = true>
   251   class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> {
   252   public:
   253     typedef _UGraph Graph;
   254     typedef SubUGraphAdaptorBase Adaptor;
   255     typedef UGraphAdaptorBase<_UGraph> Parent;
   256   protected:
   257 
   258     NodeFilterMap* node_filter_map;
   259     UEdgeFilterMap* uedge_filter_map;
   260 
   261     SubUGraphAdaptorBase() 
   262       : Parent(), node_filter_map(0), uedge_filter_map(0) { }
   263 
   264     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
   265       node_filter_map=&_node_filter_map;
   266     }
   267     void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
   268       uedge_filter_map=&_uedge_filter_map;
   269     }
   270 
   271   public:
   272 
   273     typedef typename Parent::Node Node;
   274     typedef typename Parent::Edge Edge;
   275     typedef typename Parent::UEdge UEdge;
   276 
   277     void first(Node& i) const { 
   278       Parent::first(i); 
   279       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
   280     }
   281 
   282     void first(Edge& i) const { 
   283       Parent::first(i); 
   284       while (i!=INVALID && (!(*uedge_filter_map)[i] 
   285 	     || !(*node_filter_map)[Parent::source(i)]
   286 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
   287     }
   288 
   289     void first(UEdge& i) const { 
   290       Parent::first(i); 
   291       while (i!=INVALID && (!(*uedge_filter_map)[i] 
   292 	     || !(*node_filter_map)[Parent::source(i)]
   293 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
   294     }
   295 
   296     void firstIn(Edge& i, const Node& n) const { 
   297       Parent::firstIn(i, n); 
   298       while (i!=INVALID && (!(*uedge_filter_map)[i] 
   299 	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
   300     }
   301 
   302     void firstOut(Edge& i, const Node& n) const { 
   303       Parent::firstOut(i, n); 
   304       while (i!=INVALID && (!(*uedge_filter_map)[i] 
   305 	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
   306     }
   307 
   308     void firstInc(UEdge& i, bool& d, const Node& n) const { 
   309       Parent::firstInc(i, d, n); 
   310       while (i!=INVALID && (!(*uedge_filter_map)[i] 
   311             || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d); 
   312     }
   313 
   314     void next(Node& i) const { 
   315       Parent::next(i); 
   316       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
   317     }
   318 
   319     void next(Edge& i) const { 
   320       Parent::next(i); 
   321       while (i!=INVALID && (!(*uedge_filter_map)[i] 
   322 	     || !(*node_filter_map)[Parent::source(i)]
   323 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
   324     }
   325 
   326     void next(UEdge& i) const { 
   327       Parent::next(i); 
   328       while (i!=INVALID && (!(*uedge_filter_map)[i] 
   329 	     || !(*node_filter_map)[Parent::source(i)]
   330 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
   331     }
   332 
   333     void nextIn(Edge& i) const { 
   334       Parent::nextIn(i); 
   335       while (i!=INVALID && (!(*uedge_filter_map)[i] 
   336 	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
   337     }
   338 
   339     void nextOut(Edge& i) const { 
   340       Parent::nextOut(i); 
   341       while (i!=INVALID && (!(*uedge_filter_map)[i] 
   342 	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
   343     }
   344 
   345     void nextInc(UEdge& i, bool& d) const { 
   346       Parent::nextInc(i, d); 
   347       while (i!=INVALID && (!(*uedge_filter_map)[i] 
   348             || !(*node_filter_map)[Parent::source(i)])) Parent::nextInc(i, d); 
   349     }
   350 
   351     ///\e
   352 
   353     /// This function hides \c n in the graph, i.e. the iteration 
   354     /// jumps over it. This is done by simply setting the value of \c n  
   355     /// to be false in the corresponding node-map.
   356     void hide(const Node& n) const { node_filter_map->set(n, false); }
   357 
   358     ///\e
   359 
   360     /// This function hides \c e in the graph, i.e. the iteration 
   361     /// jumps over it. This is done by simply setting the value of \c e  
   362     /// to be false in the corresponding edge-map.
   363     void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
   364 
   365     ///\e
   366 
   367     /// The value of \c n is set to be true in the node-map which stores 
   368     /// hide information. If \c n was hidden previuosly, then it is shown 
   369     /// again
   370      void unHide(const Node& n) const { node_filter_map->set(n, true); }
   371 
   372     ///\e
   373 
   374     /// The value of \c e is set to be true in the edge-map which stores 
   375     /// hide information. If \c e was hidden previuosly, then it is shown 
   376     /// again
   377     void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
   378 
   379     /// Returns true if \c n is hidden.
   380     
   381     ///\e
   382     ///
   383     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
   384 
   385     /// Returns true if \c n is hidden.
   386     
   387     ///\e
   388     ///
   389     bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
   390 
   391     typedef False NodeNumTag;
   392     typedef False EdgeNumTag;
   393 
   394     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   395     Edge findEdge(const Node& source, const Node& target, 
   396 		  const Edge& prev = INVALID) {
   397       if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
   398         return INVALID;
   399       }
   400       Edge edge = Parent::findEdge(source, target, prev);
   401       while (edge != INVALID && !(*uedge_filter_map)[edge]) {
   402         edge = Parent::findEdge(source, target, edge);
   403       }
   404       return edge;
   405     }
   406     UEdge findUEdge(const Node& source, const Node& target, 
   407 		  const UEdge& prev = INVALID) {
   408       if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
   409         return INVALID;
   410       }
   411       UEdge uedge = Parent::findUEdge(source, target, prev);
   412       while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
   413         uedge = Parent::findUEdge(source, target, uedge);
   414       }
   415       return uedge;
   416     }
   417 
   418     template <typename _Value>
   419     class NodeMap 
   420       : public SubMapExtender<Adaptor, 
   421                               typename Parent::template NodeMap<_Value> > 
   422     {
   423     public:
   424       typedef Adaptor Graph;
   425       typedef SubMapExtender<Adaptor, typename Parent::
   426                              template NodeMap<_Value> > Parent;
   427     
   428       NodeMap(const Graph& graph) 
   429 	: Parent(graph) {}
   430       NodeMap(const Graph& graph, const _Value& value) 
   431 	: Parent(graph, value) {}
   432     
   433       NodeMap& operator=(const NodeMap& cmap) {
   434 	return operator=<NodeMap>(cmap);
   435       }
   436     
   437       template <typename CMap>
   438       NodeMap& operator=(const CMap& cmap) {
   439         Parent::operator=(cmap);
   440 	return *this;
   441       }
   442     };
   443 
   444     template <typename _Value>
   445     class EdgeMap 
   446       : public SubMapExtender<Adaptor, 
   447                               typename Parent::template EdgeMap<_Value> > 
   448     {
   449     public:
   450       typedef Adaptor Graph;
   451       typedef SubMapExtender<Adaptor, typename Parent::
   452                              template EdgeMap<_Value> > Parent;
   453     
   454       EdgeMap(const Graph& graph) 
   455 	: Parent(graph) {}
   456       EdgeMap(const Graph& graph, const _Value& value) 
   457 	: Parent(graph, value) {}
   458     
   459       EdgeMap& operator=(const EdgeMap& cmap) {
   460 	return operator=<EdgeMap>(cmap);
   461       }
   462     
   463       template <typename CMap>
   464       EdgeMap& operator=(const CMap& cmap) {
   465         Parent::operator=(cmap);
   466 	return *this;
   467       }
   468     };
   469 
   470     template <typename _Value>
   471     class UEdgeMap 
   472       : public SubMapExtender<Adaptor, 
   473                               typename Parent::template UEdgeMap<_Value> > 
   474     {
   475     public:
   476       typedef Adaptor Graph;
   477       typedef SubMapExtender<Adaptor, typename Parent::
   478                              template UEdgeMap<_Value> > Parent;
   479     
   480       UEdgeMap(const Graph& graph) 
   481 	: Parent(graph) {}
   482       UEdgeMap(const Graph& graph, const _Value& value) 
   483 	: Parent(graph, value) {}
   484     
   485       UEdgeMap& operator=(const UEdgeMap& cmap) {
   486 	return operator=<UEdgeMap>(cmap);
   487       }
   488     
   489       template <typename CMap>
   490       UEdgeMap& operator=(const CMap& cmap) {
   491         Parent::operator=(cmap);
   492 	return *this;
   493       }
   494     };
   495 
   496   };
   497 
   498   template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
   499   class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false> 
   500     : public UGraphAdaptorBase<_UGraph> {
   501   public:
   502     typedef _UGraph Graph;
   503     typedef SubUGraphAdaptorBase Adaptor;
   504     typedef UGraphAdaptorBase<_UGraph> Parent;
   505   protected:
   506     NodeFilterMap* node_filter_map;
   507     UEdgeFilterMap* uedge_filter_map;
   508     SubUGraphAdaptorBase() : Parent(), 
   509 			    node_filter_map(0), uedge_filter_map(0) { }
   510 
   511     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
   512       node_filter_map=&_node_filter_map;
   513     }
   514     void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
   515       uedge_filter_map=&_uedge_filter_map;
   516     }
   517 
   518   public:
   519 
   520     typedef typename Parent::Node Node;
   521     typedef typename Parent::Edge Edge;
   522     typedef typename Parent::UEdge UEdge;
   523 
   524     void first(Node& i) const { 
   525       Parent::first(i); 
   526       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
   527     }
   528 
   529     void first(Edge& i) const { 
   530       Parent::first(i); 
   531       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
   532     }
   533 
   534     void first(UEdge& i) const { 
   535       Parent::first(i); 
   536       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
   537     }
   538 
   539     void firstIn(Edge& i, const Node& n) const { 
   540       Parent::firstIn(i, n); 
   541       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i); 
   542     }
   543 
   544     void firstOut(Edge& i, const Node& n) const { 
   545       Parent::firstOut(i, n); 
   546       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i); 
   547     }
   548 
   549     void firstInc(UEdge& i, bool& d, const Node& n) const { 
   550       Parent::firstInc(i, d, n); 
   551       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d); 
   552     }
   553 
   554     void next(Node& i) const { 
   555       Parent::next(i); 
   556       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
   557     }
   558     void next(Edge& i) const { 
   559       Parent::next(i); 
   560       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
   561     }
   562     void next(UEdge& i) const { 
   563       Parent::next(i); 
   564       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
   565     }
   566     void nextIn(Edge& i) const { 
   567       Parent::nextIn(i); 
   568       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i); 
   569     }
   570 
   571     void nextOut(Edge& i) const { 
   572       Parent::nextOut(i); 
   573       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i); 
   574     }
   575     void nextInc(UEdge& i, bool& d) const { 
   576       Parent::nextInc(i, d); 
   577       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d); 
   578     }
   579 
   580     ///\e
   581 
   582     /// This function hides \c n in the graph, i.e. the iteration 
   583     /// jumps over it. This is done by simply setting the value of \c n  
   584     /// to be false in the corresponding node-map.
   585     void hide(const Node& n) const { node_filter_map->set(n, false); }
   586 
   587     ///\e
   588 
   589     /// This function hides \c e in the graph, i.e. the iteration 
   590     /// jumps over it. This is done by simply setting the value of \c e  
   591     /// to be false in the corresponding edge-map.
   592     void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
   593 
   594     ///\e
   595 
   596     /// The value of \c n is set to be true in the node-map which stores 
   597     /// hide information. If \c n was hidden previuosly, then it is shown 
   598     /// again
   599      void unHide(const Node& n) const { node_filter_map->set(n, true); }
   600 
   601     ///\e
   602 
   603     /// The value of \c e is set to be true in the edge-map which stores 
   604     /// hide information. If \c e was hidden previuosly, then it is shown 
   605     /// again
   606     void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
   607 
   608     /// Returns true if \c n is hidden.
   609     
   610     ///\e
   611     ///
   612     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
   613 
   614     /// Returns true if \c n is hidden.
   615     
   616     ///\e
   617     ///
   618     bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
   619 
   620     typedef False NodeNumTag;
   621     typedef False EdgeNumTag;
   622 
   623     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   624     Edge findEdge(const Node& source, const Node& target, 
   625 		  const Edge& prev = INVALID) {
   626       Edge edge = Parent::findEdge(source, target, prev);
   627       while (edge != INVALID && !(*uedge_filter_map)[edge]) {
   628         edge = Parent::findEdge(source, target, edge);
   629       }
   630       return edge;
   631     }
   632     UEdge findUEdge(const Node& source, const Node& target, 
   633 		  const UEdge& prev = INVALID) {
   634       UEdge uedge = Parent::findUEdge(source, target, prev);
   635       while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
   636         uedge = Parent::findUEdge(source, target, uedge);
   637       }
   638       return uedge;
   639     }
   640 
   641     template <typename _Value>
   642     class NodeMap 
   643       : public SubMapExtender<Adaptor, 
   644                               typename Parent::template NodeMap<_Value> > 
   645     {
   646     public:
   647       typedef Adaptor Graph;
   648       typedef SubMapExtender<Adaptor, typename Parent::
   649                              template NodeMap<_Value> > Parent;
   650     
   651       NodeMap(const Graph& graph) 
   652 	: Parent(graph) {}
   653       NodeMap(const Graph& graph, const _Value& value) 
   654 	: Parent(graph, value) {}
   655     
   656       NodeMap& operator=(const NodeMap& cmap) {
   657 	return operator=<NodeMap>(cmap);
   658       }
   659     
   660       template <typename CMap>
   661       NodeMap& operator=(const CMap& cmap) {
   662         Parent::operator=(cmap);
   663 	return *this;
   664       }
   665     };
   666 
   667     template <typename _Value>
   668     class EdgeMap 
   669       : public SubMapExtender<Adaptor, 
   670                               typename Parent::template EdgeMap<_Value> > 
   671     {
   672     public:
   673       typedef Adaptor Graph;
   674       typedef SubMapExtender<Adaptor, typename Parent::
   675                              template EdgeMap<_Value> > Parent;
   676     
   677       EdgeMap(const Graph& graph) 
   678 	: Parent(graph) {}
   679       EdgeMap(const Graph& graph, const _Value& value) 
   680 	: Parent(graph, value) {}
   681     
   682       EdgeMap& operator=(const EdgeMap& cmap) {
   683 	return operator=<EdgeMap>(cmap);
   684       }
   685     
   686       template <typename CMap>
   687       EdgeMap& operator=(const CMap& cmap) {
   688         Parent::operator=(cmap);
   689 	return *this;
   690       }
   691     };
   692 
   693     template <typename _Value>
   694     class UEdgeMap 
   695       : public SubMapExtender<Adaptor, 
   696                               typename Parent::template UEdgeMap<_Value> > 
   697     {
   698     public:
   699       typedef Adaptor Graph;
   700       typedef SubMapExtender<Adaptor, typename Parent::
   701                              template UEdgeMap<_Value> > Parent;
   702     
   703       UEdgeMap(const Graph& graph) 
   704 	: Parent(graph) {}
   705       UEdgeMap(const Graph& graph, const _Value& value) 
   706 	: Parent(graph, value) {}
   707     
   708       UEdgeMap& operator=(const UEdgeMap& cmap) {
   709 	return operator=<UEdgeMap>(cmap);
   710       }
   711     
   712       template <typename CMap>
   713       UEdgeMap& operator=(const CMap& cmap) {
   714         Parent::operator=(cmap);
   715 	return *this;
   716       }
   717     };
   718   };
   719 
   720   /// \ingroup graph_adaptors
   721   ///
   722   /// \brief A graph adaptor for hiding nodes and edges from an undirected 
   723   /// graph.
   724   /// 
   725   /// SubUGraphAdaptor shows the undirected graph with filtered node-set and 
   726   /// edge-set. If the \c checked parameter is true then it filters the edgeset
   727   /// to do not get invalid edges without source or target.
   728   /// 
   729   /// If the \c checked template parameter is false then we have to note that 
   730   /// the node-iterator cares only the filter on the node-set, and the 
   731   /// edge-iterator cares only the filter on the edge-set.
   732   /// This way the edge-map
   733   /// should filter all edges which's source or target is filtered by the 
   734   /// node-filter.
   735   ///
   736   /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
   737   /// \c Graph::Node that is why \c g.id(n) can be applied.
   738   /// 
   739   template<typename _UGraph, typename NodeFilterMap, 
   740 	   typename UEdgeFilterMap, bool checked = true>
   741   class SubUGraphAdaptor : 
   742     public UGraphAdaptorExtender<
   743     SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {
   744   public:
   745     typedef _UGraph Graph;
   746     typedef UGraphAdaptorExtender<
   747       SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;
   748   protected:
   749     SubUGraphAdaptor() { }
   750   public:
   751     SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map, 
   752 		    UEdgeFilterMap& _uedge_filter_map) { 
   753       setGraph(_graph);
   754       setNodeFilterMap(_node_filter_map);
   755       setUEdgeFilterMap(_uedge_filter_map);
   756     }
   757   };
   758 
   759   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
   760   SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
   761   subUGraphAdaptor(const UGraph& graph, 
   762                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
   763     return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
   764       (graph, nfm, efm);
   765   }
   766 
   767   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
   768   SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
   769   subUGraphAdaptor(const UGraph& graph, 
   770                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
   771     return SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
   772       (graph, nfm, efm);
   773   }
   774 
   775   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
   776   SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
   777   subUGraphAdaptor(const UGraph& graph, 
   778                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
   779     return SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
   780       (graph, nfm, efm);
   781   }
   782 
   783   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
   784   SubUGraphAdaptor<const UGraph, const NodeFilterMap, const EdgeFilterMap>
   785   subUGraphAdaptor(const UGraph& graph, 
   786                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
   787     return SubUGraphAdaptor<const UGraph, const NodeFilterMap, 
   788       const EdgeFilterMap>(graph, nfm, efm);
   789   }
   790 
   791   /// \ingroup graph_adaptors
   792   ///
   793   /// \brief An adaptor for hiding nodes from an undirected graph.
   794   ///
   795   /// An adaptor for hiding nodes from an undirected graph.
   796   /// This adaptor specializes SubUGraphAdaptor in the way that only
   797   /// the node-set 
   798   /// can be filtered. In usual case the checked parameter is true, we get the
   799   /// induced subgraph. But if the checked parameter is false then we can only
   800   /// filter only isolated nodes.
   801   template<typename _UGraph, typename NodeFilterMap, bool checked = true>
   802   class NodeSubUGraphAdaptor : 
   803     public SubUGraphAdaptor<_UGraph, NodeFilterMap, 
   804                             ConstMap<typename _UGraph::UEdge, bool>, checked> {
   805   public:
   806     typedef SubUGraphAdaptor<_UGraph, NodeFilterMap, 
   807                              ConstMap<typename _UGraph::UEdge, bool> > Parent;
   808     typedef _UGraph Graph;
   809   protected:
   810     ConstMap<typename _UGraph::UEdge, bool> const_true_map;
   811 
   812     NodeSubUGraphAdaptor() : const_true_map(true) {
   813       Parent::setUEdgeFilterMap(const_true_map);
   814     }
   815 
   816   public:
   817     NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : 
   818       Parent(), const_true_map(true) { 
   819       Parent::setGraph(_graph);
   820       Parent::setNodeFilterMap(_node_filter_map);
   821       Parent::setUEdgeFilterMap(const_true_map);
   822     }
   823   };
   824 
   825   template<typename UGraph, typename NodeFilterMap>
   826   NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
   827   nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
   828     return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
   829   }
   830 
   831   template<typename UGraph, typename NodeFilterMap>
   832   NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
   833   nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
   834     return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
   835   }
   836 
   837   /// \ingroup graph_adaptors
   838   ///
   839   /// \brief An adaptor for hiding undirected edges from an undirected graph.
   840   ///
   841   /// \warning Graph adaptors are in even more experimental state
   842   /// than the other parts of the lib. Use them at you own risk.
   843   ///
   844   /// An adaptor for hiding undirected edges from an undirected graph.
   845   /// This adaptor specializes SubUGraphAdaptor in the way that
   846   /// only the edge-set 
   847   /// can be filtered.
   848   template<typename _UGraph, typename UEdgeFilterMap>
   849   class EdgeSubUGraphAdaptor : 
   850     public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>, 
   851                             UEdgeFilterMap, false> {
   852   public:
   853     typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>, 
   854                              UEdgeFilterMap, false> Parent;
   855     typedef _UGraph Graph;
   856   protected:
   857     ConstMap<typename Graph::Node, bool> const_true_map;
   858 
   859     EdgeSubUGraphAdaptor() : const_true_map(true) {
   860       Parent::setNodeFilterMap(const_true_map);
   861     }
   862 
   863   public:
   864 
   865     EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) : 
   866       Parent(), const_true_map(true) { 
   867       Parent::setGraph(_graph);
   868       Parent::setNodeFilterMap(const_true_map);
   869       Parent::setUEdgeFilterMap(_uedge_filter_map);
   870     }
   871 
   872   };
   873 
   874   template<typename UGraph, typename EdgeFilterMap>
   875   EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
   876   edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
   877     return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
   878   }
   879 
   880   template<typename UGraph, typename EdgeFilterMap>
   881   EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
   882   edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
   883     return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
   884   }
   885 
   886   template <typename _UGraph, typename _DirectionMap>
   887   class DirUGraphAdaptorBase {
   888   public:
   889     
   890     typedef _UGraph Graph;
   891     typedef _DirectionMap DirectionMap;
   892 
   893     typedef typename _UGraph::Node Node;
   894     typedef typename _UGraph::UEdge Edge;
   895    
   896     void reverseEdge(const Edge& edge) {
   897       direction->set(edge, !(*direction)[edge]);
   898     }
   899 
   900     void first(Node& i) const { graph->first(i); }
   901     void first(Edge& i) const { graph->first(i); }
   902     void firstIn(Edge& i, const Node& n) const {
   903       bool d;
   904       graph->firstInc(i, d, n);
   905       while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
   906     }
   907     void firstOut(Edge& i, const Node& n ) const { 
   908       bool d;
   909       graph->firstInc(i, d, n);
   910       while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
   911     }
   912 
   913     void next(Node& i) const { graph->next(i); }
   914     void next(Edge& i) const { graph->next(i); }
   915     void nextIn(Edge& i) const {
   916       bool d = !(*direction)[i];
   917       graph->nextInc(i, d);
   918       while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
   919     }
   920     void nextOut(Edge& i) const {
   921       bool d = (*direction)[i];
   922       graph->nextInc(i, d);
   923       while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
   924     }
   925 
   926     Node source(const Edge& e) const { 
   927       return (*direction)[e] ? graph->source(e) : graph->target(e); 
   928     }
   929     Node target(const Edge& e) const { 
   930       return (*direction)[e] ? graph->target(e) : graph->source(e); 
   931     }
   932 
   933     typedef NodeNumTagIndicator<Graph> NodeNumTag;
   934     int nodeNum() const { return graph->nodeNum(); }
   935     
   936     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
   937     int edgeNum() const { return graph->uEdgeNum(); }
   938 
   939     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   940     Edge findEdge(const Node& source, const Node& target, 
   941 		  const Edge& prev = INVALID) {
   942       Edge edge = prev;
   943       bool d = edge == INVALID ? true : (*direction)[edge];
   944       if (d) {
   945         edge = graph->findUEdge(source, target, edge);
   946         while (edge != INVALID && !(*direction)[edge]) {
   947           graph->findUEdge(source, target, edge);
   948         }
   949         if (edge != INVALID) return edge;
   950       }
   951       graph->findUEdge(target, source, edge);
   952       while (edge != INVALID && (*direction)[edge]) {
   953         graph->findUEdge(source, target, edge);
   954       }
   955       return edge;
   956     }
   957   
   958     Node addNode() const { 
   959       return Node(graph->addNode()); 
   960     }
   961 
   962     Edge addEdge(const Node& source, const Node& target) const {
   963       Edge edge = graph->addEdge(source, target);
   964       direction->set(edge, graph->source(edge) == source);
   965       return edge; 
   966     }
   967 
   968     void erase(const Node& i) const { graph->erase(i); }
   969     void erase(const Edge& i) const { graph->erase(i); }
   970   
   971     void clear() const { graph->clear(); }
   972     
   973     int id(const Node& v) const { return graph->id(v); }
   974     int id(const Edge& e) const { return graph->id(e); }
   975 
   976     int maxNodeId() const {
   977       return graph->maxNodeId();
   978     }
   979 
   980     int maxEdgeId() const {
   981       return graph->maxEdgeId();
   982     }
   983 
   984     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
   985 
   986     NodeNotifier& getNotifier(Node) const {
   987       return graph->getNotifier(Node());
   988     } 
   989 
   990     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
   991 
   992     EdgeNotifier& getNotifier(Edge) const {
   993       return graph->getNotifier(Edge());
   994     } 
   995 
   996     template <typename _Value>
   997     class NodeMap : public _UGraph::template NodeMap<_Value> {
   998     public:
   999 
  1000       typedef typename _UGraph::template NodeMap<_Value> Parent;
  1001 
  1002       explicit NodeMap(const DirUGraphAdaptorBase& ga) 
  1003 	: Parent(*ga.graph) {}
  1004 
  1005       NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
  1006 	: Parent(*ga.graph, value) {}
  1007 
  1008       NodeMap& operator=(const NodeMap& cmap) {
  1009         return operator=<NodeMap>(cmap);
  1010       }
  1011 
  1012       template <typename CMap>
  1013       NodeMap& operator=(const CMap& cmap) {
  1014         Parent::operator=(cmap);
  1015         return *this;
  1016       }
  1017 
  1018     };
  1019 
  1020     template <typename _Value>
  1021     class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
  1022     public:
  1023 
  1024       typedef typename _UGraph::template UEdgeMap<_Value> Parent;
  1025 
  1026       explicit EdgeMap(const DirUGraphAdaptorBase& ga) 
  1027 	: Parent(*ga.graph) { }
  1028 
  1029       EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
  1030 	: Parent(*ga.graph, value) { }
  1031 
  1032       EdgeMap& operator=(const EdgeMap& cmap) {
  1033         return operator=<EdgeMap>(cmap);
  1034       }
  1035 
  1036       template <typename CMap>
  1037       EdgeMap& operator=(const CMap& cmap) {
  1038         Parent::operator=(cmap);
  1039         return *this;
  1040       }
  1041     };
  1042 
  1043     
  1044 
  1045   protected:
  1046     Graph* graph;
  1047     DirectionMap* direction;
  1048 
  1049     void setDirectionMap(DirectionMap& _direction) {
  1050       direction = &_direction;
  1051     }
  1052 
  1053     void setGraph(Graph& _graph) {
  1054       graph = &_graph;
  1055     }
  1056 
  1057   };
  1058 
  1059 
  1060   /// \ingroup graph_adaptors
  1061   ///
  1062   /// \brief A directed graph is made from an undirected graph by an adaptor
  1063   ///
  1064   /// This adaptor gives a direction for each uedge in the undirected graph.
  1065   /// The direction of the edges stored in the DirectionMap. This map is
  1066   /// a bool map on the undirected edges. If the uedge is mapped to true
  1067   /// then the direction of the directed edge will be the same as the
  1068   /// default direction of the uedge. The edges can be easily reverted
  1069   /// by the reverseEdge member in the adaptor.  
  1070   template<typename _Graph, 
  1071            typename DirectionMap = typename _Graph::template UEdgeMap<bool> > 
  1072   class DirUGraphAdaptor : 
  1073     public GraphAdaptorExtender<
  1074     DirUGraphAdaptorBase<_Graph, DirectionMap> > {
  1075   public:
  1076     typedef _Graph Graph;
  1077     typedef GraphAdaptorExtender<
  1078       DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
  1079   protected:
  1080     DirUGraphAdaptor() { }
  1081   public:
  1082     DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) { 
  1083       setGraph(_graph);
  1084       setDirectionMap(_direction_map);
  1085     }
  1086   };
  1087 
  1088   template<typename UGraph, typename DirectionMap>
  1089   DirUGraphAdaptor<const UGraph, DirectionMap>
  1090   dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
  1091     return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
  1092   }
  1093 
  1094   template<typename UGraph, typename DirectionMap>
  1095   DirUGraphAdaptor<const UGraph, const DirectionMap>
  1096   dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
  1097     return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
  1098   }
  1099 
  1100 }
  1101 
  1102 #endif