lemon/gomory_hu_tree.h
changeset 544 ccd2d3a3001e
parent 543 924887566bf2
equal deleted inserted replaced
0:565908d41ae1 1:3b8e931255d6
    19 #ifndef LEMON_GOMORY_HU_TREE_H
    19 #ifndef LEMON_GOMORY_HU_TREE_H
    20 #define LEMON_GOMORY_HU_TREE_H
    20 #define LEMON_GOMORY_HU_TREE_H
    21 
    21 
    22 #include <limits>
    22 #include <limits>
    23 
    23 
       
    24 #include <lemon/core.h>
    24 #include <lemon/preflow.h>
    25 #include <lemon/preflow.h>
    25 #include <lemon/concept_check.h>
    26 #include <lemon/concept_check.h>
    26 #include <lemon/concepts/maps.h>
    27 #include <lemon/concepts/maps.h>
    27 
    28 
    28 /// \ingroup min_cut
    29 /// \ingroup min_cut
    33 
    34 
    34   /// \ingroup min_cut
    35   /// \ingroup min_cut
    35   ///
    36   ///
    36   /// \brief Gomory-Hu cut tree algorithm
    37   /// \brief Gomory-Hu cut tree algorithm
    37   ///
    38   ///
    38   /// The Gomory-Hu tree is a tree on the nodeset of the digraph, but it
    39   /// The Gomory-Hu tree is a tree on the node set of the graph, but it
    39   /// may contain arcs which are not in the original digraph. It helps
    40   /// may contain edges which are not in the original digraph. It has the
    40   /// to calculate the minimum cut between all pairs of nodes, because
    41   /// property that the minimum capacity edge of the path between two nodes 
    41   /// the minimum capacity arc on the tree path between two nodes has
    42   /// in this tree has the same weight as the minimum cut in the digraph
    42   /// the same weight as the minimum cut in the digraph between these
    43   /// between these nodes. Moreover the components obtained by removing
    43   /// nodes. Moreover this arc separates the nodes to two parts which
    44   /// this edge from the tree determine the corresponding minimum cut.
    44   /// determine this minimum cut.
    45   ///
       
    46   /// Therefore once this tree is computed, the minimum cut between any pair
       
    47   /// of nodes can easily be obtained.
    45   /// 
    48   /// 
    46   /// The algorithm calculates \e n-1 distinict minimum cuts with
    49   /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
    47   /// preflow algorithm, therefore the algorithm has
    50   /// the \ref Preflow algorithm), therefore the algorithm has
    48   /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
    51   /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
    49   /// rooted Gomory-Hu tree, the structure of the tree and the weights
    52   /// rooted Gomory-Hu tree, its structure and the weights can be obtained
    50   /// can be obtained with \c predNode() and \c predValue()
    53   /// by \c predNode(), \c predValue() and \c rootDist().
    51   /// functions. The \c minCutValue() and \c minCutMap() calculates
    54   /// 
       
    55   /// The members \c minCutMap() and \c minCutValue() calculate
    52   /// the minimum cut and the minimum cut value between any two node
    56   /// the minimum cut and the minimum cut value between any two node
    53   /// in the digraph.
    57   /// in the digraph. You can also list (iterate on) the nodes and the
    54   template <typename _Graph, 
    58   /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
    55 	    typename _Capacity = typename _Graph::template EdgeMap<int> >
    59   ///
       
    60   /// \tparam GR The undirected graph data structure the algorithm will run on
       
    61   /// \tparam CAP type of the EdgeMap describing the Edge capacities.
       
    62   /// it is typename GR::template EdgeMap<int> by default.
       
    63   template <typename GR,
       
    64 	    typename CAP = typename GR::template EdgeMap<int>
       
    65             >
    56   class GomoryHuTree {
    66   class GomoryHuTree {
    57   public:
    67   public:
    58 
    68 
    59     /// The graph type
    69     /// The graph type
    60     typedef _Graph Graph;
    70     typedef GR Graph;
    61     /// The capacity on edges
    71     /// The type if the edge capacity map
    62     typedef _Capacity Capacity;
    72     typedef CAP Capacity;
    63     /// The value type of capacities
    73     /// The value type of capacities
    64     typedef typename Capacity::Value Value;
    74     typedef typename Capacity::Value Value;
    65     
    75     
    66   private:
    76   private:
    67 
    77 
   102   public:
   112   public:
   103 
   113 
   104     /// \brief Constructor
   114     /// \brief Constructor
   105     ///
   115     ///
   106     /// Constructor
   116     /// Constructor
   107     /// \param graph The graph type.
   117     /// \param graph The graph the algorithm will run on.
   108     /// \param capacity The capacity map.
   118     /// \param capacity The capacity map.
   109     GomoryHuTree(const Graph& graph, const Capacity& capacity) 
   119     GomoryHuTree(const Graph& graph, const Capacity& capacity) 
   110       : _graph(graph), _capacity(capacity),
   120       : _graph(graph), _capacity(capacity),
   111 	_pred(0), _weight(0), _order(0) 
   121 	_pred(0), _weight(0), _order(0) 
   112     {
   122     {
   119     /// Destructor
   129     /// Destructor
   120     ~GomoryHuTree() {
   130     ~GomoryHuTree() {
   121       destroyStructures();
   131       destroyStructures();
   122     }
   132     }
   123 
   133 
   124     /// \brief Initializes the internal data structures.
   134     // \brief Initialize the internal data structures.
   125     ///
   135     //
   126     /// Initializes the internal data structures.
   136     // This function initializes the internal data structures.
   127     ///
   137     //
   128     void init() {
   138     void init() {
   129       createStructures();
   139       createStructures();
   130 
   140 
   131       _root = NodeIt(_graph);
   141       _root = NodeIt(_graph);
   132       for (NodeIt n(_graph); n != INVALID; ++n) {
   142       for (NodeIt n(_graph); n != INVALID; ++n) {
   136       _pred->set(_root, INVALID);
   146       _pred->set(_root, INVALID);
   137       _weight->set(_root, std::numeric_limits<Value>::max()); 
   147       _weight->set(_root, std::numeric_limits<Value>::max()); 
   138     }
   148     }
   139 
   149 
   140 
   150 
   141     /// \brief Starts the algorithm
   151     // \brief Start the algorithm
   142     ///
   152     //
   143     /// Starts the algorithm.
   153     // This function starts the algorithm.
       
   154     //
       
   155     // \pre \ref init() must be called before using this function.
       
   156     //
   144     void start() {
   157     void start() {
   145       Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
   158       Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
   146 
   159 
   147       for (NodeIt n(_graph); n != INVALID; ++n) {
   160       for (NodeIt n(_graph); n != INVALID; ++n) {
   148 	if (n == _root) continue;
   161 	if (n == _root) continue;
   183 	  st.pop_back();
   196 	  st.pop_back();
   184 	}
   197 	}
   185       }
   198       }
   186     }
   199     }
   187 
   200 
   188     /// \brief Runs the Gomory-Hu algorithm.  
   201     ///\name Execution Control
   189     ///
   202  
   190     /// Runs the Gomory-Hu algorithm.
   203     ///@{
   191     /// \note gh.run() is just a shortcut of the following code.
   204 
   192     /// \code
   205     /// \brief Run the Gomory-Hu algorithm.
   193     ///   ght.init();
   206     ///
   194     ///   ght.start();
   207     /// This function runs the Gomory-Hu algorithm.
   195     /// \endcode
       
   196     void run() {
   208     void run() {
   197       init();
   209       init();
   198       start();
   210       start();
   199     }
   211     }
   200 
   212     
   201     /// \brief Returns the predecessor node in the Gomory-Hu tree.
   213     /// @}
   202     ///
   214 
   203     /// Returns the predecessor node in the Gomory-Hu tree. If the node is
   215     ///\name Query Functions
       
   216     ///The results of the algorithm can be obtained using these
       
   217     ///functions.\n
       
   218     ///The \ref run() "run()" should be called before using them.\n
       
   219     ///See also MinCutNodeIt and MinCutEdgeIt
       
   220 
       
   221     ///@{
       
   222 
       
   223     /// \brief Return the predecessor node in the Gomory-Hu tree.
       
   224     ///
       
   225     /// This function returns the predecessor node in the Gomory-Hu tree.
       
   226     /// If the node is
   204     /// the root of the Gomory-Hu tree, then it returns \c INVALID.
   227     /// the root of the Gomory-Hu tree, then it returns \c INVALID.
   205     Node predNode(const Node& node) {
   228     Node predNode(const Node& node) {
   206       return (*_pred)[node];
   229       return (*_pred)[node];
   207     }
   230     }
   208 
   231 
   209     /// \brief Returns the weight of the predecessor arc in the
   232     /// \brief Return the distance from the root node in the Gomory-Hu tree.
       
   233     ///
       
   234     /// This function returns the distance of \c node from the root node
       
   235     /// in the Gomory-Hu tree.
       
   236     int rootDist(const Node& node) {
       
   237       return (*_order)[node];
       
   238     }
       
   239 
       
   240     /// \brief Return the weight of the predecessor edge in the
   210     /// Gomory-Hu tree.
   241     /// Gomory-Hu tree.
   211     ///
   242     ///
   212     /// Returns the weight of the predecessor arc in the Gomory-Hu
   243     /// This function returns the weight of the predecessor edge in the
   213     /// tree.  If the node is the root of the Gomory-Hu tree, the
   244     /// Gomory-Hu tree.  If the node is the root, the result is undefined.
   214     /// result is undefined.
       
   215     Value predValue(const Node& node) {
   245     Value predValue(const Node& node) {
   216       return (*_weight)[node];
   246       return (*_weight)[node];
   217     }
   247     }
   218 
   248 
   219     /// \brief Returns the minimum cut value between two nodes
   249     /// \brief Return the minimum cut value between two nodes
   220     ///
   250     ///
   221     /// Returns the minimum cut value between two nodes. The
   251     /// This function returns the minimum cut value between two nodes. The
   222     /// algorithm finds the nearest common ancestor in the Gomory-Hu
   252     /// algorithm finds the nearest common ancestor in the Gomory-Hu
   223     /// tree and calculates the minimum weight arc on the paths to
   253     /// tree and calculates the minimum weight arc on the paths to
   224     /// the ancestor.
   254     /// the ancestor.
   225     Value minCutValue(const Node& s, const Node& t) const {
   255     Value minCutValue(const Node& s, const Node& t) const {
   226       Node sn = s, tn = t;
   256       Node sn = s, tn = t;
   227       Value value = std::numeric_limits<Value>::max();
   257       Value value = std::numeric_limits<Value>::max();
   228       
   258       
   229       while (sn != tn) {
   259       while (sn != tn) {
   230 	if ((*_order)[sn] < (*_order)[tn]) {
   260 	if ((*_order)[sn] < (*_order)[tn]) {
   231 	  if ((*_weight)[tn] < value) value = (*_weight)[tn];
   261 	  if ((*_weight)[tn] <= value) value = (*_weight)[tn];
   232 	  tn = (*_pred)[tn];
   262 	  tn = (*_pred)[tn];
   233 	} else {
   263 	} else {
   234 	  if ((*_weight)[sn] < value) value = (*_weight)[sn];
   264 	  if ((*_weight)[sn] <= value) value = (*_weight)[sn];
   235 	  sn = (*_pred)[sn];
   265 	  sn = (*_pred)[sn];
   236 	}
   266 	}
   237       }
   267       }
   238       return value;
   268       return value;
   239     }
   269     }
   240 
   270 
   241     /// \brief Returns the minimum cut between two nodes
   271     /// \brief Return the minimum cut between two nodes
   242     ///
   272     ///
   243     /// Returns the minimum cut value between two nodes. The
   273     /// This function returns the minimum cut between the nodes \c s and \c t
   244     /// algorithm finds the nearest common ancestor in the Gomory-Hu
   274     /// the \r cutMap parameter by setting the nodes in the component of
   245     /// tree and calculates the minimum weight arc on the paths to
   275     /// \c \s to true and the other nodes to false.
   246     /// the ancestor. Then it sets all nodes to the cut determined by
   276     ///
   247     /// this arc. The \c cutMap should be \ref concepts::ReadWriteMap
   277     /// The \c cutMap should be \ref concepts::ReadWriteMap
   248     /// "ReadWriteMap".
   278     /// "ReadWriteMap".
       
   279     ///
       
   280     /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt
   249     template <typename CutMap>
   281     template <typename CutMap>
   250     Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const {
   282     Value minCutMap(const Node& s, ///< Base node
       
   283                     const Node& t,
       
   284                     ///< The node you want to separate from Node s.
       
   285                     CutMap& cutMap
       
   286                     ///< The cut will be return in this map.
       
   287                     /// It must be a \c bool \ref concepts::ReadWriteMap
       
   288                     /// "ReadWriteMap" on the graph nodes.
       
   289                     ) const {
   251       Node sn = s, tn = t;
   290       Node sn = s, tn = t;
   252 
   291       bool s_root=false;
   253       Node rn = INVALID;
   292       Node rn = INVALID;
   254       Value value = std::numeric_limits<Value>::max();
   293       Value value = std::numeric_limits<Value>::max();
   255       
   294       
   256       while (sn != tn) {
   295       while (sn != tn) {
   257 	if ((*_order)[sn] < (*_order)[tn]) {
   296 	if ((*_order)[sn] < (*_order)[tn]) {
   258 	  if ((*_weight)[tn] < value) {
   297 	  if ((*_weight)[tn] <= value) {
   259 	    rn = tn;
   298 	    rn = tn;
       
   299             s_root = false;
   260 	    value = (*_weight)[tn];
   300 	    value = (*_weight)[tn];
   261 	  }
   301 	  }
   262 	  tn = (*_pred)[tn];
   302 	  tn = (*_pred)[tn];
   263 	} else {
   303 	} else {
   264 	  if ((*_weight)[sn] < value) {
   304 	  if ((*_weight)[sn] <= value) {
   265 	    rn = sn;
   305 	    rn = sn;
       
   306             s_root = true;
   266 	    value = (*_weight)[sn];
   307 	    value = (*_weight)[sn];
   267 	  }
   308 	  }
   268 	  sn = (*_pred)[sn];
   309 	  sn = (*_pred)[sn];
   269 	}
   310 	}
   270       }
   311       }
   271 
   312 
   272       typename Graph::template NodeMap<bool> reached(_graph, false);
   313       typename Graph::template NodeMap<bool> reached(_graph, false);
   273       reached.set(_root, true);
   314       reached.set(_root, true);
   274       cutMap.set(_root, false);
   315       cutMap.set(_root, !s_root);
   275       reached.set(rn, true);
   316       reached.set(rn, true);
   276       cutMap.set(rn, true);
   317       cutMap.set(rn, s_root);
   277 
   318 
       
   319       std::vector<Node> st;
   278       for (NodeIt n(_graph); n != INVALID; ++n) {
   320       for (NodeIt n(_graph); n != INVALID; ++n) {
   279 	std::vector<Node> st;
   321 	st.clear();
   280 	Node nn = n;
   322         Node nn = n;
   281 	while (!reached[nn]) {
   323 	while (!reached[nn]) {
   282 	  st.push_back(nn);
   324 	  st.push_back(nn);
   283 	  nn = (*_pred)[nn];
   325 	  nn = (*_pred)[nn];
   284 	}
   326 	}
   285 	while (!st.empty()) {
   327 	while (!st.empty()) {
   289       }
   331       }
   290       
   332       
   291       return value;
   333       return value;
   292     }
   334     }
   293 
   335 
       
   336     ///@}
       
   337 
       
   338     friend class MinCutNodeIt;
       
   339 
       
   340     /// Iterate on the nodes of a minimum cut
       
   341     
       
   342     /// This iterator class lists the nodes of a minimum cut found by
       
   343     /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class,
       
   344     /// and call its \ref GomoryHuTree::run() "run()" method.
       
   345     ///
       
   346     /// This example counts the nodes in the minimum cut separating \c s from
       
   347     /// \c t.
       
   348     /// \code
       
   349     /// GomoruHuTree<Graph> gom(g, capacities);
       
   350     /// gom.run();
       
   351     /// int sum=0;
       
   352     /// for(GomoruHuTree<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum;
       
   353     /// \endcode
       
   354     class MinCutNodeIt
       
   355     {
       
   356       bool _side;
       
   357       typename Graph::NodeIt _node_it;
       
   358       typename Graph::template NodeMap<bool> _cut;
       
   359     public:
       
   360       /// Constructor
       
   361 
       
   362       /// Constructor
       
   363       ///
       
   364       MinCutNodeIt(GomoryHuTree const &gomory,
       
   365                    ///< The GomoryHuTree class. You must call its
       
   366                    ///  run() method
       
   367                    ///  before initializing this iterator
       
   368                    const Node& s, ///< Base node
       
   369                    const Node& t,
       
   370                    ///< The node you want to separate from Node s.
       
   371                    bool side=true
       
   372                    ///< If it is \c true (default) then the iterator lists
       
   373                    ///  the nodes of the component containing \c s,
       
   374                    ///  otherwise it lists the other component.
       
   375                    /// \note As the minimum cut is not always unique,
       
   376                    /// \code
       
   377                    /// MinCutNodeIt(gomory, s, t, true);
       
   378                    /// \endcode
       
   379                    /// and
       
   380                    /// \code
       
   381                    /// MinCutNodeIt(gomory, t, s, false);
       
   382                    /// \endcode
       
   383                    /// does not necessarily give the same set of nodes.
       
   384                    /// However it is ensured that
       
   385                    /// \code
       
   386                    /// MinCutNodeIt(gomory, s, t, true);
       
   387                    /// \endcode
       
   388                    /// and
       
   389                    /// \code
       
   390                    /// MinCutNodeIt(gomory, s, t, false);
       
   391                    /// \endcode
       
   392                    /// together list each node exactly once.
       
   393                    )
       
   394         : _side(side), _cut(gomory._graph)
       
   395       {
       
   396         gomory.minCutMap(s,t,_cut);
       
   397         for(_node_it=typename Graph::NodeIt(gomory._graph);
       
   398             _node_it!=INVALID && _cut[_node_it]!=_side;
       
   399             ++_node_it) {}
       
   400       }
       
   401       /// Conversion to Node
       
   402 
       
   403       /// Conversion to Node
       
   404       ///
       
   405       operator typename Graph::Node() const
       
   406       {
       
   407         return _node_it;
       
   408       }
       
   409       bool operator==(Invalid) { return _node_it==INVALID; }
       
   410       bool operator!=(Invalid) { return _node_it!=INVALID; }
       
   411       /// Next node
       
   412 
       
   413       /// Next node
       
   414       ///
       
   415       MinCutNodeIt &operator++()
       
   416       {
       
   417         for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
       
   418         return *this;
       
   419       }
       
   420       /// Postfix incrementation
       
   421 
       
   422       /// Postfix incrementation
       
   423       ///
       
   424       /// \warning This incrementation
       
   425       /// returns a \c Node, not a \ref MinCutNodeIt, as one may
       
   426       /// expect.
       
   427       typename Graph::Node operator++(int)
       
   428       {
       
   429         typename Graph::Node n=*this;
       
   430         ++(*this);
       
   431         return n;
       
   432       }
       
   433     };
       
   434     
       
   435     friend class MinCutEdgeIt;
       
   436     
       
   437     /// Iterate on the edges of a minimum cut
       
   438     
       
   439     /// This iterator class lists the edges of a minimum cut found by
       
   440     /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class,
       
   441     /// and call its \ref GomoryHuTree::run() "run()" method.
       
   442     ///
       
   443     /// This example computes the value of the minimum cut separating \c s from
       
   444     /// \c t.
       
   445     /// \code
       
   446     /// GomoruHuTree<Graph> gom(g, capacities);
       
   447     /// gom.run();
       
   448     /// int value=0;
       
   449     /// for(GomoruHuTree<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e)
       
   450     ///   value+=capacities[e];
       
   451     /// \endcode
       
   452     /// the result will be the same as it is returned by
       
   453     /// \ref GomoryHuTree::minCostValue() "gom.minCostValue(s,t)"
       
   454     class MinCutEdgeIt
       
   455     {
       
   456       bool _side;
       
   457       const Graph &_graph;
       
   458       typename Graph::NodeIt _node_it;
       
   459       typename Graph::OutArcIt _arc_it;
       
   460       typename Graph::template NodeMap<bool> _cut;
       
   461       void step()
       
   462       {
       
   463         ++_arc_it;
       
   464         while(_node_it!=INVALID && _arc_it==INVALID)
       
   465           {
       
   466             for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
       
   467             if(_node_it!=INVALID)
       
   468               _arc_it=typename Graph::OutArcIt(_graph,_node_it);
       
   469           }
       
   470       }
       
   471       
       
   472     public:
       
   473       MinCutEdgeIt(GomoryHuTree const &gomory,
       
   474                    ///< The GomoryHuTree class. You must call its
       
   475                    ///  run() method
       
   476                    ///  before initializing this iterator
       
   477                    const Node& s,  ///< Base node
       
   478                    const Node& t,
       
   479                    ///< The node you want to separate from Node s.
       
   480                    bool side=true
       
   481                    ///< If it is \c true (default) then the listed arcs
       
   482                    ///  will be oriented from the
       
   483                    ///  the nodes of the component containing \c s,
       
   484                    ///  otherwise they will be oriented in the opposite
       
   485                    ///  direction.
       
   486                    )
       
   487         : _graph(gomory._graph), _cut(_graph)
       
   488       {
       
   489         gomory.minCutMap(s,t,_cut);
       
   490         if(!side)
       
   491           for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
       
   492             _cut[n]=!_cut[n];
       
   493 
       
   494         for(_node_it=typename Graph::NodeIt(_graph);
       
   495             _node_it!=INVALID && !_cut[_node_it];
       
   496             ++_node_it) {}
       
   497         _arc_it = _node_it!=INVALID ?
       
   498           typename Graph::OutArcIt(_graph,_node_it) : INVALID;
       
   499         while(_node_it!=INVALID && _arc_it == INVALID)
       
   500           {
       
   501             for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}
       
   502             if(_node_it!=INVALID)
       
   503               _arc_it= typename Graph::OutArcIt(_graph,_node_it);
       
   504           }
       
   505         while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
       
   506       }
       
   507       /// Conversion to Arc
       
   508 
       
   509       /// Conversion to Arc
       
   510       ///
       
   511       operator typename Graph::Arc() const
       
   512       {
       
   513         return _arc_it;
       
   514       }
       
   515       /// Conversion to Edge
       
   516 
       
   517       /// Conversion to Edge
       
   518       ///
       
   519       operator typename Graph::Edge() const
       
   520       {
       
   521         return _arc_it;
       
   522       }
       
   523       bool operator==(Invalid) { return _node_it==INVALID; }
       
   524       bool operator!=(Invalid) { return _node_it!=INVALID; }
       
   525       /// Next edge
       
   526 
       
   527       /// Next edge
       
   528       ///
       
   529       MinCutEdgeIt &operator++()
       
   530       {
       
   531         step();
       
   532         while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
       
   533         return *this;
       
   534       }
       
   535       /// Postfix incrementation
       
   536       
       
   537       /// Postfix incrementation
       
   538       ///
       
   539       /// \warning This incrementation
       
   540       /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may
       
   541       /// expect.
       
   542       typename Graph::Arc operator++(int)
       
   543       {
       
   544         typename Graph::Arc e=*this;
       
   545         ++(*this);
       
   546         return e;
       
   547       }
       
   548     };
       
   549 
   294   };
   550   };
   295 
   551 
   296 }
   552 }
   297 
   553 
   298 #endif
   554 #endif