LEMON/LEMON-official Changeset - r643:293551ad254f

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r643:293551ad254f

« 636:630c48

644:2ca0cd »

r643:293551ad254f

Wed, 15 Apr 2009 09:37:51

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Improvements and fixes for the minimum cut algorithms (#264)

0 4 0

default

4 files changed with 317 insertions and 135 deletions:

lemon/gomory_hu.h

lemon/hao_orlin.h

test/gomory_hu_test.cc

test/hao_orlin_test.cc

130

↑ Collapse diff ↑

lemon/gomory_hu.h

Show inline comments

@@ -21,137 +21,135 @@
 		#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 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), 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 \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
 		  /// the minimum cut and the minimum cut value between any two nodes
 		  /// in the graph. You can also list (iterate on) the nodes and the
 		  /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
 		  ///
 		  /// \tparam GR The type of the undirected graph the algorithm runs on.
 		  /// \tparam CAP The type of the edge map describing the edge capacities.
 		  /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>" by default.
 		  /// \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>
 		#else
 		  template <typename GR,
 			    typename CAP = typename GR::template EdgeMap<int> >
 		#endif
 		  class GomoryHu {
 		  public:
 		    /// The graph type
+		    /// The graph type of the algorithm
 		    typedef GR Graph;
-		    /// The type of the edge capacity map
+		    /// 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;
 		    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
+		    /// 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)
+		    {
 		      checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
+		    }
 		    /// \brief Destructor
 		    ///
 		    /// Destructor
+		    /// Destructor.
 		    ~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);
@@ -194,117 +192,134 @@
 			  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
-		    ///\ref run() "run()" should be called before using them.\n
 		    ///\ref run() should be called before using them.\n
 		    ///See also \ref MinCutNodeIt and \ref 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) {
 		    /// 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 {
 		      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) {
+		    /// 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 {
 		      return (*_weight)[node];
+		    }
 		    /// \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];
+		    }
 		    /// \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 edge on the paths to
 		    /// the ancestor.
 		    /// 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 ((*_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
 		    /// in the \c cutMap parameter by setting the nodes in the component of
 		    /// \c s to \c true and the other nodes to \c false.
 		    ///
-		    /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt.
 		    /// 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.
 		    template <typename CutMap>
-		    Value minCutMap(const Node& s, ///< The base node.
 		    Value minCutMap(const Node& s, ///<
 		                    const Node& t,
-		                    ///< The node you want to separate from node \c s.
 		                    ///<
 		                    CutMap& 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.
 		                    ///<
 		                    ) 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];
+			}
+		      }
@@ -317,49 +332,49 @@
 		      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,
 		    /// 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 cnt=0;
 		    /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
 		    /// \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.
@@ -414,92 +429,96 @@
+		      {
 		        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 \c 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,
 		    /// 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::minCutValue() "gom.minCutValue(s,t)"
 		    /// The result will be the same as the value returned by
 		    /// \ref GomoryHu::minCutValue() "gom.minCutValue(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:
 		      /// Constructor
 		      /// Constructor.
 		      ///
 		      MinCutEdgeIt(GomoryHu const &gomory,
 		                   ///< The GomoryHu class. You must call its
 		                   ///  run() method
 		                   ///  before initializing this iterator.
 		                   const Node& s,  ///< The base node.
 		                   const Node& t,
 		                   ///< The node you want to separate from node \c 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,
 		                   ///  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 \c Arc

lemon/hao_orlin.h

Show inline comments

@@ -10,99 +10,106 @@
 		 * 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_HAO_ORLIN_H
 		#define LEMON_HAO_ORLIN_H
 		#include <vector>
 		#include <list>
 		#include <limits>
 		#include <lemon/maps.h>
 		#include <lemon/core.h>
 		#include <lemon/tolerance.h>
 		/// \file
 		/// \ingroup min_cut
 		/// \brief Implementation of the Hao-Orlin algorithm.
 		///
 		/// Implementation of the Hao-Orlin algorithm class for testing network
 		/// reliability.
 		/// Implementation of the Hao-Orlin algorithm for finding a minimum cut
 		/// in a digraph.
 		namespace lemon {
 		  /// \ingroup min_cut
 		  ///
-		  /// \brief %Hao-Orlin algorithm to find a minimum cut in directed graphs.
+		  /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph.
 		  ///
 		  /// Hao-Orlin calculates a minimum cut in a directed graph
 		  /// \f$D=(V,A)\f$. It takes a fixed node \f$ source \in V \f$ and
 		  /// 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
 		  /// consists of two phases: in the first phase it determines a
 		  /// minimum cut with \f$ source \f$ on the source-side (i.e. a set
 		  /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal
 		  /// out-degree) and in the second phase it determines a minimum cut
 		  /// \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
 		  /// 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
 		  /// out-degree). Obviously, the smaller of these two cuts will be a
 		  /// \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
 		  /// minimum cut of \f$ D \f$. The algorithm is a modified
-		  /// push-relabel preflow algorithm and our implementation calculates
+		  /// preflow push-relabel algorithm. Our implementation calculates
 		  /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
 		  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
 		  /// purpose of such algorithm is 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.
 		  /// purpose of such algorithm is e.g. testing network reliability.
 		  ///
 		  /// \param GR The digraph class the algorithm runs on.
 		  /// \param CAP An arc map of capacities which can be any numreric type.
 		  /// The default type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \param TOL Tolerance class for handling inexact computations. The
 		  /// 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
 		  /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename CAP, typename TOL>
 		#else
 		  template <typename GR,
 		            typename CAP = typename GR::template ArcMap<int>,
 		            typename TOL = Tolerance<typename CAP::Value> >
 		#endif
 		  class HaoOrlin {
 		  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;
 		  private:
 		    typedef GR Digraph;
 		    typedef CAP CapacityMap;
 		    typedef TOL Tolerance;
 		    typedef typename CapacityMap::Value Value;
-		    TEMPLATE_GRAPH_TYPEDEFS(Digraph);
+		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    const Digraph& _graph;
 		    const CapacityMap* _capacity;
 		    typedef typename Digraph::template ArcMap<Value> FlowMap;
 		    FlowMap* _flow;
 		    Node _source;
 		    int _node_num;
 		    // Bucketing structure
 		    std::vector<Node> _first, _last;
 		    typename Digraph::template NodeMap<Node>* _next;
 		    typename Digraph::template NodeMap<Node>* _prev;
 		    typename Digraph::template NodeMap<bool>* _active;
 		    typename Digraph::template NodeMap<int>* _bucket;
 		    std::vector<bool> _dormant;
 		    std::list<std::list<int> > _sets;
 		    std::list<int>::iterator _highest;
 		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
@@ -794,173 +801,186 @@
 		            Node v = _graph.target(a);
 		            if (!(*_active)[v] && !(*_source_set)[v]) {
 		              activate(v);
+		            }
 		            (*_excess)[v] += rem;
 		            (*_flow)[a] = 0;
+		          }
 		          target = new_target;
 		          if ((*_active)[target]) {
 		            deactivate(target);
+		          }
 		          _highest = _sets.back().begin();
 		          while (_highest != _sets.back().end() &&
 		                 !(*_active)[_first[*_highest]]) {
 		            ++_highest;
+		          }
+		        }
+		      }
+		    }
 		  public:
-		    /// \name Execution control
+		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to use
 		    /// one of the member functions called \ref run().
 		    /// \n
 		    /// If you need more control on the execution,
 		    /// first you must call \ref init(), then the \ref calculateIn() or
-		    /// \ref calculateOut() functions.
+		    /// 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 Initializes the internal data structures.
+		    /// \brief Initialize the internal data structures.
 		    ///
 		    /// Initializes the internal data structures. It creates
 		    /// the maps, residual graph adaptors and some bucket structures
-		    /// for the algorithm.
+		    /// 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.
 		    void init() {
 		      init(NodeIt(_graph));
+		    }
-		    /// \brief Initializes the internal data structures.
+		    /// \brief Initialize the internal data structures.
 		    ///
 		    /// Initializes the internal data structures. It creates
 		    /// the maps, residual graph adaptor and some bucket structures
 		    /// for the algorithm. Node \c source  is used as the push-relabel
 		    /// algorithm's source.
 		    /// 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.
 		    void init(const Node& source) {
 		      _source = source;
 		      _node_num = countNodes(_graph);
 		      _first.resize(_node_num);
 		      _last.resize(_node_num);
 		      _dormant.resize(_node_num);
 		      if (!_flow) {
 		        _flow = new FlowMap(_graph);
+		      }
 		      if (!_next) {
 		        _next = new typename Digraph::template NodeMap<Node>(_graph);
+		      }
 		      if (!_prev) {
 		        _prev = new typename Digraph::template NodeMap<Node>(_graph);
+		      }
 		      if (!_active) {
 		        _active = new typename Digraph::template NodeMap<bool>(_graph);
+		      }
 		      if (!_bucket) {
 		        _bucket = new typename Digraph::template NodeMap<int>(_graph);
+		      }
 		      if (!_excess) {
 		        _excess = new ExcessMap(_graph);
+		      }
 		      if (!_source_set) {
 		        _source_set = new SourceSetMap(_graph);
+		      }
 		      if (!_min_cut_map) {
 		        _min_cut_map = new MinCutMap(_graph);
+		      }
 		      _min_cut = std::numeric_limits<Value>::max();
+		    }
-		    /// \brief Calculates a minimum cut with \f$ source \f$ on the
+		    /// \brief Calculate a minimum cut with \f$ source \f$ on the
 		    /// source-side.
 		    ///
-		    /// Calculates a minimum cut with \f$ source \f$ on the
+		    /// This function calculates a minimum cut with \f$ source \f$ on the
 		    /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
-		    /// \f$ source \in X \f$ and minimal out-degree).
+		    /// \f$ source \in X \f$ and minimal outgoing capacity).
 		    ///
 		    /// \pre \ref init() must be called before using this function.
 		    void calculateOut() {
 		      findMinCutOut();
+		    }
 		    /// \brief Calculates a minimum cut with \f$ source \f$ on the
 		    /// target-side.
 		    /// \brief Calculate a minimum cut with \f$ source \f$ on the
 		    /// sink-side.
 		    ///
 		    /// Calculates a minimum cut with \f$ source \f$ on the
 		    /// target-side (i.e. a set \f$ X\subsetneq V \f$ with
-		    /// \f$ source \in X \f$ and minimal out-degree).
+		    /// 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.
 		    void calculateIn() {
 		      findMinCutIn();
+		    }
-		    /// \brief Runs the algorithm.
+		    /// \brief Run the algorithm.
 		    ///
 		    /// Runs the algorithm. It finds nodes \c source and \c target
 		    /// arbitrarily and then calls \ref init(), \ref calculateOut()
 		    /// This function runs the algorithm. It finds nodes \c source and
 		    /// \c target arbitrarily and then calls \ref init(), \ref calculateOut()
 		    /// and \ref calculateIn().
 		    void run() {
 		      init();
 		      calculateOut();
 		      calculateIn();
+		    }
-		    /// \brief Runs the algorithm.
+		    /// \brief Run the algorithm.
 		    ///
 		    /// Runs the algorithm. It uses the given \c source node, finds a
 		    /// proper \c target and then calls the \ref init(), \ref
-		    /// calculateOut() and \ref calculateIn().
+		    /// 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().
 		    void run(const Node& s) {
 		      init(s);
 		      calculateOut();
 		      calculateIn();
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The result of the %HaoOrlin algorithm
 		    /// can be obtained using these functions.
 		    /// \n
 		    /// Before using these functions, either \ref run(), \ref
 		    /// calculateOut() or \ref calculateIn() must be called.
 		    /// can be obtained using these functions.\n
 		    /// \ref run(), \ref calculateOut() or \ref calculateIn()
 		    /// should be called before using them.
 		    /// @{
-		    /// \brief Returns the value of the minimum value cut.
+		    /// \brief Return the value of the minimum cut.
 		    ///
-		    /// Returns the value of the minimum value 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.
 		    Value minCutValue() const {
 		      return _min_cut;
+		    }
-		    /// \brief Returns a minimum cut.
+		    /// \brief Return a minimum cut.
 		    ///
 		    /// Sets \c nodeMap to the characteristic vector of a minimum
 		    /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$
 		    /// with minimal out-degree (i.e. \c nodeMap will be true exactly
 		    /// for the nodes of \f$ X \f$).  \pre nodeMap should be a
 		    /// bool-valued node-map.
 		    template <typename NodeMap>
-		    Value minCutMap(NodeMap& nodeMap) const {
+		    /// 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 {
 		      for (NodeIt it(_graph); it != INVALID; ++it) {
-		        nodeMap.set(it, (*_min_cut_map)[it]);
+		        cutMap.set(it, (*_min_cut_map)[it]);
+		      }
 		      return _min_cut;
+		    }
 		    /// @}
 		  }; //class HaoOrlin
 		} //namespace lemon
 		#endif //LEMON_HAO_ORLIN_H

test/gomory_hu_test.cc

Show inline comments

 		#include <iostream>
 		#include "test_tools.h"
 		#include <lemon/smart_graph.h>
 		#include <lemon/concepts/graph.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/gomory_hu.h>
 		#include <cstdlib>
 		using namespace std;
 		using namespace lemon;
 		typedef SmartGraph Graph;
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "@arcs\n"
 		  "     label capacity\n"
 		  "0 1  0     1\n"
 		  "1 2  1     1\n"
 		  "2 3  2     1\n"
 		  "0 3  4     5\n"
 		  "0 3  5     10\n"
 		  "0 3  6     7\n"
 		  "4 2  7     1\n"
 		  "@attributes\n"
 		  "source 0\n"
 		  "target 3\n";
 		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);
+		}
 		GRAPH_TYPEDEFS(Graph);
 		typedef Graph::EdgeMap<int> IntEdgeMap;
 		typedef Graph::NodeMap<bool> BoolNodeMap;
 		int cutValue(const Graph& graph, const BoolNodeMap& cut,
 			     const IntEdgeMap& capacity) {
 		  int sum = 0;
 		  for (EdgeIt e(graph); e != INVALID; ++e) {
 		    Node s = graph.u(e);
 		    Node t = graph.v(e);
 		    if (cut[s] != cut[t]) {
 		      sum += capacity[e];
+		    }
+		  }
 		  return sum;
+		}
 		int main() {
 		  Graph graph;
 		  IntEdgeMap capacity(graph);
 		  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();
 		      BoolNodeMap cm(graph);
 		      ght.minCutMap(u, v, cm);
 		      check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
 		      check(cm[u] != cm[v], "Wrong cut 3");
 		      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
 		      check(cm[u] != cm[v], "Wrong cut 2");
 		      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
 		      int sum=0;
 		      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(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
 		        sum++;
 		      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
 		        sum++;
 		      check(sum == countNodes(graph), "Problem with MinCutNodeIt");
+		    }
+		  }
 		  return 0;
+		}

test/hao_orlin_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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.
+		 *
 		 */
 		#include <sstream>
 		#include <lemon/smart_graph.h>
 		#include <lemon/adaptors.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/hao_orlin.h>
 		#include <lemon/lgf_reader.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace std;
 		const std::string lgf =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "@edges\n"
 		  "     label  capacity\n"
 		  "0 1  0      2\n"
 		  "1 2  1      2\n"
 		  "2 0  2      2\n"
 		  "3 4  3      2\n"
 		  "4 5  4      2\n"
 		  "5 3  5      2\n"
 		  "2 3  6      3\n";
 		  "     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;
+		}
 		int main() {
 		  SmartGraph graph;
 		  SmartGraph::EdgeMap<int> capacity(graph);
 		  SmartDigraph graph;
 		  SmartDigraph::ArcMap<int> cap1(graph), cap2(graph), cap3(graph);
 		  SmartDigraph::NodeMap<bool> cut(graph);
 		  istringstream lgfs(lgf);
 		  graphReader(graph, lgfs).
-		    edgeMap("capacity", capacity).run();
+		  istringstream input(lgf);
 		  digraphReader(graph, input)
 		    .arcMap("cap1", cap1)
 		    .arcMap("cap2", cap2)
 		    .arcMap("cap3", cap3)
 		    .run();
 		  HaoOrlin<SmartGraph, SmartGraph::EdgeMap<int> > ho(graph, capacity);
 		  ho.run();
 		  check(ho.minCutValue() == 3, "Wrong cut value");
+		  {
 		    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");
+		  }
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account