alpar@761: /* -*- mode: C++; indent-tabs-mode: nil; -*-
tapolcai@531:  *
alpar@761:  * This file is a part of LEMON, a generic C++ optimization library.
tapolcai@531:  *
alpar@761:  * Copyright (C) 2003-2011
tapolcai@531:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
tapolcai@531:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
tapolcai@531:  *
tapolcai@531:  * Permission to use, modify and distribute this software is granted
tapolcai@531:  * provided that this copyright notice appears in all copies. For
tapolcai@531:  * precise terms see the accompanying LICENSE file.
tapolcai@531:  *
tapolcai@531:  * This software is provided "AS IS" with no warranty of any kind,
tapolcai@531:  * express or implied, and with no claim as to its suitability for any
tapolcai@531:  * purpose.
tapolcai@531:  *
tapolcai@531:  */
tapolcai@531: 
tapolcai@531: #ifndef LEMON_GOMORY_HU_TREE_H
tapolcai@531: #define LEMON_GOMORY_HU_TREE_H
tapolcai@531: 
tapolcai@531: #include <limits>
tapolcai@531: 
alpar@532: #include <lemon/core.h>
tapolcai@531: #include <lemon/preflow.h>
tapolcai@531: #include <lemon/concept_check.h>
tapolcai@531: #include <lemon/concepts/maps.h>
tapolcai@531: 
tapolcai@531: /// \ingroup min_cut
alpar@761: /// \file
tapolcai@531: /// \brief Gomory-Hu cut tree in graphs.
tapolcai@531: 
tapolcai@531: namespace lemon {
tapolcai@531: 
tapolcai@531:   /// \ingroup min_cut
tapolcai@531:   ///
tapolcai@531:   /// \brief Gomory-Hu cut tree algorithm
tapolcai@531:   ///
kpeter@534:   /// The Gomory-Hu tree is a tree on the node set of a given graph, but it
kpeter@534:   /// may contain edges which are not in the original graph. It has the
alpar@761:   /// property that the minimum capacity edge of the path between two nodes
kpeter@534:   /// in this tree has the same weight as the minimum cut in the graph
alpar@532:   /// between these nodes. Moreover the components obtained by removing
alpar@532:   /// this edge from the tree determine the corresponding minimum cut.
alpar@532:   /// Therefore once this tree is computed, the minimum cut between any pair
alpar@532:   /// of nodes can easily be obtained.
alpar@761:   ///
alpar@532:   /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
kpeter@588:   /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
kpeter@588:   /// time complexity. It calculates a rooted Gomory-Hu tree.
kpeter@588:   /// The structure of the tree and the edge weights can be
kpeter@588:   /// obtained using \c predNode(), \c predValue() and \c rootDist().
kpeter@588:   /// The functions \c minCutMap() and \c minCutValue() calculate
kpeter@534:   /// the minimum cut and the minimum cut value between any two nodes
kpeter@534:   /// in the graph. You can also list (iterate on) the nodes and the
kpeter@534:   /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
alpar@532:   ///
kpeter@534:   /// \tparam GR The type of the undirected graph the algorithm runs on.
kpeter@588:   /// \tparam CAP The type of the edge map containing the capacities.
kpeter@588:   /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
kpeter@534: #ifdef DOXYGEN
alpar@532:   template <typename GR,
alpar@761:             typename CAP>
kpeter@534: #else
kpeter@534:   template <typename GR,
alpar@761:             typename CAP = typename GR::template EdgeMap<int> >
kpeter@534: #endif
alpar@533:   class GomoryHu {
tapolcai@531:   public:
tapolcai@531: 
kpeter@588:     /// The graph type of the algorithm
alpar@532:     typedef GR Graph;
kpeter@588:     /// The capacity map type of the algorithm
alpar@532:     typedef CAP Capacity;
tapolcai@531:     /// The value type of capacities
tapolcai@531:     typedef typename Capacity::Value Value;
alpar@761: 
tapolcai@531:   private:
tapolcai@531: 
tapolcai@531:     TEMPLATE_GRAPH_TYPEDEFS(Graph);
tapolcai@531: 
tapolcai@531:     const Graph& _graph;
tapolcai@531:     const Capacity& _capacity;
tapolcai@531: 
tapolcai@531:     Node _root;
tapolcai@531:     typename Graph::template NodeMap<Node>* _pred;
tapolcai@531:     typename Graph::template NodeMap<Value>* _weight;
tapolcai@531:     typename Graph::template NodeMap<int>* _order;
tapolcai@531: 
tapolcai@531:     void createStructures() {
tapolcai@531:       if (!_pred) {
alpar@761:         _pred = new typename Graph::template NodeMap<Node>(_graph);
tapolcai@531:       }
tapolcai@531:       if (!_weight) {
alpar@761:         _weight = new typename Graph::template NodeMap<Value>(_graph);
tapolcai@531:       }
tapolcai@531:       if (!_order) {
alpar@761:         _order = new typename Graph::template NodeMap<int>(_graph);
tapolcai@531:       }
tapolcai@531:     }
tapolcai@531: 
tapolcai@531:     void destroyStructures() {
tapolcai@531:       if (_pred) {
alpar@761:         delete _pred;
tapolcai@531:       }
tapolcai@531:       if (_weight) {
alpar@761:         delete _weight;
tapolcai@531:       }
tapolcai@531:       if (_order) {
alpar@761:         delete _order;
tapolcai@531:       }
tapolcai@531:     }
alpar@761: 
tapolcai@531:   public:
tapolcai@531: 
tapolcai@531:     /// \brief Constructor
tapolcai@531:     ///
kpeter@588:     /// Constructor.
kpeter@534:     /// \param graph The undirected graph the algorithm runs on.
kpeter@534:     /// \param capacity The edge capacity map.
alpar@761:     GomoryHu(const Graph& graph, const Capacity& capacity)
tapolcai@531:       : _graph(graph), _capacity(capacity),
alpar@761:         _pred(0), _weight(0), _order(0)
tapolcai@531:     {
tapolcai@531:       checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
tapolcai@531:     }
tapolcai@531: 
tapolcai@531: 
tapolcai@531:     /// \brief Destructor
tapolcai@531:     ///
kpeter@588:     /// Destructor.
alpar@533:     ~GomoryHu() {
tapolcai@531:       destroyStructures();
tapolcai@531:     }
tapolcai@531: 
kpeter@534:   private:
alpar@761: 
kpeter@534:     // Initialize the internal data structures
tapolcai@531:     void init() {
tapolcai@531:       createStructures();
tapolcai@531: 
tapolcai@531:       _root = NodeIt(_graph);
tapolcai@531:       for (NodeIt n(_graph); n != INVALID; ++n) {
kpeter@573:         (*_pred)[n] = _root;
kpeter@573:         (*_order)[n] = -1;
tapolcai@531:       }
kpeter@573:       (*_pred)[_root] = INVALID;
alpar@761:       (*_weight)[_root] = std::numeric_limits<Value>::max();
tapolcai@531:     }
tapolcai@531: 
tapolcai@531: 
kpeter@534:     // Start the algorithm
tapolcai@531:     void start() {
tapolcai@531:       Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
tapolcai@531: 
tapolcai@531:       for (NodeIt n(_graph); n != INVALID; ++n) {
alpar@761:         if (n == _root) continue;
tapolcai@531: 
alpar@761:         Node pn = (*_pred)[n];
alpar@761:         fa.source(n);
alpar@761:         fa.target(pn);
tapolcai@531: 
alpar@761:         fa.runMinCut();
tapolcai@531: 
alpar@761:         (*_weight)[n] = fa.flowValue();
tapolcai@531: 
alpar@761:         for (NodeIt nn(_graph); nn != INVALID; ++nn) {
alpar@761:           if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
alpar@761:             (*_pred)[nn] = n;
alpar@761:           }
alpar@761:         }
alpar@761:         if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
alpar@761:           (*_pred)[n] = (*_pred)[pn];
alpar@761:           (*_pred)[pn] = n;
alpar@761:           (*_weight)[n] = (*_weight)[pn];
alpar@761:           (*_weight)[pn] = fa.flowValue();
alpar@761:         }
tapolcai@531:       }
tapolcai@531: 
kpeter@573:       (*_order)[_root] = 0;
tapolcai@531:       int index = 1;
tapolcai@531: 
tapolcai@531:       for (NodeIt n(_graph); n != INVALID; ++n) {
alpar@761:         std::vector<Node> st;
alpar@761:         Node nn = n;
alpar@761:         while ((*_order)[nn] == -1) {
alpar@761:           st.push_back(nn);
alpar@761:           nn = (*_pred)[nn];
alpar@761:         }
alpar@761:         while (!st.empty()) {
alpar@761:           (*_order)[st.back()] = index++;
alpar@761:           st.pop_back();
alpar@761:         }
tapolcai@531:       }
tapolcai@531:     }
tapolcai@531: 
kpeter@534:   public:
kpeter@534: 
alpar@532:     ///\name Execution Control
alpar@761: 
alpar@532:     ///@{
alpar@532: 
alpar@532:     /// \brief Run the Gomory-Hu algorithm.
tapolcai@531:     ///
alpar@532:     /// This function runs the Gomory-Hu algorithm.
tapolcai@531:     void run() {
tapolcai@531:       init();
tapolcai@531:       start();
tapolcai@531:     }
alpar@761: 
alpar@532:     /// @}
tapolcai@531: 
alpar@532:     ///\name Query Functions
alpar@532:     ///The results of the algorithm can be obtained using these
alpar@532:     ///functions.\n
kpeter@588:     ///\ref run() should be called before using them.\n
kpeter@534:     ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
alpar@532: 
alpar@532:     ///@{
alpar@532: 
alpar@532:     /// \brief Return the predecessor node in the Gomory-Hu tree.
tapolcai@531:     ///
kpeter@588:     /// This function returns the predecessor node of the given node
kpeter@588:     /// in the Gomory-Hu tree.
kpeter@588:     /// If \c node is the root of the tree, then it returns \c INVALID.
kpeter@588:     ///
kpeter@588:     /// \pre \ref run() must be called before using this function.
kpeter@588:     Node predNode(const Node& node) const {
tapolcai@531:       return (*_pred)[node];
tapolcai@531:     }
tapolcai@531: 
alpar@532:     /// \brief Return the weight of the predecessor edge in the
tapolcai@531:     /// Gomory-Hu tree.
tapolcai@531:     ///
alpar@761:     /// This function returns the weight of the predecessor edge of the
kpeter@588:     /// given node in the Gomory-Hu tree.
kpeter@588:     /// If \c node is the root of the tree, the result is undefined.
kpeter@588:     ///
kpeter@588:     /// \pre \ref run() must be called before using this function.
kpeter@588:     Value predValue(const Node& node) const {
tapolcai@531:       return (*_weight)[node];
tapolcai@531:     }
tapolcai@531: 
kpeter@588:     /// \brief Return the distance from the root node in the Gomory-Hu tree.
kpeter@588:     ///
kpeter@588:     /// This function returns the distance of the given node from the root
kpeter@588:     /// node in the Gomory-Hu tree.
kpeter@588:     ///
kpeter@588:     /// \pre \ref run() must be called before using this function.
kpeter@588:     int rootDist(const Node& node) const {
kpeter@588:       return (*_order)[node];
kpeter@588:     }
kpeter@588: 
alpar@532:     /// \brief Return the minimum cut value between two nodes
tapolcai@531:     ///
kpeter@588:     /// This function returns the minimum cut value between the nodes
alpar@761:     /// \c s and \c t.
kpeter@588:     /// It finds the nearest common ancestor of the given nodes in the
kpeter@588:     /// Gomory-Hu tree and calculates the minimum weight edge on the
kpeter@588:     /// paths to the ancestor.
kpeter@588:     ///
kpeter@588:     /// \pre \ref run() must be called before using this function.
tapolcai@531:     Value minCutValue(const Node& s, const Node& t) const {
tapolcai@531:       Node sn = s, tn = t;
tapolcai@531:       Value value = std::numeric_limits<Value>::max();
alpar@761: 
tapolcai@531:       while (sn != tn) {
alpar@761:         if ((*_order)[sn] < (*_order)[tn]) {
alpar@761:           if ((*_weight)[tn] <= value) value = (*_weight)[tn];
alpar@761:           tn = (*_pred)[tn];
alpar@761:         } else {
alpar@761:           if ((*_weight)[sn] <= value) value = (*_weight)[sn];
alpar@761:           sn = (*_pred)[sn];
alpar@761:         }
tapolcai@531:       }
tapolcai@531:       return value;
tapolcai@531:     }
tapolcai@531: 
alpar@532:     /// \brief Return the minimum cut between two nodes
tapolcai@531:     ///
alpar@532:     /// This function returns the minimum cut between the nodes \c s and \c t
kpeter@534:     /// in the \c cutMap parameter by setting the nodes in the component of
kpeter@534:     /// \c s to \c true and the other nodes to \c false.
alpar@532:     ///
kpeter@588:     /// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt.
kpeter@588:     ///
kpeter@588:     /// \param s The base node.
kpeter@588:     /// \param t The node you want to separate from node \c s.
kpeter@588:     /// \param cutMap The cut will be returned in this map.
kpeter@588:     /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap
kpeter@588:     /// "ReadWriteMap" on the graph nodes.
kpeter@588:     ///
kpeter@588:     /// \return The value of the minimum cut between \c s and \c t.
kpeter@588:     ///
kpeter@588:     /// \pre \ref run() must be called before using this function.
tapolcai@531:     template <typename CutMap>
alpar@761:     Value minCutMap(const Node& s, ///<
alpar@532:                     const Node& t,
alpar@761:                     ///<
alpar@532:                     CutMap& cutMap
alpar@761:                     ///<
alpar@532:                     ) const {
tapolcai@531:       Node sn = s, tn = t;
alpar@532:       bool s_root=false;
tapolcai@531:       Node rn = INVALID;
tapolcai@531:       Value value = std::numeric_limits<Value>::max();
alpar@761: 
tapolcai@531:       while (sn != tn) {
alpar@761:         if ((*_order)[sn] < (*_order)[tn]) {
alpar@761:           if ((*_weight)[tn] <= value) {
alpar@761:             rn = tn;
alpar@532:             s_root = false;
alpar@761:             value = (*_weight)[tn];
alpar@761:           }
alpar@761:           tn = (*_pred)[tn];
alpar@761:         } else {
alpar@761:           if ((*_weight)[sn] <= value) {
alpar@761:             rn = sn;
alpar@532:             s_root = true;
alpar@761:             value = (*_weight)[sn];
alpar@761:           }
alpar@761:           sn = (*_pred)[sn];
alpar@761:         }
tapolcai@531:       }
tapolcai@531: 
tapolcai@531:       typename Graph::template NodeMap<bool> reached(_graph, false);
kpeter@573:       reached[_root] = true;
alpar@532:       cutMap.set(_root, !s_root);
kpeter@573:       reached[rn] = true;
alpar@532:       cutMap.set(rn, s_root);
tapolcai@531: 
alpar@532:       std::vector<Node> st;
tapolcai@531:       for (NodeIt n(_graph); n != INVALID; ++n) {
alpar@761:         st.clear();
alpar@532:         Node nn = n;
alpar@761:         while (!reached[nn]) {
alpar@761:           st.push_back(nn);
alpar@761:           nn = (*_pred)[nn];
alpar@761:         }
alpar@761:         while (!st.empty()) {
alpar@761:           cutMap.set(st.back(), cutMap[nn]);
alpar@761:           st.pop_back();
alpar@761:         }
tapolcai@531:       }
alpar@761: 
tapolcai@531:       return value;
tapolcai@531:     }
tapolcai@531: 
alpar@532:     ///@}
alpar@532: 
alpar@532:     friend class MinCutNodeIt;
alpar@532: 
alpar@532:     /// Iterate on the nodes of a minimum cut
alpar@761: 
alpar@532:     /// This iterator class lists the nodes of a minimum cut found by
kpeter@588:     /// GomoryHu. Before using it, you must allocate a GomoryHu class
alpar@533:     /// and call its \ref GomoryHu::run() "run()" method.
alpar@532:     ///
alpar@532:     /// This example counts the nodes in the minimum cut separating \c s from
alpar@532:     /// \c t.
alpar@532:     /// \code
alpar@533:     /// GomoruHu<Graph> gom(g, capacities);
alpar@532:     /// gom.run();
kpeter@534:     /// int cnt=0;
kpeter@534:     /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
alpar@532:     /// \endcode
alpar@532:     class MinCutNodeIt
alpar@532:     {
alpar@532:       bool _side;
alpar@532:       typename Graph::NodeIt _node_it;
alpar@532:       typename Graph::template NodeMap<bool> _cut;
alpar@532:     public:
alpar@532:       /// Constructor
alpar@532: 
kpeter@534:       /// Constructor.
alpar@532:       ///
alpar@533:       MinCutNodeIt(GomoryHu const &gomory,
alpar@533:                    ///< The GomoryHu class. You must call its
alpar@532:                    ///  run() method
kpeter@534:                    ///  before initializing this iterator.
kpeter@534:                    const Node& s, ///< The base node.
alpar@532:                    const Node& t,
kpeter@534:                    ///< The node you want to separate from node \c s.
alpar@532:                    bool side=true
alpar@532:                    ///< If it is \c true (default) then the iterator lists
alpar@532:                    ///  the nodes of the component containing \c s,
alpar@532:                    ///  otherwise it lists the other component.
alpar@532:                    /// \note As the minimum cut is not always unique,
alpar@532:                    /// \code
alpar@532:                    /// MinCutNodeIt(gomory, s, t, true);
alpar@532:                    /// \endcode
alpar@532:                    /// and
alpar@532:                    /// \code
alpar@532:                    /// MinCutNodeIt(gomory, t, s, false);
alpar@532:                    /// \endcode
alpar@532:                    /// does not necessarily give the same set of nodes.
alpar@532:                    /// However it is ensured that
alpar@532:                    /// \code
alpar@532:                    /// MinCutNodeIt(gomory, s, t, true);
alpar@532:                    /// \endcode
alpar@532:                    /// and
alpar@532:                    /// \code
alpar@532:                    /// MinCutNodeIt(gomory, s, t, false);
alpar@532:                    /// \endcode
alpar@532:                    /// together list each node exactly once.
alpar@532:                    )
alpar@532:         : _side(side), _cut(gomory._graph)
alpar@532:       {
alpar@532:         gomory.minCutMap(s,t,_cut);
alpar@532:         for(_node_it=typename Graph::NodeIt(gomory._graph);
alpar@532:             _node_it!=INVALID && _cut[_node_it]!=_side;
alpar@532:             ++_node_it) {}
alpar@532:       }
kpeter@534:       /// Conversion to \c Node
alpar@532: 
kpeter@534:       /// Conversion to \c Node.
alpar@532:       ///
alpar@532:       operator typename Graph::Node() const
alpar@532:       {
alpar@532:         return _node_it;
alpar@532:       }
alpar@532:       bool operator==(Invalid) { return _node_it==INVALID; }
alpar@532:       bool operator!=(Invalid) { return _node_it!=INVALID; }
alpar@532:       /// Next node
alpar@532: 
kpeter@534:       /// Next node.
alpar@532:       ///
alpar@532:       MinCutNodeIt &operator++()
alpar@532:       {
alpar@532:         for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
alpar@532:         return *this;
alpar@532:       }
alpar@532:       /// Postfix incrementation
alpar@532: 
kpeter@534:       /// Postfix incrementation.
alpar@532:       ///
alpar@532:       /// \warning This incrementation
kpeter@534:       /// returns a \c Node, not a \c MinCutNodeIt, as one may
alpar@532:       /// expect.
alpar@532:       typename Graph::Node operator++(int)
alpar@532:       {
alpar@532:         typename Graph::Node n=*this;
alpar@532:         ++(*this);
alpar@532:         return n;
alpar@532:       }
alpar@532:     };
alpar@761: 
alpar@532:     friend class MinCutEdgeIt;
alpar@761: 
alpar@532:     /// Iterate on the edges of a minimum cut
alpar@761: 
alpar@532:     /// This iterator class lists the edges of a minimum cut found by
kpeter@588:     /// GomoryHu. Before using it, you must allocate a GomoryHu class
alpar@533:     /// and call its \ref GomoryHu::run() "run()" method.
alpar@532:     ///
alpar@532:     /// This example computes the value of the minimum cut separating \c s from
alpar@532:     /// \c t.
alpar@532:     /// \code
alpar@533:     /// GomoruHu<Graph> gom(g, capacities);
alpar@532:     /// gom.run();
alpar@532:     /// int value=0;
kpeter@534:     /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
alpar@532:     ///   value+=capacities[e];
alpar@532:     /// \endcode
kpeter@588:     /// The result will be the same as the value returned by
kpeter@588:     /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)".
alpar@532:     class MinCutEdgeIt
alpar@532:     {
alpar@532:       bool _side;
alpar@532:       const Graph &_graph;
alpar@532:       typename Graph::NodeIt _node_it;
alpar@532:       typename Graph::OutArcIt _arc_it;
alpar@532:       typename Graph::template NodeMap<bool> _cut;
alpar@532:       void step()
alpar@532:       {
alpar@532:         ++_arc_it;
alpar@532:         while(_node_it!=INVALID && _arc_it==INVALID)
alpar@532:           {
alpar@532:             for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
alpar@532:             if(_node_it!=INVALID)
alpar@532:               _arc_it=typename Graph::OutArcIt(_graph,_node_it);
alpar@532:           }
alpar@532:       }
alpar@761: 
alpar@532:     public:
kpeter@588:       /// Constructor
kpeter@588: 
kpeter@588:       /// Constructor.
kpeter@588:       ///
alpar@533:       MinCutEdgeIt(GomoryHu const &gomory,
alpar@533:                    ///< The GomoryHu class. You must call its
alpar@532:                    ///  run() method
kpeter@534:                    ///  before initializing this iterator.
kpeter@534:                    const Node& s,  ///< The base node.
alpar@532:                    const Node& t,
kpeter@534:                    ///< The node you want to separate from node \c s.
alpar@532:                    bool side=true
alpar@532:                    ///< If it is \c true (default) then the listed arcs
alpar@532:                    ///  will be oriented from the
kpeter@588:                    ///  nodes of the component containing \c s,
alpar@532:                    ///  otherwise they will be oriented in the opposite
alpar@532:                    ///  direction.
alpar@532:                    )
alpar@532:         : _graph(gomory._graph), _cut(_graph)
alpar@532:       {
alpar@532:         gomory.minCutMap(s,t,_cut);
alpar@532:         if(!side)
alpar@532:           for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
alpar@532:             _cut[n]=!_cut[n];
alpar@532: 
alpar@532:         for(_node_it=typename Graph::NodeIt(_graph);
alpar@532:             _node_it!=INVALID && !_cut[_node_it];
alpar@532:             ++_node_it) {}
alpar@532:         _arc_it = _node_it!=INVALID ?
alpar@532:           typename Graph::OutArcIt(_graph,_node_it) : INVALID;
alpar@532:         while(_node_it!=INVALID && _arc_it == INVALID)
alpar@532:           {
alpar@532:             for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}
alpar@532:             if(_node_it!=INVALID)
alpar@532:               _arc_it= typename Graph::OutArcIt(_graph,_node_it);
alpar@532:           }
alpar@532:         while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
alpar@532:       }
kpeter@534:       /// Conversion to \c Arc
alpar@532: 
kpeter@534:       /// Conversion to \c Arc.
alpar@532:       ///
alpar@532:       operator typename Graph::Arc() const
alpar@532:       {
alpar@532:         return _arc_it;
alpar@532:       }
kpeter@534:       /// Conversion to \c Edge
alpar@532: 
kpeter@534:       /// Conversion to \c Edge.
alpar@532:       ///
alpar@532:       operator typename Graph::Edge() const
alpar@532:       {
alpar@532:         return _arc_it;
alpar@532:       }
alpar@532:       bool operator==(Invalid) { return _node_it==INVALID; }
alpar@532:       bool operator!=(Invalid) { return _node_it!=INVALID; }
alpar@532:       /// Next edge
alpar@532: 
kpeter@534:       /// Next edge.
alpar@532:       ///
alpar@532:       MinCutEdgeIt &operator++()
alpar@532:       {
alpar@532:         step();
alpar@532:         while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
alpar@532:         return *this;
alpar@532:       }
alpar@532:       /// Postfix incrementation
alpar@761: 
kpeter@534:       /// Postfix incrementation.
alpar@532:       ///
alpar@532:       /// \warning This incrementation
kpeter@534:       /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect.
alpar@532:       typename Graph::Arc operator++(int)
alpar@532:       {
alpar@532:         typename Graph::Arc e=*this;
alpar@532:         ++(*this);
alpar@532:         return e;
alpar@532:       }
alpar@532:     };
alpar@532: 
tapolcai@531:   };
tapolcai@531: 
tapolcai@531: }
tapolcai@531: 
tapolcai@531: #endif