lemon/ugraph_adaptor.h
author kpeter
Tue, 05 Feb 2008 11:03:55 +0000
changeset 2560 635e7985be46
parent 2422 77ed2b97abbd
child 2617 5222a3c470ed
permissions -rw-r--r--
Fix the rename script.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     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& u, const Node& v, 
   103 		  const Edge& prev = INVALID) {
   104       return graph->findEdge(u, v, prev);
   105     }
   106     UEdge findUEdge(const Node& u, const Node& v, 
   107                     const UEdge& prev = INVALID) {
   108       return graph->findUEdge(u, v, prev);
   109     }
   110   
   111     Node addNode() const { return graph->addNode(); }
   112     UEdge addEdge(const Node& u, const Node& v) const { 
   113       return graph->addEdge(u, v); 
   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 ix) const {
   129       return graph->fromNodeId(ix);
   130     }
   131 
   132     Edge fromEdgeId(int ix) const {
   133       return graph->fromEdgeId(ix);
   134     }
   135 
   136     UEdge fromUEdgeId(int ix) const {
   137       return graph->fromUEdgeId(ix);
   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& notifier(Node) const {
   155       return graph->notifier(Node());
   156     } 
   157 
   158     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
   159 
   160     EdgeNotifier& notifier(Edge) const {
   161       return graph->notifier(Edge());
   162     } 
   163 
   164     typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
   165 
   166     UEdgeNotifier& notifier(UEdge) const {
   167       return graph->notifier(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::source(i)]
   315             || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d); 
   316     }
   317 
   318     void next(Node& i) const { 
   319       Parent::next(i); 
   320       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
   321     }
   322 
   323     void next(Edge& i) const { 
   324       Parent::next(i); 
   325       while (i!=INVALID && (!(*uedge_filter_map)[i] 
   326 	     || !(*node_filter_map)[Parent::source(i)]
   327 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
   328     }
   329 
   330     void next(UEdge& i) const { 
   331       Parent::next(i); 
   332       while (i!=INVALID && (!(*uedge_filter_map)[i] 
   333 	     || !(*node_filter_map)[Parent::source(i)]
   334 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
   335     }
   336 
   337     void nextIn(Edge& i) const { 
   338       Parent::nextIn(i); 
   339       while (i!=INVALID && (!(*uedge_filter_map)[i] 
   340 	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
   341     }
   342 
   343     void nextOut(Edge& i) const { 
   344       Parent::nextOut(i); 
   345       while (i!=INVALID && (!(*uedge_filter_map)[i] 
   346 	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
   347     }
   348 
   349     void nextInc(UEdge& i, bool& d) const { 
   350       Parent::nextInc(i, d); 
   351       while (i!=INVALID && (!(*uedge_filter_map)[i]
   352             || !(*node_filter_map)[Parent::source(i)]
   353             || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d); 
   354     }
   355 
   356     /// \brief Hide the given node in the graph.
   357     ///
   358     /// This function hides \c n in the graph, i.e. the iteration 
   359     /// jumps over it. This is done by simply setting the value of \c n  
   360     /// to be false in the corresponding node-map.
   361     void hide(const Node& n) const { node_filter_map->set(n, false); }
   362 
   363     /// \brief Hide the given undirected edge in the graph.
   364     ///
   365     /// This function hides \c e in the graph, i.e. the iteration 
   366     /// jumps over it. This is done by simply setting the value of \c e  
   367     /// to be false in the corresponding uedge-map.
   368     void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
   369 
   370     /// \brief Unhide the given node in the graph.
   371     ///
   372     /// The value of \c n is set to be true in the node-map which stores 
   373     /// hide information. If \c n was hidden previuosly, then it is shown 
   374     /// again
   375      void unHide(const Node& n) const { node_filter_map->set(n, true); }
   376 
   377     /// \brief Hide the given undirected edge in the graph.
   378     ///
   379     /// The value of \c e is set to be true in the uedge-map which stores 
   380     /// hide information. If \c e was hidden previuosly, then it is shown 
   381     /// again
   382     void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
   383 
   384     /// \brief Returns true if \c n is hidden.
   385     ///
   386     /// Returns true if \c n is hidden.
   387     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
   388 
   389     /// \brief Returns true if \c e is hidden.
   390     ///
   391     /// Returns true if \c e is hidden.
   392     bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
   393 
   394     typedef False NodeNumTag;
   395     typedef False EdgeNumTag;
   396 
   397     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   398     Edge findEdge(const Node& u, const Node& v, 
   399 		  const Edge& prev = INVALID) {
   400       if (!(*node_filter_map)[u] || !(*node_filter_map)[v]) {
   401         return INVALID;
   402       }
   403       Edge edge = Parent::findEdge(u, v, prev);
   404       while (edge != INVALID && !(*uedge_filter_map)[edge]) {
   405         edge = Parent::findEdge(u, v, edge);
   406       }
   407       return edge;
   408     }
   409     UEdge findUEdge(const Node& u, const Node& v, 
   410 		  const UEdge& prev = INVALID) {
   411       if (!(*node_filter_map)[u] || !(*node_filter_map)[v]) {
   412         return INVALID;
   413       }
   414       UEdge uedge = Parent::findUEdge(u, v, prev);
   415       while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
   416         uedge = Parent::findUEdge(u, v, uedge);
   417       }
   418       return uedge;
   419     }
   420 
   421     template <typename _Value>
   422     class NodeMap 
   423       : public SubMapExtender<Adaptor, 
   424                               typename Parent::template NodeMap<_Value> > 
   425     {
   426     public:
   427       typedef Adaptor Graph;
   428       typedef SubMapExtender<Adaptor, typename Parent::
   429                              template NodeMap<_Value> > Parent;
   430     
   431       NodeMap(const Graph& g) 
   432 	: Parent(g) {}
   433       NodeMap(const Graph& g, const _Value& v) 
   434 	: Parent(g, v) {}
   435     
   436       NodeMap& operator=(const NodeMap& cmap) {
   437 	return operator=<NodeMap>(cmap);
   438       }
   439     
   440       template <typename CMap>
   441       NodeMap& operator=(const CMap& cmap) {
   442         Parent::operator=(cmap);
   443 	return *this;
   444       }
   445     };
   446 
   447     template <typename _Value>
   448     class EdgeMap 
   449       : public SubMapExtender<Adaptor, 
   450                               typename Parent::template EdgeMap<_Value> > 
   451     {
   452     public:
   453       typedef Adaptor Graph;
   454       typedef SubMapExtender<Adaptor, typename Parent::
   455                              template EdgeMap<_Value> > Parent;
   456     
   457       EdgeMap(const Graph& g) 
   458 	: Parent(g) {}
   459       EdgeMap(const Graph& g, const _Value& v) 
   460 	: Parent(g, v) {}
   461     
   462       EdgeMap& operator=(const EdgeMap& cmap) {
   463 	return operator=<EdgeMap>(cmap);
   464       }
   465     
   466       template <typename CMap>
   467       EdgeMap& operator=(const CMap& cmap) {
   468         Parent::operator=(cmap);
   469 	return *this;
   470       }
   471     };
   472 
   473     template <typename _Value>
   474     class UEdgeMap 
   475       : public SubMapExtender<Adaptor, 
   476                               typename Parent::template UEdgeMap<_Value> > 
   477     {
   478     public:
   479       typedef Adaptor Graph;
   480       typedef SubMapExtender<Adaptor, typename Parent::
   481                              template UEdgeMap<_Value> > Parent;
   482     
   483       UEdgeMap(const Graph& g) 
   484 	: Parent(g) {}
   485       UEdgeMap(const Graph& g, const _Value& v) 
   486 	: Parent(g, v) {}
   487     
   488       UEdgeMap& operator=(const UEdgeMap& cmap) {
   489 	return operator=<UEdgeMap>(cmap);
   490       }
   491     
   492       template <typename CMap>
   493       UEdgeMap& operator=(const CMap& cmap) {
   494         Parent::operator=(cmap);
   495 	return *this;
   496       }
   497     };
   498 
   499   };
   500 
   501   template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
   502   class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false> 
   503     : public UGraphAdaptorBase<_UGraph> {
   504   public:
   505     typedef _UGraph Graph;
   506     typedef SubUGraphAdaptorBase Adaptor;
   507     typedef UGraphAdaptorBase<_UGraph> Parent;
   508   protected:
   509     NodeFilterMap* node_filter_map;
   510     UEdgeFilterMap* uedge_filter_map;
   511     SubUGraphAdaptorBase() : Parent(), 
   512 			    node_filter_map(0), uedge_filter_map(0) { }
   513 
   514     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
   515       node_filter_map=&_node_filter_map;
   516     }
   517     void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
   518       uedge_filter_map=&_uedge_filter_map;
   519     }
   520 
   521   public:
   522 
   523     typedef typename Parent::Node Node;
   524     typedef typename Parent::Edge Edge;
   525     typedef typename Parent::UEdge UEdge;
   526 
   527     void first(Node& i) const { 
   528       Parent::first(i); 
   529       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
   530     }
   531 
   532     void first(Edge& i) const { 
   533       Parent::first(i); 
   534       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
   535     }
   536 
   537     void first(UEdge& i) const { 
   538       Parent::first(i); 
   539       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
   540     }
   541 
   542     void firstIn(Edge& i, const Node& n) const { 
   543       Parent::firstIn(i, n); 
   544       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i); 
   545     }
   546 
   547     void firstOut(Edge& i, const Node& n) const { 
   548       Parent::firstOut(i, n); 
   549       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i); 
   550     }
   551 
   552     void firstInc(UEdge& i, bool& d, const Node& n) const { 
   553       Parent::firstInc(i, d, n); 
   554       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d); 
   555     }
   556 
   557     void next(Node& i) const { 
   558       Parent::next(i); 
   559       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
   560     }
   561     void next(Edge& i) const { 
   562       Parent::next(i); 
   563       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
   564     }
   565     void next(UEdge& i) const { 
   566       Parent::next(i); 
   567       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
   568     }
   569     void nextIn(Edge& i) const { 
   570       Parent::nextIn(i); 
   571       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i); 
   572     }
   573 
   574     void nextOut(Edge& i) const { 
   575       Parent::nextOut(i); 
   576       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i); 
   577     }
   578     void nextInc(UEdge& i, bool& d) const { 
   579       Parent::nextInc(i, d); 
   580       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d); 
   581     }
   582 
   583     /// \brief Hide the given node in the graph.
   584     ///
   585     /// This function hides \c n in the graph, i.e. the iteration 
   586     /// jumps over it. This is done by simply setting the value of \c n  
   587     /// to be false in the corresponding node-map.
   588     void hide(const Node& n) const { node_filter_map->set(n, false); }
   589 
   590     /// \brief Hide the given undirected edge in the graph.
   591     ///
   592     /// This function hides \c e in the graph, i.e. the iteration 
   593     /// jumps over it. This is done by simply setting the value of \c e  
   594     /// to be false in the corresponding uedge-map.
   595     void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
   596 
   597     /// \brief Unhide the given node in the graph.
   598     ///
   599     /// The value of \c n is set to be true in the node-map which stores 
   600     /// hide information. If \c n was hidden previuosly, then it is shown 
   601     /// again
   602      void unHide(const Node& n) const { node_filter_map->set(n, true); }
   603 
   604     /// \brief Hide the given undirected edge in the graph.
   605     ///
   606     /// The value of \c e is set to be true in the uedge-map which stores 
   607     /// hide information. If \c e was hidden previuosly, then it is shown 
   608     /// again
   609     void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
   610 
   611     /// \brief Returns true if \c n is hidden.
   612     ///
   613     /// Returns true if \c n is hidden.
   614     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
   615 
   616     /// \brief Returns true if \c e is hidden.
   617     ///
   618     /// Returns true if \c e is hidden.
   619     bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
   620 
   621     typedef False NodeNumTag;
   622     typedef False EdgeNumTag;
   623 
   624     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   625     Edge findEdge(const Node& u, const Node& v, 
   626 		  const Edge& prev = INVALID) {
   627       Edge edge = Parent::findEdge(u, v, prev);
   628       while (edge != INVALID && !(*uedge_filter_map)[edge]) {
   629         edge = Parent::findEdge(u, v, edge);
   630       }
   631       return edge;
   632     }
   633     UEdge findUEdge(const Node& u, const Node& v, 
   634 		  const UEdge& prev = INVALID) {
   635       UEdge uedge = Parent::findUEdge(u, v, prev);
   636       while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
   637         uedge = Parent::findUEdge(u, v, uedge);
   638       }
   639       return uedge;
   640     }
   641 
   642     template <typename _Value>
   643     class NodeMap 
   644       : public SubMapExtender<Adaptor, 
   645                               typename Parent::template NodeMap<_Value> > 
   646     {
   647     public:
   648       typedef Adaptor Graph;
   649       typedef SubMapExtender<Adaptor, typename Parent::
   650                              template NodeMap<_Value> > Parent;
   651     
   652       NodeMap(const Graph& g) 
   653 	: Parent(g) {}
   654       NodeMap(const Graph& g, const _Value& v) 
   655 	: Parent(g, v) {}
   656     
   657       NodeMap& operator=(const NodeMap& cmap) {
   658 	return operator=<NodeMap>(cmap);
   659       }
   660     
   661       template <typename CMap>
   662       NodeMap& operator=(const CMap& cmap) {
   663         Parent::operator=(cmap);
   664 	return *this;
   665       }
   666     };
   667 
   668     template <typename _Value>
   669     class EdgeMap 
   670       : public SubMapExtender<Adaptor, 
   671                               typename Parent::template EdgeMap<_Value> > 
   672     {
   673     public:
   674       typedef Adaptor Graph;
   675       typedef SubMapExtender<Adaptor, typename Parent::
   676                              template EdgeMap<_Value> > Parent;
   677     
   678       EdgeMap(const Graph& g) 
   679 	: Parent(g) {}
   680       EdgeMap(const Graph& g, const _Value& v) 
   681 	: Parent(g, v) {}
   682     
   683       EdgeMap& operator=(const EdgeMap& cmap) {
   684 	return operator=<EdgeMap>(cmap);
   685       }
   686     
   687       template <typename CMap>
   688       EdgeMap& operator=(const CMap& cmap) {
   689         Parent::operator=(cmap);
   690 	return *this;
   691       }
   692     };
   693 
   694     template <typename _Value>
   695     class UEdgeMap 
   696       : public SubMapExtender<Adaptor, 
   697                               typename Parent::template UEdgeMap<_Value> > 
   698     {
   699     public:
   700       typedef Adaptor Graph;
   701       typedef SubMapExtender<Adaptor, typename Parent::
   702                              template UEdgeMap<_Value> > Parent;
   703     
   704       UEdgeMap(const Graph& g) 
   705 	: Parent(g) {}
   706       UEdgeMap(const Graph& g, const _Value& v) 
   707 	: Parent(g, v) {}
   708     
   709       UEdgeMap& operator=(const UEdgeMap& cmap) {
   710 	return operator=<UEdgeMap>(cmap);
   711       }
   712     
   713       template <typename CMap>
   714       UEdgeMap& operator=(const CMap& cmap) {
   715         Parent::operator=(cmap);
   716 	return *this;
   717       }
   718     };
   719   };
   720 
   721   /// \ingroup graph_adaptors
   722   ///
   723   /// \brief A graph adaptor for hiding nodes and edges from an undirected 
   724   /// graph.
   725   /// 
   726   /// SubUGraphAdaptor shows the undirected graph with filtered node-set and 
   727   /// edge-set. If the \c checked parameter is true then it filters the edgeset
   728   /// to do not get invalid edges without source or target.
   729   /// 
   730   /// If the \c checked template parameter is false then we have to note that 
   731   /// the node-iterator cares only the filter on the node-set, and the 
   732   /// edge-iterator cares only the filter on the edge-set.
   733   /// This way the edge-map
   734   /// should filter all edges which's source or target is filtered by the 
   735   /// node-filter.
   736   ///
   737   template<typename _UGraph, typename NodeFilterMap, 
   738 	   typename UEdgeFilterMap, bool checked = true>
   739   class SubUGraphAdaptor : 
   740     public UGraphAdaptorExtender<
   741     SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {
   742   public:
   743     typedef _UGraph Graph;
   744     typedef UGraphAdaptorExtender<
   745       SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;
   746   protected:
   747     SubUGraphAdaptor() { }
   748   public:
   749     SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map, 
   750 		    UEdgeFilterMap& _uedge_filter_map) { 
   751       setGraph(_graph);
   752       setNodeFilterMap(_node_filter_map);
   753       setUEdgeFilterMap(_uedge_filter_map);
   754     }
   755   };
   756 
   757   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
   758   SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
   759   subUGraphAdaptor(const UGraph& graph, 
   760                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
   761     return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
   762       (graph, nfm, efm);
   763   }
   764 
   765   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
   766   SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
   767   subUGraphAdaptor(const UGraph& graph, 
   768                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
   769     return SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
   770       (graph, nfm, efm);
   771   }
   772 
   773   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
   774   SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
   775   subUGraphAdaptor(const UGraph& graph, 
   776                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
   777     return SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
   778       (graph, nfm, efm);
   779   }
   780 
   781   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
   782   SubUGraphAdaptor<const UGraph, const NodeFilterMap, const EdgeFilterMap>
   783   subUGraphAdaptor(const UGraph& graph, 
   784                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
   785     return SubUGraphAdaptor<const UGraph, const NodeFilterMap, 
   786       const EdgeFilterMap>(graph, nfm, efm);
   787   }
   788 
   789   /// \ingroup graph_adaptors
   790   ///
   791   /// \brief An adaptor for hiding nodes from an undirected graph.
   792   ///
   793   /// An adaptor for hiding nodes from an undirected graph.  This
   794   /// adaptor specializes SubUGraphAdaptor in the way that only the
   795   /// node-set can be filtered. In usual case the checked parameter is
   796   /// true, we get the induced subgraph. But if the checked parameter
   797   /// is false then we can filter only isolated nodes.
   798   template<typename _UGraph, typename NodeFilterMap, bool checked = true>
   799   class NodeSubUGraphAdaptor : 
   800     public SubUGraphAdaptor<_UGraph, NodeFilterMap, 
   801                             ConstMap<typename _UGraph::UEdge, bool>, checked> {
   802   public:
   803     typedef SubUGraphAdaptor<_UGraph, NodeFilterMap, 
   804                              ConstMap<typename _UGraph::UEdge, bool> > Parent;
   805     typedef _UGraph Graph;
   806   protected:
   807     ConstMap<typename _UGraph::UEdge, bool> const_true_map;
   808 
   809     NodeSubUGraphAdaptor() : const_true_map(true) {
   810       Parent::setUEdgeFilterMap(const_true_map);
   811     }
   812 
   813   public:
   814     NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : 
   815       Parent(), const_true_map(true) { 
   816       Parent::setGraph(_graph);
   817       Parent::setNodeFilterMap(_node_filter_map);
   818       Parent::setUEdgeFilterMap(const_true_map);
   819     }
   820   };
   821 
   822   template<typename UGraph, typename NodeFilterMap>
   823   NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
   824   nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
   825     return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
   826   }
   827 
   828   template<typename UGraph, typename NodeFilterMap>
   829   NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
   830   nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
   831     return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
   832   }
   833 
   834   /// \ingroup graph_adaptors
   835   ///
   836   /// \brief An adaptor for hiding undirected edges from an undirected graph.
   837   ///
   838   /// \warning Graph adaptors are in even more experimental state
   839   /// than the other parts of the lib. Use them at you own risk.
   840   ///
   841   /// An adaptor for hiding undirected edges from an undirected graph.
   842   /// This adaptor specializes SubUGraphAdaptor in the way that
   843   /// only the edge-set 
   844   /// can be filtered.
   845   template<typename _UGraph, typename UEdgeFilterMap>
   846   class EdgeSubUGraphAdaptor : 
   847     public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>, 
   848                             UEdgeFilterMap, false> {
   849   public:
   850     typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>, 
   851                              UEdgeFilterMap, false> Parent;
   852     typedef _UGraph Graph;
   853   protected:
   854     ConstMap<typename Graph::Node, bool> const_true_map;
   855 
   856     EdgeSubUGraphAdaptor() : const_true_map(true) {
   857       Parent::setNodeFilterMap(const_true_map);
   858     }
   859 
   860   public:
   861 
   862     EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) : 
   863       Parent(), const_true_map(true) { 
   864       Parent::setGraph(_graph);
   865       Parent::setNodeFilterMap(const_true_map);
   866       Parent::setUEdgeFilterMap(_uedge_filter_map);
   867     }
   868 
   869   };
   870 
   871   template<typename UGraph, typename EdgeFilterMap>
   872   EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
   873   edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
   874     return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
   875   }
   876 
   877   template<typename UGraph, typename EdgeFilterMap>
   878   EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
   879   edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
   880     return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
   881   }
   882 
   883   /// \brief Base of direct undirected graph adaptor
   884   ///
   885   /// Base class of the direct undirected graph adaptor. All public member
   886   /// of this class can be used with the DirUGraphAdaptor too.
   887   /// \sa DirUGraphAdaptor
   888   template <typename _UGraph, typename _DirectionMap>
   889   class DirUGraphAdaptorBase {
   890   public:
   891     
   892     typedef _UGraph Graph;
   893     typedef _DirectionMap DirectionMap;
   894 
   895     typedef typename _UGraph::Node Node;
   896     typedef typename _UGraph::UEdge Edge;
   897    
   898     /// \brief Reverse edge
   899     /// 
   900     /// It reverse the given edge. It simply negate the direction in the map.
   901     void reverseEdge(const Edge& edge) {
   902       direction->set(edge, !(*direction)[edge]);
   903     }
   904 
   905     void first(Node& i) const { graph->first(i); }
   906     void first(Edge& i) const { graph->first(i); }
   907     void firstIn(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     void firstOut(Edge& i, const Node& n ) const { 
   913       bool d;
   914       graph->firstInc(i, d, n);
   915       while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
   916     }
   917 
   918     void next(Node& i) const { graph->next(i); }
   919     void next(Edge& i) const { graph->next(i); }
   920     void nextIn(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     void nextOut(Edge& i) const {
   926       bool d = (*direction)[i];
   927       graph->nextInc(i, d);
   928       while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
   929     }
   930 
   931     Node source(const Edge& e) const { 
   932       return (*direction)[e] ? graph->source(e) : graph->target(e); 
   933     }
   934     Node target(const Edge& e) const { 
   935       return (*direction)[e] ? graph->target(e) : graph->source(e); 
   936     }
   937 
   938     typedef NodeNumTagIndicator<Graph> NodeNumTag;
   939     int nodeNum() const { return graph->nodeNum(); }
   940     
   941     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
   942     int edgeNum() const { return graph->uEdgeNum(); }
   943 
   944     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   945     Edge findEdge(const Node& u, const Node& v, 
   946 		  const Edge& prev = INVALID) {
   947       Edge edge = prev;
   948       bool d = edge == INVALID ? true : (*direction)[edge];
   949       if (d) {
   950         edge = graph->findUEdge(u, v, edge);
   951         while (edge != INVALID && !(*direction)[edge]) {
   952           graph->findUEdge(u, v, edge);
   953         }
   954         if (edge != INVALID) return edge;
   955       }
   956       graph->findUEdge(v, u, edge);
   957       while (edge != INVALID && (*direction)[edge]) {
   958         graph->findUEdge(u, v, edge);
   959       }
   960       return edge;
   961     }
   962   
   963     Node addNode() const { 
   964       return Node(graph->addNode()); 
   965     }
   966 
   967     Edge addEdge(const Node& u, const Node& v) const {
   968       Edge edge = graph->addEdge(u, v);
   969       direction->set(edge, graph->source(edge) == u);
   970       return edge; 
   971     }
   972 
   973     void erase(const Node& i) const { graph->erase(i); }
   974     void erase(const Edge& i) const { graph->erase(i); }
   975   
   976     void clear() const { graph->clear(); }
   977     
   978     int id(const Node& v) const { return graph->id(v); }
   979     int id(const Edge& e) const { return graph->id(e); }
   980 
   981     int maxNodeId() const {
   982       return graph->maxNodeId();
   983     }
   984 
   985     int maxEdgeId() const {
   986       return graph->maxEdgeId();
   987     }
   988 
   989     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
   990 
   991     NodeNotifier& notifier(Node) const {
   992       return graph->notifier(Node());
   993     } 
   994 
   995     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
   996 
   997     EdgeNotifier& notifier(Edge) const {
   998       return graph->notifier(Edge());
   999     } 
  1000 
  1001     template <typename _Value>
  1002     class NodeMap : public _UGraph::template NodeMap<_Value> {
  1003     public:
  1004 
  1005       typedef typename _UGraph::template NodeMap<_Value> Parent;
  1006 
  1007       explicit NodeMap(const DirUGraphAdaptorBase& ga) 
  1008 	: Parent(*ga.graph) {}
  1009 
  1010       NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
  1011 	: Parent(*ga.graph, value) {}
  1012 
  1013       NodeMap& operator=(const NodeMap& cmap) {
  1014         return operator=<NodeMap>(cmap);
  1015       }
  1016 
  1017       template <typename CMap>
  1018       NodeMap& operator=(const CMap& cmap) {
  1019         Parent::operator=(cmap);
  1020         return *this;
  1021       }
  1022 
  1023     };
  1024 
  1025     template <typename _Value>
  1026     class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
  1027     public:
  1028 
  1029       typedef typename _UGraph::template UEdgeMap<_Value> Parent;
  1030 
  1031       explicit EdgeMap(const DirUGraphAdaptorBase& ga) 
  1032 	: Parent(*ga.graph) { }
  1033 
  1034       EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
  1035 	: Parent(*ga.graph, value) { }
  1036 
  1037       EdgeMap& operator=(const EdgeMap& cmap) {
  1038         return operator=<EdgeMap>(cmap);
  1039       }
  1040 
  1041       template <typename CMap>
  1042       EdgeMap& operator=(const CMap& cmap) {
  1043         Parent::operator=(cmap);
  1044         return *this;
  1045       }
  1046     };
  1047 
  1048     
  1049 
  1050   protected:
  1051     Graph* graph;
  1052     DirectionMap* direction;
  1053 
  1054     void setDirectionMap(DirectionMap& _direction) {
  1055       direction = &_direction;
  1056     }
  1057 
  1058     void setGraph(Graph& _graph) {
  1059       graph = &_graph;
  1060     }
  1061 
  1062   };
  1063 
  1064 
  1065   /// \ingroup graph_adaptors
  1066   ///
  1067   /// \brief A directed graph is made from an undirected graph by an adaptor
  1068   ///
  1069   /// This adaptor gives a direction for each uedge in the undirected
  1070   /// graph. The direction of the edges stored in the
  1071   /// DirectionMap. This map is a bool map on the undirected edges. If
  1072   /// the uedge is mapped to true then the direction of the directed
  1073   /// edge will be the same as the default direction of the uedge. The
  1074   /// edges can be easily reverted by the \ref
  1075   /// DirUGraphAdaptorBase::reverseEdge "reverseEdge()" member in the
  1076   /// adaptor.
  1077   ///
  1078   /// It can be used to solve orientation problems on directed graphs.
  1079   /// By example how can we orient an undirected graph to get the minimum
  1080   /// number of strongly connected components. If we orient the edges with
  1081   /// the dfs algorithm out from the source then we will get such an 
  1082   /// orientation. 
  1083   ///
  1084   /// We use the \ref DfsVisitor "visitor" interface of the 
  1085   /// \ref DfsVisit "dfs" algorithm:
  1086   ///\code
  1087   /// template <typename DirMap>
  1088   /// class OrientVisitor : public DfsVisitor<UGraph> {
  1089   /// public:
  1090   ///
  1091   ///   OrientVisitor(const UGraph& ugraph, DirMap& dirMap)
  1092   ///     : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}
  1093   ///
  1094   ///   void discover(const Edge& edge) {
  1095   ///     _processed.set(edge, true);
  1096   ///     _dirMap.set(edge, _ugraph.direction(edge));
  1097   ///   }
  1098   ///
  1099   ///   void examine(const Edge& edge) {
  1100   ///     if (_processed[edge]) return;
  1101   ///     _processed.set(edge, true);
  1102   ///     _dirMap.set(edge, _ugraph.direction(edge));
  1103   ///   }  
  1104   /// 
  1105   /// private:
  1106   ///   const UGraph& _ugraph;  
  1107   ///   DirMap& _dirMap;
  1108   ///   UGraph::UEdgeMap<bool> _processed;
  1109   /// };
  1110   ///\endcode
  1111   ///
  1112   /// And now we can use the orientation:
  1113   ///\code
  1114   /// UGraph::UEdgeMap<bool> dmap(ugraph);
  1115   ///
  1116   /// typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
  1117   /// Visitor visitor(ugraph, dmap);
  1118   ///
  1119   /// DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
  1120   ///
  1121   /// dfs.run();
  1122   ///
  1123   /// typedef DirUGraphAdaptor<UGraph> DGraph;
  1124   /// DGraph dgraph(ugraph, dmap);
  1125   ///
  1126   /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) == 
  1127   ///              countBiEdgeConnectedComponents(ugraph), "Wrong Orientation");
  1128   ///\endcode
  1129   ///
  1130   /// The number of the bi-connected components is a lower bound for
  1131   /// the number of the strongly connected components in the directed
  1132   /// graph because if we contract the bi-connected components to
  1133   /// nodes we will get a tree therefore we cannot orient edges in
  1134   /// both direction between bi-connected components. In the other way
  1135   /// the algorithm will orient one component to be strongly
  1136   /// connected. The two relations proof that the assertion will
  1137   /// be always true and the found solution is optimal.
  1138   ///
  1139   /// \sa DirUGraphAdaptorBase
  1140   /// \sa dirUGraphAdaptor
  1141   template<typename _Graph, 
  1142            typename DirectionMap = typename _Graph::template UEdgeMap<bool> > 
  1143   class DirUGraphAdaptor : 
  1144     public GraphAdaptorExtender<
  1145     DirUGraphAdaptorBase<_Graph, DirectionMap> > {
  1146   public:
  1147     typedef _Graph Graph;
  1148     typedef GraphAdaptorExtender<
  1149       DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
  1150   protected:
  1151     DirUGraphAdaptor() { }
  1152   public:
  1153     
  1154     /// \brief Constructor of the adaptor
  1155     ///
  1156     /// Constructor of the adaptor
  1157     DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) { 
  1158       setGraph(_graph);
  1159       setDirectionMap(_direction_map);
  1160     }
  1161   };
  1162 
  1163   /// \brief Just gives back a DirUGraphAdaptor
  1164   ///
  1165   /// Just gives back a DirUGraphAdaptor
  1166   template<typename UGraph, typename DirectionMap>
  1167   DirUGraphAdaptor<const UGraph, DirectionMap>
  1168   dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
  1169     return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
  1170   }
  1171 
  1172   template<typename UGraph, typename DirectionMap>
  1173   DirUGraphAdaptor<const UGraph, const DirectionMap>
  1174   dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
  1175     return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
  1176   }
  1177 
  1178 }
  1179 
  1180 #endif