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