RhodeCode

namespace lemon {

  /// \ingroup min_cut

  ///

  /// \brief Gomory-Hu cut tree algorithm

  ///

  /// property that the minimum capacity edge of the path between two nodes 

  /// between these nodes. Moreover the components obtained by removing

  /// this edge from the tree determine the corresponding minimum cut.

  ///

  /// Therefore once this tree is computed, the minimum cut between any pair

  /// of nodes can easily be obtained.

  /// 

  /// the \ref Preflow algorithm), therefore the algorithm has

  /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a

  /// rooted Gomory-Hu tree, its structure and the weights can be obtained

  /// by \c predNode(), \c predValue() and \c rootDist().

  /// 

  /// The members \c minCutMap() and \c minCutValue() calculate

  ///

  template <typename GR,

  class GomoryHu {

  public:

    /// The graph type

    typedef GR Graph;

    typedef CAP Capacity;

    /// The value type of capacities

    typedef typename Capacity::Value Value;

  private:

  public:

    /// \brief Constructor

    ///

    /// Constructor

    GomoryHu(const Graph& graph, const Capacity& capacity) 

      : _graph(graph), _capacity(capacity),

	_pred(0), _weight(0), _order(0) 

    {

      checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();

    }

    ///

    /// Destructor

    ~GomoryHu() {

      destroyStructures();

    }

    void init() {

      createStructures();

      _root = NodeIt(_graph);

      for (NodeIt n(_graph); n != INVALID; ++n) {

	_pred->set(n, _root);

      }

      _pred->set(_root, INVALID);

      _weight->set(_root, std::numeric_limits<Value>::max()); 

    }

    void start() {

      Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);

      for (NodeIt n(_graph); n != INVALID; ++n) {

	if (n == _root) continue;

	  _order->set(st.back(), index++);

	  st.pop_back();

	}

      }

    }

    ///\name Execution Control

    ///@{

    /// \brief Run the Gomory-Hu algorithm.

    ///

    /// @}

    ///\name Query Functions

    ///The results of the algorithm can be obtained using these

    ///functions.\n

    ///@{

    /// \brief Return the predecessor node in the Gomory-Hu tree.

    ///

    /// This function returns the predecessor node in the Gomory-Hu tree.

    }

    /// \brief Return the minimum cut value between two nodes

    ///

    /// This function returns the minimum cut value between two nodes. The

    /// algorithm finds the nearest common ancestor in the Gomory-Hu

    /// the ancestor.

    Value minCutValue(const Node& s, const Node& t) const {

      Node sn = s, tn = t;

      Value value = std::numeric_limits<Value>::max();

      while (sn != tn) {

      return value;

    }

    /// \brief Return the minimum cut between two nodes

    ///

    /// This function returns the minimum cut between the nodes \c s and \c t

    ///

    template <typename CutMap>

                    const Node& t,

                    CutMap& cutMap

                    ) const {

      Node sn = s, tn = t;

      bool s_root=false;

      Node rn = INVALID;

      Value value = std::numeric_limits<Value>::max();

    ///

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

    /// \c t.

    /// \code

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

    /// gom.run();

    /// \endcode

    class MinCutNodeIt

    {

      bool _side;

      typename Graph::NodeIt _node_it;

      typename Graph::template NodeMap<bool> _cut;

    public:

      /// Constructor

      ///

      MinCutNodeIt(GomoryHu const &gomory,

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

                   ///  run() method

                   const Node& t,

                   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

      {

        gomory.minCutMap(s,t,_cut);

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

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

            ++_node_it) {}

      }

      ///

      operator typename Graph::Node() const

      {

        return _node_it;

      }

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

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

      /// Next node

      ///

      MinCutNodeIt &operator++()

      {

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

        return *this;

      }

      /// Postfix incrementation

      ///

      /// \warning This incrementation

      /// expect.

      typename Graph::Node operator++(int)

      {

        typename Graph::Node n=*this;

        ++(*this);

        return n;

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

    /// \c t.

    /// \code

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

    /// gom.run();

    /// int value=0;

    ///   value+=capacities[e];

    /// \endcode

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

    class MinCutEdgeIt

    {

      bool _side;

      const Graph &_graph;

      typename Graph::NodeIt _node_it;

      typename Graph::OutArcIt _arc_it;

      }

    public:

      MinCutEdgeIt(GomoryHu const &gomory,

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

                   ///  run() method

                   const Node& t,

                   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.

            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();

      }

      ///

      operator typename Graph::Arc() const

      {

        return _arc_it;

      }

      ///

      operator typename Graph::Edge() const

      {

        return _arc_it;

      }

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

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

      /// Next edge

      ///

      MinCutEdgeIt &operator++()

      {

        step();

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

        return *this;

      }

      /// Postfix incrementation

      ///

      /// \warning This incrementation

      typename Graph::Arc operator++(int)

      {

        typename Graph::Arc e=*this;

        ++(*this);

        return e;

      }

  std::istringstream input(test_lgf);

  GraphReader<Graph>(graph, input).

    edgeMap("capacity", capacity).run();

  GomoryHu<Graph> ght(graph, capacity);

  ght.run();

  for (NodeIt u(graph); u != INVALID; ++u) {

    for (NodeIt v(graph); v != u; ++v) {

      Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);

      pf.runMinCut();