#include <lemon/core.h>

     ///

     /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt

             s_root = false;

             s_root = true;

     ///@}

     friend class MinCutNodeIt;

     /// Iterate on the nodes of a minimum cut

     /// This iterator class lists the nodes of a minimum cut found by

     /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class,

     /// and call its \ref GomoryHuTree::run() "run()" method.

     ///

     /// This example counts the nodes in the minimum cut separating \c s from

     /// \c t.

     /// \code

     /// GomoruHuTree<Graph> gom(g, capacities);

     /// gom.run();

     /// int sum=0;

     /// for(GomoruHuTree<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum;

     /// \endcode

     class MinCutNodeIt

     {

       bool _side;

       typename Graph::NodeIt _node_it;

       typename Graph::template NodeMap<bool> _cut;

     public:

       /// Constructor

       /// Constructor

       ///

       MinCutNodeIt(GomoryHuTree const &gomory,

                    ///< The GomoryHuTree class. You must call its

                    ///  run() method

                    ///  before initializing this iterator

                    const Node& s, ///< Base node

                    const Node& t,

                    ///< The node you want to separate from Node s.

                    bool side=true

                    ///< If it is \c true (default) then the iterator lists

                    ///  the nodes of the component containing \c s,

                    ///  otherwise it lists the other component.

                    /// \note As the minimum cut is not always unique,

                    /// \code

                    /// MinCutNodeIt(gomory, s, t, true);

                    /// \endcode

                    /// and

                    /// \code

                    /// MinCutNodeIt(gomory, t, s, false);

                    /// \endcode

                    /// does not necessarily give the same set of nodes.

                    /// However it is ensured that

                    /// \code

                    /// MinCutNodeIt(gomory, s, t, true);

                    /// \endcode

                    /// and

                    /// \code

                    /// MinCutNodeIt(gomory, s, t, false);

                    /// \endcode

                    /// together list each node exactly once.

                    )

         : _side(side), _cut(gomory._graph)

       {

         gomory.minCutMap(s,t,_cut);

         for(_node_it=typename Graph::NodeIt(gomory._graph);

             _node_it!=INVALID && _cut[_node_it]!=_side;

             ++_node_it) {}

       }

       /// Conversion to Node

       /// Conversion to Node

       ///

       operator typename Graph::Node() const

       {

         return _node_it;

       }

       bool operator==(Invalid) { return _node_it==INVALID; }

       bool operator!=(Invalid) { return _node_it!=INVALID; }

       /// Next node

       /// Next node

       ///

       MinCutNodeIt &operator++()

       {

         for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}

         return *this;

       }

       /// Postfix incrementation

       /// Postfix incrementation

       ///

       /// \warning This incrementation

       /// returns a \c Node, not a \ref MinCutNodeIt, as one may

       /// expect.

       typename Graph::Node operator++(int)

       {

         typename Graph::Node n=*this;

         ++(*this);

         return n;

       }

     };

     friend class MinCutEdgeIt;

     /// Iterate on the edges of a minimum cut

     /// This iterator class lists the edges of a minimum cut found by

     /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class,

     /// and call its \ref GomoryHuTree::run() "run()" method.

     ///

     /// This example computes the value of the minimum cut separating \c s from

     /// \c t.

     /// \code

     /// GomoruHuTree<Graph> gom(g, capacities);

     /// gom.run();

     /// int value=0;

     /// for(GomoruHuTree<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e)

     ///   value+=capacities[e];

     /// \endcode

     /// the result will be the same as it is returned by

     /// \ref GomoryHuTree::minCostValue() "gom.minCostValue(s,t)"

     class MinCutEdgeIt

     {

       bool _side;

       const Graph &_graph;

       typename Graph::NodeIt _node_it;

       typename Graph::OutArcIt _arc_it;

       typename Graph::template NodeMap<bool> _cut;

       void step()

       {

         ++_arc_it;

         while(_node_it!=INVALID && _arc_it==INVALID)

           {

             for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}

             if(_node_it!=INVALID)

               _arc_it=typename Graph::OutArcIt(_graph,_node_it);

           }

       }

     public:

       MinCutEdgeIt(GomoryHuTree const &gomory,

                    ///< The GomoryHuTree class. You must call its

                    ///  run() method

                    ///  before initializing this iterator

                    const Node& s,  ///< Base node

                    const Node& t,

                    ///< The node you want to separate from Node s.

                    bool side=true

                    ///< If it is \c true (default) then the listed arcs

                    ///  will be oriented from the

                    ///  the nodes of the component containing \c s,

                    ///  otherwise they will be oriented in the opposite

                    ///  direction.

                    )

         : _graph(gomory._graph), _cut(_graph)

       {

         gomory.minCutMap(s,t,_cut);

         if(!side)

           for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)

             _cut[n]=!_cut[n];

         for(_node_it=typename Graph::NodeIt(_graph);

             _node_it!=INVALID && !_cut[_node_it];

             ++_node_it) {}

         _arc_it = _node_it!=INVALID ?

           typename Graph::OutArcIt(_graph,_node_it) : INVALID;

         while(_node_it!=INVALID && _arc_it == INVALID)

           {

             for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}

             if(_node_it!=INVALID)

               _arc_it= typename Graph::OutArcIt(_graph,_node_it);

           }

         while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();

       }

       /// Conversion to Arc

       /// Conversion to Arc

       ///

       operator typename Graph::Arc() const

       {

         return _arc_it;

       }

       /// Conversion to Edge

       /// Conversion to Edge

       ///

       operator typename Graph::Edge() const

       {

         return _arc_it;

       }

       bool operator==(Invalid) { return _node_it==INVALID; }

       bool operator!=(Invalid) { return _node_it!=INVALID; }

       /// Next edge

       /// Next edge

       ///

       MinCutEdgeIt &operator++()

       {

         step();

         while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();

         return *this;

       }

       /// Postfix incrementation

       /// Postfix incrementation

       ///

       /// \warning This incrementation

       /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may

       /// expect.

       typename Graph::Arc operator++(int)

       {

         typename Graph::Arc e=*this;

         ++(*this);

         return e;

       }

     };