Changeset 596:293551ad254f in lemon-1.2 for lemon/gomory_hu.h
- Timestamp:
- 04/15/09 09:37:51 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
-
lemon/gomory_hu.h (modified) (14 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/gomory_hu.h
r581 r596 43 43 /// between these nodes. Moreover the components obtained by removing 44 44 /// this edge from the tree determine the corresponding minimum cut. 45 ///46 45 /// Therefore once this tree is computed, the minimum cut between any pair 47 46 /// of nodes can easily be obtained. 48 47 /// 49 48 /// The algorithm calculates \e n-1 distinct minimum cuts (currently with 50 /// the \ref Preflow algorithm), therefore the algorithm has 51 /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a 52 /// rooted Gomory-Hu tree, its structure and the weights can be obtained 53 /// by \c predNode(), \c predValue() and \c rootDist(). 54 /// 55 /// The members \c minCutMap() and \c minCutValue() calculate 49 /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall 50 /// time complexity. It calculates a rooted Gomory-Hu tree. 51 /// The structure of the tree and the edge weights can be 52 /// obtained using \c predNode(), \c predValue() and \c rootDist(). 53 /// The functions \c minCutMap() and \c minCutValue() calculate 56 54 /// the minimum cut and the minimum cut value between any two nodes 57 55 /// in the graph. You can also list (iterate on) the nodes and the … … 59 57 /// 60 58 /// \tparam GR The type of the undirected graph the algorithm runs on. 61 /// \tparam CAP The type of the edge map describing the edge capacities.62 /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>" by default.59 /// \tparam CAP The type of the edge map containing the capacities. 60 /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". 63 61 #ifdef DOXYGEN 64 62 template <typename GR, … … 71 69 public: 72 70 73 /// The graph type 71 /// The graph type of the algorithm 74 72 typedef GR Graph; 75 /// The type of the edge capacity map73 /// The capacity map type of the algorithm 76 74 typedef CAP Capacity; 77 75 /// The value type of capacities … … 118 116 /// \brief Constructor 119 117 /// 120 /// Constructor 118 /// Constructor. 121 119 /// \param graph The undirected graph the algorithm runs on. 122 120 /// \param capacity The edge capacity map. … … 131 129 /// \brief Destructor 132 130 /// 133 /// Destructor 131 /// Destructor. 134 132 ~GomoryHu() { 135 133 destroyStructures(); … … 216 214 ///The results of the algorithm can be obtained using these 217 215 ///functions.\n 218 ///\ref run() "run()"should be called before using them.\n216 ///\ref run() should be called before using them.\n 219 217 ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt. 220 218 … … 223 221 /// \brief Return the predecessor node in the Gomory-Hu tree. 224 222 /// 225 /// This function returns the predecessor node in the Gomory-Hu tree. 226 /// If the node is 227 /// the root of the Gomory-Hu tree, then it returns \c INVALID. 228 Node predNode(const Node& node) { 223 /// This function returns the predecessor node of the given node 224 /// in the Gomory-Hu tree. 225 /// If \c node is the root of the tree, then it returns \c INVALID. 226 /// 227 /// \pre \ref run() must be called before using this function. 228 Node predNode(const Node& node) const { 229 229 return (*_pred)[node]; 230 }231 232 /// \brief Return the distance from the root node in the Gomory-Hu tree.233 ///234 /// This function returns the distance of \c node from the root node235 /// in the Gomory-Hu tree.236 int rootDist(const Node& node) {237 return (*_order)[node];238 230 } 239 231 … … 241 233 /// Gomory-Hu tree. 242 234 /// 243 /// This function returns the weight of the predecessor edge in the 244 /// Gomory-Hu tree. If the node is the root, the result is undefined. 245 Value predValue(const Node& node) { 235 /// This function returns the weight of the predecessor edge of the 236 /// given node in the Gomory-Hu tree. 237 /// If \c node is the root of the tree, the result is undefined. 238 /// 239 /// \pre \ref run() must be called before using this function. 240 Value predValue(const Node& node) const { 246 241 return (*_weight)[node]; 247 242 } 248 243 244 /// \brief Return the distance from the root node in the Gomory-Hu tree. 245 /// 246 /// This function returns the distance of the given node from the root 247 /// node in the Gomory-Hu tree. 248 /// 249 /// \pre \ref run() must be called before using this function. 250 int rootDist(const Node& node) const { 251 return (*_order)[node]; 252 } 253 249 254 /// \brief Return the minimum cut value between two nodes 250 255 /// 251 /// This function returns the minimum cut value between two nodes. The 252 /// algorithm finds the nearest common ancestor in the Gomory-Hu 253 /// tree and calculates the minimum weight edge on the paths to 254 /// the ancestor. 256 /// This function returns the minimum cut value between the nodes 257 /// \c s and \c t. 258 /// It finds the nearest common ancestor of the given nodes in the 259 /// Gomory-Hu tree and calculates the minimum weight edge on the 260 /// paths to the ancestor. 261 /// 262 /// \pre \ref run() must be called before using this function. 255 263 Value minCutValue(const Node& s, const Node& t) const { 256 264 Node sn = s, tn = t; … … 275 283 /// \c s to \c true and the other nodes to \c false. 276 284 /// 277 /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt. 285 /// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt. 286 /// 287 /// \param s The base node. 288 /// \param t The node you want to separate from node \c s. 289 /// \param cutMap The cut will be returned in this map. 290 /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap 291 /// "ReadWriteMap" on the graph nodes. 292 /// 293 /// \return The value of the minimum cut between \c s and \c t. 294 /// 295 /// \pre \ref run() must be called before using this function. 278 296 template <typename CutMap> 279 Value minCutMap(const Node& s, ///< The base node.297 Value minCutMap(const Node& s, ///< 280 298 const Node& t, 281 ///< The node you want to separate from node \c s.299 ///< 282 300 CutMap& cutMap 283 ///< The cut will be returned in this map. 284 /// It must be a \c bool (or convertible) 285 /// \ref concepts::ReadWriteMap "ReadWriteMap" 286 /// on the graph nodes. 301 ///< 287 302 ) const { 288 303 Node sn = s, tn = t; … … 339 354 340 355 /// This iterator class lists the nodes of a minimum cut found by 341 /// GomoryHu. Before using it, you must allocate a GomoryHu class ,356 /// GomoryHu. Before using it, you must allocate a GomoryHu class 342 357 /// and call its \ref GomoryHu::run() "run()" method. 343 358 /// … … 436 451 437 452 /// This iterator class lists the edges of a minimum cut found by 438 /// GomoryHu. Before using it, you must allocate a GomoryHu class ,453 /// GomoryHu. Before using it, you must allocate a GomoryHu class 439 454 /// and call its \ref GomoryHu::run() "run()" method. 440 455 /// … … 448 463 /// value+=capacities[e]; 449 464 /// \endcode 450 /// the result will be the same as it isreturned by451 /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)" 465 /// The result will be the same as the value returned by 466 /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)". 452 467 class MinCutEdgeIt 453 468 { … … 469 484 470 485 public: 486 /// Constructor 487 488 /// Constructor. 489 /// 471 490 MinCutEdgeIt(GomoryHu const &gomory, 472 491 ///< The GomoryHu class. You must call its … … 479 498 ///< If it is \c true (default) then the listed arcs 480 499 /// will be oriented from the 481 /// thenodes of the component containing \c s,500 /// nodes of the component containing \c s, 482 501 /// otherwise they will be oriented in the opposite 483 502 /// direction.
Note: See TracChangeset
for help on using the changeset viewer.
