1.1 --- a/lemon/Makefile.am Wed Mar 04 13:43:05 2009 +0000
1.2 +++ b/lemon/Makefile.am Wed Mar 04 14:09:45 2009 +0000
1.3 @@ -68,6 +68,7 @@
1.4 lemon/euler.h \
1.5 lemon/full_graph.h \
1.6 lemon/glpk.h \
1.7 + lemon/gomory_hu.h \
1.8 lemon/graph_to_eps.h \
1.9 lemon/grid_graph.h \
1.10 lemon/hypercube_graph.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/gomory_hu.h Wed Mar 04 14:09:45 2009 +0000
2.3 @@ -0,0 +1,551 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2008
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_GOMORY_HU_TREE_H
2.23 +#define LEMON_GOMORY_HU_TREE_H
2.24 +
2.25 +#include <limits>
2.26 +
2.27 +#include <lemon/core.h>
2.28 +#include <lemon/preflow.h>
2.29 +#include <lemon/concept_check.h>
2.30 +#include <lemon/concepts/maps.h>
2.31 +
2.32 +/// \ingroup min_cut
2.33 +/// \file
2.34 +/// \brief Gomory-Hu cut tree in graphs.
2.35 +
2.36 +namespace lemon {
2.37 +
2.38 + /// \ingroup min_cut
2.39 + ///
2.40 + /// \brief Gomory-Hu cut tree algorithm
2.41 + ///
2.42 + /// The Gomory-Hu tree is a tree on the node set of a given graph, but it
2.43 + /// may contain edges which are not in the original graph. It has the
2.44 + /// property that the minimum capacity edge of the path between two nodes
2.45 + /// in this tree has the same weight as the minimum cut in the graph
2.46 + /// between these nodes. Moreover the components obtained by removing
2.47 + /// this edge from the tree determine the corresponding minimum cut.
2.48 + ///
2.49 + /// Therefore once this tree is computed, the minimum cut between any pair
2.50 + /// of nodes can easily be obtained.
2.51 + ///
2.52 + /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
2.53 + /// the \ref Preflow algorithm), therefore the algorithm has
2.54 + /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
2.55 + /// rooted Gomory-Hu tree, its structure and the weights can be obtained
2.56 + /// by \c predNode(), \c predValue() and \c rootDist().
2.57 + ///
2.58 + /// The members \c minCutMap() and \c minCutValue() calculate
2.59 + /// the minimum cut and the minimum cut value between any two nodes
2.60 + /// in the graph. You can also list (iterate on) the nodes and the
2.61 + /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
2.62 + ///
2.63 + /// \tparam GR The type of the undirected graph the algorithm runs on.
2.64 + /// \tparam CAP The type of the edge map describing the edge capacities.
2.65 + /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>" by default.
2.66 +#ifdef DOXYGEN
2.67 + template <typename GR,
2.68 + typename CAP>
2.69 +#else
2.70 + template <typename GR,
2.71 + typename CAP = typename GR::template EdgeMap<int> >
2.72 +#endif
2.73 + class GomoryHu {
2.74 + public:
2.75 +
2.76 + /// The graph type
2.77 + typedef GR Graph;
2.78 + /// The type of the edge capacity map
2.79 + typedef CAP Capacity;
2.80 + /// The value type of capacities
2.81 + typedef typename Capacity::Value Value;
2.82 +
2.83 + private:
2.84 +
2.85 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
2.86 +
2.87 + const Graph& _graph;
2.88 + const Capacity& _capacity;
2.89 +
2.90 + Node _root;
2.91 + typename Graph::template NodeMap<Node>* _pred;
2.92 + typename Graph::template NodeMap<Value>* _weight;
2.93 + typename Graph::template NodeMap<int>* _order;
2.94 +
2.95 + void createStructures() {
2.96 + if (!_pred) {
2.97 + _pred = new typename Graph::template NodeMap<Node>(_graph);
2.98 + }
2.99 + if (!_weight) {
2.100 + _weight = new typename Graph::template NodeMap<Value>(_graph);
2.101 + }
2.102 + if (!_order) {
2.103 + _order = new typename Graph::template NodeMap<int>(_graph);
2.104 + }
2.105 + }
2.106 +
2.107 + void destroyStructures() {
2.108 + if (_pred) {
2.109 + delete _pred;
2.110 + }
2.111 + if (_weight) {
2.112 + delete _weight;
2.113 + }
2.114 + if (_order) {
2.115 + delete _order;
2.116 + }
2.117 + }
2.118 +
2.119 + public:
2.120 +
2.121 + /// \brief Constructor
2.122 + ///
2.123 + /// Constructor
2.124 + /// \param graph The undirected graph the algorithm runs on.
2.125 + /// \param capacity The edge capacity map.
2.126 + GomoryHu(const Graph& graph, const Capacity& capacity)
2.127 + : _graph(graph), _capacity(capacity),
2.128 + _pred(0), _weight(0), _order(0)
2.129 + {
2.130 + checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
2.131 + }
2.132 +
2.133 +
2.134 + /// \brief Destructor
2.135 + ///
2.136 + /// Destructor
2.137 + ~GomoryHu() {
2.138 + destroyStructures();
2.139 + }
2.140 +
2.141 + private:
2.142 +
2.143 + // Initialize the internal data structures
2.144 + void init() {
2.145 + createStructures();
2.146 +
2.147 + _root = NodeIt(_graph);
2.148 + for (NodeIt n(_graph); n != INVALID; ++n) {
2.149 + _pred->set(n, _root);
2.150 + _order->set(n, -1);
2.151 + }
2.152 + _pred->set(_root, INVALID);
2.153 + _weight->set(_root, std::numeric_limits<Value>::max());
2.154 + }
2.155 +
2.156 +
2.157 + // Start the algorithm
2.158 + void start() {
2.159 + Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
2.160 +
2.161 + for (NodeIt n(_graph); n != INVALID; ++n) {
2.162 + if (n == _root) continue;
2.163 +
2.164 + Node pn = (*_pred)[n];
2.165 + fa.source(n);
2.166 + fa.target(pn);
2.167 +
2.168 + fa.runMinCut();
2.169 +
2.170 + _weight->set(n, fa.flowValue());
2.171 +
2.172 + for (NodeIt nn(_graph); nn != INVALID; ++nn) {
2.173 + if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
2.174 + _pred->set(nn, n);
2.175 + }
2.176 + }
2.177 + if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
2.178 + _pred->set(n, (*_pred)[pn]);
2.179 + _pred->set(pn, n);
2.180 + _weight->set(n, (*_weight)[pn]);
2.181 + _weight->set(pn, fa.flowValue());
2.182 + }
2.183 + }
2.184 +
2.185 + _order->set(_root, 0);
2.186 + int index = 1;
2.187 +
2.188 + for (NodeIt n(_graph); n != INVALID; ++n) {
2.189 + std::vector<Node> st;
2.190 + Node nn = n;
2.191 + while ((*_order)[nn] == -1) {
2.192 + st.push_back(nn);
2.193 + nn = (*_pred)[nn];
2.194 + }
2.195 + while (!st.empty()) {
2.196 + _order->set(st.back(), index++);
2.197 + st.pop_back();
2.198 + }
2.199 + }
2.200 + }
2.201 +
2.202 + public:
2.203 +
2.204 + ///\name Execution Control
2.205 +
2.206 + ///@{
2.207 +
2.208 + /// \brief Run the Gomory-Hu algorithm.
2.209 + ///
2.210 + /// This function runs the Gomory-Hu algorithm.
2.211 + void run() {
2.212 + init();
2.213 + start();
2.214 + }
2.215 +
2.216 + /// @}
2.217 +
2.218 + ///\name Query Functions
2.219 + ///The results of the algorithm can be obtained using these
2.220 + ///functions.\n
2.221 + ///\ref run() "run()" should be called before using them.\n
2.222 + ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
2.223 +
2.224 + ///@{
2.225 +
2.226 + /// \brief Return the predecessor node in the Gomory-Hu tree.
2.227 + ///
2.228 + /// This function returns the predecessor node in the Gomory-Hu tree.
2.229 + /// If the node is
2.230 + /// the root of the Gomory-Hu tree, then it returns \c INVALID.
2.231 + Node predNode(const Node& node) {
2.232 + return (*_pred)[node];
2.233 + }
2.234 +
2.235 + /// \brief Return the distance from the root node in the Gomory-Hu tree.
2.236 + ///
2.237 + /// This function returns the distance of \c node from the root node
2.238 + /// in the Gomory-Hu tree.
2.239 + int rootDist(const Node& node) {
2.240 + return (*_order)[node];
2.241 + }
2.242 +
2.243 + /// \brief Return the weight of the predecessor edge in the
2.244 + /// Gomory-Hu tree.
2.245 + ///
2.246 + /// This function returns the weight of the predecessor edge in the
2.247 + /// Gomory-Hu tree. If the node is the root, the result is undefined.
2.248 + Value predValue(const Node& node) {
2.249 + return (*_weight)[node];
2.250 + }
2.251 +
2.252 + /// \brief Return the minimum cut value between two nodes
2.253 + ///
2.254 + /// This function returns the minimum cut value between two nodes. The
2.255 + /// algorithm finds the nearest common ancestor in the Gomory-Hu
2.256 + /// tree and calculates the minimum weight edge on the paths to
2.257 + /// the ancestor.
2.258 + Value minCutValue(const Node& s, const Node& t) const {
2.259 + Node sn = s, tn = t;
2.260 + Value value = std::numeric_limits<Value>::max();
2.261 +
2.262 + while (sn != tn) {
2.263 + if ((*_order)[sn] < (*_order)[tn]) {
2.264 + if ((*_weight)[tn] <= value) value = (*_weight)[tn];
2.265 + tn = (*_pred)[tn];
2.266 + } else {
2.267 + if ((*_weight)[sn] <= value) value = (*_weight)[sn];
2.268 + sn = (*_pred)[sn];
2.269 + }
2.270 + }
2.271 + return value;
2.272 + }
2.273 +
2.274 + /// \brief Return the minimum cut between two nodes
2.275 + ///
2.276 + /// This function returns the minimum cut between the nodes \c s and \c t
2.277 + /// in the \c cutMap parameter by setting the nodes in the component of
2.278 + /// \c s to \c true and the other nodes to \c false.
2.279 + ///
2.280 + /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt.
2.281 + template <typename CutMap>
2.282 + Value minCutMap(const Node& s, ///< The base node.
2.283 + const Node& t,
2.284 + ///< The node you want to separate from node \c s.
2.285 + CutMap& cutMap
2.286 + ///< The cut will be returned in this map.
2.287 + /// It must be a \c bool (or convertible)
2.288 + /// \ref concepts::ReadWriteMap "ReadWriteMap"
2.289 + /// on the graph nodes.
2.290 + ) const {
2.291 + Node sn = s, tn = t;
2.292 + bool s_root=false;
2.293 + Node rn = INVALID;
2.294 + Value value = std::numeric_limits<Value>::max();
2.295 +
2.296 + while (sn != tn) {
2.297 + if ((*_order)[sn] < (*_order)[tn]) {
2.298 + if ((*_weight)[tn] <= value) {
2.299 + rn = tn;
2.300 + s_root = false;
2.301 + value = (*_weight)[tn];
2.302 + }
2.303 + tn = (*_pred)[tn];
2.304 + } else {
2.305 + if ((*_weight)[sn] <= value) {
2.306 + rn = sn;
2.307 + s_root = true;
2.308 + value = (*_weight)[sn];
2.309 + }
2.310 + sn = (*_pred)[sn];
2.311 + }
2.312 + }
2.313 +
2.314 + typename Graph::template NodeMap<bool> reached(_graph, false);
2.315 + reached.set(_root, true);
2.316 + cutMap.set(_root, !s_root);
2.317 + reached.set(rn, true);
2.318 + cutMap.set(rn, s_root);
2.319 +
2.320 + std::vector<Node> st;
2.321 + for (NodeIt n(_graph); n != INVALID; ++n) {
2.322 + st.clear();
2.323 + Node nn = n;
2.324 + while (!reached[nn]) {
2.325 + st.push_back(nn);
2.326 + nn = (*_pred)[nn];
2.327 + }
2.328 + while (!st.empty()) {
2.329 + cutMap.set(st.back(), cutMap[nn]);
2.330 + st.pop_back();
2.331 + }
2.332 + }
2.333 +
2.334 + return value;
2.335 + }
2.336 +
2.337 + ///@}
2.338 +
2.339 + friend class MinCutNodeIt;
2.340 +
2.341 + /// Iterate on the nodes of a minimum cut
2.342 +
2.343 + /// This iterator class lists the nodes of a minimum cut found by
2.344 + /// GomoryHu. Before using it, you must allocate a GomoryHu class,
2.345 + /// and call its \ref GomoryHu::run() "run()" method.
2.346 + ///
2.347 + /// This example counts the nodes in the minimum cut separating \c s from
2.348 + /// \c t.
2.349 + /// \code
2.350 + /// GomoruHu<Graph> gom(g, capacities);
2.351 + /// gom.run();
2.352 + /// int cnt=0;
2.353 + /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
2.354 + /// \endcode
2.355 + class MinCutNodeIt
2.356 + {
2.357 + bool _side;
2.358 + typename Graph::NodeIt _node_it;
2.359 + typename Graph::template NodeMap<bool> _cut;
2.360 + public:
2.361 + /// Constructor
2.362 +
2.363 + /// Constructor.
2.364 + ///
2.365 + MinCutNodeIt(GomoryHu const &gomory,
2.366 + ///< The GomoryHu class. You must call its
2.367 + /// run() method
2.368 + /// before initializing this iterator.
2.369 + const Node& s, ///< The base node.
2.370 + const Node& t,
2.371 + ///< The node you want to separate from node \c s.
2.372 + bool side=true
2.373 + ///< If it is \c true (default) then the iterator lists
2.374 + /// the nodes of the component containing \c s,
2.375 + /// otherwise it lists the other component.
2.376 + /// \note As the minimum cut is not always unique,
2.377 + /// \code
2.378 + /// MinCutNodeIt(gomory, s, t, true);
2.379 + /// \endcode
2.380 + /// and
2.381 + /// \code
2.382 + /// MinCutNodeIt(gomory, t, s, false);
2.383 + /// \endcode
2.384 + /// does not necessarily give the same set of nodes.
2.385 + /// However it is ensured that
2.386 + /// \code
2.387 + /// MinCutNodeIt(gomory, s, t, true);
2.388 + /// \endcode
2.389 + /// and
2.390 + /// \code
2.391 + /// MinCutNodeIt(gomory, s, t, false);
2.392 + /// \endcode
2.393 + /// together list each node exactly once.
2.394 + )
2.395 + : _side(side), _cut(gomory._graph)
2.396 + {
2.397 + gomory.minCutMap(s,t,_cut);
2.398 + for(_node_it=typename Graph::NodeIt(gomory._graph);
2.399 + _node_it!=INVALID && _cut[_node_it]!=_side;
2.400 + ++_node_it) {}
2.401 + }
2.402 + /// Conversion to \c Node
2.403 +
2.404 + /// Conversion to \c Node.
2.405 + ///
2.406 + operator typename Graph::Node() const
2.407 + {
2.408 + return _node_it;
2.409 + }
2.410 + bool operator==(Invalid) { return _node_it==INVALID; }
2.411 + bool operator!=(Invalid) { return _node_it!=INVALID; }
2.412 + /// Next node
2.413 +
2.414 + /// Next node.
2.415 + ///
2.416 + MinCutNodeIt &operator++()
2.417 + {
2.418 + for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
2.419 + return *this;
2.420 + }
2.421 + /// Postfix incrementation
2.422 +
2.423 + /// Postfix incrementation.
2.424 + ///
2.425 + /// \warning This incrementation
2.426 + /// returns a \c Node, not a \c MinCutNodeIt, as one may
2.427 + /// expect.
2.428 + typename Graph::Node operator++(int)
2.429 + {
2.430 + typename Graph::Node n=*this;
2.431 + ++(*this);
2.432 + return n;
2.433 + }
2.434 + };
2.435 +
2.436 + friend class MinCutEdgeIt;
2.437 +
2.438 + /// Iterate on the edges of a minimum cut
2.439 +
2.440 + /// This iterator class lists the edges of a minimum cut found by
2.441 + /// GomoryHu. Before using it, you must allocate a GomoryHu class,
2.442 + /// and call its \ref GomoryHu::run() "run()" method.
2.443 + ///
2.444 + /// This example computes the value of the minimum cut separating \c s from
2.445 + /// \c t.
2.446 + /// \code
2.447 + /// GomoruHu<Graph> gom(g, capacities);
2.448 + /// gom.run();
2.449 + /// int value=0;
2.450 + /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
2.451 + /// value+=capacities[e];
2.452 + /// \endcode
2.453 + /// the result will be the same as it is returned by
2.454 + /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)"
2.455 + class MinCutEdgeIt
2.456 + {
2.457 + bool _side;
2.458 + const Graph &_graph;
2.459 + typename Graph::NodeIt _node_it;
2.460 + typename Graph::OutArcIt _arc_it;
2.461 + typename Graph::template NodeMap<bool> _cut;
2.462 + void step()
2.463 + {
2.464 + ++_arc_it;
2.465 + while(_node_it!=INVALID && _arc_it==INVALID)
2.466 + {
2.467 + for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
2.468 + if(_node_it!=INVALID)
2.469 + _arc_it=typename Graph::OutArcIt(_graph,_node_it);
2.470 + }
2.471 + }
2.472 +
2.473 + public:
2.474 + MinCutEdgeIt(GomoryHu const &gomory,
2.475 + ///< The GomoryHu class. You must call its
2.476 + /// run() method
2.477 + /// before initializing this iterator.
2.478 + const Node& s, ///< The base node.
2.479 + const Node& t,
2.480 + ///< The node you want to separate from node \c s.
2.481 + bool side=true
2.482 + ///< If it is \c true (default) then the listed arcs
2.483 + /// will be oriented from the
2.484 + /// the nodes of the component containing \c s,
2.485 + /// otherwise they will be oriented in the opposite
2.486 + /// direction.
2.487 + )
2.488 + : _graph(gomory._graph), _cut(_graph)
2.489 + {
2.490 + gomory.minCutMap(s,t,_cut);
2.491 + if(!side)
2.492 + for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
2.493 + _cut[n]=!_cut[n];
2.494 +
2.495 + for(_node_it=typename Graph::NodeIt(_graph);
2.496 + _node_it!=INVALID && !_cut[_node_it];
2.497 + ++_node_it) {}
2.498 + _arc_it = _node_it!=INVALID ?
2.499 + typename Graph::OutArcIt(_graph,_node_it) : INVALID;
2.500 + while(_node_it!=INVALID && _arc_it == INVALID)
2.501 + {
2.502 + for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}
2.503 + if(_node_it!=INVALID)
2.504 + _arc_it= typename Graph::OutArcIt(_graph,_node_it);
2.505 + }
2.506 + while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
2.507 + }
2.508 + /// Conversion to \c Arc
2.509 +
2.510 + /// Conversion to \c Arc.
2.511 + ///
2.512 + operator typename Graph::Arc() const
2.513 + {
2.514 + return _arc_it;
2.515 + }
2.516 + /// Conversion to \c Edge
2.517 +
2.518 + /// Conversion to \c Edge.
2.519 + ///
2.520 + operator typename Graph::Edge() const
2.521 + {
2.522 + return _arc_it;
2.523 + }
2.524 + bool operator==(Invalid) { return _node_it==INVALID; }
2.525 + bool operator!=(Invalid) { return _node_it!=INVALID; }
2.526 + /// Next edge
2.527 +
2.528 + /// Next edge.
2.529 + ///
2.530 + MinCutEdgeIt &operator++()
2.531 + {
2.532 + step();
2.533 + while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
2.534 + return *this;
2.535 + }
2.536 + /// Postfix incrementation
2.537 +
2.538 + /// Postfix incrementation.
2.539 + ///
2.540 + /// \warning This incrementation
2.541 + /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect.
2.542 + typename Graph::Arc operator++(int)
2.543 + {
2.544 + typename Graph::Arc e=*this;
2.545 + ++(*this);
2.546 + return e;
2.547 + }
2.548 + };
2.549 +
2.550 + };
2.551 +
2.552 +}
2.553 +
2.554 +#endif
3.1 --- a/test/CMakeLists.txt Wed Mar 04 13:43:05 2009 +0000
3.2 +++ b/test/CMakeLists.txt Wed Mar 04 14:09:45 2009 +0000
3.3 @@ -21,6 +21,7 @@
3.4 edge_set_test
3.5 error_test
3.6 euler_test
3.7 + gomory_hu_test
3.8 graph_copy_test
3.9 graph_test
3.10 graph_utils_test
4.1 --- a/test/Makefile.am Wed Mar 04 13:43:05 2009 +0000
4.2 +++ b/test/Makefile.am Wed Mar 04 14:09:45 2009 +0000
4.3 @@ -17,6 +17,7 @@
4.4 test/edge_set_test \
4.5 test/error_test \
4.6 test/euler_test \
4.7 + test/gomory_hu_test \
4.8 test/graph_copy_test \
4.9 test/graph_test \
4.10 test/graph_utils_test \
4.11 @@ -57,6 +58,7 @@
4.12 test_edge_set_test_SOURCES = test/edge_set_test.cc
4.13 test_error_test_SOURCES = test/error_test.cc
4.14 test_euler_test_SOURCES = test/euler_test.cc
4.15 +test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
4.16 test_graph_copy_test_SOURCES = test/graph_copy_test.cc
4.17 test_graph_test_SOURCES = test/graph_test.cc
4.18 test_graph_utils_test_SOURCES = test/graph_utils_test.cc
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/test/gomory_hu_test.cc Wed Mar 04 14:09:45 2009 +0000
5.3 @@ -0,0 +1,92 @@
5.4 +#include <iostream>
5.5 +
5.6 +#include "test_tools.h"
5.7 +#include <lemon/smart_graph.h>
5.8 +#include <lemon/lgf_reader.h>
5.9 +#include <lemon/gomory_hu.h>
5.10 +#include <cstdlib>
5.11 +
5.12 +using namespace std;
5.13 +using namespace lemon;
5.14 +
5.15 +typedef SmartGraph Graph;
5.16 +
5.17 +char test_lgf[] =
5.18 + "@nodes\n"
5.19 + "label\n"
5.20 + "0\n"
5.21 + "1\n"
5.22 + "2\n"
5.23 + "3\n"
5.24 + "4\n"
5.25 + "@arcs\n"
5.26 + " label capacity\n"
5.27 + "0 1 0 1\n"
5.28 + "1 2 1 1\n"
5.29 + "2 3 2 1\n"
5.30 + "0 3 4 5\n"
5.31 + "0 3 5 10\n"
5.32 + "0 3 6 7\n"
5.33 + "4 2 7 1\n"
5.34 + "@attributes\n"
5.35 + "source 0\n"
5.36 + "target 3\n";
5.37 +
5.38 +GRAPH_TYPEDEFS(Graph);
5.39 +typedef Graph::EdgeMap<int> IntEdgeMap;
5.40 +typedef Graph::NodeMap<bool> BoolNodeMap;
5.41 +
5.42 +int cutValue(const Graph& graph, const BoolNodeMap& cut,
5.43 + const IntEdgeMap& capacity) {
5.44 +
5.45 + int sum = 0;
5.46 + for (EdgeIt e(graph); e != INVALID; ++e) {
5.47 + Node s = graph.u(e);
5.48 + Node t = graph.v(e);
5.49 +
5.50 + if (cut[s] != cut[t]) {
5.51 + sum += capacity[e];
5.52 + }
5.53 + }
5.54 + return sum;
5.55 +}
5.56 +
5.57 +
5.58 +int main() {
5.59 + Graph graph;
5.60 + IntEdgeMap capacity(graph);
5.61 +
5.62 + std::istringstream input(test_lgf);
5.63 + GraphReader<Graph>(graph, input).
5.64 + edgeMap("capacity", capacity).run();
5.65 +
5.66 + GomoryHu<Graph> ght(graph, capacity);
5.67 + ght.run();
5.68 +
5.69 + for (NodeIt u(graph); u != INVALID; ++u) {
5.70 + for (NodeIt v(graph); v != u; ++v) {
5.71 + Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
5.72 + pf.runMinCut();
5.73 + BoolNodeMap cm(graph);
5.74 + ght.minCutMap(u, v, cm);
5.75 + check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
5.76 + check(cm[u] != cm[v], "Wrong cut 3");
5.77 + check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
5.78 +
5.79 + int sum=0;
5.80 + for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
5.81 + sum+=capacity[a];
5.82 + check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
5.83 +
5.84 + sum=0;
5.85 + for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
5.86 + sum++;
5.87 + for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
5.88 + sum++;
5.89 + check(sum == countNodes(graph), "Problem with MinCutNodeIt");
5.90 +
5.91 + }
5.92 + }
5.93 +
5.94 + return 0;
5.95 +}