# Changeset 591:ccd2d3a3001e in lemon

Ignore:
Timestamp:
02/25/09 12:10:52 (10 years ago)
Branch:
default
Phase:
public
Message:

Cut iterators for GomoryHuTree? + doc cleanup + bug fixes (#66)

Files:
2 edited

Unmodified
Removed
• ## lemon/gomory_hu_tree.h

 r590 #include #include #include #include /// \brief Gomory-Hu cut tree algorithm /// /// The Gomory-Hu tree is a tree on the nodeset of the digraph, but it /// may contain arcs which are not in the original digraph. It helps /// to calculate the minimum cut between all pairs of nodes, because /// the minimum capacity arc on the tree path between two nodes has /// the same weight as the minimum cut in the digraph between these /// nodes. Moreover this arc separates the nodes to two parts which /// determine this minimum cut. /// 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 distinict minimum cuts with /// preflow algorithm, therefore the algorithm has /// 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, the structure of the tree and the weights /// can be obtained with \c predNode() and \c predValue() /// functions. The \c minCutValue() and \c minCutMap() calculates /// 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. template > /// 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 by default. template > class GomoryHuTree { public: /// The graph type typedef _Graph Graph; /// The capacity on edges typedef _Capacity Capacity; typedef GR Graph; /// The type if the edge capacity map typedef CAP Capacity; /// The value type of capacities typedef typename Capacity::Value Value; /// /// Constructor /// \param graph The graph type. /// \param graph The graph the algorithm will run on. /// \param capacity The capacity map. GomoryHuTree(const Graph& graph, const Capacity& capacity) } /// \brief Initializes the internal data structures. /// /// Initializes the internal data structures. /// // \brief Initialize the internal data structures. // // This function initializes the internal data structures. // void init() { createStructures(); /// \brief Starts the algorithm /// /// Starts the algorithm. // \brief Start the algorithm // // This function starts the algorithm. // // \pre \ref init() must be called before using this function. // void start() { Preflow fa(_graph, _capacity, _root, INVALID); } /// \brief Runs the Gomory-Hu algorithm. /// /// Runs the Gomory-Hu algorithm. /// \note gh.run() is just a shortcut of the following code. /// \code ///   ght.init(); ///   ght.start(); /// \endcode ///\name Execution Control ///@{ /// \brief Run the Gomory-Hu algorithm. /// /// This function runs the Gomory-Hu algorithm. void run() { init(); start(); } /// \brief Returns the predecessor node in the Gomory-Hu tree. /// /// Returns the predecessor node in the Gomory-Hu tree. If the node is /// @} ///\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) { } /// \brief Returns the weight of the predecessor arc in the /// \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. /// /// Returns the weight of the predecessor arc in the Gomory-Hu /// tree.  If the node is the root of the Gomory-Hu tree, the /// result is undefined. /// 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 Returns the minimum cut value between two nodes /// /// Returns the minimum cut value between two nodes. The /// \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 while (sn != tn) { if ((*_order)[sn] < (*_order)[tn]) { if ((*_weight)[tn] < value) value = (*_weight)[tn]; if ((*_weight)[tn] <= value) value = (*_weight)[tn]; tn = (*_pred)[tn]; } else { if ((*_weight)[sn] < value) value = (*_weight)[sn]; if ((*_weight)[sn] <= value) value = (*_weight)[sn]; sn = (*_pred)[sn]; } } /// \brief Returns the minimum cut between two nodes /// /// 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. Then it sets all nodes to the cut determined by /// this arc. The \c cutMap should be \ref concepts::ReadWriteMap /// \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 Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const { 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::max(); while (sn != tn) { if ((*_order)[sn] < (*_order)[tn]) { if ((*_weight)[tn] < value) { if ((*_weight)[tn] <= value) { rn = tn; s_root = false; value = (*_weight)[tn]; } tn = (*_pred)[tn]; } else { if ((*_weight)[sn] < value) { if ((*_weight)[sn] <= value) { rn = sn; s_root = true; value = (*_weight)[sn]; } typename Graph::template NodeMap reached(_graph, false); reached.set(_root, true); cutMap.set(_root, false); cutMap.set(_root, !s_root); reached.set(rn, true); cutMap.set(rn, true); cutMap.set(rn, s_root); std::vector st; for (NodeIt n(_graph); n != INVALID; ++n) { std::vector st; Node nn = n; st.clear(); Node nn = n; while (!reached[nn]) { st.push_back(nn); } ///@} 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 gom(g, capacities); /// gom.run(); /// int sum=0; /// for(GomoruHuTree::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum; /// \endcode class MinCutNodeIt { bool _side; typename Graph::NodeIt _node_it; typename Graph::template NodeMap _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 gom(g, capacities); /// gom.run(); /// int value=0; /// for(GomoruHuTree::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 _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; } }; };
• ## test/gomory_hu_test.cc

 r590 #include "test_tools.h" #include #include #include #include #include #include #include #include check(cm[u] != cm[v], "Wrong cut 3"); check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2"); int sum=0; for(GomoryHuTree::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a) sum+=capacity[a]; check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt"); sum=0; for(GomoryHuTree::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n) sum++; for(GomoryHuTree::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n) sum++; check(sum == countNodes(graph), "Problem with MinCutNodeIt"); }
Note: See TracChangeset for help on using the changeset viewer.