Ignore:
Timestamp:
04/15/09 09:37:51 (12 years ago)
Branch:
default
Phase:
public
Message:

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

Files:
4 edited

Unmodified
Removed
• ## lemon/gomory_hu.h

 r628 /// 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 /// /// \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" by default. /// \tparam CAP The type of the edge map containing the capacities. /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap". #ifdef DOXYGEN template 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; /// 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 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. /// ///   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 { public: /// Constructor /// Constructor. /// MinCutEdgeIt(GomoryHu const &gomory, ///< The GomoryHu class. You must call its ///< 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.
• ## lemon/hao_orlin.h

 r628 /// \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". /// \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". /// \tparam TOL Tolerance class for handling inexact computations. The /// default tolerance type is \ref Tolerance "Tolerance". #ifdef DOXYGEN #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; 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. /// /// Initializes the internal data structures. It creates /// the maps, residual graph adaptors and some bucket structures /// for the algorithm. /// \brief Initialize the internal data structures. /// /// This function initializes the internal data structures. It creates /// the maps and some bucket structures for the algorithm. /// The first node is used as the source node for the push-relabel /// algorithm. void init() { init(NodeIt(_graph)); } /// \brief Initializes 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. /// \brief Initialize the internal data structures. /// /// This function initializes the internal data structures. It creates /// the maps and some bucket structures for the algorithm. /// The given node is used as the source node for the push-relabel /// algorithm. void init(const Node& source) { _source = source; /// \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. /// /// 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). /// \brief Calculate a minimum cut with \f$source \f$ on the /// sink-side. /// /// This function calculates a minimum cut with \f$source \f$ on the /// sink-side (i.e. a set \f$X\subsetneq V \f$ with /// \f$source \notin X \f$ and minimal outgoing capacity). /// /// \pre \ref init() must be called before using this function. void calculateIn() { findMinCutIn(); /// \brief Runs the algorithm. /// /// Runs the algorithm. It finds nodes \c source and \c target /// arbitrarily and then calls \ref init(), \ref calculateOut() /// \brief Run the algorithm. /// /// This function runs the algorithm. It finds nodes \c source and /// \c target arbitrarily and then calls \ref init(), \ref calculateOut() /// and \ref calculateIn(). void run() { } /// \brief Runs 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(). /// \brief Run the algorithm. /// /// This function runs the algorithm. It uses the given \c source node, /// finds a proper \c target node and then calls the \ref init(), /// \ref calculateOut() and \ref calculateIn(). void run(const Node& s) { init(s); /// \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. /// /// Returns the value of the minimum value cut. /// \brief Return the value of the minimum cut. /// /// This function returns the value of the minimum cut. /// /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() /// must be called before using this function. Value minCutValue() const { return _min_cut; /// \brief Returns 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 Value minCutMap(NodeMap& nodeMap) const { /// \brief Return a minimum cut. /// /// This function sets \c cutMap to the characteristic vector of a /// minimum value cut: it will give a non-empty set \f$X\subsetneq V \f$ /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly /// for the nodes of \f$X \f$). /// /// \param cutMap A \ref concepts::WriteMap "writable" node map with /// \c bool (or convertible) value type. /// /// \return The value of the minimum cut. /// /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() /// must be called before using this function. template 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
• ## test/gomory_hu_test.cc

 r593 #include "test_tools.h" #include #include #include #include #include "target 3\n"; void checkGomoryHuCompile() { typedef int Value; typedef concepts::Graph Graph; typedef Graph::Node Node; typedef Graph::Edge Edge; typedef concepts::ReadMap CapMap; typedef concepts::ReadWriteMap CutMap; Graph g; Node n; CapMap cap; CutMap cut; Value v; int d; GomoryHu gh_test(g, cap); const GomoryHu& 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 IntEdgeMap; 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; sum++; check(sum == countNodes(graph), "Problem with MinCutNodeIt"); } }
• ## test/hao_orlin_test.cc

 r463 #include #include #include #include #include #include #include #include "test_tools.h" "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 CapMap; typedef concepts::WriteMap CutMap; Digraph g; Node n; CapMap cap; CutMap cut; Value v; HaoOrlin ho_test(g, cap); const HaoOrlin& 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 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 capacity(graph); SmartDigraph graph; SmartDigraph::ArcMap cap1(graph), cap2(graph), cap3(graph); SmartDigraph::NodeMap 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 > ho(graph, capacity); ho.run(); check(ho.minCutValue() == 3, "Wrong cut value"); { HaoOrlin 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 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 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 UGraph; UGraph ugraph(graph); { HaoOrlin > 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 > 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 > 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;
Note: See TracChangeset for help on using the changeset viewer.