RhodeCode

  /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall

  /// time complexity. It calculates a rooted Gomory-Hu tree.

  /// The structure of the tree and the edge weights can be

  /// obtained using \c predNode(), \c predValue() and \c rootDist().

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

  /// \tparam CAP The type of the edge map containing the capacities.

  /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".

    /// The graph type of the algorithm

    /// The capacity map type of the algorithm

    /// Constructor.

    /// Destructor.

    ///\ref run() should be called before using them.\n

    /// This function returns the predecessor node of the given node

    /// in the Gomory-Hu tree.

    /// If \c node is the root of the tree, then it returns \c INVALID.

    ///

    /// \pre \ref run() must be called before using this function.

    Node predNode(const Node& node) const {

    /// This function returns the weight of the predecessor edge of the 

    /// given node in the Gomory-Hu tree.

    /// If \c node is the root of the tree, the result is undefined.

    ///

    /// \pre \ref run() must be called before using this function.

    Value predValue(const Node& node) const {

    /// \brief Return the distance from the root node in the Gomory-Hu tree.

    ///

    /// This function returns the distance of the given node from the root

    /// node in the Gomory-Hu tree.

    ///

    /// \pre \ref run() must be called before using this function.

    int rootDist(const Node& node) const {

      return (*_order)[node];

    }

    /// This function returns the minimum cut value between the nodes

    /// \c s and \c t. 

    /// It finds the nearest common ancestor of the given nodes in the

    /// Gomory-Hu tree and calculates the minimum weight edge on the

    /// paths to the ancestor.

    ///

    /// \pre \ref run() must be called before using this function.

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

    ///

    /// \param s The base node.

    /// \param t The node you want to separate from node \c s.

    /// \param cutMap The cut will be returned in this map.

    /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap

    /// "ReadWriteMap" on the graph nodes.

    ///

    /// \return The value of the minimum cut between \c s and \c t.

    ///

    /// \pre \ref run() must be called before using this function.

    Value minCutMap(const Node& s, ///< 

                    ///< 

                    ///< 

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

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

    /// The result will be the same as the value returned by

    /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)".

      /// Constructor

      /// Constructor.

      ///

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

/// Implementation of the Hao-Orlin algorithm for finding a minimum cut 

/// in a digraph.

  /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph.

  /// This class implements the Hao-Orlin algorithm for finding a minimum

  /// value cut in a directed graph \f$D=(V,A)\f$. 

  /// It takes a fixed node \f$ source \in V \f$ and

  /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal outgoing

  /// capacity) and in the second phase it determines a minimum cut

  /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing

  /// capacity). Obviously, the smaller of these two cuts will be a

  /// preflow push-relabel algorithm. Our implementation calculates

  /// purpose of such algorithm is e.g. testing network reliability.

  /// For an undirected graph you can run just the first phase of the

  /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,

  /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$ 

  /// time. It is implemented in the NagamochiIbaraki algorithm class.

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam CAP The type of the arc map containing the capacities,

  /// which can be any numreric type. The default map type is

  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

  /// \tparam TOL Tolerance class for handling inexact computations. The

  public:

    /// The digraph type of the algorithm

    typedef GR Digraph;

    /// The capacity map type of the algorithm

    typedef CAP CapacityMap;

    /// The tolerance type of the algorithm

    typedef TOL Tolerance;

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    /// \name Execution Control

    /// If you need better control on the execution,

    /// you have to call one of the \ref init() functions first, then

    /// \ref calculateOut() and/or \ref calculateIn().

    /// \brief Initialize the internal data structures.

    /// This function initializes the internal data structures. It creates

    /// the maps and some bucket structures for the algorithm.

    /// The first node is used as the source node for the push-relabel

    /// algorithm.

    /// \brief Initialize the internal data structures.

    /// This function initializes the internal data structures. It creates

    /// the maps and some bucket structures for the algorithm. 

    /// The given node is used as the source node for the push-relabel

    /// algorithm.

    /// \brief Calculate a minimum cut with \f$ source \f$ on the

    /// This function calculates a minimum cut with \f$ source \f$ on the

    /// \f$ source \in X \f$ and minimal outgoing capacity).

    ///

    /// \pre \ref init() must be called before using this function.

    /// \brief Calculate a minimum cut with \f$ source \f$ on the

    /// sink-side.

    /// This function calculates a minimum cut with \f$ source \f$ on the

    /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with

    /// \f$ source \notin X \f$ and minimal outgoing capacity).

    ///

    /// \pre \ref init() must be called before using this function.

    /// \brief Run the algorithm.

    /// This function runs the algorithm. It finds nodes \c source and

    /// \c target arbitrarily and then calls \ref init(), \ref calculateOut()

    /// \brief Run the algorithm.

    /// This function runs the algorithm. It uses the given \c source node, 

    /// finds a proper \c target node and then calls the \ref init(),

    /// \ref calculateOut() and \ref calculateIn().

    /// can be obtained using these functions.\n

    /// \ref run(), \ref calculateOut() or \ref calculateIn() 

    /// should be called before using them.

    /// \brief Return the value of the minimum cut.

    /// This function returns the value of the minimum cut.

    ///

    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 

    /// must be called before using this function.

    /// \brief Return a minimum cut.

    /// This function sets \c cutMap to the characteristic vector of a

    /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$

    /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly

    /// for the nodes of \f$ X \f$).

    ///

    /// \param cutMap A \ref concepts::WriteMap "writable" node map with

    /// \c bool (or convertible) value type.

    ///

    /// \return The value of the minimum cut.

    ///

    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 

    /// must be called before using this function.

    template <typename CutMap>

    Value minCutMap(CutMap& cutMap) const {

        cutMap.set(it, (*_min_cut_map)[it]);

#include <lemon/concepts/graph.h>

#include <lemon/concepts/maps.h>

void checkGomoryHuCompile()

{

  typedef int Value;

  typedef concepts::Graph Graph;

  typedef Graph::Node Node;

  typedef Graph::Edge Edge;

  typedef concepts::ReadMap<Edge, Value> CapMap;

  typedef concepts::ReadWriteMap<Node, bool> CutMap;

  Graph g;

  Node n;

  CapMap cap;

  CutMap cut;

  Value v;

  int d;

  GomoryHu<Graph, CapMap> gh_test(g, cap);

  const GomoryHu<Graph, CapMap>&

    const_gh_test = gh_test;

  gh_test.run();

  n = const_gh_test.predNode(n);

  v = const_gh_test.predValue(n);

  d = const_gh_test.rootDist(n);

  v = const_gh_test.minCutValue(n, n);

  v = const_gh_test.minCutMap(n, n, cut);

}

      check(cm[u] != cm[v], "Wrong cut 2");

      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");

#include <lemon/adaptors.h>

#include <lemon/concepts/digraph.h>

#include <lemon/concepts/maps.h>

#include <lemon/lgf_reader.h>

  "     cap1 cap2 cap3\n"

  "0 1  1    1    1   \n"

  "0 2  2    2    4   \n"

  "1 2  4    4    4   \n"

  "3 4  1    1    1   \n"

  "3 5  2    2    4   \n"

  "4 5  4    4    4   \n"

  "5 4  4    4    4   \n"

  "2 3  1    6    6   \n"

  "4 0  1    6    6   \n";

void checkHaoOrlinCompile()

{

  typedef int Value;

  typedef concepts::Digraph Digraph;

  typedef Digraph::Node Node;

  typedef Digraph::Arc Arc;

  typedef concepts::ReadMap<Arc, Value> CapMap;

  typedef concepts::WriteMap<Node, bool> CutMap;

  Digraph g;

  Node n;

  CapMap cap;

  CutMap cut;

  Value v;

  HaoOrlin<Digraph, CapMap> ho_test(g, cap);

  const HaoOrlin<Digraph, CapMap>&

    const_ho_test = ho_test;

  ho_test.init();

  ho_test.init(n);

  ho_test.calculateOut();

  ho_test.calculateIn();

  ho_test.run();

  ho_test.run(n);

  v = const_ho_test.minCutValue();

  v = const_ho_test.minCutMap(cut);

}

template <typename Graph, typename CapMap, typename CutMap>

typename CapMap::Value 

  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)

{

  typename CapMap::Value sum = 0;

  for (typename Graph::ArcIt a(graph); a != INVALID; ++a) {

    if (cut[graph.source(a)] && !cut[graph.target(a)])

      sum += cap[a];

  }

  return sum;

}

  SmartDigraph graph;

  SmartDigraph::ArcMap<int> cap1(graph), cap2(graph), cap3(graph);

  SmartDigraph::NodeMap<bool> cut(graph);

  istringstream input(lgf);

  digraphReader(graph, input)

    .arcMap("cap1", cap1)

    .arcMap("cap2", cap2)

    .arcMap("cap3", cap3)

    .run();

  {

    HaoOrlin<SmartDigraph> ho(graph, cap1);

    ho.run();

    ho.minCutMap(cut);

    // BUG: The cut value should be positive

    check(ho.minCutValue() == 0, "Wrong cut value");

    // BUG: It should work

    //check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");

  }

  {

    HaoOrlin<SmartDigraph> ho(graph, cap2);

    ho.run();

    ho.minCutMap(cut);

    // BUG: The cut value should be positive

    check(ho.minCutValue() == 0, "Wrong cut value");

    // BUG: It should work

    //check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");

  }

  {

    HaoOrlin<SmartDigraph> ho(graph, cap3);

    ho.run();

    ho.minCutMap(cut);

    // BUG: The cut value should be positive

    check(ho.minCutValue() == 0, "Wrong cut value");

    // BUG: It should work

    //check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");

  }

  typedef Undirector<SmartDigraph> UGraph;

  UGraph ugraph(graph);

  {

    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1);

    ho.run();

    ho.minCutMap(cut);

    // BUG: The cut value should be 2

    check(ho.minCutValue() == 1, "Wrong cut value");

    // BUG: It should work

    //check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");

  }

  {

    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2);

    ho.run();

    ho.minCutMap(cut);

    // TODO: Check this cut value

    check(ho.minCutValue() == 4, "Wrong cut value");

    // BUG: It should work

    //check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");

  }

  {

    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3);

    ho.run();

    ho.minCutMap(cut);

    // TODO: Check this cut value

    check(ho.minCutValue() == 5, "Wrong cut value");

    // BUG: It should work

    //check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");

  }