lemon-1.2: comparison lemon/gomory

equal deleted inserted replaced

-:00a797224124
+:3489607882e0
-/* -*- C++ -*-
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
-* This file is a part of LEMON, a generic C++ optimization library
+* This file is a part of LEMON, a generic C++ optimization library.
 *
-* Copyright (C) 2003-2008
+* Copyright (C) 2003-2010
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 #include <lemon/preflow.h>
 #include <lemon/concept_check.h>
 #include <lemon/concepts/maps.h>
 /// \ingroup min_cut
 /// \file
 /// \brief Gomory-Hu cut tree in graphs.
 namespace lemon {
 /// \ingroup min_cut
 ///
 /// \brief Gomory-Hu cut tree algorithm
 ///
 /// The Gomory-Hu tree is a tree on the node set of a given graph, but it
 /// may contain edges which are not in the original graph. It has the
 /// property that the minimum capacity edge of the path between two nodes
 /// in this tree has the same weight as the minimum cut in the graph
 /// 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 algorithm calculates \e n-1 distinct minimum cuts (currently with
 /// 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().
 /// \tparam GR The type of the undirected graph the algorithm runs on.
 /// \tparam CAP The type of the edge map containing the capacities.
 /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
 #ifdef DOXYGEN
 template <typename GR,
-	    typename CAP>
+typename CAP>
 #else
 template <typename GR,
-	    typename CAP = typename GR::template EdgeMap<int> >
+typename CAP = typename GR::template EdgeMap<int> >
 #endif
 class GomoryHu {
 public:
 /// The graph type of the algorithm
 typedef GR Graph;
 /// The capacity map type of the algorithm
 typedef CAP Capacity;
 /// The value type of capacities
 typedef typename Capacity::Value Value;
 private:
 TEMPLATE_GRAPH_TYPEDEFS(Graph);
 const Graph& _graph;
 typename Graph::template NodeMap<Value>* _weight;
 typename Graph::template NodeMap<int>* _order;
 void createStructures() {
 if (!_pred) {
-	_pred = new typename Graph::template NodeMap<Node>(_graph);
+_pred = new typename Graph::template NodeMap<Node>(_graph);
 }
 if (!_weight) {
-	_weight = new typename Graph::template NodeMap<Value>(_graph);
+_weight = new typename Graph::template NodeMap<Value>(_graph);
 }
 if (!_order) {
-	_order = new typename Graph::template NodeMap<int>(_graph);
+_order = new typename Graph::template NodeMap<int>(_graph);
 }
 }
 void destroyStructures() {
 if (_pred) {
-	delete _pred;
+delete _pred;
 }
 if (_weight) {
-	delete _weight;
+delete _weight;
 }
 if (_order) {
-	delete _order;
+delete _order;
 }
 }
 public:
 /// \brief Constructor
 ///
 /// Constructor.
 /// \param graph The undirected graph the algorithm runs on.
 /// \param capacity The edge capacity map.
 GomoryHu(const Graph& graph, const Capacity& capacity)
 : _graph(graph), _capacity(capacity),
-	_pred(0), _weight(0), _order(0)
+_pred(0), _weight(0), _order(0)
 {
 checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
 }
 ~GomoryHu() {
 destroyStructures();
 }
 private:
 // Initialize the internal data structures
 void init() {
 createStructures();
 _root = NodeIt(_graph);
 for (NodeIt n(_graph); n != INVALID; ++n) {
 (*_pred)[n] = _root;
 (*_order)[n] = -1;
 }
 (*_pred)[_root] = INVALID;
 (*_weight)[_root] = std::numeric_limits<Value>::max();
 }
 // Start the algorithm
 void start() {
 Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
 for (NodeIt n(_graph); n != INVALID; ++n) {
-	if (n == _root) continue;
+if (n == _root) continue;
-	Node pn = (*_pred)[n];
+Node pn = (*_pred)[n];
-	fa.source(n);
+fa.source(n);
-	fa.target(pn);
+fa.target(pn);
-	fa.runMinCut();
+fa.runMinCut();
-	(*_weight)[n] = fa.flowValue();
+(*_weight)[n] = fa.flowValue();
-	for (NodeIt nn(_graph); nn != INVALID; ++nn) {
+for (NodeIt nn(_graph); nn != INVALID; ++nn) {
-	  if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
+if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
-	    (*_pred)[nn] = n;
+(*_pred)[nn] = n;
-	  }
+}
-	}
+}
-	if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
+if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
-	  (*_pred)[n] = (*_pred)[pn];
+(*_pred)[n] = (*_pred)[pn];
-	  (*_pred)[pn] = n;
+(*_pred)[pn] = n;
-	  (*_weight)[n] = (*_weight)[pn];
+(*_weight)[n] = (*_weight)[pn];
-	  (*_weight)[pn] = fa.flowValue();
+(*_weight)[pn] = fa.flowValue();
-	}
+}
 }
 (*_order)[_root] = 0;
 int index = 1;
 for (NodeIt n(_graph); n != INVALID; ++n) {
-	std::vector<Node> st;
+std::vector<Node> st;
-	Node nn = n;
+Node nn = n;
-	while ((*_order)[nn] == -1) {
+while ((*_order)[nn] == -1) {
-	  st.push_back(nn);
+st.push_back(nn);
-	  nn = (*_pred)[nn];
+nn = (*_pred)[nn];
-	}
+}
-	while (!st.empty()) {
+while (!st.empty()) {
-	  (*_order)[st.back()] = index++;
+(*_order)[st.back()] = index++;
-	  st.pop_back();
+st.pop_back();
-	}
+}
 }
 }
 public:
 ///\name Execution Control
 ///@{
 /// \brief Run the Gomory-Hu algorithm.
 ///
 /// This function runs the Gomory-Hu algorithm.
 void run() {
 init();
 start();
 }
 /// @}
 ///\name Query Functions
 ///The results of the algorithm can be obtained using these
 ///functions.\n
 }
 /// \brief Return the weight of the predecessor edge in the
 /// Gomory-Hu tree.
 ///
 /// 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 minimum cut value between two nodes
 ///
 /// 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.
 Value minCutValue(const Node& s, const Node& t) const {
 Node sn = s, tn = t;
 Value value = std::numeric_limits<Value>::max();
 while (sn != tn) {
-	if ((*_order)[sn] < (*_order)[tn]) {
+if ((*_order)[sn] < (*_order)[tn]) {
-	  if ((*_weight)[tn] <= value) value = (*_weight)[tn];
+if ((*_weight)[tn] <= value) value = (*_weight)[tn];
-	  tn = (*_pred)[tn];
+tn = (*_pred)[tn];
-	} else {
+} else {
-	  if ((*_weight)[sn] <= value) value = (*_weight)[sn];
+if ((*_weight)[sn] <= value) value = (*_weight)[sn];
-	  sn = (*_pred)[sn];
+sn = (*_pred)[sn];
-	}
+}
 }
 return value;
 }
 /// \brief Return the minimum cut between two nodes
 ) const {
 Node sn = s, tn = t;
 bool s_root=false;
 Node rn = INVALID;
 Value value = std::numeric_limits<Value>::max();
 while (sn != tn) {
-	if ((*_order)[sn] < (*_order)[tn]) {
+if ((*_order)[sn] < (*_order)[tn]) {
-	  if ((*_weight)[tn] <= value) {
+if ((*_weight)[tn] <= value) {
-	    rn = tn;
+rn = tn;
 s_root = false;
-	    value = (*_weight)[tn];
+value = (*_weight)[tn];
-	  }
+}
-	  tn = (*_pred)[tn];
+tn = (*_pred)[tn];
-	} else {
+} else {
-	  if ((*_weight)[sn] <= value) {
+if ((*_weight)[sn] <= value) {
-	    rn = sn;
+rn = sn;
 s_root = true;
-	    value = (*_weight)[sn];
+value = (*_weight)[sn];
-	  }
+}
-	  sn = (*_pred)[sn];
+sn = (*_pred)[sn];
-	}
+}
 }
 typename Graph::template NodeMap<bool> reached(_graph, false);
 reached[_root] = true;
 cutMap.set(_root, !s_root);
 reached[rn] = true;
 cutMap.set(rn, s_root);
 std::vector<Node> st;
 for (NodeIt n(_graph); n != INVALID; ++n) {
-	st.clear();
+st.clear();
 Node nn = n;
-	while (!reached[nn]) {
+while (!reached[nn]) {
-	  st.push_back(nn);
+st.push_back(nn);
-	  nn = (*_pred)[nn];
+nn = (*_pred)[nn];
-	}
+}
-	while (!st.empty()) {
+while (!st.empty()) {
-	  cutMap.set(st.back(), cutMap[nn]);
+cutMap.set(st.back(), cutMap[nn]);
-	  st.pop_back();
+st.pop_back();
-	}
+}
 }
 return value;
 }
 ///@}
 friend class MinCutNodeIt;
 /// Iterate on the nodes of a minimum cut
 /// This iterator class lists the nodes of a minimum cut found by
 /// GomoryHu. Before using it, you must allocate a GomoryHu class
 /// and call its \ref GomoryHu::run() "run()" method.
 ///
 /// This example counts the nodes in the minimum cut separating \c s from
 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
 /// GomoryHu. Before using it, you must allocate a GomoryHu class
 /// and call its \ref GomoryHu::run() "run()" method.
 ///
 /// This example computes the value of the minimum cut separating \c s from
 for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
 if(_node_it!=INVALID)
 _arc_it=typename Graph::OutArcIt(_graph,_node_it);
 }
 }
 public:
 /// Constructor
 /// Constructor.
 ///
 step();
 while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
 return *this;
 }
 /// Postfix incrementation
 /// Postfix incrementation.
 ///
 /// \warning This incrementation
 /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect.
 typename Graph::Arc operator++(int)

branch	1.2
changeset 882	7af2ae7c1428
parent 786	e20173729589