lemon/bpugraph_adaptor.h
author deba
Thu, 22 Jun 2006 15:16:11 +0000
changeset 2107 e1055232c670
parent 2040 c7bd55c0d820
child 2231 06faf3f06d67
permissions -rw-r--r--
Added reserveNode function.
     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_BPUGRAPH_ADAPTOR_H
    20 #define LEMON_BPUGRAPH_ADAPTOR_H
    21 
    22 #include <lemon/bits/invalid.h>
    23 #include <lemon/maps.h>
    24 
    25 #include <lemon/bits/graph_adaptor_extender.h>
    26 
    27 #include <lemon/bits/traits.h>
    28 
    29 #include <iostream>
    30 
    31 ///\ingroup graph_adaptors
    32 ///\file
    33 ///\brief Several graph adaptors.
    34 ///
    35 ///This file contains several useful bpugraph adaptor functions.
    36 ///
    37 ///\author Balazs Dezso
    38 
    39 namespace lemon {
    40 
    41   /// \ingroup graph_adaptors
    42   ///
    43   /// \brief Base type for the Bipartite Undirected Graph Adaptors
    44   ///
    45   /// This is the base type for most of LEMON bpugraph adaptors. 
    46   /// This class implements a trivial graph adaptor i.e. it only wraps the 
    47   /// functions and types of the graph. The purpose of this class is to 
    48   /// make easier implementing graph adaptors. E.g. if an adaptor is 
    49   /// considered which differs from the wrapped graph only in some of its 
    50   /// functions or types, then it can be derived from BpUGraphAdaptor, and 
    51   /// only the differences should be implemented.
    52   ///
    53   /// \author Balazs Dezso 
    54   template<typename _BpUGraph>
    55   class BpUGraphAdaptorBase {
    56   public:
    57     typedef _BpUGraph Graph;
    58     typedef Graph ParentGraph;
    59 
    60   protected:
    61     Graph* graph;
    62 
    63     BpUGraphAdaptorBase() : graph(0) {}
    64 
    65     void setGraph(Graph& _graph) { graph = &_graph; }
    66 
    67     Graph& getGraph() { return *graph; }
    68     const Graph& getGraph() const { return *graph; }
    69 
    70   public:
    71 
    72     BpUGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
    73  
    74     typedef typename Graph::Node Node;
    75     typedef typename Graph::ANode ANode;
    76     typedef typename Graph::BNode BNode;
    77     typedef typename Graph::Edge Edge;
    78     typedef typename Graph::UEdge UEdge;
    79    
    80     void first(Node& i) const { graph->first(i); }
    81     void firstANode(Node& i) const { graph->firstANode(i); }
    82     void firstBNode(Node& i) const { graph->firstBNode(i); }
    83     void first(Edge& i) const { graph->first(i); }
    84     void first(UEdge& i) const { graph->first(i); }
    85     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
    86     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
    87     void firstInc(UEdge &i, bool &d, const Node &n) const {
    88       graph->firstInc(i, d, n);
    89     }
    90 
    91     void next(Node& i) const { graph->next(i); }
    92     void nextANode(Node& i) const { graph->nextANode(i); }
    93     void nextBNode(Node& i) const { graph->nextBNode(i); }
    94     void next(Edge& i) const { graph->next(i); }
    95     void next(UEdge& i) const { graph->next(i); }
    96     void nextIn(Edge& i) const { graph->nextIn(i); }
    97     void nextOut(Edge& i) const { graph->nextOut(i); }
    98     void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
    99 
   100     Node source(const UEdge& e) const { return graph->source(e); }
   101     Node target(const UEdge& e) const { return graph->target(e); }
   102 
   103     Node source(const Edge& e) const { return graph->source(e); }
   104     Node target(const Edge& e) const { return graph->target(e); }
   105 
   106     Node aNode(const UEdge& e) const { return graph->aNode(e); }
   107     Node bNode(const UEdge& e) const { return graph->bNode(e); }
   108 
   109     bool aNode(const Node& n) const { return graph->aNode(n); }
   110     bool bNode(const Node& n) const { return graph->bNode(n); }
   111 
   112     typedef NodeNumTagIndicator<Graph> NodeNumTag;
   113     int nodeNum() const { return graph->nodeNum(); }
   114     int aNodeNum() const { return graph->aNodeNum(); }
   115     int bNodeNum() const { return graph->bNodeNum(); }
   116     
   117     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
   118     int edgeNum() const { return graph->edgeNum(); }
   119     int uEdgeNum() const { return graph->uEdgeNum(); }
   120 
   121     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   122     Edge findEdge(const Node& source, const Node& target, 
   123 		  const Edge& prev = INVALID) {
   124       return graph->findEdge(source, target, prev);
   125     }
   126     UEdge findUEdge(const Node& source, const Node& target, 
   127                     const UEdge& prev = INVALID) {
   128       return graph->findUEdge(source, target, prev);
   129     }
   130   
   131     Node addANode() const { return graph->addANode(); }
   132     Node addBNode() const { return graph->addBNode(); }
   133     UEdge addEdge(const Node& source, const Node& target) const { 
   134       return graph->addEdge(source, target); 
   135     }
   136 
   137     void erase(const Node& i) const { graph->erase(i); }
   138     void erase(const UEdge& i) const { graph->erase(i); }
   139   
   140     void clear() const { graph->clear(); }
   141 
   142     bool direction(const Edge& e) const { return graph->direction(e); }
   143     Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
   144     
   145     int id(const Node& v) const { return graph->id(v); }
   146     int id(const ANode& v) const { return graph->id(v); }
   147     int id(const BNode& v) const { return graph->id(v); }
   148     int id(const Edge& e) const { return graph->id(e); }
   149     int id(const UEdge& e) const { return graph->id(e); }
   150 
   151     Node fromNodeId(int id) const { return graph->fromNodeId(id); }
   152     ANode fromANodeId(int id) const { return graph->fromANodeId(id); }
   153     BNode fromBNodeId(int id) const { return graph->fromBNodeId(id); }
   154     Edge fromEdgeId(int id) const { return graph->fromEdgeId(id); }
   155     UEdge fromUEdgeId(int id) const { return graph->fromUEdgeId(id); }
   156 
   157     int maxNodeId() const { return graph->maxNodeId(); }
   158     int maxANodeId() const { return graph->maxANodeId(); }
   159     int maxBNodeId() const { return graph->maxBNodeId(); }
   160     int maxEdgeId() const { return graph->maxEdgeId(); }
   161     int maxUEdgeId() const { return graph->maxEdgeId(); }
   162 
   163     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
   164     NodeNotifier& getNotifier(Node) const {
   165       return graph->getNotifier(Node()); 
   166     } 
   167 
   168     typedef typename ItemSetTraits<Graph, ANode>::ItemNotifier ANodeNotifier;
   169     ANodeNotifier& getNotifier(ANode) const {
   170       return graph->getNotifier(ANode());
   171     } 
   172 
   173     typedef typename ItemSetTraits<Graph, BNode>::ItemNotifier BNodeNotifier;
   174     BNodeNotifier& getNotifier(BNode) const {
   175       return graph->getNotifier(BNode());
   176     } 
   177 
   178     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
   179     EdgeNotifier& getNotifier(Edge) const {
   180       return graph->getNotifier(Edge());
   181     } 
   182 
   183     typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
   184     UEdgeNotifier& getNotifier(UEdge) const {
   185       return graph->getNotifier(UEdge());
   186     } 
   187 
   188     template <typename _Value>
   189     class NodeMap : public Graph::template NodeMap<_Value> {
   190     public:
   191       typedef typename Graph::template NodeMap<_Value> Parent;
   192       explicit NodeMap(const BpUGraphAdaptorBase<Graph>& ga) 
   193 	: Parent(*ga.graph) {}
   194       NodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
   195 	: Parent(*ga.graph, value) {}
   196 
   197       NodeMap& operator=(const NodeMap& cmap) {
   198 	return operator=<NodeMap>(cmap);
   199       }
   200 
   201       template <typename CMap>
   202       NodeMap& operator=(const CMap& cmap) {
   203         Parent::operator=(cmap);
   204 	return *this;
   205       }
   206     };
   207 
   208     template <typename _Value>
   209     class ANodeMap : public Graph::template ANodeMap<_Value> {
   210     public:
   211       typedef typename Graph::template ANodeMap<_Value> Parent;
   212       explicit ANodeMap(const BpUGraphAdaptorBase& ga) 
   213 	: Parent(*ga.graph) {}
   214       ANodeMap(const BpUGraphAdaptorBase& ga, const _Value& value)
   215 	: Parent(*ga.graph, value) {}
   216 
   217       ANodeMap& operator=(const ANodeMap& cmap) {
   218 	return operator=<ANodeMap>(cmap);
   219       }
   220 
   221       template <typename CMap>
   222       ANodeMap& operator=(const CMap& cmap) {
   223         Parent::operator=(cmap);
   224 	return *this;
   225       }
   226     };
   227 
   228     template <typename _Value>
   229     class BNodeMap : public Graph::template BNodeMap<_Value> {
   230     public:
   231       typedef typename Graph::template BNodeMap<_Value> Parent;
   232       explicit BNodeMap(const BpUGraphAdaptorBase<Graph>& ga) 
   233 	: Parent(*ga.graph) {}
   234       BNodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
   235 	: Parent(*ga.graph, value) {}
   236 
   237       BNodeMap& operator=(const BNodeMap& cmap) {
   238 	return operator=<BNodeMap>(cmap);
   239       }
   240 
   241       template <typename CMap>
   242       BNodeMap& operator=(const CMap& cmap) {
   243         Parent::operator=(cmap);
   244 	return *this;
   245       }
   246     };
   247 
   248     template <typename _Value>
   249     class EdgeMap : public Graph::template EdgeMap<_Value> {
   250     public:
   251       typedef typename Graph::template EdgeMap<_Value> Parent;
   252       explicit EdgeMap(const BpUGraphAdaptorBase<Graph>& ga) 
   253 	: Parent(*ga.graph) {}
   254       EdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
   255 	: Parent(*ga.graph, value) {}
   256 
   257       EdgeMap& operator=(const EdgeMap& cmap) {
   258 	return operator=<EdgeMap>(cmap);
   259       }
   260 
   261       template <typename CMap>
   262       EdgeMap& operator=(const CMap& cmap) {
   263         Parent::operator=(cmap);
   264 	return *this;
   265       }
   266     };
   267 
   268     template <typename _Value>
   269     class UEdgeMap : public Graph::template UEdgeMap<_Value> {
   270     public:
   271       typedef typename Graph::template UEdgeMap<_Value> Parent;
   272       explicit UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga) 
   273 	: Parent(*ga.graph) {}
   274       UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
   275 	: Parent(*ga.graph, value) {}
   276 
   277       UEdgeMap& operator=(const UEdgeMap& cmap) {
   278 	return operator=<UEdgeMap>(cmap);
   279       }
   280 
   281       template <typename CMap>
   282       UEdgeMap& operator=(const CMap& cmap) {
   283         Parent::operator=(cmap);
   284 	return *this;
   285       }
   286     };
   287 
   288   };
   289 
   290   /// \ingroup graph_adaptors
   291   ///
   292   /// \brief Trivial Bipartite Undirected Graph Adaptor
   293   ///
   294   /// Trivial Bipartite Undirected Graph Adaptor. It does not change
   295   /// the functionality of the adapted graph.
   296   template <typename _BpUGraph>
   297   class BpUGraphAdaptor 
   298     : public BpUGraphAdaptorExtender< BpUGraphAdaptorBase<_BpUGraph> > { 
   299   public:
   300     typedef _BpUGraph Graph;
   301     typedef BpUGraphAdaptorExtender<BpUGraphAdaptorBase<_BpUGraph> > Parent;
   302   protected:
   303     BpUGraphAdaptor() : Parent() {}
   304 
   305   public:
   306     explicit BpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
   307   };
   308 
   309   template <typename _BpUGraph>
   310   class SwapBpUGraphAdaptorBase : public BpUGraphAdaptorBase<_BpUGraph> {
   311   public:
   312     
   313     typedef _BpUGraph Graph;
   314     typedef BpUGraphAdaptorBase<_BpUGraph> Parent;
   315 
   316   protected:
   317     
   318     SwapBpUGraphAdaptorBase() {}
   319 
   320   public:
   321 
   322     typedef typename Parent::Node Node;
   323     typedef typename Parent::BNode ANode;
   324     typedef typename Parent::ANode BNode;
   325     typedef typename Parent::Edge Edge;
   326     typedef typename Parent::UEdge UEdge;
   327 
   328     bool direction(const Edge& e) const { return !Parent::direction(e); }
   329     Edge direct(const UEdge& e, bool b) const { return Parent::direct(e, !b); }
   330 
   331     Node aNode(const UEdge& e) const { return Parent::bNode(e); }
   332     Node bNode(const UEdge& e) const { return Parent::aNode(e); }
   333 
   334     bool aNode(const Node& n) const { return Parent::bNode(n); }
   335     bool bNode(const Node& n) const { return Parent::aNode(n); }
   336 
   337     void firstANode(Node& i) const { Parent::firstBNode(i); }
   338     void firstBNode(Node& i) const { Parent::firstANode(i); }
   339 
   340     void nextANode(Node& i) const { Parent::nextBNode(i); }
   341     void nextBNode(Node& i) const { Parent::nextANode(i); }
   342 
   343     int id(const ANode& v) const { return Parent::id(v); }
   344     int id(const BNode& v) const { return Parent::id(v); }
   345 
   346     ANode fromANodeId(int id) const { return Parent::fromBNodeId(id); }
   347     BNode fromBNodeId(int id) const { return Parent::fromANodeId(id); }
   348 
   349     int maxANodeId() const { return Parent::maxBNodeId(); }
   350     int maxBNodeId() const { return Parent::maxANodeId(); }
   351 
   352     int aNodeNum() const { return Parent::bNodeNum(); }
   353     int bNodeNum() const { return Parent::aNodeNum(); }
   354 
   355     typedef typename Parent::BNodeNotifier ANodeNotifier;
   356     ANodeNotifier& getNotifier(ANode) const {
   357       return Parent::getNotifier(typename Parent::BNode());
   358     } 
   359 
   360     typedef typename Parent::ANodeNotifier BNodeNotifier;
   361     BNodeNotifier& getNotifier(BNode) const {
   362       return Parent::getNotifier(typename Parent::ANode());
   363     } 
   364 
   365     template <typename _Value>
   366     class ANodeMap : public Graph::template BNodeMap<_Value> {
   367     public:
   368       typedef typename Graph::template BNodeMap<_Value> Parent;
   369       explicit ANodeMap(const SwapBpUGraphAdaptorBase& ga) 
   370 	: Parent(*ga.graph) {}
   371       ANodeMap(const SwapBpUGraphAdaptorBase& ga, const _Value& value)
   372 	: Parent(*ga.graph, value) {}
   373 
   374       ANodeMap& operator=(const ANodeMap& cmap) {
   375 	return operator=<ANodeMap>(cmap);
   376       }
   377 
   378       template <typename CMap>
   379       ANodeMap& operator=(const CMap& cmap) {
   380         Parent::operator=(cmap);
   381 	return *this;
   382       }
   383     };
   384 
   385     template <typename _Value>
   386     class BNodeMap : public Graph::template ANodeMap<_Value> {
   387     public:
   388       typedef typename Graph::template ANodeMap<_Value> Parent;
   389       explicit BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga) 
   390 	: Parent(*ga.graph) {}
   391       BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga, const _Value& value)
   392 	: Parent(*ga.graph, value) {}
   393 
   394       BNodeMap& operator=(const BNodeMap& cmap) {
   395 	return operator=<BNodeMap>(cmap);
   396       }
   397 
   398       template <typename CMap>
   399       BNodeMap& operator=(const CMap& cmap) {
   400         Parent::operator=(cmap);
   401 	return *this;
   402       }
   403     };
   404     
   405   };
   406 
   407   /// \ingroup graph_adaptors
   408   ///
   409   /// \brief Bipartite graph adaptor which swaps the two nodeset.
   410   ///
   411   /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's
   412   /// anode-set will be the original graph's bnode-set and the adaptor's
   413   /// bnode-set will be the original graph's anode-set.
   414   ///
   415   /// As example look at an algorithm what can be sped up with the
   416   /// swap bipartite undirected graph adaptor. If we want to find the
   417   /// maximum matching in the bipartite graph then it will be not changed
   418   /// if we swap the two nodesets. But the algorithm use the two nodeset
   419   /// different way. If we swap the nodesets it provides different
   420   /// running time. We run a test on random bipartite graphs with
   421   /// different rate of the anode-set size and bnode-set size.
   422   /// We always made graphs with 10000 nodes and 20000 edges and we
   423   /// computed the maximum cardinality matching with the Hopcroft-Karp 
   424   /// algorithm.
   425   ///
   426   /// The next diagram shows the running time of the tests. If the anode-set
   427   /// is smaller than the bnode-set the running time is better than with 
   428   /// the swapped graph. Other conclusion is that the running time
   429   /// is greater when the two nodesets size are nearly equal. 
   430   ///
   431   /// \image html swap_test.png
   432   /// \image latex swap_test.eps "Swapping nodesets" width=\textwidth
   433   /// 
   434   /// The next part shows how can we swap the two nodeset:
   435   ///
   436   ///\code
   437   /// typedef SwapBpUGraphAdaptor<BpUGraph> SBpUGraph;
   438   /// SBpUGraph sbpugraph(bpugraph);
   439   /// MaxBipartiteMatching<SBpUGraph> sbpumatch(sbpugraph);
   440   ///\endcode
   441   template <typename _BpUGraph>
   442   class SwapBpUGraphAdaptor 
   443     : public BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > { 
   444   public:
   445 
   446     typedef _BpUGraph Graph;
   447     typedef BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > 
   448     Parent;
   449 
   450   protected:
   451     SwapBpUGraphAdaptor() : Parent() {}
   452 
   453   public:
   454 
   455     /// \brief Construct a swapped graph.
   456     ///
   457     /// Construct a swapped graph.
   458     explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
   459 
   460   };
   461 
   462 
   463   template <typename _BpUGraph, 
   464             typename _ANMatchingMap, typename _BNMatchingMap>
   465   class MatchingBpUGraphAdaptorBase 
   466     : public BpUGraphAdaptorBase<const _BpUGraph>
   467   {
   468   public:
   469     
   470     typedef _BpUGraph Graph;
   471     typedef _ANMatchingMap ANodeMatchingMap;
   472     typedef _BNMatchingMap BNodeMatchingMap;
   473 
   474     typedef BpUGraphAdaptorBase<const _BpUGraph> Parent;
   475 
   476   protected:
   477     
   478     MatchingBpUGraphAdaptorBase() {}
   479 
   480     void setANodeMatchingMap(ANodeMatchingMap& _anode_matching) {
   481       anode_matching = &_anode_matching;
   482     }
   483 
   484     void setBNodeMatchingMap(BNodeMatchingMap& _bnode_matching) {
   485       bnode_matching = &_bnode_matching;
   486     }
   487 
   488   public:
   489 
   490     typedef typename Parent::Node Node;
   491     typedef typename Parent::Edge Edge;
   492 
   493     void firstOut(Edge& edge, const Node& node) const {
   494       if (Parent::aNode(node)) {
   495         Parent::firstOut(edge, node);
   496         if (edge != INVALID && (*anode_matching)[node] == edge) {
   497           Parent::nextOut(edge);
   498         }
   499       } else {
   500         edge = (*bnode_matching)[node] != INVALID ?
   501           Parent::direct((*bnode_matching)[node], false) : INVALID;
   502       }
   503     }
   504 
   505     void nextOut(Edge& edge) const {
   506       if (Parent::aNode(Parent::source(edge))) {
   507         Parent::nextOut(edge);
   508         if (edge != INVALID && (*anode_matching)[Parent::aNode(edge)] == edge) {
   509           Parent::nextOut(edge);
   510         }
   511       } else {
   512         edge = INVALID;
   513       }
   514     }
   515  
   516     void firstIn(Edge& edge, const Node& node) const {
   517       if (Parent::aNode(node)) {
   518         edge = (*bnode_matching)[node] != INVALID ?
   519           Parent::direct((*anode_matching)[node], false) : INVALID;
   520       } else {
   521         Parent::firstIn(edge, node);
   522         if (edge != INVALID && (*bnode_matching)[node] == edge) {
   523           Parent::nextIn(edge);
   524         }
   525       }
   526     }
   527 
   528     void nextIn(Edge& edge) const {
   529       if (Parent::aNode(Parent::target(edge))) {
   530         edge = INVALID;
   531       } else {
   532         Parent::nextIn(edge);
   533         if (edge != INVALID && (*bnode_matching)[Parent::bNode(edge)] == edge) {
   534           Parent::nextIn(edge);
   535         }
   536       }
   537     } 
   538 
   539   private:
   540     ANodeMatchingMap* anode_matching;
   541     BNodeMatchingMap* bnode_matching;
   542   };
   543 
   544 
   545   /// \ingroup graph_adaptors
   546   ///
   547   /// \brief Bipartite graph adaptor to implement matching algorithms.
   548   ///
   549   /// Bipartite graph adaptor to implement matchings. It implements
   550   /// the residual graph of the matching.
   551   template <typename _BpUGraph, 
   552             typename _ANMatchingMap, typename _BNMatchingMap>
   553   class MatchingBpUGraphAdaptor 
   554     : public BpUGraphAdaptorExtender<
   555     MatchingBpUGraphAdaptorBase<_BpUGraph, _ANMatchingMap, _BNMatchingMap> > 
   556   { 
   557   public:
   558 
   559     typedef _BpUGraph BpUGraph;
   560     typedef _BpUGraph Graph;
   561     typedef _ANMatchingMap ANodeMatchingMap;
   562     typedef _BNMatchingMap BNodeMatchingMap;
   563     typedef BpUGraphAdaptorExtender<
   564       MatchingBpUGraphAdaptorBase<BpUGraph, 
   565                                   ANodeMatchingMap, BNodeMatchingMap> > 
   566     Parent;
   567 
   568   protected:
   569     MatchingBpUGraphAdaptor() : Parent() {}
   570 
   571   public:
   572 
   573     MatchingBpUGraphAdaptor(const Graph& _graph, 
   574                             ANodeMatchingMap& _anode_matching,
   575                             BNodeMatchingMap& _bnode_matching) {
   576       setGraph(_graph);
   577       setANodeMatchingMap(_anode_matching);
   578       setBNodeMatchingMap(_bnode_matching);
   579     }
   580 
   581   };
   582 
   583 }
   584 
   585 #endif