# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1235560257 0
# Node ID e72bacfea6b78fd9d84df2128824bc027f6e5afa
# Parent ccd2d3a3001ebc80a67dd8d4de56486d82eec773
Remane GomoryHuTree to GomoryHu (#66)
diff -r ccd2d3a3001e -r e72bacfea6b7 lemon/Makefile.am
--- a/lemon/Makefile.am Wed Feb 25 11:10:52 2009 +0000
+++ b/lemon/Makefile.am Wed Feb 25 11:10:57 2009 +0000
@@ -68,7 +68,7 @@
lemon/euler.h \
lemon/full_graph.h \
lemon/glpk.h \
- lemon/gomory_hu_tree.h \
+ lemon/gomory_hu.h \
lemon/graph_to_eps.h \
lemon/grid_graph.h \
lemon/hypercube_graph.h \
diff -r ccd2d3a3001e -r e72bacfea6b7 lemon/gomory_hu.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/gomory_hu.h Wed Feb 25 11:10:57 2009 +0000
@@ -0,0 +1,554 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * 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
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_GOMORY_HU_TREE_H
+#define LEMON_GOMORY_HU_TREE_H
+
+#include <limits>
+
+#include <lemon/core.h>
+#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 the graph, but it
+ /// may contain edges which are not in the original digraph. 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 digraph
+ /// 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), 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
+ /// the minimum cut and the minimum cut value between any two node
+ /// in the digraph. You can also list (iterate on) the nodes and the
+ /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
+ ///
+ /// \tparam GR The undirected graph data structure the algorithm will run on
+ /// \tparam CAP type of the EdgeMap describing the Edge capacities.
+ /// it is typename GR::template EdgeMap<int> by default.
+ template <typename GR,
+ typename CAP = typename GR::template EdgeMap<int>
+ >
+ class GomoryHu {
+ public:
+
+ /// The graph type
+ typedef GR Graph;
+ /// The type if the edge capacity map
+ typedef CAP Capacity;
+ /// The value type of capacities
+ typedef typename Capacity::Value Value;
+
+ private:
+
+ TEMPLATE_GRAPH_TYPEDEFS(Graph);
+
+ const Graph& _graph;
+ const Capacity& _capacity;
+
+ Node _root;
+ typename Graph::template NodeMap<Node>* _pred;
+ typename Graph::template NodeMap<Value>* _weight;
+ typename Graph::template NodeMap<int>* _order;
+
+ void createStructures() {
+ if (!_pred) {
+ _pred = new typename Graph::template NodeMap<Node>(_graph);
+ }
+ if (!_weight) {
+ _weight = new typename Graph::template NodeMap<Value>(_graph);
+ }
+ if (!_order) {
+ _order = new typename Graph::template NodeMap<int>(_graph);
+ }
+ }
+
+ void destroyStructures() {
+ if (_pred) {
+ delete _pred;
+ }
+ if (_weight) {
+ delete _weight;
+ }
+ if (_order) {
+ delete _order;
+ }
+ }
+
+ public:
+
+ /// \brief Constructor
+ ///
+ /// Constructor
+ /// \param graph The graph the algorithm will run on.
+ /// \param capacity The capacity map.
+ GomoryHu(const Graph& graph, const Capacity& capacity)
+ : _graph(graph), _capacity(capacity),
+ _pred(0), _weight(0), _order(0)
+ {
+ checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
+ }
+
+
+ /// \brief Destructor
+ ///
+ /// Destructor
+ ~GomoryHu() {
+ destroyStructures();
+ }
+
+ // \brief Initialize the internal data structures.
+ //
+ // This function initializes the internal data structures.
+ //
+ void init() {
+ createStructures();
+
+ _root = NodeIt(_graph);
+ for (NodeIt n(_graph); n != INVALID; ++n) {
+ _pred->set(n, _root);
+ _order->set(n, -1);
+ }
+ _pred->set(_root, INVALID);
+ _weight->set(_root, std::numeric_limits<Value>::max());
+ }
+
+
+ // \brief Start the algorithm
+ //
+ // This function starts the algorithm.
+ //
+ // \pre \ref init() must be called before using this function.
+ //
+ void start() {
+ Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
+
+ for (NodeIt n(_graph); n != INVALID; ++n) {
+ if (n == _root) continue;
+
+ Node pn = (*_pred)[n];
+ fa.source(n);
+ fa.target(pn);
+
+ fa.runMinCut();
+
+ _weight->set(n, fa.flowValue());
+
+ for (NodeIt nn(_graph); nn != INVALID; ++nn) {
+ if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
+ _pred->set(nn, n);
+ }
+ }
+ if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
+ _pred->set(n, (*_pred)[pn]);
+ _pred->set(pn, n);
+ _weight->set(n, (*_weight)[pn]);
+ _weight->set(pn, fa.flowValue());
+ }
+ }
+
+ _order->set(_root, 0);
+ int index = 1;
+
+ for (NodeIt n(_graph); n != INVALID; ++n) {
+ std::vector<Node> st;
+ Node nn = n;
+ while ((*_order)[nn] == -1) {
+ st.push_back(nn);
+ nn = (*_pred)[nn];
+ }
+ while (!st.empty()) {
+ _order->set(st.back(), index++);
+ st.pop_back();
+ }
+ }
+ }
+
+ ///\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
+ ///The \ref run() "run()" should be called before using them.\n
+ ///See also MinCutNodeIt and MinCutEdgeIt
+
+ ///@{
+
+ /// \brief Return the predecessor node in the Gomory-Hu tree.
+ ///
+ /// This function returns the predecessor node in the Gomory-Hu tree.
+ /// If the node is
+ /// the root of the Gomory-Hu tree, then it returns \c INVALID.
+ Node predNode(const Node& node) {
+ return (*_pred)[node];
+ }
+
+ /// \brief Return the distance from the root node in the Gomory-Hu tree.
+ ///
+ /// This function returns the distance of \c node from the root node
+ /// in the Gomory-Hu tree.
+ int rootDist(const Node& node) {
+ return (*_order)[node];
+ }
+
+ /// \brief Return the weight of the predecessor edge in the
+ /// Gomory-Hu tree.
+ ///
+ /// This function returns the weight of the predecessor edge in the
+ /// Gomory-Hu tree. If the node is the root, the result is undefined.
+ Value predValue(const Node& node) {
+ return (*_weight)[node];
+ }
+
+ /// \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
+ /// tree and calculates the minimum weight arc on the paths to
+ /// 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) {
+ if ((*_order)[sn] < (*_order)[tn]) {
+ if ((*_weight)[tn] <= value) value = (*_weight)[tn];
+ tn = (*_pred)[tn];
+ } else {
+ if ((*_weight)[sn] <= value) value = (*_weight)[sn];
+ sn = (*_pred)[sn];
+ }
+ }
+ return value;
+ }
+
+ /// \brief Return the minimum cut between two nodes
+ ///
+ /// This function returns the minimum cut between the nodes \c s and \c t
+ /// the \r cutMap parameter by setting the nodes in the component of
+ /// \c \s to true and the other nodes to false.
+ ///
+ /// The \c cutMap should be \ref concepts::ReadWriteMap
+ /// "ReadWriteMap".
+ ///
+ /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt
+ template <typename CutMap>
+ Value minCutMap(const Node& s, ///< Base node
+ const Node& t,
+ ///< The node you want to separate from Node s.
+ CutMap& cutMap
+ ///< The cut will be return in this map.
+ /// It must be a \c bool \ref concepts::ReadWriteMap
+ /// "ReadWriteMap" on the graph 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 ((*_weight)[tn] <= value) {
+ rn = tn;
+ s_root = false;
+ value = (*_weight)[tn];
+ }
+ tn = (*_pred)[tn];
+ } else {
+ if ((*_weight)[sn] <= value) {
+ rn = sn;
+ s_root = true;
+ value = (*_weight)[sn];
+ }
+ sn = (*_pred)[sn];
+ }
+ }
+
+ typename Graph::template NodeMap<bool> reached(_graph, false);
+ reached.set(_root, true);
+ cutMap.set(_root, !s_root);
+ reached.set(rn, true);
+ cutMap.set(rn, s_root);
+
+ std::vector<Node> st;
+ for (NodeIt n(_graph); n != INVALID; ++n) {
+ st.clear();
+ Node nn = n;
+ while (!reached[nn]) {
+ st.push_back(nn);
+ nn = (*_pred)[nn];
+ }
+ while (!st.empty()) {
+ cutMap.set(st.back(), cutMap[nn]);
+ 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
+ /// \c t.
+ /// \code
+ /// GomoruHu<Graph> gom(g, capacities);
+ /// gom.run();
+ /// int sum=0;
+ /// for(GomoruHu<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(GomoryHu const &gomory,
+ ///< The GomoryHu 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
+ /// 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
+ /// \c t.
+ /// \code
+ /// GomoruHu<Graph> gom(g, capacities);
+ /// gom.run();
+ /// int value=0;
+ /// for(GomoruHu<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 GomoryHu::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(GomoryHu const &gomory,
+ ///< The GomoryHu 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;
+ }
+ };
+
+ };
+
+}
+
+#endif
diff -r ccd2d3a3001e -r e72bacfea6b7 lemon/gomory_hu_tree.h
--- a/lemon/gomory_hu_tree.h Wed Feb 25 11:10:52 2009 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,554 +0,0 @@
-/* -*- C++ -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2003-2008
- * 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
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_GOMORY_HU_TREE_H
-#define LEMON_GOMORY_HU_TREE_H
-
-#include <limits>
-
-#include <lemon/core.h>
-#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 the graph, but it
- /// may contain edges which are not in the original digraph. 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 digraph
- /// 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), 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
- /// the minimum cut and the minimum cut value between any two node
- /// in the digraph. You can also list (iterate on) the nodes and the
- /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
- ///
- /// \tparam GR The undirected graph data structure the algorithm will run on
- /// \tparam CAP type of the EdgeMap describing the Edge capacities.
- /// it is typename GR::template EdgeMap<int> by default.
- template <typename GR,
- typename CAP = typename GR::template EdgeMap<int>
- >
- class GomoryHuTree {
- public:
-
- /// The graph type
- typedef GR Graph;
- /// The type if the edge capacity map
- typedef CAP Capacity;
- /// The value type of capacities
- typedef typename Capacity::Value Value;
-
- private:
-
- TEMPLATE_GRAPH_TYPEDEFS(Graph);
-
- const Graph& _graph;
- const Capacity& _capacity;
-
- Node _root;
- typename Graph::template NodeMap<Node>* _pred;
- typename Graph::template NodeMap<Value>* _weight;
- typename Graph::template NodeMap<int>* _order;
-
- void createStructures() {
- if (!_pred) {
- _pred = new typename Graph::template NodeMap<Node>(_graph);
- }
- if (!_weight) {
- _weight = new typename Graph::template NodeMap<Value>(_graph);
- }
- if (!_order) {
- _order = new typename Graph::template NodeMap<int>(_graph);
- }
- }
-
- void destroyStructures() {
- if (_pred) {
- delete _pred;
- }
- if (_weight) {
- delete _weight;
- }
- if (_order) {
- delete _order;
- }
- }
-
- public:
-
- /// \brief Constructor
- ///
- /// Constructor
- /// \param graph The graph the algorithm will run on.
- /// \param capacity The capacity map.
- GomoryHuTree(const Graph& graph, const Capacity& capacity)
- : _graph(graph), _capacity(capacity),
- _pred(0), _weight(0), _order(0)
- {
- checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
- }
-
-
- /// \brief Destructor
- ///
- /// Destructor
- ~GomoryHuTree() {
- destroyStructures();
- }
-
- // \brief Initialize the internal data structures.
- //
- // This function initializes the internal data structures.
- //
- void init() {
- createStructures();
-
- _root = NodeIt(_graph);
- for (NodeIt n(_graph); n != INVALID; ++n) {
- _pred->set(n, _root);
- _order->set(n, -1);
- }
- _pred->set(_root, INVALID);
- _weight->set(_root, std::numeric_limits<Value>::max());
- }
-
-
- // \brief Start the algorithm
- //
- // This function starts the algorithm.
- //
- // \pre \ref init() must be called before using this function.
- //
- void start() {
- Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
-
- for (NodeIt n(_graph); n != INVALID; ++n) {
- if (n == _root) continue;
-
- Node pn = (*_pred)[n];
- fa.source(n);
- fa.target(pn);
-
- fa.runMinCut();
-
- _weight->set(n, fa.flowValue());
-
- for (NodeIt nn(_graph); nn != INVALID; ++nn) {
- if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
- _pred->set(nn, n);
- }
- }
- if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
- _pred->set(n, (*_pred)[pn]);
- _pred->set(pn, n);
- _weight->set(n, (*_weight)[pn]);
- _weight->set(pn, fa.flowValue());
- }
- }
-
- _order->set(_root, 0);
- int index = 1;
-
- for (NodeIt n(_graph); n != INVALID; ++n) {
- std::vector<Node> st;
- Node nn = n;
- while ((*_order)[nn] == -1) {
- st.push_back(nn);
- nn = (*_pred)[nn];
- }
- while (!st.empty()) {
- _order->set(st.back(), index++);
- st.pop_back();
- }
- }
- }
-
- ///\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
- ///The \ref run() "run()" should be called before using them.\n
- ///See also MinCutNodeIt and MinCutEdgeIt
-
- ///@{
-
- /// \brief Return the predecessor node in the Gomory-Hu tree.
- ///
- /// This function returns the predecessor node in the Gomory-Hu tree.
- /// If the node is
- /// the root of the Gomory-Hu tree, then it returns \c INVALID.
- Node predNode(const Node& node) {
- return (*_pred)[node];
- }
-
- /// \brief Return the distance from the root node in the Gomory-Hu tree.
- ///
- /// This function returns the distance of \c node from the root node
- /// in the Gomory-Hu tree.
- int rootDist(const Node& node) {
- return (*_order)[node];
- }
-
- /// \brief Return the weight of the predecessor edge in the
- /// Gomory-Hu tree.
- ///
- /// This function returns the weight of the predecessor edge in the
- /// Gomory-Hu tree. If the node is the root, the result is undefined.
- Value predValue(const Node& node) {
- return (*_weight)[node];
- }
-
- /// \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
- /// tree and calculates the minimum weight arc on the paths to
- /// 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) {
- if ((*_order)[sn] < (*_order)[tn]) {
- if ((*_weight)[tn] <= value) value = (*_weight)[tn];
- tn = (*_pred)[tn];
- } else {
- if ((*_weight)[sn] <= value) value = (*_weight)[sn];
- sn = (*_pred)[sn];
- }
- }
- return value;
- }
-
- /// \brief Return the minimum cut between two nodes
- ///
- /// This function returns the minimum cut between the nodes \c s and \c t
- /// the \r cutMap parameter by setting the nodes in the component of
- /// \c \s to true and the other nodes to false.
- ///
- /// The \c cutMap should be \ref concepts::ReadWriteMap
- /// "ReadWriteMap".
- ///
- /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt
- template <typename CutMap>
- Value minCutMap(const Node& s, ///< Base node
- const Node& t,
- ///< The node you want to separate from Node s.
- CutMap& cutMap
- ///< The cut will be return in this map.
- /// It must be a \c bool \ref concepts::ReadWriteMap
- /// "ReadWriteMap" on the graph 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 ((*_weight)[tn] <= value) {
- rn = tn;
- s_root = false;
- value = (*_weight)[tn];
- }
- tn = (*_pred)[tn];
- } else {
- if ((*_weight)[sn] <= value) {
- rn = sn;
- s_root = true;
- value = (*_weight)[sn];
- }
- sn = (*_pred)[sn];
- }
- }
-
- typename Graph::template NodeMap<bool> reached(_graph, false);
- reached.set(_root, true);
- cutMap.set(_root, !s_root);
- reached.set(rn, true);
- cutMap.set(rn, s_root);
-
- std::vector<Node> st;
- for (NodeIt n(_graph); n != INVALID; ++n) {
- st.clear();
- Node nn = n;
- while (!reached[nn]) {
- st.push_back(nn);
- nn = (*_pred)[nn];
- }
- while (!st.empty()) {
- cutMap.set(st.back(), cutMap[nn]);
- 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
- /// 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;
- }
- };
-
- };
-
-}
-
-#endif
diff -r ccd2d3a3001e -r e72bacfea6b7 test/gomory_hu_test.cc
--- a/test/gomory_hu_test.cc Wed Feb 25 11:10:52 2009 +0000
+++ b/test/gomory_hu_test.cc Wed Feb 25 11:10:57 2009 +0000
@@ -3,7 +3,7 @@
#include "test_tools.h"
#include <lemon/smart_graph.h>
#include <lemon/lgf_reader.h>
-#include <lemon/gomory_hu_tree.h>
+#include <lemon/gomory_hu.h>
#include <cstdlib>
using namespace std;
@@ -60,7 +60,7 @@
GraphReader<Graph>(graph, input).
edgeMap("capacity", capacity).run();
- GomoryHuTree<Graph> ght(graph, capacity);
+ GomoryHu<Graph> ght(graph, capacity);
ght.init();
ght.run();
@@ -75,14 +75,14 @@
check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
int sum=0;
- for(GomoryHuTree<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
+ for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
sum+=capacity[a];
check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
sum=0;
- for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
+ for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
sum++;
- for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
+ for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
sum++;
check(sum == countNodes(graph), "Problem with MinCutNodeIt");